[ethresear.ch] [Cryptography] Paranoid EIP-8288: heterogeneous recursion with an authenticated class bank

EIP-8288 proposes recursive aggregation under a fixed protocol-level verification key. One backend choice worth exploring is whether recursive steps should support several approved proof sizes, so that small aggregates can use a smaller proving relation.

I implemented this kind of heterogeneous recursion in Parano1d, where small and large recursive state-transition proofs already run on a public mainnet. The construction uses a finite authenticated bank of verifier classes. I recently published the paper, and I think the mechanism is relevant to the aggregation backend being discussed here.

Carrying deferred checks across classes

A verifier class fixes a relation, its constraint matrix, polynomial commitment parameters and transcript layout. Classes share a public accumulator layout, while their witness dimensions, matrices and commitment geometries can differ. The permitted classes and their ordered bank digest are authenticated public parameters.

The part that needs care is deferred verification. Replaying a parent proof leaves a matrix-evaluation claim that must remain accounted for through subsequent recursive steps, including steps using another class.

The bank has one accumulator lane per class. At step k, let i_k be the current proof’s class and i_{k-1} its parent’s class. Replaying the parent emits a fresh matrix claim f_{k-1}. The update is:

The current class selects the new outer relation. The parent class selects the lane being updated. Every other lane, including its live bit, is carried exactly.

For example, after four proofs with classes 0,1,0,1, lane 0 accounts for claims f_1 and f_3, lane 1 accounts for f_2, and f_4 remains the fresh tip claim.

Terminal verification checks that fresh tip claim and every live lane against their authenticated matrices. Assuming backward correctness of the folds, the bank invariant gives correctness of every fresh matrix claim along the selected ancestry. Section 6 of the paper proves this invariant and gives the two-phase matrix fold and its public-coin reduction bound.

The authentication also covers how specialized hash reductions connect to the outer proof. They refer to exact slices of the committed trace. The verifier derives their opening claims, and those claims are checked in the same code-based polynomial commitment proof. The fold transcript binds the class, route and input claims before sampling its challenges.

This builds on non-uniform IVC and per-relation accumulation, including SuperNova. Here the construction is instantiated in a transparent proof system over binary tower fields, with different parent-verifier geometries and an explicit terminal check of all accumulated matrix obligations.

There is a cost to keeping the bank: public accumulator state and terminal work grow with the supported classes. Each recursive relation also includes capacity for the approved parent-verifier arms.

Applying this to aggregation

The implemented construction follows one parent per recursive step. For EIP-8288, the next construction to work out is a merge of several child banks, bound to the aggregate’s dependency set.

Each required child-verification obligation would need to be checked inside the merge or carried into the resulting bank. The merge invariant would also need to cover the dependency list’s union, deduplication and discard rules. A fixed terminal relation would then have to recognize the approved classes and close all remaining obligations under the protocol-level verification key.

There is also a connection to Exposing an ISA for post-quantum proofs on Ethereum. Program identity names the computation being proved; class identity authenticates the concrete proof configuration used to prove it. Supporting several classes for one program would need an explicit rule establishing their semantic compatibility.

I would like feedback on three questions:

1. What would be a useful merge invariant for child banks when the output dependency set supports deduplication and discards?
2. For small and large aggregation workloads, when would a finite class bank justify its accumulator and terminal costs compared with one largest-size relation?
3. How should a stable program/ISA identity be associated with the permitted verifier classes as proof-system parameters change?