The Fiat-Shamir transform: how a hash function replaces a conversation

This post assumes you've read the Schnorr signatures post. You should be comfortable with s = k + ex, the verification equation sG = R + eP, and why nonce reuse is catastrophic. We're picking up exactly where that left off.

1. Schnorr as a conversation

Here's something I glossed over in the previous post. The Schnorr scheme we walked through - pick k, compute R = kG, hash everything to get e, compute s = k + ex, publish (R, s) - that's the non-interactive version. But Schnorr didn't start there.

Schnorr originally designed his scheme as an identification protocol - a way for Alice to prove to a server that she's the real account holder. Think of it like logging in, except instead of sending a password, Alice proves she knows the private key x without ever transmitting it. The protocol was a live conversation between two parties: a prover (Alice) and a verifier (Bob). Three messages, back and forth:

1. Alice → Bob: Alice picks a random nonce k, computes R = kG, and sends R to Bob. This is her commitment - she's locked into a particular k without revealing it.
2. Bob → Alice: Bob picks a random challenge e and sends it back.
3. Alice → Bob: Alice computes s = k + ex and sends s to Bob. Bob verifies that sG = R + eP.

Why does this prove anything? The key is the ordering. Alice commits to R in step 1 before she knows what e will be. Bob picks e randomly in step 2, after he's already received R. So Alice can't engineer the math - the only way she can produce an s that satisfies sG = R + eP for a random e she didn't choose is if she actually knows x. Bob's unpredictable challenge is what keeps her honest.

This protocol works. The question is: can we take this conversation offline?

On a blockchain, there is no Bob. There's no one to send a live challenge between steps 1 and 3. "Bob" is thousands of nodes verifying a transaction hours or days after it was created. There's no conversation, no real-time back-and-forth - just a signature sitting in a block, waiting to be checked by anyone, at any time.

2. The Fiat-Shamir heuristic: replace Bob with a hash

In 1986, Amos Fiat and Adi Shamir had a deceptively simple idea: what if the prover generates the challenge herself, by hashing the data she's already committed to?

Instead of waiting for Bob to send a random e, Alice computes:

e = H(R || P || m)

Alice takes her commitment R, her public key P, and the message m, and hashes them together. The output is the challenge e. No Bob needed.

Why is this secure? Because Alice commits to R before she can compute e. She can't predict what H(R || P || m) will produce before choosing R, and she can't reverse-engineer an R that gives her a convenient e. The hash binds the challenge to the commitment - exactly the guarantee that Bob's randomness provided in the interactive version.

What does verification actually prove?

Say you receive a signature (R, s) for a message m, and you know Alice's public key P. You compute e = H(R || P || m) and check whether sG = R + eP. If both sides are equal - the signature is valid. But what does that actually mean?

The equation sG = R + eP is really sG = R + e(xG), since P = xG. The only way to produce an s that makes both sides match is to compute s = k + ex - which requires knowing the private key x. You can't work backwards from P to extract x (that's the discrete logarithm problem), and you can't guess an s that works for a random e you didn't choose. So if the equation holds, whoever produced this signature must have known x.

The message is protected too. If someone tampers with m, the recomputed e = H(R || P || m) changes, the right side of the equation shifts, and verification fails. Same thing if R is modified, or if the signature was made with a different private key. Any mismatch and the equation breaks.

Alice proved she owns the private key behind P without revealing it. That's what every digital signature does - proves control of a secret without exposing it. In fact, this is a zero-knowledge proof - the simplest possible one. The statement being proved is just "I know x such that P = xG." Remember that when we get to ZK-SNARKs, where the statement is an entire computation.

3. The signature: three steps collapsed into one

Let's write out the full Fiat-Shamir-ized Schnorr signature:

Signing:

1. Pick a random nonce k
2. Compute R = kG
3. Compute e = H(R || P || m)
4. Compute s = k + ex (mod n)
5. Publish the signature (R, s)

Verification:

1. Recompute e = H(R || P || m)
2. Check that sG = R + eP

Look familiar? This is exactly the Schnorr signing and verification we covered in the previous post. The whole time, we were already using Fiat-Shamir - I just didn't name it. The "challenge" e that seemed like a straightforward hash was actually doing something profound: replacing an interactive protocol with a non-interactive one.

The three-message conversation (send R, receive e, send s) collapses into a single step: compute everything locally and publish the result. Anyone can verify later, offline, without participating in a conversation. This is what makes digital signatures possible in decentralized systems - there's no trusted verifier, no live interaction, just math and a hash function.

4. The Random Oracle: why this is secure (with a caveat)

The security proof for Fiat-Shamir relies on a model called the Random Oracle Model (ROM). The idea is simple: pretend the hash function is a perfect black box that outputs truly random values for each unique input. Under this assumption, the hash-generated challenge is indistinguishable from Bob's random challenge, so the non-interactive scheme inherits the security of the interactive one.

SHA-256 isn't actually a Random Oracle. It's a deterministic algorithm with a fixed structure. But it behaves enough like one that no practical attack has ever exploited the difference. In cryptography, "good enough" is a real thing - if the best known attack requires more computation than there are atoms in the universe, you're fine.

5. Why this matters: from conversations to blockchains

Fiat-Shamir gives us three things that make modern cryptographic systems work:

Non-interactivity. A signature is created once and verified by anyone, anytime. No live connection, no trusted verifier, no conversation. This is essential for blockchains, where a transaction might be verified by thousands of nodes months after it was signed.

Determinism. Given the same inputs (k, x, m), the signature is always the same. Combined with deterministic nonce generation (RFC 6979), the entire signing process is reproducible - no randomness needed at verification time.

Security. The hash function binds the challenge to the commitment. Changing any input - the nonce, the public key, the message - produces a completely different challenge. There's no wiggle room.

And here's the thing that makes Fiat-Shamir more than a historical footnote: it's everywhere. Every time a cryptographic protocol needs to turn an interactive proof into a non-interactive one, Fiat-Shamir is the tool. Schnorr signatures use it. Ed25519 uses it. But it goes far beyond signatures.

ZK-SNARKs use Fiat-Shamir. STARKs use Fiat-Shamir. Bulletproofs use Fiat-Shamir. Every modern zero-knowledge proof system that produces a non-interactive proof is applying the same trick: replace the verifier's random challenge with a hash of the prover's commitments.

In the Schnorr case, the statement being proved is "I know the private key x." But what if the statement were something more complex - like "I know an input that makes this entire computation produce this output"? That's where zero-knowledge proofs go next, and Fiat-Shamir is the bridge that makes them practical.