Skip to content
LumenaryAcademy
Verifiable 80 min

Zero knowledge

Convincing someone that a statement is true while telling them nothing else, defined precisely, built from commitments, and made non-interactive.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Proving without revealing

To buy a bottle of wine, you show a cashier your identity card. The cashier needs one bit — over 18, yes or no — and receives your full name, birth date, address, card number and photograph. To log in to a website, you send it your password, and the site must now protect a secret that was never its own. To show that a rollup's new state is correct, an operator could publish every transaction, which works on a public blockchain and would be unthinkable for a payroll.

Each case asks for a proof that reveals nothing except the truth of the statement. That sounds paradoxical: how can I convince you that I know a password without giving you any information about it? In 1985 Goldwasser, Micali and Rackoff showed that it is possible, and made "nothing" precise. This lesson builds that definition, the tools that achieve it, and the trick that turns it into the kind of proof a blockchain can store. Along the way we meet real failures: zero-knowledge proofs are subtle, and production systems have shipped broken ones.

IntuitionH

A story: the coffee test

Lucía roasts coffee in Medellín. She says she can tell her washed Caturra from her honey-processed Castillo by taste alone. Her friend Tomás thinks the two taste identical, and he proposes a test. In each round he goes into the kitchen, tosses a coin out of her sight, brews the coffee the coin picks, and brings her the cup. She sips and names it. They play twenty rounds, and she is right every time.

Tomás is convinced. If the coffees really were indistinguishable, Lucía would be guessing, and twenty correct guesses in a row happen with probability 2−202^{-20}, less than one in a million. Notice what Tomás did not learn: not how Lucía tells them apart, not which notes she tastes, nothing he could use to pass the test himself. He learned one fact, that she can.

Now Tomás films the twenty rounds and shows the video to his cousin Wanjiru in Nairobi. She shrugs. "You two could have agreed in advance which cup you would bring each time. Anyone could make that video." She is right: a video of a successful test can be produced by people with no tasting skill at all, simply by choosing the answers before choosing the cups. And that is the heart of the matter. Whatever Tomás saw, he could have staged by himself. The interaction convinced him, because he flipped the coins himself at the moment it mattered; but it gave him nothing he could not have produced on his own, and so it gave him no knowledge beyond the fact itself.

Analogy, not a formal construction

In the formal definition, the video is the verifier's view (everything he saw, including his own coin flips), and the person staging a fake video is the simulator. A protocol is zero-knowledge if fake videos are indistinguishable from real ones.

DefinitionsH

Simulators, and what zero knowledge means

Take an interactive proof (from the previous lesson) for statements of the form "x∈Lx \in L", where the prover holds a witness ww (a secret that makes the statement easy to prove, such as a password, a private key or a colouring).

Definition— zero knowledge

The view of a verifier V∗V^* in an interaction with the honest prover P(x,w)P(x, w) is everything V∗V^* sees: xx, its own random coins, and every message it receives. The proof is zero-knowledge if for every efficient verifier strategy V∗V^* there is an efficient algorithm SS, the simulator, which given only xx (and no witness) outputs something indistinguishable from V∗V^*'s view, for every x∈Lx \in L.

It is perfect, statistical or computational zero knowledge according to whether the two distributions are identical, statistically close, or indistinguishable to every efficient algorithm. If the simulator is only required for the honest verifier VV, the protocol is honest-verifier zero-knowledge (HVZK).

Why does this capture "learning nothing"? Anything V∗V^* could compute from its view after the interaction, it could equally compute from the simulator's output, which it could have produced alone, without ever meeting the prover. So the interaction added nothing to what V∗V^* could compute, except the conviction that x∈Lx \in L. Note what the definition does not say: the simulator may cheat in ways the real prover cannot (Lucía's fake-video maker chose the answers first, a luxury the real test denies her). Simulators typically choose messages out of order, or "rewind" the verifier, which is fine because they are thought experiments run on paper, not participants in the real protocol.

Two more properties will appear constantly.

Definition— proof of knowledge

