Paper 2023/1749

Dora: A Simple Approach to Zero-Knowledge for RAM Programs

Abstract

Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness tradeoff: supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (diminishing performance). We present Dora, a very simple and concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora’s approach is united by intuitive abstraction we call a ZKBag, a cryptographic primitive constructed from linearly homomorphic commitments that captures the properties of a physical bag. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step. Our evaluation shows that Dora has notably better end-to-end performance than concurrent work targeting the same problem.

Note: The initial eprint version of this paper reported that Dora offered slower proving times for both processor execution and updating memory than concurrent work. This was due to an error in our evaluation that compared the performance of Dora on an 128-bit field to concurrent work on a 61-bit field. The evaluation presented in this version is more accurate. The conference version had a typo when comparing to concurrent work, which is fixed in this eprint version.