The ECDSA tax: a field guide to threshold signing

Two vendors sell you an “MPC wallet”. Both keep the key in shares that never meet, both produce ordinary signatures, both have a whitepaper with a lock icon on it. One of them signs in two rounds of 282 bytes. The other one runs nine rounds of Paillier ciphertexts and zero-knowledge proofs, and its protocol family has spent the last five years getting patched against key-extraction attacks. The difference between them is not engineering quality. It is one line of algebra, and it was decided in 1992, long before anyone tried to split a key.

I recently implemented three of these protocols from scratch - FROST, CGGMP, and DKLs23, in one codebase, zig-mpc - and benchmarked them against the reference implementations they were ported from. This article is the map I wish I’d had at the start: what the families are, why they exist, what each one costs, and where the bodies are buried.

The tax, in one equation

A Schnorr signature - which includes Ed25519 and Bitcoin’s Taproot flavor - is

s = k + e·x

where x is the private key, k is a fresh nonce, and e is a hash everyone can compute. Look at the shape of it: the secrets appear added together, each multiplied only by public values. If three parties hold shares of x that sum to the key, and shares of k that sum to the nonce, then each party computes its own little s_i = k_i + e·x_i, the shares are added up, and the sum is a valid signature. Nobody ever holds x. Nobody has to do anything clever. The entire threshold problem reduces to “agree on the nonce commitment first so nobody can bias it”, which is what FROST spends its two rounds on.

An ECDSA signature is

s = k⁻¹ · (m + r·x)

Same ingredients, catastrophically different shape. That k⁻¹ is the inverse of a secret that must never exist in one place, and it multiplies x, another secret that must never exist in one place. Shares of k do not give you shares of k⁻¹. Shares of k and shares of x do not give you shares of k·x. To sign, the parties must jointly compute products and an inversion of numbers none of them knows, and prove to each other they did it honestly - because a party that cheats in this step doesn’t just break the signature, it can walk away with the key.

Everything else in this field - the Paillier encryption, the oblivious transfer, the range proofs, the nine-round protocols, most of the CVEs - is the bill for that inversion. That is the ECDSA tax. You don’t pay it because your vendor is bad. You pay it because Bitcoin, Ethereum and every EVM chain settled on ECDSA before threshold signing was a requirement anyone had.

EdDSA and Schnorr sit on the other side of the line, and the price difference is not subtle. Later in this article there’s a table where the same library, on the same machine, signs with FROST in 3 milliseconds and with threshold ECDSA in 5 seconds.

The family tree

Every practical threshold-ECDSA protocol answers one question: how do two parties multiply secrets they don’t have? There are two mainstream answers, and they define the two lineages. A third lineage - Schnorr - never has to answer it.

The Paillier lineage encrypts one secret under Paillier - an encryption scheme where you can multiply a ciphertext by a known number and the plaintext gets multiplied too. Party A sends an encryption of k_A, party B multiplies it by x_B inside the ciphertext, adds a mask, and sends it back. Neither learned the other’s secret; together they now hold additive shares of the product. The catch: Paillier needs an RSA-sized modulus per party, generating one needs safe primes, and a maliciously crafted modulus is a weapon - so the protocols wrap everything in zero-knowledge range proofs, and the setup ceremony proves your modulus is well-formed before anyone will talk to you. Lindell’s 2017 protocol did this for two parties and made MPC wallets practical; GG18 extended it to t-of-n; GG20 added identifiable aborts (when signing fails, you learn who broke it); CMP and CGGMP21 rebuilt it with UC security proofs, presigning, and proactive share refresh. CGGMP21 has been revised repeatedly since publication - the 2024 revision is what I implemented.

The OT lineage replaces the encryption with oblivious transfer: a primitive where a receiver picks one of two values a sender offers, the sender doesn’t learn which, and the receiver doesn’t learn the other. Chain a few hundred of these and you can build multiplication out of what is essentially binary long multiplication, using only elliptic-curve and hash operations - no RSA, no safe primes, no aux ceremony. Doerner, Kondi, Lee and shelat built the 2-of-2 version in 2018, t-of-n in 2019, and DKLs23 is the current form. The trade: OT-based signing moves a lot more bytes.

