# The Discrete Log Held; The Proofs Leaked: A Field Guide to Commitments and Sigma Protocols
> How the discrete log stayed hard for forty years while the proofs built on it kept breaking: Pedersen commitments, Schnorr, Sigma protocols, and Fiat-Shamir.
*Published: 2026-07-13*
*Canonical: https://paragmali.com/blog/the-discrete-log-held-the-proofs-leaked-a-field-guide-to-com*
*© Parag Mali. All rights reserved.*
---
A discrete-log zero-knowledge proof is one three-move conversation -- commit, challenge, respond -- and for forty years every real break landed on one of those moves, never on the discrete logarithm underneath. Move 1, the commitment: Pedersen hides perfectly and binds on the discrete log, but a trapdoor-holder can equivocate. Move 2, the Fiat-Shamir challenge: hash too little and you get weak Fiat-Shamir, the Frozen Heart bug that forged "zero-knowledge" proofs in Helios (2012) and in Bulletproofs and PlonK (2022) with the math untouched. Move 3, the response: reuse the nonce and the witness falls out by algebra; exploit its linearity across concurrent sessions and the ROS attack forges naive multisignatures in polynomial time. This is the field guide to those three moves -- Pedersen, Schnorr, Sigma protocols, Fiat-Shamir -- how they compose into Bulletproofs, MuSig2, FROST, Signal's credentials, and Privacy Pass, and every documented way each has been gotten wrong.
## 1. The Math Was Fine. The Proofs Were Forgeable.
In April 2022, Trail of Bits published a coordinated disclosure with an unsettling shape [@tob-part1]. Across three unrelated "zero-knowledge" proof systems -- Girault's classic proof of knowledge, Bulletproofs (the range proof securing confidential Monero transactions), and PlonK (a modern general-purpose SNARK) -- the proofs were *forgeable*. An attacker could produce a convincing proof of a statement that was simply false [@tob-part1], [@tob-girault], [@tob-bp], [@tob-plonk].
And in none of the three cases had anyone broken the discrete logarithm, or factoring, or any hard problem. The math was untouched. The bug was that a single hash had omitted part of the statement it was supposed to be about [@tob-part1].
> **Note:** In every Frozen Heart case, the discrete logarithm was never solved. The forgery lived entirely in what a hash function failed to bind. Soundness turned out to be a property of the protocol's plumbing, not of the hard problem beneath it.
The Bulletproofs instance was the sharpest. Trail of Bits traced it to an insecure Fiat-Shamir generation *recommended in the original 2017 Bulletproofs paper itself* -- the flaw was in the specification, not a careless implementer's shortcut [@tob-bp], [@bulletproofs]. It received a CVE: CVE-2022-29566 [@cve]. A vulnerability class was born, and Trail of Bits named it. The word "Frozen" is the acronym -- FoRging Of ZEro-kNowledge proofs; "Heart" nods to the Fiat-Shamir transform that sits at the heart of these proof systems [@tob-part1].
Then the twist that makes it a pattern, not an incident: this exact bug had already been named and published a decade earlier. In 2012, David Bernhard, Olivier Pereira, and Bogdan Warinschi showed that the Helios internet-voting system used the same shortcut -- and that its "zero-knowledge" ballot proofs could be transplanted and forged the same way [@bpw]. Two breaks, ten years apart, identical root cause, and the second one shipped in production behind a CVE.
Now widen the aperture. The discrete logarithm -- the hard problem under Diffie-Hellman, Schnorr, ElGamal, and the whole family -- has resisted forty years of attack; [nobody broke the discrete log](/blog/nobody-broke-the-discrete-log-a-field-guide-to-diffie-hellma/), as Part 18 argued at length. Yet the proof systems built on top of it break with some regularity. Why?
Because a discrete-log zero-knowledge proof is not one thing. It is a three-move conversation -- **commit, challenge, respond** -- and each move is a separate attack surface. The prover sends a commitment, the verifier sends a random challenge, the prover sends a response, and one equation decides the outcome.
Frozen Heart and Helios are failures of the second move, the challenge. Reusing a signature nonce -- the catastrophe that [hands over a private key when one number repeats](/blog/one-number-used-twice-how-a-repeated-nonce-hands-over-your-p/) (Part 8) -- is a failure of the third move, the response. A trapdoor that lets a committer change its mind after the fact is a failure of the first move, the commitment. Three moves, three ways to leak, and not one of them is the discrete logarithm.
That is the whole thesis of this article, stated once so you can hold it through everything that follows: **the discrete log held; the three moves leaked.** The hard problem underneath these systems has never fallen. The conversation built on top of it has failed, repeatedly, in ways that are precise, named, and preventable.
The reach of these three moves is easy to underestimate. The same commit-challenge-respond skeleton runs under Bitcoin's Taproot multisignatures, under Monero's confidential transaction amounts, under Signal's private group membership, and under the digital-identity credentials now standardizing at the IETF. Master the three moves and you have a lens that resolves an entire branch of applied cryptography -- and a checklist that separates a deployment that ships from one that ships a CVE.
Those three moves were not invented together, and the cleanest one was invented first and deployed last -- frozen for nearly two decades by a patent [@schnorr-patent]. To see why the conversation has exactly three moves, and why each one leaks, we start where the vocabulary was born.
## 2. The Three-Move Conversation
Strip away the applications -- the multisignatures, the range proofs, the credentials -- and there is one shape underneath all of them. Learn that shape precisely, and every guarantee and every failure in this article becomes a statement about one of its three parts.
The archetype is Schnorr's protocol for proving you know a discrete logarithm. You have a public key $y = g^x$ in a group of prime order $q$ generated by $g$, and you want to convince a verifier that you know the secret exponent $x$ without revealing it. The conversation has exactly three moves:
1. **Commit.** Pick a fresh random nonce $r$ and send the commitment $a = g^r$.
2. **Challenge.** The verifier picks a random $e$ and sends it back.
3. **Respond.** Send $z = r + e\cdot x$.
The verifier accepts if and only if $g^z = a\cdot y^e$. Check the algebra: $g^{r + e x} = g^r\cdot (g^x)^e = a\cdot y^e$. It works whenever the prover really knows $x$.
A three-move public-coin proof -- commitment, then a random challenge, then a response -- in which the verifier checks a single equation. It must satisfy two properties: special soundness and special honest-verifier zero-knowledge. Schnorr's proof of knowledge of a discrete logarithm is the archetype [@damgard].
sequenceDiagram
participant P as Prover (knows x)
participant V as Verifier (knows y)
Note over P: pick fresh random nonce r
Note over P: commitment a holds g to the r
P->>V: send commitment a
Note over V: pick random challenge e
V->>P: send challenge e
Note over P: response z holds r plus e times x
P->>V: send response z
Note over V: check g to the z equals a times y to the e
Why is this a *proof*, and why does it reveal nothing? Both answers are visible by inspection, which is exactly why Schnorr is the teaching example.
### Two accepting transcripts hand you the secret
Suppose a prover produces two accepting conversations that share the same commitment $a$ but have different challenges $e_1 \ne e_2$, with responses $z_1$ and $z_2$. Then $g^{z_1} = a\cdot y^{e_1}$ and $g^{z_2} = a\cdot y^{e_2}$. Divide the two equations and the $a$ cancels: $g^{z_1 - z_2} = y^{e_1 - e_2}$. Since $y = g^x$, the exponents must match, and you can solve for the witness:
$$x = \frac{z_1 - z_2}{e_1 - e_2} \pmod q.$$
This is **special soundness**, and the algorithm that recovers $x$ is called the *extractor*. It is what makes Schnorr a proof of *knowledge*: a prover who can answer two different challenges on the same commitment demonstrably possesses $x$, because we could run the extractor and read it out [@damgard].
The property that two accepting transcripts sharing a commitment but with different challenges yield the witness through an efficient extractor. It is what upgrades a Sigma protocol from "the statement is true" to "the prover actually knows a witness" [@damgard].
Hold on to that extractor. In Section 6 we will watch an attacker run exactly this formula -- same $a$, two different $e$ values -- against a signer who reused a nonce, and read out the private key. The defender's soundness proof and the attacker's key-recovery are the same three lines of algebra.
### One accepting transcript hands you nothing
Now run the trick the other way. Pick the response $z$ and the challenge $e$ *first*, both at random, and then define the commitment as $a = g^z\cdot y^{-e}$. By construction $g^z = a\cdot y^e$, so this transcript passes verification perfectly -- and you built it without knowing $x$ at all. The distribution of $(a, e, z)$ produced this way is identical to a real run.
The property that any accepting transcript can be produced without the witness by choosing the response and challenge first and back-solving for the commitment. The algorithm that does this is the simulator, and its existence proves the exchange reveals nothing about the secret [@damgard].
That algorithm is the *simulator*, and its existence is the proof that the conversation leaks nothing about $x$: anything a verifier sees, it could have generated by itself. The whole edifice of zero knowledge -- the idea that "reveals nothing" can be made mathematically precise by demanding a simulator -- traces to Goldwasser, Micali, and Rackoff in 1985 [@gmr]. Part 1 covers those [security definitions](/blog/secure-against-whom-the-security-definitions-every-protocol-/) in full; here we take them as the bedrock they are.
> **Key idea:** A Sigma protocol is one three-move conversation -- commit, challenge, respond -- whose two guarantees are both visible by inspection. Two accepting transcripts on the same commitment extract the secret (special soundness); a single transcript can be simulated without the secret (special honest-verifier zero knowledge). Two transcripts hand you the key; one transcript hands you nothing. That knife-edge is the entire game.
The distinction the extractor forces is worth naming. A Sigma protocol is a **proof of knowledge** -- the prover provably *possesses* a witness -- not merely a **proof of membership**, which would only assert that the statement is true. The gap matters: "this public key has a corresponding private key" is trivially true for every well-formed key, but "I know that private key" is the thing a signature must establish.
A proof that the prover actually possesses a witness, formalized by the existence of an extractor that could recover the witness from a successful prover. It is strictly stronger than a proof of membership, which asserts only that the statement is true [@damgard].
The simulator is not just a proof device; it is a construction tool. To prove "I know the secret behind public key A OR the one behind B" without revealing which, the prover *honestly* runs the branch it can answer and *simulates* the branch it cannot -- choosing that branch's challenge and response first and back-solving for its commitment, exactly as SHVZK allows. A shared challenge, split between the branches, ties them together so a cheater cannot simulate both at once. That is the Cramer-Damgard-Schoenmakers OR-proof, and it is why the toolkit composes into disjunctions, ring signatures, and selective-disclosure credentials [@cds].
Here is that whole story in code. The extractor is not a metaphor; it is a five-line function that turns two transcripts into a private key.
{`
// A toy prime-order group: the order-q subgroup of the integers mod p.
// p = 2039 is prime, q = 1019 is prime, and g = 4 has order exactly q.
const p = 2039n, q = 1019n, g = 4n;
const mod = (a, m) => ((a % m) + m) % m;
function powmod(base, exp, m) {
let r = 1n; base = mod(base, m);
while (exp > 0n) { if (exp & 1n) r = mod(r * base, m); base = mod(base * base, m); exp >>= 1n; }
return r;
}
const invModQ = (a) => powmod(a, q - 2n, q); // inverse mod prime q, via Fermat
const x = 777n; // the secret witness (never sent)
const y = powmod(g, x, p); // public key y = g^x
// One honest run with nonce r and challenge e:
function transcript(r, e) {
const a = powmod(g, r, p); // commit
const z = mod(r + e * x, q); // respond
return { a, e, z };
}
const verify = (t) => powmod(g, t.z, p) === mod(t.a * powmod(y, t.e, p), p);
const r = 314n; // ONE nonce, reused across two challenges
const t1 = transcript(r, 11n);
const t2 = transcript(r, 90n); // same a, different e -- the fatal pair
console.log('t1 verifies = ' + verify(t1) + ', t2 verifies = ' + verify(t2));
// The extractor: x = (z1 - z2) / (e1 - e2) mod q
const xRecovered = mod((t1.z - t2.z) * invModQ(mod(t1.e - t2.e, q)), q);
console.log('recovered x = ' + xRecovered + ', true x = ' + x + ', match = ' + (xRecovered === x));
`}
That is the knife-edge in code: two transcripts hand you the key, one hands you nothing -- so every guarantee and every failure ahead is a statement about one of the three moves. But this clean picture took eleven years and five separate ideas to assemble, and the cleanest idea of all sat frozen behind a patent.
## 3. Five Ideas and a Patent (1985-1996)
The three-move conversation was assembled one idea at a time, mostly by people who were not trying to build it. And the sharpest tension in the story is this: the cleanest, smallest scheme in the whole toolkit was invented in 1989 and could not be legally deployed at scale until its patent expired around 2008 [@schnorr-patent]. The best piece shipped last. Here is how five disconnected papers became a coherent toolkit.
**Goldwasser, Micali, and Rackoff (1985)** gave the field its vocabulary. Their paper on the knowledge complexity of interactive proof systems defined zero knowledge through the simulator argument -- a proof reveals nothing if a simulator can produce the same transcript without the secret [@gmr]. Without this definition, none of the three moves would be analyzable; "reveals nothing" would be a slogan rather than a theorem.
**Fiat and Shamir (1986)** contributed two things in one paper. First, a practical zero-knowledge identification scheme based on factoring. Second, and far more consequential, the *transform* that bears their name: replace the verifier's random challenge with the output of a hash function, and the interactive protocol collapses into a non-interactive one -- a signature [@fiat-shamir]. This is the birth of Move 2, and it arrived as a heuristic, a plausible trick without a proof. That gap between "plausible" and "proven" is where three decades of trouble would later live.
**Schnorr (1989)** produced the efficient discrete-log archetype we dissected in Section 2: three moves, special soundness by inspection, and -- once you apply Fiat-Shamir -- the compact Schnorr signature.Schnorr's US Patent 4,995,082, granted in 1991, is widely reported to have expired around 2008. That is why patent-free DSA and later ECDSA colonized the internet through the 1990s, 2000s, and 2010s while Schnorr-proper waited, and why Bitcoin's BIP-340 could finally standardize native Schnorr signatures only in 2020 [@schnorr-patent], [@bip340]. Part 17 tells that [signature story](/blog/the-math-held-the-interface-leaked-a-field-guide-to-digital-/). The irony is total: the scheme with the cleanest security argument was the one the market could not touch, so the industry standardized on messier alternatives and lived with them for twenty years.
**Pedersen (1991)** was working on verifiable secret sharing, not commitments, when he handed the field its Move 1 workhorse.The Pedersen commitment debuted as a *byproduct* of a non-interactive, information-theoretically secure verifiable secret sharing scheme [@pedersen]. The toolkit's most-used commitment arrived as a side effect of a paper about something else -- a recurring pattern in this history. His commitment $C = g^m\cdot h^r$ is perfectly hiding, computationally binding, and additively homomorphic [@pedersen] -- three properties we will spend all of Section 4 unpacking, because the entire range-proof line stands on the third one.
**Cramer, Damgard, and Schoenmakers (1994)** turned Schnorr from a single protocol into a toolkit. Their proofs-of-partial-knowledge construction composes Sigma protocols with AND and OR: prove you know *one* of two secrets without revealing which, by honestly answering the branch you know and *simulating* the branch you do not [@cds].The name "Sigma protocol" was coined later, in Cramer's 1996 doctoral thesis. The letter is said to trace the three-move zig-zag of the conversation -- commitment down, challenge across, response back -- though the mnemonic is folklore. The OR-proof trick reuses the very simulator that proves zero knowledge, now as a constructive building block [@cds]. This is the deep reuse the article keeps returning to -- the simulator that proves a single proof leaks nothing is the same object that fakes the clauses you cannot answer in a disjunction. Okamoto's 1992 identification scheme sharpens the point: it is the witness-indistinguishable sibling of Schnorr, with a two-generator, Pedersen-shaped first move $y = g^{x_1} h^{x_2}$.Because many witness pairs $(x_1, x_2)$ open the same $y = g^{x_1} h^{x_2}$, an Okamoto transcript never reveals *which* pair the prover used -- the scheme is witness-indistinguishable by construction [@okamoto]. That is exactly the property a CDS OR-proof leans on to hide which clause is the real one, and it is why the Pedersen shape shows up again the moment you want to hide a witness among many.
**Pointcheval and Stern (1996)** finally proved that Fiat-Shamir signatures are unforgeable -- in the random-oracle model -- with the forking lemma: rewind a successful forger, feed it a different challenge on the same commitment, and its two answers extract the discrete log, contradicting hardness [@pointcheval-stern-96], [@pointcheval-stern]. The proof works, but it is *loose*: it loses a quadratic factor, and it does not extend cleanly to many sessions running at once. That looseness is not a blemish to be polished away later -- it is the first visible crack of the concurrency failure that Section 6 tears wide open.
flowchart LR
A["1982 Chaum blinding"] --> B["1985 GMR zero knowledge"]
B --> C["1986 Fiat-Shamir transform"]
C --> D["1989 Schnorr identification"]
D --> E["1991 Pedersen commitment"]
E --> F["1994 CDS OR-proofs"]
F --> G["1996 forking lemma"]
G --> H["2018 Bulletproofs"]
H --> I["2021 ROS and MuSig2"]
I --> J["2024 FROST RFC 9591"]
J --> K["2026 BBS drafts"]
By 1996 the conversation was complete and had a name. The rest of the story is what happened when people started *building* with it -- and the failures organize themselves, cleanly, one per move. Start with the move you make first: the commitment.
## 4. Move 1: What You Bind
Every proof begins by pinning down a value you are not yet ready to reveal. A commitment is the cryptographic envelope: you seal a value now and open it later, and the sealing must satisfy two opposing demands. It must be **hiding** -- the sealed envelope leaks nothing about what is inside -- and **binding** -- you cannot swap the contents after sealing. There are two standard ways to build one, and they sit at opposite corners of a trade-off you cannot escape.
A protocol to lock in a value now and reveal it later, such that the commitment leaks nothing about the value (hiding) and cannot be opened to a different value than the one committed (binding). No scheme can make both properties perfect at once [@damgard].
### The Pedersen corner
Pedersen's commitment lives in a group of prime order $q$ with two generators $g$ and $h$, where nobody knows the discrete logarithm $\log_g h$. To commit to a message $m$, pick a random blinding scalar $r$ and publish
$$C = g^m\cdot h^r.$$
It has three properties, and each one matters downstream [@pedersen]:
- **Perfectly hiding.** Because $r$ is uniform, $h^r$ is a uniform group element, so $C$ is uniformly distributed regardless of $m$. Even an adversary with unlimited computing power learns *nothing* about $m$ from $C$. This is information-theoretic, not merely computational.
- **Computationally binding.** Opening $C$ to two different messages means finding $(m, r) \ne (m', r')$ with $g^m h^r = g^{m'} h^{r'}$, which rearranges to $\log_g h = (m - m')/(r' - r)$. In other words, breaking binding *is* computing a discrete logarithm. The binding reduction is not near the hard problem; it *is* the hard problem [@pedersen].
- **Additively homomorphic.** Multiply two commitments and the exponents add: $C(m_1, r_1)\cdot C(m_2, r_2) = C(m_1 + m_2,\ r_1 + r_2)$. You can add committed values without opening them.
That third property is the one the whole range-proof line stands on, so hold it in mind. But first, the precision that must never be smoothed over.
> **Note:** A Pedersen commitment is perfectly *hiding* and only *computationally* binding. Anyone who knows the trapdoor $\log_g h$ can **equivocate**: open a single commitment to any message they like, by solving one linear equation for a matching blinder. The security of the whole scheme rests on nobody knowing that trapdoor -- which makes the generation of $h$ a security-critical step, not a formality.
Equivocation is the entire Move-1 failure class. If the party who set up the parameters secretly chose $h = g^t$ and kept $t$, then for any commitment $C = g^m h^r$ they can produce a blinder $r'$ that opens it to a different message $m'$ -- because $C = g^{m + t r}$, and they can solve $m' + t r' \equiv m + t r$ for $r'$. The defense is to make the trapdoor un-knowable to everyone.The second generator $h$ must have unknown $\log_g h$, so it is derived by a nothing-up-my-sleeve procedure -- hash a fixed string to a curve point, so that no party could have planted a trapdoor. Part 16 covers [hashing a string into the group](/blog/the-doorway-into-the-group-a-field-guide-to-hashing-a-string/); the takeaway here is that "pick $h$ honestly" is a real engineering requirement, not a throwaway line.
### The hash corner
The dual construction throws away the algebra. Commit to $m$ by publishing `H(m ‖ r)` for a random $r$ and a collision-resistant hash `H`. This is computationally hiding and computationally binding -- and its binding rests on collision resistance, not on the discrete logarithm, which makes it the post-quantum-friendly choice. What it gives up is homomorphism: there is no way to add two hash commitments and get a commitment to the sum. Hashes shred structure by design.
Why can you not have everything -- perfect hiding *and* perfect binding? Because it is impossible. If a commitment is perfectly hiding, then $C$ is statistically independent of $m$, which means some opening to every message must exist; a computationally unbounded opener could always equivocate, so binding cannot also be perfect [@damgard]. Pedersen sits at the perfectly-hiding end; hash commitments sit near the perfectly-binding end; nothing sits at both.
flowchart TD
Q{"What does the job need?"}
Q -->|"add or range-prove values"| PED["Pedersen commitment g to the m times h to the r"]
Q -->|"post-quantum binding, no algebra"| HASH["Hash commitment H of m with r"]
PED --> P1["perfectly hiding"]
PED --> P2["computationally binding on the discrete log"]
PED --> P3["additively homomorphic"]
PED --> P4["trapdoor holder can equivocate"]
HASH --> H1["computationally hiding and binding"]
HASH --> H2["not homomorphic"]
HASH --> H3["post-quantum from collision resistance"]
Here is the corner choice as a table you can keep next to a design review.
| Property | Pedersen `g^m · h^r` | Hash `H(m ‖ r)` |
|---|---|---|
| Hiding | Perfect (information-theoretic) | Computational |
| Binding | Computational (discrete log) | Computational (collision resistance) |
| Homomorphic | Yes, additively | No |
| Post-quantum | No -- Shor breaks binding | Yes -- binding survives Shor |
| Commitment size | ~32 bytes (one ristretto255 point) | ~32 bytes (one SHA-256 output) |
| Equivocation risk | Trapdoor holder of `log_g h` opens to anything | None -- needs a hash collision |
| Best suited for | Confidential amounts, range proofs, sums | PQ binding, timestamps, no algebra needed |
The homomorphism is not a curiosity; it is the concrete cash-in of Move 1. Committed values that add correctly are exactly what confidential transactions need -- inputs and outputs whose hidden amounts must balance -- and they are the value commitments that a range proof later proves lie in a valid range. Section 7 follows that thread from Pedersen to Bulletproofs. First, watch the homomorphism and the equivocation trapdoor in code.
{`
const p = 2039n, q = 1019n, g = 4n;
const mod = (a, m) => ((a % m) + m) % m;
function powmod(base, exp, m) {
let r = 1n; base = mod(base, m);
while (exp > 0n) { if (exp & 1n) r = mod(r * base, m); base = mod(base * base, m); exp >>= 1n; }
return r;
}
// In a real system NOBODY knows t; we plant it here only to demonstrate equivocation.
const t = 503n; // the trapdoor: t = log_g h
const h = powmod(g, t, p);
const commit = (m, r) => mod(powmod(g, m, p) * powmod(h, r, p), p);
// 1) Additive homomorphism: C(m1,r1) * C(m2,r2) opens to (m1+m2, r1+r2)
const C1 = commit(100n, 7n), C2 = commit(250n, 9n);
const product = mod(C1 * C2, p);
const summed = commit(mod(100n + 250n, q), mod(7n + 9n, q));
console.log('homomorphism holds = ' + (product === summed));
// 2) Equivocation: the trapdoor holder opens ONE commitment to a different message
const m = 100n, r = 7n, C = commit(m, r);
const mFake = 999n;
const rFake = mod(r + (m - mFake) * powmod(t, q - 2n, q), q); // solve m'+t r' = m+t r
console.log('same C reopened to ' + mFake + ' = ' + (commit(mFake, rFake) === C));
`}
A Pedersen commitment binds a value the verifier cannot see. But an interactive proof about it needs a live verifier to send a random challenge -- and live verifiers do not scale to signatures or blockchains. The fix is to fake the verifier with a hash. That single fix is the most-broken move in the toolkit.
## 5. Move 2: What Goes Into the Hash
The transform that makes the whole toolkit shippable is one line of code -- and that one line has been written wrong, in production, for thirty years.
The interactive Sigma protocol needs a live verifier to supply a random challenge $e$. That is fine for a login handshake and useless for a signature or a blockchain, where there is no verifier standing by. Fiat and Shamir's fix was to *derive* the challenge from a hash of the transcript so far: compute $e = H(\dots)$ yourself and proceed [@fiat-shamir]. In the random-oracle model -- where the hash is treated as a truly random function -- the hash *is* the verifier, and the interactive proof becomes a non-interactive one.
A method to make an interactive Sigma protocol non-interactive by replacing the verifier's random challenge with a hash of the transcript. The prover computes the challenge itself, turning a proof of knowledge into a signature or an on-chain proof [@fiat-shamir].
An idealization that treats a hash function as a truly random function answering consistently to repeated queries. It is the model in which Fiat-Shamir soundness is provable; Part 10 covers the [hash machinery](/blog/the-fingerprint-two-files-shared-a-field-guide-to-cryptograp/) it idealizes [@fiat-shamir].
Everything now rides on what you put inside that hash. And this is where the failures cluster, because the answer is not obvious and the wrong answer still runs.
### The decision rule
**Strong Fiat-Shamir** binds everything the proof is about:
$$e = H(\texttt{domain\_separator} \,\|\, \text{statement} \,\|\, \text{public params} \,\|\, a \,\|\, \text{transcript}).$$
**Weak Fiat-Shamir** hashes only the commitment, $e = H(a)$, and omits the statement. That omission is the bug. When the challenge does not depend on the statement, a proof built for one statement can be transplanted onto another -- a statement it was never made for -- and it still verifies [@bpw]. The extreme case is a signature: if the message is not in the hash, a signature on "pay 5" is a valid signature on "pay 5000," because verification never touches the message.
flowchart TD
A["Sigma commitment a and statement x"] --> B{"What enters the challenge hash?"}
B -->|"weak FS: only a"| W["e is H of a"]
B -->|"strong FS: statement, params, a"| S["e is H of x with params and a"]
W --> W2["challenge ignores the statement"]
W2 --> W3["transplant the proof onto a false x prime"]
W3 --> W4["forgery verifies"]
S --> S2["challenge binds the exact statement"]
S2 --> S3["transplant recomputes a different e"]
S3 --> S4["forgery rejected"]
You can watch the transplant happen and then watch the fix stop it. In the model below, the "statement" is the signed message; weak Fiat-Shamir lets one signature verify against any message, and strong Fiat-Shamir binds it.
{`
const p = 2039n, q = 1019n, g = 4n;
const mod = (a, m) => ((a % m) + m) % m;
function powmod(base, exp, m) {
let r = 1n; base = mod(base, m);
while (exp > 0n) { if (exp & 1n) r = mod(r * base, m); base = mod(base * base, m); exp >>= 1n; }
return r;
}
function H(str) { let h = 0n; for (const ch of str) h = mod(h * 131n + BigInt(ch.charCodeAt(0)), q); return mod(h, q); }
const x = 777n, y = powmod(g, x, p);
const r = 421n; // nonce hardcoded only so the demo is deterministic
// WEAK Fiat-Shamir: the challenge hashes only the commitment a (message omitted)
const signWeak = () => { const a = powmod(g, r, p); const e = H(a.toString()); return { a, z: mod(r + e * x, q) }; };
const verifyWeak = (msg, s) => { const e = H(s.a.toString()); return powmod(g, s.z, p) === mod(s.a * powmod(y, e, p), p); };
const sigW = signWeak();
console.log('weak valid on original = ' + verifyWeak('alice pays 5', sigW));
console.log('weak valid on FORGED = ' + verifyWeak('alice pays 5000', sigW)); // true -> universal forgery
// STRONG Fiat-Shamir: the challenge binds the public key AND the message AND a
const signStrong = (msg) => { const a = powmod(g, r, p); const e = H(y.toString() + '|' + msg + '|' + a.toString()); return { a, z: mod(r + e * x, q) }; };
const verifyStrong = (msg, s) => { const e = H(y.toString() + '|' + msg + '|' + s.a.toString()); return powmod(g, s.z, p) === mod(s.a * powmod(y, e, p), p); };
const sigS = signStrong('alice pays 5');
console.log('strong valid on original = ' + verifyStrong('alice pays 5', sigS));
console.log('strong valid on FORGED = ' + verifyStrong('alice pays 5000', sigS)); // false -> rejected
`}
### The same bug, forged twice, a decade apart
This is not a hypothetical. It is the single most-repeated real-world break in the toolkit, and it has a body count.
In 2012, Bernhard, Pereira, and Warinschi formalized the weak-versus-strong distinction and showed that the Helios internet-voting system used weak Fiat-Shamir. Its ballot proofs -- the "zero-knowledge" proofs that a vote is well-formed -- could be transplanted and forged [@bpw]. The paper's title is a warning label: *How Not to Prove Yourself*.
Ten years later, in April 2022, Trail of Bits disclosed the same class of bug in three live systems at once: Girault's proof of knowledge, Bulletproofs, and PlonK [@tob-part1], [@tob-girault], [@tob-bp], [@tob-plonk]. The Bulletproofs instance was traced to an insecure Fiat-Shamir generation recommended in the original 2017 paper, and it carried CVE-2022-29566 [@tob-bp], [@cve], [@bulletproofs].Note the attribution carefully: "Girault" is the name of an *affected scheme* (a proof of knowledge in an RSA group), not the researcher. The disclosure was by Jim Miller at Trail of Bits [@tob-part1], [@tob-girault].
"We've dubbed this class of vulnerabilities Frozen Heart. The word frozen is an acronym for FoRging Of ZEro kNowledge proofs ... a mistake in the original academic paper, in which the authors recommend an insecure Fiat-Shamir generation." -- Trail of Bits [@tob-part1]
> **Note:** Helios in 2012 and Frozen Heart in 2022 are the same failure: a challenge hash that omitted the statement. In neither case did anyone break the discrete logarithm. The security lived in one line of the hash, and that line was wrong -- in a shipped e-voting system and in a peer-reviewed range-proof paper -- ten years apart [@bpw], [@tob-part1].
Bind the whole statement and the challenge is safe. But Fiat-Shamir also turns the Schnorr *identification* protocol into the Schnorr *signature* -- and that hands the third move, the response, a fresh way to leak. This one does not even need a mistake in the hash. It needs a mistake in a single random number.
## 6. Move 3: How the Response Behaves
The response $z = r + e\cdot x$ is the only message in the whole conversation that touches the secret, and it protects that secret with exactly one thing: a fresh, secret, one-time nonce $r$. Everything the third move can suffer is a story about that nonce -- a number that is never even transmitted, yet is where the key most often escapes.
Start with the bridge that Fiat-Shamir just built. Apply the transform to Schnorr's identification protocol and you get the Schnorr signature: the commitment $a$ and response $z$ are the signature, and the challenge is $e = H(y \,\|\, m \,\|\, a)$. Read that carefully, because it is one of the article's quiet revelations: **a Schnorr signature is a non-interactive proof of knowledge of the private key.** Signing is proving you know $x$; the message rides along in the challenge hash [@bip340].
### Reuse the nonce, lose the key
Now recall the extractor from Section 2. Two accepting transcripts that share the commitment $a$ but differ in the challenge $e$ yield the witness $x = (z_1 - z_2)/(e_1 - e_2)$. That was the *defender's* proof that Schnorr is a proof of knowledge. Turn it around: if a signer produces two signatures with the same nonce $r$, they produce two transcripts with the same $a = g^r$ and different challenges. The attacker runs the same three lines of algebra the extractor runs, and the private key falls out.
This is the identical failure as a reused ECDSA nonce -- the catastrophe covered in Parts 8 and 17 -- because both signature schemes hide the key behind a per-signature nonce, and both surrender it the moment the nonce repeats.There is a sharp distinction worth carrying. The reused-nonce break in [Part 8](/blog/one-number-used-twice-how-a-repeated-nonce-hands-over-your-p/) happens *within* a single scheme when one nonce is used for two signatures. The ROS break below happens *across* many concurrent sessions of a multi-party scheme, exploiting the linearity of the response rather than a literal repeat. Same move, two different exploits. A biased nonce -- not repeated, just slightly non-uniform -- leaks the key more slowly, through lattice attacks that aggregate many partial leaks. The discipline is absolute: nonces must be fresh, secret, and uniform, whether drawn from a [well-seeded CSPRNG or derived deterministically](/blog/predictable-or-repeated-the-only-two-ways-cryptographic-rand/) as Part 2 describes.
### Why concurrency is the hard part
Pointcheval and Stern's forking lemma proves single-session Schnorr unforgeable in the random-oracle model: rewind a forger, give it a fresh challenge on the same commitment, and its two answers extract the discrete log, which is assumed hard [@pointcheval-stern]. The proof works, but it pays a price -- a quadratic loss in tightness -- and, more importantly, the rewinding trick does not compose when many sessions run at once. You cannot cleanly rewind one of a hundred interleaved conversations without disturbing the rest.
The rewinding technique of Pointcheval and Stern that turns a random-oracle forger into a discrete-log solver by running it twice with different challenges on the same commitment. It gives Schnorr and Fiat-Shamir their ROM security proof, but loosely -- with a quadratic security loss -- and only for the single-session setting [@pointcheval-stern].
That gap between "one session is provably secure" and "many concurrent sessions are secure" stayed hidden for two decades. Then it was pried open.
### The ROS attack
In 2021, Benhamouda, Lepoint, Loss, Orru, and Raykova published a polynomial-time solution to the ROS problem, and with it broke naive two-round Schnorr multisignatures and blind Schnorr signatures [@ros]. The mechanism is pure linear algebra. Open enough concurrent signing sessions -- more than about $\log_2 p$ of them -- collect the responses, and set up a linear system whose solution forges a signature on a message the signers never agreed to. No discrete logarithm is solved anywhere in the attack.
"Random inhomogeneities in an Overdetermined, Solvable system of linear equations." It is solvable in polynomial time once the number of concurrent sessions exceeds roughly $\log_2 p$, which is exactly what breaks naive linear Schnorr multi-signatures and blind signatures. It is emphatically NOT "Random Oracle Substitution," a common web mistranslation [@ros].
The 2021 result had a predecessor. In 2019, Drijvers and co-authors had already shown, at IEEE S&P, that the same naive two-round multisignatures were insecure under concurrency -- their attack ran in sub-exponential time using Wagner's generalized-birthday (k-sum) algorithm [@drijvers], [@wagner]. The 2021 ROS work sharpened sub-exponential into polynomial. Together they closed the case: naive linear Schnorr multisignatures are not merely hard to prove secure under concurrency; they are concretely broken.
flowchart TD
Z["response z holds r plus e times x"] --> B{"how is the nonce misused?"}
B -->|"reuse or bias one nonce"| R1["two transcripts share commitment a"]
R1 --> R2["extractor recovers x from two responses"]
B -->|"open many concurrent sessions"| C1["responses are linear across sessions"]
C1 --> C2["ROS solves the linear system"]
C2 --> C3["forge a signature, no discrete log solved"]
No discrete log is ever solved. The response simply leaks across concurrent sessions, and linear algebra does the rest.
> **Note:** The simple "everyone sends a nonce, everyone sends a response" two-round multisignature is forgeable under concurrent sessions -- sub-exponentially since Drijvers (S&P 2019), and in polynomial time since ROS (2021). Use MuSig2 (n-of-n) or FROST (t-of-n), which are built specifically to defeat this attack [@drijvers], [@ros].
Move 1 can be equivocated, Move 2 can be transplanted, Move 3 can be solved by linear algebra -- and not one of these touched the discrete logarithm. That is the thesis, proven three times. The story from here is how each sub-lineage climbed *out* of its break, while the three moves kept running underneath.
## 7. What Superseded What (and What Never Did)
Here is the classic mistake this article exists to correct: there is no single "what superseded what" ladder for this toolkit. The three moves are a *substrate*. Supersession happens in the *composites* built on top of them, and there are exactly **three construction ladders** -- one per application: range proofs, multi-party Schnorr, and anonymous credentials. Every rung was forced by a break or a cost on a specific move, never by an advance against the discrete logarithm.
The one change to the foundation itself -- weak Fiat-Shamir hardened to strong -- is not a fourth ladder but a fix applied in place, so we take it first.
flowchart TD
subgraph FOUND["Foundations, never superseded, Move 2 hardened weak to strong in place"]
F1["Move 1 Pedersen"]
F2["Move 2 Fiat-Shamir, hardened weak to strong"]
F3["Move 3 Schnorr response"]
end
FOUND --> RP["Range proofs"]
FOUND --> MP["Multi-party Schnorr"]
FOUND --> AC["Anonymous credentials"]
RP --> RP1["Borromean 2015"]
RP1 -->|"superseded by"| RP2["Bulletproofs 2018"]
RP2 -->|"superseded by"| RP3["Bulletproofs plus 2022"]
MP --> MP1["naive two-round"]
MP1 -->|"superseded by"| MP2["three-round"]
MP2 -->|"superseded by"| MP3["MuSig2 and FROST"]
AC --> AC1["Chaum blind signature"]
AC1 -->|"superseded by"| AC2["CL-Idemix and U-Prove"]
AC2 -->|"shipped instead"| AC3["KVAC, BBS, Privacy Pass"]
### Foundation hardening: weak Fiat-Shamir becomes strong
The one part of the foundation that changed was never superseded -- it was hardened in place. Weak Fiat-Shamir was the default misreading of the heuristic; Helios in 2012 and Frozen Heart in 2022 forged proofs under it [@bpw], [@tob-part1], [@cve]. Strong Fiat-Shamir -- bind the whole statement -- is what the random-oracle proof had silently assumed all along. The two generations differ only in what enters one hash, and the discrete logarithm is untouched in both. Move 2 was not replaced by a better construction; it was corrected to the instantiation it always needed.
### Ladder A -- range proofs: cashing in the homomorphism
This ladder cashes in Move 1's homomorphism, and it is the one with dramatic size numbers. The textbook starting point is a bit-decomposition OR-proof: to show a committed value lies in $[0, 2^n)$, prove each of its $n$ bits is either 0 or 1 with an OR-proof. It works and it is $O(n)$ -- linear in the bit width, which is a lot of bytes.
Monero's RingCT initially shipped Borromean ring range proofs (Maxwell and Poelstra, 2015), which packed the bit proofs into ring signatures at roughly 6 kB per output -- the dominant cost of a confidential transaction [@monero]. Then **Bulletproofs** (Bunz, Bootle, Boneh, Poelstra, Wuille, and Maxwell, 2018) reduced the range statement to an inner-product relation and compressed it with a recursive argument that halves the vectors each round, yielding an $O(\log n)$ proof of about 600 to 700 bytes -- with **no trusted setup** [@bulletproofs], [@monero].
Monero's own documentation reports the deployment cut transaction size by at least 80 percent [@monero]. **Bulletproofs+** (2022) shrank the constant further with a weighted inner-product argument [@bulletproofs-plus].
The honest footnote on this ladder is the one Section 5 set up: Bulletproofs also *broke*, via weak Fiat-Shamir, as CVE-2022-29566 [@tob-bp], [@cve]. That was a Move-2 failure inside a Move-1 construction, and it was fixed by strong Fiat-Shamir -- not by Bulletproofs+. The size ladder and the security fix are independent axes on the same object.
### Ladder B -- multi-party Schnorr: climbing out of the ROS break
This ladder is Move 3 recovering from the concurrency break of Section 6. The naive two-round multisignature -- everyone sums nonces, everyone sums responses -- fell to Drijvers (2019) and then ROS (2021) [@drijvers], [@ros]. The first fix was to spend a round: three-round commit-then-reveal schemes make each signer commit to its nonce before revealing it, which restores concurrent security at the cost of an extra round trip [@musig2].
**MuSig2** (Nick, Ruffing, and Seurin, 2021) got back to two rounds by a clever trick: each signer publishes *two* nonces, and the effective nonce is a hash-weighted combination of them, so the combined nonce is a *nonlinear* function of the inputs -- exactly what defeats the linear-algebra ROS forgery [@musig2]. **FROST** (standardized as RFC 9591 in June 2024) then added genuine threshold signing [@rfc9591].
The distinction that matters: MuSig2, standardized as BIP-327, is **n-of-n** -- every signer must participate, and the output is a single 64-byte signature indistinguishable from a single-key one [@bip327], [@musig2]. FROST is the **t-of-n threshold** scheme, where any $t$ of $n$ signers suffice [@rfc9591]. They are different tools for different policies, not two names for the same thing.
### Ladder C -- anonymous credentials: the elegant generation that lost
This ladder is the strange one, because the most elegant generation is the one that did *not* win. It begins with Chaum's blind signatures -- blind, let the issuer sign, unblind -- introduced in 1982 [@chaum-blind] and set out as a whole transaction system in his 1985 paper, the root of unlinkable credentials, though single-show [@chaum-cacm]. It climbs to the multi-attribute systems: Camenisch-Lysyanskaya (Idemix) and Brands (U-Prove), which let a holder prove statements about many attributes and were genuinely beautiful cryptography [@cl-2001], [@cl-2004], [@uprove]. And then, mostly, it did not ship.
The winners are three deployed corners, not one. **Signal KVAC** (2020) is a keyed-verification credential where the issuer is also the verifier, built on an algebraic MAC and a Sigma-protocol presentation proof, deployed in Signal's private groups [@signal], [@kvac]. **BBS** signatures are the publicly-verifiable corner, a multi-message credential now in IETF drafts [@bbs-draft].
And **Privacy Pass / Apple Private Access Tokens**, standardized at the IETF in June 2024, are the unlinkable single-use authorization-token corner -- the deployed realization of Chaum's blind-token idea, in which a client redeems an anonymously issued token at an origin that cannot link it back to issuance [@rfc9576], [@cloudflare-pat]. All three are Sigma proofs over the same three moves, filled in for three different trust models; Section 8 attaches the parameters to each.
> **Key idea:** Every real-world break lives on one of the three moves. The discrete logarithm was never broken. The commitment equivocates, the challenge transplants, the response leaks -- and the composites climb their ladders while Pedersen, Fiat-Shamir, and Schnorr keep running underneath, never superseded.
Here is the whole picture as one matrix.
| Approach | Year | Lineage / move | Key idea | Size or cost | Status |
|---|---|---|---|---|---|
| Weak Fiat-Shamir | 1986 | Move 2 | hash only the commitment | -- | Superseded (insecure) |
| Strong Fiat-Shamir | 2012 | Move 2 | bind the whole statement | -- | Active |
| Bit-decomposition range proof | classic | Move 1 | OR-prove each bit | O(n) | Historical |
| Borromean range proof | 2015 | Move 1 | ring signatures over bits | ~6 kB/output | Superseded |
| Bulletproofs | 2018 | Move 1 | recursive inner-product | ~600-700 B, O(log n) | Active |
| Bulletproofs+ | 2022 | Move 1 | weighted inner-product | shorter constant | Active |
| Naive two-round multisig | 2010s | Move 3 | sum nonces and responses | 2 rounds, broken | Superseded |
| Three-round multisig | 2006 | Move 3 | commit-then-reveal nonces | 3 rounds | Superseded |
| MuSig2 (BIP-327) | 2021 | Move 3 | two nonces, nonlinear combine | 2 rounds, n-of-n | Active |
| FROST (RFC 9591) | 2024 | Move 3 | threshold nonce commitments | 2 rounds, t-of-n | Active |
| Chaum blind signature | 1982 | Credentials | blind, sign, unblind | single-show | Historical |
| CL-Idemix / U-Prove | 2001 | Credentials | multi-attribute proofs | multi-show (Idemix); single-show (U-Prove) | Niche (undeployed) |
| Signal KVAC | 2020 | Credentials | algebraic MAC, issuer verifies | deployed | Active |
| BBS | 2023 | Credentials | pairing, multi-message | ~80 B signature | Standardizing |
| Privacy Pass / Apple PAT | 2024 | Credentials | unlinkable single-use token | RFC 9576/9577/9578 | Deployed |
Three ladders, three break-driven climbs, over a foundation that was itself hardened in place -- three ascents on one unchanging three-move base. Which rung is at the top of each ladder today -- and with which exact parameters -- is the difference between a design review that passes and one that ships a CVE.
## 8. State of the Art (2024-2026): What Actually Ships
The frontier is not one best algorithm. It is a layered stack: three foundational moves that were never superseded, and above them a handful of composites that ship at scale, each with a standard and a parameter set. If you have to build with this in 2026, here is the state of the art with the numbers attached.
**The moves, still the state of the art as primitives.** A Pedersen commitment is a single 32-byte point on ristretto255. Strong Fiat-Shamir is the correct instantiation now baked into every standard below. And Schnorr-proper, standardized as **BIP-340**, is a 64-byte signature [@bip340]; Bitcoin's Taproot upgrade activated it at block 709,632 in November 2021 [@bip341], [@taproot-wiki], and native Schnorr has been available for every spend since. These are not legacy pieces waiting to be replaced; they are the load-bearing base of everything else.
**MuSig2 / BIP-327** is the deployed answer for n-of-n multisignatures: a two-round protocol producing a single 64-byte Schnorr signature that is indistinguishable on-chain from a single-key spend, implemented in `libsecp256k1` and `secp256k1-zkp` [@bip327], [@musig2]. Every co-signer participates, and the verifier does one ordinary Schnorr check.
**FROST / RFC 9591** (June 2024) is the most consequential *new* standard in the window: a two-round t-of-n threshold Schnorr signature, specified across five ciphersuites -- Ed25519, ristretto255, Ed448, P-256, and secp256k1 [@rfc9591]. On its own, FROST assumes signers do not vanish mid-protocol; **ROAST** (CCS 2022) wraps it to keep signing alive even when some signers are faulty or offline, giving fault tolerance for asynchronous deployments [@roast].
| Scheme | Nonce structure | Rounds | Concurrent-secure | Fault-tolerant | Signature | Status |
|---|---|---|---|---|---|---|
| Naive two-round | sum the nonces | 2 | No (Drijvers, ROS) | No | 64 B | Broken |
| Three-round | commit then reveal | 3 | Yes | No | 64 B | Superseded |
| MuSig2 (BIP-327) | two nonces, nonlinear | 2 | Yes | No | 64 B (n-of-n) | Deployed |
| FROST (RFC 9591) | threshold commitments | 2 | Yes | No | 64 B (t-of-n) | Standardized |
| FROST + ROAST | ROAST wrapper | 2+ | Yes | Yes | 64 B (t-of-n) | Active |
A zero-knowledge proof that a committed value lies in a fixed interval such as $[0, 2^n)$ without revealing the value. Bulletproofs are the deployed transparent construction, proving a Pedersen-committed amount is in range in about 600 to 700 bytes [@bulletproofs].
**Bulletproofs and Bulletproofs+** are the state of the art for *transparent* range proofs -- logarithmic size, no trusted setup -- and they secure confidential amounts in Monero, where Bulletproofs deployed in October 2018 and Bulletproofs+ followed in 2022 [@bulletproofs], [@bulletproofs-plus], [@monero]. They are the default whenever you need a range proof without a setup ceremony and can accept linear verification time. This is the immediate cash-in of Move 1's homomorphism at production scale.
On the credential side, three systems ship, and they occupy different economic corners.
An anonymous credential in which the issuer and the verifier are the same party, so the credential can be built on a fast algebraic MAC instead of a public-key signature. The holder presents it with a Sigma-protocol proof of knowledge, revealing only the attributes it chooses [@kvac], [@signal].
**Signal KVAC** is the keyed-verification credential in production in Signal's private group system: the issuer is also the verifier, so it runs on an algebraic MAC with no pairings, and presentation is a Sigma-protocol proof of knowledge [@kvac], [@signal]. It is the standing counter-example to "elegant but undeployed."
**BBS and Blind BBS**BBS takes its name from the 2004 Boneh-Boyen-Shacham short group signature scheme it descends from, by way of the later BBS+ variant [@bbs-origin]. are the publicly-verifiable answer: multi-message, selective-disclosure credentials over the BLS12-381 pairing curve, with roughly 80-byte signatures, now in `draft-irtf-cfrg-bbs-signatures-10` (8 January 2026) and Blind BBS `draft-03` [@bbs-draft], [@blind-bbs]. BBS is the standardizing choice for W3C Verifiable Credentials and identity wallets, where a third party must verify what an issuer signed. KVAC and BBS are parallel answers -- private-issuer economy versus public verifier -- not one replacing the other.
**Privacy Pass**, deployed at population scale as **Apple Private Access Tokens**, is the third corner: a different shape from the other two -- an unlinkable single-use authorization token rather than a multi-attribute credential. A client anonymously obtains a token backed by some attestation and later redeems it at an origin that cannot link the redemption to issuance.
It was standardized at the IETF in June 2024 across three documents -- **RFC 9576** for the architecture, **RFC 9578** for issuance, and **RFC 9577** for the `PrivateToken` HTTP authentication scheme [@rfc9576], [@rfc9578], [@rfc9577]. Apple shipped it in iOS 16 and macOS Ventura in 2022 with hardware-backed device attestation, and Cloudflare uses it to drop the CAPTCHA for attested devices [@cloudflare-pat].Direct Anonymous Attestation (2004), the deployed exception detailed in Section 7, ships in two hardware generations -- TPM 1.2 RSA-DAA and TPM 2.0 ECDAA -- and adds per-verifier basename linkability, so a device proves it is genuine without becoming trackable [@daa], [@tpm2-spec].
Underneath, it is still commit, challenge, respond over the discrete log. Keep it distinct from KVAC and BBS: it is single-*show* authorization, not multi-attribute selective disclosure, and its privately-verifiable issuance is a verifiable oblivious PRF whose Chaum-Pedersen mechanism Part 20 owns and this section only signposts.
| System | Verifiability | Cryptographic base | Size | Deployment |
|---|---|---|---|---|
| U-Prove / Idemix | Public | Discrete log, RSA, pairings | multi-kB | Standardized, largely undeployed |
| Signal KVAC | Keyed (issuer verifies) | Algebraic MAC, no pairings | Compact | Deployed in Signal |
| BBS / Blind BBS | Public | Pairings on BLS12-381 | ~80 B signature | Standardizing (IETF) |
| Privacy Pass / Apple PAT | Public or keyed, per token type | VOPRF or blind RSA issuance | Small single-use token | Deployed (iOS 16, macOS Ventura) |
This is the same primitive Part 20 built on: an [oblivious PRF's verifiability](/blog/the-server-helped-and-never-saw-a-field-guide-to-oblivious-p/) rests on a Chaum-Pedersen Sigma proof -- and Privacy Pass's privately-verifiable issuance is exactly that VOPRF. The deployed [anonymous-credential systems](/blog/the-age-gate-that-doesnt-know-your-age-how-anonymous-credent/) are Sigma proofs of knowledge of a signature, and [Direct Anonymous Attestation](/blog/direct-anonymous-attestation-the-zero-knowledge-proof-alread/) is the Sigma-protocol credential already shipping in TPM silicon. Every composite in this section is the three moves with the parameters filled in.
Every one of these is a defensible point on a Pareto frontier, not a single winner -- which is exactly why the toolkit is a toolkit. To choose between them, and between the whole family and a general-purpose proof system, you need the line where Sigma plus Fiat-Shamir stops being the right tool.
## 9. Competing Approaches and Where the Line Is
The toolkit's real competition is the general-purpose proof system -- the SNARK or STARK that can prove *any* circuit. Knowing when *not* to reach for one is half of using this toolkit well.
A bespoke Sigma proof plus strong Fiat-Shamir is transparent (it needs only the random-oracle assumption, no setup ceremony), tiny for narrow statements (a constant number of group elements, growing only with the number of clauses), and cheap to prove. A pairing-based SNARK gives a constant-size proof and near-constant verification, but at the price of a trusted setup: Groth16 lands near 200 bytes and PLONK near 400 [@groth16], [@plonk].
A STARK is transparent and plausibly post-quantum, but its proofs run to tens or hundreds of kilobytes. The Bulletproofs authors made the transparency contrast explicit: their range proofs need no trusted setup, unlike the succinct pairing SNARKs [@bulletproofs].
The decision rule falls out of the shape of your statement:
- A **fixed algebraic relation** -- "I know a discrete log," "this Pedersen value is in range," "one of these $n$ public keys signed" -- wants a hand-verified Sigma proof with strong Fiat-Shamir. It is smaller, faster, and setup-free.
- An **arbitrary circuit** -- "this value is the output of running this program" -- is where you reach for a SNARK or STARK, accepting the setup or the proof size in exchange for expressiveness you cannot get from a fixed relation.
| Approach | Proof size (64-bit range) | Trusted setup | Prover | Verify | Post-quantum | Aggregation |
|---|---|---|---|---|---|---|
| Bit-decomposition OR | O(n), large | No | O(n) | O(n) | No | Weak |
| Borromean | ~6 kB/output | No | O(n) | O(n) | No | No |
| Bulletproofs | ~0.6-0.7 kB, O(log n) | No | O(n) | O(n), batchable | No | Yes |
| Bulletproofs+ | smaller constant, O(log n) | No | O(n) | O(n), batchable | No | Yes |
| SNARK (Groth16/PLONK) | ~0.2 kB (Groth16) to ~0.4 kB (PLONK), O(1) | Yes | O(circuit) | ~O(1) | No | Circuit-dependent |
| STARK | tens to hundreds of kB | No | O(n log n) | polylog | Plausibly | Limited |
Two more axes decide the corner. **Commitment choice** is the Section 4 recap: need to add committed values, pick Pedersen; need post-quantum binding or no algebra, pick a hash commitment. And **interactivity** is a genuine fork: an interactive Sigma protocol is *deniable* -- because anyone could have simulated the transcript, it proves nothing to a third party -- and needs no random-oracle assumption, while Fiat-Shamir buys you a signature or an on-chain proof at the cost of making the proof transferable to everyone forever. Deniability versus non-interactivity is a real tension we return to in the open problems.
The line is drawn by the shape of your statement and the trust you can assume. But even the right tool, used perfectly, runs into limits that no parameter choice can buy its way out of.
## 10. Theoretical Limits
The discrete log has held for forty years. But "the hard problem is hard" is not the same claim as "your proof is secure," and the gap between them is where this section lives. Every limit below survives even if the discrete logarithm stays hard forever.
Start with the good news, because it is genuinely good. For the *interactive* protocol, special soundness gives a tight, unconditional extractor -- two transcripts and three lines of algebra recover the witness, no assumptions -- and SHVZK gives a *perfect* simulator [@damgard]. Interactive Schnorr is about as close to an ideal proof of knowledge as anything in cryptography gets. The trouble starts when you make it non-interactive, or run many copies at once.
### Soundness is only ROM-deep
Fiat-Shamir soundness is provable, but only in the random-oracle model, via the forking lemma [@pointcheval-stern]. In the standard model it is *uninstantiable*: Goldwasser and Kalai (FOCS 2003) exhibited schemes whose Fiat-Shamir transform is insecure for *every* concrete hash function you could plug in [@gk-focs]. That was a theoretical construction for two decades. Then in 2025, Khovratovich, Rothblum, and Soukhanov turned it practical, making a GKR-based commercial proof system accept false statements regardless of the hash instantiating the transform [@khovratovich], [@quanta].
> **Note:** The Khovratovich-Rothblum-Soukhanov result targets Fiat-Shamir applied to GKR-style succinct arguments, not the short algebraic Sigma statements that strong Fiat-Shamir fully binds [@khovratovich]. It does not forge a Schnorr signature. What it does is harden the general lesson: Fiat-Shamir soundness is a property of the random-oracle idealization, and the more your proof leans on the hash doing something a real hash may not do, the thinner the ice [@gk-focs].
### Forking is loose, and looseness is the seam
The random-oracle reduction is not tight. Rewinding a forger to extract the discrete log loses roughly a quadratic factor in the security bound [@pointcheval-stern]. This is not sloppy proof engineering; it is inherent to the rewinding technique.The quadratic looseness and the concurrency failure are the same fact seen twice. Rewinding extracts from *one* session by replaying it with a fresh challenge; it does not compose when many sessions interleave, because you cannot rewind one without disturbing the others. That is precisely the seam the ROS attack pries open [@pointcheval-stern], [@ros]. One line of work sidesteps rewinding entirely: the Fischlin transform (2005) uses an *online*, straight-line extractor that reads the witness out of a single transcript by inspecting the prover's oracle queries, so its extraction composes concurrently and carries more cleanly into the quantum random-oracle model -- at the price of larger proofs, which is why it coexists with Fiat-Shamir rather than replacing it [@fischlin]. And because rewinding does not compose across concurrent sessions, the single-session forking proof simply does not extend to the multi-party concurrent setting.
That gap has a sharp quantitative edge. Naive linear Schnorr multisignatures and blind signatures are secure only while the number of concurrent open sessions stays below roughly $\log_2 p$; above that threshold, the ROS forgery runs in polynomial time with no discrete log solved [@ros]. MuSig2's two-nonce nonlinear combination is the construction that evades the bound -- not a discrete-log advance, just a change that makes the response nonlinear so the linear system has no solution [@musig2].
### Two settled negatives
Some limits are not open questions; they are proven impossibilities you must design around.
1. **No commitment is both perfectly hiding and perfectly binding.** The Move-1 trade-off of Section 4 is fundamental, not an artifact of Pedersen [@damgard]. You choose a corner; you do not get both.
2. **None of this is post-quantum.** Every guarantee in the article rests on the hardness of the discrete logarithm or of pairing problems, and Shor's algorithm breaks all of them on a sufficiently large quantum computer. No parameter choice rescues it -- a bigger group buys nothing against Shor. The hard problem that held against classical attackers for forty years is exactly the one a quantum computer dissolves.
The discrete log is hard, and this multisignature is secure under concurrency, are simply different claims -- and the second one was false until MuSig2 made the combined nonce nonlinear.
Those are the settled negatives. The open frontiers -- where the field is still moving -- are next, and the sharpest is the quantum cliff the whole toolkit stands at the edge of.
## 11. Open Problems
The toolkit is deployed and load-bearing, and it still has open edges sharp enough to end careers on. Here is what is genuinely unsolved, and which of it should keep a protocol designer awake.
**Standard-model Fiat-Shamir.** A universal, hash-instantiable, tight Fiat-Shamir is believed impossible in general. The 2003 uninstantiability result and the 2025 practical break together bound the ambition: the realistic goal is not a universal fix but per-protocol *correlation intractability* -- proving a specific hash is good enough for a specific proof system [@gk-focs], [@khovratovich]. Straight-line alternatives such as the Fischlin transform trade larger proofs for cleaner, rewinding-free extraction, but they are not a universal drop-in replacement [@fischlin]. For the short algebraic statements in this article, strong Fiat-Shamir remains the right practice; for succinct arguments, the question is live.
**Post-quantum Sigma protocols.** This is the sharpest frontier, because it is where the whole toolkit meets its deadline. Discrete-log zero knowledge dies to Shor -- but the three-move *template* does not. It reappears over other hardness assumptions.The Sigma template outlives its discrete-log instantiation. Fiat-Shamir-with-aborts over lattices is the shape behind Dilithium-style signatures, and MPC-in-the-head -- instantiated as Picnic -- builds a zero-knowledge signature from a hash and a secret-sharing protocol, needing no structured hardness assumption at all [@picnic]. Commit, challenge, respond survives the move to a post-quantum world; only the algebra underneath changes. What does *not* yet transfer cleanly is the efficient, verifiable, partially-oblivious machinery: post-quantum range proofs and post-quantum multi-show credentials exist but are large and immature compared to Bulletproofs and BBS. The [thirty-year migration to post-quantum cryptography](/blog/the-thirty-year-migration-ships-in-a-pip-install-how-post-qu/) is the sibling part that tracks this deadline in full.
**Round-optimal blind Schnorr after ROS.** Plain two-round blind Schnorr is inherently ROS-vulnerable [@ros]. Getting a secure blind signature in few rounds needs extra structure: clause or boosting variants that break the linearity, a proof in the algebraic group model (Fuchsbauer, Plouviez, and Seurin), or a different scheme entirely [@fps]. There is no known plain, standard-model, round-optimal blind Schnorr that survives concurrency.
**Threshold Schnorr, hardened.** RFC 9591 standardized two-round threshold Schnorr for custody in June 2024, and FROST is now entering production custody [@rfc9591], but stronger guarantees remain research targets: adaptive security (against an attacker who corrupts signers mid-protocol), proofs that do not lean on the algebraic group model, and distributed key generation that scales asynchronously to large signer sets.
**Anonymous-credential revocation at population scale** without breaking unlinkability is still mostly finessed rather than solved -- deployed systems lean on short-lived credentials that simply expire, because a true privacy-preserving revocation list that scales to millions of holders is hard to make both efficient and unlinkable.
**Deniability versus non-interactivity.** A Fiat-Shamir'd proof is transferable -- anyone who receives it is convinced, forever. An interactive Sigma proof is deniable -- because it could have been simulated, it convinces only the live verifier. Getting both properties at once is a per-application tension, not a solved problem.
None of these block you from shipping today; they tell you what to watch. What you ship comes down to a small, unglamorous set of rules that separate a correct deployment from a forged one.
## 12. Use X With These Parameters In Case Y
Here are the rules a reviewer can apply without re-deriving anything, organized -- of course -- by the three moves, in the order you make them.
### Move 1: pick the commitment by the job
Need to add or range-prove committed values -- confidential amounts, homomorphic tallies? Use a **Pedersen commitment on ristretto255**, and derive the second generator $h$ by hashing a fixed string to a curve point so that nobody holds the trapdoor $\log_g h$. A known trapdoor is silent equivocation; the generator setup is security-critical, not boilerplate. Need post-quantum binding, or you are committing to something with no algebra -- a Merkle leaf, a coin flip? Use a **hash commitment** `H(m ‖ r)`.
### Move 2: get the challenge right, every time
Use **strong Fiat-Shamir**: hash the full statement, all public parameters, the prior transcript, and a domain separator. The operational habit that prevents the entire Frozen Heart class is one sentence: for every proof, write down "what is this proof *about*?" and confirm each item on that list is inside the hash. The statement is about a public key? The public key goes in the hash. It is about a specific message or ciphertext? That goes in too. Weak Fiat-Shamir is what happens when that list is incomplete [@tob-part1].
### Move 3: nonce discipline
Nonces must be fresh, secret, and uniform per session. Draw them from a well-seeded CSPRNG, or derive them deterministically with the tagged-hash discipline BIP-340 specifies so a broken RNG cannot repeat or bias them [@bip340]. In MuSig2 and FROST, honor the two-nonce and preprocessing rules exactly, and never reuse a nonce commitment across sessions -- the multi-party schemes defeat ROS only if the nonce rules are followed [@musig2], [@rfc9591].
> **Note:** Move 1 -- is your second generator $h$ from a nothing-up-my-sleeve hash, with no known trapdoor? Move 2 -- write down what the proof is about, and verify every item is inside the challenge hash, behind a domain separator. Move 3 -- is every nonce fresh, secret, and uniform, and are the MuSig2 or FROST nonce rules followed to the letter? Three questions, in order. Most Frozen-Heart and nonce-reuse incidents fail one of them.
### Then pick the composite
flowchart TD
START{"What are you building?"}
START -->|"commit to a value"| COMMIT{"need to add or range-prove it?"}
COMMIT -->|"yes"| C1["Pedersen on ristretto255"]
COMMIT -->|"no, need PQ binding"| C2["Hash commitment"]
START -->|"prove a range"| C3["Bulletproofs plus, aggregated, strong FS"]
START -->|"multi-party signature"| SIG{"all signers or t of n?"}
SIG -->|"all n"| C4["MuSig2 BIP-327"]
SIG -->|"t of n"| C5["FROST RFC 9591 plus ROAST"]
START -->|"anonymous credential"| CRED{"who verifies?"}
CRED -->|"the issuer itself"| C6["Signal KVAC"]
CRED -->|"any third party"| C7["BBS"]
START -->|"arbitrary circuit"| C8["SNARK or STARK"]
The composite rules, stated plainly:
- **Range proof, small and transparent:** Bulletproofs+, aggregated, with strong Fiat-Shamir binding [@bulletproofs-plus].
- **All parties co-sign one key (n-of-n):** MuSig2, standardized as BIP-327 [@bip327].
- **Any t of n signers suffice:** FROST, RFC 9591, run with a distributed key generation -- and add ROAST if a faulty signer must not be able to stall the protocol [@rfc9591], [@roast].
- **Authenticate your own users anonymously (you issue and verify):** Signal KVAC [@kvac], [@signal].
- **A third party must verify selective disclosure:** BBS [@bbs-draft].
- **A fixed algebraic relation, tiny and setup-free:** a hand-rolled Sigma proof with strong Fiat-Shamir, using a vetted library -- never your own group arithmetic.
- **An arbitrary circuit:** a SNARK or STARK, accepting the setup or proof-size cost.
- **Anything that must stay secure through the quantum transition:** do not rely on these guarantees; plan a post-quantum migration.
For the implementations, use the libraries that encode these defaults: `bitcoin-core/secp256k1` and `secp256k1-zkp` for BIP-340 and MuSig2 [@bip340], [@bip327]; FROST implementations validated against the RFC 9591 test vectors [@rfc9591]; `dalek-cryptography` for Bulletproofs; Signal's `libsignal` and zkgroup for KVAC [@signal]; BBS libraries tracking the CFRG drafts [@bbs-draft]; and Damgard's notes together with Trail of Bits' ZKDocs when you need the correct Fiat-Shamir recipe written out [@damgard], [@tob-part1].
Most of the ways this goes wrong are the same handful of mistakes phrased for different audiences -- and they are worth naming head-on, because reviewers find them in real code every week.
## 13. Common Misuse, and the Questions Engineers Ask
The antipattern catalog is short because the failures are few and repeat. Reviewers find these in real code, and every one maps to a move.
| Misuse | Move | Root cause | Fix |
|---|---|---|---|
| Weak Fiat-Shamir in real code | Move 2 | statement omitted from the challenge hash | bind the full statement and parameters (strong FS) |
| Reused or biased nonce | Move 3 | two transcripts share a commitment; extractor recovers the key | fresh, uniform, per-session nonces; hedged derivation |
| Assuming Pedersen is perfectly binding | Move 1 | it is only computationally binding | design for computational binding; protect the trapdoor |
| Equivocation via a known `log_g h` | Move 1 | someone knows the trapdoor | derive `h` by nothing-up-my-sleeve hash-to-curve |
| Rolling your own OR-proof or CDS composition | all three | simulator and challenge-splitting are subtle | use a vetted implementation |
| Naive linear multisig under concurrency | Move 3 | linear responses solved by ROS | MuSig2 (n-of-n) or FROST (t-of-n) |
| Treating credentials as "just signatures" | Move 1-3 | they are Sigma proofs with selective disclosure | model unlinkability and presentation proofs |
| "ROS means Random Oracle Substitution" | Move 3 | mistranslated acronym | it is an overdetermined, solvable linear system |
| Conflating BIP-340 with EdDSA | Move 3 | different encoding, nonce, and curve | pin the exact standard you mean |
No. A Pedersen commitment is perfectly *hiding* and only *computationally* binding. A party who knows the trapdoor $\log_g h$ can open a single commitment to any message they like, by solving one linear equation for a matching blinder [@pedersen], [@damgard]. This is why the second generator must be produced so that nobody knows that trapdoor, and why "Pedersen is perfectly binding" is a dangerous thing to write in a spec.
The full statement, all public parameters, the prior transcript, and a domain separator -- not just the commitment [@bpw]. Omitting the statement is weak Fiat-Shamir, the bug behind both the Helios voting break in 2012 and the Frozen Heart disclosures in 2022 [@bpw], [@tob-part1]. The habit that prevents it: write down what the proof is about, and confirm each item is inside the hash.
Yes, and seeing that is worth the price of admission. A Schnorr signature is Fiat-Shamir applied to the Schnorr identification protocol, with the verifier's challenge replaced by a hash of the public key, message, and commitment [@fiat-shamir], [@bip340]. A signature *is* a non-interactive proof of knowledge of the private key; the message just rides along in the challenge.
Don't. The CDS construction for AND/OR composition relies on splitting the challenge and simulating the branches you cannot answer, and getting the challenge algebra or the simulator subtly wrong breaks soundness or zero knowledge [@cds]. Use a vetted implementation; this is exactly the code that looks simple and is not.
No. It is forgeable under concurrent sessions -- sub-exponentially since Drijvers at S&P 2019, and in polynomial time since the ROS result in 2021 [@drijvers], [@ros]. Use MuSig2 for n-of-n signing or FROST for t-of-n threshold signing; both are engineered specifically to defeat that attack [@musig2], [@rfc9591].
No. They are Sigma-protocol proofs of knowledge of a signature or an algebraic MAC, and they support selective disclosure and unlinkability -- a plain signature has neither [@bbs-draft], [@signal]. Treating a credential presentation as an ordinary signature verification misses the entire privacy machinery that is the point of the primitive. Privacy Pass and Apple's Private Access Tokens are the single-*show* authorization-token cousin -- unlinkable, but a one-time "you are allowed" token rather than a multi-attribute selective-disclosure credential [@rfc9576].
No, and the mistranslation is everywhere online. ROS is "Random inhomogeneities in an Overdetermined, Solvable system of linear equations" -- a linear-algebra object, not an oracle trick [@ros]. The attack forges by solving a system of equations over responses collected across concurrent sessions, with no discrete logarithm ever solved.
### The discrete log held; the three moves leaked
Follow the whole failure catalog back and it lands in one place. In April 2022, three unrelated proof systems were forgeable at once, and the discrete logarithm was untouched in all three [@tob-part1]. A decade earlier, the same weak-Fiat-Shamir bug had forged ballot proofs in Helios [@bpw]. A reused nonce hands over a private key by the same algebra that proves Schnorr sound [@bip340]. The ROS attack forges naive multisignatures in polynomial time by solving a linear system, no hard problem broken [@ros]. A Pedersen commitment equivocates the instant someone knows a trapdoor [@pedersen].
Four decades, and the discrete logarithm never fell. Every named break -- Frozen Heart, Helios, nonce reuse, ROS, Drijvers, equivocation -- landed on one of the three moves built on top of it.
And the composites climbed while the foundations stayed put. Borromean gave way to Bulletproofs and Bulletproofs+ [@bulletproofs], [@bulletproofs-plus]; naive multisignatures gave way to MuSig2 and FROST [@musig2], [@rfc9591]; Chaum's blind signatures gave way, in deployment, to Signal KVAC, BBS, and Privacy Pass [@signal], [@bbs-draft], [@rfc9576]. Not one of those ladders replaced Pedersen, Schnorr, or Fiat-Shamir. The three moves keep running underneath every rung, exactly as they were written between 1985 and 1996 -- and where the foundation moved at all, it was Move 2 being hardened in place, weak Fiat-Shamir corrected to strong, never a piece torn out and replaced.
This is the frame the series keeps returning to from a new angle each time. Part 18 argued that [nobody broke the discrete log](/blog/nobody-broke-the-discrete-log-a-field-guide-to-diffie-hellma/); Part 17 that the math held and the interface leaked. Here, the math held and the *conversation* leaked -- because a discrete-log zero-knowledge proof was never one thing. It was always three moves, and each one is a separate promise that can be broken without touching the problem underneath.
The discrete log held. The three moves leaked.