From Proof Trees to Proof State

1. Introduction

zkVMs let a verifier check that a program ran correctly without re-running it. They execute a compiled program, record a trace of registers, memory, and input/output events, arithmetize that trace, and prove that its transitions obey the machine rules [1]. For large executions, the trace is split into segments so that leaf proofs can be generated in parallel. The remaining engineering problem is composition: how does a verifier learn that all segment proofs are valid and that segment i ends exactly where segment i + 1 begins?

The common answer is recursive proof aggregation. A circuit verifies child proofs, emits a parent proof, and the process repeats until a root proof remains. Halo is an influential construction of recursive proof composition without a trusted setup [5]. Nova instead builds incrementally verifiable computation from a folding scheme for relaxed constraint instances [6]. SP1, RISC Zero, OpenVM, Pico, Airbender, and Miden are catalogued as using recursive aggregation in a recent zkVM survey [1]. Some systems then wrap the result in a pairing-based SNARK for a compact on-chain object.

We investigate accumulation as a replacement for the intermediate segment-composition layer. We carry local segment statements and continuity constraints in one evolving state, then use a decider or terminal SNARK/STARK wrapper to export a conventional verification object. This may make the repeated composition relation smaller than a general-purpose proof-verifier circuit.

2. Scope and Analytical Method

We analyze deterministic executions represented as an ordered sequence of trace segments. We isolate the composition layer from the guest ISA, trace-generation strategy, and particular polynomial-commitment implementation. We compare the interfaces and asymptotic costs of recursive composition and accumulation, then instantiate the latter with WARP’s polynomial-equation-satisfiability (PESAT) relation. That relation encompasses R1CS, generalized R1CS, and CCS representations [2].

Three distinctions govern the argument. First, a relation proof is distinct from a proof of the verifier for that relation. Second, a batch of valid segment proofs is distinct from a proof that their boundary states form one execution. Third, asymptotic efficiency of an accumulation primitive is distinct from end-to-end zkVM performance. The last distinction is material because arithmetization overhead, code selection, field extensions, Merkle authentication, GPU utilization, and the terminal wrapper can dominate a nominally cheaper composition step.

3. Segmented Execution as a Relation

Number the segments from 1 to N. Let s_i−1 and s_i be the committed boundary states of segment i: program counter, relevant register and memory commitments, public I/O digest, and a segment index. Let w_i contain its private trace and auxiliary witness. Define the segment relation

to mean that the segment follows the zkVM transition rules, begins at s_i−1, ends at s_i, and belongs to the specified program. The global claim has two parts: every segment is valid, and each begins where the previous one ended.

More precisely, let S be the space of committed machine states and let Next_P^L(s, s’; w) denote validity of L steps of program P. For a partition L₁, …, L_N, the desired language is

A secure construction must bind the commitment scheme, domain separation, program digest, segment index, and public input encoding into the Fiat–Shamir transcript.

The contents of s_i are architecture-dependent. In a RISC-style zkVM they may include a program counter, register-file commitment, memory-root commitment, and system-event digest. In a modular AIR design they may additionally include interaction-bus state, lookup-table commitments, and chip-local boundary values. The SoK emphasizes that ISA choice determines trace geometry and that memory checking varies from Merkle-based online checks to offline permutation, logarithmic-derivative, and timestamp-based arguments [1].

4. Recursion and Accumulation Are Different Primitives

Recursive composition uses a succinct argument ARG = (P_ARG, V_ARG). Its parent circuit takes child proofs as witness data and constrains V_ARG to accept them. For a binary aggregation tree, an internal relation has the schematic form

where C enforces the boundary connection and any public-input policy. Recursion-friendly fields and fast commitments therefore matter as much as the guest trace.

An accumulation scheme ACC = (P_ACC, V_ACC, D_ACC) instead maintains an accumulator a = (a.x, a.w) with a short public part and a potentially long witness. Given prior state a_i and a new claim (x_i, w_i), the prover returns (a_i+1, pf_i). The update verifier checks the public transition. The decider later receives the complete state. Completeness requires

Knowledge soundness requires more than acceptance of an update transcript: from an accepted update ending in a decider-accepted state, an extractor must recover a witness for the new relation instance and a valid witness part for the predecessor accumulator [2].

To make the update itself succinct, a proof-carrying-data construction can recursively prove that V_ACC accepted. WARP’s comparison isolates the relevant circuit: direct PCD from a generic argument incurs ℓ executions of V_ARG for arity ℓ, whereas accumulation-based PCD incurs one execution of the specialized V_ACC [2, Appendix A].

4.1 Verifier Arithmetization as the Recursive Bottleneck

In a STARK-based zkVM, the outer proof must represent the inner verifier as arithmetic constraints. This includes Fiat–Shamir challenges, Merkle paths, field operations, and proximity checks. The cost and correctness of this circuit become part of every recursive layer [1, 3, 4]. A mismatch between the native verifier and its circuit can invalidate the composition even when both implementations appear to work on honest proofs.

This creates an important implementation trust boundary. The outer proof establishes only that the arithmetic verifier accepted. The intended security statement therefore depends on that circuit implementing the native verifier exactly, including canonical parsing, transcript order, domain separation, challenge derivation, commitment checks, and public-input binding. This is best understood as a verifier-circuit equivalence obligation rather than an additional cryptographic assumption. A missing constraint can preserve every honest test while admitting proofs that the native verifier would reject.

Recursion also requires algebraic compatibility. The child verifier may use a field, extension, hash, or polynomial commitment that is expensive to represent in the parent field. Repeating the construction requires a recursion strategy whose output can itself be verified at the next layer. Curve cycles, as used in Halo, and recursion-oriented STARK designs address this closure problem in different ways [5, 4]. In practice, each conversion between representations enlarges the circuit and creates another place where the recursive statement can diverge from the original verifier.

Accumulation changes the size and shape of this boundary. A proof-carrying construction arithmetizes the specialized accumulator verifier once per update instead of embedding several complete child-proof verifiers [2, Appendix A]. The smaller circuit can be audited against a native reference through differential transcript tests, adversarial mutations, and explicit checks of every public binding. The terminal decider and any final wrapper still require faithful arithmetization. WARP also introduces its own assumptions about knowledge soundness, Merkle binding, extraction, the selected code, the field, and the random-oracle model [2]. Accumulation therefore offers a narrower verifier circuit and a different assumption profile, while end-to-end security continues to rely on equivalence between native and constrained verification.

5. WARP and Hash-Based Accumulation

WARP constructs a hash-based, random-oracle-model accumulation scheme with linear prover time and logarithmic verifier time, supports unbounded depth, and is plausibly post-quantum in the same qualified sense as hash-based SNARKs [2].

At a high level, WARP reduces polynomial-equation satisfaction to a code-based accumulation relation and batches many proximity claims into one. It uses interactive-oracle reductions, Merkle commitments, and Fiat–Shamir. For a polynomial equation system p̂ = (p̂_j)_j∈[M] over N variables, the relation requires p̂_j(z) = 0 for every j.

For ℓ instances and accumulators, WARP states an accumulation prover cost of O(ℓ|p̂| + λ log k) field operations. Its verifier performs O(ℓ(log N + log M + λ) + λ log k) field operations in addition to specified random-oracle queries. Its decider performs O(|p̂|) field operations [2].

WHIR is a fast proximity protocol for constrained Reed–Solomon codes [3]. SWIRL uses WHIR to make recursive aggregation cheaper in a heterogeneous zkVM frontend [4]. WARP raises the question of whether repeated composition can use a specialized accumulator verifier.

6. Accumulator Construction for Segmented zkVM Execution

The accumulator must encode both local correctness and continuity. For each segment, form an instance

where h denotes binding commitments appropriate to the zkVM. The witness includes trace columns, memory-consistency data, and openings required for R_seg. A direct representation would enforce instruction transitions, CPU/ALU constraints, lookup or permutation checks, memory consistency, public I/O, and equality with the prior outgoing state.

The accumulator records the program, segment order, initial and current final states, and a commitment to the accumulated relation.

There are two scheduling options. A streaming prover updates the accumulator as each segment completes, giving low latency but a serial state dependency. A tree-shaped schedule combines partial accumulators and retains more leaf parallelism. We use a bounded running accumulator to limit live memory. Its call schedule and ordering commitments are explicit parts of our statement.

7. Current OpenVM Research: Composing SWIRL with WARP

Our prototype changes where an OpenVM segment proof ends. We run each segment through the established AIR frontend: OpenVM constructs the main and auxiliary traces, SWIRL handles the heterogeneous AIR and LogUp reductions, and the resulting columns are arranged under a stacked Reed–Solomon (RS) commitment. We stop after the constraint and stacked-opening reductions have fixed their claims, before terminal WHIR proximity testing [4, 3].

The SWIRL interactive-oracle reduction (IOR) translates the execution claim at this boundary into the constrained-code relation

The recursive source proof certifies that each R_C instance was derived from the segment’s AIR, LogUp, and stacking reductions. The exported claim is bound to the existing codeword commitment, the reduction transcript, and the code parameters. This type information prevents the prover from silently changing the field, dimensions, coordinate order, or relation version.

7.1 Reusing Committed Data and Certifying WARP Updates

WARP receives the constrained-code source under the same commitment and coordinate order already used by SWIRL. Our adapter binds the root, code parameters, coordinate map, and reduction claim together.

We apply WARP to one setup-fixed relation R_C, following Construction 9.4 of the supplied WARP revision [2, Construction 9.4]. Our running implementation uses bounded calls with a fixed arity of eight, and the schedule is bound into the transcript.

Each call produces one bounded combined recursive leaf. One part verifies the SWIRL reduction and authenticates the exported R_C instances. The other verifies the V_ACC update over those same instances and checks the machine-state boundary.

Once a call is certified, we retain the new accumulator, the compact leaf proof, and the public endpoints. We release consumed traces and temporary commitment data.

7.2 Reconciling a Running Chain with the Block Statement

WARP groups segments into calls, while the application describes one ordered block. We bind both views through a canonical manifest and a rolling digest. The recursive leaves expose their segment ranges, VM boundaries, and accumulator endpoints. A final check recomputes the fixed schedule from the manifest.

7.3 Terminal Decision and Optional Export

WARP’s decider establishes the accumulated post-IOR R_C claims, while the codeword side establishes that the decided message is encoded by the RS word under the final accumulator root. WHIR supplies the terminal constrained-opening and proximity argument. The standalone proof combines the recursive source/history proof, terminal R_C Decide, and the same-root WHIR obligation. If r_acc is the final WARP root and r_WHIR is WHIR’s initial root, then the terminal proof enforces

together with the precise map between message coordinates and the WHIR linear claim. An RS adjoint may implement that map, and the proof constrains the map and its transcript challenge [2, 3].

A native verifier can check this terminal certificate directly. An EVM deployment will more likely wrap the recursive history root and terminal decision in a proof tailored to the chain’s verifier. Ethereum’s pairing precompile was introduced specifically to make succinct-argument verification practical inside the block gas limit [8]. Its public statement retains the application and verifying-key digests, block manifest, initial and final state, public I/O, and final accumulator instance.

Composition invariant. Let A_t be the accumulator after the t-th WARP call, where that call incorporates a contiguous ordered interval of segments [j_t, j_t+1). Assume that A₀ is the valid empty accumulator, that every source certificate soundly derives its accumulated claim from a valid SWIRL segment reduction, and that every authenticated WARP transition is knowledge-sound. The manifest binds one program, contiguous segment indices, and equal adjacent boundary-state commitments. If the authenticated history covers [1, N+1) and the final decider accepts A_T, then, except with the composed protocol and hash-binding errors,

