MLE-DB

A balance is a table entry. MLE-DB stores those entries as the values of a multilinear polynomial—the format Sumcheck consumes. Updating one entry changes one value, without rebuilding an authentication path for each access inside the execution proof.

The protocol separates three jobs: routing keys to entries, committing the state, and checking the execution’s reads and writes. The key-binding column and overflow stash are authenticated along with the value table. Initial and final memory records are anchored to the corresponding epoch commitments.

No per-access path hashing does not mean no hashes. Commitments still bind the data; the memory check verifies that execution agrees with it.

The accepted transition binds its profile, epoch, predecessor root, complete execution trace, and successor root. Key relocation moves the current value with the key; deletion distinguishes an empty slot from an occupied zero value. A non-inclusion proof covers both candidate locations and the authenticated stash.

The transition contract fixes the operation order, word arithmetic, routing policy, eviction rules, and stash behavior. Every intermediate operation must be valid: two valid endpoint states do not justify a transition that would overflow midway. The verifier checks the complete resulting layout as well as the logical key-value state before deriving the successor root.

A versioned Merkle profile supports complete-state and sparse transition witnesses under the same verification rules. Sparse witnesses authenticate every location demanded by execution or relocation, together with the complete stash. Unopened subtrees retain their committed hashes. An admitted context keeps its routing policy fixed across successors.

The paper’s state-access model compares B × log2(N) × 300 for Merkle-Poseidon2 with B + N for MLE-DB. N is the number of entries and B the number of accesses. These are model units, not a measured speedup for an entire proof or blockchain.

At N=2^20 and B=1,000,000, the ratio is 2,928.86×. At N=2^30 and B=2,000,000, it is 16.73×. The benefit depends on how much work touches the state; commitment updates, key binding, trace anchoring, and the rest of the proof must also be accounted for.

Criterion microbenchmarks, release mode, Intel Core Ultra 7 255U, Windows x86-64, October 8, 2026. Each run uses a one-second warmup, two-second measurement, and 1,000 samples. These are local operations, not durable storage or end-to-end proof timings.

Each durable mutation records its identity and pre-state before modifying data. Recovery keeps a committed value or restores the recorded pre-state. Restoring an absolute value is idempotent: restarting recovery does not subtract the update twice.

The persistence contract requires an actual durable medium, ordered flushes, atomic control markers, and a valid recovery record. A heap-backed test cannot establish survival through a physical power cut. A consistent rollback of an uncommitted write is not a promise that no write is ever lost.

For 16,384 slots and 64 operations opening 32 slots, a cached sparse witness reduced the measured local producer, encode/decode, and verifier path by 2.16–2.19× across three separate native Windows release runs, each with 31 paired samples. Both paths enforce the same exact transition and Merkle profile. Initial database setup is excluded; one-time cache admission is measured separately and excluded from the steady path.

The serialized proofs contain 13,968 bytes for the sparse path and 1,344,798 bytes for the complete-state path. Operation transport and network framing are separate. These measurements exclude Jolt proving, durable database mutations, network transfer, and Ring0 finality.

Workload matters: the dense absent-read control was slower with sparse verification. Smaller witnesses do not imply lower CPU cost for every transition. The complete-state verifier remains the comparison baseline.

The verifier compares the products encoding read-and-final records with write-and-initial records over GR(2^64,155). Challenges come from a uniformly sampled Teichmüller set of size 2^155, where distinct challenge differences are invertible. Trace encoding preserves distinct residues; commitments anchor both boundary states.

For a nonzero difference polynomial of degree D, the collision bound is D/2^155. Composition adds the Sumcheck error and the binding and authentication reductions. A 128-bit bound applies only when the complete error budget is at most 2^-128; it is not obtained merely by using 64-bit words or a large ring.

Every access consumes the current memory-version token and produces a newer token bound to execution. Final records carry the last version actually produced, including an unchanged initial version for untouched state. Product equality is checked together with chronology, coverage, legal value changes, and authenticated boundary states.

The degree budget includes boundary records: a dense epoch with B accesses and N boundary entries has product degree at most N+B, with one leading term cancelled when both cardinalities agree. Uniform whole-ring sampling has the same normalized D/2^155 bound; the Teichmüller domain supplies unit differences and a smaller challenge representation. The security budget covers repeated epochs as well as a single proof.