A protocol is a proof of knowledge if there is an efficient extractor that, given the ability to run (and rewind) any prover that convinces the verifier with good probability, outputs a witness ww. It formalises "the prover does not just know that x∈Lx \in L; it knows a witness".

Definition— commitment scheme

A commitment scheme lets a sender fix a value now and reveal it later. Commit(m;r)\mathrm{Commit}(m; r) uses fresh randomness rr and outputs CC; opening means revealing (m,r)(m, r). It must be hiding (CC reveals nothing about mm) and binding (no efficient sender can open CC to two different values). It is the digital version of a locked box placed on the table.

ExplanationH

Zero knowledge for every NP statement: graph 3-colouring

Is zero knowledge a curiosity of a few algebraic problems? In 1986 Goldreich, Micali and Wigderson showed it is not: every NP statement has a zero-knowledge proof, assuming commitments exist (which follows from one-way functions). They gave a proof for graph 3-colouring, which is NP-complete, so any NP statement can be translated into it (see hard problems for reductions).

The prover knows a proper 3-colouring of a graph GG with edge set EE. One round goes like this:

  1. The prover picks a random permutation of the three colours and recolours its colouring with it. (A proper colouring stays proper; the colour names now carry no information.)
  2. It commits to the colour of every vertex separately: one locked box per vertex.
  3. The verifier picks a random edge (u,v)(u, v).
  4. The prover opens the boxes of uu and vv only. The verifier checks that the two colours are valid and different.
????????23prover commitsverifier picks an edge
One round of the zero-knowledge proof of 3-colouring. Left: the prover commits to a freshly permuted colouring, one sealed box per vertex. Right: the verifier picks an edge, and only its two boxes are opened; they must show different colours.

Soundness. If GG has no proper 3-colouring, then whatever the prover committed to, at least one edge has equal (or invalid) colours at its ends, and the verifier picks it with probability at least 1/∣E∣1/|E|. Repeating nn rounds with fresh permutations and commitments drives the error down to (1−1/∣E∣)n(1 - 1/|E|)^n, below e−ke^{-k} after n=k∣E∣n = k|E| rounds.

Zero knowledge. In each round the verifier sees two different colours chosen uniformly by the random permutation, plus unopened boxes that, by hiding, reveal nothing. A simulator can produce that: guess an edge, commit to two random different colours at its ends and anything at all elsewhere, and if the verifier asks for a different edge, rewind and try again. The real argument needs care about cheating verifiers whose edge choice depends on the commitments, which is where hiding is used.

This protocol is a theorem, not a product: it needs many rounds and a commitment per vertex per round, so nobody proves real statements this way. But it establishes that zero knowledge is available for everything we will want to prove, and later lessons build the efficient versions.

ComputationC

Pedersen commitments

Let G\mathbb{G} be a group of prime order qq with generators gg and hh such that nobody knows log⁡gh\log_g h (for example, hh is derived by hashing a public string onto the group). The Pedersen commitment to m∈Zqm \in \mathbb{Z}_q with randomness r∈Zqr \in \mathbb{Z}_q is

C=gmhr.C = g^m h^r.
  • Perfectly hiding: for any CC and any message m′m', there is exactly one r′r' with C=gm′hr′C = g^{m'} h^{r'}. So when rr is uniform, CC is uniform in G\mathbb{G} whatever mm is; not even an all-powerful observer learns anything.
  • Computationally binding: two openings (m,r)≠(m′,r′)(m, r) \neq (m', r') of the same CC give gm−m′=hr′−rg^{m - m'} = h^{r' - r}, hence log⁡gh=(m−m′)/(r′−r) mod q\log_g h = (m - m')/(r' - r) \bmod q. Binding is as hard as computing that discrete logarithm.
  • Additively homomorphic: C(m1;r1)⋅C(m2;r2)=C(m1+m2; r1+r2)C(m_1; r_1)\cdot C(m_2; r_2) = C(m_1 + m_2;\ r_1 + r_2). Confidential-transaction schemes use this to check that hidden input amounts equal hidden output amounts.

