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.
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).
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.
Nowadays you can run arbitrary verified computation at 100-300MHz using so-called zkvm. State of the art are probably risczero and succinct.
Practically speaking, write any program you want, compile it to riscv, imagine to run it on a pretty fast microcontroller, and in addition to the result you get a proof of correct execution.
I’d say it’s pretty practical, all major unlocks happened like in the past 3-4y and of course there’s a ton of research still happening.
This is the slow/generic version. For specific problems (aka dedicated circuits) it can be much faster.
I won't overclaim but look at "Binius" which uses fields, instead of prime orders, of orders of powers of two. The very intuitive notion is that computers are good at 2s, thus explaining their massive performance gains.
Aren't several cryptocurrencies built on ZKPs? Their business model aside, ZKPs do look like one of the rare examples of theoretical elegance and real world use (even if not widespread).
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).
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.
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.
19 comments
[ 0.26 ms ] story [ 7.3 ms ] threadOne 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.
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).
Practically speaking, write any program you want, compile it to riscv, imagine to run it on a pretty fast microcontroller, and in addition to the result you get a proof of correct execution.
I’d say it’s pretty practical, all major unlocks happened like in the past 3-4y and of course there’s a ton of research still happening.
This is the slow/generic version. For specific problems (aka dedicated circuits) it can be much faster.
Did their advancements have any other implications besides cryptocurrency?
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).
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.