The Schnorr lineage is FROST, now RFC 9591. Two rounds, tiny messages, and the code is small enough to actually read in an afternoon. If your chain verifies Ed25519 (Solana, Cardano, TON) or BIP-340 Schnorr (Bitcoin Taproot), the tax simply doesn’t apply to you. I walked through a live in-browser FROST ceremony in an earlier article, including what happens when a participant cheats.

There’s a fourth answer - class-group-based encryption that removes the RSA modulus while keeping the homomorphic approach - which is elegant and has seen little production uptake, so I’ll leave it as a pointer.

One more distinction worth naming, because vendors blur it: 2-of-2 is a different problem from t-of-n. Lindell17 and DKLs18 are two-party protocols - your phone and the vendor’s server, each useless alone. They are dramatically simpler than general threshold schemes, which is exactly why they shipped first and why several “2-of-N” products are really a two-party protocol run against N different counterparties. Simpler is not worse. It is, however, a different trust model than 3-of-5 across your own infrastructure, and the marketing rarely tells you which one you bought.

Who actually ships what

The implementations below are the ones you’ll actually encounter if you go looking. I cloned and built each of them; the audit claims are from the repos and reports themselves.

Lindell17: Unbound’s blockchain-crypto-mpc (C++, protocols designed by Yehuda Lindell, archived read-only since September 2021 with the notice “Unbound will not provide any security updates”; the company was later acquired by Coinbase) and ZenGo’s gotham-city two-party wallet. This is the “simple 2-of-N” workhorse of the industry.

GG18: bnb-chain/tss-lib (Go), the implementation behind Binance’s TSS and half the bridges you’ve used. Audited by Kudelski Security in October 2019. Its signing protocol runs nine rounds plus finalization - you can count the round_1.go through round_9.go files.

GG18 + GG20 + Lindell17 in one box: ZenGo’s multi-party-ecdsa (Rust), the research library much of the ecosystem learned from - audited in 2019, and now archived with a note that deserves quoting: “This repository is no longer maintained… Zengo will not provide any security updates or hotfixes (should an issue arise).” It is still being forked into production systems today.

CMP: Fireblocks’ mpc-lib (C++), their open-sourced production algorithms - MPC-CMP for ECDSA plus threshold EdDSA - audited by NCC per the repo’s SECURITY.md. It built cleanly for me, though its benchmark harness is shaped around their cosigner service, so I didn’t extract a comparable number.

CGGMP21: Taurus’ multi-party-sig (Go), the cleanest open CGGMP implementation, with both the online and presigning variants - and an honest disclaimer: “needs further testing and auditing to be production-ready.”

DKLs23: two independent implementations, and the contrast between them taught me more than any paper. Silence Labs’ dkls23 (Rust, audited by Trail of Bits in April 2024, non-commercial license) and 0xCarbon’s dkls23-core (Rust, MIT/Apache, unaudited). Same paper, different engineering choices - more on that below.

FROST: Zcash Foundation’s frost crates (Rust, RFC 9591, audit report from March 2021 shipped in the repo), plus FROST implementations inside Taurus’ library and mine.

Where the bodies are buried

Threshold ECDSA’s attack history is not a story of sloppy programmers. It is a story of protocols with so many moving parts that audited implementations kept falling to the same class of bug: a missing check on something an honest party would never send.

December 2021, Alpha-Rays (Tymokhanov and Shlomovits): two key-extraction attacks on GG18/GG20 implementations. The worse one exploits implementations that ran the multiplication step without range proofs - a documented performance option - and pulls the full key with eight signatures. The other uses a deliberately small Paillier key, a value no honest party would generate and which nothing in most implementations rejected. The GG18 paper on eprint was revised three days after the attack went up, with the changelog “Fixes some issues in the protocol and security proof.”

