Fiat–Shamir transform

Why do we need the Fiat–Shamir transform?

Start with an interactive proof.

A prover wants to convince a verifier that some statement is true. The verifier sends unpredictable challenges, and the prover responds.

This interaction is useful because the verifier's challenge is unpredictable to the prover when the commitment is created.

But an interactive protocol has a practical problem: the prover and verifier must communicate during the proof.

The Fiat–Shamir transform removes that interaction by replacing the verifier's random challenge with a cryptographic hash of the transcript.

First understand an interactive proof

Most Fiat–Shamir explanations become much easier if you first understand the interactive protocol it transforms.

A common three-message public-coin protocol has this shape:

The verifier checks:

The important property is that c is chosen after A.

The prover commits first, before knowing which challenge it will have to answer.

What does “public-coin” mean?

In a public-coin protocol, the verifier's message is essentially a random challenge.

There is no secret verifier state that the prover needs to learn.

This matters because Fiat–Shamir is designed around replacing this public random challenge with a deterministic value derived from the transcript.

The central Fiat–Shamir idea

Instead of:

the prover computes:

or, more generally:

The response is then computed using that challenge:

The verifier independently computes the same hash and therefore derives the same challenge.

The transcript is the key

The verifier must derive the exact same challenge as the prover.

Therefore both parties need the same transcript bytes.

This is why real proving systems use transcript objects rather than casually concatenating arbitrary values.

The transcript typically defines:

• what gets absorbed into the hash;
• the exact byte encoding;
• domain-separation labels;
• when a challenge is sampled;
• how the digest becomes a field element or other challenge type.

Concrete example: Schnorr identification

Consider a cyclic group with generator g.

The prover knows a secret:

and the public key is:

The prover wants to demonstrate knowledge of x without revealing it.

Step 1 — commitment

The prover chooses random:

and computes:

Step 2 — verifier challenge

In the interactive protocol:

Step 3 — response

The prover sends:

Step 4 — verification

The verifier checks:

Why?

Apply Fiat–Shamir to Schnorr

Replace the verifier's random challenge with a hash:

The prover computes:

The final proof is approximately:

The verifier receives the public key, message, and proof. It recomputes:

and checks:

No interactive challenge was required.

Why can't the prover choose the challenge?

This is the heart of the soundness intuition.

Suppose the prover could choose both:

before committing to the protocol state.

Then a malicious prover might construct a response specifically for a challenge it already knows.

Interactive protocols prevent this by forcing:

Fiat–Shamir tries to preserve that ordering cryptographically:

The prover cannot choose c independently after fixing A; the challenge is tied to the commitment through the hash.

The random-oracle viewpoint

Security proofs for Fiat–Shamir are often described using the random oracle model.

In this idealized model, a hash function behaves like a random function:

For an input that has not previously been queried, the output is modeled as unpredictable.

This resembles the verifier's random challenge:

In the random-oracle model, the second value can behave like a fresh random challenge once the transcript has been fixed.

Where does soundness come from?

Suppose a false statement can only be answered successfully for a small fraction of possible challenges.

For example, imagine a false prover succeeds for at most:

of all possible challenges.

In the interactive protocol, the verifier independently chooses the challenge, so the prover cannot reliably predict it.

With Fiat–Shamir, the challenge is generated from the commitment:

Under the random-oracle heuristic, the prover cannot predict or freely program this challenge in the ordinary execution of the protocol.

This preserves the basic intuition that a false prover must get lucky with the challenge.

The special role of rewinding in proofs

Interactive-proof security proofs often use a technique called rewinding.

Conceptually, a simulator or extractor may run a prover, observe a commitment, and then obtain responses to different challenges.

Two valid responses to different challenges can reveal useful algebraic information.

For Schnorr, for example:

Subtract:

so:

This illustrates why a malicious prover that can answer many different challenges consistently may be forced to know the underlying witness.

What about zero knowledge?

Fiat–Shamir itself is not a zero-knowledge property.

It is a transformation that removes interaction from certain public-coin protocols.

Whether the resulting proof is zero knowledge depends on the underlying protocol and its security proof.

Transcript design is cryptographic design

A common beginner mistake is:

without specifying exactly which values and how they are encoded.

A robust transcript should make the protocol state explicit.

The exact fields depend on the protocol.

Why include the statement?

The challenge should be bound to the statement being proved. Otherwise the same commitment could potentially be reused across different statements in ways the protocol did not intend.

Why include a domain separator?

Different protocols should not accidentally interpret the same hash input as the same challenge.

Why specify encoding?

If two implementations serialize the same mathematical object differently, they will derive different challenges and the proof will fail verification.

Turning a hash into a field challenge

