Path ORAM: Hiding Memory Access

Path ORAM, proposed by Stefanov, van Dijk, Shi, Fletcher, Ren, Yu, and Devadas (2013), is the most practically influential ORAM construction. It organizes server storage as a binary tree of buckets, with each leaf corresponding to a position for a data block. Path ORAM achieves O(log^2 N) communication overhead per access in its basic form and is simple enough to implement in a few hundred lines of code.

The position map is a client-side data structure that maps each logical block address to a leaf node in the binary tree. For a database of N blocks with a tree of height L = log N, the position map is an array of N leaf indices. Before accessing block b, the client looks up its current assigned leaf in the position map and assigns it a new random leaf. The old leaf path will be read from and written back to the server.

The stash is a small client-side buffer (typically 20-40 blocks) that temporarily holds blocks that have been read from the server but not yet written back. When a block is read, it is removed from its path and placed in the stash. After accessing and possibly modifying it, all blocks in the stash that can be placed on the new path are written back. Blocks that cannot fit a path remain in the stash.

Server storage is a complete binary tree with L+1 levels (L = log N). Each node (bucket) holds Z blocks (typically Z = 5). Leaves correspond to positions for data blocks. There are N leaf nodes, so there are 2N-1 total nodes and O(NZ) total server storage. Each leaf-to-root path has log N nodes and can hold Z*log N blocks, providing the capacity for the path-eviction strategy.

To read block b: (1) look up the current leaf l for b in the position map; (2) assign b a new random leaf l' and update the position map; (3) read all buckets on the path from leaf l to the root (log N buckets); (4) find block b in the read path or the stash; (5) write back all blocks that can be assigned to the new path l', and fill remaining bucket slots with dummy blocks. The server sees a random path read every time.

Path ORAM maintains obliviousness because every access reads and writes exactly one root-to-leaf path, regardless of which block is being accessed. The path is determined by a uniformly random leaf assignment, not by the block content or address. Dummy blocks fill any empty bucket slots so that every path has the same number of occupied slots. An adversary observing the server sees only random path accesses.

Each Path ORAM access requires reading and writing one root-to-leaf path: O(log N) buckets of Z blocks each. With block size B and bucket size Z, each access transfers O(Z * log N * B) bits. For typical parameters (N = 2^20, Z = 5, B = 4KB), this is about 400KB per access, compared to 4KB for a plaintext access — a 100x overhead. Recursive position maps reduce this to O(log^2 N) communication in terms of blocks.

The naive position map requires N entries stored at the client, which is O(N) client storage — as large as the entire database. The recursive position map shrinks client storage to O(log^2 N) by storing the position map itself in a smaller ORAM recursively. The recursion terminates when the ORAM is small enough to fit in the stash. This is the standard technique to make Path ORAM practical for large datasets.

The stash size in Path ORAM grows if blocks cannot be evicted to their assigned paths due to path conflicts. Stefanov et al. proved that the stash overflows (exceeds R blocks) with probability exponentially small in R — specifically, at most 14 * (0.6002)^R for the standard analysis. Setting R = 40 gives a failure probability of about 2^{-38}, and this holds for all access sequences including adversarially chosen ones.

Before Path ORAM, the best practical ORAM constructions had O(log^3 N) overhead (Shi et al. 2011, "Oblivious RAM with O((log N)^3) Worst-Case Cost"). Path ORAM reduced this to O(log^2 N) with much simpler structure. Subsequent work (Circuit ORAM, OptORAMa) further improved constants and asymptotic bounds, but Path ORAM remains the most widely implemented construction due to its simplicity.

Path ORAM has been implemented in dozens of research and production systems. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM over cloud storage), and Opaque (Path ORAM over Apache Spark) are notable implementations. The Stanford secure computation group maintains an open-source C++ Path ORAM implementation. AWS offers Path ORAM as part of their Nitro Enclaves research prototypes for privacy-preserving data analytics.

What is the role of the position map in Path ORAM?

Path ORAM organizes server storage as a binary tree where each access reads/writes one root-to-leaf path. The position map tracks each block's current leaf assignment; the stash buffers recently accessed blocks. Every access is randomized by assigning new random leaf positions, making all server-visible accesses identically distributed. Communication overhead is O(Z * log N) per access. Recursive position maps reduce client storage to O(log^2 N). Path ORAM is the most widely implemented ORAM construction.