Our recent paper, a joint effort between the Zengo (KZen) research team, Claudio Orlandi, Bernardo Magri, and Yashvanth Kondi, is about proactive security and how it applies to threshold wallets. In this technical blog post we will give background on threshold wallets, illustrate our research using real world examples, and present our protocol and its main properties.
Tl;dr: Secret shares can be updated with any threshold. Other parties can remain offline and update their secret when they return.
Threshold Wallets
A wallet is client side software responsible for communication with a blockchain and for managing users’ keys. A threshold wallet is a distributed wallet which is not controlled by a single party, but by a set of parties according to some access structure. Often the access structure simply says that a set of signers larger than the threshold t (out of a total set of n signers possible signers) is required to complete a signature. This can be implemented with Mutlisig if the wallet is for a single chain that has Multisig support (e.g. Bitcoin). But in most cases, using Threshold Signatures (TSS) makes more sense, since this allows for multi-chain support and maintaining signers privacy by generating a regular-looking transaction. See our blog for a full comparison, including with Shamir secret sharing.
In our new paper we focus on an additional advantage of TSS wallets: support for proactive security.
Proactive Secret Sharing (PSS)
Proactive security can be seen as adding the dimension of time to the security model. It guarantees security even when the adversary controls different parties at different moments in time. A threshold system with PSS works in phases: In each phase the entire set of n participants holds a completely different set of secret shares. Changing phases is a multiparty computation protocol which inputs the old secret shares and outputs the new secret shares so that the public key remains the same.
In a threshold wallet, this means that a transaction can be signed and verified with the same public key in each phase. However, since the shares are changed at every stage, an attacker must control at least t+1 participants within the same phase to forge a signature. So for instance, if an attacker controls (t+1)/2 participants in one phase and (t+1)/2 participants in another phase it cannot forge a signature. This is a strong notion of security explored extensively in the literature. The latest work in this line is CHURP. Here is a survey table from CHURP:
One thing to notice is that all existing protocols work in the honest majority setting (which only guarantees security for thresholds restricted to t < n/2). On the other hand, when constructing threshold signatures protocols we are more often interested in the dishonest majority setting (which guarantees security for any threshold t<n). This discrepancy is what our paper solves, namely: how to do PSS in threshold signatures with t<n.
PSS in the blockchain space
This research was motivated by the growing interest in the blockchain space for threshold wallets with proactive security. As new implementations emerge we noticed that the PSS parts of the code are not backed up by any reference protocol with provable security. We asked ourselves if such a protocol is even possible and if it can be optimized in any way. In the paper we answer both in the affirmative. To be concrete, we provide two examples we encountered in the wild, of libraries using proactive security. In each one we describe the vulnerability we found. We note that the bugs were disclosed responsibly and closed. We can attest to the high quality of the code in both cases. We put forward these examples in order to emphasize the need for our protocol.
Binance tss-lib delete share attack: Tss-lib provides threshold ECDSA based on GG18 paper which is a protocol supporting any t<n. The library provides support for another protocol called “Resharing” which is defined as “Dynamic Groups to change the group of participants while keeping the secret”. This is exactly PSS. Their protocol is based on Verifiable Secret Sharing which includes a direct channel between two parties and a broadcast channel. While the broadcast channel (which is not implemented in the library) assumes that all parties will see the same message, a party can send different messages to different parties using the direct channels. Messages on both channel types must be verified. We noticed that even though all checks are done properly, there is no “blame” step that allows for parties that received “bad” direct messages to declare them to the rest of the quorum. In that case, if an attacker sends “bad” messages to some parties and “good” messages to the rest, the parties that received “good” messages will continue the protocol, eventually re-writing their secret shares. The parties that received the “bad” messages will abort the protocol and keep the old secret shares. As we mentioned before, secret shares from two different phases cannot be used together, so this attack effectively deletes the secrets of one of the sets of parties (the ones that got “bad” messages or the ones that got “good” messages).
Unbound blockchain-crypto-mpc encrypt to anything attack. Unbound library implements Lindell’s two-party ecdsa protocol. This protocol works for specific parameters t=1,n=2 which is dishonest majority. The library adds support for “Key sharing refresh”, defined in Unbound white paper as a protocol to “jointly generate new random shares of an existing shared key so that the old shares become useless”. Later it is mentioned that this security property is called proactive in academic literature. The specific 2P-ECDSA protocol by Lindell requires the use of Paillier cryptosystem. One of the parties holds an encryption of its secret share under the Paillier public key and after Refresh, the same party must hold a new secret share encrypted under a new Paillier public key. The refresh protocol implemented by the library suggested a clever way to make the refresh efficient: use of zero-knowledge (ZK) proof to show that two Paillier ciphertexts encrypts the same plaintext under two different Paillier public keys. Unfortunately, the ZK proof chosen works only if the prover does not know the private key for one of the Paillier public keys which is not the case since the prover here generates both private keys. This leads to a prover (party one) that can convince the verifier (party two) that the new ciphertext is an encryption of any number chosen by the prover. In our Breaking Bitcoin talk we had conjectured that this vulnerability might lead to oracle access for the prover party that after many tries can recover the counterparty private key.
Our new PSS scheme
The key to making our scheme possible is producing a threshold signature within the threshold signature intended for the blockchain.
Our new scheme is compatible with the threshold versions of Schnorr, EdDSA, and ECDSA. What is common to all is the existence of a ‘sweet-spot’ between computing the joint nonce point R and the full signature s. This is the point where our online parties will generate another threshold signature, bounded to the outer nonce point R, as well as other relevant information for the refresh. The inclusion of the outer signatures (R,s) on the blockchain signals the offline parties on successful refresh cycles they need to follow.
Security wise, we require no extra assumptions.
No dedicated protocol is required. In fact, no extra rounds of communication are needed for the original threshold signature protocol: The refresh protocol can be folded into the threshold signature protocol. Each time the parties sign they can also have proactivization almost for free. We run tests on the threshold ECDSA protocol of Gennaro and Goldfeder with t=1 and the overhead in general is extremely efficient (extra 200 bytes of communication and 14% more computation). The code is public.
Offline Support
The most interesting feature of our scheme is the support of offline parties. We figured out that it doesn’t make sense to require all n parties to be online while only t+1 parties are actually engaging in the protocol. In the paper, we put forward some examples to why for the specific case of a threshold wallet it is unreasonable. As a concrete example we take a 2 out of 3 threshold scheme where two shares are, lets say, a desktop and mobile used to sign transactions, while the third share is for backup. For example, a cold storage or some secure hardware device that will be used to recover the key only in case recovery is needed. In that scenario, having the hardware device online each time the user wants to rotate the secret shares makes it exposed. With our protocol the hardware device can stay offline. Each time the two other parties are doing a rotation of the secret share they will send a message (e.g.call it an email) to the offline device. When the offline device comes online, it will be able to use its secret shares and the messages it received when it was offline to compute the current phase secret share.
Outro
Threshold signatures (TSS) present a step function in key management security. Combining TSS with proactive security, when implemented correctly, adds a major layer to the overall security of the system. We argue that TSS libraries can improve on (1) their security, by implementing provable secure PSS, and (2) their efficiency, by using a lightweight PSS protocol between just the online parties. Our paper provides this solution. We encourage the reader to read the paper and find out exactly how this is done 🙂
