Bulletproofs+: Shorter Proofs for a Privacy-Enhanced Distributed Ledger

HeeWon Chung, Kyoohyung Han, Chanyang Ju, Myungsun Kim, Jae Hong SeoIEEE Access 2022 · OpenReview

Abstract

Bulletproofs+ introduces a novel zero-knowledge argument for range proofs and arithmetic circuits that achieves the shortest proof size for systems without a trusted setup. By revisiting sublinear zero-knowledge arguments and introducing a zero-knowledge weighted inner product argument (zk-WIP), this protocol reduces the size of a standard 64-bit range proof to 576 bytes—an 85.7% reduction compared to the original Bulletproofs. This improvement enhances the scalability of privacy-centric distributed ledgers like Monero without compromising computational efficiency or requiring risky initialization phases.

Introduction

In the landscape of decentralized ledgers, transaction transparency is essential for public auditability but detrimental to user privacy. Confidential Transactions (CT) address this by masking transaction amounts using cryptographic commitments. However, the network must verify that these hidden amounts are valid—specifically, that they are non-negative to prevent the unauthorized creation of currency. Range proofs are the cryptographic tool used to prove that a committed value lies within a specific interval (e.g., $[0, 2^{64}-1]$) without revealing the value itself.

The original Bulletproofs protocol, introduced in 2018, was a landmark development because it offered short proofs and was "transparent," meaning it required no trusted setup. Despite its efficiency, range proofs still constitute a significant portion of blockchain data. Bulletproofs+ seeks to further optimize this overhead, providing a more compact solution for distributed ledger technology.

Methodology: The zk-WIP Argument

The primary innovation of Bulletproofs+ is the zero-knowledge weighted inner product argument (zk-WIP). The original Bulletproofs protocol relies on an inner product argument that is not inherently zero-knowledge. To ensure privacy, the protocol must append "blinding factors" (random numbers) at the final stage, which increases the total proof size.

In contrast, Bulletproofs+ integrates the zero-knowledge property directly into the weighted inner product argument from the outset. By utilizing a weighted inner product—where elements are scaled by powers of a challenge value—the protocol can more efficiently batch multiple equations. During the recursive reduction process, where a large problem is halved repeatedly, Bulletproofs+ requires the transmission of fewer elements. While the original protocol might require five elements for certain steps, the zk-WIP approach minimizes this transmission cost. Furthermore, the authors demonstrate that complex arithmetic circuits can be reduced to this zk-WIP framework, extending the benefits beyond simple range proofs to general-purpose verifiable computation.

Performance and Results

The authors implemented Bulletproofs+ in Rust using the curve25519-dalek library and benchmarked it against the standard Bulletproofs implementation on a MacBook Pro (Intel i5 CPU).

  • Proof Size: For a 64-bit range proof, Bulletproofs+ achieves a size of 576 bytes, compared to 672 bytes for the original, representing a 14.3% reduction in storage requirements.
  • Proving Efficiency: The prover is significantly faster; for a batch of 64 32-bit range proofs, the Bulletproofs+ prover is approximately 26.8% faster than the original.
  • Verification: Verification time remains nearly identical to the original protocol. Although there is a marginal 3.3% increase in computational overhead due to larger exponents in multiexponentiation, this is considered negligible in the context of network propagation and validation.

For a high-throughput network like Monero, adopting Bulletproofs+ could reduce ledger growth by over 1 MB per day, leading to lower transaction fees and faster node synchronization.

Conclusion

Bulletproofs+ represents a significant step forward in trustless zero-knowledge proofs. By refining the inner product argument into a native zero-knowledge weighted variant, it provides the most compact proofs available for range verification today. While the verifier's complexity remains linear relative to the circuit size, the reduction in communication overhead makes it an ideal candidate for immediate deployment in privacy-enhanced distributed ledgers. Future research remains focused on achieving logarithmic verification times without sacrificing the transparency and proof-size advantages of the Bulletproofs family.

Summary updated

Abstract

This paper presents a new short zero-knowledge argument for the range proof and arithmetic circuits without a trusted setup. In particular, it can achieve the shortest proof size of the proof system categories without a trusted setup. More specifically, when proving that a committed value is a positive integer less than 64 bits, except for negligible error in the 128-bit security parameter, the proof size is 576 bytes long, which is 85.7% the size of the previous shortest proof due to Bünz et al. (Bulletproofs, IEEE Security and Privacy 2018). Similarly, circuit satisfiability can be proven with less communication overhead. Nevertheless, computational overheads in both proof generation and verification are comparable with those of Bulletproofs. Bulletproofs is established as one of the important privacy-enhancing technologies for a distributed ledger due to its trustless feature and short proof size. In particular, it has been implemented and optimized in various programming languages for practical usage by independent entities since it was proposed. The essence of Bulletproofs is based on the logarithmic inner product argument with no zero-knowledge. This paper revisits Bulletproofs from the viewpoint of the first sublinear zero-knowledge argument for linear algebra due to Groth (CRYPTO 2009) and then propose Bulletproofs+, an improved variety of Bulletproofs. The main component is the zero-knowledge weighted inner product argument (zk-WIP) which enables to reduce both the range proof and the arithmetic circuit proof. It already has zero-knowledge properties, there is no additional information when reducing zk-WIP, and it incurs a minimal transmission cost during the reduction process. Note that zk-WIP has all characteristics of the inner product argument, such as an aggregating range proof and batch verification; thus, Bulletproofs+ is superior to Bulletproofs in all aspects.
BibTeX
@inproceedings{chung2022bulletproofs,
  author = {HeeWon Chung and Kyoohyung Han and Chanyang Ju and Myungsun Kim and Jae Hong Seo},
  title = {{Bulletproofs+: Shorter Proofs for a Privacy-Enhanced Distributed Ledger}},
  booktitle = {IEEE Access},
  year = {2022},
  url = {https://openreview.net/forum?id=I4VZC7mFpu},
}
Figure