ZK-EVM Prover Input Standardization

Special thanks to Justin Drake, Elias Tazartes, Clément Walter, Rami Khalil for review and feedback.

TL;DR

On the path towards enabling real-time block proving, this post proposes a unified data format for the input that ZK-EVM prover engines should accept to prove an Ethereum Execution Layer (or EVM) block (see article by Vitalik for context about Validity proofs of EVM execution).

Note: This article focuses only on the input for ZK-EVM to generate Execution Layer proofs and does not address the Consensus Layer, which is considered an independent problem.

Motivation

The ZK-EVM block proving ecosystem is rapidly expanding, with various teams implementing their own ZK-EVM engines, such as Keth (Cairo) by Kakarot, Zeth (RiscV) by RiscZero, and RSP (RiscV) by Succinct.

While all these ZK-EVMs aim to prove the same EVM blocks, they currently accept unique, vendor-specific inputs. This hinders operators who need to work with multiple vendors and does not allow to achieve a neutral and open supply chain for real-time block proving.

This post proposes a standardized EVM data format for ZK-EVM Prover Input that:

  • EL clients can generate for every block.
  • ZK-EVM provers accept to generate EL proofs.

The Prover Input format aims to facilitate the creation of a neutral supply chain for real-time block proving by:

  • Facilitating multi-proof proving infrastructure: Allowing operators to work seamlessly with multiple ZK-EVM prover vendors by always passing the same input to every ZK-EVM prover engine.
  • Enabling the creation of a standard interface: Between EL clients (Execution Layer full clients executing block) and the multiple proving infrastructures running ZK-EVM(s) prover (proving the blocks).

ZK-EVM Prover Input

Workflow

When dealing with ZK-EVMs, we can broadly distinguish three types of data for generating the block’s proof:

  1. The Prover Input: The EVM data required by the ZK-EVM engine to execute the block and generate the Execution Trace. This is vendor-agnostic.
  2. The Execution Trace: An intermediary input generated by the ZK-EVM engine for each block, required by the proving engine to generate the final proof. This is vendor-specific.
  3. The Proof: The final output of the prover, the proofs execution and state transition. This is the vendor-specific

Statelessness

ZK-EVM proving engines, when proving a block, operate in a stateless environment without direct access to a full node. Therefore, the Prover Input must include the block witness, which consists of the minimal state and chain data required for EVM block execution (executing all transactions in the block, applying fee rewards, and deriving the post-state root).

Prover Input Data

We propose the following format for Prover Input data:

Item Description Rationale
Version A string field indicating the version of the prover input. The required prover input may evolve over time, so the format needs to be versioned.

Another use case is to enable to extend the existing format for other EVM chains to include some specific data.
Blocks Blocks to be proven, including:
Header of the block to be proven.
Transactions: The list of the RLP-encoded transactions of the block to be proven.
Uncles: The list of uncle block headers.
Withdrawals: The list of validator withdrawals for the block.
Necessary to compute the block hash, create the EVM Context, execute transactions and finalize the block.
Blocks’ Witness Minimal state and chain data required for EVM block execution, including:
Pre-State: The list of all RLP-encoded Merkle Patricia Trie nodes resolved during block execution (from both the account trie and the storage tries, mixed in a single list).
Codes: The list of all smart contract bytecodes called during block execution.
“• Ancestors: The list of block headers, containing at least the direct parent of every block and optionally older ancestors if accessed with the BLOCKHASH opcode during block execution.”
Necessary data to execute the blocks.
Chain Configuration The chain configuration, including all hard forks. The proving infrastructure will generate proofs for multiple chains. Passing the chain configuration in the Prover Input enables a ZK-EVM instance running in a proving infrastructure to be chain-agnostic and generate proofs for multiple chains.

Note: This does not include the total_difficulty accrued as of the parent block, which is necessary for fork selection in a pre-merge context. Assuming proving pre-merge blocks is not absolutely necessary, we keep this open for discussion.

In JSON format, it gives:

{
    "version": "...",
    "blocks": [ 
        {
            "header": {...}, 
            "transactions": [ 
                "0x...",
                ...
            ],
            "uncles": [{...},...],
            "withdrawals": [{...},...]
        }
    ],
    "witness": {
        "state": [ 
            "0x....",
            ...
        ],
        "codes": [ 
            "0x....",
            ...
        ],
        "ancestors": [ 
            {...},
            ...
        ]
    },
    "chainConfig": { 
        "chainId": ...,
        "homesteadBlock": ...,
        "daoForkBlock": ...,
        "daoForkSupport": ...,
        "eip150Block": ...,
        ...
    }
}

Prover Input Format

We are currently evaluating various options for Prover Input formats (e.g., Protobuf, SSZ, RLP) and compression (e.g., gzip). The primary goals are to:

  • Reduce Prover Input size: Speed up network communication, which is crucial for real-time block proving.
  • Ensure compatibility: Support all major programming languages and existing blockchain tooling.

Batching Blocks in a Single Prover Input

To enable batching and optimize proving costs, we propose a Prover Input containing a list of blocks (instead of a single block).

