eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/1090

Bulletproofs With Stochastic Equation Sets

Michael Brand, RMIT University
Benoit Poletti

Bulletproofs are general-purpose Zero Knowledge Proof protocols that allow a Prover to demonstrate to a Verifier knowledge of a solution to a set of equations, represented as a Rank 1 Constraint System. We present a protocol extending the standard Bulletproof protocol, which introduces a second layer of interactivity to the protocol, by allowing the Verifier to choose the set of equations after the Prover has already committed to portions of the solution. We show that such Verifier-chosen (or stochastically-chosen) equation sets can be used to design smaller equation sets with less variables that have the same proving-power as their larger, deterministic counterparts but are, in practice, orders of magnitude faster both in proof generation and in proof verification, and even reduce the size of the resulting proofs. We demonstrate this with an example from a real-world application. Our method maintains all the classical benefits of the Bulletproof approach: efficient proof generation, efficient proof checking, extremely short proofs, and the ability to use Fiat-Shamir challenges in order to turn an interactive proof into a non-interactive proof.

Available format(s)
Cryptographic protocols
Publication info
zero-knowledge proofbulletproofstochastic equation set
Contact author(s)
michael brand @ rmit edu au
bpoletti @ incert lu
2023-07-16: approved
2023-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Brand and Benoit Poletti},
      title = {Bulletproofs With Stochastic Equation Sets},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1090},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1090}},
      url = {https://eprint.iacr.org/2023/1090}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.