Cryptocurrency Weekend Keynote Chelsea Button, Alfonso Tinoco & Elaine Shi

Cryptocurrency Weekend Keynote Chelsea Button, Alfonso Tinoco & Elaine Shi

Speakers: Elaine Shi (Professor, Carnegie Mellon University)

Conference: DEF CON

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

Overview

In this keynote address, Professor Elaine Shi from Carnegie Mellon University demystifies Oblivious RAM (ORAM), a foundational cryptographic primitive that has transitioned from complex theoretical constructs to large-scale, real-world deployments. The talk, titled "Oblivious RAM: From Theory to Large Scale Development Deployment," delves into how ORAM tackles a critical, often overlooked security vulnerability: access pattern leakage. While traditional encryption protects data content, it fails to conceal which data is being accessed, a side channel that can reveal sensitive information about users, programs, or transactions. Shi eloquently illustrates ORAM's journey, highlighting its adoption by major platforms like Signal, Meta, and the Ethereum Foundation, and its potential to revolutionize privacy in areas ranging from contact discovery to private AI and blockchain transactions.

Professor Shi emphasizes that ORAM is not merely an academic curiosity but a practical, efficient solution for ensuring data privacy in dynamic memory access scenarios, especially when combined with Trusted Execution Environments (TEEs) or other secure computation paradigms. The talk meticulously explains the underlying principles of a simple ORAM construction, specifically Path ORAM, and showcases its dramatic performance improvements over naive approaches. By demonstrating how ORAM can provide robust, provable security against access pattern inference with minimal overhead, Shi positions it as an indispensable component for future privacy-preserving technologies across various industries.

Background

▶ Watch: Introduction to ORAM and talk roadmap (0:45)

The core problem ORAM addresses is access pattern leakage, a subtle yet powerful side channel that undermines privacy even when data contents are fully encrypted. Modern security solutions often rely on encryption or Trusted Execution Environments (TEEs) (also known as secure processors or enclaves) to protect sensitive data during computation. TEEs, like Intel SGX or ARM TrustZone, create hardware-isolated sandboxes where data can be decrypted and processed, with anything leaving the enclave remaining encrypted. However, as Shi explains, this approach is insufficient on its own. While the contents of memory are secure, the sequence and locations of memory accesses remain observable by an adversary.

This leakage is not theoretical; it has been practically demonstrated to compromise privacy in various contexts. For instance, in a binary search algorithm, observing the access patterns (e.g., repeatedly accessing the left half of an array) can reveal whether the search target is a large or small value. More critically, if a program's control flow branches depend on a secret variable (like a bit of a secret key), different branches might exhibit distinct memory access patterns, allowing an attacker to infer the secret. Researchers from UT Austin and Microsoft Research have shown that even coarse-grained, page-level access patterns observed from image processing software running inside a TEE can be exploited to recover the shape and location of objects within an image.

The challenge is to defeat such leakage while preserving program efficiency. A naive solution, like a linear scan over the entire database for every query, would indeed hide specific access patterns but at an exorbitant computational cost. Signal, for instance, initially employed an optimized linear scan for its private contact discovery, requiring 500 servers. This illustrates the fundamental trade-off: privacy at the cost of performance. ORAM emerges as the sophisticated solution, designed to "encrypt" access patterns by ensuring that all physical memory accesses appear identically distributed to an observer, regardless of the actual logical operations being performed. Its theoretical roots trace back to Goldreich and Ostrovsky in the 1980s, who first proposed non-trivial constructions, albeit with impractical overheads.

Key Findings

▶ Watch: Signal adopts Path ORAM after initial struggles (5:15)

Professor Shi's talk highlights several crucial findings and contributions related to ORAM's evolution and practical deployment:

1. Practicality and Efficiency of Path ORAM: A major breakthrough has been the development and real-world deployment of Path ORAM, a scheme proposed in 2013 by Shi and her collaborators. This scheme significantly reduced the theoretical complexity and constant factors, making ORAM practically viable. Path ORAM achieves an asymptotic overhead of log^2 n (where n is the database size), which in practice often translates to an effective log n overhead due to the large base of one of the logarithmic factors.
2. Dramatic Cost Savings for Signal: The most compelling evidence of ORAM's impact comes from Signal's adoption. By replacing their previous optimized linear scan solution (which required 500 servers) with Path ORAM, Signal reduced their operational infrastructure to just six servers. This represents an almost 100x cost saving, underscoring the immense practical value of ORAM for large-scale privacy-preserving applications.
3. Broad Industry Adoption and Interest: Beyond Signal, ORAM is gaining traction across various sectors:

• Meta has an implementation of Path ORAM, likely for private AI applications.
• The Ethereum Foundation is working to integrate ORAM for private blockchain reads, enabling users to access public blockchain data privately.
• Flashbots is exploring ORAM for private block building to mitigate Miner Extractable Value (MEV) and enhance decentralization.
• The concept extends to private Large Language Models (LLMs), allowing users to query models like ChatGPT without disclosing their intentions or queries.

1. Superior Performance of Oblivious Labs' Implementation: The speaker's team at Oblivious Labs has developed a highly optimized ORAM implementation. Benchmarked on Ethereum or Signal-scale datasets (100 GB to 1 TB) on a single desktop machine, it achieves:

• Latency: 20 to 50 microseconds per key-value lookup, demonstrating near-instantaneous access.
• Throughput: Up to 200,000 queries per second on a single node.
• Scalability: ORAM is inherently amenable to horizontal scaling, with throughput increasing proportionally with added machines.
• Performance Leadership: This implementation outperforms Signal's by roughly an order of magnitude, Meta's by about 100x, and state-of-the-art academic implementations like Abl X by approximately 600x, establishing it as arguably the fastest known implementation to date.

1. Bridging Theory and Practice: The research by Shi and her colleagues not only yielded a practical scheme (Path ORAM) but also successfully bridged the theoretical gap between the known lower bound (log n) and previous upper bounds (log^3 n), although these theoretical and practical schemes are distinct.

These findings collectively demonstrate ORAM's maturity as a technology, moving from theoretical possibility to a robust, efficient, and widely applicable solution for a critical privacy problem.

Technical Deep Dive

▶ Watch: ORAM yields 100x cost savings for Signal (5:30)

At its heart, Oblivious RAM (ORAM) is an algorithmic technique designed to "encrypt access patterns," meaning it obfuscates the memory access sequences of a program. Unlike traditional encryption, which secures data content, ORAM aims to ensure that an observer cannot distinguish between different program executions or infer sensitive information based on which memory locations are being accessed. The fundamental security requirement is that for any logical request (read or write to a specific logical address), the observed physical access patterns must be identically distributed, regardless of the actual data being accessed or the specific logical operations performed.

The talk focuses on the construction of Path ORAM, a tree-based data structure that achieves this goal with high efficiency. Path ORAM is remarkably simple, structurally a binary tree where each node is called a bucket. Each bucket has a finite capacity, capable of storing a small, constant number of data blocks. These blocks can be either real blocks (encrypted actual data) or filler blocks (encryption of zeros), which are present solely for security purposes, ensuring that buckets always appear full to an adversary.

The most crucial invariant in Path ORAM is that every data block is assigned to a random path in the tree, specifically a path from the root to some leaf node. To manage these assignments, the ORAM client (running within a TEE or secure boundary) maintains a position map that records which path each logical block currently resides on.

Let's break down the process of reading a block:

1. Locate the Block: When a request comes to read logical address X, the ORAM client first consults its position map to find the random path (e.g., the "blue path") currently assigned to block X.
2. Read the Path: The client then reads all blocks along this entire path from the external, untrusted memory. This is a crucial step for security: by reading an entire path, the specific location of X within that path is hidden.
3. Remove and Relocate: Once the blocks from the path are in the client's secure cache, the client identifies and removes the requested block X. This block is now available for computation.
4. The Key Insight: Constant Movement: To prevent statistical attacks and access pattern leakage, blocks cannot remain in the same physical location. As soon as block X is read, it must be relocated. The client samples a new random path (e.g., the "green path") and updates its position map to reflect this new assignment for block X.
5. Writing Back to the Root: Here lies a critical security mechanism. The block X (potentially updated if it was a write operation) is then written back into the tree. However, it's not written directly to its new random path. Instead, it is always written back to the root of the tree. The root is a node on every possible path. By writing to the root, the ORAM client hides the specific choice of the new random path from the external observer, maintaining the invariant that the block is on a random path without revealing which one.

This "write-to-root" strategy introduces two main challenges:

1. Root Overflow: Continuously writing blocks back to the root will quickly cause the root's bucket to overflow, as it has finite capacity.
2. Large Position Map: The position map, which tracks the path assignment for every logical block, can become very large, potentially exceeding the capacity of the CPU's cache or registers, making it susceptible to the very access pattern leakage ORAM aims to prevent.

Path ORAM addresses these challenges with elegant solutions:

1. Eviction Process: To resolve overflow, Path ORAM employs a clever eviction process. Every time a path is accessed for a read or write, the ORAM client uses this opportunity to "repack" the blocks on that path. It attempts to move blocks closer to their assigned leaf nodes, while still respecting the path invariant (i.e., a block assigned to a path must reside on that path, but can be at any node along it). This process is carefully designed to ensure that, except with negligible probability, no bucket ever overflows. This "read and evict" strategy along a single path is why the scheme is called Path ORAM.
2. Recursion for Position Map: To handle the large position map, ORAM employs recursion. The position map itself is treated as a separate, smaller ORAM tree. This recursive application reduces the size of the position map by a constant factor at each level of recursion. The recursion continues logarithmically many times until the final, smallest position map is of constant size, small enough to be stored directly in the CPU's cache or registers, thus becoming oblivious to its own access patterns.

The entire Path ORAM algorithm, as Professor Shi points out, is surprisingly compact, comprising only about 16 lines of pseudocode. While the algorithm's structure is simple, the rigorous stochastic proof that guarantees no bucket overflow and ensures access pattern obliviousness is mathematically complex. This elegant design enables ORAM to provide strong security guarantees with practical performance.

Demo / Proof of Concept

▶ Watch: Why traditional encrypted databases fail for these use cases (7:00)

While the talk did not feature a live, interactive demonstration, Professor Shi presented compelling evidence of ORAM's practical viability and performance through its real-world deployments and rigorous benchmarking. These serve as powerful proofs of concept for ORAM's transition from theory to large-scale application.

The most prominent example is Signal's private contact discovery. Signal initially used an optimized linear scan, requiring 500 servers to achieve privacy for its users' address books. Upon adopting Path ORAM, their infrastructure needs dramatically shrunk to just six servers, representing an almost 100x reduction in operational costs. This concrete deployment in a widely used privacy-focused application unequivocally demonstrates ORAM's efficiency and practicality in a real-world, high-stakes environment.

Further validating ORAM's utility, Professor Shi highlighted ongoing collaborations and deployments:

• Meta has integrated Path ORAM into its systems, likely for private AI computations, though specific applications were not disclosed.
• The Ethereum Foundation is actively working on incorporating ORAM to enable private blockchain reads, allowing users to query public blockchain data without revealing their access patterns.
• Flashbots is collaborating to use ORAM for private block building, a critical step in mitigating Miner Extractable Value (MEV) and fostering a more decentralized blockchain ecosystem.

Professor Shi also presented performance benchmarks from Oblivious Labs' own implementation of Path ORAM. Tested on datasets ranging from 100 GB to 1 TB (representative of Ethereum or Signal scale) on a single desktop machine, the results are striking:

• Each key-value lookup takes only 20 to 50 microseconds, indicating near-instantaneous response times.
• The system achieves a throughput of up to 200,000 queries per second on a single node.
• The implementation significantly outperforms existing solutions: roughly 10x faster than Signal's previous approach, 100x faster than Meta's reported performance, and a remarkable 600x faster than Abl X, a state-of-the-art academic implementation.

These figures and real-world adoptions collectively serve as a robust proof of concept, demonstrating that ORAM is no longer a theoretical curiosity but a highly efficient, scalable, and indispensable technology for achieving strong data privacy in dynamic computation environments.

Defensive Implications

▶ Watch: Beginning the explanation of ORAM construction (7:45)

The insights from Professor Shi's talk provide critical defensive implications for security practitioners, developers, and architects working with sensitive data and secure computation.

1. Rethink TEE Security: The most immediate implication is that simply using Trusted Execution Environments (TEEs) like Intel SGX or ARM TrustZone is often insufficient for comprehensive data privacy. While TEEs protect data content, they do not, by default, protect against access pattern leakage. Any application performing dynamic memory accesses within a TEE is potentially vulnerable to side-channel attacks that infer sensitive information from observable memory traces. Defenders must assume that if their TEE-protected computation involves non-linear memory access patterns (i.e., not a full linear scan), ORAM or similar oblivious techniques are likely required.

1. Beyond Traditional Encryption: Traditional encrypted databases, which only encrypt data contents, are fundamentally inadequate for scenarios where query privacy is paramount, or where the database itself is public (as in blockchains). Defenders need to recognize that privacy-preserving systems must consider not just what data is stored, but also how it is accessed. ORAM provides the necessary mechanism to obfuscate these access patterns.

1. Mitigating MEV and Enhancing Blockchain Privacy: For blockchain ecosystems, ORAM offers a powerful tool to combat issues like Miner Extractable Value (MEV). By enabling private orderflow and private block building, ORAM can help obscure transaction details from block builders, preventing front-running, back-running, and other forms of predatory value extraction. This is crucial for maintaining the decentralization and fairness of public blockchains, as exemplified by the Flashbots collaboration. Developers building decentralized applications (dApps) or blockchain infrastructure should explore ORAM to enhance user privacy and network integrity.

1. Enabling Private AI and LLMs: The application of ORAM extends to emerging fields like private AI and Large Language Models (LLMs). Organizations deploying or querying AI models with sensitive data (e.g., medical records, proprietary information, personal queries) must consider ORAM to prevent the leakage of query intent or training data access patterns. This allows for privacy-preserving machine learning inference and interaction with powerful models without compromising user confidentiality.

1. Custom Oblivious Algorithms for Performance: While generic ORAM compilation can make any algorithm oblivious, Professor Shi highlighted that customized oblivious algorithms for specific data structures (like those in Oblivious STL) or computational tasks (e.g., graph algorithms, sorting) can often achieve significantly better performance than a generic ORAM transformation. Defenders and developers should be aware of this distinction and, where possible, leverage or contribute to libraries of optimized oblivious algorithms for common tasks to maximize efficiency while retaining strong privacy guarantees.

1. Horizontal Scaling for High Throughput: ORAM implementations, particularly the one from Oblivious Labs, are designed for horizontal scaling. This means that organizations requiring very high throughput for privacy-preserving operations can achieve it by adding more machines, scaling performance proportionally. This makes ORAM suitable for even the most demanding enterprise and public-facing applications.

In essence, the defensive implication is a call to elevate the understanding of privacy beyond data content encryption to include access pattern obfuscation. As TEEs and secure computation become more prevalent, integrating ORAM becomes a best practice for truly robust privacy guarantees.

Key Takeaways

• Access Pattern Leakage is a Critical Privacy Threat: Traditional encryption and Trusted Execution Environments (TEEs) protect data content, but not which data is being accessed. This access pattern leakage is a powerful side channel that can reveal sensitive information and must be actively mitigated.
• Oblivious RAM (ORAM) Solves Access Pattern Leakage: ORAM is an algorithmic technique that "encrypts" access patterns by ensuring all physical memory accesses appear identically distributed to an observer, regardless of the actual logical operations.
• Path ORAM is Practical and Highly Efficient: The Path ORAM scheme, developed by Professor Shi and her team, has transitioned ORAM from theory to practical deployment. It offers an asymptotic log^2 n (practically log n) overhead, making it viable for large-scale applications.
• Real-World Impact and Cost Savings: Path ORAM has enabled significant advancements in privacy, demonstrated by Signal's adoption, which reduced server requirements by 100x (from 500 to 6 servers) for private contact discovery.
• Broad Applications Across Industries: ORAM is crucial for enhancing privacy in diverse fields, including private AI (Meta), private blockchain reads and block building (Ethereum, Flashbots), and private interactions with Large Language Models (LLMs).
• High Performance and Scalability: Modern ORAM implementations, such as those by Oblivious Labs, achieve remarkable performance (e.g., 20-50 microseconds per lookup, 200k queries/second on a single node) and support horizontal scaling, making them suitable for demanding production environments.
• Beyond Generic ORAM: Oblivious STL: While ORAM can make any algorithm oblivious, custom-optimized oblivious algorithms for specific data structures and tasks (like the proposed Oblivious STL library) can offer even greater performance gains.

About the Speaker(s)

Elaine Shi is a distinguished Professor at Carnegie Mellon University, renowned for her extensive contributions to the fields of cryptography, security, mechanism design, algorithms, foundations of blockchains, and programming languages. Her pioneering research work includes significant advancements in Oblivious RAM (ORAM) and differentially private algorithms, which have found practical adoption in major platforms such as Signal, Meta, and Google. Professor Shi is also a co-founder of Oblivious Labs Inc., a company dedicated to bringing these advanced privacy-preserving technologies to real-world applications. Her exceptional contributions to computer science and cryptography have been recognized through prestigious accolades, including being a Packard fellow, a Sloan fellow, an ACM fellow, and an IACR fellow.