Threshold Digital Signatures: How to Keep Your Crypto Secure

Threshold digital signatures keep your crypto safer than ever. Here’s how they work.

Digital signatures are a foundational concept in blockchain and cryptocurrencies. Modern blockchains use digital signatures to secure billions of dollars of value. Digital signatures use what is known as a key-pair, a pair of random looking values, where one key is a “private key” and the other a “public key.” Through digital signatures, any person with the private key can sign a transaction and spend the digital currencies. Therefore, it is crucial to safeguard the private key.

Some tech-savvy users of blockchains opt to safeguard the private key themselves and accept the risk of theft or loss of the key (and therefore the loss of their funds). In contrast, other blockchain users trust online wallets or exchanges with the safeguarding of their keys. Of course, this decision comes with its own set of risks based on the competency of the third party.

In both these options, the user puts all their trust in a single entity, which may not be desirable. Enter the threshold digital signature: a solution which requires a threshold of at least two cooperating participants to produce a signature, and which removes the problem of trusting a single entity.

In this article we:

• Explain threshold signatures and their applications

• Dig a bit deeper and look into various threshold signature schemes

• Compare threshold signatures with other techniques, such as mulitsig wallets

What Is a Threshold Signature?

As a developer in the space of threshold cryptography, it’s really exciting to see these innovations becoming a mainstream topic, but readers unfamiliar with cryptography or the math behind it quickly hit roadblocks upon encountering phrases like “Paillier cryptosystem,” “homomorphic encryption” or “Galois field.” This process gets even more complicated when you discuss all the moving pieces to coordinate communication.

Consequently, very few organizations have been willing to investigate the potential of threshold cryptography. But it doesn’t have to be scary; in the end, the math comes down to multiplication and addition. So let’s ELI5: What the heck is a threshold signature?

In metaphorical terms, signatures are akin to flying a kite on an invisible string. The kite itself is the public key — everyone can see it in the sky. The kite flier moves the kite around by manipulating the invisible string — the private key. The path it takes in the sky as it flies is the signature. Everyone saw the kite fly through the sky in that path, and only through the use of that invisible string was that flight path possible. This feels really simplified compared to the underlying math, but ultimately this metaphor demonstrates the coordination and work required to make threshold signing possible.

In order to fly the kite, the threshold number of people must come together and combine their threads into a single string again.

Enter threshold cryptography. The premise of threshold is literally in its name: The operation must meet some numerical value to succeed. Oftentimes these processes are defined using t of n, where n is the number of total possible participants, and t is the threshold number that must be met.

Shamir’s secret sharing scheme is a common threshold cryptographic scheme that’s been in use for quite some time. For the uninitiated, the process uses a mathematical technique called Lagrange interpolation to recombine split values into a secret value. In other words, we’re taking that invisible string and separating it into individual threads that many people can hold on to. In order to fly the kite, the threshold number of people must come together and combine their threads into a single string again.

Services all over the world use this process to secure secret data. The downside is that everyone involved must complete the process in a secure location when breaking apart and recombining the secret. In cryptocurrencies, this also means that once the private key is recombined and used for signing, it should be considered exposed and all funds held by the key should be moved, so if any participant who helped in recombining the key walks away with it, they can’t do anything meaningful. This is expensive and, needless to say, requires a lot of coordination of people.

What if we can take the powerful math behind cryptography and improve upon this process so nobody has to ever meet in a secure location at all?

The great news is that we can! Navigating this field requires significant time and expertise, but at Coinbase, we’ve found and implemented strategies that enable us to leverage and support these novel approaches as they are discovered and peer reviewed.

So how does it work? The innovation here is in the process we use to help our (kite) pilots take flight in the first place. Each participant follows the same rule: They bring their own invisible thread and their own piece of kite. Each pilot agrees with the others in advance about how they’re going to fly, and they all proceed to run with their piece of kite at the agreed speed, angle and time. If anyone strays from the agreed flight plan, the whole tangled mess of kites comes crashing to the ground, but if everyone proceeds as agreed, the kite takes off as one combined piece through the sky, able to perform the flight as planned.

When the flight concludes, the parts disassemble mid-air, and everyone goes home with their kite and thread. At no point does any one person hold the whole kite or string, and each party sees the flight plan ahead of time to know that nobody is going to try some wild antics that will let them run away with the kite.

A Deeper Dive Into Threshold Signatures

