Zero-Knowledge Proofs Without Crypto: A 30-Line Implementation
A quick look at zero-knowledge proofs
A developer explores zero-knowledge proofs through the classic graph 3-coloring problem, implementing a simple interactive proof in Python. The post walks through the protocol from a 1986 paper, explains the importance of nonces and hashing, and provides a live networked demo. It's a hands-on introduction that avoids cryptocurrency entirely, focusing on the graph theory and the elegance of the concept.
The idea of a zero-knowledge proof (ZKP) is that there are two parties: the prover and the verifier. The prover asserts that it has a solution to a (generally NP-complete) problem. The prover can convince the verifier of this without sharing the actual solution to the problem.
- _alphageek
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.
- jackb4040
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.
- Cider9986
Zcash make a significant contro to ZKPs though, what would be the state without their tec?
Did their advancements have any other implications besides cryptocurrency?
- diamondclouds
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).