The program uses a toy group, the squares modulo the safe prime p=2039p = 2039, which have prime order q=1019q = 1019. Group elements are numbers modulo pp and exponents are numbers modulo qq (see groups).

python
import random

# A toy group: the squares modulo the safe prime p = 2q + 1 form a subgroup of prime order q.
# Real systems use groups of order about 2^256 (for example elliptic curves). Learning only!
p, q = 2039, 1019
g, h = 4, 9                    # two generators of the order-q subgroup; nobody should know log_g(h)

def commit(m, r):
    return pow(g, m % q, p) * pow(h, r % q, p) % p

rng = random.Random(42)
m, r = 25, rng.randrange(q)                     # commit to the message 25 with fresh randomness
C = commit(m, r)
print("commitment C =", C, "  opens to 25:", C == commit(25, r), "  to 26 with the same r:", C == commit(26, r))

# Hiding: for this C, EVERY message has exactly one r that opens it, so C reveals nothing about m.
openings = {msg: next(s for s in range(q) if commit(msg, s) == C) for msg in [0, 1, 25, 500]}
print("an opening of C exists for each message:", openings)

# Homomorphism: multiplying commitments adds the messages (and the randomness).
m2, r2 = 17, rng.randrange(q)
print("C(25) * C(17) == C(42):", C * commit(m2, r2) % p == commit(m + m2, r + r2))

# Binding holds only while log_g(h) is unknown. In this tiny group we can just search for it...
t = next(x for x in range(q) if pow(g, x, p) == h)
print("log_g(h) =", t)
# ...and then open C to any message we like: g^m h^r = g^(m + t r), so solve m + t r = m' + t r'.
m_fake = 999
r_fake = (r + (m - m_fake) * pow(t, -1, q)) % q
print("C also opens to 999 with r' =", r_fake, ":", commit(m_fake, r_fake) == C)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The last lines are the whole security story in miniature. With q=1019q = 1019, a loop finds log⁡gh\log_g h instantly and binding is gone. In a group of order about 22562^{256}, the best known classical attacks need about 21282^{128} operations, which is why real commitments use such groups, and why whoever generates hh must provably not know its logarithm. (A large quantum computer would break binding, but not hiding: Pedersen commitments made today stay hiding forever.)

ComputationC

Schnorr's protocol: proving you know a discrete logarithm

Signatures and keys introduced Schnorr signatures. Underneath them sits an interactive protocol from 1989, in which a prover convinces a verifier that it knows the secret key xx behind a public key y=gxy = g^x, without revealing xx.

Definition— Schnorr identification protocol

Public: a group of prime order qq with generator gg, and y=gxy = g^x. The prover knows xx.

  1. Commit: the prover picks a fresh random k∈Zqk \in \mathbb{Z}_q and sends t=gkt = g^k.
  2. Challenge: the verifier sends a random c∈Zqc \in \mathbb{Z}_q.
  3. Response: the prover sends s=k+cx mod qs = k + cx \bmod q.

The verifier accepts if gs=t⋅ycg^s = t \cdot y^c.

Completeness is one line: gs=gk+cx=gk(gx)c=tycg^s = g^{k + cx} = g^k (g^x)^c = t y^c. This three-move shape — commitment, challenge, response — is called a Σ-protocol, and it has two properties that make it so useful.

