CHURP: Dynamic-Committee Proactive Secret Sharing
Introducing CHURP, a decentralized key management system.
The Oasis Tech Series focuses on new, exciting work being done in data privacy and security both on the Oasis Network and elsewhere. This week we bring you CHURP: Dynamic-Committee Proactive Secret Sharing (to appear in The 26th ACM Conference on Computer and Communications Security, Nov 11–15, 2019), a research project initially conducted by Sai Krishna Deepak Maram, Fan Zhang, Lun Wang, Andrew Low, Yupeng Zhang, Ari Juels, and Dawn Song. Lun was an intern at Oasis this summer and started initial implementation on the network while here. The Oasis Team has plans to further implement this in the future as well.
If you’re interested in learning more, Lun will also be giving at talk at CESC as a part of SF Blockchain Week on October 28. More details here.
Secure storage of private keys is a pervasive challenge in cryptographic systems. It is especially acute for blockchains and other decentralized systems. In these systems, private keys control the most important resources — money, identities, etc. Their loss has serious and often irreversible consequences. For example, an estimated four million Bitcoin (today worth $14+ Billion) has vanished due to lost keys. As a result, many users store their cryptocurrency with exchanges such as Coinbase, which holds at least 10% of all circulating Bitcoin. But such centralized key storage is also undesirable because it erodes the very decentralization that defines blockchain systems.
One simple solution to the lost key problem is to backup the key on multiple servers. However, making backup copies increases risks of key disclosure. For instance, an attacker can launch a compromising attack on the servers based on a vulnerability. If one of the server is compromised, the attacker can obtain access to the keys and transfer coins without authorization. Taking a step back to assess the solution of centralized backup, one can see that the origin of the disclosure risk roots in that we place all our trust on each backup of the key. In this case, if one of the servers gets compromised, the trust of the whole system is completely destroyed. One way to address this issue is to split trust among multiple entities.
This requirement of distributing trust is widely studied in cryptography under the name “secret-sharing”. In our scenario, the method of secret sharing distributes the sensitive key among servers, each of whom is allocated a share of the key. However, traditional secret sharing still faces the risk of disclosure if the attacker can compromise enough (more than a threshold) servers in the long term.
In this blogpost we introduce a churn-robust proactive¹ secret-sharing protocol that lowers the risk of disclosure by updating the secret shares on servers and rotating servers periodically. Based on the protocol, we design a decentralized key management system namely CHURP that addresses most of the issues discussed above.
What is CHURP?
Briefly speaking, CHURP is a key management system that provides two core properties:
- Security: private keys managed by CHURP are hard to compromise.
- Availability: the system is able to provide the user with a copy of their own key when requested.
CHURP manages to achieve the above two properties based on the following assumptions:
- Adversaries are only able to compromise up to a fixed number of network nodes within a certain period.
- Cryptographic assumptions that are needed for the underlying cryptographic primitives in CHURP such as t-Bilinear Strong Diffie-Hellman (t-BSDH) assumption.
With these assumptions in hand, we designed CHURP in a decentralized architecture which helps prevent loss of a key due to putting all trust in a single entity². Instead the key is distributed among a management committee with a large number of nodes. Stealing a key in this system requires someone to control more than half of the servers in the committee. Thus CHURP helps prevent an adversary from stealing the key since he needs to compromise a large number of servers.
Although compromising a large number of nodes in a short time is difficult, it is still possible if the committee does not change frequently enough. Since the member list of the committee is typically public³, the adversary can launch targeted attacks on the member nodes one by one until he gets control of enough nodes to steal the secret. In order to address this challenge, we also require our committee to proactively update its members and secret shares. The name of our protocol, CHURP (CHUrn-Robust Proactive Secret Sharing), captures all these hardening properties.
System Workflow
The system architecture of CHURP is composed of many decentralized servers over the network called a committee. A server can join and leave the committee as they like. As shown in Figure 1, the workflow of CHURP is divided into three phases:
- Key distribution: The user creates secret channels (e.g. TLS channel) with CHURP servers and sends initial key shares to them.
- Share update: The CHURP committee updates the key shares and rotates the committee members periodically.
- Key retrieval: When the user needs the key, each CHURP committee node sends the key share back to the user via a secret channel. The user recovers the key locally.
Churn-Robust Proactive Secret Sharing Protocol
In order to achieve the goals mentioned at the beginning of this blog, we designed a new secret sharing protocol as the basis for the CHURP system. In the blogpost we only outline some key design principles and techniques used in the protocol. If you are interested in learning more about the details and the rigorous cryptographic analysis of our constructions, you can read our paper at CCS’19.
Low Communication Complexity
Compared with other proactive secret sharing protocols, the main advantage of our protocol is its low communication complexity. The term communication complexity describes the number of bytes transferred over the network during the execution of the protocol. Specifically, we care about two kinds of communication complexity in CHURP: (1) on-chain complexity: how many bytes we put on blockchain, (2) off-chain complexity: how many bytes we transfer in the peer-to-peer network.
Specifically, CHURP has O(n) on-chain complexity and O(n²) off-chain complexity in optimistic path⁴. While the on-chain complexity is lower than the off-chain, it comes with the additional cost of placing transactions on the blockchain. In the presence of cheating nodes the on-chain communication complexity drops to O(n²) without any additionally off-chain cost. Both communication costs are substantially lower than any previously proposed scheme. Table 1 includes detailed comparison between CHURP and other secret sharing protocols in terms of communication complexity and other useful properties like if the protocol deals with dynamic committee and active adversary, etc.
KZG Commitment Scheme
Commitment scheme is a cryptographic primitive that is heavily used in most proactive secret sharing protocols. It enables one to commit to a chosen value while keeping the value hidden to others and reveal it later. One of the main reasons that CHURP has lower complexity is that we leverage a new polynomial commitment scheme introduced by Kate, Zaverucha, and Goldberg (KZG). This exciting commitment scheme has a constant commitment size of O(1) compared with classical schemes with per-commitment size O(t), where t is the degree of the polynomial. We omit the details of the commitment scheme here and refer interested readers to the original paper.
Bivariate Polynomial Secret Sharing
Recall that the key shares are updated periodically in CHURP. Another challenge we faced when designing CHURP is that during an update, the old committee has to hand off the key shares to the new committee. During this handoff period, the adversary may compromise part of the old committee and part of the new committee to steal or destroy the key without compromising more than the threshold of servers in each committee. Previous schemes address this problem with costly communication. CHURP introduces a novel, low communication-complexity technique called dimension-switching. It uses an asymmetric bivariate polynomial B(x, y), i.e., a polynomial with two variables x, y, and degree t (same as the underlying threshold) in one dimension and degree 2t in the other dimension. During a handoff, we switch temporarily to a (2t,n)-sharing to tolerate up to 2t compromised shares; afterwards, it switches back to a (t,n)-sharing.
Point-To-Point Communication Technique
Recall that in CHURP, we need P2P communication channels between committee servers. However, due to the frequent churn of the committee, the communication channels should be easy to maintain in this scenario. Off-chain P2P channels can be implemented in different ways depending on the deployment environment. However, in a decentralized setting, establishing direct off-chain connection between nodes is undesirable, as it would compromise nodes’ anonymity. Revealing network-layer identities (e.g., IP addresses) would also be dangerous, as it could lead to targeted attacks. Anonymizing overlay networks, such as Tor will incur the cost of additional setup and engineering complexity when facing committee churn.
Alternatively, off-chain channels can be implemented as an overlay on existing blockchain infrastructure. In this section, we introduce Transaction Ghosting, a technique for cheap P2P messaging on a blockchain. The key insight to reduce cost is to overwrite transactions so that they are broadcast, but subsequently dropped by the network. Most of these transactions — and their embedded messages — are then essentially broadcast for free. We focus on Ethereum, but similar techniques can apply to other blockchains, e.g., Bitcoin.
Transaction Ghosting
A (simplified) Ethereum transaction tx = (n,m,g) includes a nonce n, payload m, and a per-byte gas price g paid to the miner of tx. For a basic (“send”) transaction, Alice pays a miner f_0 + |m| × g, where f_0 is a base transaction cost and |m| is the payload size. Alice sends tx to network peers, who add tx to their pools of unconfirmed transactions, known as the mempool. They propagate tx so that it can be included ultimately in all peers’ view of the mempool. tx remains in the mempool until a miner includes it in a block, at which point it is removed and f_0 + |m| × g units of currency is transferred from Alice to the miner. The key observation is, until tx is mined, Alice can overwrite it with another transaction tx′ . When this happens, tx is dropped from the mempool. Thus, both tx and tx′ are propagated to all nodes, but Alice only pays for tx′ . Two additional techniques can further reduce costs. Alice can embed m in tx only, putting no message data in tx′ . She then pays nothing for the data containing m, only the cost associated with tx′ . This technique also generalizes to multiple overwrites, i.e., Alice can embed a large message m in multiple transactions {tx_i}, i∈[k−1], which is useful given bounds (e.g., 32kB in Ethereum) on transaction sizes. Alice will only pay the cost of the final transaction tx_k.
Implementation
We now have started an initial implementation of CHURP at Oasis Labs. It is in about 5,000 lines of Go. This implementation inherits part of the utility library in the previous academic research open-source repo but completely refactors the protocol itself to address many issues including bugs in the previous version and provides a more complete implementation of the protocol as well. Our cryptographic primitives are implemented using the GNU Multiprecision Library and the Pairing-Based Cryptography Library. Network infrastructure is implemented with gRPC. We plan to integrate CHURP in Oasis Network in the future.
Performance Evaluation
In our evaluation, experiments are run in a distributed network of up to 1000 EC2 c5.large instances, each with 2 vCPU and 4GB of memory. Each instance acts as a node in the committee and the handoff protocol is executed assuming a static committee. All experiments are averaged over 1000 epochs, i.e., 1000 invocations of optimistic path of CHURP. We measure the latency (the total execution time) and the evaluation results are presented below.
Latency: In the first set of experiments, all EC2 instances belong to the same region, also referred to as the LAN setting. This setting is useful to understand the computation time of optimistic path of CHURP, results are presented in Fig. 2. The experimental results show a quadratic increase consistent with the O(n²) asymptotic computational complexity of CHURP and suggests a low constant. In the second set of experiments, we select EC2 instances across multiple regions in US, Canada, Asia and Europe, also referred to as the WAN setting. In this setting the network latency is relatively unstable, although even in the worst-case it is still sub-second. Hence, during a handoff of the optimistic path of CHURP in the WAN setting, we expect a constant increase in the latency over the LAN setting. Moreover, we expect this constant to be relatively small compared to the time spent in computation. We validate our hypothesis — for a committee size of 100, the WAN latency is 4.54 seconds while the LAN latency is 2.92 seconds (Fig. 2), i.e., the additional time spent in network latency is around 1.6 seconds and constant across different committee sizes as expected.
Summary
We have introduced CHURP, a dynamic committee secret-sharing scheme with several technical innovations: an efficient proactivization scheme for bivariate polynomials and the use of dimension switching technique to tolerate threshold change during share handoff. CHURP achieves extremely low communication complexity compared to existing schemes: O(n) on-chain and O(n²) off-chain in the optimistic case. To learn more about CHURP, you can read our full paper here.
[1] Proactive means the secret shares are updated periodically.
[2] CHURP is a threshold secret sharing protocol which means the adversary has to compromise up to a threshold of servers to either steal or destroy the secret.
[3] A fact that stems from the need to implement a peer-to-peer communication protocol for the committee servers in which case all the IP addresses are published on the blockchain.
[4] CHURP is a layered protocol. By default it runs in optimistic path. When the correctness checking in the optimistic path fails, it will deviate to pessimistic paths with higher communication complexity: O(n²) on chain.
