The Proof That Tells You Nothing

Somebody says they can colour the ten dots below with three colours so that no line ever joins two of the same. Try it first, because it is fiddlier than it looks. Then they refuse to show you their answer, and over a hundred rounds they convince you anyway, past any doubt you care to name, while handing you nothing you did not already have. This is the 1986 Goldreich, Micali and Wigderson protocol running for real: SHA-256 commitments you recompute yourself, a prover sealed in a worker so the page cannot peek, and a challenge you choose. Then the part the explainers skip. A machine holding no colouring at all makes transcripts you cannot tell from the true ones, and you can sit the blind test and watch yourself score fifty percent. Shrink one number from 128 bits to 12 and the same protocol hands over the whole secret in under a second, which is what the word computational is doing in computational zero knowledge.

Movement I

First, try to do it yourself

This is the Petersen graph: ten vertices, fifteen edges, the standard awkward customer of graph theory. Click a vertex to cycle its colour. The task is to leave no edge with the same colour at both ends.

There are 120 ways to do it, out of 59,049 possible colourings, so a random guess works about 1 time in 492. The page enumerated all of them just now, in your browser, to say that.

Movement II

The claim, and why it looks impossible

Now suppose somebody else says: I have a proper three-colouring of that graph, and I am not going to show it to you. Convince yourself that they are telling the truth.

The obvious move fails. If they show you the colouring, you learn it, and they have given away the thing they were trying to keep. If they show you nothing, you learn nothing, including whether they were telling the truth. There seems to be a straight trade between the two, and for most of the history of the subject people assumed there was.

Here is the move that breaks the trade. They cover every vertex, so you can see there is a colour under each cover but not which. You point at one edge. They uncover exactly its two ends. If the colours differ, they survive the round; if they match, they are caught. Then they shuffle which colour is which and start again, so that what you saw last round tells you nothing about what you will see next.

Covering something so that it cannot be changed later, and can be uncovered on demand, is what a commitment is. On this page the cover is a SHA-256 digest of three things: the vertex number, the colour, and a random nonce. To uncover, the prover hands you the colour and the nonce, and you recompute the digest and see that it is the one they published before you chose.

Movement III

Run it

Press new round. Ten digests appear, one per vertex, computed by a prover running in a separate worker thread; the page you are reading never receives the colouring. Then choose an edge by clicking it, and check the answer.

That third counter is the only thing the protocol actually buys you, so it is worth being exact about what it means. This is the place where short explanations usually go wrong.

The guarantee is about the statement, not about the person. Suppose the graph were not three-colourable at all. The prover still has to commit to some colour at every vertex before you choose, and whatever they commit to, at least one edge must then have matching ends. If you point at it, they are finished. The best case for them is that exactly one edge is bad, so they survive one round with probability at most 14/15, and k rounds with probability at most (14/15)^k. Driving that under one in a million takes 201 rounds.

Two footnotes that matter. It is an inequality, not an equality: a carelessly chosen assignment leaves several bad edges and gets caught far sooner. And the Petersen graph is three-colourable, so on this instrument the thing being proved is true and the arithmetic above describes a bluffer who never found a colouring rather than a liar who could not have one. Movement VII runs the identical protocol on a graph where no colouring exists, and there the bound is exactly tight.

Movement IV

So what did you just learn?

You now hold a transcript: a pile of digests, and for each round the two colours at the ends of the edge you picked. It is worth asking what is in it.

Two things, and only two. The pair of colours was always different, which you knew in advance would be the case if the prover was honest. And which two colours they were is uniformly random, because the prover reshuffles the naming of the colours every round. Run enough rounds and watch both facts appear.

Every vertex comes up each colour a third of the time. Not because the prover is being coy, but because there is nothing else it could be: any proper colouring can have its three colours renamed six ways, all of them equally valid, and the prover picks one of the six at random each round. The transcript records a colouring that changes its mind about which colour is which every few seconds.

Movement V

The transcript could have been faked, and that is the good news

Here is the claim that makes this a zero-knowledge proof rather than merely a convincing one. The transcript you are holding contains nothing about the colouring, and the way to demonstrate that is to produce the same transcript without one.

Consider a machine that has never seen a colouring and could not find one. It guesses which edge will be challenged, colours only those two ends (two different colours, chosen at random), fills every other vertex with noise, and commits to that. If the guess was right, the round it produces is indistinguishable from a real one. If the guess was wrong, it throws the round away and tries again. With fifteen edges it will need about fifteen attempts per kept round.

