Paper 2023/494

Spartan and Bulletproofs are simulation-extractable (for free!)

Quang Dao, Carnegie Mellon University
Paul Grubbs, University of Michigan–Ann Arbor

Increasing deployment of advanced zero-knowledge proof systems, especially zkSNARKs, has raised critical questions about their security against real-world attacks. Two classes of attacks of concern in practice are adaptive soundness attacks, where an attacker can prove false statements by choosing its public input after generating a proof, and malleability attacks, where an attacker can use a valid proof to create another valid proof it could not have created itself. Prior work has shown that simulation-extractability (SIM-EXT), a strong notion of security for proof systems, rules out these attacks. In this paper, we prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (SIM-EXT) in the random oracle model if the discrete logarithm assumption holds in the underlying group. Since these assumptions are required to prove standard security properties for Spartan and Bulletproofs, our results show that SIM-EXT is, surprisingly, "for free" with these schemes. Our result is the first SIM-EXT proof for Spartan and encompasses both linear- and sublinear-verifier variants. Our result for Bulletproofs encompasses both the aggregate range proof and arithmetic circuit variants, and is the first to not rely on the algebraic group model (AGM), resolving an open question posed by Ganesh et al. (EUROCRYPT '22). As part of our analysis, we develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC '22), which may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
simulation extractabilitySpartanBulletproofsnon-interactive zero-knowledgezkSNARKsFiat-Shamir
Contact author(s)
qvd @ andrew cmu edu
paulgrub @ umich edu
2023-04-05: approved
2023-04-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Quang Dao and Paul Grubbs},
      title = {Spartan and Bulletproofs are simulation-extractable (for free!)},
      howpublished = {Cryptology ePrint Archive, Paper 2023/494},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.