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