Now that we have an understanding of threshold signatures, let’s dive deeper into the concepts and technology. The threshold signature schemes are part of the secure multi-party computation (MPC) field of cryptography. The main goal of MPC is to enable computation on private data without revealing the private data to anyone but the owner.

For example, in the kite metaphor, the invisible pieces of the thread are the secret shares of the private key and threshold signature uses these secret shares to reconstruct the private key and sign the transaction without revealing the composite private key or the secret shares.

A very important ingredient of threshold signing is a mathematical construct called Elliptic curve cryptography.

TL;DR: Given y=x*g, where y and g are publicly known values, it’s very hard (or even impossible) to find x in a reasonable time frame. There are many curves that offer this property:

• Secp256k1: used in Bitcoin, Ethereum and many others

• Edwards25519: used in Cardano, Monero and many others

• BLS12–381: used in Ethereum 2.0 and some other chains

Given an appropriate elliptic curve, the next step towards a threshold signature is to first choose a standard (i.e. single-signer) digital signature scheme. The popular digital signature schemes are as follows:

• ECDSA: based on the Secp256k1 curve used by Bitcoin

• Schnorr: based on the Secp256k1 curve used by Bitcoin Cash and Mina

• Ed25519: based on the Edwards25519 curve used by Cardano

Now that we have a digital signature we can discuss threshold signature schemes. The threshold signature schemes start from a single-signer scheme and split the private key between n participants. Then, in the signing phase, t-out-of-n participants can run the signing algorithm to obtain the signature.

Finally, any single (external) party can verify the signature using the same algorithm used to verify the single-signer signatures. The signatures generated by threshold signature and single-signer signature schemes are interchangeable. In other words, a threshold signing algorithm has three phases.

1. Generate the public/private key pair. Next, split the private key into multiple secret shares and distribute these shares between the n parties. This phase can be performed in two modes:

• Trusted Dealer Mode: A single trusted party will generate the private key, then split and distribute the keys. The main problem with this approach is that the dealer will see the private key in plaintext.
• Distributed Key Generation (DKG): An MPC protocol runs between the n participants such that at the end, the participants will obtain the secret shares and no one will ever see the private key in plaintext at any point in the process.

2. Gather a threshold of t participants and run an MPC protocol to sign the transaction.

3. Verify the signature, using the standard signature’s verification algorithm.

​​​​​​The threshold signature schemes are fast evolving. At the time of writing this post, the secure and popular schemes include the following.

• FROST: A threshold signature and DKG protocol that offers minimal rounds of communication and is secure to be run in parallel. FROST protocol is a threshold version of the Schnorr signature scheme.

• DKLs18: A two-out-of-two threshold signature and DKG protocol that offers fast signature computation for ECDSA signature scheme.

Threshold Signatures and Multisig

Multisig, or multisignature schemes offer similar capabilities to threshold signatures with one major difference: Each participant has their own public key (instead of secret shares of a single common public key). This small difference has a huge impact on cost, speed and availability of the multisig on various blockchains.

EFFICIENCY

In threshold signature schemes, each public key, and its corresponding private keyshares, belong permanently to a single, fixed group of signers; in multisignatures, each individual participant has its own distinct, dedicated public key. The benefit of the latter is that each such participant can reuse their private-public keypair to participate in many distinct signing groups.

The cost of using multisignatures, however, is that the size of the public key (actually, a list of public keys) representing any particular such group must grow linearly with the number of members of that group. Similarly, the verification time of a multisignature obviously must grow linearly with the size of the group, as the verifier must read the entire list of public keys representing the group. In threshold schemes, by contrast, just one public key represents the entire group, and both key size and verification time are constant.

AVAILABILITY

To ensure a group meets the minimum threshold t, the blockchain should have native support for multisignatures. In most cases, this support comes in the form of a smart contract. As a result, not all blockchains support multisig wallets. In contrast, the MPC-based threshold signatures are independent of the blockchain as long as the signature scheme used by the blockchain has a secure threshold version.

Threshold digital signatures enable us to do incredible things previously not possible in cryptocurrencies. Now we can support a whole new tier of wallets; this threshold ECDSA approach allows customers to be an active participant in this signing process.

With this approach, the user holds a share of the private key, and Coinbase holds another. Only when both agree to the flight plan can transactions receive a signature. This provides the security and trust Coinbase is known for, while the user remains the one in control.