The Fiat–Shamir Transformation: How to Remove Interaction from Proofs
--
A practical guide to turning interactive protocols into non-interactive ones — and the subtle ways it can go wrong.
Imagine you want to prove something to someone — say, that you know the solution to a puzzle — without revealing the solution itself. Interactive proof systems let you do exactly this: the prover and verifier go back and forth, exchanging messages, until the verifier is convinced.
But interaction is expensive. It requires both parties to be online at the same time, adds latency, and makes it hard to share proofs publicly. What if you could compress that entire conversation into a single message anyone can verify?
That’s what the Fiat–Shamir transformation does. It sits at the heart of SNARKs, STARKs, and virtually every zero-knowledge proof system deployed today.
In this post, we’ll walk through the transformation itself, explain hash chaining, and then solve Exercises 5.1 and 5.2 from Justin Thaler’s Proofs, Arguments, and Zero-Knowledge — the go-to textbook for interactive proofs and argument systems. These exercises expose two distinct ways the transformation can silently break. If you’ve been following along with my earlier posts on the Sum-Check Protocol and the GKR Protocol, this is the natural next step — Fiat–Shamir is how those interactive protocols become non-interactive.
Starting Point: Public-Coin Protocols
The Fiat–Shamir transformation applies to a specific class of interactive protocols called public-coin protocols. In these, the verifier doesn’t do anything clever — it simply sends random challenges. The prover sends messages, the verifier flips coins, and this goes back and forth.
The key property: since the verifier’s messages are just uniform randomness, the prover could in principle generate them itself — if there were a way to ensure it does so honestly.
Why Naive Approaches Fail
Two tempting shortcuts immediately break soundness.
Naive attempt 1 — let the prover choose the challenges itself. Obviously unsound. A cheating prover can simply pick whatever challenges make its fraudulent proof pass. Nothing enforces honesty.
Naive attempt 2 — derive challenges from a fixed function of the round index:
rᵢ = H(i) , for i ∈ {1, 2, …, n}
This is also broken. Because H is deterministic and publicly known, the entire sequence (r₁, r₂, …, rₙ) is a vector of fixed constants, fully determined before the protocol even begins. The prover can precompute every rᵢ and then craft its messages g₁, g₂, … to cheat against those known challenges. The challenges carry zero entropy from the prover’s perspective — there is no unpredictability left.
Both approaches fail for the same fundamental reason: the prover sees the challenge before committing to its message. The whole point of interaction is that challenges arrive after commitment. The Fiat–Shamir transformation must preserve this ordering.
The Core Idea
Replace every random challenge with the output of a hash function applied to the full transcript so far.
Concretely, instead of the verifier sampling a random rᵢ, the prover computes:
rᵢ = H(x, g₁, g₂, …, gᵢ)
where x is the public statement being proved and g₁, …, gᵢ are all the prover’s messages up to round i.
The prover now runs the entire protocol by itself, producing a single transcript that anyone can verify by recomputing the hashes and checking that the original interactive verifier would have accepted.
Key insight: The hash input must depend on the prover’s previous messages. This is what simulates the temporal ordering of the interactive protocol — the prover can’t see the next challenge before committing to its current message.
Hash Chaining
In the description above, each challenge hashes the entire transcript prefix: H(x, g₁, …, gᵢ). This works, but in practice the hash input grows linearly with the round number, which gets unwieldy for protocols with many rounds.
The standard optimization is hash chaining: instead of hashing the full prefix, each challenge hashes only the previous challenge, the current round index, and the latest prover message:
rᵢ = H(rᵢ₋₁, i, gᵢ)
where r₀ = H(x) bootstraps the chain from the public statement.
This keeps every hash input constant-sized while preserving the same security property — each rᵢ still depends on the full history, just indirectly through the chain. If any earlier message gⱼ changes, every subsequent rₖ for k ≥ j changes too. It’s the same idea, just implemented more efficiently.
Why Does This Work?
The security argument relies on the random oracle model — we pretend the hash function behaves like a truly random function. Under this idealization, querying the hash on a new input is like flipping a fresh coin. The prover can’t predict the output without actually computing it, and computing it requires committing to a message first.
The formal proof is a reduction: if someone could cheat the Fiat–Shamir protocol, you could use them to cheat the original interactive protocol too. When the cheating prover queries the hash at the critical point, the reduction intercepts the query, forwards the prover’s message to a real interactive verifier, and plugs the verifier’s genuine random challenge back in as the “hash output.” The cheating prover can’t tell the difference.
So the Fiat–Shamir transformation is sound in the random oracle model — but only when applied carefully. The next two sections walk through Exercises 5.1 and 5.2 from Thaler’s Proofs, Arguments, and Zero-Knowledge, which expose two distinct ways the transformation can silently break. The first shows that even negligible soundness error doesn’t guarantee safety after Fiat–Shamir. The second shows that omitting a single field from the hash input can make the entire system unsound.
Pitfall #1: Nonce Grinding Breaks Repeated Protocols
This is Exercise 5.1 from Thaler’s book.
Here’s a subtle failure mode that catches people off guard.
Take an interactive proof with soundness error 1/3. Standard amplification says: repeat it n times in sequence, and the error drops to 3⁻ⁿ — negligible for large n. In the interactive setting, this works perfectly because the prover must commit to each message before seeing the next challenge.
Now apply Fiat–Shamir to this repeated protocol, and suppose the prover is allowed to pad its messages with ignored nonces — a seemingly harmless allowance. Everything falls apart.
The Attack
For each repetition, the prover’s message determines the challenge via the hash. But by appending different nonce values ρ, the prover generates different hash inputs — and therefore different challenges — for semantically the same message:
β = H(x, a ‖ ρ)
where a is the “real” message and ρ is an arbitrary nonce the verifier ignores. Each new ρ yields a fresh, independent challenge.
With soundness error 1/3, at most a 1/3 fraction of challenges let the prover cheat. But each nonce is a new roll of the dice. After T independent tries, the probability of finding at least one favorable challenge is:
1 − (2/3)ᵀ
which climbs rapidly toward 1. A few dozen nonces are enough.
Here’s the problem. The prover repeats this grinding process independently for each of the n copies. Instead of facing n independent unpredictable challenges with combined success probability:
(1/3)ⁿ
it searches until each copy succeeds individually. After T trials per copy, the overall success probability becomes:
(1 − (2/3)ᵀ)ⁿ
For polynomially large T, this approaches 1. The exponential security promised by sequential repetition has been completely destroyed.
The lesson: sequential repetition only amplifies soundness when the prover genuinely can’t retry. Fiat–Shamir with nonce padding gives the prover exactly the retry capability that interactive protocols deny. Preventing this requires a stronger structural property called round-by-round soundness, which ensures that even a single round of cheating is hard to find by offline search.
We just saw what happens when the prover can retry — now let’s see what happens when the prover can postpone a choice.
Pitfall #2: Forgetting to Hash the Input
This is Exercise 5.2 from Thaler’s book.
The second pitfall is more insidious and has led to real-world vulnerabilities — sometimes called weak Fiat–Shamir.
Consider the GKR protocol (which I covered in detail in a previous post), an interactive proof for circuit evaluation built on the Sum-Check Protocol. The prover claims “circuit C on input x produces output y.” Now suppose someone applies Fiat–Shamir but omits x from the hash inputs. The challenges depend only on the circuit, the claimed output, and the prover’s messages — not on the actual input.
The Attack
An analogy first.
Imagine a teacher gives a math test. The rules are: you get the questions, then you write your answers, then you hand in both the question sheet and the answer sheet together. The teacher checks that your answers match the questions.
Now imagine a broken version of this test: the teacher lets you hand in the answer sheet first, and then pick which questions to staple to it. You could write down any answers you want, and then choose questions that happen to match those answers. You’d get a perfect score every time — not because you’re smart, but because you chose the questions after seeing what you needed them to be.
That’s exactly what happens when x is left out of the Fiat–Shamir hash. The prover gets to pick the “questions” (the input x) after already seeing what “answers” are needed (the final check values r and c).
Now let’s see this concretely.
What the prover claims. There’s a circuit C that takes an input x and produces an output. The prover says: “I have an input x such that C(x) = 0.”
We’ll use the simplest possible circuit: C(x) = x₁. It just outputs the first entry of the input. So the prover is claiming “my first input entry is 0.”
The prover is lying. It intends to use x₁ = 1. But it will get away with it.
How GKR verification works at the end.
The GKR protocol works layer by layer through the circuit, reducing the original claim to simpler and simpler claims. If you’ve read my previous post on GKR, you’ll recall that each layer uses the sum-check protocol to push the claim one level deeper.
At the very end — after all layers have been processed — the verifier is left with one final task: check something about the actual input x. Specifically, the protocol produces a random point r and a target value c, and the verifier checks:
x̃(r) = c
Here x̃ is the multilinear extension of x — just a fancy way of encoding the input as a polynomial that we can evaluate at non-Boolean points.
The important thing is: r and c are determined entirely by the challenges generated throughout the protocol. And the input x only matters at this single final step. Everything before it was about the circuit’s structure, not the input’s values.
What “x̃(r) = c” actually looks like.
This is the key piece, so let’s slow down.
The multilinear extension x̃ evaluated at a point r expands into a very simple expression — a weighted sum of all the input entries:
x̃(r) = α₁x₁ + α₂x₂ + ⋯ + αₘxₘ
Where do the weights α₁, …, αₘ come from? They are the Lagrange basis polynomials evaluated at r. Each αᵢ is computed from the coordinates of r alone — no input values involved. For example, if r = (r₁, r₂, r₃), then one of the weights might look like:
α₍₁,₀,₁₎ = r₁ · (1 − r₂) · r₃
Once r is fixed, every αᵢ is just a concrete number. So the check x̃(r) = c becomes:
(some known number) · x₁ + (some known number) · x₂ + ⋯ + (some known number) · xₘ = c
This is a single linear equation in m unknowns. If you remember high school algebra — one equation with many unknowns has infinitely many solutions. You can fix all but one variable to whatever you want and solve for the last one.
The attack, step by step.
Step 1. The prover runs the entire Fiat–Shamir protocol — generating all the challenges by hashing — without choosing x. This is possible because x was not included in the hash. The challenges don’t depend on x at all. The prover leaves x blank, like an empty form to fill in later.
Step 2. After generating the full transcript, the prover now knows r and c. It writes down the final check equation:
α₁x₁ + α₂x₂ + ⋯ + αₘxₘ = c
All the αᵢ are known numbers at this point. The prover stares at one equation with m blanks.
Step 3. The prover fills in the blanks strategically:
x₁ = 1 (this is the lie — it makes C(x) = 1, not 0)
x₂ = 0, x₃ = 0, …, xₘ₋₁ = 0 (zeros for simplicity)
The equation simplifies to:
α₁ · 1 + αₘ · xₘ = c
Solving for the one remaining unknown:
xₘ = (c − α₁) / αₘ
Over a large finite field, αₘ is nonzero with overwhelming probability, so this division works.
The result. The prover submits x = (1, 0, 0, …, 0, xₘ). The verifier checks x̃(r) = c — it passes, because the prover literally solved for an x that satisfies it. The verifier checks the rest of the transcript — it all passes too, because none of it depended on x. The verifier accepts.
But C(x) = x₁ = 1 ≠ 0 = y. The proof is for a false statement.
Why hashing x prevents this. If x were included in the Fiat–Shamir hash, the challenges would depend on x. The prover would have to choose x first, and only then would it learn r and c. It could no longer generate the transcript, peek at the final check, and reverse-engineer a convenient input.
Back to our analogy: if the teacher staples the questions to the answer sheet before handing it out, you can’t swap them anymore. You have to actually solve the questions you were given.
Core lesson: If the prover can choose part of the statement adaptively, that part must be included in the hash. Otherwise the prover can tailor the statement after seeing the challenges.
Takeaways
✓ Fiat–Shamir converts public-coin interaction into a single non-interactive message by replacing verifier randomness with hash outputs.
✓ Hash inputs must include the prover’s prior messages — this is what simulates the “commit before seeing the challenge” property of interaction.
✓ Hash chaining (rᵢ = H(rᵢ₋₁, i, gᵢ)) keeps inputs constant-sized while preserving full transcript dependence.
✓ For adaptive soundness, all adversarially chosen parts of the statement must be hashed too. Omitting them leads to the weak Fiat–Shamir vulnerability.
✓ Negligible soundness error alone isn’t sufficient — structural properties like round-by-round soundness are needed to resist offline grinding attacks.
The Fiat–Shamir transformation looks deceptively simple: just hash the transcript. But as Exercises 5.1 and 5.2 from Thaler’s book show, the details of what gets hashed, and what structural guarantees the base protocol provides, make the difference between a sound proof system and a broken one. If you’re building or auditing a real proof system, these aren’t academic curiosities — they’re the exact mistakes that have caused vulnerabilities in production implementations.
For a rigorous treatment of everything covered here — including formal security proofs and the precise conditions under which Fiat–Shamir preserves soundness — I highly recommend reading Chapter 5 of Thaler’s book. And for the original construction that started it all, see Fiat and Shamir’s 1986 paper How to Prove Yourself: Practical Solutions to Identification and Signature Problems, which remains remarkably readable forty years later.
References:
Justin Thaler, Proofs, Arguments, and Zero-Knowledge (2024), Chapter 5.
Amos Fiat and Adi Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems,” CRYPTO 1986.
