Author: Omer Shlomovits, ZenGo.

The Threshold Signature Scheme (TSS) is a cryptographic element for generating and signing distributed keys. The use of TSS in blockchain clients is a new paradigm that can provide numerous benefits, especially from a security perspective. More broadly, TSS can influence the design of key management systems (e.g., crypto wallets) and pave the way for native support in DeFi use cases. That said, TSS is still a new technology, so risks and limitations should also be considered.

In this article, we will look at what TSS is, what potential benefits it brings to the blockchain space, how it can be implemented in a blockchain client, how it differs from Shamir secret distribution schemes and multi-signature, what are the different ways TSS can be used for distributed key management, and finally, we will discuss the risks and limitations.


The power of cryptography

To understand TSS, we first need a basic understanding of cryptography. Since the 1970s, more and more Internet systems (such as TLS and PGP) have used asymmetric cryptography, also known as public key cryptography (PKC). PKC uses two keys: one public and one private. While the public key is not a secret and can be published and used by anyone, the private key is a piece of secret information that ensures the security of the system.

Encryption and digital signatures are the two most common uses of PKC. Both encryption and digital signature schemes rely on sets of three algorithms. The first is the generation of a private and public key pair, the second is the generation of the ciphertext/signature, and the third is the decryption/verification process. In the case of digital signatures, the signature algorithm requires a private key, known only to its owner, to create a unique signature. The signature is appended to a given message in such a way that anyone with the public key can verify its authenticity and correctness.


Blockchain

There is no doubt that blockchain is a very powerful technology. It provides a layer of consensus that organizes and records events. This infrastructure gives us, the users, the potential to build decentralized economies and even governments. Ironically, the cryptography required to make the underlying blockchain work can be based solely on digital signatures. In the context of blockchain, private keys are individuals, and a signature is a public statement or claim made by an individual. The blockchain organizes statements and verifies them against a set of rules that ensure, among other things, that signatures are not forged and are correct.

Unlike the more classical cryptography used in blockchain, the modern cryptographic toolkit includes some amazing tricks: zero-disclosure proofs, homomorphic encryption, and multiparty computation, etc. Over the past decade, blockchain research has significantly boosted applied cryptography, with recent breakthroughs in all of the above and more.

In this article, we will focus on one such breakthrough: efficient threshold secure signatures (TSS).


MPC and Threshold Signature Scheme (TSS)

Multiparty computation (MPC) is a branch of cryptography that began with the seminal work of Andrew Qizhi Yao nearly 40 years ago. In MPC, a set of parties who do not trust each other attempt to jointly compute a function on their inputs, keeping those inputs private.

As an example, let's say that n employees in a company want to know who earns the most, but without revealing their actual salaries to each other. Here, the private inputs are the salaries, and the output is the name of the employee with the highest salary. Performing this calculation using MPC, we get that no salary leaks out during the calculation.

The two main properties of MPC are correctness and confidentiality:

  • Correctness: The result obtained by the algorithm is correct (as expected).

  • Confidentiality: Secret input data owned by one party will not be disclosed to other parties.

We will use MPC to compute a digital signature in a distributed manner. 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 difficult. We need to generate a key that will be public and used to verify future signatures. But we also need to generate a separate secret for each party, which we will call the secret share. In terms of correctness and confidentiality, we say that the function outputs the same public key for all parties and a separate secret share for each party under the following conditions: (1) confidentiality: no secret data is leaked between the parties, and (2) correctness: the private key is a function of the secret shares.

  • Signing: This step involves the signature creation function. The input for each party will be their secret share, created as a result of the previous step (generating the shared key). There is also a public input, known to everyone, which is the message to be signed. The output will be a digital signature, and the confidentiality property ensures that no secret shares are leaked during the computation.

  • Verification: The verification algorithm remains the same as in the classic setup. To be compatible with single-key signatures, anyone who knows the public key must be able to check and verify the signatures. This is exactly what the nodes-validators do on the blockchain.

Threshold Signature Scheme (TSS) is the name we give to this composition of distributed key generation (DKG) and distributed signature threshold signature scheme.


Combining TSS with blockchains

The natural way to use TSS in a blockchain is to modify the blockchain client to generate keys and signatures using TSS. Here, we use the term blockchain client to refer to the set of commands that a full node executes. In practice, TSS technology allows us to replace all private key-related commands with distributed computations.

To explain this in more detail, we will start with a brief description of how new addresses are created in the classic blockchain design. In short, we can create a new address by generating a private key and then calculating the public key from the private key. Finally, the blockchain address is obtained from the public key.

Now, using TSS, we will have a set of n parties that jointly compute a public key, each of which holds a secret portion of the private key (the individual portions are not revealed to other parties). From the public key, we can derive an address in the same way as in a traditional system, making the blockchain independent of how the address is generated. The advantage is that the private key is no longer a single point of failure, since each party holds only one portion of it.

The same can be done when signing transactions. In this case, instead of one party signing their private key, we trigger the generation of a distributed signature between multiple parties. This way, each party can create a valid signature if most of them act honestly. We have again moved from local computation (single point of failure) to interactive computation.

It is important to note that distributed key generation can be done in a way that allows for different types of access structures: a general "t of n" setup will be able to withstand up to t arbitrary failures in operations involving the private key without compromising security.


TSS and Multi-Signature

Some blockchains offer TSS functionality as a built-in or programmable part of the software. We call this multi-signature or multisig functionality. To better understand the differences, we can think of multi-signature as TSS at the blockchain application level.