Notice what just happened. That round passes the check. It was produced by something with no colouring, on a graph it cannot colour. And the throwing-away is not a cheat that a real prover could use, because a real prover cannot rewind you and make you choose again. The whole point of the rewinding is that it is available to the simulator and not to the prover, which is precisely why a transcript the simulator can produce is a transcript that carried no secret.

So the honest form of the claim is not "the simulator can fool you live". It is: the finished transcript is the same object either way. Which invites a test.

If your hit rate settles near half, you have just operated the definition. A proof is zero-knowledge when whatever you could compute after seeing it, you could have computed before, by running the simulator yourself. You did not learn a colouring, because there was a transcript on the table that never contained one and you could not pick it out.

Movement VI

Where the word computational earns its keep

All of that rests on one thing: that a digest hides what went into it. There are only three colours. If the prover hashed the colour alone, anyone could hash all three candidates, compare, and read the entire colouring straight off the board before choosing an edge. The nonce is the only reason that fails, and it fails only because the nonce is long.

So shorten it and watch the protocol stop working. Below, the prover commits with a nonce of whatever length you choose, and the page brute-forces every commitment in the round.

At twelve bits the whole colouring falls out in a fraction of a second, and the blind test above becomes trivial: brute-force both transcripts, and the one that unpacks into a genuinely proper colouring was the real one. At 128 bits the same attack is the same attack. It is only the number of tries that changed, and the number of tries is the security.

That is the precise content of the word computational. A perfectly hiding commitment would leak nothing even to an adversary with unbounded time. A hash-based one leaks everything to such an adversary, and nothing to any adversary that has to finish. Every practical zero-knowledge proof in the world sits on that distinction.

Movement VII

Catching a liar, and how long it takes

Everything so far assumed the prover was honest. Now watch one that cannot be. This is the Grötzsch graph: eleven vertices, twenty edges, no triangle anywhere in it, and it cannot be three-coloured. The page checked all 177,147 possible assignments a moment ago and found zero that work. It needs four colours, and Chvátal proved in 1974 that it is the unique smallest triangle-free graph that does.

A prover who claims to three-colour it is lying, necessarily. The best it can do is commit to the least-bad assignment there is, which leaves exactly one broken edge out of twenty. (There are 660 ways to achieve that, and none better.) So every round it survives with probability 19/20, and the bound is not just a bound here, it is exactly tight.

One run tells you very little, which is the honest problem with anecdotes about probability. So run it two thousand times and look at the shape.

Movement VIII

Why anyone builds these

The obvious use is the one you would guess: proving you know a password without sending it, proving a transaction is valid without publishing who paid whom. Zcash has had shielded transactions on that basis since 2016, built on a much later descendant of this idea rather than on this protocol itself.

That descendant earns a paragraph here, because it comes with its own honest failure. On 1 March 2018 a cryptographer at the Zcash company found that the parameter setup described in the paper their proving system was built on generated extra elements that broke soundness: anyone holding the transcript of the setup ceremony could have manufactured false proofs and counterfeited shielded coins undetectably. It was fixed by the network upgrade of 28 October 2018 and disclosed the following February. The company's own account is careful in exactly the way this page is trying to be. They believe no counterfeiting occurred; they also note that a system which hides amounts is a system that cannot easily prove none happened. Note also which half broke. Zero-knowledge held throughout, and would have held even against a subverted ceremony. It was the soundness that failed, which is the recurring lesson: the two halves of a proof system fail separately, and the one that fails quietly is not the one people worry about.

The use that stays with me is stranger. In 2014 Alexander Glaser, Boaz Barak and Robert Goldston published a zero-knowledge protocol for nuclear warhead verification: how an inspector confirms that the object in front of them is a genuine warhead of the declared type, without learning anything about its internal design, which is the exact secret no state will surrender and the exact obstacle that has stalled warhead-level arms control for decades.

The shape is the one you have been running. The candidate is interrogated with 14 MeV neutrons and compared against a trusted template item, recorded on detectors that hold no electronics and no memory. The classified image is never measured, because the host supplies detector boards preloaded with the negative of the expected signal, drawn from a Poisson distribution chosen so that preload plus measurement comes out Poisson with a mean both sides agreed in advance. That distribution is the same for every valid item, so the inspector's data could have been produced with no warhead in the room at all, which is the simulator argument made physical. Soundness comes from the inspector rather than the host: it is the inspector who decides at random which preloaded board goes with which item, so a cheating host is caught with substantial probability per round, much as a bluffer here is caught by an edge they did not expect. The 2014 paper established this in Monte Carlo simulation on an unclassified test object; the physical demonstration followed in 2016.

Same shape. Arrange the world so that the only thing you can observe is the answer to the question you asked, and so that the observation would have looked identical for every secret consistent with that answer.