Paper 2025/039

VDORAM: Towards a Random Access Machine with Both Public Verifiability and Distributed Obliviousness

Abstract

Verifiable random access machines (vRAMs) serve as a foundational model for expressing complex computations with provable security guarantees, serving applications in areas such as secure electronic voting, financial auditing, and privacy-preserving smart contracts. However, no existing vRAM provides distributed obliviousness, a critical need in scenarios where multiple provers seek to prevent disclosure against both other provers and the verifiers, because existing solutions struggle with a paradigm mismatch between MPC and ZKP that limits the development of practical multi-prover ZKP front-ends. This gap arises because MPC protocols are optimized for minimal computation, whereas ZKPs require a complete trace for proving. Furthermore, adapting RAM designs is also challenging, as vRAMs are not built for the high costs of oblivious execution and existing DORAMs lack public verifiability. To address these challenges, we introduce CompatCircuit, the first multi-prover ZKP front-end implementation to our knowledge, designed to bridge this gap. CompatCircuit integrates collaborative zkSNARKs with novel MPC protocols, unifying computation and verification into a single compatible circuit paradigm. Building upon CompatCircuit, we present VDORAM, the first publicly verifiable distributed oblivious RAM. VDORAM reconciles the high communication latency of online MPC with the complexity of offline proof generation, resulting in a RAM design that balances these competing demands. We have implemented CompatCircuit and VDORAM in approximately 15,000 lines of code, demonstrating their practical feasibility through extensive experiments, including micro-benchmarks, comparative analysis, and program examples.

Note: Accepted in NDSS Symposium 2026