August 2023, TSSHOCK (Verichains, presented at Black Hat): three attacks - α-shuffle, c-split, c-guess - against GG18/GG20/CGGMP21 implementations, several of them enabling full key extraction from a single malicious participant. The line from their disclosure that should be printed on every vendor’s slide deck: nearly all implementations they examined were vulnerable “despite having undergone multiple security audits.”

Also August 2023, BitForge (Fireblocks): CVE-2023-33241, the missing small-factor check on the Paillier modulus in GG18/GG20 implementations - key extraction in 16-bit chunks, full key in about sixteen signatures - and CVE-2023-33242, against Lindell17 implementations that mishandled aborts and kept signing, leaking a bit at a time until roughly 200 signatures gave up the key. Affected parties included ZenGo, Coinbase WaaS and BitGo; the vendors patched. The paper version is eprint 2023/1234, and it’s worth reading just to see how mundane the openings were.

Three patterns worth extracting. First, every one of these is in the Paillier lineage. That is partly age and deployment share - attackers go where the money is - but it is also surface area: the security of GG-style protocols rests on a stack of number-theoretic side conditions (modulus well-formed, no small factors, ranges proved, aborts handled) and each unchecked condition was someone’s CVE. The OT lineage’s checks are fewer and more mechanical; FROST barely has any to forget. Second, “audited” is a statement about effort, not a property of the code. The TSSHOCK targets were audited. tss-lib was audited in 2019; Alpha-Rays and BitForge both landed afterward. An audit samples a moment. Third, the reference implementations everyone forks are abandoned. ZenGo’s library and Unbound’s are explicitly unmaintained, with attack papers published after maintenance ended. The forks did not all get the memo.

If you take one operational question from this section: ask your vendor which protocol they run, which implementation it descends from, and what their story was in August 2023. A vendor who can’t answer the first question can’t have answered the other two. I’ve written before about what vendor recovery tooling does and doesn’t prove; protocol disclosure belongs on the same checklist.

Numbers from one machine

Benchmarks in papers are run on the authors’ hardware with the authors’ favorite parameters. These are all from my workstation - an i7-10510U laptop core, everything pinned to a single CPU so concurrency can’t flatter anyone, every number the total across all parties. Absolute values are modest (it’s a laptop); the ratios are the point.

First, the tax itself, measured inside one codebase - Taurus’ multi-party-sig, Go, three parties, two signers, their own example harness with timing added:

Same authors, same language, same curve. Threshold ECDSA costs three orders of magnitude more than threshold Schnorr, until presigning hides the cost - a trade we’ll come back to, because it isn’t free.

Second, the three families side by side in my own codebase, same harness, 2-of-3 with two signers throughout:

The CGGMP row needs an honest asterisk: those numbers use a 1152-bit Paillier modulus, a demo parameter set. At production size - 2048-bit modulus, safe primes, 80 proof repetitions - the same harness measured 5.9 minutes per party just to generate the safe primes, a 31-second aux ceremony, and a 9.8-second presign. Prime generation is the long pole, which is why every serious deployment generates primes offline and why tss-lib ships precomputed test fixtures. For calibration: tss-lib’s GG18 keygen for five parties took 56 seconds on this machine with the expensive Paillier parameters already precomputed, and its 3-of-5 signing took 2.6 seconds end to end. The ZF frost crates, for contrast, sign in sub-millisecond steps (63 µs round one, 220 µs round two, 304 µs aggregation in their seven-signer Ed25519 criterion bench).

Third, one protocol, three implementations - because implementation choices matter almost as much as protocol choices. DKLs23, keygen-through-first-signature, three parties:

The interesting fact is why the audited one is fastest: the same base-OT paper can be instantiated with or without per-instance zero-knowledge proofs, and Silence Labs chose without, leaning on the random-oracle structure instead. About 1,500 elliptic-curve operations per party-pair exist in my implementation solely to carry proofs theirs doesn’t send. I kept the proof-carrying variant anyway, because it matches the reference implementation byte for byte - which means every random oracle in my port is cross-checked against an independent codebase. Faster or checkable against someone else’s bugs: that’s a real tradeoff, and reasonable people land on both sides.

