7 ms·

Bulletproofs – Short zero-knowledge arguments of knowledge

185 points by rwosync 8y ago

coolspot 8y ago
See also original Blockstream paper (pdf): https://eprint.iacr.org/2017/1066.pdf https://eprint.iacr.org/2017/1066.pdf
- Ar-Curunir 8y ago
  The primary innovations are not really from the Blockstream folks, but from the graduate students involved: Benedikt and Jonathan
- relyio 8y ago
  More UCL and Stanford but okay
dbranes 8y ago
Tangent: I like that the logo for the organization 'adjoint' resembles the notation for adjoint functors.
- darkkindness 8y ago
  Likewise! Looks like it was intentional: > 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 https://www.adjoint.io/about/adjoint)
  - dtseng123 8y ago
    It was very intentional.
  - tobbe2064 8y ago
    Just out of curiosity, do you actually use adjunctions? If so I would be really happy to know more about it.
  - dbranes 8y ago
    Ugh, I'm cringing a little that they consider adjunctions 'advanced mathematics'. Adjunctions are ubiquitous even in elementary math. For example, in linear algebra whenever one writes down a matrix to represent a operator in some basis, this is using the tensor-hom adjunctions for modules.
jlrubin 8y ago
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)
- infogulch 8y ago
  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?
  - askmike 8y ago
    I don't think this will ever be hardforked into bitcoin, but there are other ways of getting this in, such as via sidechains (see liquid[1] for example). [1] https://blockstream.com/liquid/ https://blockstream.com/liquid/
  - zodiac 8y ago
    Well, the verification guarantees you want out of a public ledger for currency are weaker than that (no money is created out of thin air, the person you're receiving money from actually has enough money to send to you, etc). I'm not sure anyone is philosophically attached to "all balances are visible".
    - infogulch 8y ago
      Ok yes, in a single transaction you can prove to everyone else that the net exchange is zero, but how do you prove that you have enough money to send to them? That's global state that depends on all past transactions, even if they're hidden. Include more ZKPs for every transaction ever associated with that address? You have to prove that 1. you received enough to cover it and 2. you haven't spent it already. Just slapping some ZKP on top of bitcoin is not enough to make it magically private. It needs deeper integration to the model than that.
hackathonguy 8y ago
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. :-) [1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_Baba_cave https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B... [2] http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf
- AstralStorm 8y ago
  By that you mean someone wake who also found Waldo can verify if the shape matched. 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.
  - pas 8y ago
    Maybe you can show only Waldo's face?
    - tomaha 8y ago
      The Waldo zk proof isn't a good example. You can easily fake knowing where Waldo is by gluing a Waldo to the board you use to hide the book. That way you can even proof you know a solution for a picture that doesn't even have Waldo in it.
      - hackathonguy 8y ago
        This can easily be remedied by having the verifier ensure the prover is in an empty room, equipped with only cardboard and scissors.
arisAlexis 8y ago
for those who don't know, Monero is using bulletproofs.
- Expez 8y ago
  Not yet. 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.
mehrdadn 8y ago
> 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).
- zodiac 8y ago
  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. One thing I found useful is section 2.2 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf, on blinding in RSA.
  - mehrdadn 8y ago
    Interesting, thanks!
deleted 8y ago
[deleted]
dtseng123 8y ago
More about bulletproof in context of Uplink. https://www.adjoint.io/docs/privacy.html#upperlink https://www.adjoint.io/docs/privacy.html#upperlink
cdecker 8y ago
There is also an implementation by Andrew Poelstra (one of the Bulletproof authors) in a PR to the secp256k1-zkp repository: https://github.com/ElementsProject/secp256k1-zkp/pull/23 https://github.com/ElementsProject/secp256k1-zkp/pull/23
MrXOR 8y ago
What is difference between Bulletproof and zk-SNARK (of ZCash)? Any advantage?

185 points by rwosync 8y ago

coolspot 8y ago

See also original Blockstream paper (pdf): https://eprint.iacr.org/2017/1066.pdf https://eprint.iacr.org/2017/1066.pdf

Ar-Curunir 8y ago
The primary innovations are not really from the Blockstream folks, but from the graduate students involved: Benedikt and Jonathan
relyio 8y ago
More UCL and Stanford but okay

dbranes 8y ago

Tangent: I like that the logo for the organization 'adjoint' resembles the notation for adjoint functors.

darkkindness 8y ago
Likewise! Looks like it was intentional: > 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 https://www.adjoint.io/about/adjoint)
- dtseng123 8y ago
  It was very intentional.
- tobbe2064 8y ago
  Just out of curiosity, do you actually use adjunctions? If so I would be really happy to know more about it.
- dbranes 8y ago
  Ugh, I'm cringing a little that they consider adjunctions 'advanced mathematics'. Adjunctions are ubiquitous even in elementary math. For example, in linear algebra whenever one writes down a matrix to represent a operator in some basis, this is using the tensor-hom adjunctions for modules.

jlrubin 8y ago

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)

infogulch 8y ago
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?
- askmike 8y ago
  I don't think this will ever be hardforked into bitcoin, but there are other ways of getting this in, such as via sidechains (see liquid[1] for example). [1] https://blockstream.com/liquid/ https://blockstream.com/liquid/
- zodiac 8y ago
  Well, the verification guarantees you want out of a public ledger for currency are weaker than that (no money is created out of thin air, the person you're receiving money from actually has enough money to send to you, etc). I'm not sure anyone is philosophically attached to "all balances are visible".
  - infogulch 8y ago
    Ok yes, in a single transaction you can prove to everyone else that the net exchange is zero, but how do you prove that you have enough money to send to them? That's global state that depends on all past transactions, even if they're hidden. Include more ZKPs for every transaction ever associated with that address? You have to prove that 1. you received enough to cover it and 2. you haven't spent it already. Just slapping some ZKP on top of bitcoin is not enough to make it magically private. It needs deeper integration to the model than that.

hackathonguy 8y ago

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. :-) [1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_Baba_cave https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B... [2] http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf

AstralStorm 8y ago
By that you mean someone wake who also found Waldo can verify if the shape matched. 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.
- pas 8y ago
  Maybe you can show only Waldo's face?
  - tomaha 8y ago
    The Waldo zk proof isn't a good example. You can easily fake knowing where Waldo is by gluing a Waldo to the board you use to hide the book. That way you can even proof you know a solution for a picture that doesn't even have Waldo in it.
    - hackathonguy 8y ago
      This can easily be remedied by having the verifier ensure the prover is in an empty room, equipped with only cardboard and scissors.

arisAlexis 8y ago

for those who don't know, Monero is using bulletproofs.

Expez 8y ago
Not yet. 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.

mehrdadn 8y ago

> 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).

zodiac 8y ago
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. One thing I found useful is section 2.2 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf, on blinding in RSA.
- mehrdadn 8y ago
  Interesting, thanks!

deleted 8y ago

[deleted]

dtseng123 8y ago

More about bulletproof in context of Uplink. https://www.adjoint.io/docs/privacy.html#upperlink https://www.adjoint.io/docs/privacy.html#upperlink

cdecker 8y ago

There is also an implementation by Andrew Poelstra (one of the Bulletproof authors) in a PR to the secp256k1-zkp repository: https://github.com/ElementsProject/secp256k1-zkp/pull/23 https://github.com/ElementsProject/secp256k1-zkp/pull/23

MrXOR 8y ago

What is difference between Bulletproof and zk-SNARK (of ZCash)? Any advantage?