Block Prover v3

[rpanic]

Currently, we have 1:1 relationship between the BlockProof and the aggregated TransactionProof of that given block with respect to the proveBlock() circuit method.
This has the drawback of having to create a Proof for every block, even if that block is empty. This has the consequence of becoming very expensive for low-throughput appchains since they'll constantly have to do proving work, even though nothing is happening.

The technique proposed to fix this is very similar to the one we use in the STBatches architecture: We can aggregate all TransactionProofs of a given Settlement on a side-channel once per settlement, then batch-prove all blocks of that settlement on another sidechannel, and on both keep a tracker of the Block -> Transaction[] structure. And then at the end, merge both together and check the equality of the tracker.

This should have performance benefits for both busy and empty appchains. In the case of no transactions, the sequencer only has to prove the block hooks (which should be fairly cheap and batches might reach 100s of blocks)

Specification: BlockProver & TransactionProver Architecture

1. Preliminaries

Produce and Reconcile

This BlockProver uses a pattern that we already use in the STProver, we call it the "produce and reconcile" pattern.
In essence, this pattern is a way to batch a lot of operations that have various relationships with a distinct operation (a circuit) to minimize the amount of verification dependencies.
Gemini describes it as "decoupling Execution Verification from Structural Consensus to enable parallel proving".

To make that clearer, let's start with the problem that we try to solve. The setting that we are in allows us to recursively verify proofs from other circuits, but the crucial limitation here is that we can only verify two proofs at a time. Now, lets think of our relationship, where we have a set of blocks, where every block has a set of transactions in them.
To prove the correctness of this construction, the naive way to do this, is to let every BlockProof consume one (recursively merged) TransactionProof. But the caveat with this is that we can fit a maximum of two blocks into every proof (since the maximum amount of TransactionProofs we can consume is 2).

The produce and reconcile pattern solves this:

1. Produce (TransactionProver):
   Executes business logic blindly, generating a cryptographic log (BundleList) of all batches that are executes, along with their inputs and input state. It proves the validity of transaction execution without validating the wider context of blocks - it just assumes they are correct.

2. Reconcile (BlockProver):
   The BlockProver does the exact opposite of the TransactionProver: It executes only the wider context of blocks, while assuming validity of the transaction execution. Concretely, it provides the inputs and input state, but assumes the validity of a given set of transactions, again collecting everything in its own copy of a BundleList.
   At the end of processing all the blocks, the BlockProver asserts that the BundleList (that both have constructed with their opposite sets of trusted vs. assumed inputs) is equal on both "sides" of the story. It consumes exactly one TransactionProof, containing all transactions from the long list of blocks, and asserts the previous fact.

The heavy lifting of execution is proven in isolation, while the consensus layer simply verifies that both sides did their part sound and complete - ensuring integrity.
This allows both "paths" - all blocks and all transactions - to be proven completely in parallel and only coming together in the end. More importantly, it allows us to minimize the amount of total proofs generated (and recursed over) by cramming 100s of blocks into each BlockProof (since creating a block is a very simple operation).

-- The following is generated by gemini and only adapted/corrected by me

2. Core Concept: The Bundle & BundleList

The central synchronization primitive between the two provers is the BundleList, implemented as a Provable Hash List.

2.1 The Bundle

A Bundle represents the aggregate effects of an ordered list of transactions within a block. It serves as a commitment to "what happened" during execution and what all the inputs were.

Structure:

• transactionsHash: A commitment to the list of transactions executed in this bundle.
• networkStateHash: The network state (timestamp, block height, globals) used during the execution of these transactions.
• pendingSTBatchesHash (FieldTransition): A generic transition (From -> To) commitment representing the accumulation of State Transitions (STs) generated by the runtime code and hooks.
• witnessedRootsHash (FieldTransition): A transition commitment representing the Merkle roots accessed/witnessed during execution. This is currently unused and should always be a noop.

2.2 The BundleList Mechanism

The BundleList acts as a "Has-Done" list.

1. Accumulation: As the TransactionProver proves transactions, it pushes new Bundle objects onto this list or updates the current one.
2. Commitment: The resulting TransactionProof output contains the commitment of this list (bundlesHash).
3. Verification: The BlockProver uses this hash to ensure the blocks it is building exactly match the transactions that were proven.

---

3. TransactionProver

The TransactionProver is responsible for generating a proof of correctness for the application layer. It operates recursively to batch multiple transaction executions.

3.1 Primary Workflows

proveTransaction

Proves a single transaction execution.

1. Input Verification: Accepts a DynamicRuntimeProof (The corresponding proof of Runtime execution).
2. Before Hooks: Executes beforeTransaction hooks. Resulting state transitions are pushed to pendingSTBatches.
3. Bundle Accumulation: The transaction is added to the current Bundle state and the STs are pushed to the pendingSTBatches.
4. After Hooks: Executes afterTransaction hooks. Resulting STs are pushed to pendingSTBatches.
5. Validation:
   • Validates transaction signatures.
   • Matches the transaction hash against the runtime output.
