Zero knowledge proofs are fascinating - as a non-mathematician, I particularly enjoy real-world examples.<p>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].<p>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.<p>Would love to know of other real world examples. :-)<p>[1] <a href="https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_Baba_cave" rel="nofollow">https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B...</a>
[2] <a href="http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf" rel="nofollow">http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf</a>
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.<p>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)
There is also an implementation by Andrew Poelstra (one of the Bulletproof authors) in a PR to the secp256k1-zkp repository: <a href="https://github.com/ElementsProject/secp256k1-zkp/pull/23" rel="nofollow">https://github.com/ElementsProject/secp256k1-zkp/pull/23</a>
See also original Blockstream paper (pdf): <a href="https://eprint.iacr.org/2017/1066.pdf" rel="nofollow">https://eprint.iacr.org/2017/1066.pdf</a>
> They rely on the discrete logarithmic assumption<p>> Range proofs do not leak any information about the secret value<p>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 <i>are</i> 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).
More about bulletproof in context of Uplink. <a href="https://www.adjoint.io/docs/privacy.html#upperlink" rel="nofollow">https://www.adjoint.io/docs/privacy.html#upperlink</a>