Paper 2026/2689

Weir: Bounded-Memory Indexing and Proving with Sequential Storage

Abstract

A low-memory prover must control sumcheck tables, sparse accesses, commitments and proof assembly. We present Weir, a Shockwave-derived protocol with a complete read-write (RW) index-and-prove schedule. The schedule restores sparse request order, retains commitment state through later openings and assembles the proof externally. These steps preserve the direct RAM prover's canonical bytes across buffer choices, with a common verifier. Under an external-query-tape model, the schedule uses $O(B+\log T)$ field RAM, constant digest RAM and polylogarithmic auxiliary RAM. Algebraic work and record traffic are quasilinear; oracle-query byte work is charged separately. A classical random-oracle analysis bounds knowledge error. Fused Split-Butterfly-Merge removes $n-1$ materialized transform passes at length $2^n$. Its ordered routing contract extends to multiplicative-coset Reed-Solomon (RS) and recursive foldable encoders; component checks match reference codewords, traffic counts and RS fold states. In a fixed 64 MiB worker-cap grid, RW completes all tested matrix and Poseidon inputs; RAM completes matrix dimension 8. Within the matrix grid, the largest RW point has 64 times as many padded constraints as that RAM point, using 3.33 MB prover RSS and 9.51 minutes index+prove. We report latency, external payload, query bytes, proof size and verification time for this offline operating range.