Proof-Carrying Data (PCD)

PCDs are designed to be recursively composable. The output of one PCD can be used as an input to generate another, creating a chain of verifiable computation. This allows complex, multi-step processes (like a blockchain rollup) to be broken down and verified piecemeal, while the final proof attests to the correctness of the entire pipeline.

• Example: A ZK-Rollup can generate a PCD for a batch of transactions, and that PCD can be used as input for a proof of state transition, which is then verified on the main chain.

The cryptographic proof attached to the data is succinct, meaning its size and the time required to verify it are small and constant, regardless of the complexity of the original computation. This is typically achieved using zk-SNARKs or similar proof systems.

• Key Benefit: Enables lightweight clients or resource-constrained chains (like Layer 1s) to verify the outcome of massive off-chain computations efficiently.

Unlike traditional zero-knowledge proofs that often prove statements about secret inputs, PCDs are fundamentally about proving properties of public data. The proof travels with the data itself, cryptographically certifying that it was produced according to specific rules or from a trusted source.

• Core Mechanism: Anyone can verify the attached proof to be convinced of the data's provenance and computational integrity without re-executing the logic.

PCDs enable trust-minimized interoperability. Participants in a decentralized network do not need to trust each other or a central coordinator; they only need to trust the correctness of the cryptographic proof system and the validity of the initial inputs (e.g., a genesis block or a trusted setup).

• Application: This is critical for building scalable blockchains (via rollups) and cross-chain bridges where the security of one chain does not depend on the honest majority of another.

A specialized form of composability where many individual proofs are aggregated into a single, constant-sized proof. This is essential for scaling systems that produce a high volume of proofs (e.g., every transaction in a ZK-Rollup).

• Process: Multiple transaction proofs are "rolled up" into a single proof, which itself can be rolled up further, creating a recursive proof tree. The root proof verifies the entire set.

PCD is a framework or application pattern, while zk-SNARKs and zk-STARKs are specific cryptographic proof systems used to implement it. PCD specifies how proofs and data are structured and composed; the proof system provides the underlying math for generating the succinct, zero-knowledge arguments.

• zk-SNARKs: Commonly used for PCDs due to small proof sizes, but require a trusted setup.
• zk-STARKs: Can also be used, offering post-quantum security and no trusted setup, with larger proof sizes.

PCDs allow users to prove personal attributes without revealing the underlying data. For example, a user can generate a PCD proving they are over 18 from a government-issued credential, then use that proof to access a service. The service verifies the proof's validity without ever seeing the user's birth date or document.

• Selective Disclosure: Prove specific claims (e.g., "is a citizen," "has a degree") from a broader credential.
• Privacy-Preserving: The original data never leaves the user's device.
• Interoperability: Credentials from one issuer can be used to generate proofs for verifiers in a completely different system.

PCDs are a foundational primitive for zk-rollups seeking recursive proof composition. In this model, a rollup's validity proof itself can be a PCD. Subsequent rollup batches can incorporate and verify previous proofs, creating a chain of attested state transitions.

• Recursive Proof Aggregation: Multiple proofs are combined into a single, succinct proof, drastically reducing on-chain verification costs.
• Incremental Verifiability: New participants can verify the entire chain's history by checking the latest proof, without replaying all transactions.
• Modular Stack: Decouples proof generation from settlement, allowing for specialized proving systems.

PCDs enable bridges and cross-chain applications where a message's provenance and state must be verified on a destination chain. A light client on Chain A can produce a PCD attesting to an event (e.g., a token lock). This proof is sent to Chain B, which verifies it without needing to trust the relayer or fully sync Chain A's state.

• Minimal Trust Assumptions: Removes the need for a centralized multisig or federation.
• State Proofs: Can prove arbitrary state, such as account balances or Merkle tree inclusions, not just transaction existence.
• Gas Efficiency: A small proof is cheaper to verify on-chain than re-executing logic.

PCDs can enforce complex voting rules while maintaining ballot secrecy. A voter generates a proof that their ballot is valid (e.g., they are an eligible member, haven't voted before, and their vote is within allowed options) without revealing which option they chose.

• Coercion Resistance: The proof contains no information that can be used to prove a specific vote to a third party.
• Complex Eligibility: Proofs can combine credentials from multiple sources (e.g., token ownership + DAO membership).
• Public Verifiability: Anyone can verify all submitted proofs are valid, ensuring election integrity without compromising privacy.

PCDs allow the output of a machine learning model to be accompanied by a proof of correct execution. A model provider can run inference off-chain and deliver both the result and a PCD. The client verifies the proof, ensuring the result came from the specified, unaltered model without performing the heavy computation.

• Model Integrity: Proof attests the inference used the exact, published model weights.
• Proprietary Model Protection: The model owner does not need to reveal the model's internal parameters (weights).
• Auditable AI: Creates a verifiable trail for regulatory compliance or fairness audits in automated decisions.

At its core, PCD provides the framework for recursive proof systems. A SNARK that verifies another SNARK is a PCD. This allows proofs about proofs, enabling systems to aggregate an unbounded number of computations into a single, constant-sized proof.

• Infinite Scalability: The verification cost for N statements becomes constant, not linear.
• Parallel Proving: Different components of a large computation can be proven independently, then merged.
• Key Primitive: This is the underlying mechanism enabling many of the other use cases, particularly in blockchain scaling.

PCDs enable off-chain computation where complex proofs are generated externally and submitted to a blockchain as succinct zero-knowledge proofs (ZKPs). This drastically reduces on-chain load and gas costs. Key use cases include:

• Private voting systems where votes are tallied off-chain and only a proof of a valid result is published.
• Cross-chain bridges that prove the validity of state transitions or events on another chain without re-executing them.

PCDs allow users to hold cryptographically verifiable credentials (like attestations or memberships) that can be selectively disclosed. A user can prove they hold a valid credential from an issuer without revealing the credential's contents or their identity. This is crucial for:

• Sybil resistance in governance or airdrops by proving unique personhood.
• Access control to gated communities or services based on proven attributes.

A core feature of PCD is proof composition, where the output proof of one computation can be used as an input to another, creating a chain of verified computations. This enables:

• Recursive proof systems (like zk-SNARKs) where proofs can be aggregated.
• Complex workflow verification, such as proving a series of valid financial transactions led to a final state, without executing each step on-chain.

PCDs can attest to the availability and correct encoding of data without requiring verifiers to download the entire dataset. This is a key component in data availability sampling schemes used by modular blockchain layers (like Celestia) and validiums. It allows light clients to trust that data is published and correct based on a small, verifiable proof.

PCDs are built using advanced cryptographic tools. Key components include:

• Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) for generating compact proofs.
• Commitment schemes to bind data to a proof.
• Signature schemes for issuer authentication in credential systems. The security of a PCD relies on the cryptographic hardness of these underlying primitives.

The security of a PCD rests on the soundness and zero-knowledge properties of its underlying proof system (e.g., zk-SNARKs, zk-STARKs). A flaw in the proving scheme or its trusted setup can compromise the entire data chain. Key considerations include:

• Soundness: A malicious prover cannot create a valid proof for a false statement.
• Zero-Knowledge: The proof reveals nothing beyond the validity of the statement.
• Trusted Setup: Some systems require a secure, one-time ceremony; a compromised setup creates a systemic vulnerability.

PCDs are designed for recursive proof composition, where a proof attests to the validity of other proofs. This introduces a unique attack surface where a single invalid proof could be hidden within a chain of valid ones. Security requires:

• Robust recursion invariants that are preserved at every step.
• Careful circuit design to prevent proof malleability or context-specific attacks during composition.
• Formal verification of the recursive verifier logic to ensure it correctly checks all nested claims.

A PCD proves a statement about data, but the verifier must also have access to the referenced data to act on the claim. Critical issues are:

• Data Hiding: In some PCD constructions, the data itself is not revealed, which is a privacy feature but requires trust that the prover will reveal it if challenged.
• Data Binding: The proof must be cryptographically bound to the specific data it references to prevent replay attacks or malleability.
• Storage Assumptions: Verifiers must consider where and how the attested data is stored and retrieved.

Many PCD applications rely on oracles or trusted attestors to generate the initial proofs about real-world data (e.g., a KYC check). This creates a trust dependency.

• The security of the entire PCD chain is only as strong as the weakest attestor in its history.
• Decentralized oracle networks and multi-party attestation can mitigate single points of failure.
• The PCD must clearly encode the identity and authority of the attestor for the verifier to evaluate trust.

Even with a theoretically secure proof system, vulnerabilities can arise from implementation bugs and side-channel attacks.

• Cryptographic library bugs in elliptic curve operations or hash functions.
• Timing attacks or power analysis that could leak secret witness data during proof generation.
• Circuit bugs where the arithmetic circuit does not correctly encode the intended statement logic, creating a soundness gap.
• Regular audits and formal verification of critical components are essential.

The computational cost and complexity for the verifier are security factors. If verification is too expensive, systems may be forced to trust intermediary relays, reintroducing trust assumptions.

• Verifier time should be sub-linear or constant relative to the complexity of the proven computation.
• Gas costs for on-chain verification in blockchain contexts must be manageable to prevent denial-of-service via high fees.
• A verifier must be able to run the verification algorithm correctly in its environment (e.g., a smart contract).

