Paper 2024/325
Proofs for Deep Thought: Accumulation for large memories and deterministic computations
, New York University, New York UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Proof systemAccumulation SchemeIncrementally Verifiable Computation
- Contact author(s)
-
bb @ nyu edu
jessicachen @ nyu edu - History
- 2024-04-22: revised
- 2024-02-26: received
- See all versions
- Short URL
- https://ia.cr/2024/325
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/325,
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{https://eprint.iacr.org/2024/325}},
url = {https://eprint.iacr.org/2024/325}
}
