Zero-Knowledge Proofs
Transcript
Made automatically from the video's sound, so it may contain mistakes. Click a line to play from there.
Welcome back to The Explainer. Now, last time we looked at how Rust's compiler proves memory lifetime safety without ever inspecting runtime values. Well, today, in Arc 4, we're pushing mathematical proof to an absolute paradox.
We're diving deep into another hard problem in computing zero knowledge proofs. So, how exactly do you prove a secret statement is true without revealing a single bit of the secret itself? I mean, it sounds like literal magic, right?
Or just a massive contradiction, but I promise you it's pure maths. This question has puzzled computer scientists since the 1980s. How do you actually convince a massive sceptic that you hold a secret without just handing it over?
The zero knowledge paradox. To wrap our heads around this, we've got to strip away everything we intuitively think we know about data verification and go right back to first principles. You'll often see this explained using Jean-Jacques Cuisquata's famous Alibar Cave analogy.
But underneath all that, any valid zero knowledge system hinges on two absolutely crucial concepts. First up, completeness. This just means that if a statement is true, an honest prover is always gonna convince the verifier.
Always. Second, we have soundness. If the statement is completely false, the chance of a cheater successfully tricking the verifier is exponentially crushed out of existence across multiple rounds of interaction.
So true statements are always accepted, and false ones are mathematically obliterated. This whole concept sparked a massive new hope for authentication. Imagine servers that literally never learn your clear text password.
This seminal 1985 paper by Goldwasser, Mikhail, and Rakhoff really hit the nail on the head. They proved it is theoretically possible to build systems that provably reveal absolutely no information beyond a single bit of truth.
Basically, just a simple yes or no that the statement is valid, nothing else. Right, section two, the time rewinding simulator. Now, things are gonna get a little bit mind-bending here as we run through a thought experiment to prove that absolutely no knowledge is actually transferred.
The cryptographer Matthew Green illustrates this brilliantly with his time rewinding simulator on a three-colorable graph. So imagine you're not interacting with a person, but an actual computer program acting as a simulator trying to fake a proof.
The simulator spits out an initial guess, then, after seeing the verifier's challenge, it uses a virtual machine snapshot to literally rewind time on the verifier. By going back to the exact split second before the challenge was issued, the simulator obviously already knows what the verifier is going to ask, so it can just compute a perfectly valid response and completely fake a protocol run without knowing the actual secret at all.
And here is the kicker. Because a time rewinding simulator could fake the exact same transcript. A recorded transcript of this interaction is completely useless to a third party. It carries literally zero transferable knowledge.
If a judge looks at the record later, they have absolutely no way of knowing if it was generated by a genuine prover or just a rewound simulation. So we've proven that exactly zero information leaked. But how do we make this practical?
Well, outlined in RFC 8235, the Fiat Shamir heuristic is a real game changer. It elegantly transitions us from these clunky interactive loops to a single non interactive proof. How?
By replacing the verifier's challenge with a secure cryptographic hash function. The prover automatically gets their challenges by hashing certain inputs of the proof, which acts like a random oracle. Just like that, the entire multi-round interaction collapses into a single non-interactive zero knowledge proof, or N I Z K, that can be verified in a flash.
Snarks, Starks, and polynomials. Let's dig into the maths and see the modern engineering that makes these succinct proofs a reality. Now, you can't just feed raw application code straight into a zero knowledge prover.
That's not gonna work. First, the code has to flatten into arithmetic circuits, translating millions of computation steps into polynomial equations using formats like R1CS, Plonkish, or AIR. Because polynomials are these incredibly dense mathematical objects, a single equation between them can represent an unbounded number of computational checks.
This is huge because it means the verifier can securely check everything in a fraction of a second without inspecting millions of individual steps. So what are we actually using? Well, we have ZK snarks, which give you tiny constant size proofs that are incredibly cheap to verify, but they usually rely on pairing based cryptography, requiring a complex, trusted setup, like the powers of tau ceremony to destroy what we call the toxic waste.
Then you have ZK Starks. These eliminate the toxic waste risk entirely by using transparent post-quantum hash functions like FRI, zero trusted setup. But the trade-off is you have to handle significantly larger proof sizes.
And right in the middle, we have systems like Halo 2, which use transparent inner product commitments to perfectly balance these trade-offs. And if you think this is just theoretical moon maths, it's actually running on the devices in your pocket right now.
Google Wallet uses the Longfellow CK library to prove a user is over 18 over ISO compliant credentials, without ever revealing their exact date of birth. And Cloudflare is using zero knowledge proofs for private hardware key attestation, authenticating without exposing the underlying identity.
It's incredibly powerful stuff. The Vibe Coder Trap. Look, implementing this maths is an absolute minefield, especially for developers blindly asking AI to write privacy preserving authentication.
If you rely on AI to write your zero-knowledge architecture, you are practically guaranteed to fall into one of these three catastrophic, fundamentally broken hallucinations. Hallucination one, pass the hash client-side SHA256, which, spoiler alert, isn't zero knowledge at all.
Number two, broken do-it-yourself Fiat Shamir maths. And number three, underconstrained circuits. Let's unpack those last two, because honestly, they plague human engineers just as much as AI.
Take the frozen heart vulnerability, discovered by Trail of Bits. If you forget to include public inputs, like the Pedersen commitment in your Fiat Shamir transcript hash, you give malicious provers the mathematical freedom to fake their proofs entirely.
Because the challenge becomes totally independent of the commitment, a cheater can just blindly guess random values until they forge a successful proof. This completely compromises implementations in Giro, Bulletproofs, and Planck. Then we have Zero X Park's number one zero-knowledge exploit class, under constrained circuits.
This happens a lot in languages like Circom. If a developer uses a left-pointing arrow assignment operator to assign a witness, but forgets to strictly constrain it with the triple equals polynomial constraint operator, well, a cheater can input wildly out-of-bounds values, and the verifier will still accept the output because the circuit literally just forgot to check the rule.
It's a complete disaster. The judiciousness ladder. Given all these catastrophic risks, security architects desperately need a strict framework for when to actually deploy these advanced circuits.
In software engineering, YAGNI, you aren't gonna need it, is a core pragmatic rule. In cryptography, it's absolutely vital. It explicitly defines when not to use custom zero knowledge proofs. Frankly, you should exhaust literally every other standard option before you even think about writing a custom circuit.
Reaching for ZK too early is just inviting massive security risks. And that brings us to the five-rung cryptographic judiciousness ladder. On rung one, just stick to standard Web Auth NPAS keys, or TLS with Argon 2 ID for normal logins.
Simple. Rung two, if the server must never see the password, use an asymmetric protocol, like opaque. Rung three, client-side AES 256 GCM envelope encryption for unreadable cloud storage.
Rung four, SDJWT or BBS Plus for selective issuer claims. You only ever step up to rung 5, complex audited noir, Circum or Halo 2 circuits checked by static tools like CircomSpect, when you absolutely require third-party verification over private witnesses.
Well, that brings this explainer to a close, but it perfectly tees up our series finale. We'll be exploring what happens when algorithms simply cannot be proven to ever finish in the halting problem and undecidability.
Because as Zero Knowledge Proof pushes the absolute boundaries of verifiable truth today, we have to ask are we prepared for the ultimate limits of computing? Thanks for sticking with us, and we'll see you in the finale.