The power of cryptography
In this article, we will focus on a single such breakthrough: efficient secure threshold signatures (TSS).
MPC and the threshold signature scheme (TSS)
Multi-party computation (MPC) is a branch of cryptography that started with the seminal work of Andrew C. Yao, almost 40 years ago. In MPC, a set of parties that do not trust each other try to jointly compute a function over their inputs while keeping those inputs private.
The two main properties of MPC are correctness and privacy:
Correctness: the output produced by an algorithm is correct (as expected).
Privacy: the secret input data that a party holds would not leak to the other parties.
We will use MPC to compute a digital signature in a distributed way. Let's see how the above properties can be applied to signatures. Recall that, for signatures, we have three steps:
Key Generation: the first step is also the most complex. We need to generate a key which will be public and used to verify future signatures. But, we also need to generate an individual secret for each party, which we will call a secret share. In terms of correctness and privacy we say that the function will output the same public key to all parties, and a different secret share for each such that: (1) privacy: no secret shares data is leaked between the parties, and (2) correctness: the public key is a function of the secret shares.
Signing: this step involves a signature generation function. The input of each party will be its secret share, created as output of the previous step (distributed key generation). There is also public input known to all, which is the message to be signed. The output will be a digital signature, and the property of privacy ensures that no leakage of secret shares occurred during the computation.
- Verification: the verification algorithm remains as it is in the classical setting. To be compatible with single key signatures, everyone with knowledge of the public key should be able to verify and validate the signatures. This is exactly what blockchain validating nodes do.
Threshold signature scheme (TSS) is the name we give to this composition of distributed key generation (DKG) and distributed signing a threshold signature scheme.
Combining TSS with blockchains
To explain it in more detail, we start by describing briefly how new addresses are created on the classical blockchain design. Simply put, we can create a new address by generating a private key, and then computing the public key from the private key. Finally, the blockchain address is derived out of the public key.
Now, using TSS, we would have a set of n parties jointly computing the public key, each holding a secret share of the private key (the individual shares are not revealed to the other parties). From the public key, we can derive the address in the same way as in the traditional system, making the blockchain agnostic to how the address is generated. The advantage is that the private key is not a single point of failure anymore because each party holds just one part of it.
The same can be done when signing transactions. In this case, instead of a single party signing with their private key, we run a distributed signature generation between multiple parties. So each party can produce a valid signature as long as enough of them are acting honestly. Again we moved from local computation (single point of failure) to an interactive one.
It is important to mention that the distributed key generation can be done in a way that allows different types of access structures: the general “t out of n” setting will be able to withstand up to t arbitrary failures in private key related operations, without compromising security.
TSS vs. Multisig
Put differently, both multisig and TSS are essentially trying to achieve similar goals, but TSS is using cryptography off-chain, while multisig happens on-chain. However, the blockchain needs a way to encode multisig, which might harm privacy because the access structure (number of signers) is exposed on the blockchain. The cost of a multisig transaction is higher because the information on the different signers also needs to be communicated on the blockchain.
In TSS, the signers’ details are folded into a regular looking transaction, reducing cost and maintaining privacy. On the other hand, multisig can be non-interactive, which saves the trouble of running a complex communication layer between the different signers.
TSS vs. Shamir secret sharing scheme
The Shamir secret sharing scheme (SSSS) provides a way to store the private key in a distributed manner such that while the private key is at rest, it is stored in multiple locations. There are two differences between SSSS and TSS:
Key Generation: in SSSS, there is a single party called “the dealer” that is in charge of generating the private key secret shares. It means that at time of Key Generation, the private key is generated at a single location and then distributed by the dealer to the different locations. In TSS, there is no dealer as its role is distributed such that the full private key is never at a single location.
Signing: in SSSS, the parties must reconstruct the full private key in order to sign, which again results in a single point of failure each time a signature is needed. In TSS, the signing is done in a distributed way without ever reconstructing the secret shares.
As we can see, in TSS the private key (which represents the security of the system) is never at a single location throughout its entire lifetime.
In a threshold wallet, things are more complex. Although it is possible to generate an HD structure, its generation must be computed in a distributed manner, as another MPC protocol. The parties need to jointly decide on what is the next key to be used. In other words, each party will have a seed phrase of its own. The seed phrases are generated separately and never combined so that one party alone can’t derive the private keys from its seed.
TSS-based wallets, also have a nice security feature, which is enabling of private key rotation without changing the corresponding public key and blockchain address. Private key rotation, also known as proactive secret sharing, is yet another MPC protocol that takes the secret shares as input, and outputs a new set of secret shares. The old secret shares can be deleted and the new ones can be used in the same way.
Such a structure adds a time dimension to the security, which means an attacker must be at multiple locations at the same time to attack a threshold wallet. Combining secret shares before rotation and after the rotation will give the attacker no extra power if they want to forge a signature.
A downside of this type of wallet is that the lack of a seed phrase makes it incompatible with single-key wallet systems. So it’s important to consider which parties will hold the secret shares.
There are a few possible architectures:
Outsourcing TSS: the user will let “n” servers run the computation on their behalf. Effectively outsourcing the key generation, management and signing to service providers who are not the owners of the assets but provide a security layer in return to some incentive.
Using multiple devices: The user will run the TSS between the devices they own. For example - one party will be some IoT device, another party will be the user mobile, another party their laptop, and so on.
Hybrid: TSS will run such that some parties are controlled by outside service providers and some parties run on user-owned devices.
The first method offloads the heavy TSS computation from the user client side. On the other hand, the service providers can collude (we assume enough of them are not attacked at the same time, but in practice, they might) and steal the assets of the user.
The second method gives the user full control but makes it cumbersome to conduct transactions as you need multiple devices to go online and engage with the TSS computation.
The third option is considered the best of both worlds as it gives the user an easy and fast way to conduct transactions but without compromising on having transactions done without the user authorization.
TSS and smart contracts
On the positive side, existing and new implementations are becoming stronger due to an increase in quality contributions, peer reviews, audits, and algorithmic performance improvements.
In this article, we introduced the basics of the threshold signature scheme (TSS), which is a fascinating cryptographic primitive that has the potential to change significantly the way we use blockchain.
Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody
Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations