Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger

[WildCryptoFox]

(Just an FYI post in case you missed it. More techniques for reducing costs.)

https://eprint.iacr.org/2020/735

Abstract: We present a new short zero-knowledge argument for the range proof and the arithmetic circuits without a trusted setup. In particular, the proof size of our protocol is the shortest of the category of proof systems with a trustless setup. More concretely, when proving 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 byte long, which is of 85.7% size of the previous shortest one due to B"unz et al.~(Bulletproofs, IEEE Security and Privacy 2018), while computational overheads in both proof generation and verification are comparable with those of Bulletproofs, respectively. Bulletproofs is established as one of important privacy enhancing technologies for 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 usages by independent entities since it proposed. The essence of Bulletproofs is based on the logarithmic inner product argument with no zero-knowledge. In this paper, we revisit 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 ingredient of our proposal is the zero-knowledge weighted inner product argument (zk-WIP) to which we reduce both the range proof and the arithmetic circuit proof. The benefit of reducing to the zk-WIP is a minimal transmission cost during the reduction process. Note the zk-WIP has all nice features of the inner product argument such as an aggregating range proof and batch verification.

[rubdos]

For fair comparison with optimized implementation for Bulletproofs, our protocols are implemented in Rust using the curve25519-dalek library for ECC operations [54] and compared with the January 2020 git version of Bulletproofs implementation in by Valence et al. [28], which is, to the best of our knowledge, one of the most optimized implementations for Bulletproofs.

They have an implementation based on dalek25519, and compare directly with this crate. I wonder whether they'll release their source code at some point. To what extent would the crate owners (@oleganza ?) be interested in having this in here? We might want a peer-reviewed paper first (or introduce a yoloyoloproofs feature).

[omershlo]

https://github.com/KZen-networks/bulletproofs
not as fast as this library (4x slower using bulletproofs+) but a good playground if you want to play use bulletproofs+ or use as reference code (until the authors of the paper will release their code)

[cathieyun]

This is a cool development, thanks for sharing!
After the paper goes through peer review, I'd be down to include it, maybe under the yoloproofs feature guard.

@omershlo, do you mean that your code is 4x slower than this library? Do you know what the cause of the slowdown? From a skim of the paper, it seems like Bulletproofs+ should have about comparable proving and verification times than Bulletproofs, with smaller proof sizes.

[omershlo]

Hi @cathieyun ,
X = Dalek range proof computing time using Bulletproofs
Y = KZen range proof computing time using Bulletproofs
Z = KZen range proof computing time using Bulletproofs+

X is ~4x faster than Z
X is ~6x faster than Y
Y compare to Z is similar to the results in the paper (we actually get faster verification times as opposed to the paper). We will release a doc with a detailed table very soon.

[daira]

Re: peer review, yous know that it usually doesn't check proofs, right? (And peer reviewers are explicitly not required to even look at "supplementary information", which the proofs are forced into because of page limits for most journals/conferences.)

[rubdos]

Re: peer review, yous know that it usually doesn't check proofs, right? (And peer reviewers are explicitly not required to even look at "supplementary information", which the proofs are forced into because of page limits for most journals/conferences.)

Peer review has more value that just proof checking :-)

Also, the reviewers are not forced to read the proofs, but in my experience they do take a look at them.