Threshold Cryptography III: Binance tss-lib’s 9-Round Threshold ECDSA

In our recent blog, Threshold Cryptography II, we explored the FROST protocol for threshold EdDSA. Compared to EdDSA, threshold ECDSA is significantly more complex due to the difficulty of securely distributing the signature’s non-linear terms. This issue was addressed in GG18 [3] using the Multiplicative-to-Additive (MtA) secret share conversion protocol and Paillier additively homomorphic encryption scheme, enabling a secure and efficient threshold signature scheme.

This protocol enhances fault tolerance and security guarantees, making it suitable for decentralized use cases such as cross-chain bridges, multiparty computation (MPC) wallets, and other blockchain applications that require resilience against single points of failure when nodes (parties) are performing cryptographic signing operations.

Binance tss-lib [1] is a Go implementation of threshold ECDSA protocol based on GG18 [3]. It performs distributed key generation and a 9-round signing protocol, allowing any subset of $t+1$ out of $n$ participants to jointly produce a valid ECDSA signature without reconstructing the secret key.

This third post in the Threshold Cryptography series provides a bird’s-eye view of the 9-round threshold ECDSA protocol implemented in tss-lib [1]. Detailed exposition of the underlying MtA secret share conversion protocol and zero-knowledge proofs will follow in the next two posts.

ECDSA

Elliptic Curve Digital Signature Algorithm (ECDSA) is an elliptic curve variant of the Digital Signature Algorithm (DSA). It operates over a cyclic group $G$ of large prime order $q$, generated by a curve base point $g$ on the elliptic curve. Additionally, a cryptographic hash function $H$ maps arbitrary strings to elements in the prime field $\mathbb{Z}_q$. The notation $+$ stands for curve point addition and $\bullet$ stands for scalar multiplication with a curve point. The secret key is a nonzero scalar $x \in \mathbb{Z}_q^*$ (i.e., nonzero elements in \mathbb{Z}_q$), and its public key is the curve point $y = x \bullet g \in G.

Signature Generation

1. Given a message $M$, compute the hash $m = H(M) \in \mathbb{Z}_q$.
2. Select a random nonce $k \in \mathbb{Z}_q^*$.
3. Compute point $R = k^{-1} \bullet g \in G$ and let $r \in \mathbb{Z}_q$ be its $x$-coordinate.
4. Then compute $s = k \cdot (m+ x \cdot r)$ mod $q$.
5. The ECDSA signature is $\sigma = (r, s)$ where both $r$ and $s$ are scalars in $\mathbb{Z}_q$.

Signature Verification

1. Given a signature $\sigma = (r, s)$, verify $r, s \in \mathbb{Z}_q$.
2. Compute $R' = (m \cdot s^{-1}) \bullet g + (r \cdot s^{-1}) \bullet y$, where $m = H(M) \in \mathbb{Z}_q$ and $y$ is the public key.
3. The signature $\sigma$ is valid if the x$-coordinate of $R' equals to $r$.

Challenge in ECDSA Threshold Signing

Unlike EdDSA, the challenge to create threshold ECDSA lies in the nonlinear terms $k^{-1}$ and $k \cdot x$ during the signature generation. Simply distributing the nonce $k = \sum_i k_i$ and private key $x = \sum_i \omega_i$ among $t+1$ parties do not directly yield signature shares.

To get around with it, the Bar-Ilan and Beaver inversion trick was utilized in the MtA protocol of GG18 [3] by introducing a random value $\gamma$, then computing $\delta = k \cdot \gamma$, and rewriting $k^{-1} = \delta^{-1} \cdot \gamma$.

If $\gamma =\sum_i \gamma_i$ is additively shared among the $t+1$ parties, then $\delta = k \cdot \gamma = \sum_i k_i \cdot \sum_i \gamma_i = \sum_{i,j} k_i \cdot \gamma_j$ is publicly revealed, while $σ\sigma =k \cdot x = \sum_i k_i \cdot \sum_i \omega_i = \sum_{i,j} k_i \cdot \omega_j$ remains secretly shared.

Defining intermediate values $\delta_i = k_i \sum_j \gamma_j = k_i \cdot \gamma_i + k_i \cdot \sum_{i \ne j}\gamma_j$ and $\sigma_i = k_i \cdot \omega_i + k_i \cdot \sum_{i \ne j} \omega_j$, then $\delta = \sum_i \delta_i$ and $\sigma = \sum_i \sigma_i$, so each party holds one share $\delta_i$ and $\sigma_i$.

As long as the multiplicative shares $a \cdot b$ (i.e., each term $k_i \cdot \gamma_j$ in $k_i \cdot \sum_{i \ne j} \gamma_j$ and $k_i \cdot \omega_j$ in k_i \cdot \sum_{i \ne j} \omega_j$) can be converted to additive share $\alpha and $\beta$ such that $a \cdot b = \alpha + \beta$, then each party will hold the additive shares $\delta_i$ and $\sigma_i$ of the product $\delta = k \cdot \gamma$ and $\sigma = k \cdot x$.

9-Round Threshold ECDSA

Binance tss-lib [1] assumes two types of communication channels: a broadcast channel for disseminating messages to all parties except for itself, and a peer-to-peer (p2p) channel for secure, private communication between two individual parties.

The implementation of the threshold ECDSA over the Secp256k1 curve operates in 9 rounds with two additional offline stages, prepare and finalize. In each round, parties validate and process messages received from peers via broadcast or p2p channels, then generate and transmit new messages accordingly.

It assumes that a secret key is distributed to $n$ parties (for example, with methods on secret sharing schemes in the first post) so that each holds a secret share and any $t+1$ parties or more could reconstruct the private key. At the beginning of the protocol, the parties in the group prepared to participate in the signing are predetermined and the group size is $\geq t+1$. For simplicity, we assume that only $t+1$ parties $P_1, \cdots,P_{t+1}$ in the group participate in the ECDSA threshold signing.

Prepare

Given the $t+1$ parties, each party $P_i$ converts its Shamir secret share to additive secret share by multiplying the i$-th Lagrange coefficient $\lambda_i = \sum_{j=1,i\ne j}^{t+1} \frac{p_j}{p_j - p_i}, where $p_j$ is the participant identifier associated to $P_j$ used in the key sharing (Note that the first post on distributed key generation assumes $p_j = j$ for simplicity). Additionally, $P_i$ computes all the public key shares of the $t+1$ parties by taking scalar multiplication with the Lagrange coefficients.

Refer to GG18 [3], Page 11:

Round 1

Each party $P_i$ checks that the hash of message $m$ is within the range of the scalar field of the Secp256k1 curve, then every $P_i$ starts to run the MtA protocol with every other peer to convert the multiplicative shares to additive shares.

1. $P_i$ selects nonce share $k_i \in \mathbb{Z}_q^*$ and auxiliary random value $\gamma_i \in \mathbb{Z}_q^*$.
2. Computes point $\Gamma_i = \gamma_i \bullet g$ and creates its commitment (i.e., hash of the point $\Gamma_i$ and a random value $r$.).
3. With every other P_j$’s Paillier public key, $P_i invokes AliceInit() to encrypt the nonce share $k_i$ (Alice’s share a$) and create range proof of $k_i for each $P_j$.
4. $P_i$ sends the encrypted value (ciphertext) of $k_i$ and its range proof to every corresponding $P_j$ via the p2p channel.
5. $P_i$ broadcasts the commitment to $\gamma_i \bullet g$.

Refer to GG18 [3], Page 11:

Refer to GG18 [3], Page 9:

Round 2

1. Each party $P_j$ invokes BobMid() to

   • verify the range proof from round 1.
   • report the party with invalid range proof.
   • call ProveBob() to create its share $\beta_{i,j}$ and encrypt the share with $\gamma_j$ (Bob’s share $b$) and $P_i$’s Paillier public key, then generate the Bob proof.
   • Aborts if an error occurs.

2. $P_j$ invokes BobMidWC() (i.e., MtA with check) to

   • verify the range proof from round 1.
   • report the party with invalid range proof.
   • call ProveBob() to create its share $\nu_{i,j}$ and encrypt the share with its private key share $\omega_j$ (Bob’s share b$) and $P_i$’s Paillier public key, then generate the Bob proof with check with an extra [Schnorr proof](https://datatracker.ietf.org/doc/rfc8235/) to the $\omega_j.
   • Aborts if an error occurs.

3. $P_j$ sends encrypted shares and Bob proofs to the corresponding peer $P_i$.

Refer to GG18 [3], Page 9:

Round 3

1. Each party $P_i$ invokes AliceEnd() to

   • verify the Bob proof.
   • report the party with invalid Bob proof.
   • decrypt the encrypted share and compute its share $\alpha_{i,j}$.
   • Aborts if an error occurs.

2. Each party $P_i$ invokes AliceEndWC() to

   • verify the Bob proof with check.
   • report the party with invalid Bob proof with check.
   • decrypt the encrypted share and compute its share $\mu_{i,j}$.
   • Aborts if an error occurs.

3. Each party $P_i$ computes the $\delta_i = k_i \cdot \gamma_i + \sum_{i \ne j} \alpha_{i,j} + \sum_{i \ne j} \beta_{j,i}$ and $\sigma_i = k_i \cdot \omega_i + \sum_{i \ne j} \mu_{i,j} + \sum_{i \ne j} \nu_{j,i}$, where $k_i \cdot \gamma_j = \alpha_{i,j} + \beta_{i,j}$ and $k_i \cdot \omega_j = \mu_{i,j} + \nu_{i,j}$.

4. $P_i$ broadcasts $\delta_i$ to other participants.

Refer to GG18 [3], Page 9:

Refer to GG18 [3], Page 11:

Round 4

1. Each party $P_i$ sums over all the $\delta_i$ mod $q$ and computes its inverse mod $q$.
2. $P_i$ creates a Schnorr proof to $\gamma_i$.
3. $P_i$ broadcasts the Schnorr proof with the decommitment in round 1.

Refer to GG18 [3], Page 11:

Round 5

1. Each party $P_i$ verifies P_j$'s commitment and extracts $\Gamma_j from it, then verifies its Schnorr proof.
2. $P_i$ computes the curve point $R = \delta^{-1} \bullet (\sum_j \Gamma_j)$ (equal to k^{-1} \bullet g$) and gets its $x$-coordinate, $r.
3. $P_i$ computes its signature share $s_i = m \cdot k_i + r \cdot \sigma_i$ with the hash of the signing message $m$ and the share $\sigma_i$.
4. $P_i$ selects random values $l_i$, $\rho_i$, then computes $V_i = s_i \bullet R + l_i \bullet g$, $A_i = \rho_i \bullet g$ and creates hash commitment to $V_i$, $A_i$.
5. $P_i$ broadcasts the hash commitment.

Refer to GG18 [3], Page 11:

Round 6

1. Each party $P_i$ creates Schnorr proof to $s_i, l_i$ with $V_i = s_i \bullet R + l_i \bullet g$ and Schnorr proof to $\rho_i$ with $A_i = \rho_i \bullet g$.
2. $P_i$ broadcasts the decommitment in round 5 and Schnorr proofs.

Refer to GG18 [3], Page 11 and 12:

Round 7

1. Each party $P_i$ verifies the hash commitment to $V_i$ and $A_i$.
2. $P_i$ verifies the Schnorr proofs.
3. Reports the party with invalid Bob proof with check. Aborts if it fails.
4. $P_i$ computes $V = (-m) \bullet g + (-r) \bullet y + \sum_j V_j$ and $A = \sum_j A_j$.
5. $P_i$ continues to compute $U_i = \rho_i \bullet V$ and $T_i = l_i \bullet A$.
6. $P_i$ creates the hash commitment to $U_i$ and $T_i$.
7. $P_i$ broadcasts the hash commitment.

Refer to GG18 [3], Page 12:

Round 8

1. Each party $P_i$ broadcasts the decommitment to $V_i$ and $A_i$ from round 7.

Refer to GG18 [3], Page 12:

Round 9

1. Each party $P_i$ computes $U = \sum_j U_j$ and $T = \sum_j T_j$.
2. $P_i$ verifies if $U == T$. Aborts if it is not.
3. Until this point, it is safe for $P_i$ to broadcast its signature share $s_i$.

Refer to GG18 [3], Page 12:

Finalize

1. Each party $P_i$ computes $s = \sum_j s_j$.
2. $P_i$ creates the signature $(r, s)$ and converts it to a standard format with recovery ID to prevent signature malleability.
3. $P_i$ verifies the newly created signature to ensure it is valid.

Conclusion

This post provides a high-level overview of the 9-round threshold ECDSA scheme implemented in Binance tss-lib [1]. The technical details on the MtA secret share conversion protocol and zero-knowledge proofs utilized in the protocol will be covered in the following two posts.

References

1. Binance: https://github.com/bnb-chain/tss-lib
2. Binance: Binance Open-Sources Threshold Signature Scheme Library
3. Rosario Gennaro, Steven Goldfeder, 2018: Fast Multiparty Threshold ECDSA with Fast Trustless Setup (GG18)
4. Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, Udi Peled, 2021: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts (CGGMP21)