Threshold Signatures

Privacy requires randomness, but to understand how the Keep network will get that randomness, we have to understand threshold signatures.

This is the second article in a series exploring the underlying concepts behind modern decentralized systems, including the Keep network, a privacy layer for Ethereum.

A common underpinning of secure systems is randomness: security often requires unpredictability, which in turn depends on being able to generate random numbers. As such, the first component of the Keep network that will be released is a public random beacon that can generate random numbers on demand for any Ethereum application — including the Keep network itself.

Over the next few posts, we’ll introduce various concepts that explain the random beacon, starting from the base concepts and building to a description of how the beacon itself works. Before we get to the high levels of how the random beacon works, however, we need to understand cryptographic signatures and their close relative, threshold signatures.

Why Signatures?

Signatures are a basic underpinning of cryptographic security. A signature is a way for someone to prove that a certain message came from them and has not been tampered with. So for example, say Alice sent a message to Bob, “The sky is gray in London today.”

If Bob receives that message, he doesn’t know if Eve intercepted “It’s a sunny day in London!” and modified it to make the day dreary.

A signature is an additional value you can send alongside the message that will prove to Bob that the message is exactly what Alice sent.

In public key cryptosystems, the sender signs their message with their private key, which no one else can access. This produces a number that the receiver can check against the message and the sender’s public key, to verify that the message was not tampered with. In mathematical terms, given a private key s, a public key p, and a message M, the signature function S(s, M) produces a number σ. That number can then be verified using the verification function V(p, σ, M), which produces true if the message does in fact match the signature, or false otherwise.

Signatures let us communicate information in public, while still ensuring that the information itself has not been tampered with.

Multiple Signatures

One drawback of the simple version of signatures described above is that it is limited to a single sender. When that sender is the one individual that is producing the message, that’s okay. In certain cases, however, the message can be from a group, and in those cases using simple signatures requires trusting one member of the group. That is, if Alice’s family wants to send Bob’s family a message, and they decide that Evelyn, Alice’s mischievous 12-year-old daughter, will be the one to sign the message, Evelyn can sign a different message, send it and its signature to Bob’s family, and they will be none the wiser that this wasn’t the intended message.

The simple way to solve the above problem is to ask for more than one signature. Rather than just let Evelyn sign the message, Evelyn and Alice both sign the message, and Bob can check both to make sure everything was right. As a bonus, this makes sure that Alice can’t secretly include any embarassing stories about Evelyn in the family message.

One downside of this is that it can require a lot of extra work and data. Say that Evelyn’s soccer team wants to send Bob’s family a thank you note for the jerseys they helped them buy. That team is all 12-year-olds, so trusting any one of them to send the right note can be a real leap of faith. If the whole team signs, however, with 11 players and 10 on the bench, that’s 21 people who have to sign, and the message now has to include 21 signatures! As if that’s not enough hassle, Bob’s family has to then check the message against all 21 of those signatures to be certain none of Evelyn’s teammates worked together to tamper with the message.

Threshold Signatures

Bob’s family isn’t willing to jump through all these hoops, but they’re willing to accept that no one will be able to convince 5 players on the team to all tamper with a message that the team as a whole agreed to send. This is where the concept of a threshold signature comes into the mix. A threshold signature is a special way of doing multiple signatures where given a group of participants, some minimum number of them have to contribute a share of the signature in order to produce a single overall valid signature. This means we have a way of making a signature that’s only valid if at least 5 of the 21 team members contribute a share. If only 4 of the team members work together to sign the message, the resulting signature is completely invalid. If 5 or more of the team members work together, then the overall signature they produce will be valid (assuming the message hasn’t been changed).

Based on work done by the Dfinity team, we’ve decided Keep will use a threshold signature scheme called BLS, after the initials of the three authors of the paper who proposed it, Boneh, Lynn, and Shacham. That scheme was fundamentally geared towards producing shorter signatures than the ones typically seen for single signers, but it also has the property of allowing for threshold signatures. In addition, by relying on some additional work by Genarro, Jarecki, Krawczyk, and Rabin, the key generation needed to be able to produce the keys used for signing messages and verifying signatures can be done in a distributed way, which eliminates the need for a single participant to be trusted.

BLS signatures combined with the linked distributed key generation provide us with some really nice guarantees:

• There is relatively little coordination required to set up everyone’s participation in the group that can produce threshold signatures. The little coordination that is required is simply to verify that each participant is honest and then produce the group’s public key from the participants’ shares.
• No single member of the group has to be trusted; instead, in the distributed key generation, each participant generates their piece of the puzzle, and then broadcasts some information that allows the other participants to verify that their generation process was in fact correct — or call them out if not.
• The key generation step is resilient in the face of up to half the participants being malicious or failing to generate. The signature scheme similarly supports up to half the participants being malicious or failing to sign.

This gives us the right properties to create signatures that are resilient to both attacks and network issues.

Random Beacons and Threshold Signatures

The random beacon Keep will be providing needs to be robust in the face of network failure and provably reliable in the face of bad actors, so a scheme that lets us operate without having to trust or rely on any single individual participant is a powerful tool. With BLS threshold signatures in hand, we have a key component of a robust, reliable beacon, which in turn is the first building block of the Keep privacy network.

Have a look at our random beacon alpha API demo and Keep’s random beacon in action posts, as well as at our approach on the road to mainnet.
Be sure to leave us a comment with your thoughts!

Learn More

For more information about the Keep Network:

• Join us on Reddit.
• Check out our whitepaper.
• Read our business primer.
• Subscribe for email updates.
• Follow us on Twitter.
• Join our Slack.
• Join our Telegram.