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

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

Speakers: Huayi Qi

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=u1Iv935x_mc

Overview

This talk addresses a fundamental gap at the intersection of zero-knowledge proofs (ZKP) and secure multi-party computation (MPC): how do you prove to the public that a collaborative computation among multiple parties was performed correctly, without any party revealing their secret inputs? The researchers introduce VDORAM (Verifiable Distributed Oblivious RAM), a system that achieves both public verifiability (anyone can verify the computation was correct via a ZKP) and distributed obliviousness (no party learns another's secrets, as in MPC). The key technical contribution is a novel compat circuit representation that unifies MPC evaluation and ZKP constraint generation, along with new MPC protocols for comparison and equality testing in finite fields that produce all values needed to build valid ZKP constraints.

Background

▶ Watch: Background: ZKP, MPC, and the trust gap for outsiders (0:00)

Non-interactive zero-knowledge proofs (ZKPs) allow a prover with secret input to demonstrate that a computation was performed correctly without revealing the input. The verifier can be anyone and can verify at any time. Secure multi-party computation (MPC) allows multiple parties to collaboratively compute a function on their private inputs without revealing those inputs to each other, under the assumption that at most t parties are adversarial.

The critical limitation of MPC is the trust boundary: the participating parties can trust the output under their collusion assumptions, but outsiders have no such guarantee. If all parties collude, they can fabricate results. This creates real-world problems -- imagine banks and factories running audit algorithms where they have financial incentive to produce false results, or DNA testing scenarios where parties could fake results for inheritance fraud. The 2022 Collaborative zk-SNARKs work partially addressed this through publicly auditable MPC (PAMPC), but assumed a compiler exists that can transfer MPC protocols into ZKP constraints -- a non-trivial challenge the current work addresses.

Key Findings

▶ Watch: The gap: MPC computations that can't become ZKP constraints (4:00)

The researchers identified that the core barrier to combining MPC with ZKP is that not all common MPC computations can be directly expressed as the addition and multiplication operations that ZKP constraint systems require. Specifically:

Comparison Operations: Computing whether A < B in MPC typically uses an underflow method (compute D = A - B and extract the sign bit), but this only works in a ring, not a finite field. ZKP constraints must be built in finite fields, and extracting a single bit is insufficient -- the full bit decomposition is required.

Equality Testing: Checking if A == B in MPC uses inverse computation, but building the corresponding ZKP constraint requires careful formulation using only input and output variables.

Bit Decomposition: The researchers found and improved a 2006 paper that supports extracting all bits in a finite field, producing an improved version that enables valid ZKP constraint generation.

These findings led to the design of MPC protocols that operate in finite fields, support both linear and nonlinear computations, and output all intermediate values needed to construct valid ZKP constraints.

Technical Deep Dive

▶ Watch: Equality testing and constraint building challenges (8:00)

The central technical contribution is the compat circuit (compatibility circuit), a new circuit representation that looks like an arithmetic circuit but includes nonlinear operations: specifically the inverse-or-zero operation and full bit extraction. This circuit can be both evaluated in MPC and used to generate ZKP constraints -- one circuit serving dual purposes.

The compat circuit supports four fundamental operations: multiplication, addition, inverse-or-zero, and full bit extraction. All other computations (comparison, equality testing, etc.) can be expressed as direct compositions of these four operations.

Building on the compat circuit, the researchers constructed VDORAM -- a virtual machine architecture with registers, memory tables, and I/O buffers. The VM uses a register-based ISA (Instruction Set Architecture) that allows programmers to write programs that simultaneously execute MPC and generate ZKP proofs. During execution, provers run the RAM blindly -- they do not know which instructions are executing or whether memory access operations occur, preserving obliviousness.

The implementation integrates with the Collaborative zk-SNARKs project for proof generation, with the MPC protocol layer implemented in C#. The cryptographic assumptions are the same as those required for SNARKs.

Performance: Each party requires 4 CPU cores, 4 GB of RAM, and 20 GB of SSD. Running time is constant regardless of instruction type (expected, since provers run blindly). Memory sorting operations dominate the time cost. The system scales moderately as party count increases but currently only runs on local networks due to high overhead. The researchers acknowledge VDORAM is the slowest RAM compared to systems that provide either verifiability or obliviousness alone -- the cost of achieving both properties simultaneously.

Demo / Proof of Concept

▶ Watch: Compat circuit: one circuit for MPC evaluation and ZKP constraints (10:00)

The researchers demonstrated example programs running on VDORAM, showing compat circuit design and RAM execution. The system was compared against prior works in both the VRAM (verifiable RAM) and DORAM (distributed oblivious RAM) spaces. While VDORAM achieves both properties, it comes at a significant performance cost relative to systems optimizing for only one property.

Defensive Implications

▶ Watch: Performance evaluation: the slowest RAM that does both (16:00)

VDORAM addresses scenarios where multiple parties with competing interests must prove to the public that their joint computation is correct. The practical applications include:

Enterprise Auditing: Banks, manufacturers, or other regulated entities running collaborative audits can generate publicly verifiable proofs that results are correct, even if all parties have incentive to collude on false outcomes.

DNA/Identity Verification: Testing laboratories could be required to produce publicly verifiable proofs of test results, preventing fraud in scenarios like inheritance disputes.

Regulatory Compliance: Any scenario where regulators need assurance that multi-party computations were performed honestly, without requiring trust in any subset of the participants.

The current performance limitations (local network only, high overhead) mean VDORAM is not yet practical for production deployment. Future work focuses on performance optimization and proof compression to make the system viable for real-world applications.

Key Takeaways

• Standard MPC allows participating parties to trust results but provides no guarantees to outsiders; VDORAM adds public verifiability via ZKP
• Common MPC operations (comparison, equality testing) cannot be directly expressed as ZKP constraints; new finite-field MPC protocols are needed
• The compat circuit unifies MPC evaluation and ZKP constraint generation in a single representation supporting four fundamental operations
• VDORAM provers run blindly without knowing which instructions execute, preserving obliviousness while generating zero-knowledge proofs
• The system is currently the slowest RAM in its class due to achieving both verifiability and obliviousness simultaneously
• Practical applications include publicly auditable multi-party enterprise computations and fraud-resistant identity verification

About the Speaker(s)

Huayi Qi recently completed a PhD at Shandong University and is now a postdoctoral researcher at Tsinghua University. His research focuses on the intersection of secure multi-party computation and zero-knowledge proofs, working to bridge the gap between these two foundational cryptographic primitives for practical privacy-preserving computation.