TY - GEN
T1 - Bulletproofs
T2 - 39th IEEE Symposium on Security and Privacy, SP 2018
AU - Bunz, Benedikt
AU - Bootle, Jonathan
AU - Boneh, Dan
AU - Poelstra, Andrew
AU - Wuille, Pieter
AU - Maxwell, Greg
N1 - Funding Information:
We thank Shashank Agrawal for coming up with the Bulletproof name (short like a bullet with bulletproof security assumptions). We thank Peter Dettmann for pointing out the batch inversion trick. We thank Sean Bowe for various optimizations applicable to arithmetic circuits for Pedersen hash functions. Further we thank Philip Hayes and the anonymous reviewers for helpful corrections. This work was supported by NSF, DARPA, a grant from ONR, and the Simons Foundation.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/23
Y1 - 2018/7/23
N2 - We propose Bulletproofs, a new non-interactive zero-knowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values: they enable proving that a committed value is in a range using only 2 log2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n. Bulletproofs greatly improve on the linear (in n) sized range proofs in existing proposals for confidential transactions in Bitcoin and other cryptocurrencies. Moreover, Bulletproofs supports aggregation of range proofs, so that a party can prove that m commitments lie in a given range by providing only an additive O(log(m)) group elements over the length of a single proof. To aggregate proofs from multiple parties, we enable the parties to generate a single proof without revealing their inputs to each other via a simple multi-party computation (MPC) protocol for constructing Bulletproofs. This MPC protocol uses either a constant number of rounds and linear communication, or a logarithmic number of rounds and logarithmic communication. We show that verification time, while asymptotically linear, is very efficient in practice. The marginal cost of batch verifying 32 aggregated range proofs is less than the cost of verifying 32 ECDSA signatures. Bulletproofs build on the techniques of Bootle et al. (EUROCRYPT 2016). Beyond range proofs, Bulletproofs provide short zero-knowledge proofs for general arithmetic circuits while only relying on the discrete logarithm assumption and without requiring a trusted setup. We discuss many applications that would benefit from Bulletproofs, primarily in the area of cryptocurrencies. The efficiency of Bulletproofs is particularly well suited for the distributed and trustless nature of blockchains. The full version of this article is available on ePrint.
AB - We propose Bulletproofs, a new non-interactive zero-knowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values: they enable proving that a committed value is in a range using only 2 log2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n. Bulletproofs greatly improve on the linear (in n) sized range proofs in existing proposals for confidential transactions in Bitcoin and other cryptocurrencies. Moreover, Bulletproofs supports aggregation of range proofs, so that a party can prove that m commitments lie in a given range by providing only an additive O(log(m)) group elements over the length of a single proof. To aggregate proofs from multiple parties, we enable the parties to generate a single proof without revealing their inputs to each other via a simple multi-party computation (MPC) protocol for constructing Bulletproofs. This MPC protocol uses either a constant number of rounds and linear communication, or a logarithmic number of rounds and logarithmic communication. We show that verification time, while asymptotically linear, is very efficient in practice. The marginal cost of batch verifying 32 aggregated range proofs is less than the cost of verifying 32 ECDSA signatures. Bulletproofs build on the techniques of Bootle et al. (EUROCRYPT 2016). Beyond range proofs, Bulletproofs provide short zero-knowledge proofs for general arithmetic circuits while only relying on the discrete logarithm assumption and without requiring a trusted setup. We discuss many applications that would benefit from Bulletproofs, primarily in the area of cryptocurrencies. The efficiency of Bulletproofs is particularly well suited for the distributed and trustless nature of blockchains. The full version of this article is available on ePrint.
KW - Bitcoin
KW - Blockchain
KW - confidential transactions
KW - privacy
KW - Zero Knowledge proof of knowledge
UR - http://www.scopus.com/inward/record.url?scp=85051036417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85051036417&partnerID=8YFLogxK
U2 - 10.1109/SP.2018.00020
DO - 10.1109/SP.2018.00020
M3 - Conference contribution
AN - SCOPUS:85051036417
T3 - Proceedings - IEEE Symposium on Security and Privacy
SP - 315
EP - 334
BT - Proceedings - 2018 IEEE Symposium on Security and Privacy, SP 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 21 May 2018 through 23 May 2018
ER -