Author: Omer Shlomovits, ZenGo.

Threshold Signing Scheme (TSS) is a cryptographic primitive scheme for generating and signing distributed keys. Using TSS in blockchain calculations is a new paradigm that can offer many different benefits especially in terms of security. That is, TSS can influence the design of key management systems (such as digital wallets) and lead the field for local support in DeFi use cases. Having said this TSS is still a new technology so the risks and limitations must also be considered when using it.

In this article, we will cover what TSS is, what potential advantages it may bring to the blockchain field, how it can be implemented in the Client blockchain, how it compares to Shamir secret sharing and Multisig, what are the different ways to use TSS in distributed key management, and finally we discuss its potential risks and limitations. .

Role of encryption

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

Encryption and digital signatures are the most common uses of PKC. Both encryption and digital signature schemes are based on sets of three algorithms. The first is the generation of the private and public key pair, the second is the generation of ciphertext/signature and the third is the decryption/verification process. Regarding digital signatures: The signature algorithm requires that a private key that is known only to its owner creates a unique signature. A signature is attached to a particular message in such a way that anyone holding the public key can verify its authenticity and authenticity.


Blockchain

There is no doubt that blockchain is an extremely powerful technology. It provides a consensus layer that organizes and records events. Such infrastructure gives us users and even governments the potential power to build decentralized economies. Surprisingly, the encryption needed to run a simple blockchain can only rely on digital signatures. In blockchain, private keys represent identities while signatures are a public statement or claim made by an identity. The blockchain requests and verifies data according to a set of rules that ensure, among many other things, that signatures are unforgeable and valid.

The modern cryptography toolbox includes some cool magic tricks unlike the more classic cryptography used in blockchain. Some examples of these tricks include zero-knowledge proofs, homomorphic cryptography, and multi-party computation. As we have seen over the past decade blockchain research has dramatically pushed applied cryptography with surprising recent advances in knowledge in all of the above and much more.

In this article, we will focus on one of the breakthroughs, which is effective secure threshold signatures (TSS).


MPC and the threshold signature scheme (TSS)

Multiparty computation (MPC) is a branch of cryptography that began with the seminal work of Andrew C. Yao nearly 40 years ago. In MPC a group of parties that do not trust each other attempt to compute a function over their inputs while keeping those inputs private.

For example, let's say that a number of company employees want to know who gets paid more but without revealing their actual salary to each other. Here the special input is salaries and embarrassments will be the name of the employee with the highest salary. When this calculation is performed using MPC, the result is that not even a single salary is leaked during the calculation.

The two main features of MPC are authenticity and privacy:

  • Correctness: The output generated by an algorithm is correct (as expected).

  • Privacy: Confidential input data held by one party will not be leaked to other parties.

We will use MPC to compute the digital signature in a distributed manner. Let's see how the above properties can be applied to signatures. For signatures, we have three steps:

  • Key generation: The first step is also the most complicated. We need to create a key that will be public and used to verify future signatures. But we also need to create an individual secret for each participating party which we will call a secret share. In the context of correctness and privacy we say that the function will output the same public key for all parties and a different secret share for both the following: (1) Privacy: No data about the secret share is leaked between the two parties and (2) Correctness: The public key is a function of the secret shares.

  • Signature: This step includes the function of creating a signature. Each party's contribution is their secret share, which is generated as the output from the previous step (distributed key generation). There is also a general input known to everyone which is the message to be signed. The output will be a digital signature and the privacy feature ensures that no leakage of secret shares occurs during the calculation.

  • Verification: The verification algorithm remains the same as in the classic settings. To be compatible with individual key signatures, everyone with knowledge of the public key must be able to verify and authenticate the signatures. This is exactly what blockchain verification nodes do.

Threshold signature scheme (TSS) is the name we give to the combination of distributed key generation (DKG) and signature distribution over a threshold signature scheme.


Combining TSS and blockchain

The natural way in which TSS can be used in a blockchain is by changing the blockchain client to generate keys and signatures using TSS. Here we use the term client to refer to a set of commands that are executed by a full node. In practical application, TSS technology allows us to replace all commands related to the private key with distributed computations.

To explain this in more detail we will start with a quick description of how to create new addresses on a classic blockchain structure. Simply put, 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 derived from the public key.

Now using TSS we will have a group of parties jointly calculating the public key. Each participating party holds a secret share of the private key (the individual shares are not revealed to the other participating parties). Using the public key, we can derive the address in the same way as in the traditional system, which makes the blockchain somewhat neutral in the way addresses are generated. The advantage here is that the private key is no longer a single point of failure because each party keeps one part of it.

The same can be done when signing transactions. In this case, instead of one party signing with its private key, we run a distributed signature generator between multiple parties. Even each party can produce a valid signature as long as enough participants act honestly. We moved again from a local account (single point of failure) to an interactive account.

It is important to note that the generation of distributed keys can be done in a way that allows different types of access to them: a generic “t out of n” setting will be able to withstand up to t arbitrary failures in operations related to the private key without compromising security.


TSS vs. Multisig

Some blockchain networks offer TSS functionality as a built-in or programmable part of the software. We call this function multisig or multi-signature. To better understand the differences we can look at multisig as a TSS in the implementation phase of the blockchain.

In other words, both multisig and TSS basically try to achieve similar goals but TSS uses off-chain encryption while multisig uses on-chain. However, the blockchain requires a method for multisig encryption, which may compromise privacy because the access structure (number of signatories) is exposed on the blockchain. The cost of a multisig transaction is higher because the information on the two different sites also needs to be communicated on the blockchain.

