Rendered at 15:29:54 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
_alphageek 16 hours ago [-]
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.
namjh 10 hours ago [-]
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.
jackb4040 14 hours ago [-]
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.
ecesena 12 hours ago [-]
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.
greenhillx 11 hours ago [-]
[dead]
mw888 10 hours ago [-]
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.
schoen 14 hours ago [-]
There's a big asymmetry where creating a proof is usually dramatically more expensive than verifying it (which is often extremely cheap!). That might be OK for some applications but still rule out other applications.
mw888 10 hours ago [-]
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.
10 hours ago [-]
Cider9986 14 hours ago [-]
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?
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).
ChadNauseam 12 hours ago [-]
Zcash and many other cryptocurrency-related projects. The amount of cryptographers working on zero-knowledge proofs probably multiplied 10x thanks to cryptocurrencies.
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.)
Funny that not only are you ignorant you are violently confident in your ignorance. I suffer from this sometimes too so I get it. Get some help.
diamondclouds 15 hours ago [-]
> Alice sends out
It relies on trusting that Alice’s request is valid. If Alice sends another proof, she will have a different balance. Alice decides what to send. The server blindly accepts it.
You actually don’t want that for a lot of security and that’s why nobody uses ZKP for passwords or really anywhere outside theory - dumb theory that doesn’t understand basic web dev. We already have hashing and databases. There is a narrow use case for trusting clients - like receiving updates from intranet or p2p devices - maybe you use ZKP to omit unnecessary pii. But that’s it. It’s not what you think it is.
Groxx 15 hours ago [-]
> Alice sends out
Alice can send anything in any cryptographic scheme involving two parties, the only real safety in any of it is "are the odds of an accepted different value low enough to be impractical for an attacker". Does that apply here too?
rubyclouds 13 hours ago [-]
What? Of course it’s a massive security flaw if you let any end user device send anything they want and just go “well they probably won’t send fake amounts”
Imagine such a bank. Or social media (impersonate anyone, just say you’re them on the request why not), or any website.
The “zero knowledge” part of the name checks out.
nojokepoke 14 hours ago [-]
Please explain how Alice’s request can ever be not valid. It’s literally a pre authenticated exchange.
Also nice sock puppet.
rubyclouds 13 hours ago [-]
[dead]
diamondclouds 15 hours ago [-]
It has a use case in peer-to-peer or anywhere that you want the server to trust the connections.
Sometimes you want clients to be authoritative (although rare).
Retr0id 16 hours ago [-]
A great way to announce that you don't understand ZKP
goldthreads 16 hours ago [-]
Explain why you need ZKP for their flagship problem - the “prove you’re 21” thing.
Or choose any case you like.
Explain why I can’t do it without this hilariously elementary philosophy detached from real world dev.
No cheating! I get access to the same resources. Explain why I need ZKP.
striking 15 hours ago [-]
I think the fine article says it best when it says
> After doing a bit of research, we decided that the most common real world use cases of zero-knowledge proofs (age verification, crypto, etc) aren’t particularly interesting to us. We enjoyed the graphs and theory of computation and networked computing though. We hope you had fun playing around with interactive proofs too.
The inclusion of this statement makes your comments look rather bizarre and strangely combative by comparison. Maybe we can just enjoy a bit of math together?
Retr0id 15 hours ago [-]
I actually don't think ZKPs solve the age verification problem (for a variety of reasons that won't fit here), but they solve plenty of more interesting problems. Private transactions in Zcash, for example.
diamondclouds 15 hours ago [-]
Only because zcash trusts the sending node - whoever is hosting that ledger.
If they had no clue who it was, like the typical http web, they could not allow a sender to be a prover, since they would not be able to verify their balance. At some point a balance inquiry would have to reveal who they are. It only works if you trust the banker.
Or by being a middleman. You send [payment service] the money and they send it to the recipient, hiding your info.
Ar-Curunir 14 hours ago [-]
Yes, they just hand out Turing Awards for bullshit.
rubyclouds 13 hours ago [-]
[dead]
yellowkitex 11 hours ago [-]
[flagged]
yellowkitex 12 hours ago [-]
[dead]
yellowkitex 12 hours ago [-]
[flagged]
akoboldfrying 11 hours ago [-]
> are you fucking stupid unable to think for yourself??
I was about to write you off as ignorant and unhinged, but then you wrote this, which persuaded me that you were right all along
windingpath 11 hours ago [-]
ZKPs verify statements about data, not the authenticity of the data source itself.
diamondclouds 15 hours ago [-]
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).
teravor 15 hours ago [-]
> 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.
what 12 hours ago [-]
> this way you can conceal the input while still proving something about it
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?
schoen 10 hours ago [-]
You can prove that you possess a digital signature from some authority over a statement that says that you are 18 or that you have $1,000,000. However, you don't have to reveal that actual statement or signature. Typically, that would be because the statement contains your offline identity and you don't want to reveal that to the verifier.
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!
teravor 10 hours ago [-]
in that scenario you can obtain a nullifier which serves as your identifier but prevents you from generating a new one without another valid passport.
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.
cryptonector 11 hours ago [-]
Consider ZK password proof protocol: at enrollment (password set / change) the server -or a third party it trusts- knows the password and computes a verifier, while at login time the server uses the verifier to validate that the client knows the password but without the client revealing the password to the server. The client could perhaps have found an alternative password that matches the same verifier, but the ZKPP's security characteristics are supposed to make that exceedingly difficult. Meanwhile, the ZKPP is also supposed to make it exceedingly difficult to recover the password from a ZKPP exchange that any eavesdropper could record.
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.
ctdinjeu99 10 hours ago [-]
LOL
This guy has like 11k rep here.
We're cooked boys
ahmetson 12 hours ago [-]
But it’s not working that way, there is a third party like attestation that provides the data to client to generate zk proof
what 11 hours ago [-]
Then just ask the third party?
teravor 10 hours ago [-]
a third party can voluntarily surrender complete control over what is going on. they can issue a token for something, for example a $10 dollar bill but do it in such a way (blind signature) that when you go to spend it they cannot connect the spend to the bill they issued.
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).
Nursie 11 hours ago [-]
That can leak information to the third party that you may not want them to know.
ctdinjeu99 10 hours ago [-]
...
diamondclouds 14 hours ago [-]
> the client is constrained to send you true information
Yeah ok bud. You wouldn’t last a week.
Ar-Curunir 14 hours ago [-]
What is your envisaged application? ZKPs give you integrity guarantees which prevent malicious behaviour.
teravor 12 hours ago [-]
there is a dead comment below yours, these new accounts (weird?) seem convinced that a prover needs to be trusted. but if you trust the prover why would you need a proof? nevermind the fact that they are entirely mistaken it doesn't even make sense what they are alleging.
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?
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).
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.)
Funny that not only are you ignorant you are violently confident in your ignorance. I suffer from this sometimes too so I get it. Get some help.
It relies on trusting that Alice’s request is valid. If Alice sends another proof, she will have a different balance. Alice decides what to send. The server blindly accepts it.
You actually don’t want that for a lot of security and that’s why nobody uses ZKP for passwords or really anywhere outside theory - dumb theory that doesn’t understand basic web dev. We already have hashing and databases. There is a narrow use case for trusting clients - like receiving updates from intranet or p2p devices - maybe you use ZKP to omit unnecessary pii. But that’s it. It’s not what you think it is.
Alice can send anything in any cryptographic scheme involving two parties, the only real safety in any of it is "are the odds of an accepted different value low enough to be impractical for an attacker". Does that apply here too?
Imagine such a bank. Or social media (impersonate anyone, just say you’re them on the request why not), or any website.
The “zero knowledge” part of the name checks out.
Also nice sock puppet.
Sometimes you want clients to be authoritative (although rare).
Or choose any case you like.
Explain why I can’t do it without this hilariously elementary philosophy detached from real world dev.
No cheating! I get access to the same resources. Explain why I need ZKP.
> After doing a bit of research, we decided that the most common real world use cases of zero-knowledge proofs (age verification, crypto, etc) aren’t particularly interesting to us. We enjoyed the graphs and theory of computation and networked computing though. We hope you had fun playing around with interactive proofs too.
The inclusion of this statement makes your comments look rather bizarre and strangely combative by comparison. Maybe we can just enjoy a bit of math together?
If they had no clue who it was, like the typical http web, they could not allow a sender to be a prover, since they would not be able to verify their balance. At some point a balance inquiry would have to reveal who they are. It only works if you trust the banker.
Or by being a middleman. You send [payment service] the money and they send it to the recipient, hiding your info.
I was about to write you off as ignorant and unhinged, but then you wrote this, which persuaded me that you were right all along
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).
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?
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.
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 guy has like 11k rep here.
We're cooked boys
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).
Yeah ok bud. You wouldn’t last a week.
something is fishy in this comment section.