Scala, E., & Mostarda, L. 2023, Range proofs with constant size and trustless setup. Paper presented at Advanced Information Networking and Applications: Proceedings of the 37th International Conference on Advanced Information Networking and Applications (AINA-2023), Volume 3.
Added by: Jack (2023-03-28 21:38) Last edited by: Jack (2023-03-29 18:12)
|Resource type: Proceedings Article
BibTeX citation key: Scala2023
View all bibliographic details
|Categories: Not Monero-focused
Creators: Mostarda, Scala
Collection: Advanced Information Networking and Applications: Proceedings of the 37th International Conference on Advanced Information Networking and Applications (AINA-2023), Volume 3
|URLs https://link.sprin ... 8-3-031-28694-0_28
Range proofs are widely adopted in practice in many privacy-preserving cryptographic protocols in the public blockchain. The performances known in the literature for range proofs are logarithmic-sized proofs and linear verification time. In contexts where the proof verification is left to the ledger maintainers and proofs are stored in blocks, one might expect higher transaction fees and blockchain space when the size of the relation over the proof grows. With this paper, we improve Bulletproofs, a zero-knowledge argument of knowledge for range proofs, by modifying its Inner Product Argument (IPA) subroutine. In particular, we adopt a new relation from the polynomial commitment scheme of Halo, based on standard groups and assumptions (DLOG and RO) with a trustless setup. We design a two-step reduction algorithm and we obtain a constant number of two rounds in the IPA and a constant-sized proof composed of 5 G1 points and 2 Zp scalars.
MRL meeting notes with the authors: https://github.com/monero-project/meta/issues/818
Sarang: The paper seems to jump from security properties of the Halo2 design to conclusions about range proof security. Do you intend to extent the security proofs to cover this? On an initial read of the paper, it was not immediately clear if/why this jump should be valid. That is, if the Halo2 construction is sound and ZK, and if the original BP paper relied on certain IPP properties (like WEE), do these necessarily play nicely together?
Emanuele: Yes, exactly. This is our ongoing work, we now have assumed the IPA argument relation of Halo as secure in our design. However, we need to prove the whole range proof when the new IPA relation is integrated. Referring to Halo and BP, they share the same security properties (WEE, HVZK) and hardness assumptions. I think they can play nicely together.
Sarang: Can you remind me if the construction supports efficient batch verification? I don't have the paper handy and unfortunately don't recall if this was the case. BP and BP+ verify linearly-ish, but shared generators mean pretty big savings in batch
Emanuele: Yes the work support batch verification and aggregation of range values. In fact the evaluation shows a constant proof size when the number of range values increase.
Added by: Jack Last edited by: Jack