Threshold Signature: How it Works

With growing popularity and adoption of cryptocurrency, keeping your assets safe is as important as ever. When it comes to protecting your crypto assets, keeping your private keys from unauthorized access is crucial, because these are used to withdraw funds from your cryptocurrency account.

Threshold Signature Scheme, or TSS, is a cryptographic signature scheme that can establish higher security levels compared to traditional signature schemes. It is gaining popularity among crypto services providers as a way to ensure secure information flow without interference from external parties like hackers and phishers.

In this article we will look at how threshold signatures work, how these are used to keep your transactions secure and what advantages they have compared to traditional signature schemes.
Public Key Cryptography

To understand the idea behind threshold signature schemes, we must first familiarize ourselves with some important underlying concepts.

Public Key Cryptography (PKC) is an asymmetric encryption system that uses a pair of mathematically linked keys – a public key, used for encrypting, and a private key, used for decrypting information. This system came about in the 1970s to replace the older Symmetric-key Cryptography, where a single key was used for both encryption and decryption. In PKC, the public key can be freely shared and does not compromise security, but the private key must be kept secret, so that only the owner can use it for information decryption.
Blockchain and PKC

In the context of blockchain technology, a key pair is generated when a new crypto wallet is created. The public key is then used to generate the wallet address while the private key is used to create digital signatures and verify transactions. Key pairs are also used when we execute transactions on the blockchain, such as sending and receiving cryptocurrency. You can check our article on key pairs if want to know more.

Now let's take a look at how we use digital signatures to approve blockchain transactions.
Digital Signature Scheme

A digital signature is a mathematical scheme that is used for digital message or document verification. This is fundamental to blockchain technology, because digital signatures are used to authenticate transactions. For example when a user wants to send some bitcoins, a digital signature is used as a proof that this user is authorized to spend these funds.

A digital signature scheme consists of three basic steps – key generation, signature generation and verification. Let’s look at the steps it takes to sign and verify a blockchain transaction:

Key generation: A public/private key pair is created – the private key for signing and the public key for signature verification.
Signature generation: The private key is used together with the transaction to generate a signature.
Verification: The verification algorithm uses a public key together with the transaction to verify that the signature is valid.

Security concerns

For most transactions today, a single signature model is used – that means there is a single approver and a single key used per transaction. And while such approach is easy to implement and low-cost, it also provides the lowest level of security. In case of a crypto transaction – if the holder of the private key gets hacked, their funds are essentially gone.

There are other signature schemes available that overcome the vulnerability of the single signature scheme. One of them is threshold signature scheme, which uses a technique called Multi-party Computation.
Introducing MPC

Multi-party Computation, or MPC is a subfield of cryptography that develops methods for multiple parties to collectively compute a function over their inputs while insuring that these inputs stay private. Let’s look at how this can be used for crypto transactions.

MPC takes a set of n parties and locally generates one key share on each party’s device. This ensures that the entire key never exists on any system at any time and as a result makes key theft significantly more difficult. In addition, the system specifies a subset m out of n parties, that must sign the transaction in order for it to be executed. This allows for a number of parties to be corrupt while the system successfully executes and approves valid transactions.

There are two critical properties every MPC design must follow:

Correctness – the output of the algorithm is correct.
Privacy – Each party’s input is kept private and will not be disclosed to other parties.

As a result of executing an MPC protocol among multiple parties we produce a single signature that can be used to authenticate messages and transactions. Now that we know how MPC functions, let’s see how it is used in TSS.
Threshold Signature Scheme

Threshold signature scheme will produce the same result as a Single-key Digital Signature Scheme, however, it will employ MPC to establish an interactive multi-party protocol to generate private key shares and create a single digital signature. Returning to the signature steps we looked at before, let’s see how these will change if we substitute the key and signature generation steps with an interactive MPC protocol:

