By Cassandra Heart, Arash Afshar
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 keypair, 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 this 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 is putting 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:
As a developer in the space of threshold cryptography, it’s really exciting to see these innovations becoming a topic in the mainstream, but readers unfamiliar with cryptography or the math behind it quickly hit roadblocks upon encountering phrases like “Paillier cryptosystem”, “homomorphic encryption” or “Galois field”. It gets even more complicated when you discuss all the moving pieces behind it to coordinate the communication, and as a consequence, very few organizations have been willing to investigate its potential. But it doesn’t have to be scary; at the end, the math comes down to not much more than 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 is useful for demonstrating the coordination and work required to make threshold signing possible.
Enter threshold cryptography. The premise of threshold is literally in its name: some numerical value must be met for an operation to succeed. Oftentimes these processes are defined using the phrase “t of n”, where n is the number of total possible participants, and t is the threshold number that must be met. A common threshold cryptographic scheme that has been used for quite some time is Shamir’s secret sharing scheme. For those unfamiliar, the process involved uses a mathematical technique called Lagrange interpolation to recombine split values into a secret value. In the metaphorical world, it is taking that invisible string, and separating it into individual threads that many people can hold onto, and in order to fly the kite, the threshold number of people must come together and combine their threads into the string again.
This process works well, and services all over the world use it to secure secret data. The downside is that everyone who is involved must do this 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 not to mention, requires a lot of coordination of people. What if we can take the powerful math behind cryptography and improve upon this so that nobody has to ever meet in a secure location at all?
The great news is that we can! There are mountains of literature that have risen overnight with new approaches to existing cryptosystems, improvements on previous ones, and completely groundbreaking cryptographic protocols. Navigating this field requires significant time and expertise, but here at Coinbase, we have found and implemented strategies that enable us to leverage these approaches, and support the novel approaches as they are discovered and peer reviewed. There’s a lot involved in this process, so let’s bring it back to the metaphor.
The setup process for getting our avid kite fliers ready is ultimately the unique twist that enables this entire process to work: each participant follows the same rule: they bring their own invisible thread, and their own piece of kite. Each flier agrees with the others in advance how they are 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 into 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.
Now that we have an intuitive understanding of threshold signatures, let’s dive deeper into the concepts and terminologies. 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 them to anyone but the owner of the private data. 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, nor the secret shares.
A very important ingredient of threshold signing is a mathematical construct called Elliptic Curve Cryptography. The TL;DR version is that given y = x · G, where y and G are publicly known values, it is very hard or even impossible to find x in a reasonable time frame. There are many “curves” that offer this property: