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. Applications 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, these constructions do not come with security analyses that yield useful concrete security bounds, leaving practitioners in the dark about how to securely instantiate PCD constructions. In this work we study the concrete security of recursive composition, with the goal of enabling practitioners to set efficient 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. In this setting, recursive composition incurs no security loss. We describe how straightline knowledge soundness is achieved by SNARKs in several oracle models, including SNARKs that are deployed in practice. Crucially, SNARKs in these settings can be \emph{relativized}, allowing us to construct PCD without instantiating the SNARK's oracle explicitly. This results in a highly efficient security analysis of PCD that makes black-box use of the SNARK's oracle. As a notable application, our work offers an idealized model that provides useful, albeit heuristic, guidance for setting the security parameters of \emph{recursive STARKs} currently used in blockchain systems.

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
2023-10-26: approved
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.