Key generation: A set of n parties interactively generate an m out of n sharing of the private key. This is done using direct generation in a shared manner and not locally. As a result, no subset smaller than m has any information about the key. A public key is also generated, which can be done by each party independently, using just their share of the private key.
Signature generation: A signature is generated, but only if m parties agree to sign the transaction. A signature cannot be generated by any subset of less than m parties.
Verification: The verification algorithm uses a public key together with the transaction to verify that the signature is valid. This step remains completely unchanged.

It is important to note, that even though multiple inputs from independent parties are used in the process, only one private key and, consequently, a single signature is created in the end. Because of this, using threshold signatures can provide us with a number of benefits when compared to regular digital signatures. Let's now take a look at what these benefits are.
Advantages of Threshold signature schemes

Security: It is significantly harder for attackers to gain access to a TSS-based crypto wallet, because there is no single point of failure – multiple parties must be compromised in order to get access to the private key. Private key rotation can also be used as an additional safety measure – an MPC protocol that produces new secret shares based on the old ones. The old shares can then be deleted and the new ones used in their place.
Tolerance to failure: Since the threshold number of parties required to approve transactions (threshold set) can be smaller than the total number of secret share holders, the system can sustain multiple participants failing while still being able to generate signatures and approve transactions.
Privacy: The nature of the MPC protocol does not require participants to reveal their secret share to others, which means that every party’s input is kept private. In addition, the signature-generating parties are not exposed or visible over the network.
Flexibility: It is possible to modify the threshold set beyond the simple m out of n notion by using a formula of logical operators as well as employing different threshold sets.
Efficiency and cost : Since only a single signature is generated per transaction, TSS transactions are carried out in a matter of milliseconds. And since only one signature has to be verified, additional verification fees can be avoided, making transactions much cheaper.

Alternatives to Threshold signatures

Using threshold signatures is not the only way of introducing multiple participants to your transactions to improve security. Let's look at two alternative signature schemes and see how they compare to TSS.
Multisig and TSS

Multi-signature, or Multisig is a signature scheme that requires multiple participants to authenticate transactions, just like with threshold signatures. But instead of using secret shares of one key to produce a single signature, it uses multiple keys that produce multiple signatures. This ensures a distributed nature of signature creation, but introduces some disadvantages and potential risks to the system.

In TSS, the cryptography is happening off-chain, which means that while the process involves multiple parties, none of them are revealed or exposed to the network. In fact, from the outside it looks just like a regular, single-key transaction.

On the other hand, Multisig uses an on-chain process, which means that the number of participants is publicly visible on the blockchain. This introduces security risk by exposing the transaction access structure (description of who is involved in the process) and may attract unwanted attention.

In addition, because Multisig transactions require data to be communicated on-chain, the transaction costs increase as well. Threshold signatures, however, keep the costs low due to their off-chain nature.
Shamir secret sharing and TSS

Shamir Secret Sharing Scheme (SSSS) is another example of how threshold signature schemes can be used to cut down on transaction fees and improve security. In essence, SSSS is based on threshold cryptography and functions almost exactly like TSS, but introduces a major security flaw to the process.

First, it uses an entity called "Dealer" to generate an entire key in a single location before distributing the shares between other parties. Second, the signing phase requires the entire private key to be reconstructed, again, in a single location. During both of these instances, there exists a single point of failure for the system, which lowers the overall security of this threshold signature scheme.

As we learned before, TSS eliminates both of these points of failure. Distributed key generation ensures that private keys never exist on a single system at any point in time. Secret shares are generated independently on each participants' device and the signing algorithm uses secret shares in turns, without the need to reconstruct private keys.
Conclusion

Now that we understand how threshold cryptography works, it is easy to see why there is a growing interest in threshold signature wallets, such as TotalSig. Not only are such wallets more secure than traditional single-signature wallets, but they also have significantly lower fees than regular Multisig wallets. And while threshold signature scheme is still a recent addition to the blockchain world, they do have a big potential and we can expect to see a wider adoption of this technology in the future.