Proof of Correct Encoding

A Proof of Correct Encoding is a succinct cryptographic argument that demonstrates a prover has correctly transformed raw data into an erasure-coded format. This is crucial for systems like data availability sampling (DAS), where light nodes need assurance that the full data can be reconstructed from randomly sampled fragments. The proof typically involves polynomial commitments or vector commitments to verify the encoding process without downloading the entire dataset.

PoCE is the foundational trust mechanism for Data Availability Sampling (DAS). Light clients randomly sample small pieces of erasure-coded data. The accompanying PoCE provides the cryptographic guarantee that if the samples are valid, the entire original data block is available and can be reconstructed. This allows for secure scaling without requiring every node to store the full blockchain history.

The encoding process proven by PoCE typically uses erasure coding techniques like Reed-Solomon codes. This transforms the original data into a larger set of encoded pieces with redundancy. A common scheme is 2x redundancy: a 1 MB block becomes 2 MB of encoded data. The proof verifies this expansion was performed correctly, ensuring any 50% of the pieces are sufficient for full reconstruction.

PoCE operates as a validity proof for data formatting, distinct from fraud proofs which challenge invalid state transitions.

• PoCE: Proves "the data was encoded correctly." It is required upfront for data to be accepted.
• Fraud Proof: Challenges "this state transition is incorrect." It is submitted after the fact if a fault is detected. Together, they form a comprehensive security model for optimistic rollups and L2s.

Major data availability layers implement PoCE as a core protocol component.

• Celestia: Uses 2D Reed-Solomon encoding and proofs based on Namespaced Merkle Trees (NMTs).
• EigenDA: Leverages re-staking and a committee of operators to generate and verify KZG commitments for the encoded data. These implementations allow light nodes to verify data availability with minimal resource requirements.

A leading method for constructing efficient PoCE uses KZG (Kate-Zaverucha-Goldberg) polynomial commitments. The data is interpolated into a polynomial, and a commitment to this polynomial is published. The proof demonstrates that the erasure-coded shares are evaluations of this same polynomial. This provides constant-size proofs and verification, which is essential for scalability.

In validity rollups (zk-rollups), PoCE is used to prove that the raw transaction data has been correctly encoded into the state transition function's required format, such as a Merkle tree or an arithmetic circuit. This ensures the zero-knowledge proof (ZKP) is verifying computations on valid, untampered input data.

• Process: The sequencer encodes batch transactions, generates a PoCE, and submits both to the base layer.
• Purpose: Prevents proving incorrect state transitions from malformed data.

PoCE is critical for Data Availability Sampling protocols, like those used in EigenDA or Celestia. It proves that erasure-coded data blocks are correctly generated from the original data.

• Mechanism: A node produces a 2D Reed-Solomon encoding of the data and generates a PoCE (e.g., a KZG commitment).
• Trust: Light clients can sample small random chunks, relying on the PoCE to guarantee that if a sample is available, the entire dataset is recoverable.

Cross-chain messaging and bridge protocols use PoCE to verify that the information (e.g., a transaction receipt or state root) being relayed from a source chain has been correctly serialized and committed.

• Example: A light client bridge on Chain A receives a block header and a PoCE demonstrating that the relevant Merkle-Patricia Trie path for a specific log was correctly encoded within it.
• Benefit: Reduces the trust assumption to the security of the cryptographic proof rather than a third-party attestation.

When storing data on networks like Filecoin or Arweave, PoCE can be used to prove that the data submitted to the network matches the data that was originally encoded for storage commitments.

• Application: A storage provider generates a proof that the data they are storing is the correct Merkle tree root or cryptographic hash they committed to.
• Outcome: Enables efficient and trustless verification of storage claims without retrieving the entire dataset.

PoCE is not a single algorithm but a class of proofs implemented using various cryptographic primitives.

• Polynomial Commitments: Using KZG commitments to prove a piece of data is the correct evaluation of a committed polynomial.
• Vector Commitments: Using Merkle trees with specific hash functions to prove inclusion and correct ordering.
• SNARKs/STARKs: A specialized arithmetic circuit or AIR (Algebraic Intermediate Representation) can be constructed to verify the encoding process itself.

It is crucial to distinguish PoCE from Proof of Storage (PoS) or Proof of Retrievability (PoR).

• Proof of Correct Encoding: Verifies the format and integrity of data transformation. "Is this data correctly structured?"
• Proof of Storage/Retrievability: Verifies the continued possession and accessibility of raw data. "Do you still have this data?"

PoCE is often a prerequisite for generating efficient PoS/PoR proofs in decentralized systems.

The primary security guarantee of PoCE is data integrity. It ensures that the raw data submitted to a system matches the structure and constraints defined by the protocol's schema. This prevents:

• Garbage data from being accepted, which could corrupt state or cause runtime errors.
• Malformed transactions that might exploit parser vulnerabilities in downstream applications.
• Schema violations that could lead to inconsistent interpretations of the data.

A critical consideration is who generates the proof. If the proof is generated by a trusted, centralized party, the system inherits that trust assumption. Decentralized alternatives include:

• Client-side proving, where the user's wallet generates the proof.
• A decentralized network of provers with economic security (e.g., staking and slashing).
• Trusted Execution Environments (TEEs) for generating attestations, though this introduces hardware trust.

The security of the entire system depends on the verification contract or node software correctly checking the proof. Key risks include:

• Bugs in the verification circuit or smart contract that allow invalid proofs to be accepted.
• Upgrade mechanisms that could introduce faulty verifiers.
• Insufficient cryptographic parameters, making the proof system vulnerable to brute-force or cryptographic attacks over time.

The proof itself may reveal information about the private data it encodes. Security designs must consider:

• Zero-knowledge proofs (ZKPs) can prove correctness without revealing the underlying data, enhancing privacy.
• Proof size and complexity can be a denial-of-service vector if they are too large to process efficiently.
• Selective disclosure mechanisms may be needed if the proof is used in multi-party scenarios.

For decentralized prover networks, cryptoeconomic security is essential. The design must ensure:

• Cost of cheating > reward for cheating. Provers must be sufficiently penalized (slashed) for submitting invalid proofs.
• Liveness guarantees. The network must have enough provers to prevent censorship of proof generation.
• Fee market design. Proof generation costs must be predictable and not subject to manipulation that could halt the system.