Paper 2025/2037

On the Simulation-Extractability of Proof-Carrying Data

Abstract

Proof-carrying data (PCD) is a powerful paradigm for verifying distributed computations. Each node in the computation produces a proof that can be checked efficiently, regardless of how complex the overall computation is. As PCDs—and their special case, incrementally verifiable computation (IVC)—gain wider adoption, it becomes crucial to understand how robust they are against malleability attacks. In particular, it remains completely unexplored whether recursive proof systems satisfy simulation extractability (SIM-EXT)—a property ensuring non-malleability and composability. This work provides the first systematic study of simulation extractability for PCD. We begin by observing that the standard SIM-EXT notion for non-recursive zkSNARKs does not directly extend to PCD/IVC settings. To address this, we propose a new definition of SIM-EXT tailored to proof-carrying data that accounts for their idiosyncratic features. Using this framework, we prove two general results: (1) that a simulation-extractable SNARK implies a simulation-extractable PCD when used recursively, and (2) that more lightweight PCD constructions—built from a (not necessarily succinct) argument of knowledge (NARK) combined with a split-accumulation scheme—also achieve SIM-EXT of PCD by requiring SIM-EXT only from the underlying NARK. Our results show that many modern PCD systems are already simulation-extractable by design.