Paper 2024/979
Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs
Abstract
In verifiable outsourcing, an untrusted server runs an expensive computation and produces a succinct proof (called a SNARK) of the results. In many scenarios, the computation accesses a RAM that the server maintains a commitment to (persistent RAM) or that is initially zero (volatile RAM). But, SNARKs for such scenarios are limited by the high overheads associated with existing techniques for RAM checking. We develop new proofs about volatile, persistent, and sparse persistent RAM that reduce SNARK proving times. Our results include both asymptotic and concrete improvements---including a proving time reduction of up to 51.3$\times$ for persistent RAM. Along the way, we apply two tools that may be of independent interest. First, we generalize an existing construction to convert any algebraic interactive proof (AIP) into a SNARK. An AIP is a public-coin, non-succinct, interactive proof with a verifier that is an arithmetic circuit. Second, we apply Bézout's identity for polynomials to construct new AIPs for uniqueness and disjointness. These are useful for showing the independence of accesses to different addresses.
Note: Revision 1: update for camera-ready publication version.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. IEEE S&P '25
- Keywords
- zkSNARKsmemory proofsinteractive proofs
- Contact author(s)
-
aozdemir @ cs stanford edu
emlaufer @ stanford edu
dabo @ cs stanford edu - History
- 2024-10-19: revised
- 2024-06-18: received
- See all versions
- Short URL
- https://ia.cr/2024/979
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/979,
author = {Alex Ozdemir and Evan Laufer and Dan Boneh},
title = {Volatile and Persistent Memory for {zkSNARKs} via Algebraic Interactive Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/979},
year = {2024},
url = {https://eprint.iacr.org/2024/979}
}
