How Threshold ECDSA Signs

In the previous note the key was split so that each party holds an additive piece x_i with d = Σ x_i. Schnorr signatures can use that directly. ECDSA can't, and the reason is worth working through.

The obstacle

Recall the ECDSA signing equation:

r = (k \cdot G)_x \bmod n, \qquad s = k^{-1}(z + r d) \bmod n

With additive shares k = Σ k_i and d = Σ x_i, there are two non-linear steps:

the inverse k⁻¹ of a sum is not the sum of inverses
k⁻¹·d is a product of two secrets that are each split across parties

Both come down to multiplying two secret-shared values. If you hold a = Σ a_i and b = Σ b_j, the product is:

ab = \sum_i \sum_j a_i b_j

The diagonal terms a_i·b_i are local. The cross terms a_i·b_j mix two different parties' secrets and need a protocol.

Multiplicative-to-additive conversion (MtA)

MtA lets party i holding a_i and party j holding b_j end up with additive shares of the product, without learning each other's inputs:

\alpha_{ij} + \beta_{ji} = a_i b_j \pmod n

One classic construction uses Paillier encryption, which is additively homomorphic. Party i sends E_i(a_i) under its own key. Party j picks a random mask β' and replies with:

c = E_i(a_i)^{b_j} \cdot E_i(-\beta') = E_i(a_i b_j - \beta')

Party i decrypts to get α_ij = a_i·b_j - β', and party j keeps β_ji = β'. They sum to the product, and neither party holds it. Oblivious-transfer based variants do the same job without Paillier.

Getting R without exposing k

The trick used in the GG18 and GG20 family is to avoid inverting a secret. Each party also picks a random γ_i, and the group computes the product δ = k·γ with MtA over every pair:

\delta_i = k_i \gamma_i + \sum_{j \ne i} (\alpha_{ij} + \beta_{ji}), \qquad \text{so} \quad \sum_i \delta_i = k\gamma

Each δ_i is published. The sum δ = kγ is safe to reveal because γ masks k. Meanwhile every party publishes Γ_i = γ_i·G, and everyone computes:

R = \delta^{-1} \sum_i \Gamma_i = (k\gamma)^{-1} \cdot \gamma G = k^{-1} G

So the shared point is k⁻¹·G, the inverse is applied to a public scalar, and nobody learned k or γ. Set r = R.x mod n.

Producing s

With R = k⁻¹·G, the effective ECDSA nonce is k⁻¹, so the signature scalar becomes:

s = (k^{-1})^{-1}(z + r d) = kz + r k d

Both terms are things the parties can hold in additive form. The product k·d is again a product of two shared secrets, so one more round of MtA gives shares σ_i with Σ σ_i = k·d. Each party then outputs:

s_i = z k_i + r \sigma_i, \qquad s = \sum_i s_i \bmod n

The signature (r, s) is an ordinary ECDSA signature. The verifier can't tell it was produced by several parties, and the chain doesn't need to know either.

What this sketch leaves out

The above is the algebra, and it is not a safe protocol on its own. Real implementations add a lot:

Zero-knowledge proofs. Each party must prove its MtA messages are well formed and its values are in range. Published attacks on implementations that skipped or mis-implemented these checks have extracted private key shares.
Commit-reveal for the Γ_i. Without commitments, a party that sees others' values first can bias the result.
Identifiable abort. Newer protocols such as CGGMP21 are designed so that when a signature fails, the culprit can be identified instead of the round silently failing.
Preprocessing. Rounds that don't depend on the message can be done in advance, so the online signing step is short.
Different building blocks. DKLs-style protocols replace Paillier with oblivious transfer extension, trading communication for computation.

Why bother

All of that machinery exists to produce a signature that looks like any other one. The payoff is operational: a stolen laptop or a compromised server holds a share that is useless on its own, and approval policy can sit in front of the signing round instead of hoping the key holder behaves. The cost is a more complicated protocol to implement, test, and operate than a single key, and that cost deserves honesty in any design discussion.