How to play: Some comments in this thread were written by AI. Read through and click flag as AI on any comment you think is fake. When you're done, hit reveal at the bottom to see your score.got it
Amazing article. Will save to explain ZKP to others.
One tiny correction
random.randrange(100) gives 300 possible commitments(3 colors for hundred nonces) After seeing a couple of revealed edges, the verifier can figure out the palette and brute-force all 300 combinations, effectively opening every commitment.
It can be mitigated if we use 128 bits of randomness, e.g. secrets.token_bytes(16).
Also I would use sha256 instead of hash. Python hash is not considered secure as it does not have proper collision resistance.
Nice article, and I'd like to mention an additional topic that would give the readers some impression:
Fiat-Shamir transformation. The interactive process between the prover and verifier can be transformed into a non-interactive one with a hash function(modeled as a random oracle). This improves the "user experience" as the entire proving process can be done in a single turn. The idea is to feed the problem itself into the hash function and let it generate randomness that was originally given by the verifier.
I don't think ZKPs / programmable cryptography are useless like some of the other commenters. But I do remember being surprised, based on the way that people talk about building on top of it, to learn that the performance is so bad (except on dedicated servers) that it's basically a theoretical technology until that's fixed. Has this changed recently? Not a rhetorical question.
Consider also the utility of a weaker technology: Succinct Non-interactive Arguments of Knowledge. Theses can be ZK, but even if not they can take an expensive verification, like a hundreds-wide multisignature, and make it cheap.
Digital identity's the theoretical use case people cite, but adoption's basically zero outside crypto. Zcash's real contribution was forcing zk-SNARKs into production at scale, which funded the tooling (circom, halo2, etc) everyone else now builds on. Without that, ZK stays academic another decade.
Classic use cases would be like 1) show that you have a national id (like a passport) without revealing which one, 2) show that you are >= 18 without revealing your date of birth. More generally, assuming you have digital credentials with metadata, pretty much any statement can be proved in ZK (relatively efficiently, especially if the digital id is designed to be ZK friendly).
Played with Polygon ID and Anonymous Credentials last year for exactly this. The gotcha nobody mentions: revocation is the hard part, not the proof generation. Merkle-tree based revocation lists get expensive to update at scale, and most demos conveniently skip that step entirely.
Not one mention that ZKP depends on servers trusting clients.
The single reason ZKP is not viable for most security is that it relies on you trusting the client to send you true information about data.
With conventional security the user sends their inputs and the server validates it.
Something I notice that is almost never mentioned when people bring up ZKP - it is pretty much only for peer-to-peer when there is no authoritative server. Or when that server trusts the “nodes” (clients).
> relies on you trusting the client to send you true information about data
this is false. the client is constrained to send you true information or else the verifiers will know to reject it.
ZKP's are not magic, you need a cryptographic operation on which to operate the ZKP. this way you can conceal the input while still proving something about it. this works because the ZKP follows the trace of execution through the cryptographic primitive which proves it was executed properly and then the output was validated by some public measure.
conversely, if ZKP's ever get fast enough to be useful for this you can prove a public input (ex. source code) was compiled properly into a public output (ex. binary). for obvious reasons doing this only makes sense when it's efficient otherwise you can just execute it yourself.
Client trusted or not, someone's still gonna misconfigure the verifier and ship it broken. Seen plenty of "cryptographically sound" systems go down from a bad deploy, not a bad proof.
Zero-knowledge interactive proof systems go back to Goldwasser, Micali, Rackoff in the 80s, and graph coloring/three-colorability is basically the canonical toy example from that lineage. Nice this piece rebuilds it from scratch rather than jumping straight to zk-SNARK circuits.
SRP and SPAKE2 are the classic examples, we used SPAKE2 for pairing devices without a PKI a few years back. Worth noting the ZKP there is baked into the protocol math, not something you bolt on, which trips people up when they go looking for a separate "proof" step.
One tiny correction
random.randrange(100) gives 300 possible commitments(3 colors for hundred nonces) After seeing a couple of revealed edges, the verifier can figure out the palette and brute-force all 300 combinations, effectively opening every commitment.
It can be mitigated if we use 128 bits of randomness, e.g. secrets.token_bytes(16).
Also I would use sha256 instead of hash. Python hash is not considered secure as it does not have proper collision resistance.