Proof Carrying Data (PCD)

Unlike single-prover IVC, PCD allows multiple independent provers to each generate a proof for their local computation step. These proofs are then recursively composed into a single, constant-size proof that attests to the correctness of the entire distributed computation. Each participant only needs to know their own input and the incoming proof from the previous step, not the entire global history.

• Enables asynchronous collaboration across untrusted parties
• Final proof size and verification time are independent of the total number of steps
• Built on recursive composition of Succinct Non-Interactive Arguments of Knowledge (SNARKs)

PCD enforces compliance predicates—local rules that each step of the computation must satisfy. A predicate is a boolean function that checks whether a state transition is valid given the input, output, and incoming proof. If any step violates its predicate, no valid final proof can be generated.

• Predicates act as distributed invariant checks
• Enables policy enforcement without a central authority
• Used in blockchain rollups to ensure every transaction follows protocol rules

PCD formalizes distributed computation as a message-passing graph where nodes represent computation steps and edges carry both data and proofs. Each node receives a message with an attached proof of its sender's correct execution, performs its local computation, and outputs a new message with an updated proof.

• The graph topology can be arbitrary and dynamic
• Supports branching and merging of computation paths
• Natural fit for modeling asynchronous distributed systems and cross-chain communication

A defining property of PCD is that the final proof size and verification cost remain constant regardless of how many steps or parties contributed to the computation. This is achieved through recursive SNARK composition, where each new proof absorbs and verifies the previous proof before generating its own.

• Verification time: O(1) relative to computation length
• Proof size typically a few hundred bytes in modern systems
• Critical for resource-constrained verifiers like light clients and on-chain smart contracts

Modern PCD constructions leverage folding schemes like Nova to achieve dramatically faster prover times. Instead of fully verifying the incoming proof at each step, a folding scheme reduces two instances of a constraint system into a single instance, deferring expensive cryptographic operations.

• Nova achieves sub-linear prover costs through incremental folding
• Eliminates the need for expensive proof verification at each recursive step
• Enables practical PCD for long-running distributed computations with frequent state updates

PCD is the cryptographic backbone of recursive zk-rollups and verifiable blockchain scaling solutions. Each transaction generates a proof of valid execution, and a batch prover recursively composes these into a single proof submitted to the Layer-1 chain.

• Enables horizontal scaling through parallel proof generation
• Used in systems like Mina Protocol where the entire blockchain is a single recursive proof
• Supports cross-rollup interoperability by carrying proofs across independent execution environments

A paradigm where a prover updates a proof after each step of a long-running computation. The final proof size and verification time remain constant regardless of the total number of steps executed. PCD is a distributed generalization of IVC, where different parties may perform each step.

• IVC: Single prover, sequential steps
• PCD: Multiple provers, potentially branching paths
• Use Case: Verifying a blockchain's entire history in a single, succinct proof

A directed acyclic graph representing a computation as a series of addition and multiplication gates over a finite field. This is the foundational representation for all ZKP systems, including PCD. The computation being proven at each step of a PCD chain must first be compiled into an arithmetic circuit.

• Gates: Addition and multiplication over a prime field
• Wires: Carry intermediate values between gates
• Constraint: The circuit's structure defines the valid execution trace

The abstract model that PCD secures. A system where state transitions can be performed by multiple independent parties, each appending their proof of correct execution. The final proof attests to the integrity of the entire distributed lineage.

• Example: A supply chain where each custodian updates a shipment's status
• Example: A multi-rollup blockchain ecosystem with cross-chain message passing
• Guarantee: Any verifier can check the final state's validity without trusting any intermediate party