Bulletproofs: Short Proofs for Confidential Transactions and More
By Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Gregory Maxwell. 2018
1,327 citations recorded by the source corpus.
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 log_2(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.
Subfields: Artificial Intelligence, Information Systems, Privacy & Security, Mathematical Optimization
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Qiang Yang
- Martin Jaggi
- Jakub Konecný
- Srinath T. V. Setty
- Peter Richtárik
- Yang Liu
- Peter Kairouz
- Ananda Theertha Suresh
In Information Systems
- Srinath T. V. Setty
- Dan Boneh
- Markulf Kohlweiss
- Benedikt Bünz
- Michael Riabzev
- Sarah Meiklejohn
- Eli Ben-Sasson
- Ben Fisch
In Privacy & Security
- Peter Kairouz
- Srinath T. V. Setty
- Dan Boneh
- Badih Ghazi
- Rasmus Pagh
- Qiang Yang
- Adrià Gascón
- H. Brendan McMahan
In Mathematical Optimization
- Srinath T. V. Setty
- H. Brendan McMahan
- Martin Jaggi
- Daniel Ramage
- Aleksandra Korolova
- Sebastian U. Stich
- Eli Ben-Sasson
- Zachary B. Charles
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “If we relax the requirements for succinctness or non-interactiveness for the construction, there is a large body of constructions that achieve a wide range of efficiency trade-offs, avoid the trusted setup requirement and use more standard cryptographic assumptions [84, 397, 23, 58].”
- Can You Really Backdoor Federated Learning? (2019, background): “BulletProof (8)) can guarantee this when using secure multiparty computation but how to implement them in a computationally and communication efficient way is still an active research direction.”
- zkLedger: Privacy-Preserving Auditing for Distributed Ledgers (2018, background): “There are also newer proof systems, such as Bulletproofs, which might create much smaller range proofs [13].”
- Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “Among transparent SNARKs, Spartan offers the fastest prover with a speedup of 17.5–115× depending on the baseline, produces proofs that are shorter (except compared to SuperSonic and Bulletproofs) by 2–540×, and incurs verification times that are faster (except compared to Fractal) by 71–240×.”
- Aurora: Transparent Succinct Arguments for R1CS (2019, methodology): “Bulletproofs [31, 35] proves the satisfaction of an N -gate arithmetic circuit via a recursive use of a low-communication protocol for inner products, achieving a proof with O(logN) group elements.”
- Zether: Towards Privacy in a Smart Contract World (2020, background): “Bulletproofs [61] enable proofs on Pedersen committed values by computing a linear combination of commitments and opening that combination.”
- Transparent SNARKs from DARK Compilers (2020, background): “1KB PLONK [30] no 2n GB O(n) EXP 1 Pairing O(1) GB 720b Groth16 [35] no 2n GB O(n) EXP 1 Pairing O(1) GB 192b BP [18] yes 2n GP O(n) EXP O(n) EXP 2 log(n) GP 1.”
- Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, methodology): “e, inner products of vectors of commitments, is provided in[15] and optimized in [18].”
- Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, methodology): “Before Bulletproof [16], earlier discrete-log based ZKP schemes include the work of Groth [30], Bayer and Groth [8] and Bootle et al.”
- Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (2021, background): “As of mid-2020, many protocols that employ zero-knowledge proofs use (or plan to use) pairing-based proof systems [23, 27, 35, 49] or Bulletproofs [19].”
- Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings (2019, background): “We also give a more concrete efficiency comparison in Table 2 of Sonic against the fastest zk-SNARK in the literature (Groth 2016 [45]) and Bulletproofs [26].”
- Enhancing Privacy via Hierarchical Federated Learning (2020, neutral): “, range proofs [3]).”