Paper 2022/510

Bulletproofs++: Next Generation Confidential Transactions via Reciprocal Set Membership Arguments

Liam Eagen, Blockstream
Sanket Kanjalkar, Blockstream
Tim Ruffing, Blockstream
Jonas Nick, Blockstream
Abstract

Zero-knowledge proofs are a cryptographic cornerstone of privacy-preserving technologies such as "Confidential Transactions" (CT), which aims at hiding monetary amounts in cryptocurrency transactions. Due to its asymptotically logarithmic proof size and transparent setup, most state-of-the-art CT protocols use the Bulletproofs (BP) zero-knowledge proof system for set membership proofs such as range proofs. However, even taking into account recent efficiency improvements, BP comes with a serious overhead in terms of concrete proof size as well as verifier running time and thus puts a large burden on practical deployments of CT and its extensions. In this work, we introduce Bulletproofs++ (BP++), a drop-in replacement for BP that improves its concrete efficiency and compactness significantly. As for BP, the security of BP++ relies only on the hardness of the discrete logarithm problem in the random oracle model, and BP++ retains all features of Bulletproofs including transparent setup and support for proof aggregation, multi-party proving and batch verification. Asymptotically, BP++ range proofs require only $O(n / \log n)$ group scalar multiplications compared to $O(n)$ for BP and BP+. At the heart of our construction are novel techniques for permutation and set membership, which enable us to prove statements encoded as arithmetic circuits very efficiently. Concretely, a single BP++ range proof to establish that a committed value is in a 64-bit range (as commonly required by CT) is just 416 bytes over a 256-bit elliptic curve, 38\% smaller than an equivalent BP and 27\% smaller than BP+. When instantiated using the secp256k1 curve as used in Bitcoin, our benchmarks show that proving is about 5 times faster than BP and verification is about 3 times faster than BP. When aggregating 32 range proofs, proving and verification are about 9.5 times and 5.5 times faster, respectively.

Note: Haskell proof of concept code available at https://github.com/Liam-Eagen/BulletproofsPP WIP C implementation at https://github.com/BlockstreamResearch/secp256k1-zkp

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero knowledgecryptocurrency
Contact author(s)
liameagen @ protonmail com
sanket1729 @ blockstream com
crypto @ timruffing de
jonas @ n-ck net
History
2023-07-17: revised
2022-05-02: received
See all versions
Short URL
https://ia.cr/2022/510
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/510,
      author = {Liam Eagen and Sanket Kanjalkar and Tim Ruffing and Jonas Nick},
      title = {Bulletproofs++: Next Generation Confidential Transactions via Reciprocal Set Membership Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2022/510},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/510}},
      url = {https://eprint.iacr.org/2022/510}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.