Paper 2024/325

Proofs for Deep Thought: Accumulation for large memories and deterministic computations

Benedikt Bünz, New York University
Jessica Chen, New York University

We construct two new accumulation schemes. The first one is for checking that $\ell$ read and write operations were performed correctly from a memory of size $T$. The prover time is entirely independent of $T$ and only requires committing to $6\ell$ field elements, which is an over $100$X improvement over prior work. The second one is for deterministic computations. It does not require committing to the intermediate wires of the computation but only to the input and output. This is achieved by building an accumulation scheme for a modified version of the famous GKR protocol. We show that these schemes are highly compatible and that the accumulation for GKR can further reduce the cost of the memory-checking scheme. Using the BCLMS (Crypto 21) compiler, these protocols yield an efficient, incrementally verifiable computation (IVC) scheme that is particularly useful for machine computations with large memories and deterministic steps.

Note: Added section on performing accumulation step in sublinear time.

Available format(s)
Cryptographic protocols
Publication info
Proof systemAccumulation SchemeIncrementally Verifiable Computation
Contact author(s)
bb @ nyu edu
jessicachen @ nyu edu
2024-04-22: revised
2024-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benedikt Bünz and Jessica Chen},
      title = {Proofs for Deep Thought: Accumulation for large memories and deterministic computations},
      howpublished = {Cryptology ePrint Archive, Paper 2024/325},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.