This follows by extracting each accepted batch and predecessor accumulator in reverse order. Contiguous indices prevent omissions, duplication, and reordering, while boundary equality prevents splicing otherwise valid executions.

8. Performance Implications and Evaluation Criteria

Our proposed composition narrows repeated recursive work to a specialized update verifier and lets the high-volume phase use WARP’s linear accumulator prover. A conventional wrapper gives the ledger a succinct public proof.

The comparison is clearest when the common work is visible. Let T_red cover execution, trace commitments, AIR/LogUp, and stacked-opening reduction. Let T_segWHIR be per-segment terminal WHIR and let T_rec be recursive aggregation. The existing path is approximately

For the experimental seam, write T_acc for native WARP updates, T_cert for the combined recursive leaves and their reduction, and T_dec for terminal decision. Its cost is

The omitted per-segment term must outweigh all four replacement costs. Small blocks may be dominated by terminal work, while long blocks may expose serialization or memory-pressure costs in the running accumulator.

WARP’s random-oracle and field-size requirements must also match the deployed field arithmetic. Translation from an AIR/STARK reduction to PESAT may erase an apparent saving, and the final decider may be too large for direct public verification.

We therefore use a controlled, end-to-end experiment. The recursive and accumulation paths should prove the same programs, boundaries, and public outputs at the same security target and should terminate in comparable public proof formats. We include compute-heavy, memory-heavy, and I/O-heavy workloads because they induce different trace geometry, and we report failed cases alongside any wins. Benchmark parity is meaningful only if both paths certify the same public statement. Section 9 describes that statement.

9. Publication Benchmark: Real Ethereum Blocks

We benchmarked four Ethereum mainnet blocks containing 413–568 OpenVM segments on an NVIDIA RTX 5090, using BabyBear EF4 arithmetic. Each value in Table 2 is the mean of two passes, and every proof verified successfully.

Two timing boundaries are useful. Prove is the SDK proof-generation call itself. Pipeline starts after common workload construction and includes lane-specific setup, proof generation, artifact encoding, and in-process verification. The pass-to-pass spread of proof generation remained below 0.35% for every block.

WARP is 1.51–1.54 times slower during proof generation and 1.34–1.37 times slower across the complete lane-specific pipeline. Setup and post-processing account for a larger fraction of recursive time, which narrows the pipeline ratio without reducing the cost of accumulation itself. The result places WARP in the same performance order as recursive aggregation, but not at prover parity.

The final WARP proof averaged 198.2 kB, against 277.7 kB for recursive, a 28.6% reduction. Steady-state verification averaged 3.437 ms for WARP and 3.467 ms for recursive. The succinct wrapper therefore removes execution depth from the public proof size and verification cost; the remaining accumulation overhead is confined to proving.

Terminal constrained WHIR took only 0.15–0.21 s, and the final wrapper plus recursive adapter took about 0.9–1.0 s. Most WARP time lies in the streamed source-and-accumulation phase, which took 206.7–278.4 s. Transition-certificate synchronization accounts for 28.2–35.2 s within that phase, followed by 19.6–26.7 s in the transition-tree normalization layer. Further prover improvements must therefore target transition certification and normalization rather than terminal WHIR.

WARP averaged 67.4% GPU utilization, compared with 54.2% for recursive, while peaking at 22.2 GiB (about 23 GB) of device memory and 4.3 GiB of host memory. The higher utilization and longer proving time show that the gap comes from additional authenticated accumulation work rather than GPU starvation. WARP remains within the 32 GiB GPU and 64 GiB host-memory limits.

10. End-to-End Statement and Ledger Deployment

The checks described in Section 7 work together: the source and history proofs establish where the claims came from and their order, while the terminal checks establish that the final accumulator is valid and tied to its committed data.

