Adds a frame type for quantum-resistant Signature and STARK Aggregation
This supports signatures and STARKs (for privacy or for eg. L2s) in a post-quantum world in a highly gas-efficient way, by providing a way for transactions to declare them as “dependencies”, in a way that allows the mempool and the block builder to replace them with a recursive STARK proving that they all exist.
This is exactly the direction where a receipt/dependency layer becomes important.
Post-quantum signatures and STARKs are too heavy to treat as isolated per-transaction checks. The interesting layer is the verifiable record of what each transaction depends on, and how those dependencies can be aggregated, replay-protected, and audited later.
A concrete question about omission accountability:
If a builder receives a valid signature or STARK dependency but does not include it in the recursive aggregate, does the proposed frame provide any durable evidence that the dependency was received?
The aggregate can prove validity of the included dependencies, but it may not prove that all valid dependencies submitted to the builder were included.
Is this intentionally left to the mempool/builder protocol, or could the frame commit to a dependency identifier or receipt that enables later inclusion or omission checks?
I see the EIP is drafted around the SPHINCS signature scheme. Are lattice-based signatures being considered, and if not why is that?
We want to be minimalistic with dependencies, and have a strong preference to keep the base layer purely hash-based for that reason.
It also means we have to maintain less total infrastructure.
That makes sense.
So the clean boundary seems to be:
- the base frame stays minimal and hash-based;
- the aggregate proves validity of included dependencies;
- omission accountability, if needed, belongs to a surrounding mempool / builder / receipt layer.
A minimal approach would be a hash-only dependency receipt: commit to the submitted dependency identifier, submission context, timestamp/slot, and builder endpoint/session, without adding new signature dependencies to the base layer.
That would keep the EIP minimal while still allowing later inclusion / omission checks outside the core frame.
There’s a broader design principle here beyond the specific cryptography, and Vitalik’s reply gets at it directly: keep the base layer minimal, prefer hash-based dependencies, and avoid carrying more permanent infrastructure than necessary.
That looks a lot like classic narrow-waist architecture: keep one small, stable interface in the middle, and allow the systems around it to evolve independently.
commitment → specialised mechanism → proof → verification
Authentication will change. Privacy tech will change. Execution environments will change. The stable layer only needs enough information to bind those pieces together safely.
The important point is that complexity doesn’t disappear. It moves to layers where it can continue to be upgraded, replaced, audited, and improved without forcing every change into consensus-critical infrastructure.
I think the same discipline applies to coordination protocols. They should capture the durable facts what was proposed, who agreed, and under what conditions without absorbing every authentication or execution mechanism into the core.
ERC-8001 happens to follow that pattern by committing to payloads and conditions while leaving execution outside the core. But that’s really just one instance of the broader idea.
Keep the narrow waist small. Let everything around it keep evolving.
One boundary I would keep explicit in that narrow waist: a commitment to the set that was included is not automatically evidence that nothing valid was omitted.
The reusable pattern we just ran into elsewhere is that completeness is always relative to an enumerable admission domain. Without a committed admission set or sequence, a recursive proof can prove every included dependency is valid while saying nothing about dependencies the builder received and silently left out.
So I’d separate two claims:
inclusion validity — every dependency represented by the frame/proof is valid;
admission-relative completeness — every dependency that entered a committed, enumerable admission domain is accounted for.
The first fits naturally in the narrow waist. The second needs an explicit admission commitment outside or alongside it; otherwise “nothing was omitted” becomes a stronger claim than the frame can support.
That seems consistent with keeping the base layer hash-only: the core need not know why a dependency was admitted, only what committed domain later completeness claims are relative to.
Vitalik’s update today made the implementation boundary here worth testing directly.
I tested whether an arbitrary LeanSTARK program can enter current leanVM recursion without adding a universal wrapper solely to preserve program identity.
The relevant invariant is:
if state omitted from the recursive statement can be changed and flip validity, the statement is incomplete.
For an arbitrary inner program, verify_sub already exposes an exact deferred evaluation of that program’s bytecode. I bound that claim to an authenticated commitment to the program and discharged it inside the outer proof using leanVM’s existing WHIR opening machinery.
The first construction failed at the recursive Merkle opening. The failure reduced to two independent openings consuming an aliased witness stream. Keeping those witness streams distinct produced:
ARBITRARY_VERIFY_SUB_PASS=true
EXACT_DEFERRED_BYTECODE_CLOSURE_PASS=true
ARBITRARY_DIRECT_LEANSTARK_KERNEL_PASS=true
Program substitution is rejected as well.
So the direct relation now demonstrated is:
arbitrary program + proof
↓
verify_sub
↓
exact deferred bytecode claim
↓
authenticated program commitment
↓
in-circuit WHIR opening
↓
valid LeanSTARK dependency
This gives a concrete implementation of the generic verification-key-hash transformation assumed by 8288: the full verification material can remain witness data while the dependency commits to its verification identity. The EIP can keep the narrow interface (scheme, data_hash, verification_key_hash) without losing the program identity required to reproduce the validity judgment.
Once that boundary closes, the recursive construction reduces to:
direct valid dependencies
+ valid recursive children
↓
union
↓
discard
↓
sort / deduplicate
↓
deps_hash
↓
same relation again
The implementation proof is running against current leanVM in Actions run 34413454829.
The remaining object is the single self-recursive 8288 guest that performs that whole transition and emits the same statement type it consumes. Once that guest reaches a stable identity, that identity can become the candidate AGGREGATED_VK.
I have not found another state that must cross the recursive boundary to preserve the validity judgment. A counterexample would be any state outside the commitment whose substitution can make a previously valid dependency invalid, or vice versa.
Following up on my last post: I still don’t see another state that has to cross the recursive verifier boundary itself. I do see one remaining binding one layer outside it.
For mode 0, validation explicitly requires that deps equal the sorted, deduplicated union of the dependencies declared by the wrapper’s transactions.
For mode 1, the listed checks require recursive_stark.deps_hash == hash(deps) and a valid recursive proof, but do not explicitly require recomputing deps from transactions. That leaves a simple falsifier.
Suppose dependencies(T) = {A} and a mode-1 wrapper contains transactions = [T], deps = [B], and a valid recursive proof for {B}.
The proof can be valid and its deps_hash can match hash(deps), while the dependency actually required by T — A — was never proven.
So I think mode 1 needs the same explicit package binding as mode 0:
deps == deduplicate_and_sort(union(dependencies(tx) for tx in transactions))
and then:
recursive_stark.deps_hash == hash(deps)
The distinction is that a valid proof of dependency set D does not establish that D is authoritative for transaction package P unless D == dependencies(P).
This is separate from the earlier omission-accountability question. No outside admission set is needed here; the wrapper already declares the transaction set whose dependencies it claims to cover.
The same rule also makes discard precise: recursion may discard a dependency while constructing a successor aggregate, but the resulting package cannot retain a transaction that still requires that dependency.
For a wrapper containing only a previously broadcast transaction hash, the receiver also has to resolve that transaction before deriving the package dependency set. The recursive proof cannot establish its own scope; the transaction set defines that scope.
I’d add one negative test: keep deps and the valid recursive proof fixed, replace the wrapper’s transaction set with one whose canonical dependency set differs, and require rejection.
So the additional closure condition is:
valid proof of D != proof that D is authoritative for P
until:
D == dependencies(P).
If the intended interpretation is that the wrapper-level definition of deps already makes this equality normative for mode 1, then I think the fix is simply to make that recomputation explicit in the mode-1 validation rules and test cases. The same explicit check would be useful for FOCIL as well.
@vbuterin @pipavlo82 and everyone following the thread —
Thank you for the precise questions on omission accountability and the broader receipt/dependency layer. They highlight an important design boundary that is worth locking in clearly.
The current EIP-8288 surface correctly focuses on inclusion validity: the recursive STARK proves that every dependency declared by the transactions that actually land in a valid block is authentic. It does not (and, in my view, should not) attempt to prove admission-relative completeness — i.e., that a builder received a particular valid dependency and then chose to omit it. That stronger claim requires an explicit, enumerable admission domain, which would enlarge the consensus-critical interface and re-introduce the very infrastructure burden the proposal is trying to avoid.
A clean way to close the gap without compromising the narrow-waist design is to treat omission accountability as a first-class but out-of-band concern. One concrete next step would be a minimal companion pattern (or small follow-up document) for a hash-only dependency receipt:
• Commit only to (dependency_id, submission_context, slot_or_timestamp, builder_session).
• Keep it purely hash-based and outside the DEP_VERIFY frames.
• Enable later inclusion/omission audits and replay protection without adding any new signature or STARK dependencies to the base layer.
This keeps EIP-8288 itself lean and future-proof while still giving the mempool/builder ecosystem the durable evidence it needs. It also aligns with the preference already expressed for remaining hash-based at the protocol core.
Caught the PQTS breakout call. Thought I’d give some input on what looked like translation problems to me, and really the main problems I saw coming out of that call.
VALID PROOF(D)
does not imply
AUTHORITATIVE FOR P
until
D = dependencies(P)
and
VALID PROOF(D, VK)
does not imply protocol validity until
VK = protocol-authorized AGGREGATED_VK
So, in PQTS terms:
transaction P
→ derive canonical dependencies(P)
→ bind each dependency to its verification identity
→ prove exactly that dependency set
→ bind deps_hash
→ verify under the fixed recursive guest identity
→ for a block, independently recompute dependencies(block)
→ require equality with block_deps_hash
→ native verifier accepts proof
→ only then does the block acquire validity.
Wrote this up a year ago, adding as is - so not aligned with the full 8288 spec as it is right now, but I want to raise the main idea.
We should not think about the STARK aggregator only as an efficiency mechanism for the hash based signatures. We can use it as a “partially PQ secure” way of continuing to use ECDA/EdDSA signatures (that wallets already support). If we don’t have a real break in ECC in the next couple or years - it will allow all those ECDSA signatures to stay safe onchain and solve the HNDL attack risk.