Paper 2023/1646

Security Bounds for Proof-Carrying Data from Straightline Extractors

Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Ziyi Guan, École Polytechnique Fédérale de Lausanne
Shahar Samocha, StarkWare
Eylon Yogev, Bar-Ilan University

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses would lead to setting parameters that are prohibitively expensive. In this work we study the concrete security of recursive composition, with the goal of better understanding how to reasonably set parameters for certain PCD constructions of practical interest. Our main result is that PCD obtained from SNARKs with \emph{straightline knowledge soundness} has essentially the same security as the underlying SNARK (i.e., recursive composition incurs essentially no security loss). We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, which results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle (there is no need to instantiated the oracle to carry out the security reduction). As a notable application, our work offers an idealized model that provides new, albeit heuristic, insights for the concrete security of \emph{recursive STARKs} used in blockchain systems. Our work could be viewed as partial evidence justifying the parameter choices for recursive STARKs made by practitioners.

Available format(s)
Publication info
proof-carrying datasuccinct non-interactive argumentsrelativizationconcrete security
Contact author(s)
alessandro chiesa @ epfl ch
ziyi guan @ epfl ch
shahars @ starkware co
eylon yogev @ biu ac il
2024-05-20: revised
2023-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alessandro Chiesa and Ziyi Guan and Shahar Samocha and Eylon Yogev},
      title = {Security Bounds for Proof-Carrying Data from Straightline Extractors},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1646},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.