Zero knowledge proofs are fascinating - as a non-mathematician, I particularly enjoy real-world examples.
Two famous examples ("The Ali Baba Cave" and the "Two Balls and the Color Blind Friend") appear in the Wikipedia article on zero knowledge proofs [1].
My favorite, however, is this paper [2] on convincing another person you've found Waldo, without revealing his location and therefore ruining the game. It's extraordinarily simple: take a piece of cardboard larger than the Where's Waldo book, make a small, Waldo-sized cutout, and position the cardboard in a way that only Waldo himself is visible. As long as you don't give away the position of the book underneath the cardboard, you can prove you've found Waldo without providing _any_ information as to where he is! It's pretty great.
Would love to know of other real world examples. :-)
I also really love the Waldo example, and give it often. Just FYI (as noted by SilasX in other comments), this is not officially a Zero Knowledge proof, since you're "proving too much" (people who are not the verifier will "know that you know", which is not allowed in ZKPs).
Btw, another favorite of mine which I often give as a riddle (not a ZKP, but an interactive proof): Assume I claim to have the superpower of knowing exactly how many leaves are on a tree just by looking at it. How can you verify this without actually having to count an entire tree's worth of leaves?
Just thought of another ZKP - my niece can prove to me that she knows the password to a device by logging in, without me ever knowing the password myself.
What am I missing about the Ali Baba cave proof? Why does Victor ever need to hide which entrance she takes at first? (In fact this is brought up in the last paragraph with no reason as to why it's not the entire proof).
Does Victor knowing the initial path make it non-zero-knowledge? Because if so, the example feels super contrived. I agree your Waldo example is much better.
Bulletproofs are significant because they allows you to check that the amount being input and output in a Bitcoin transaction is correct without revealing the amounts to non-parties to the transaction. The size of a bulletproof is small enough (and they grow with O(c + log n)) that for transactions with a couple inputs and outputs, there is minimal overhead compared to a unblinded transaction.
The link provided is to a relatively new library for doing bullet proofs written in Haskell -- the README might benefit from more disclaimer about the verification steps taken and analysis of side channels for the library (probably not ready for production)
In a Mimblewimble [1] blockchain, values are hidden inside Pedersen commitments, blind * G + value * H, and inputs can be seen to match outputs of a transaction if the latter minus the former is of the form blind*G (the difference in value is 0). But this form is a public key that the transactors can produce a signature for! This is way simpler than a bulletproof. BUT, bulletproofs are needed to show that the output values are in a certain range, to prevent overflow in value arithmetic.
How is that possible? Bitcoin's whole premise is a globally verifiable balance of each address after each block (aka public ledger). I could see this being very helpful for new crypto currencies, but Bitcoin is pretty set in stone on this matter, no?
> Our name comes from advanced mathematics and represents the numerous ways in which we simplify financial processes and products using blockchain technology.
> They rely on the discrete logarithmic assumption
> Range proofs do not leak any information about the secret value
Could someone explain this? I can't say I followed the proof algorithm (don't have background on blinded Pederson commitments etc.), but to me these sound contradictory. If you're relying on a discrete log assumption then it means you are leaking information, but you hope it's not enough information to reconstruct the secret. It doesn't sound like an algorithm that truly doesn't leak information (like OTP).
The does-not-leak-information property doesn't depend on the discrete log assumption, but the binding property does. I.e., if you have an oracle that solves the discrete log problem you can now open commitments in different ways, but if someone else generates a commitment you still can't tell what their secret input was.
A hard fork later this fall is expected to bring Bulletproofs to main net. Right now the code is being vetted by 3 external auditors, hired by the community through fund-raising.
The benefit to Monero, once this is implemented, is transactions that are almost an order of magnitude smaller. This is a huge win, for many reasons, and it doesn't even come at the cost of CPU time.
[+] [-] hackathonguy|7 years ago|reply
Two famous examples ("The Ali Baba Cave" and the "Two Balls and the Color Blind Friend") appear in the Wikipedia article on zero knowledge proofs [1].
My favorite, however, is this paper [2] on convincing another person you've found Waldo, without revealing his location and therefore ruining the game. It's extraordinarily simple: take a piece of cardboard larger than the Where's Waldo book, make a small, Waldo-sized cutout, and position the cardboard in a way that only Waldo himself is visible. As long as you don't give away the position of the book underneath the cardboard, you can prove you've found Waldo without providing _any_ information as to where he is! It's pretty great.
Would love to know of other real world examples. :-)
[1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B... [2] http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf
[+] [-] edanm|7 years ago|reply
Btw, another favorite of mine which I often give as a riddle (not a ZKP, but an interactive proof): Assume I claim to have the superpower of knowing exactly how many leaves are on a tree just by looking at it. How can you verify this without actually having to count an entire tree's worth of leaves?
[+] [-] AstralStorm|7 years ago|reply
It still slightly ruins the game as you know the shape you're looking for now.
This is why one way functions are used instead.
[+] [-] SilasX|7 years ago|reply
https://news.ycombinator.com/item?id=15323790
[+] [-] hackathonguy|7 years ago|reply
[+] [-] scrollaway|7 years ago|reply
Does Victor knowing the initial path make it non-zero-knowledge? Because if so, the example feels super contrived. I agree your Waldo example is much better.
[+] [-] visvavasu|7 years ago|reply
[+] [-] jlrubin|7 years ago|reply
The link provided is to a relatively new library for doing bullet proofs written in Haskell -- the README might benefit from more disclaimer about the verification steps taken and analysis of side channels for the library (probably not ready for production)
[+] [-] tromp|7 years ago|reply
[1] https://www.youtube.com/watch?v=BMiM0rabRjc
[+] [-] infogulch|7 years ago|reply
[+] [-] cdecker|7 years ago|reply
[+] [-] coolspot|7 years ago|reply
[+] [-] Ar-Curunir|7 years ago|reply
[+] [-] relyio|7 years ago|reply
[+] [-] dbranes|7 years ago|reply
[+] [-] darkkindness|7 years ago|reply
> Our name comes from advanced mathematics and represents the numerous ways in which we simplify financial processes and products using blockchain technology.
(https://www.adjoint.io/about/adjoint)
[+] [-] mehrdadn|7 years ago|reply
> Range proofs do not leak any information about the secret value
Could someone explain this? I can't say I followed the proof algorithm (don't have background on blinded Pederson commitments etc.), but to me these sound contradictory. If you're relying on a discrete log assumption then it means you are leaking information, but you hope it's not enough information to reconstruct the secret. It doesn't sound like an algorithm that truly doesn't leak information (like OTP).
[+] [-] zodiac|7 years ago|reply
One thing I found useful is section 2.2 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf, on blinding in RSA.
[+] [-] dtseng123|7 years ago|reply
[+] [-] unknown|7 years ago|reply
[deleted]
[+] [-] arisAlexis|7 years ago|reply
[+] [-] Expez|7 years ago|reply
A hard fork later this fall is expected to bring Bulletproofs to main net. Right now the code is being vetted by 3 external auditors, hired by the community through fund-raising.
The benefit to Monero, once this is implemented, is transactions that are almost an order of magnitude smaller. This is a huge win, for many reasons, and it doesn't even come at the cost of CPU time.
[+] [-] MrXOR|7 years ago|reply