A cryptographic method where one party (the prover) can prove to another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself. PCDs are built upon ZKPs, allowing the proof to travel with the data.

• Core Mechanism: Uses complex mathematical protocols (e.g., zk-SNARKs, zk-STARKs).
• Key Property: Provides succinctness and privacy.
• Example: Proving you are over 21 without revealing your birth date.

The process of using the output of one proof as an input to generate another, creating a chain or tree of proofs. This is the foundational mechanism that makes PCD possible, enabling proofs about proofs.

• How it works: A proof attesting to the validity of data and the validity of a previous proof.
• Benefit: Allows for incremental verification and unbounded computation proofs.
• Analogy: Like a notary stamping a document that itself contains another notary's stamp, verifying the entire chain.

A prevalent type of zero-knowledge proof characterized by small proof size and fast verification, independent of the original computation's complexity. It is a common cryptographic backend for constructing PCDs.

• Key Traits: Succinct (small proofs), Non-interactive (single message), Argument (computational soundness).
• Role in PCD: Provides the efficient proof system that can be composed recursively.
• Use Case: Zcash for private transactions; many Layer 2 rollups.

The broader field of cryptographically proving that a computation was executed correctly. PCD is a specialized form of verifiable computation where the proof is attached to the computation's output data.

• Contrast: General verifiable computation proves a program's execution. PCD proves properties of data that may be the result of such executions.
• Goal: Enable trust in outsourced or decentralized computation.
• Application: Cloud computing integrity, blockchain smart contracts.

A primary application domain for PCD. By moving complex computation and state updates off-chain and generating a compact PCD, blockchain throughput can be dramatically increased while maintaining security.

• Mechanism: dApp logic runs off-chain; only the final state and its PCD are posted on-chain.
• Benefit: Reduces on-chain gas costs and congestion.
• Example: A decentralized game where turn calculations happen off-chain, with only the final score and a PCD posted to the blockchain.

Using PCDs to create a cryptographically verifiable history or "pedigree" for a piece of data. Each transformation or check on the data generates a new proof, carried alongside it.

• Process: Data starts with a source attestation (proof). Each subsequent processor adds a new proof, forming a verifiable chain.
• Key Use: Supply chain tracking, credential verification, and data integrity in multi-party workflows.
• Property: Enables trust in data without trusting the intermediaries who handled it.

Recursive SNARKs (Succinct Non-interactive Arguments of Knowledge) are the core cryptographic engine behind PCD. They allow a proof to verify the correctness of another proof, creating a chain of verification. This enables:

• Incrementally verifiable computation (IVC): Continuously proving the state of a long-running process.
• Proof composition: Aggregating many proofs into a single, small proof.
• Efficient blockchain scaling: As used in systems like Mina Protocol, where the entire chain state is verified by a constant-sized proof.

PCD can be instantiated with different proving systems. Understanding the trade-offs is key:

• zk-SNARKs (Zero-Knowledge Succinct Non-interactive Arguments of Knowledge): Require a trusted setup but produce very small, fast-to-verify proofs. Used in Zcash and early PCD constructions.
• STARKs (Scalable Transparent Arguments of Knowledge): Do not require a trusted setup and offer potentially faster prover times, but proofs are larger. Offer post-quantum security assumptions. The choice impacts PCD's trust assumptions and performance profile.

PCD is a foundational technology for advanced Layer 2 scaling solutions.

• zkRollups: Can use PCD to generate a single proof that attests to the validity of a batch of transactions, where each transaction's proof is built upon the previous one.
• State Transition Proofs: The rollup's state root can be updated with a PCD that proves the entire batch execution was correct, enabling trustless bridging to Layer 1. This moves beyond simple transaction batching to verifiable computation of entire state updates.

Both verify data integrity, but with different trust models and computational guarantees.

• Merkle Proofs: Prove membership of a piece of data in a set (e.g., a transaction in a block). They are cryptographically cheap but only prove existence, not correctness of computation.
• Proof-Carrying Data: Proves that data was produced by a specific, correct computation. It's computationally intensive but provides a much stronger guarantee: the data is not just present, but valid according to predefined rules.

Incrementally Verifiable Computation (IVC) is the theoretical problem PCD solves. Formally, it allows a prover to produce a proof π_i that attests to the correct execution of a step function F applied i times to an initial input.

• Each new proof π_{i+1} is constructed using the previous proof π_i and the new input.
• The verifier only needs to check the latest proof, which itself attests to the correctness of all previous steps. PCD generalizes IVC to distributed settings where proofs are generated by multiple, untrusted parties.