# How does the Fiat-Shamir transform work?

The Fiat-Shamir transform turns an interactive proof, where the verifier sends random challenges, into a single message. The prover computes each challenge as a hash of everything sent so far, so no back-and-forth is needed.

Also called Fiat-Shamir heuristic.

## The problem it solves

In an interactive proof, the verifier picks random challenges after seeing the prover's messages, and the prover must answer them. That exchange needs both sides online at the same time, which is impractical for a proof that anyone should be able to check later.

## How the transform works

The prover runs the protocol alone. Wherever the verifier would send a random challenge, the prover applies a hash function to the messages so far and uses the result as the challenge.

Because the challenge depends on the prover's earlier messages, the prover has to commit before it learns the challenge. The result is one message that anyone can check by recomputing the same hashes.

## Where it is used

STARKs and PLONK-style SNARKs use it to become non-interactive. The FRI paper notes that this approach is typically realized with a hash function such as SHA-2.

The random oracle model treats the hash as a random function, so each protocol needs its own security analysis. A 2023 ePrint studies whether the transform stays secure for FRI and related SNARKs.

## In Redacted

In bunker mode, every proof transcript uses SHA-256, and the STARK behind each spend has no cryptographic building block other than the hash.

More: [Bunker mode](https://redacted.gg/docs/using-redacted/bunker-mode.md)

## Related terms

- [Hash function](https://redacted.gg/glossary/hash-function.md): A hash function turns any input into a short fingerprint of fixed size. The same input always gives the same fingerprint, and nobody can work back from it or find two inputs that share one.
- [STARK](https://redacted.gg/glossary/stark.md): A STARK is a short proof that a long computation was done correctly, which anyone can check quickly. It is built from hash functions alone, so it needs no trusted setup and no elliptic curves, and it can keep the inputs secret.
- [Prover and verifier](https://redacted.gg/glossary/prover-and-verifier.md): In a proof system, the prover makes a claim and builds a proof, and the verifier checks that proof. The verifier accepts only a valid proof, so the prover's claim does not have to be trusted.
- [FRI](https://redacted.gg/glossary/fri.md): FRI is the low-degree test used in STARKs. It checks that committed values come from a polynomial of low degree by halving the problem round after round and testing a few random points, and it rests only on hash functions.
- [zk-SNARK](https://redacted.gg/glossary/zk-snark.md): A zk-SNARK is a zero-knowledge proof that is small, quick to verify and needs only one message from the prover, which is why blockchains can check them inside a smart contract.
- [Soundness and completeness](https://redacted.gg/glossary/soundness-and-completeness.md): Completeness means an honest prover can always convince the verifier of a true statement. Soundness means a cheater cannot convince the verifier of a false one, except with a negligible chance.

Sources: [Fast Reed-Solomon Interactive Oracle Proofs of Proximity, ECCC 2017](https://eccc.weizmann.ac.il/report/2017/134/), [Fiat-Shamir Security of FRI and Related SNARKs, Block et al., IACR ePrint 2023/1071](https://eprint.iacr.org/2023/1071)
---

Page: https://redacted.gg/glossary/fiat-shamir/