In TSS, the details of the signatories are folded into a regular transaction, which reduces cost and maintains privacy. Multisig, on the other hand, can be non-interactive, saving the problem of running a complex communication layer between different sites.

The main point of difference is that blockchain multisig needs to be re-implemented on each blockchain and in some cases is not supported at all. In contrast, TSS is based on pure encryption, so it is always supportable. A great article laying out the differences can be found here.


TSS vs. Shamir secret sharing scheme

The Shamir secret sharing scheme (SSSS) provides a distributed way to store the private key. While the private key is in storage 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 creating the secret shares of the key. This means that at the time of key generation, the private key is generated in one place and then distributed by the distributor to the different locations. But in TSS there is no distributor because its role is distributed such that the complete private key is never in one place.

  • Signing: In SSSS the parties must reconstruct the full private key in order to sign which again leads to a single point of failure every time a signature is required. On the other hand in TSS the signing is done in a distributed manner without recreating the secret shares.

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


Threshold Governor

A wallet built on TSS technology is a little different from traditional cryptocurrency wallets. A traditional wallet typically creates a seed phrase and uses it to derive addresses deterministically. The user can later use the deterministic hierarchical structure (HD) to 1) access the private keys that correspond to the wallet addresses and sign transactions with them. 2) To recover all wallet keys using seed phrase.

In threshold wallets things are more complicated. Although it is possible to create a deterministic hierarchical (HD) architecture, its construction must be computed in a distributed manner like another MPC protocol. The parties involved need to make a joint decision on what key will be used next. In other words, each party will have its own initial statement. The seed statements are generated separately and are not combined so that neither party alone can deduce the private keys from the seed statement.

TSS-based wallets also have a nice security feature that allows the private key to be rotated without changing its corresponding public key and blockchain address. Private Key Rotation also known as Proactive Secret Sharing is another MPC protocol that takes secret shares as input and outputs a new set of secret shares. Old secret shares can be deleted and new shares can also be used in the same way.

This architecture adds a temporal dimension to security which means that an attacker would have to be in multiple locations at the same time to attempt a Threshold wallet hack. Combining pre-rotate and post-rotate secret shares would not give an attacker any additional power if he wanted to forge a signature.

The downside of this type of wallet is the lack of a seed phrase which makes it incompatible with single-key wallet systems. It is therefore important to decide which parties will keep confidential sharing.

There are some possible ways such as:

  • TSS Outsourcing: The user will allow “n” servers to run the computation on his behalf. Effectively outsource key creation, management and signing to service providers who are not the owners of the assets but provide a layer of security in exchange for some incentive.

  • Using multiple devices: The user will run TSS on the devices they own. For example, one party would be an IoT device, another party would be a mobile phone user, another third party would be a laptop, and so on.

  • Hybrid Systems: The TSS will be operated such that some parties are controlled by external service providers while some parties run on their own hardware.

The first method offloads the heavy TSS computation on the user client side. On the other hand, service providers can collude (we assume that a large number of them are not under attack at the same time but in practice they can be attacked at the same time) and steal user assets.

The second method gives the user complete control but makes the process of making transactions cumbersome as you need multiple devices to connect to the Internet and participate in the TSS account.

The third option is the best of both the options as it gives the user an easy and quick way to make transactions without the compromise of making transactions without the user's permission.


TSS and smart contracts

Over the years, researchers have found many uses for digital signatures, but some are not surprising. As mentioned earlier, TSS is a primitive encryption that can increase security in a significant way. In the context of blockchain we might say that many functions can be replaced by TSS-based cryptography. Decentralized applications, Layer 2 solutions for scaling, atomic swaps, shuffling, inheritance, and much more can be built on the TSS framework. This will eventually allow expensive and risky smart contract operations to be replaced with cheaper and more reliable alternatives.

To give some concrete examples: Multi-Hop Locks uses two-party signatures in a clever way and can be used to swap Bitcoin's lightning network for a more secure and private payment channel network. ShareLock is probably the cheapest Ethereum blockchain scrambling solution built on verification using a single threshold signature.


Risks

Over the past two years there has been a significant increase in TSS applications. But like any relatively new technology it still has some limitations and concerns. Compared to traditional public key cryptography, TSS protocols can be very complex and have not yet been “tested in action.” TSS usually requires additional, weaker cryptographic assumptions compared to simple digital signatures. As a result cryptographic attack vectors are now being detected that did not exist in traditional settings before (see this presentation from Breaking Bitcoin Conference 2019). Security engineers and application cryptographers can help implement TSS securely into your system.

On the positive side, existing and new applications are becoming stronger due to increased quality contributions, peer reviews, cross-checking, and computational performance improvements using algorithms.


Concluding thoughts

In this article we introduce the basics of Threshold Signature Scheme (TSS), an amazing cryptography primitive that has the potential to dramatically change the way blockchain is used.

Since this article did not discuss the Threshold ECDSA that can be used on Binance Chain and Bitcoin, interested people can read the articles in the following list. Also if you want to try out some TSS implementations you can find code for a 2-party Binance Chain wallet here or try ZenGo wallet which uses the hybrid method of providing a 2-party Binance Chain wallet.


In-depth reading:

  • Fast Secure Two-Party ECDSA Signing

  • Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody

  • Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations

  • Fast Multiparty Threshold ECDSA with Fast Trustless Setup

  • Secure Two-party Threshold ECDSA from ECDSA Assumptions

  • Threshold ECDSA from ECDSA Assumptions: The Multiparty Case