Non-interactive zero-knowledge proofs: Fiat–Shamir with Schnorr

In the Ali Baba cave example, the verifier must choose an unexpected exit after the prover enters. A recording can be staged with the questions agreed in advance. So how can a proof saved in a file convince someone who never took part in its creation?

Start with three messages

Consider the Schnorr identification protocol. Alice has a secret number a and publishes A = ga mod p. Here, mod p means taking the remainder after division by p. The public parameters specify a group in which recovering a from A is computationally difficult.

The claim is precise: Alice knows the exponent producing this particular A. Showing that some exponent exists would not establish that she knows it.

1. Alice chooses a fresh secret random number v, computes V = gv mod p and sends V. This first message is the commitment.
2. Bob chooses a random challenge c and sends it to Alice.
3. Alice sends the response r = v − a × c mod q, where q is the order of the group: exponents repeat after q steps.

Bob checks the public values belong to the required group and verifies V = gr × Ac mod p. Substituting Alice’s response explains the equality: gv−ac × gac = gv. Neither a nor v is sent.

Let a hash supply the challenge

Fiat–Shamir replaces Bob’s message with a computation. Alice first creates V, then hashes the public statement, that commitment and the protocol context to obtain c. Only then does she calculate r.

The verifier already knows the public parameters and statement, and receives the required context with the proof. The hash input contains no secret exponent. It includes only messages preceding the challenge; the response r is calculated afterwards.

Both sides must encode the input identically. Simply joining variable-length strings is ambiguous: “1” followed by “23” and “12” followed by “3” both produce “123”. A length prefix gives each field an unambiguous boundary. A protocol label and context bind the result to its intended use.

A complete numerical example

Take p = 23, q = 11 and g = 2 so we can follow the arithmetic by hand. Powers of 2 modulo 23 repeat after 11 steps. Let Alice’s secret be a = 3 and her fresh random value be v = 6.

• Public statement: A = 23 mod 23 = 8.
• First message: V = 26 mod 23 = 18.

For this calculation, encode the following eight UTF-8 strings in order. Put each string’s byte length in a four-byte unsigned big-endian integer before its bytes:

yieldo:schnorr-example:v1
23
11
2
8
18
alice
article-2026-11-03

SHA-256 of those bytes is:

20334aa464de6ff6c3b5bb30644be32eb7f2fd4f187fbf1a96e8b85e00a1a79a

Read the digest as an unsigned big-endian integer and take its remainder modulo 11. This gives c = 4. Alice’s response is r = (6 − 3 × 4) mod 11 = 5. The proof carries V = 18, r = 5 and the agreed context; it does not carry her secret 3.

The verifier recomputes the hash, obtains the same challenge 4, checks the public value is in the subgroup (811 mod 23 = 1), then checks:

2^5 mod 23 = 9
8^4 mod 23 = 2
9 × 2 mod 23 = 18 = V

The full computation can also be reproduced with Python’s standard library:

import hashlib

p, q, g, a, v = 23, 11, 2, 3, 6
A, V = pow(g, a, p), pow(g, v, p)
fields = ["yieldo:schnorr-example:v1", str(p), str(q),
          str(g), str(A), str(V), "alice", "article-2026-11-03"]
encoded = b"".join(len(s.encode()).to_bytes(4, "big")
                   + s.encode() for s in fields)
c = int.from_bytes(hashlib.sha256(encoded).digest(), "big") % q
r = (v - a * c) % q
print(A, V, c, r)  # 8 18 4 5
print(pow(g, r, p) * pow(A, c, p) % p == V)  # True

Why not choose a convenient challenge?

The security analysis treats the hash as a random oracle: a new input gets an independent random answer, while a repeated input gets the same answer as before. A real hash is deterministic. The random oracle is the mathematical model used to analyse this construction, with assumptions about both the starting protocol and the hash.

That also explains an apparent puzzle about zero knowledge. In the simulation argument, an algorithm can construct a convincing transcript without the secret by programming the model’s oracle. An ordinary participant cannot program SHA-256 that way. This simulation establishes what the proof reveals; it does not give that participant control of the real hash.

Why the random value must stay fresh

The secret random value v, also called a nonce, masks Alice’s secret in the response. Reusing it for two different challenges exposes the secret through subtraction. Suppose the same v = 6 gives a second challenge c′ = 7 and response r′ = 7. Anyone with both transcripts can recover:

a = (r − r′) / (c′ − c) mod 11
  = (5 − 7) / (7 − 4) mod 11
  = 3

Division modulo 11 means multiplying by the modular inverse: the inverse of 3 is 4, since 3 × 4 mod 11 = 1. Thus −2 × 4 mod 11 = 3. The same issue arises when one commitment is reused across different contexts that produce different challenges.

Where this fits in ZK

NIZK means non-interactive zero-knowledge proof: the verifier checks a proof without an exchange of fresh questions with its creator. Public parameters and an agreed verification algorithm are still needed. Proof size is a separate property.

Fiat–Shamir is a way to remove verifier messages from suitable protocols whose challenges are public randomness. A common reference string, or CRS, describes public setup information; it is a different part of a proof system’s design. Names such as SNARK and STARK introduce further properties and constructions. The ZK platform map connects those systems to networks, private applications and computation markets.