A quick look at zero-knowledge proofs
bernsteinbear.com
bernsteinbear.com
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.
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.
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?
It's a little bit funny to me. I can understand a response of "Hmm, while your application of cryptography may have some legitimate uses, in practice it seems like it's largely used for crime and scams." But I wonder what they thought the primary application of cryptography was going to me! Privacy-preserving technologies that allow you to hide from the government are necessarily going to be useful to criminals. But that's the price of freedom, no?
(I guess to be fair, some cryptographers might be interested in things like privacy-preserving voting, which wouldn't ever be useful to criminals.)
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).
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
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.
This doesn’t mean the input is “true” though. I can send some zkp that says I’m at least 18 or that I have at least $1M in my bank account, but it doesn’t mean that I actually am or do. Or am I missing something?
if you want to do it without a third party you end up with something like zcash. monero plans to follow suit (currently only the amounts in monero are zero knowledge).
Or you can make it for remote programming job. Create a zk proof of codes he has worked on. And apply to HR so hr doesnt have to waste time on due diligence or mess with nda to look at private code base, few devs have public code. Zk makes, cross institute as an online service more efficient.
A non-augmented ZKPP protects the password from eavesdroppers, but the server's verifier is a password-equivalent (though it isn't the password, just a one-way function of it).
A ZKPP is the simplest ZKP application, but others work similarly.
In other words: you're missing everything about ZKPs.
This setting is generally "proof of attribute" or "proof of group membership" although in practice it is most often more like "proof of possession of a credential". An interesting example demonstrated a few years ago is that you could prove that you possess a passport from a certain country without revealing anything else about your identity (as the passports are digitally signed by their issuing authorities using publicly-known keys). You could then have, for example, an online forum or poll that only allows participation of people with a certain credential, yet the forum or poll operator never learns the offline identities of the members or participants.
There are some logistical issues with this depending on the purpose for which the verifier is relying on the statement, including what happens if a prover submits the same credential twice, and what happens if a prover borrows a credential from someone else. In some settings this is OK or unlikely, while in other settings it might effectively blow up the whole application!
the nullifier can then be your cryptographic identity as a member of some group. without disclosing the actual member.
it will likely be some time before such structures see use.
imagine a physical meeting between 1000 people and they all exchange some random-seeming string (prepared ahead of time), then they join a special group chat where they know there can only be 1000 members and each one corresponds to someone who was present in the meeting. but unless they out themselves (or everyone else does) they will never know who is who. and yet the group chat can be entirely p2p and no one can cheat. and there could be spy cameras watching every exchange in the meeting and all the exchanged notes and it wouldn't matter.
that way that works is by using a ZKP to prove that a previously secret but now disclosed nullifier string is a cryptographic relation to one member of the sorted list of all the exchanged strings in the meeting. and the nullifier happens to be a public key hash.
something is fishy in this comment section.