Theorem— Schnorr's protocol is special-sound and HVZK

  1. Special soundness: from two accepting transcripts (t,c,s)(t, c, s) and (t,c′,s′)(t, c', s') with the same commitment and c≠c′c \neq c', one can compute x=(s−s′)/(c−c′) mod qx = (s - s')/(c - c') \bmod q.
  2. Honest-verifier zero knowledge: choosing cc and ss uniformly from Zq\mathbb{Z}_q and setting t=gsy−ct = g^s y^{-c} produces transcripts with exactly the same distribution as real ones with an honest verifier.

Proof

(1) Dividing gs=tycg^s = t y^c by gs′=tyc′g^{s'} = t y^{c'} gives gs−s′=yc−c′=gx(c−c′)g^{s - s'} = y^{c - c'} = g^{x(c - c')}, so x(c−c′)≡s−s′(modq)x(c - c') \equiv s - s' \pmod q, and c−c′c - c' is invertible because qq is prime.

(2) In a real transcript, cc is uniform, kk is uniform and independent of it, so s=k+cxs = k + cx is uniform and independent of cc; and tt is then determined by t=gsy−ct = g^s y^{-c}. The simulator produces cc and ss uniform and independent, with tt determined by the same equation. The distributions are identical.

∎

Special soundness gives the proof-of-knowledge property: an extractor runs a convincing prover, then rewinds it to just after it sent tt, sends a different challenge, and applies (1). The simulator is the formal version of Wanjiru's objection: by choosing the challenge first it can produce valid-looking transcripts without xx. Both are checked below; in a group of order 11 we can compare the two distributions exactly by listing every possibility.

python
import random
from collections import Counter

def schnorr_round(g, p, q, x, c, k):
    """One run of Schnorr identification. Prover knows x with y = g^x.
    k: the prover's fresh secret nonce; c: the verifier's random challenge."""
    t = pow(g, k, p)                  # 1. prover commits
    s = (k + c * x) % q               # 3. prover responds to the challenge c
    return t, c, s

def verify(g, p, q, y, t, c, s):
    return pow(g, s, p) == t * pow(y, c, p) % p

def simulate(g, p, q, y, c, s):
    """The simulator: choose the challenge and response FIRST, then solve for t. No secret needed."""
    t = pow(g, s, p) * pow(y, -c, p) % p
    return t, c, s

# --- Exact comparison in a tiny group: squares mod 23, prime order q = 11 (toy only) ----------
p, q, g = 23, 11, 4
x = 7                                 # the prover's secret
y = pow(g, x, p)
real = Counter(schnorr_round(g, p, q, x, c, k) for c in range(q) for k in range(q))
fake = Counter(simulate(g, p, q, y, c, s) for c in range(q) for s in range(q))
print("real transcripts:", len(real), " simulated:", len(fake), " identical distributions:", real == fake)
print("all simulated transcripts verify:", all(verify(g, p, q, y, *tr) for tr in fake))

# --- Special soundness: two answers to one commitment reveal the secret ------------------------
p, q, g = 2039, 1019, 4
rng = random.Random(3)
x = rng.randrange(1, q)
y = pow(g, x, p)
k = rng.randrange(q)                  # the prover is "rewound" and answers twice with the same k
t1, c1, s1 = schnorr_round(g, p, q, x, rng.randrange(q), k)
t2, c2, s2 = schnorr_round(g, p, q, x, rng.randrange(q), k)
assert t1 == t2 and c1 != c2 and verify(g, p, q, y, t1, c1, s1) and verify(g, p, q, y, t2, c2, s2)
extracted = (s1 - s2) * pow(c1 - c2, -1, q) % q
print(f"transcripts (t={t1}, c={c1}, s={s1}) and (t={t2}, c={c2}, s={s2})")
print("extracted secret:", extracted, " true secret:", x, " match:", extracted == x)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Schnorr's protocol is honest-verifier zero-knowledge; against a verifier that picks cc cleverly from the commitment, the simple simulator fails (it would have to guess cc in advance, with probability 1/q1/q). Restricting challenges to a small set and repeating, or the Fiat–Shamir transform below, deal with this. Σ-protocols for many other statements follow the same pattern: knowledge of an opening of a Pedersen commitment, equality of two discrete logarithms (used for verifiable decryption and verifiable random functions), and "I know the secret for one of these keys, without saying which" (the basis of ring signatures).

ComputationC

Fiat–Shamir: removing the verifier, and the weak-hash pitfall

An interactive proof convinces only the verifier who took part; a blockchain needs a proof that anyone can check later. In 1986 Fiat and Shamir proposed replacing the verifier's random challenge by a hash of everything said so far:

c=H(public parameters, statement, t [, message]).c = H(\text{public parameters},\ \text{statement},\ t\ [,\ \text{message}]).

The prover computes tt, then cc, then ss, and publishes (t,s)(t, s); anyone recomputes cc and checks. The transform works for any public-coin protocol (sumcheck included), and hashing a message in as well turns Schnorr identification into the Schnorr signature of Signatures and keys, where tt was called RR and cc was called ee. The intuition is that a hash behaves like a fresh random oracle: the prover cannot predict cc before fixing tt. That intuition is formalised in the random oracle model, where Fiat–Shamir is proven secure for Σ-protocols (Pointcheval and Stern, 1996).

The fine print is in the brackets. If the hash omits the statement — the public key, the commitments, the public inputs of a circuit — then the prover can fix tt and ss first, learn cc, and only then choose a statement that makes the equations hold. This is the weak Fiat–Shamir transform, analysed by Bernhard, Pereira and Warinschi in 2012 after they found it in the Helios voting system. The program attacks a Chaum–Pedersen proof, which claims that A=gxA = g^x and B=hxB = h^x for the same xx, and produces an accepting proof for a pair whose logarithms differ.

python
import hashlib
import random

# Toy group again: squares modulo p = 2q + 1, prime order q. For learning only.
p, q = 2039, 1019
g, h = 4, 9

def H(*items):
    """Hash a list of integers to a challenge in Z_q."""
    data = b"|".join(str(i).encode() for i in items)
    return int.from_bytes(hashlib.sha256(data).digest(), "big") % q

# Chaum-Pedersen: prove that A = g^x and B = h^x for the SAME secret x (equal discrete logs).
def prove(x, A, B, rng, strong=True):
    k = rng.randrange(q)
    t1, t2 = pow(g, k, p), pow(h, k, p)
    c = H(g, h, A, B, t1, t2) if strong else H(t1, t2)   # strong FS hashes the statement too
    return t1, t2, (k + c * x) % q

def verify(A, B, proof, strong=True):
    t1, t2, s = proof
    c = H(g, h, A, B, t1, t2) if strong else H(t1, t2)
    return pow(g, s, p) == t1 * pow(A, c, p) % p and pow(h, s, p) == t2 * pow(B, c, p) % p

rng = random.Random(2022)
x = 321
A, B = pow(g, x, p), pow(h, x, p)
print("honest proof, strong FS:", verify(A, B, prove(x, A, B, rng)))

# The attack on WEAK Fiat-Shamir: pick the commitments and the response first, learn c, and only
# then choose a (false!) statement A, B that makes the verification equations hold.
k1, k2, s = rng.randrange(q), rng.randrange(q), rng.randrange(q)
t1, t2 = pow(g, k1, p), pow(h, k2, p)
c = H(t1, t2)
a = (s - k1) * pow(c, -1, q) % q          # then g^s = t1 * (g^a)^c
b = (s - k2) * pow(c, -1, q) % q          # and  h^s = t2 * (h^b)^c
A_bad, B_bad = pow(g, a, p), pow(h, b, p)
forged = (t1, t2, s)
print("forged statement: log_g(A) =", a, " log_h(B) =", b, " equal?", a == b)
print("weak verifier accepts the forgery:  ", verify(A_bad, B_bad, forged, strong=False))
print("strong verifier accepts the forgery:", verify(A_bad, B_bad, forged, strong=True))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The forged proof "proves" a false statement, and the attacker never broke any hash or discrete logarithm. With the statement inside the hash, changing AA or BB changes cc, and the same trick fails.

This is not a classroom curiosity. In April 2022 Trail of Bits disclosed a family of such bugs, which it called Frozen Heart, in several open-source implementations of Girault's proof of knowledge, of Bulletproofs (traced to an under-specified transcript in the original paper) and of PlonK (public inputs missing from the hash); the affected projects were fixed before publication (disclosure). In June 2025 the Solana Foundation published a post-mortem on its ZK ElGamal Proof program, where components missing from a Fiat–Shamir transcript would have allowed forged proofs for confidential token transfers; it was patched and the program disabled for audit, with no known exploitation. The engineering rule that follows: hash everything — protocol and parameters, the full statement, and every prover message — with domain separation, and prefer transcript libraries that make omissions hard.

ExplanationH

Zero knowledge is not succinctness

Two properties are often blurred together, even in product names:

PropertyQuestion it answersExample
Zero knowledgeDoes the proof hide the witness?Schnorr's proof hides xx; a ZK proof of age hides the birth date.
SuccinctnessIs the proof short and fast to verify, compared with the computation?A sumcheck transcript is tiny compared with the sum it checks.

They are independent. The 3-colouring proof is zero-knowledge but not succinct: it grows with the graph. The sumcheck protocol of the previous lesson is succinct but not zero-knowledge: its messages leak information about gg. Many "zk-rollups" use succinct validity proofs with no zero-knowledge property at all, because their transaction data is public anyway; the name stuck for historical reasons. Systems that need both (private payments, private identity) take a succinct proof system and add zero knowledge, usually by masking polynomials with random blinding terms, which costs a little extra. When you read "ZK" in a product description, ask which of the two properties is actually claimed.

ExplanationH

Applications: private payments, credentials and age

Private payments. The Zerocash design (2014), deployed as Zcash in 2016, lets a user spend a hidden coin. The prover shows, in zero knowledge, that it knows a coin commitment inside the public Merkle tree of all coins (Hashes and Merkle trees), the secret key that owns it, and a nullifier derived from it that marks it spent without saying which coin it was; and that input and output amounts balance. Observers learn that some valid coin was spent, not which, by whom, to whom, or for how much. Zcash's later Orchard protocol (2022) uses the Halo 2 proof system, which needs no trusted setup (next lesson). Other designs reach different privacy points: Monero hides senders with ring signatures and amounts with Pedersen commitments and Bulletproofs range proofs. Financial privacy is also contested; misuse for laundering stolen funds and the regulatory responses are discussed in Applications, limits and regulation.

Anonymous credentials. David Chaum proposed in 1985 that people should be able to prove things about themselves without being tracked. Modern anonymous credential schemes let an issuer (a university, a state, a bank) sign a set of attributes, and let the holder later prove statements about those attributes to any verifier, revealing only what the statement requires, with each presentation unlinkable to the others. IBM's Idemix and Microsoft's U-Prove were early systems; the BBS signature scheme, designed for exactly this kind of selective disclosure, is in standardisation at the IRTF as of 2026.

Proving age without a birth date. A credential contains a birth date signed by an issuer. To enter an age-restricted website, the holder proves: I hold a credential with a valid issuer signature, bound to a key on my device, whose birth date is at least 18 years before today. The verifier learns one bit, plus the issuer's identity. The "at least 18 years" part is a range proof on a committed number, and the signature check is a computation proved in zero knowledge. In July 2025 Google open-sourced Longfellow ZK, a library that proves such statements about existing ECDSA-signed identity documents (announcement), in connection with European age-assurance and digital-identity-wallet efforts. Deployments like this are early, and questions remain about issuers, revocation, and who controls the wallets — but they are the first large-scale uses of zero knowledge outside blockchains.

Common misconceptionsH

Common misconceptions

Misconception

"Zero knowledge means the data is encrypted." Encryption hides data from people without a key; zero knowledge proves a statement about data while revealing nothing beyond its truth. A ZK proof may concern data that is public (the rollup state) or that nobody but the prover will ever see.

Misconception

"Honest-verifier zero knowledge is good enough." Only if verifiers follow the protocol. A verifier who chooses challenges adaptively may learn more, as Tomás with his mystery bag would. Fiat–Shamir sidesteps this because the "verifier" becomes a hash function, which cannot be malicious in the random oracle model, and many protocols are proven fully zero-knowledge directly.

Misconception

"Fiat–Shamir is a mechanical step that cannot go wrong." It is the most common place where implementations of correct protocols become unsound: omitted public inputs, parameters or prover messages; ambiguous encodings of what is hashed; and challenges reduced modulo the wrong number. There are also theoretical limits: there exist (contrived) protocols that are secure interactively and insecure under every concrete hash function, and in 2025 such an attack was made practical against a GKR-based proof system (the frontier lesson returns to this).

Misconception

"A zero-knowledge proof reveals nothing, so the statement can be anything." The statement itself is public, and it can leak. "My balance is exactly 1,234,567" proved in zero knowledge reveals the balance. Designing what to prove is part of the privacy engineering.

Exercises

Exercises

1. Zero knowledge

Warm-upHuman

A protocol has a simulator that, given only the public statement, produces transcripts indistinguishable from real ones. What does this establish?

Choose one

2. Zero knowledge

CoreHuman

Run one round of Schnorr's protocol in the toy group of squares modulo p=23p = 23, which has prime order q=11q = 11, with generator g=4g = 4. The prover's secret is x=7x = 7, its nonce is k=5k = 5, and the verifier's challenge is c=3c = 3. What response ss (an integer from 0 to 10) does the prover send?

3. Zero knowledge

CoreHuman

In a Schnorr group of prime order q=11q = 11, a prover answered the same commitment tt twice: challenge c1=9c_1 = 9 with response s1=2s_1 = 2, and challenge c2=4c_2 = 4 with response s2=5s_2 = 5. Both transcripts verify. What is the secret xx (from 0 to 10)?

4. Zero knowledge

StretchHuman

The zero-knowledge proof of 3-colouring is run on the five-vertex "house" graph of the lesson's figure, which has ∣E∣=6|E| = 6 edges. If the graph had no proper 3-colouring, a cheating prover would survive each round with probability at most 1−1/61 - 1/6. What is the smallest number of rounds nn for which (5/6)n≤2−40(5/6)^n \le 2^{-40}?

5. Zero knowledge

CoreHuman

You implement a non-interactive Chaum–Pedersen proof that A=gxA = g^x and B=hxB = h^x for the same xx, with prover messages t1=gkt_1 = g^k, t2=hkt_2 = h^k and response s=k+cxs = k + cx. Which values must go into the hash that computes the challenge cc? Select all that apply.

Choose all that apply

6. Zero knowledge

CoreHuman

In the coffee story, Tomás secretly buys a bag of unknown origin and brings Lucía a cup from it, asking "Caturra or Castillo?". Why does this matter for the definition of zero knowledge?

Choose one

7. Zero knowledge

CoreComputational

Write the honest-verifier simulator for Schnorr's protocol. simulate(g, p, q, y, c, s) receives the group (the subgroup of prime order q of the integers modulo p, generated by g), the public key y, and a challenge c and response s that the caller chose at random. Return a transcript (t, c, s) that the verifier accepts, gs≡t yc(modp)g^s \equiv t\,y^c \pmod p, without knowing the secret xx.

The tests check that every simulated transcript verifies, and that over a group of order 11 the simulated transcripts have exactly the distribution of real ones.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Zero knowledge

StretchComputational

Generalise Schnorr's protocol to prove knowledge of an opening (m,r)(m, r) of a Pedersen commitment C=gmhrC = g^m h^r, without revealing mm or rr, and make it non-interactive with strong Fiat–Shamir.

  • prove_opening(m, r, C, rng): pick random k1,k2∈Zqk_1, k_2 \in \mathbb{Z}_q with rng.randrange(q), set t=gk1hk2t = g^{k_1} h^{k_2}, compute the challenge exactly as c = H(g, h, C, t), and return (t, s1, s2) with s1=k1+cms_1 = k_1 + cm and s2=k2+cr(modq)s_2 = k_2 + cr \pmod q.
  • verify_opening(C, proof): recompute c = H(g, h, C, t) and check gs1hs2≡t Cc(modp)g^{s_1} h^{s_2} \equiv t\,C^c \pmod p.

The toy group, H and commit are provided. The tests also try a forgery built for a verifier that forgot to hash CC.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources