programming

By Anika Raghuvanshi, Software Engineer on the Crypto Engineering Team

When generating keys to secure customer funds, we take many precautions to ensure keys cannot be stolen. Cryptocurrency wallets are associated with two keys: a secret or private key, known only to the wallet holder, and a public key, known to the world.¹ To send funds from a wallet, the wallet owner produces a valid digital signature, which requires signing a message (a transaction in this case) with their private key. If a malicious party gains access to the private key, they could steal the wallet’s funds. For most customers, Coinbase has the responsibility of protecting private keys to make sure funds remain secure and out of reach of attackers.

Reusable Keys

During key generation, we segment private keys into shares using Shamir Secret Sharing (SSS) and delete the full key for extra security. Each share is held by a different party, and no individual party has full access to the private key. For a long time, there was one way to create a signature: reassemble private key shares to sign a transaction. Therefore, for our wallets to maintain the highest level of security, we only used an address once. If 1 BTC needed to be withdrawn from a key that stores 100 BTC, the remaining 99 BTC would be sent to a new private key during the withdrawal to ensure that we were not storing funds at a potentially vulnerable address.

However, one-time-use addresses have limits. In addition to the overhead required with continuing to generate keys, an even stronger need for securely reusing keys came along with cryptocurrency staking. Staking generally requires multiple uses of a single long-term address. We needed a way to generate valid digital signatures without reconstructing the private key.

Multiparty computation (MPC) saved the day. MPC protocols allow multiple parties to compute a function together, revealing no other information besides the output. Threshold signing, a specific use of MPC, permits individual parties to collaborate and produce a digital signature without reconstituting the original, composite private key. In practice, this means that rather than parties uploading their private key shares, they individually sign a transaction with their key share and upload a partial signature. These partial signatures² are combined to create the valid signature, which is published to the blockchain.³ Key shares are never uploaded by parties nor combined, therefore maintaining the highest security while allowing keys to be reused.

Threshold Signing Service

We applied MPC to create Threshold Signing Service (TSS). Different cryptocurrency assets use different digital signatures algorithms. We will focus the rest of this article on the TSS protocol for Ed25519 signatures. There are five phases for this protocol:

• Party Key Generation. Creates long-term public and private keys in a trusted environment for parties who will participate in signing. Each party’s private keys are loaded onto Hardware Security Modules (HSMs), which prevent anyone from using the private keys without physical access to the HSM.
• Key Generation. Creates a set of TSS keys and divides the keys using SSS. Uses the public keys produced in party key generation to encrypt each signing key share to the party who will receive it.
• Nonce Generation. Round 1 of 2 of the signing protocol. Participants in this round generate nonce values and send them to all other parties.
• Partial Sign. Round 2 of 2 of the signing protocol. Participants use the nonce shares received from other parties and their signing key share to generate partial signatures.
• Generate Final Signature. Combine partial signatures into the final result.

The first two phases occur rarely (once in the lifetime of a signing key). The final three phases repeat every time a transaction, which we call a message, is signed. The next section takes a technical deep dive into the signing phases of the protocol.Ed25519 Signatures

The method for generating a digital signature for an Ed25519 key is as follows: Ed25519 is the EdDSA signature scheme that is parameterized to SHA-512 and Curve25519. For elliptic curves, G is the base point and q is the base point order. Given a message m to be signed and a private key k, a signature is produced as follows:

Our threshold signing protocol is an adaptation of the threshold Schnorr signature scheme by Gennaro, Jarecki, Krawczyk, and Rabin.

In the protocol, participants generate both the nonce r and signature s in a distributed fashion without reconstituting the underlying private key. In Round 1, participants produce and distribute nonce shares rᵢ. In Round 2, participants compute the composite nonce r from the nonce shares rᵢ and produce partial signatures sᵢ, which the server combines to produce the composite signature s. The final signature is identical to the signature which would be produced by combining secret shares and signing the original message with the composite private key.

Nonce Generation

In Round 1, participants use the message m and the key share kᵢ to do the following

After t participants have completed the nonce generation, signing begins.

Nonce Aggregation

After t nonces have been posted, participants perform Round 2 by aggregating the nonce shares to derive the composite nonce. Each participant i performs:

Partial Signatures

Participants create partial signatures⁴, which can be combined to generate the signature s.

Each participant i performs:

Signature Aggregation

Finally, the server aggregates components into signature that can be verified with public key K.

Below is an example that combines two partial signatures without Shamir sharing:

As long as the challenge, c, is the same for both signatures, the nonce and private key shares behave linearly under addition. Due to this property, we can apply the standard Shamir’s reconstruction to the sᵢ values to construct s:

This result, along with nonce public key R, is a valid signature. The server verifies the signature (R, s) using message m and public key K and checks the nonce value R has not been previously used.

From Concept to Production

Deploying a production-level system involves solving for certain real-world problems. For example, getting attention from human participants can take a long time (on the order of hours). Since the protocol supports human participants, we run the risk of delaying transaction approval for too long. For example, the cryptocurrency Algorand has a short validation time: just a few hours. If we cannot compute a signature over a transaction in this time frame, partial progress must be discarded. Two of our design decisions help reduce the burden for humans approving transactions: 1. Rounds are asynchronous, meaning participants do not have to participate at the same exact time, and 2. Each round requires a threshold of parties, but both rounds do not require the same set of participants to participate.

Another challenge is the issue of storing secret information, since the devices used to store key shares and participate in the signing protocol could be lost or broken. This led to a model where parties are relatively stateless: the only state they have is a small amount of long term storage on HSMs, which are highly secure, portable, and durable. Participants in the signing protocol do not communicate with each other: a centralized server stores all artifacts, such as nonce shares and partial signatures. A natural concern to come up is what happens if a centralized server is compromised — we investigate this threat and other threat models in the following section.

Security

TSS has two primary security goals:

1. Without the private key, an attacker should not be able to generate a valid signature over an unauthorized message. This is known as existential unforgeability under adaptive chosen message attack and is the expected security for a digital signature scheme.
2. Private key privacy after the key generation ceremony. This should protect against an attacker who has access to some (less than threshold t) private key shares.

Below are some attacks we considered and defenses we created for selected threat models.

Server Trust. The centralized server transfers messages between participants.

• Attack: Unauthorized access to data.
  Defense: All secret data uploaded to the server must be encrypted to the intended participant. The server has no access to private keys, so cannot access data in the messages it relays.
• Attack: Manipulation of data.
  Defense: Participants validate every piece of data provided by the server, and halt the protocol if they detect data modification.
• Attack: Data loss.
  Defense: Data from key generation ceremonies are backed up through our disaster-recovery processes (not discussed in detail here) and can be recovered in the case of server data loss.

Participant Trust. Participants hold onto key shares and participate in the signing protocol.

• Attack: Individual participant performing existential forgery.
  Defense: Participants have the critical responsibility of validating data provided by the server. Any participant can abort the protocol and trigger incident response procedures if malicious activity is detected.
• Attack: Participants colluding to perform existential forgery.
  Defense: Since any single participant can halt the protocol if they detect malicious activity, the protocol requiring t participants remains secure with up to t — 1 malicious participants. An additional protection against collusion is supporting a hybrid participant model: a combination of humans and servers. We use weighted secret sharing to ensure that every signing requires participation from both human and server participants. This further increases the barrier for compromising t participants.
• Attack: Nonce Reuse. A well-known attack for Schnorr-style signatures is using the same nonce multiple times on different messages. This leads to a trivial recovery of private keys, compromising our second security goal and opening the door for an immediate loss of funds.
  Defense: Nonce shares encode information about the message, making it simple to detect nonce reuse upon decryption. Having a two-round protocol allows participants to authenticate nonce shares in Round 2 and abort if they detect nonce reuse.

Key Issuer Trust. The key issuer generates private keys and distributes key shares.

• Attack: Exfiltrating secrets from a key generation ceremony.
  Defense: The process of generating keys is a fully documented and audited process, which requires that all plaintext of keys are destroyed before the culmination of the key generation ceremony.

Through this threat modeling, we see that a malicious entity needs to compromise a threshold of participants to have any chance of stealing funds. We carefully calibrate the human and server participant thresholds with this in mind to ensure that our funds maintain the highest level of security.

Summary

TSS for signing payloads over the Ed25519 curve is an elegant and simple service: it takes as input a message payload and produces a valid signature, after a series of signers interact with the two-round protocol. This service provides a solution for reusing cold keys without bringing them online. Through translating a full cryptographic protocol to a real life service, we created TSS, the first production-level threshold signing service in existence to secure billions of dollars in assets.

Footnotes

1. More precisely, the public key is used to derive the wallet’s address, which is known to the public.
2. that are invalid in isolation
3. The blockchain does not have to be aware of nor support special logic for threshold signatures, since the signature created is the same signature created using the composite private key.
4. Using the message as associated data for encryption. This ensures that this nonce can only be used for signing this message. This defends against nonce-replay attacks that lead to private key recovery.

Read more about Cryptography at Coinbase.

If you are interested in the complexity of applying threshold cryptography, Coinbase is hiring Cryptographers and Software Engineers.

This website contains links to third-party websites or other content for information purposes only (“Third-Party Sites”). The Third-Party Sites are not under the control of Coinbase, Inc., and its affiliates (“Coinbase”), and Coinbase is not responsible for the content of any Third-Party Site, including without limitation any link contained in a Third-Party Site, or any changes or updates to a Third-Party Site. Coinbase is not responsible for webcasting or any other form of transmission received from any Third-Party Site. Coinbase is providing these links to you only as a convenience, and the inclusion of any link does not imply endorsement, approval or recommendation by Coinbase of the site or any association with its operators.

All images herein are by Coinbase.

Production Threshold Signing Service was originally published in The Coinbase Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.