Authors: Omer Shlomovits, ZenGo.
Threshold Signature Scheme (TSS) is a cryptographic primitive that enables distributed key generation and signing. Introducing TSS in blockchain clients is a new paradigm that brings numerous advantages, particularly in terms of security. Broadly speaking, TSS can redefine the design of key management systems (such as cryptocurrency wallets) and provide native support for DeFi use cases. However, as an emerging technology, TSS also poses certain risks and limitations.
This article will provide a detailed overview of the basic concepts of TSS, its potential advantages for the blockchain field, implementation methods in blockchain clients, and its differences from Shamir's Secret Sharing and multi-signature schemes. Additionally, we will explore different ways to utilize TSS for distributed key management and discuss related risks and limitations.
The Power of Cryptography
To understand the concept of TSS, we first need to grasp some basics of cryptography. Since the 1970s, an increasing number of internet systems (such as TLS and PGP) have begun to adopt asymmetric encryption technology, also known as public key cryptography (PKC). PKC is based on two keys: a public key and a private key. The public key is public and can be published and used by anyone, while the private key is the core secret that protects the system's security.
Encryption and digital signatures are the two main application scenarios of PKC. Both technologies rely on three algorithms: first, generating a pair of private and public keys; second, generating ciphertext/signature; and finally, the decryption/verification process. Taking digital signatures as an example, the signing algorithm uses a private key known only to the owner to generate a unique signature, which is then attached to the message. Subsequently, anyone holding the public key can verify the authenticity and accuracy of the signature.
Blockchain
Undoubtedly, blockchain is a powerful technology with great potential, providing a consensus layer for organizing and recording events. This infrastructure empowers users to build decentralized economies and even decentralized governments. Surprisingly, the cryptography required to run a basic blockchain relies solely on digital signatures. In a blockchain, the private key represents identity, while the signature is a public declaration or assertion made by that identity. The blockchain ensures the non-repudiability and accuracy of signatures by ordering these assertions and verifying them according to a set of rules.
Compared to traditional cryptographic techniques used in blockchain, modern cryptography has introduced many exciting new results, such as zero-knowledge proofs, homomorphic encryption, and multi-party computation. Over the past decade, blockchain research has greatly propelled the development of applied cryptography, achieving significant breakthroughs in the aforementioned areas and more.
This article will focus on one of these breakthroughs, the secure and efficient Threshold Signature Scheme (TSS).
MPC and Threshold Signature Scheme (TSS)
Multi-Party Computation (MPC) is a branch of cryptography with origins tracing back to approximately 40 years ago in Andrew C. Yao's groundbreaking research. The core of MPC is to allow a group of mutually distrustful participants to jointly compute the result of a function without disclosing their individual input information.
For example, suppose n employees of a company want to know who has the highest salary but do not wish to reveal their actual salaries. In this scenario, each employee's input is their salary, and the final output is the name of the employee with the highest salary. Through MPC, this computation can be completed without exposing any employee salary information.
The two core features of MPC are correctness and privacy:
Correctness: The algorithm's output is the expected correct result.
Privacy: The input data of any participant will not be disclosed to others.
We will utilize MPC technology to calculate digital signatures in a distributed manner and explore how the above features can be applied to the signing process. As previously mentioned, signing typically consists of three steps:
Key Generation: The first step is the most complex in the entire process. This step requires generating a public key for verifying subsequent signatures. Additionally, an independent 'secret share' must be generated for each participant. In terms of correctness and privacy, this function will output the same public key to all participants while generating different secret shares for each participant, ensuring: (1) Privacy: Secret share data will not be leaked among parties, and (2) Correctness: The public key is the function computation result of all secret shares.
Signing: This step involves the signature generation function. The inputs from each party are their secret shares, derived from the output of the previous step (distributed key generation). There is also a well-known public input, which is the message to be signed. The output is the digital signature, and privacy ensures that the secret shares will not be leaked throughout the computation process.
Verification: The verification algorithm remains consistent with traditional methods. To ensure compatibility with single signature schemes, anyone who possesses the public key can verify and confirm the signature, which is also the core task executed by blockchain verification nodes.
Threshold Signature Scheme (TSS) is the name we give to the combination of distributed key generation (DKG) and the distributed signing process.
Combining TSS with blockchain
An intuitive way to adopt TSS in blockchain is to modify the blockchain client so that it generates keys and signatures through TSS technology. Here, 'blockchain client' refers to a set of commands executed by full nodes. In practical applications, TSS can replace all single-key related commands with distributed computation.
To elaborate, let us first briefly introduce how new addresses are created in traditional blockchain design. In simple terms, a private key is first generated, then a public key is computed from the private key, and finally a blockchain address is derived from the public key.
In TSS mode, the public key is jointly computed by n participants, each holding only a secret share of the private key (and the shares do not leak to each other). We can derive the address from the public key in the same way as traditional systems, making the address generation independent of the blockchain. The advantage of this method is that each party holds only a portion of the private key, thus the private key is no longer a single point of failure.
Transaction signatures can also adopt a similar approach. The difference is that instead of using a private key for unilateral signing, a distributed signature is generated through multi-party collaboration. Therefore, as long as enough participants act in good faith, valid signatures can be produced, achieving a shift from local computation (single point of failure) to interactive computation.
It is worth mentioning that distributed key generation can support different types of access structures: the general 't out of n' model can ensure that key-related operations can still be executed securely even in the event of up to t arbitrary failures.
TSS and Multi-signature
Some blockchains offer TSS functionality as a built-in or programmable part of the software, which we usually refer to as multi-signature. To better understand the differences between the two, multi-signature can be viewed as TSS at the application layer of the blockchain.
In other words, both multi-signature and TSS essentially aim to achieve similar goals, but TSS uses off-chain cryptographic techniques while multi-signature occurs on-chain. However, the blockchain requires a specific method to encode multi-signatures, which can impact privacy since the access structure (number of signers) will be exposed on the blockchain. Additionally, multi-signature transactions tend to be more expensive since the information of each signer needs to be transmitted to the blockchain.
In TSS, the details of the signers are embedded in regular transactions, thereby reducing costs and protecting privacy. On the other hand, multi-signature can be realized through non-interactive methods, saving the trouble of running complex communication layers between different signers.
The main difference between the two is that multi-signature is specific to the blockchain and needs to be implemented separately for each blockchain, and may not be supported at all in certain blockchains. In contrast, TSS is entirely based on cryptography and can always be supported. For further understanding of the differences between the two, please refer to this link.
TSS and Shamir's Secret Sharing Scheme
Shamir's Secret Sharing Scheme (SSSS) provides a method for distributed storage of private keys, allowing them to be dispersed across multiple locations while in a stationary state. SSSS and TSS mainly differ in two aspects:
Key Generation: In SSSS, a role known as the 'dealer' is responsible for generating the secret shares of the private key. The dealer generates the complete private key at a single location, splits it into multiple secret shares, and then distributes them to different locations. In TSS, there is no dealer, as the entire process is distributed, and the complete private key is never generated at a single location.
Signing: In SSSS, parties need to reconstruct the complete private key before they can sign, leading to the risk of a single point of failure every time a signature is made. In TSS, the signing process is completed in a distributed manner without the need to reconstruct the secret shares.
Therefore, in the TSS scheme, the private key never appears at a single location throughout its lifecycle, significantly enhancing system security.
Threshold Wallet
Wallets based on TSS technology differ slightly from traditional cryptocurrency wallets. Traditional wallets typically derive wallet addresses deterministically by generating mnemonic phrases. Users can utilize this hierarchical deterministic (HD) structure to: 1) obtain the private key associated with the wallet address and sign transactions; 2) recover all wallet keys through the mnemonic phrase.
The operation mechanism of threshold wallets is more complex. While it also supports generating HD structures, this process needs to be computed in a distributed manner, similar to another MPC protocol. The participants need to jointly decide on the next key to be used. In other words, each participant has their own independent mnemonic phrase. These mnemonic phrases are generated separately and do not combine, so no party can derive the complete private key from their own mnemonic phrase alone.
Additionally, TSS-based wallets possess a powerful security feature, allowing private key rotation without changing the public key and blockchain address. Private key rotation, also known as active secret sharing, is another MPC protocol that takes old secret shares as input and generates a new set of secret shares. The old secret shares can be deleted, while the new shares can continue to be used.
This architecture introduces a temporal dimension to the security of threshold wallets, meaning that an attacker must appear at multiple locations simultaneously to successfully attack the wallet. Even if they attempt to forge signatures, the secret shares obtained by the attacker before and after the private key rotation cannot be combined to form a complete key, posing no additional threat to security.
However, one limitation of such wallets is that they do not support mnemonic phrases, making them incompatible with single-key wallet systems. Therefore, it is crucial to clarify which parties hold the secret shares.
Possible architectures include the following:
Outsourced TSS: Users outsource the computation to 'n' servers. Key generation, management, and signing are effectively outsourced to service providers who are not asset owners but receive compensation through security guarantees.
Multi-device collaboration: Users run TSS across devices they own. For example, Internet of Things devices, mobile devices, and laptops work together.
Hybrid model: Some participants are controlled by external service providers while others run on the user's own devices, collectively completing the TSS computation.
The first method reduces the TSS computation burden on the user client, but service providers may collude to steal user assets (although it is usually assumed that enough service providers will not be compromised simultaneously, this possibility cannot be ruled out).
The second method gives users complete control, but the need for multiple devices to be online for TSS computation makes transaction operations cumbersome.
The third method balances both, allowing users to complete transactions in a simple and efficient manner while ensuring that transactions cannot be completed without the user's authorization.
TSS and Smart Contracts
Over the years, researchers have explored many uses of digital signatures, some of which have become indispensable key technologies. As mentioned earlier, TSS is a cryptographic primitive that can significantly enhance security. In blockchain scenarios, TSS-based cryptographic schemes can replace many traditional functions. For example, decentralized applications, Layer 2 scaling solutions, atomic swaps, mixing coins, inheritance, and more can all be realized through the TSS framework. This allows the costly and risky on-chain smart contract operations to gradually give way to more economically reliable solutions.
For example, multi-hop locks cleverly utilize two-party signatures to provide a more secure and private payment channel network, serving as an alternative to the Bitcoin Lightning Network. ShareLock may be the lowest-cost on-chain mixing solution on Ethereum, based on single threshold signature verification.
Risks
In recent years, the application of TSS has gradually increased. However, as a relatively new technology, it still faces some limitations and potential issues. Compared with traditional public key cryptography techniques, TSS protocols are more complex and have not been extensively 'battle-tested'. Generally, TSS requires additional cryptographic assumptions compared to simple digital signatures, and these assumptions may not be robust enough, introducing cryptographic attack vectors not present in traditional schemes (see related presentations from the 2019 Breaking Bitcoin Conference). It is recommended to seek professional support from security engineers and cryptography experts to securely deploy TSS in systems.
On the positive side, thanks to increasing community contributions, peer reviews, code audits, and algorithm optimizations, existing and emerging TSS applications are becoming increasingly mature.
Conclusion
This article introduces the basic concepts of the Threshold Signature Scheme (TSS), which is a highly promising cryptographic primitive expected to change the way we interact with blockchain.
As this article does not cover the threshold ECDSA applicable in BNB Chain and Bitcoin, interested readers may refer to the latest papers below. Additionally, if you wish to try some TSS applications, you can check the open-source code of the two-party BNB Chain wallet here or use the ZenGo wallet, which is a non-custodial two-party BNB Chain wallet that adopts a hybrid model.
Further Reading:
Secure and Efficient Two-Party ECDSA Signature Scheme
Secure and Efficient Multi-Party ECDSA Scheme Supporting Practical Distributed Key Generation and Cryptocurrency Custody Applications
Two-Party ECDSA Based on Hash Proof Systems and Its Efficient Instantiation
Multi-Party Threshold ECDSA with Efficient Trustless Setup
Secure Two-Party Threshold ECDSA Based on ECDSA Assumptions
Threshold ECDSA Based on ECDSA Assumptions: Multiple Schemes