This allows setting the witness for all the blocks at once, so there is no duplication when multiple blocks access the same account, storage, headers, or codes.

In the context of real-time block proving, which requires a proof per block, the prover input will contain only a single block, but other use cases may benefit from a list.

Storing Prover Input

Beyond posting Prover Input to proving infrastructure for real-time block proving, Prover Input can be reused for other use cases by any agents. We are considering options to also store Prover Inputs on:

  • Data Availability layers (e.g., Avail, Celestia): Ideal for making input available temporarily, allowing all provers to generate proofs before purging the data.
  • A shared data bucket (e.g., S3): Public for reads, with policies in place to freeze older data.

Extending to Other EVM Chains

The Prover Input format can be easily extended to other EVM chains by using a specific version. For example, in the case of Optimism, the OP-specific chain configuration fields would also be included.

10 Likes

Ooh this is a good point.

My preference is toward using serialization formats that are Ethereum-native (ie. SSZ; not RLP because we are trying to get rid of RLP). The reason is that eventually we want to use these techniques at L1, and at L1 we also eventually want to put the Ethereum block data into blobs. And so we would love to be able to use the provers that get created for L2s “as-is” to prove L1 blocks, given only the L1 block header as a public witness.

(Note that I don’t mean overfitting to the standards of today, rather I mean ideally we can have a collaborative standards process where both L1 and L2 can agree on the final outcome)

4 Likes

That’s a really interesting proposal!!

I agree this would facilitate a lot the integration with any ZKVM-backend and make them all participants and candidates to lead ZKEL.

I have a couple of questions or remarks:

  1. I think this can be generalized but to some extend only. What I mean by that is that if we assume that ZKVMs will have different backends (Plonky3, GKR(if How to Prove False Statements: Practical Attacks on Fiat-Shamir doesn’t just reck it) etc… And more importantly, different co-processors. This means that for some of them, we will need to send some extra auxiliary data hints to the proving backend. While some might do constraints for a certain check, others we might perform lookups to prove certain parts, thus requiring sorting. What if some team uses base-4 decomposition for certain witness that needs to be range-checked while another one prefers to use a byte-based lookup decomposition check? I just see too many cases where this will be really complex to make uniform if we want to avoid another Execution Trace-kind of step.
  2. Why would that be a requirement for this to be standarized? I agree that the Proof and the Prover Input do actually need to be if we want good interop. But this intermediate data that no-one else will read aside from the specific prover-backend of each ZKVM is something really hard to standarize that will probably impact performance at the cost of generality. (And will likely still force some ZKVM designs to actually have another step to adapt to their specifics).
  3. I agree with Vitalik on RLP encoding being avoided. In fact, I’d avoid ProtoBuff too. There’s just so many nuances in lots of different data types (at least on it’s 3rd version IIRC). Can’t we just stick to some good compression algorithm that brings a good performance/compression ratio? I was checking this for Blobs indeed and found decent sources: lzturbo - Compression Benchmark and Comparison of Compression Algorithms - LinuxReviews (more assessment needed ofc)

What’s the exact use case for that? To re-do a proof? What kind of thing will enforce that? I’m curious!!
In this case, IIUC we would be trading off Trace -> ProverInput time by Storagecosts. Is that the case?
If so, is it really worth it? I remember when we build the first ZKEVM exploration that the Prover Input generator wasn’t a crazy cost (although nowadays, it might very-well be arround 10-25% of the whole proving process time?
I assume it would be nice to see how much is witgen taking to teams relatively to the whole Proof generation time in order to go towards this direction.

1 Like

The idea of the standard is to define a set of data that will be sufficient for any ZK-EVM to generate an EL proof. Each ZK-EVM is free to process the prover input as needed in order to generate the proof, this may require to generate intermediary inputs that are ZK-EVM vendor-specific and that are not meant to be part of the standard.

This is not meant to be part of the Prover Input standard. The Prover Input are on a standard format then the proving infrastructure and ZK-EVM are free to convert it into a specific optimized format.

If you see the EL proof generation as a sequence of data processing steps, starting from a full node data and ending with a proof, the prover input is the data the most advanced in the processing sequence that is still ZK-EVM vendor-agnostic, any further processing steps are in the vendor-specific realm of the ZK-EVM.

We can fairly assume that an open and neutral supply chain for real-time block proving, will involve multiple proving infrastructures each of which running one or more ZK-EVMs.

At some point in this supply chain a full node EL client will have to generate the prover input necessary for the ZK-EVM to generate their proof. The point of standardizing the Prover Input is to not have to implement/maintain/run EL clients for each ZK-EVM, and instead having a single Prover Input standard that is accepted by every ZK-EVM, making the job of proving infrastructures lighter.

A second use case, is to standardize the interface between the different agents involved in the real-time block proving supply chain. Let’s for example imagine that real-time block proving will require the validator proposing a new block to signal proving infrastructures that a new block is about to be proposed so proving infrastructures can start proving while the block is propagated, an option would be for the validator to post the prover input.

1 Like