For a ledger, these internal objects are evidence for a simpler public assertion: an ordered batch changes one recognized state into another under a specified program and verification key. A state root is a digest of the application state, while a batch commitment fixes the ordered input data. Ethereum’s validity-rollup documentation describes pre-state, post-state, and batch roots as verifier inputs and advances the canonical state only after proof verification [7]. Following that pattern, our OpenVM wrapper would expose a statement such as

The contract compares s_pre with the state it currently recognizes before accepting s_post. The wrapper constrains the WARP root, call-chain digest, and terminal WHIR data to these public values.

A deployed accumulator proof binds the batch commitment expected by the settlement protocol. Availability and sequencing are handled by the surrounding ledger protocol.

The OpenVM relation certifies signatures, nonces, and spending rules when it checks them and binds the relevant keys or policy digests as public inputs. Our contribution carries one authenticated execution statement from an accepted pre-state to a batch-bound post-state.

11. Conclusion

Accumulation offers a different internal composition boundary: a running proof state and a specialized update verifier. In our prototype, we stop SWIRL before per-segment WHIR, reuse the committed constrained-code source, certify WARP updates, and defer codeword decision to one terminal step. On four 413–568-segment blocks, two passes placed the core WARP prover at 1.51–1.54 times the matched recursive prover and the complete lane-specific pipeline at 1.34–1.37 times its recursive counterpart. The final proof was 28.6% smaller and had comparable steady-state verification latency. This is a credible same-order result, not prover parity or a production-security claim. At the ledger boundary, the proof establishes the transition from an accepted pre-state to a batch-bound post-state.

We are continuing this implementation and evaluation work. For code, benchmarks, and future updates, follow github.com/Loris-EPFL.

1. Y. Yang, Y. Cheng, H. Tang, G. Yang, B. Zhang, and K. Ren. SoK: Understanding zkVM: From Research to Practice. Cryptology ePrint Archive, Report 2026/525, 2026. eprint.iacr.org/2026/525
2. B. Bünz, A. Chiesa, G. Fenzi, and W. Wang. Linear-Time Accumulation Schemes. May 2025. Cryptology ePrint Archive, Report 2025/753. eprint.iacr.org/2025/753
3. G. Arnon, A. Chiesa, G. Fenzi, and E. Yogev. WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification. In Advances in Cryptology–EUROCRYPT 2025, Part IV, LNCS 15604, pp. 214–243. Springer, 2025. Full version: Cryptology ePrint Archive, Report 2024/1586. eprint.iacr.org/2024/1586
4. OpenVM Contributors. SWIRL: Stacked WHIR with Interaction Reductions via LogUp. Public technical report, March 13, 2026. openvm.dev/swirl.pdf
5. S. Bowe, J. Grigg, and D. Hopwood. Recursive Proof Composition without a Trusted Setup. Cryptology ePrint Archive, Report 2019/1021, 2019. eprint.iacr.org/2019/1021
6. A. Kothapalli, S. Setty, and I. Tzialla. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. In Advances in Cryptology: CRYPTO 2022, Part IV, LNCS 13510, pp. 359–388. Springer, 2022. doi.org/10.1007/978-3-031-15985-5_13
7. Ethereum.org. Zero-knowledge rollups. Developer Documentation. ethereum.org/developers/docs/scaling/zk-rollups
8. V. Buterin and C. Reitwiessner. EIP-197: Precompiled Contracts for Optimal Ate Pairing Check on the Elliptic Curve alt_bn128. Ethereum Improvement Proposals, 2017. eips.ethereum.org/EIPS/eip-197
9. P. Gauthier. Revenge of the Atoms. Ledger, March 13, 2026. ledger.com/blog-revenge-atoms
10. Zcash. What are zk-SNARKs? z.cash/learn/what-are-zk-snarks

I, Loris Tran, confirm that this submission is my original work, that I have reviewed and take responsibility for its claims and citations, and that any AI assistance used in research or drafting has been disclosed according to the competition rules.

Loris Tran  ·  September 16, 2026