That is, both multi-signature and TSS essentially try to achieve similar goals, but TSS uses off-chain cryptography, while multi-signature uses on-chain cryptography. However, the blockchain needs a way to encode multi-signature, which can compromise privacy because the access structure (number of signatories) is exposed on the blockchain. The cost of a multi-signature transaction is higher because information about the different signatories must also be transmitted to the blockchain.

In TSS, signer data is rolled up into a regular transaction, which reduces costs and preserves confidentiality. On the other hand, multi-signature can be non-interactive, which eliminates the problems of providing a complex level of communication between different signers.

The main difference is that multi-signature is blockchain-dependent and needs to be re-implemented for each blockchain, and in some cases it is not supported at all. Conversely, TSS relies on pure cryptography, so support is always possible. You can find a great article illustrating the differences here.


TSS and Shamir's Secret Distribution Scheme

Shamir Secret Sharing Scheme (SSSS) provides a way to distribute private key storage in such a way 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 one party called the "dealer" who is responsible for generating the private key. This means that during key generation, the private key is generated in one place and then distributed by the dealer to different places. In TSS, there is no dealer because its role is distributed in such a way that the complete private key is never in one place.

  • Signing: In SSSS, parties must reconstruct the full private key to sign, which again leads to a single point of failure each time a signature is required. In TSS, signing is done in a distributed manner without reconstructing the secret parts.

As we can see, in TSS, the private key (which represents the security of the system) is never in one place throughout its lifetime.


Threshold wallets

A TSS wallet is a little different from a traditional cryptocurrency wallet. Typically, a traditional wallet generates a seed phrase and uses it to deterministically retrieve addresses. The user can then use this hierarchical deterministic (HD) structure to 1) retrieve private keys that correspond to wallet addresses and sign transactions with them, and 2) recover all wallet keys using the seed phrase.

With a threshold wallet, things get more complicated. While it is possible to generate an HD structure, its generation must be computed in a distributed manner, like other MPC protocols. The parties must collectively decide which key to use next. That is, each party will have its own seed phrase. The seed phrases are generated separately and are never combined, so that one party cannot obtain private keys from its own seed phrase.

TSS-based wallets also have a good security feature that allows private key rotation without changing the corresponding public key and blockchain address. Private key rotation, also known as proactive secret exchange, is another MPC protocol that takes secret shares as input and outputs a new set of secret shares. Old secret resources can be deleted, and new ones can be used in the same way.

This structure adds a time dimension to security, meaning that an attacker would have to be in multiple places at once to attack a threshold wallet. Combining the secret shares before and after the rotation would not give the attacker any additional options if they wanted to forge a signature.

The downside to this type of wallet is that the lack of a seed phrase makes it incompatible with single-key wallet systems. Therefore, it is important to consider who will own the secret shares.

There are several possible architectures:

  • TSS outsourcing: the user allows "n" servers to perform computations on their behalf. In effect, transferring the generation, management, and signing of keys to service providers who do not own the assets but provide a level of security in exchange for some incentive.

  • Multiple device usage: A user initiates TSS between devices that they own. For example, one party would be some IoT device, another party would be the user’s mobile device, the third would be their laptop, etc.

  • Hybrid: TSS will operate in a way where some sides are controlled by external service providers and some sides run on user-owned devices.

The first method removes the heavy TSS computation from the user-client side. On the other hand, service providers can collude (we assume that a large number of them are not attacked simultaneously, but in practice they can) and steal user assets.

The second method gives the user full control, but makes it more difficult to conduct transactions because you need multiple devices to access the internet and participate in TSS calculations.

The third option is considered the best of both worlds, as it gives the user a simple and fast way to conduct transactions, but without compromising transactions without user authorization.


TSS and smart contracts

Over the years, researchers have come up with many applications for digital signatures, some of which are surprisingly non-trivial. As mentioned, TSS is a cryptographic element that can significantly improve security. In the context of blockchains, it can be said that many functions can be replaced with TSS-based cryptography. Decentralized applications, level 2 scaling solutions, atomic swaps, mixing, inheritance, and much more can be built on top of the TSS framework. This will ultimately allow expensive and risky on-chain smart contract operations to be replaced with cheaper and more reliable alternatives.

Here are some concrete examples: Multi-Hop Locks makes smart use of two-way signatures and can be used as an alternative to the Bitcoin Lightning Network with a more secure and private payment channel network. ShareLock is probably the cheapest solution for on-chain mixing on Ethereum, based on single-threshold signature verification.


Risks

The past few years have seen a significant increase in the number of TSS implementations. However, as a relatively new technology, it still has some limitations and challenges. Compared to classical public-key cryptography, TSS protocols can be very complex and have not yet been "battle-tested." TSS typically requires additional, weaker cryptographic assumptions compared to simple digital signatures. As a result, cryptographic attack vectors that did not exist in traditional settings are now exposed (see this presentation from the Breaking Bitcoin Conference 2019). Security engineers and applied cryptographers can help you safely deploy TSS in your system.

The positive point is that current and new implementations are becoming stronger due to increasing quality of contributions, peer reviews, audits, and improved algorithm performance.


Results

In this article, we introduced the basics of the Threshold Signature Scheme (TSS), which is an exciting cryptographic element that could significantly change the way blockchain is used.

Since this article did not discuss Threshold ECDSA, which can be used on BNB Chain and Bitcoin, those interested can refer to the following list of recent articles. Alternatively, if you want to play around with some TSS implementations, you can find the code for the BNB Chain two-party wallet here or try the ZenGo wallet, which uses a hybrid method to provide a non-custodial two-party wallet on BNB Chain.


Related articles: