MVP-ORAM: a Wait-free Concurrent ORAM for Confidential BFT Storage

MVP-ORAM: a Wait-free Concurrent ORAM for Confidential BFT Storage

Speakers: Robin Vassantlal

Conference: NDSS Symposium

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

Overview

Bernardo Ferreira from the University of Lisbon (presenting for Robin Vassantlal) introduces MVP-ORAM (Multi-Version Path ORAM), the first wait-free Byzantine fault-tolerant Oblivious RAM. ORAM hides data access patterns in storage systems -- even if data is encrypted, the pattern of which blocks are accessed can reveal sensitive information through inference attacks. MVP-ORAM eliminates client synchronization by allowing multiple clients to operate independently on versioned copies of the ORAM data structures, achieving higher throughput and lower latency than prior fault-tolerant ORAM schemes. The system provides Byzantine fault tolerance (surviving compromised servers, not just crashes), while maintaining obliviousness under skewed access distributions. Benchmarked on BFT-SMaRt, the system achieves stable throughput up to 10 concurrent clients with latency below 140 milliseconds for 50 clients, outperforming the crash-fault-tolerant ConcurORAM in both throughput and latency despite providing strictly stronger security guarantees.

Background

▶ Watch: BFT-SMR basics: surviving server compromises in distributed systems (0:15)

Byzantine Fault Tolerant State Machine Replication (BFT-SMR) enables distributed systems to survive server compromises -- if one out of four servers is compromised, the other three continue correctly. This is the foundation for blockchains and intrusion-tolerant services. Confidential BFT-SMR adds encryption to protect data privacy, but does not hide access patterns -- which blocks clients read or write. These patterns enable inference attacks: if Alice accesses both her block and Bob's block, the pattern reveals a relationship between them.

Oblivious RAM (ORAM) hides access patterns by accessing multiple blocks per request and continuously reshuffling data. However, existing ORAM protocols face two fundamental limitations for BFT integration: no prior ORAM provides Byzantine fault tolerance (only crash tolerance via ConcurORAM), and achieving wait-freedom (every client finishes in finite steps regardless of other clients' delays or faults) while maintaining collision freedom (no two clients access the same block simultaneously) is inherently challenging because traditional collision avoidance requires client synchronization, which prevents wait-freedom.

Key Findings

▶ Watch: The tension: wait-freedom vs collision-freedom in concurrent ORAM (4:00)

First wait-free Byzantine fault-tolerant ORAM: MVP-ORAM combines wait-freedom, Byzantine fault tolerance, and obliviousness -- properties that had not been achieved together previously.

Multi-version approach eliminates synchronization: Instead of locking or coordinating between clients, each client operation creates a new version of the ORAM data structures. Versions are merged when subsequent clients read the current state. This eliminates the need for inter-client communication.

Skewed access distributions maintain security: Under realistic workloads where some blocks are accessed more frequently (the common case in databases), the statistical distance between MVP-ORAM access patterns and random patterns remains near zero even with many concurrent clients.

Outperforms ConcurORAM: Despite providing stronger security guarantees (Byzantine vs crash fault tolerance), MVP-ORAM achieves higher throughput and lower latency than ConcurORAM, directly attributable to the concurrency benefits of wait-freedom.

New security definition required: The researchers formalize asynchronous wait-free ORAM security, which depends on database size, number of concurrent clients, and access distribution. This is weaker than standard ORAM security but is the necessary trade-off for wait-freedom.

Technical Deep Dive

▶ Watch: All data structures moved to server with BFT secret sharing (8:00)

MVP-ORAM is built on Path ORAM, chosen for its minimal client-server interactions (only two rounds). In standard Path ORAM, the client stores a position map and stash locally. MVP-ORAM moves all data structures (tree, position map, stash) to the server, encrypted via the secret sharing of the underlying confidential BFT-SMR system.

A client access requires three server interactions: (1) read the position map and decrypt to find the target block's path, (2) request the path and stash, and (3) perform eviction. Because clients operate independently, concurrent access creates multiple versions of the ORAM tree, position map, and stash. New clients merge existing versions before performing their operation.

To avoid collisions without synchronization, MVP-ORAM exploits two properties: blocks can be read via any path that passes through them (a root-level block can be accessed via any path), and popular blocks naturally migrate upward in the tree (toward the root and stash). This means frequently accessed blocks have many available paths, reducing collision probability. For skewed distributions (the realistic case), the statistical distance from random remains near zero.

The system cannot assume adversaries are unable to inject queries (which could force collisions), leading to the restriction that the adversary model excludes adversarial query injection. A stronger variant (Strong MVP-ORAM) addresses this at the cost of performance by using dummy accesses and sacrificing asynchrony.

Demo / Proof of Concept

▶ Watch: Collision avoidance: popular blocks migrate upward in the tree (10:00)

Implementation was done in Java on top of BFT-SMaRt, a popular Byzantine fault-tolerant replication library. Benchmarks covered 1-50 concurrent clients with 4, 7, and 10 server replicas. Throughput scales to approximately 10 clients before plateauing (due to version management overhead). Latency remains below 140ms for 50 clients. Comparison with Cobra (a non-oblivious confidential BFT store) shows the expected performance gap, while comparison with ConcurORAM shows MVP-ORAM's throughput and latency advantages.

Defensive Implications

▶ Watch: Strong MVP-ORAM variant for adversarial query injection (14:00)

MVP-ORAM enables confidential, access-pattern-hiding storage systems that can survive server compromises. This is relevant for multi-party computation platforms, blockchain-based confidential data stores, and any system where both data confidentiality and access pattern privacy are required in an adversarial distributed environment. The practical implication is that organizations can build intrusion-tolerant storage systems where even compromised servers cannot learn which data blocks are being accessed.

Key Takeaways

• First ORAM achieving wait-freedom and Byzantine fault tolerance simultaneously
• Multi-version approach eliminates client synchronization, improving concurrency and fault tolerance
• Security holds under skewed access distributions (the realistic case for databases)
• Outperforms crash-fault-tolerant ConcurORAM in both throughput and latency despite stronger security guarantees
• Latency below 140ms for 50 concurrent clients on BFT-SMaRt
• New security definition (asynchronous wait-free ORAM) formalizes the necessary trade-offs between wait-freedom and obliviousness

About the Speaker(s)

Bernardo Ferreira is a professor at the University of Lisbon, presenting on behalf of PhD student Robin Vassantlal. The research group works on oblivious computation and Byzantine fault-tolerant systems, with the goal of making access-pattern-hiding storage practical for distributed computing environments.