public-coin interactive proofs, collapsed by a hash

Fiat-Shamir — the bridge that turns an interactive protocol into a single signed transaction.

A 1986 technique due to Fiat and Shamir that converts any public-coin interactive proof into a non-interactive one by replacing each verifier challenge with the hash of the transcript so far. Challenges become deterministic, verifiable, and recomputable from the proof bytes — no live verifier dialogue required.

~3–5 rounds of PLONK interaction collapsed into one proof, with every challenge hashed under Poseidon2 over $F_r$, soundness in the random oracle model. The on-chain verifier re-derives the same challenges from the proof bytes and checks the same algebraic identity the interactive verifier would have checked.

~3–5 rounds
collapsed
Poseidon2
transcript hash
ROM
security model
per-relation
domain tag
deterministic
challenges

the shape — the interactivity collapse

Same prover messages. Different source of challenges.

A public-coin interactive proof is a sequence of rounds: the prover sends a message, the verifier draws a uniformly-random challenge, the prover sends the next message. Fiat-Shamir keeps the prover-side messages exactly the same and replaces the verifier with a hash function — each challenge is the hash of every message seen so far.

Interactive prover ↔ verifier · live
PROVER VERIFIER m₁ = [a]₁,[b]₁,[c]₁ β, γ ← rand() m₂ = [z]₁ α ← rand() m₃ = [t]₁ ζ ← rand() m₄ = evals υ ← rand() R1 R2 R3 R4

Each challenge is sampled fresh on the verifier side. The proof requires a live channel back to the prover.

Fiat-Shamir prover · transcript · Poseidon2
PROVER Poseidon2(·) over F_r m₁ = [a]₁,[b]₁,[c]₁ β, γ ← H(tag‖x‖m₁) m₂ = [z]₁ α ← H(prev‖m₂) m₃ = [t]₁ ζ ← H(prev‖m₃) m₄ = evals υ ← H(prev‖m₄) R1 R2 R3 R4

Prover messages are identical. The challenge source becomes a hash of the transcript — recomputable by anyone holding the proof bytes.

Transcript
append-only buffer of every message
Public input enters first, before any challenge is drawn. Each prover message is appended in order; the buffer is what every challenge hashes over.
Challenge
one $F_r$ element per round
Drawn by hashing the transcript-so-far with Poseidon2 over $F_r$. Replaces a uniformly-random verifier message; under the ROM the distribution is indistinguishable.
Domain tag
per-relation · per-tier prefix
Binds the transcript to a specific protocol context. Prevents a prover from transplanting a challenge derived in one relation into another that shares the same hash.

The collapse is one-sided: nothing about the prover's algorithm changes. The verifier's randomness is replaced by determinism. Under the random oracle model, no efficient prover can tell the difference — and the proof is now a single static byte string.

the transcript, step-through

A four-round PLONK transcript, message by message.

The hash is doing one job over and over: it absorbs the next prover message and emits the next challenge. Step through a representative PLONK transcript to see what's absorbed at each round and which challenge comes out.

/ 04 ·

transcript · absorbed so far
challenge · drawn this round

Every challenge depends on every prior message. A prover that tampers with a single prior message changes every downstream challenge — and the proof no longer verifies. That is the entire soundness intuition.

parameters

Concrete numbers.

Four fields fix the transform in this deployment. Two are protocol-level (hash, security model); two are deployment-level (round count, domain tag).

Transcript hash
Poseidon2 over $F_r$
Number of rounds collapsed
~3–5 (PLONK-variant dependent)
Domain-separation
per-relation · per-tier · circuit-binding context tag
Security model
Random Oracle Model (ROM)
Soundness reduction
Don–Fehr–Majenz–Schaffner 2019 · polynomial in rounds × queries
Verifier randomness budget
0 bytes · challenges are deterministic

wiring — prover, verifier, domain separation

One hash, two sides of the wire, same digests.

The transform is symmetric in a precise way: the prover and the verifier run the same Poseidon2 calls on the same accumulated transcript. The verifier never samples anything random — and that determinism is exactly what makes on-chain verification possible.

