The unintuitive power of zero-knowledge proofs

It’s sometimes difficult for someone who doesn’t have a zero-knowledge proof background to see the power and usefulness of this concept. And that’s not surprising, as zero-knowledge proofs were discovered only in 1985 (Goldwasser, Micali, and Rackoff), 80 years after special relativity was discovered. If the concept were easy to grasp and its usefulness easy to see, it would have been discovered before.

In the case of media authenticity and, more specifically, in the case of proving what edits you made to a photo or video, the story goes as follows. You have a photo, but for some reason you don’t want to use it without some modifications. Let’s say this modification is a redaction: you want to hide some person on it.

So, you have an original photo that was signed in the camera, and you are now editing the photo on your computer.

But the camera signed the original pixels, not the redacted ones. The moment you cover the face, the signature no longer matches what you are about to publish, and the reader is back where they started: they have to take your word that you only covered the face and did not touch anything else. This is the problem the proof solves.

In a zero-knowledge proof, those original pixels are the witness: you prove facts about them without showing them. In our example, we only really care that one rectangle of the photo remains a mystery.

But what are the facts about the original pixels that we want to prove? Two things. We want to prove that the signature of the witness is some particular value: the signature produced by the camera. And we want to prove that when you apply the declared edit to the witness, you get the photo you published. Or equivalently, that the published pixels hash to a value that the reader can compute by themselves by running a hash function over the published photo.

The editor on this site enables you to do some simple edits and to generate the proof. Note that the proof generation is a time- and memory-consuming process, so there are some tricks to make it more efficient. Loading the whole photo into memory and proving it in one go would be too heavy, so what the editor does (the underlying technique was discovered and published in Eva) is splitting the photo into tiles, processing a small group of them, mixing the result into a running claim, then the next group, and so on: four tiles at a time, 16×16 pixels each. The picture below shows where it currently is: cyan marks the tiles being processed now, green marks the ones already mixed in.

When the last group is mixed in, the editor wraps the running claim into a short proof. The photo and the proof can then be downloaded and published together on some website, and the reader who visits it verifies the proof, which is a much faster operation than proving. What the reader’s checker runs on is the camera signature, the declared edit, the published photo, and the proof. The original never leaves the prover.

The surprising part is that the reader checks all of this against a photo they never see. They know nothing about the original except the two facts that were proven. In this particular example, most of the photo stays the same in the process of editing, so the reader does learn what the photo is outside of the rectangle, but that is a property of the redaction, not of the proof. There are many scenarios where the witness remains totally hidden. For example, from a digital ID you can prove that someone is over 18 without ever showing the ID.

The funny thing is that zero-knowledge proofs were discovered when Goldwasser and Micali (then Berkeley students) were working on playing poker over the phone. It started as a fun project that turned into something much bigger.