Dora: Processor Expressiveness is (Nearly) Free in Zero-Knowledge for RAM Programs
Aarushi Goel
Abstract:
Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-off: 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 (which diminishes performance).
In this talk, I will present Dora, a concretely effiicient 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 is also highly generic and only assumes the existence of linearly homomorphic commitments. 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.
This is based on joint work (https://eprint.iacr.org/2023/1749) with Mathias Hall-Andersen and Gabriel Kaptchuk.
Bio:
Aarushi Goel is currently a postdoc at NTT Research, mentored by Sanjam Garg. She obtained her PhD in 2022 from Johns Hopkins University, where she was advised by Abhishek Jain. She has a broad interest in cryptography and in related areas of security and theoretical computer science. The focus of her recent works has been on the design of secure multiparty computation protocols and zero-knowledge proof systems.