Abstract

The Fiat-Shamir transform converts an interactive public-coin proof protocol - where the verifier sends random challenges - into a non-interactive proof by replacing the verifier’s challenges with outputs of a hash function applied to the transcript so far. First described by Amos Fiat and Adi Shamir in 1986, the transform is provably secure in the random oracle model and is the mechanism behind every practically deployed non-interactive zero-knowledge proof system, from Schnorr signatures to PLONK to Bulletproofs. Understanding exactly how the transform is applied and where it can fail is critical for anyone implementing or auditing ZK systems.

The Interactive Protocol and the Transform

A public-coin sigma protocol has three moves: commitment (prover sends a commitment to randomness), challenge (verifier sends a uniformly random challenge), and response (prover sends a response that depends on the challenge and the witness). The Fiat-Shamir transform replaces the challenge with H(statement

commitment), where H is modeled as a random oracle. The prover can now compute the challenge themselves, produce the response, and publish the triple (commitment, challenge, response) as a standalone proof. The verifier recomputes the challenge from the public inputs and checks the response. No interaction is needed; the proof is a fixed-size object that can be posted on-chain, stored in a file, or batched with other proofs.

Transcript Binding and Common Implementation Errors

The most critical implementation detail is what goes into the hash. The challenge must be bound to the full statement being proved, including all public inputs, the generator parameters, and every prior message in the transcript. Omitting any component creates a malleability attack where a prover can produce a valid proof for a different statement or reuse proof elements across unrelated proofs. A well-known example is Schnorr signature malleability when the message is not included in the hash. In multi-round protocols like PLONK and STARK, each round challenge must also include all prior round commitments to prevent an adversary from adaptively choosing earlier commitments after seeing a later challenge. Libraries like merlin (Rust) implement transcript objects that enforce correct binding by requiring the application to label every element added to the transcript, making omissions visible in code review.

Domain Separation in Multi-Protocol Systems

When multiple proof systems share a hash function implementation - common in composite ZK systems that combine, say, a Merkle membership proof with a range proof - domain separation is mandatory. Without it, a valid proof for one subprotocol could be replayed as a challenge contribution in another, breaking soundness. Domain separation is typically achieved by prefixing each hash invocation with a protocol-specific label string. The merlin library enforces this through typed transcript operations; other systems use a domain separation byte prepended to each H() call. The absence of domain separation has been the root cause of several ZK soundness bugs found during audits of custom proof systems built by teams who hand-rolled their Fiat-Shamir instantiation rather than using a well-tested transcript library.

Random Oracle Model Versus Standard Model

The Fiat-Shamir transform is proven secure only in the random oracle model (ROM), where the hash function is treated as an idealized object that returns uniform random outputs. In the standard model, using a concrete hash function, there exist artificial counterexamples where Fiat-Shamir fails - constructed by Goldwasser and Tauman Kalai. For practical applications, ROM security is considered sufficient: no attacks against ROM-secure Fiat-Shamir instantiations using SHA-3, Blake2b, or Poseidon have been demonstrated. The practical risk is not the ROM assumption but rather incorrect transcript construction, domain separation omissions, or hash function misuse at the implementation level. For production deployments, using established libraries like bellman, halo2, or gnark which handle Fiat-Shamir internally is significantly safer than building a custom instantiation.