The tradeoffs nobody puts on the pricing page

Rounds are latency, not compute. A nine-round protocol between a phone in Berlin and an HSM in Virginia pays nine WAN round trips; at 100 ms each, the network dwarfs every benchmark above. This is why round count was the headline metric in every paper from GG18 onward, and why DKLs23’s three rounds and FROST’s two matter more in production than their CPU times. Conversely, if your signers share a rack, rounds are nearly free and you should stop paying for round-reduction with complexity.

Presigning converts latency into risk. CGGMP’s party trick - grind the expensive part before the message exists, sign in one message when it arrives - is genuinely valuable for trading systems. But a presignature is a nonce that already exists, stored on disk, waiting. Use one twice and you’ve published your key share; that is not a theoretical footnote, it is mechanically the same mistake as CVE-2023-33242’s abort mishandling. Every presigning deployment needs presignature state management with the same seriousness as key management. FROST has the same property in miniature (its round-one commitments are nonces), which is why RFC 9591 spends so many words on never reusing them.

Identifiable abort is an operations feature, not a security feature. GG20 and CGGMP can tell you which party broke a signing session; GG18 and plain DKLs generally abort without blame. With three parties in one company this is a debugging nicety. With five parties across four organizations and an SLA, “the ceremony failed and we can’t say who caused it” is a governance incident. Price accordingly.

Setup amortizes; know your denominator. The Paillier lineage front-loads minutes of ceremony and then signs relatively cheaply forever. The OT lineage front-loads about a second and pays ~25 ms and ~80 KB per signature. FROST front-loads nothing worth mentioning. A custody vault signing twice a week and an infra wallet signing ten times a second should not choose the same protocol, and neither should copy a market maker’s presigning architecture because a blog said it was fast.

Bytes are the quiet constraint. FROST messages fit in a text message. DKLs signing moves ~80 KB per pair - fine on any real network, awkward over Bluetooth to a hardware signer. GG-style messages are Paillier-ciphertext-sized but the protocols are chatty across many rounds. If your transport is constrained or metered, this row of the table can dominate the decision.

What I’d actually pick

If your chain verifies Schnorr or EdDSA, use FROST and collect the refund. This isn’t advanced advice; it’s the consensus position, it’s an RFC, and the remaining excuses are inertia. Taproot means Bitcoin qualifies.

If you need threshold ECDSA for a 2-of-2 wallet product, Lindell17-style protocols remain a defensible choice if you inherit a maintained implementation and treat abort handling as the security boundary BitForge proved it is. What you should not do is fork an archived research repo whose own authors promise you nothing.

If you need t-of-n ECDSA and are building fresh, my order of operations is: DKLs-family first (small assumption set, no Paillier ceremony, mechanical checks), CGGMP where presigning or identifiable abort is a hard requirement (and budget for the state management that comes with it), and GG18/GG20 not at all in 2026 - not because the papers are refuted, but because the implementation ecosystem around them is where four years of key-extraction papers went hunting, and the successor exists.

And whichever row of the table you buy: the protocol name is a question your vendor should answer in one word, and the August 2023 question - “what did BitForge and TSSHOCK mean for you?” - is one they should answer in one paragraph. The tax is real, it’s been priced, and the receipts are public.

About the implementation: the zig-mpc numbers come from a codebase I built implementing FROST (RFC 9591), CGGMP24 and DKLs23 in Zig, with DKLs23’s random oracles kept byte-compatible with 0xCarbon’s Rust implementation so the two can check each other. It is unaudited, pre-production software - the benchmarks are honest, the security claims are aspirational. The interactive companion piece, a live threshold ceremony in your browser, runs the same code as WebAssembly. Benchmark harnesses for the other libraries are their own: tss-lib’s end-to-end tests, Taurus’ example driver with timing added, and ZF frost’s criterion suite, all pinned to one core of an i7-10510U.