Cryptology ePrint Archive: Report 2022/510

Bulletproofs++

Liam Eagen

Abstract: Bulletproofs++ is a new protocol based on Bulletproofs and Bulletproofs+ for shorter range proofs and confidential transactions with multiple types of currency supporting multiparty proving. Both the range proofs and confidential transactions use a permutation argument based on the logarithmic derivative of a polynomial encoding the elements of a multiset of field elements. This protocol makes the multiplicities legible to the proof system and is linear in the elements of the multiset.

Using the permutation argument, as well as a new variant of the weighted inner product argument for weighted norms, Bulletproofs++ range proofs can support larger bases and achieve much smaller witness sizes. For a 64 bit range, representing the value as 16 hexadecimal digits reduces the length of the witness per commitment by a factor of approximately 6, asymptotically approaching 8 as the number of values increases. The proof size for a single value using Curve25519 is 416 bytes, which is 160 bytes smaller than Bulletproofs+. This technique has a small asymptotic affect on the witness size, going from O(n) to O(n/log n) where n is the number of bits required to encode all the values to be proven.

For confidential transactions, the ``elements" of the multiset are the types of currency and the multiplicities are the amounts for each input. Since the argument is linear in the elements of the set, multiple provers can show that all the inputs and outputs for a transaction satisfy typed conservation of money without breaking their mutual privacy. This confidential transaction protocol has essentially the same structure as the generic base range proof and can be added to a range proof at minimal additional cost to make a confidential transaction protocol.

Category / Keywords: cryptographic protocols / zero knowledge cryptocurrency

Date: received 28 Apr 2022

Contact author: liameagen at protonmail com

Available format(s): PDF | BibTeX Citation

Note: Haskell proof of concept code available at https://github.com/Liam-Eagen/BulletproofsPP

Version: 20220502:104928 (All versions of this report)

Short URL: ia.cr/2022/510


[ Cryptology ePrint archive ]