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

TY - GEN

T1 - Dora

T2 - 31st ACM SIGSAC Conference on Computer and Communications Security, CCS 2024

AU - Goel, Aarushi

AU - Hall-Andersen, Mathias

AU - Kaptchuk, Gabriel

PY - 2024/12/9

Y1 - 2024/12/9

N2 - 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.

AB - 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.

KW - Linearly Homomorphic Commitments

KW - RAM Programs

KW - Zero-Knowledge Proofs

UR - https://www.scopus.com/pages/publications/85215518882

U2 - 10.1145/3658644.3690213

DO - 10.1145/3658644.3690213

M3 - Article in proceedings

AN - SCOPUS:85215518882

SP - 869

EP - 883

BT - CCS 2024 - Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security

PB - Association for Computing Machinery

Y2 - 14 October 2024 through 18 October 2024

ER -