Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension

Gil Segev

doi:10.62056/a6qj893y6

Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension

Authors

Gil Segev

School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel
Coinbase, USA
segev at cs dot huji dot ac dot il

Keywords: Zero Knowledge Bulletproofs R1CS

Abstract

Bulletproofs, introduced by Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell (IEEE S& P, 2018), is a highly efficient non-interactive argument system that does not require a trusted setup. Recently, Bünz (PhD Thesis, 2023) extended Bulletproofs to support arguments for rank-1 constraint satisfaction (R1CS) systems, a widely-used representation for arithmetic satisfiability problems. Although the argument system constructed by Bünz preserves the attractive properties of Bulletproofs, it presents a gap between its completeness and soundness guarantees: The system is complete for a restricted set of instances, but sound only for a significantly broader set. Although argument systems for such gap relations nevertheless provide clear and concrete guarantees, the gaps they introduce may lead to various inconsistencies or undesirable gaps within proofs of security, especially when used as building blocks within larger systems.

In this work we show that the argument system presented by Bünz can be extended to bridge the gap between its completeness and soundness, and to additionally provide honest-verifier zero-knowledge. For the extended argument system, we introduce a refined R1CS relation that captures the precise set of instances for which both completeness and soundness hold without resorting to a gap formulation. The extended argument system preserves the performance guarantees of the argument system presented by Bünz, and yields a non-interactive argument system using the Fiat-Shamir transform.

References

[AC20]

Thomas Attema and Ronald Cramer. Compressed $\varSigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 513–543. August 2020. DOI: 10.1007/978-3-030-56877-1_18

Google Scholar ePrint

[AFK23]

Thomas Attema, Serge Fehr, and Michael Klooß. Fiat-Shamir Transformation of Multi-Round Interactive Proofs (Extended Version). Journal of Cryptology, 36(4):36, October 2023. DOI: 10.1007/s00145-023-09478-y

Google Scholar ePrint

[BBB⁺18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. May 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00020

Google Scholar ePrint

[BCC⁺16]

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 327–357. May 2016. DOI: 10.1007/978-3-662-49896-5_12

Google Scholar ePrint

[BCR⁺19]

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part I, volume 11476 of Lecture Notes in Computer Science, pages 103–128. May 2019. DOI: 10.1007/978-3-030-17653-2_4

Google Scholar ePrint

[B{\"{u}}n23]

Benedikt Bünz. Improving the Privacy, Scalability, and Ecological Impact of Blockchains. PhD thesis, Stanford University, 2023.

Google Scholar ePrint

[CHJ⁺22]

Heewon Chung, Kyoohyung Han, Chanyang Ju, Myungsun Kim, and Jae Hong Seo. Bulletproofs+: Shorter Proofs for a Privacy-Enhanced Distributed Ledger. IEEE Access, 10:42067–42082, 2022. DOI: 10.1109/ACCESS.2022.3167806

Google Scholar ePrint

[CHM⁺20]

Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738–768. May 2020. DOI: 10.1007/978-3-030-45721-1_26

Google Scholar ePrint

[FS87]

Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology – CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186–194. August 1987. DOI: 10.1007/3-540-47721-7_12

Google Scholar ePrint

[GGPR13]

Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 626–645. May 2013. DOI: 10.1007/978-3-642-38348-9_37

Google Scholar ePrint

[Gro16]

Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 305–326. May 2016. DOI: 10.1007/978-3-662-49896-5_11

Google Scholar ePrint

[Lin03]

Yehuda Lindell. Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. Journal of Cryptology, 16(3):143–184, June 2003. DOI: 10.1007/s00145-002-0143-7

Google Scholar ePrint

[OB22]

Alex Ozdemir and Dan Boneh. Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets. In Kevin R. B. Butler and Kurt Thomas, editors, USENIX Security 2022: 31st USENIX Security Symposium, pages 4291–4308. August 2022. USENIX Association.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6qj893y6

History

Submitted: 2025-01-08
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Gil Segev, Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6qj893y6.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a6qj893y6,
         author={Gil Segev},
         title={Bulletproofs for R1{CS}: Bridging the Completeness-Soundness Gap and a {ZK} Extension},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/a6qj893y6},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Gil Segev
PY  - 2025
TI  - Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/a6qj893y6
UR  - https://doi.org/10.62056/a6qj893y6
AB  - <p>Bulletproofs, introduced by Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell (IEEE S&amp; P, 2018), is a highly efficient non-interactive argument system that does not require a trusted setup. Recently, Bünz (PhD Thesis, 2023) extended Bulletproofs to support arguments for rank-1 constraint satisfaction (R1CS) systems, a widely-used representation for arithmetic satisfiability problems. Although the argument system constructed by Bünz preserves the attractive properties of Bulletproofs, it presents a gap between its completeness and soundness guarantees: The system is complete for a restricted set of instances, but sound only for a significantly broader set. Although argument systems for such gap relations nevertheless provide clear and concrete guarantees, the gaps they introduce may lead to various inconsistencies or undesirable gaps within proofs of security, especially when used as building blocks within larger systems.</p><p>In this work we show that the argument system presented by Bünz can be extended to bridge the gap between its completeness and soundness, and to additionally provide honest-verifier zero-knowledge. For the extended argument system, we introduce a refined R1CS relation that captures the precise set of instances for which both completeness and soundness hold without resorting to a gap formulation. The extended argument system preserves the performance guarantees of the argument system presented by Bünz, and yields a non-interactive argument system using the Fiat-Shamir transform. </p>
ER  -

Gil Segev, Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6qj893y6.