6. Output: Updates the TransactionProverState by adding the current execution artifacts to the bundleList.

proveTransactions (Optimization)

A specialized leaf optimization that proves two distinct runtime executions (runtimeProof1, runtimeProof2) in a single step before merging. This reduces the recursion depth of the proof tree by one level.

---

4. BlockProver

The BlockProver is the settlement-facing circuit. It manages the L2 blockchain progression.

4.1 Inputs

• TransactionProof: The proof from Section 3.
• StateTransitionProof: A proof from the StateTransitionProver attesting that applying a specific list of STs to Root A results in Root B.
• BlockArgumentsBatch: Plaintext data describing the blocks to be proved.
• deferSTProof / deferTransactionProof: Boolean flags allowing for "optimistic" accumulation during intermediate steps, ensuring expensive verifications happen only once per batch.

4.2 The Verification Loop (proveBlockBatch)

The BlockProver iterates through the provided batch of blocks and performs the following reconciliation:

Step 1: Reconstruct the Target Bundle

For every block in the batch, the BlockProver calculates what the Bundle should look like based on the block arguments:

• It computes the expected transactionsHash.
• It computes the expected networkStateHash (result of running the block hooks).
• It computes the block's final pendingSTBatchesHash (beforeBlock + all transactions + afterBlock).

Step 2: Verify Transaction Execution (The "Consume" Step)

The BlockProver checks the TransactionProof.

• It asserts that the bundlesHash output by the TransactionProof is equal to the bundleList constructed from the block arguments.
• Concept: "The execution proof claims it produced Bundles [A, B]. I have constructed Bundles [A, B] from the block data. They match."

Step 3: Verify State Transitions

• Fast-Forward: We use the resulting pendingSTBatches list of Steps 1 and 2 to determine the exact list of STBatches that need to be proven.
• Matching: It asserts that the StateTransitionProof actually applied that specific list of STs.
  • StateTransitionProof.publicOutput.batchesHash must equal TransactionProof.pendingSTBatchesHash.

Recall that the process for state transitions here also uses the "produce and reconcile" pattern.

Step 4: Apply to Global State

• If the ST proof is valid and matches the transaction bundle, the BlockProver updates its stateRoot using the output of the StateTransitionProof.
• In addition to everything above, for every block, the BlockProver also updates the blockHashRoot (Merkle tree of block history).

---

5. The Coordinated Flow (Visualized)

The process utilizes a "Produce and Reconcile" pattern.

graph TD
    %% Subgraph for the Inputs
    subgraph Inputs [Inputs / Sequencer Data]
        RawTxs("Transaction inputs (signature, network state, ...)")
        BatchArgs(Block Arguments Batch)
        RuntimeProof(Runtime Proofs)
    end

    %% Subgraph for Transaction Prover
    subgraph TxProver [TransactionProver]
        direction TB
        TP_Logic["<b>Proving logic</b> (verifying runtime proof + executing hooks)"]
        
        %% Internal Accumulators
        subgraph BundleState [Internal Accumulators]
            TP_BundleList["<b>BundleList</b><br/>(The 'Has-Done' List)"]
            TP_STBatches["<b>Pending ST Batches</b><br/>(Generated Side Effects)"]
        end
        
        TP_Logic --> TP_BundleList
        TP_Logic --> TP_STBatches
    end

    STP_Output[<b>ST Proof</b><br/>From Root -> To Root<br/>Commitment to ST Batches]

    %% Subgraph for Block Prover
    subgraph BlockProver [BlockProver]
        direction TB
        BP_Reconstruction["<b>Block Reconstruction</b><br/>(Builds expected BundleList from BatchArgs)"]
        
        %% The Core Verification Logic
        subgraph Verification [Verification & Alignment]
            Check1{<b>Check 1:</b><br/>Bundles Match?}
            Check2{<b>Check 2:</b><br/>STs Match?}
            UpdateState[<b>Update Global State</b><br/>State Root & Block Tree]
        end 
    end

    %% Connections - Data Flow
    RawTxs --> TP_Logic
    RuntimeProof --> TP_Logic
    
    %% Transaction Proof Flow
    TP_BundleList -->|Transaction Proof| Check1
    TP_STBatches -->|Transaction Proof| Check2

    %% Block Construction Flow
    BatchArgs --> BP_Reconstruction
    BP_Reconstruction -->|Expected Bundles| Check1

    %% State Transition Flow
    STP_Output -->|Witnessed STs| Check2
    STP_Output -->|New Root| UpdateState

    %% Annotations for the Checks
    style Check1 fill:#d4edda,stroke:#28a745,stroke-width:2px
    style Check2 fill:#d4edda,stroke:#28a745,stroke-width:2px
    
    linkStyle default stroke-width:2px,fill:none,stroke:gray;

Loading