Bulletproofs: Short Proofs for Confidential Transactions and More

Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Greg Maxwell

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE Symposium on Security and Privacy, SP 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages315-334
Number of pages20
ISBN (Electronic)9781538643525
DOIs
StatePublished - Jul 23 2018
Event39th IEEE Symposium on Security and Privacy, SP 2018 - San Francisco, United States
Duration: May 21 2018May 23 2018

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
Volume2018-May
ISSN (Print)1081-6011

Other

Other39th IEEE Symposium on Security and Privacy, SP 2018
Country/TerritoryUnited States
CitySan Francisco
Period5/21/185/23/18

Keywords

  • Bitcoin
  • Blockchain
  • confidential transactions
  • privacy
  • Zero Knowledge proof of knowledge

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Bulletproofs: Short Proofs for Confidential Transactions and More'. Together they form a unique fingerprint.

Cite this