Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs
This page was written by an AI model to give a high-level overview of the paper. Please check the paper for detail: IACR ePrint.
In verifiable outsourcing, a weak client (or every validator of a blockchain) hands a computation to an untrusted server, which returns the result plus a short proof that it computed correctly. The standard tool is a zkSNARK (zero-knowledge succinct non-interactive argument of knowledge): proofs are a few hundred bytes and check in milliseconds, but producing one costs thousands of times more than running the computation. Many such computations read and write state, for example a RAM holding every account balance in a payment system. The client keeps only a short digest of that memory, and the server must prove that the computation, started from the memory the digest names, ends in the memory the new digest names.
zkSNARKs prove statements written as arithmetic circuits: fixed networks of additions and multiplications over a large prime field. A circuit has no notion of reading address idx when idx is only known at run time, so memory has to be emulated, and the emulation dominates the cost. Existing approaches encode cryptography inside the circuit. A Merkle tree costs one collision-resistant hash (about 300 constraints even for the circuit-friendly Poseidon hash) per tree level for each read, two for a write. RSA accumulators avoid the dependence on memory size but carry about 10 million constraints of fixed overhead. For memory that starts at zero ("volatile" memory), prior proofs sort the accesses by address, and proving that sort costs something that grows with the address-space size.
The paper's approach is to write each memory check as an algebraic interactive proof (AIP): a protocol in which the prover sends vectors of field elements, the verifier answers with random challenges, and the verifier's final test is an arithmetic circuit. The authors generalize an existing zkSNARK, Mirage, into CP-Mirage+, which compiles any such AIP into a zkSNARK whose proving time is governed by the size of the AIP verifier's circuit. Its commit-and-prove (CP) form lets the memory be committed as a Pedersen vector commitment that is checked outside the circuit, so no hash function needs to be encoded as constraints. The design goal then becomes simple to state: build memory-checking AIPs whose verifier circuit is as small as possible.
The main new tool is Bézout's identity for polynomials. To show that addresses a1, ..., aA are all distinct, both sides form z(X) = (X − a1)···(X − aA); a repeated address is a repeated root, which z shares with its derivative z′. The prover sends polynomials s and t with z·s + z′·t = 1, which exist only when z and z′ share no root, and the verifier checks the identity at one random point. That costs 4A + O(1) constraints instead of the Θ(A2) of pairwise checks. The paper builds three memories on this kind of reasoning: volatile RAM (group accesses by address instead of sorting them), persistent RAM with N committed cells (pick out the touched cells with a randomized multiset hash), and sparse persistent RAM with at most C non-zero cells in a huge address space (variants of the test that tolerate the dummy address 0).
For persistent RAM, the implementation reduces constraint counts by up to 98.2× and proving time by up to 51.3× against the Merkle and RSA implementations of prior work, with the best results for mid-size memories (210 ≤ N ≤ 220). For volatile RAM, the verifier cost is the first to be independent of the memory size N, but the measured gain is modest: at most a 32.9% proving-time reduction for N up to 260. For sparse persistent RAM, a cost model (not a full implementation) predicts up to 143× fewer constraints. In a simple payment rollup, where signature checks dominate, constraints drop by up to 2.55×. Proofs are 500 bytes and verify in about 9 ms.
Key takeaways
- Emulating RAM inside a zkSNARK is expensive because prior methods put cryptography (Merkle hashes, RSA accumulator operations) or address-size-dependent sorting into the circuit.
- The paper writes memory checks as algebraic interactive proofs and compiles them with CP-Mirage+, a generalization of Mirage; proving cost then tracks the AIP verifier's circuit size, and committed memory is checked outside the circuit.
- Bézout's identity turns "these addresses are distinct" (or "these two sets are disjoint") into one polynomial identity checked at a random point, at linear cost.
- Persistent RAM: up to 98.2× fewer constraints and 51.3× faster proving than Merkle and RSA baselines, best for 210 ≤ N ≤ 220. Volatile RAM: verifier cost independent of N, but at most 32.9% faster proving.
- Sparse persistent RAM is evaluated with a cost model (up to 143× fewer constraints); a rollup case study gains up to 2.55× because signature checks dominate.
Memory checking as algebraic interactive proofs, compiled into zkSNARKs
The background, why RAM is costly in a circuit, the AIP-to-SNARK compiler, the Bézout uniqueness test, the three memories, and the measurements.
1 · Background: zkSNARKs and arithmetic circuits
A SNARK lets a prover P convince a verifier V that it knows a secret input (the witness w) satisfying some relation R(x, w) with a public input x. It is succinct (the proof is small and checking it costs time polynomial in the logarithm of R's size plus the size of x), non-interactive (a single message from P to V), and an argument of knowledge (an accepting P must in effect know w). A zkSNARK is also zero-knowledge: the proof reveals nothing about w beyond the fact that it exists. Concretely, the paper cites proofs of a few hundred bytes that verify in a few milliseconds, while proving costs time and memory "thousands of times higher" than the original computation.
Most SNARKs, including Groth16, the construction this paper builds on, prove statements written as an arithmetic circuit over a prime field F (here p ≈ 2255). The usual encoding is a rank-1 constraint system (R1CS): a vector z of all the circuit's values must satisfy
Each row says "a linear combination of variables times another linear combination equals a third", so each non-linear multiplication in the circuit costs one constraint, and additions are nearly free (general knowledge). Proving time grows with the number of constraints n: for Mirage+ it is dominated by O(n log n) field operations for Fourier transforms and O(nλ / log n) group operations for multi-scalar multiplications (MSMs), where λ is the security parameter. Constraint count is therefore the paper's main cost metric.
2 · Why RAM is expensive inside a circuit
A circuit is fixed before the inputs are known, so it cannot compute mem[idx] for a run-time idx by wiring. Memory must be emulated by checking a transcript of accesses: a list of (address, value, write-bit) tuples that P supplies and V checks for read-over-write (RoW) consistency, meaning every read returns the most recent write to that address. The paper treats three cases:
| Memory | Initial and final state | Example use |
|---|---|---|
| Volatile | Starts at zero; final state is not kept | Scratch memory of a RAM program being proven |
| Persistent | N cells; initial and final states are committed with a short digest | Account balances of a payment system, carried from proof to proof |
| Sparse persistent | Address space nearly all of F (e.g. N ≈ 2256), at most C (e.g. 220) non-zero cells | Addresses that are hashes of identifiers such as an email address |
For persistent memory, prior work checks the transcript against a digest with cryptography encoded as constraints. The costs (the paper's Table 2, using estimates from Ozdemir et al., USENIX Security 2020):
| Approach | Constraints for A accesses to N cells | Where the cost comes from |
|---|---|---|
| Linear scan | 3 · N · A | Every access touches every cell |
| Merkle tree | 600 · A · log N | One hash per tree level for a read, two for a write; about 300 constraints per Poseidon hash |
| RSA accumulator | 10M + 4k · A | About 5M per Wesolowski proof verifier, about 2k per accumulator insert or delete; the prover also computes a 2048N-bit RSA exponentiation |
| This work | 3 · N + 41 · A | Outside the constraints: two size-N multi-scalar multiplications in G1 |
For volatile memory, prior proofs sort the transcript by address and then time, and prove (1) the sorted copy is a permutation of the original, (2) it is correctly ordered, and (3) it satisfies RoW. Steps (1) and (3) already have linear-cost proofs. The ordering step is the problem: every prior ordering proof has a verifier cost that depends on N, because showing ai ≥ ai−1 means range-checking a difference, by bit-splitting (TinyRAM) or lookups into a table of size about N (Arya, Haböck).
3 · Algebraic interactive proofs and CP-Mirage+
An interactive proof is a conversation in which P tries to convince a probabilistic polynomial-time V of a claim. It must be complete (true claims are accepted) and sound (false claims are accepted only with negligible probability). It is public-coin if V's messages are just uniform random values. The paper defines an algebraic interactive proof (AIP) as a public-coin interactive proof in which every message is a vector of field elements and V's final test is an arithmetic circuit. An AIP need not be succinct or zero-knowledge.
Its encoding is I-R1CS (interactive R1CS): over μ rounds P sends wi and receives random ri, and V accepts if Az ∘ Bz = Cz for z = (x, r1, ..., rμ, w1, ..., wμ). Randomness matters because many facts are cheap to check at a random point: two different polynomials of degree d agree at a random field element with probability at most d/|F| (the Schwartz-Zippel lemma), which is negligible for |F| ≈ 2255.
- Mirage+ generalizes Mirage (Kosba et al., USENIX Security 2020), itself a generalization of Groth16, from two rounds to μ rounds. Each round's prover message is committed as a group element (with a fresh blinding value), and the Fiat-Shamir transform replaces V's random challenges with hashes so the result is non-interactive. Theorem 1: a complete, knowledge-sound I-R1CS becomes a zkSNARK in the generic group model.
- Cost. Verification takes O(ℓx + μ) time; a proof is μ + 2 elements of G1 plus 1 of G2. Proving cost is driven by n, the number of I-R1CS constraints, which is the size of the AIP verifier's circuit. So "make proving cheaper" becomes "make the AIP verifier smaller".
- CP-Mirage+ adds commit-and-prove: parts of the witness (the initial and final memory) are bound to Pedersen commitments, and a commitment-linking proof ties them to the SNARK. The commitment is checked with group operations outside the circuit, instead of hashing the memory inside it (Theorem 2).
4 · The core tool: uniqueness via Bézout's identity
Bézout's identity for polynomials says that polynomials s, t with f·s + g·t = h exist exactly when gcd(f, g) divides h. With h = 1, s and t exist exactly when f and g share no factor. The uniqueness proof (Protocol 1) uses this to show that a1, ..., aA are distinct, which naively takes Θ(A2) pairwise disequality checks:
- Encode the list as roots. Both parties define z(X) = ∏i(X − ai). Its roots are all simple exactly when the ai are distinct, because a double root r makes z = (X − r)2f, and then z′ also vanishes at r.
- P sends Bézout coefficients. P sends the coefficients of s (degree ≤ A − 2) and t (degree ≤ A − 1) with z·s + z′·t = 1.
- V tests at one random point. V samples α and checks z(α)s(α) + z′(α)t(α) = 1. It evaluates s and t by Horner's rule, and z and z′ with a running recurrence: zj(α) = zj−1(α)(α − aj) and z′j(α) = zj−1(α) + z′j−1(α)(α − aj).
- Cost and soundness. The circuit has 4A + O(1) constraints. If the list has a duplicate, z·s + z′·t − 1 is a non-zero polynomial of degree ≤ 2A − 2, so V wrongly accepts with probability at most (2A − 2)/|F| (Theorem 3).
The prover needs s and t. The textbook route is the fast extended Euclidean algorithm, which has large constants (22A log2A in the worst case) and is hard to parallelize. The paper instead observes that z(ai) = 0, so the identity forces t(ai) = 1/z′(ai). Its divide-and-conquer algorithm builds z with a product tree, evaluates z′ at every ai, interpolates t from the inverses, and computes s = (1 − z′t)/z. The optimized version, UniqBez, runs in at most 4.5A log2A + O(A log A) field operations (Theorem 4).
5 · Volatile memory: group, do not sort
The paper's first observation is that sorting by (address, time) is sufficient but not necessary. It is enough that the reordered transcript is grouped by address and time-ordered within each group: let gi = 1 mark the first access of a group; then each adjacent pair needs gi = 1 or ti > ti−1, and the addresses of the group heads must be unique. The order of the groups does not matter, because different addresses are independent (proved in Appendix C.1).
- Conditional uniqueness. The uniqueness proof generalizes to "the ai with gi = 1 are distinct": P leaves the other ai out of z, and V uses a conditional recurrence that multiplies by (α − aj) only where gj = 1. The circuit grows to 6A + O(1).
- The rest is standard. Permutation, within-group time ordering and RoW use existing linear-cost techniques, written as AIPs in Appendix C.
| Reference | How accesses are arranged | Verifier cost for A accesses, size-N memory |
|---|---|---|
| TinyRAM | Sorted, via bit-splitting | Θ(A(log A + log N)) |
| Arya | Sorted, via lookups | ΘA(log N / log log N), ΘN(A) |
| Haböck | Sorted, via lookups | ΘA(log N / log log N), ΘN(A) |
| Per-cell initialization (three works) | Other tools | Θ(A + N) |
| This work | Grouped by address, time-ordered within groups | Θ(A) |
The paper's Table 1. ΘA means the constant may depend on A. The trade-off is on the prover side: UniqBez makes P's cost O(A log2A), but the paper argues that verifier size is the concrete bottleneck once the AIP is compiled.
6 · Persistent memory: extract the touched cells
Now the initial and final states are vectors m and m′ of N field elements, each committed with CP-Mirage+. P sends the list a of addresses the transcript touches, with their initial values v and final values v′. Two sub-proofs follow.
- Selecting active cells (Πactive). V samples β and treats each (value, address) pair as the field element v + βa. P sends the hashes h of the N − A untouched cells. V samples α and checks two products: ∏(α + mi + iβ) = c · ∏(α + vj + ajβ) for the initial state and the same with m′ and v′ for the final state, where c = ∏(α + hi) is shared. Sharing h is what forces every untouched cell to be unchanged. Cost: 3N + 2A + O(1) constraints, soundness error at most (N2 + 2N + A)/|F| (Theorem 5).
- Why P sends hashes, not pairs. Sending the untouched (address, value) pairs and letting V hash them would save one round and give a tighter soundness bound, but would add N − A constraints. The paper picks the cheaper verifier because extra rounds cost little in CP-Mirage+.
- Transcript validity. The transcript is the time-0 initializations, the A real accesses, then time-(A+1) finalizations. Group-start bits are set in the original transcript (1 for initializations, 0 otherwise) and carried through the permutation, so the conditional uniqueness step disappears.
The overall cost is 3N + 41A constraints. The N term comes from Πactive; the 41 per access is measured by regression on the Section 9.2 experiments. Relative to Merkle or RSA, the improvement comes from not encoding hashing or Wesolowski proofs as constraints.
7 · Sparse persistent memory: punctured tests
With an address space nearly all of F, the state is stored as C (address, value) pairs, where address 0 marks an empty slot (and must hold value 0) and all non-zero addresses must be unique. P sends, for each active cell, its address and value before (bj, vj) and after (b′j, v′j) the accesses. A slot may go from empty to used, so V only requires b′j = bj when bj is non-zero, via the constraint (b′j − bj)bj = 0. The new difficulty is proving that the final non-zero addresses are unique while many slots repeat the address 0.
- Plain uniqueness fails. With d ≥ 2 copies of 0, Xd−1 divides both z and z′, so no s, t with z·s + z′·t = 1 exist. A conditional uniqueness proof plus indicator bits works but costs 8C + O(1).
- Punctured uniqueness (Protocol 3). P instead sends c, the number of extra zeros, and s, t for the de-duplicated list, and V checks z·s + z′·t = Xc at a random α. This shows that 0 is the only repeated root. Cost: 4C + O(log C), soundness error at most (C + A − 1)/|F| (Theorem 6).
- Punctured disjointness (Protocol 4). A persistent memory proof is one link in a chain of proofs over the same committed memory, so each proof can assume its input addresses are unique and only prove its output addresses are; induction covers the chain. The non-zero differences dj = b′j − bj are exactly the newly created addresses, so it suffices to show that {ai} and {dj} share nothing except 0: with f having roots a and g roots d, P sends c, s, t with f·s + g·t = Xc. Cost: 2C + 2A + O(log C) (Theorem 7).
| Approach (sparse, capacity C) | Constraints | Other bottlenecks |
|---|---|---|
| Linear scan | 3 · C · A | |
| Sparse Merkle tree (depth ≈ 256) | 150k · A | |
| RSA accumulators plus batched non-membership | 30M + 8k · A | 2048C-bit RSA exponentiations |
| This work | 7 · C + 51 · A | 2 MSMs over G1 of size 2C |
The paper's Table 3, a cost model. The 7C is 3C from active-cell selection, C for extra hash evaluations and 2C from punctured disjointness; the per-access term is the dense RAM's 41 plus a conservative 10. The paper notes that for very large C (say C > 225), Merkle trees look best, because only their cost is independent of C.
8 · Implementation and evaluation setup
- Proof system. CP-Mirage+ is a patch to bellman, a Rust implementation of Groth16: 2.4k lines plus 1.3k lines of tests, including a linear-subspace proof (Kiltz and Wee) and the commitment-linking proof of LegoSNARK (Campanelli, Fiore and Querol).
- Compiler. The CirC compiler infrastructure is extended so its intermediate representation can express public-coin interactive proofs and its R1CS backend can emit I-R1CS (about 4k lines of Rust). A compiler pass replaces memory operations with the new RAM proofs, and TinyRAM's and Arya's memory proofs are reimplemented for comparison (about 2k lines).
- Programming interface. In CirC's Z# language, an array argument marked
committedbecomes persistent memory (the SNARK includes commitments to its initial and final states), and a local array markedtranscriptbecomes volatile memory. Ordinary array syntax is used for reads and writes. - Baselines. Volatile: TinyRAM, Arya and Haböck. Persistent and sparse: Merkle trees and RSA accumulators (the implementation of Ozdemir et al., USENIX Security 2020) and a linear scan.
- Metrics. Constraint count (platform-independent and correlated with proving time), proving time, and in some experiments Setup time, verifier time and proof size. Sparse persistent memory is compared through the Table 3 cost model only.
9 · Results
| Experiment | Range | Headline |
|---|---|---|
| Volatile, constraints | N ∈ {220, 240, 260}, A ∈ {25, ..., 210} | Up to 20% fewer than the best baseline, at A = 25, N = 260 |
| Volatile, proving time | N ∈ {240, 260} | Up to 32.9% lower; Haböck is sometimes better, so the best choice depends on N and A |
| Persistent, constraints | N ∈ {210, 215, 220}, A ∈ {25, ..., 212} | Up to 98.2× fewer, at N = 215 |
| Persistent, proving time | N ∈ {215, 220}, A up to 3000 | Up to 51.3× lower, at N = 215, A = 211 |
| Sparse persistent (modeled) | C ∈ {210, 215, 220}, A ∈ {25, ..., 212} | Up to 143× fewer constraints, at C = 215, A = 212 |
| zk-Rollup (payments) | N up to 220 accounts | Up to 2.55× fewer constraints than the prior state of the art |
Verifier time is 6 to 10 ms for all systems in Table 4. The paper explains why the proving-time gain (51.3×) is a little below the constraint gain (98.2×): CP-Mirage+ adds a commitment-linking proof, and many of its witness values depend on uniformly random 255-bit challenges, which slows bellman's MSMs compared with RSA's mostly small witness values. In the rollup, each transaction checks a signature, which costs the same in every system, so the relative advantage is smaller than for memory alone.
10 · Limits the paper states
- Volatile gains are small in practice. The baselines depend on N only mildly, and the new proof replaces only the ordering part of the memory proof, so the concrete gain tops out at 32.9% (proving time) for addresses up to 60 bits, and Haböck's method sometimes wins.
- Prover cost of uniqueness. UniqBez makes the volatile prover O(A log2A); the paper argues the verifier size still dominates concrete proving time.
- Where persistent RAM wins. The advantage shrinks against Merkle trees for small A or large N, and against a linear scan for very small N. RSA's large fixed overhead amortizes as A grows, though its per-access cost stays higher than C&P's.
- Sparse RAM is modeled. Its numbers come from the cost model, and for very large capacities (C > 225) sparse Merkle trees appear better.
- Proof size and soundness. C&P proofs are 500 bytes against 308 bytes for the baselines. Πactive's soundness error, O(N2/|F|), is looser than an alternative protocol's N/|F|, which the paper judges immaterial given CP-Mirage+'s own soundness error.
FAQ
Q·What is the difference between volatile and persistent memory here?▾
Volatile memory exists only during one proof: it starts at zero and its final contents are discarded, like the heap of a program being proven. Persistent memory outlives the proof: its initial and final contents are committed, so a chain of proofs can each pick up the memory where the previous one left it, as a blockchain rollup does with account balances. Sparse persistent memory is persistent memory over an enormous address space (nearly all of a 255-bit field) in which at most C cells are non-zero.
Q·Why can a circuit not just index into an array?▾
A circuit's wiring is fixed before the inputs are known, so there is no gate that selects element idx for a run-time idx. The direct alternative, comparing the index against every cell, costs about 3·N constraints per access (the paper's linear scan). Memory-checking proofs avoid that by letting the prover supply the values read and then proving that the whole list of accesses is consistent.
Q·Where does the interaction go? The final proof is non-interactive.▾
The memory checks are designed as interactive proofs because random challenges let the verifier test polynomial identities cheaply. Mirage+ then commits to each prover message and applies the Fiat-Shamir transform, which replaces each verifier challenge with a hash of the transcript so far. The result is a single proof message, analyzed in the generic group model.
Q·Why does proving time depend on the verifier's circuit?▾
Because the SNARK proves that the AIP verifier would accept. The verifier's final test is encoded as n rank-1 constraints, and the prover's dominant work (Fourier transforms and multi-scalar multiplications) scales with n. A smaller AIP verifier means fewer constraints and a faster prover, which is why the paper reports verifier complexities such as 4A + O(1) and 3N + 41A.
Q·Is the result still zero-knowledge if the AIPs are not?▾
Yes. The paper's AIPs need not be zero-knowledge or succinct; CP-Mirage+ adds both. Each committed prover message carries a fresh blinding value, so the compiled proof is a CP-zkSNARK. The paper notes that its goal is efficiency, for which a CP-SNARK would suffice, but zero-knowledge comes with the construction.
Q·What does Bézout's identity buy over sorting or pairwise checks?▾
Pairwise disequality for A addresses costs Θ(A2), and proving a sort costs range checks whose size depends on the address-space size N. The Bézout test turns "all distinct" into one statement, z·s + z′·t = 1, that the prover backs with two polynomials and the verifier checks at one random point, at 4A + O(1) constraints regardless of N. Variants with Xc on the right side tolerate repeated zeros (punctured uniqueness) or show two sets share only 0 (punctured disjointness).
Q·How does this compare to a Merkle tree for persistent state?▾
A Merkle proof encodes about log N hashes per read (two per level for a write), at roughly 300 constraints each for Poseidon, so its cost is 600·A·log N in the paper's model. The new proof costs 3N + 41A: linear in memory size but with a small constant per access. That is why the gain is largest for mid-size memories and many accesses, and shrinks for small A or large N. For sparse memory with very large capacity (C > 225), the paper expects sparse Merkle trees to be best.
Q·Why are the volatile-memory gains so much smaller than the persistent ones?▾
The paper gives two reasons: the best baselines depend on N only mildly (roughly log N / log log N), and the new proof improves only the ordering part of the memory check, while the permutation and read-over-write parts stay the same. Constraints drop by up to 20% and proving time by up to 32.9% for N up to 260, and Haböck's lookup-based method is sometimes better. The improvement is mainly asymptotic: the first volatile proof whose verifier cost does not depend on N.
Q·Does it need a trusted setup?▾
The construction extends Groth16, whose Setup samples secret field elements to produce proving and verification keys (Protocol 5). Setup runs once per application and is the most expensive step measured: 28 s to 598 s for C&P in Table 4, versus about 1215 s for RSA and 2087 s to 2914 s for Merkle. That this per-circuit setup must be trusted is general knowledge about Groth16-style systems, not a point the paper discusses.
Q·How large are the proofs and how fast is verification?▾
A Mirage+ proof is μ + 2 elements of G1 and one of G2, where μ is the number of rounds. In Table 4, C&P proofs are 500 bytes against 308 bytes for the Merkle and RSA baselines, and verification takes 9 ms for C&P and 6 to 10 ms for all systems.
Q·Is this related to lookup arguments?▾
Lookup arguments prove that values appear in a fixed table, which the paper describes as essentially read-only memory. Prior volatile RAM proofs (Arya, Haböck) use lookups to range-check address differences, which brings in a table whose size depends on N. The new volatile proof avoids range checks by grouping accesses instead of sorting them. A concurrent work (Zhang et al., ASIACRYPT 2023) also builds volatile RAM from Bézout's identity, but does not treat persistent or sparse memory.
Q·What does the evaluation not cover?▾
Sparse persistent memory is compared only through a constraint cost model, not an implementation. The persistent proving-time plot leaves out non-cryptographic transcript computation, which Table 4 reports separately (and which is also faster for C&P). Memory sizes are moderate: N up to 220 for persistent RAM and accesses up to 212. The paper does not describe the benchmark machine. The application study is one rollup, where the gain (up to 2.55×) is limited by signature verification.