ZK systems frequently need a challenge in a finite field:

But a cryptographic hash gives bytes.

So the transcript must define a conversion:

For a simple educational field, one might reduce an integer modulo the field modulus:

Real protocols may use rejection sampling or specialized challenge-generation rules to avoid undesirable statistical bias or other issues.

Fiat–Shamir with multiple rounds

ZK protocols often have many challenge points.

For example:

The transcript is extended after every message.

This creates a deterministic chain of challenges.

In a transcript implementation, this often looks like:

Fiat–Shamir inside STARKs

Fiat–Shamir is fundamental to non-interactive STARK-style protocols.

A simplified STARK flow is:

The prover does not wait for a network message from a verifier after every commitment. Instead, the transcript determines the challenges.

This is what turns an interactive public-coin proof into a non-interactive proof that can be generated and verified independently.

Fiat–Shamir inside FRI

FRI repeatedly commits to evaluation vectors and derives challenges that determine how the prover folds them.

Conceptually:

The verifier recomputes the same challenges from the transcript.

This is why transcript correctness is not a cosmetic implementation detail in FRI or STARK code. A different byte encoding or challenge order means a completely different proof.

Fiat–Shamir transcript in Rust

Here is a small educational transcript implementation. It demonstrates the core pattern: absorb protocol data, hash the transcript, and derive a challenge.

// Cargo.toml:
// sha2 = "0.10"

use sha2::{Digest, Sha256};

struct Transcript {
    state: Vec<u8>,
}

impl Transcript {
    fn new(domain: &[u8]) -> Self {
        let mut state = Vec::new();

        // Domain separation.
        state.extend_from_slice(domain);

        Self { state }
    }

    fn append_message(
        &mut self,
        label: &[u8],
        message: &[u8],
    ) {
        // Length prefixes make the encoding explicit.
        self.state
            .extend_from_slice(&(label.len() as u64).to_le_bytes());

        self.state.extend_from_slice(label);

        self.state
            .extend_from_slice(&(message.len() as u64).to_le_bytes());

        self.state.extend_from_slice(message);
    }

    fn challenge_bytes(&self) -> [u8; 32] {
        let digest = Sha256::digest(&self.state);
        digest.into()
    }

    fn challenge_u64(&self) -> u64 {
        let digest = self.challenge_bytes();

        let mut bytes = [0u8; 8];
        bytes.copy_from_slice(&digest[..8]);

        u64::from_le_bytes(bytes)
    }
}

fn main() {
    let commitment = b"commitment-A";

    let transcript =
        Transcript::new(b"example-protocol-v1")
            .append_message(
                b"commitment",
                commitment,
            );

    let challenge = transcript.challenge_u64();

    println!("challenge = {challenge}");
}

This is deliberately simple. A production transcript should be designed around the exact protocol and should use an appropriate challenge-generation construction rather than treating arbitrary bytes as a complete cryptographic specification.

A more realistic STARK-style transcript pattern

In a proving system, the transcript often follows a pattern like:

The critical invariant is:

If they diverge by even one byte, every subsequent challenge can diverge.

Why transcript binding matters

Suppose a challenge were generated only from a commitment:

But the proof is actually intended to establish a statement S.

It is generally safer for the challenge derivation to bind the relevant statement and protocol context:

Otherwise a transcript might be reusable in a context where the protocol did not intend it to be reusable.

Exact transcript binding requirements are protocol-specific, but the general principle is universal: hash the data that the challenge is logically supposed to depend on.

The forking intuition

Security proofs for Fiat–Shamir often use a forking argument.

Very roughly, imagine a successful malicious prover that produces:

If a reduction can obtain another accepting transcript with the same commitment but a different challenge:

then the two accepting transcripts may reveal information that contradicts the prover's supposed ability to prove a false statement without the witness.

For Schnorr, this is exactly the algebra behind extracting the secret:

The full security theorem is more subtle than this intuition, but the example shows why challenge unpredictability and transcript binding are central.

Fiat–Shamir is not magic

Interactive vs Fiat–Shamir

How it fits into a ZK proving pipeline

For a STARK, this can involve commitments to trace-derived evaluation vectors, random field challenges, composition-polynomial combinations, FRI commitments, and query positions.

For a SNARK, Fiat–Shamir can be used to derive challenges in polynomial interactive-oracle protocols, inner-product arguments, and other proof components.

The recurring pattern is:

The whole idea in one map

If Merkle trees answer “how do we commit to a large vector?”, and polynomial commitments answer “how do we commit to a polynomial?”, Fiat–Shamir answers “how can a public-coin interactive proof generate its own verifier challenges from a cryptographic transcript?”