Paper 2023/1646

Security Bounds for Proof-Carrying Data from Straightline Extractors

Abstract

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.