Prover · off-chain
Verifier · on-chain
Domain separation · once per circuit
build
Append the transcript
Starts with the domain tag and the public input $x$. Each prover message is appended in canonical byte order before any challenge is drawn from it.
F_r · Poseidon2
Hash for the next challenge
$c_i \leftarrow \text{Poseidon2}(\text{transcript so far})$. The prover plugs $c_i$ into the next-round computation as if it had been sent by an honest verifier.
emit
Pack the proof bytes
Only the prover messages ship — the challenges don't. The verifier will re-derive them. The full transaction is one signed artifact submitted to chain.
on-chain
Replay the same hashes
poseidon2(transcript)
Reads the proof bytes; reconstructs the transcript by interleaving the domain tag, public input, and prover messages; recomputes every $c_i$ bit-identically.
check
One algebraic identity
With challenges in hand, the verifier evaluates the final identity (a pairing, in PLONK's case). One bit out: accept or reject.
no RNG
Never asked to sample
A smart contract has no usable source of fresh randomness during proof verification — and doesn't need one. Determinism is what makes on-chain verification possible.
prefix
Per-relation · per-tier tag
The transcript is opened with a context string binding $(\text{relation name}, \text{tier index}, \text{circuit hash})$ — distinct for every circuit deployed.
why
No cross-protocol transplant
Two circuits sharing the same Poseidon2 instance cannot let a prover lift a challenge derived under one transcript and reuse it under another. The tag is what separates them.
operational landmine Every public input must enter the transcript before any challenge is drawn. Real-world deployments have shipped soundness bugs from omitting this — a missing absorb makes the proof malleable.

Cool/blue for the prover (off-chain); amber for the verifier (on-chain, the one side the chain pays for); neutral for the per-circuit domain-separation column. The red callout is the operational caveat: a missing absorb is the single most common source of Fiat-Shamir-related soundness bugs in deployed systems.

security

A heuristic that holds. A degradation that's bounded.

Two assumptions, two horizons — and unusually, both cards are green. Fiat-Shamir inherits the underlying hash's posture: well-studied soundness in the ROM today, a bounded Grover loss tomorrow. The system around it falls long before the transform itself does.

classical · holding
ROM

Sound in the random oracle model.

The Don, Fehr, Majenz, Schaffner (2019) analysis covers multi-round protocols of the PLONK family under Fiat-Shamir-with-aborts. Soundness loss is polynomial in the number of rounds and the prover's query budget — tight enough for production deployment at the chosen round counts.

  • ROM is a heuristic, not a standard-model proof — specific Fiat-Shamir instantiations have been broken when the hash exposed algebraic structure to the prover.
  • Poseidon2 has no published attacks of that kind, but its cryptanalysis is younger than SHA-256's.
  • Soundness reduction is tight enough for production deployment at the chosen round counts.
post-quantum · conjectured
Grover

Inherits the hash's PQ stance, with reduced margin.

Grover's algorithm gives a quantum prover a $\sqrt{N}$ advantage in searching for a transcript whose challenges align favorably. The Don et al. analysis quantifies the loss; in practice the underlying SNARK breaks for other reasons long before Fiat-Shamir does.

  • The PQ degradation is bounded and well-studied — not a collapse, just a reduced margin.
  • In practice the underlying SNARK falls under Shor on BLS12-381 long before Fiat-Shamir becomes the bottleneck.
  • Hash-based commitments would push Fiat-Shamir back to the front of the PQ analysis — but require a different SNARK family entirely.
critical
State-binding is critical. Every transcript message must enter the hash. Real-world deployments have shipped soundness bugs from getting this wrong — the public input must be bound to the proof before any verifier challenge is drawn, or a malleable proof becomes possible.

fiat-shamir vs bcs vs interactive

Three ways to collapse an interactive proof — and the baseline that doesn't.

Fiat-Shamir is the textbook collapse: it trades a standard-model soundness proof for the ROM and produces a non-interactive proof. BCS extends the same idea to interactive oracle proofs and pays in transcript size. Interactive is the baseline — and the one a smart-contract verifier cannot adopt.

this page

Fiat-Shamir

public-coin · transcript-hashing
Applies to
public-coin interactive proofs
Collapses
3–5 rounds of PLONK-family protocols
Security model
random oracle model (ROM)
Representative deployment
pairing-based SNARKs · PLONK, Groth16, Bulletproofs

BCS / IOP-Fiat-Shamir

interactive oracle proofs · Merkle-committed
Applies to
interactive oracle proofs (IOPs)
Collapses
many more rounds · e.g. FRI's $\log^2(n)$ rounds
Security model
ROM · oracle messages committed via a Merkle root
Representative deployment
hash-based SNARKs · FRI, STARKs

Interactive (no collapse)

live verifier dialogue · baseline
Applies to
any interactive proof
Collapses
nothing — every round is a live exchange
Security model
standard model · no ROM needed if the underlying protocol is sound
Representative deployment
classical zero-knowledge literature · impractical on-chain

Fiat-Shamir trades a standard-model soundness proof for the ROM and gets a non-interactive proof in return. BCS extends the same idea to IOPs and pays in transcript size. Interactive is the baseline neither the PLONK-on-Stellar verifier nor any deployed registry contract can adopt — the contract has no channel back to the prover.

references

Primary literature.

Four sources. The original Fiat–Shamir paper, the modern multi-round security analysis, the PLONK paper that consumes the transform, and the Poseidon2 paper for the hash instance.