Fiat-Shamir heuristic

The Fiat-Shamir heuristic is the standard trick for turning an interactive proof into a non-interactive one. In the interactive version, the verifier injects fresh randomness by sending random challenges; Fiat-Shamir replaces that human-in-the-loop randomness with a hash. The prover computes each "challenge" themselves by hashing everything said so far in the protocol — the transcript — and because a good hash is unpredictable, the prover cannot steer the challenge to their advantage any more than they could a real random coin. The result is a single self-contained proof anyone can verify offline, which is exactly what a blockchain needs.

The security argument lives in the random oracle model: if the hash behaves like a truly random function, the compiled non-interactive proof is as sound as the interactive original. This is why STARKs, Bulletproofs, and the non-interactive forms of sigma protocols all rely on Fiat-Shamir. It is called a heuristic because real hash functions are not actually random oracles, so the guarantee is heuristic rather than fully proven — though no practical break of a correctly applied instance is known.

The dangerous subtlety is what you hash. "Strong" Fiat-Shamir hashes the entire transcript, including the public statement and all prior commitments; "weak" Fiat-Shamir omits some of it. Skipping inputs has caused real, severe vulnerabilities — the 2022 "Frozen Heart" disclosures found that several widely used proof libraries derived challenges without binding the public inputs, letting attackers forge proofs of false statements. The rule of thumb is brutal but simple: absorb everything the verifier would have seen, or your soundness can silently evaporate.