Path ORAM: Hiding Memory Access Patterns

The tree layout and the position map

Path ORAM stores N logical blocks inside a binary tree with roughly N leaves, where each tree node is a bucket capable of holding a small constant number of blocks, commonly four, plus padding with dummy blocks when a bucket is not full. The client keeps a position map, a lookup table associating every logical block identifier with a randomly chosen leaf, meaning the client always knows which leaf a block is currently assigned to even though the block's exact bucket along the path from root to that leaf can vary. Because the position map itself can be large for big datasets, practical implementations recursively store it in a smaller ORAM of its own, shrinking the client-side metadata down to something that fits comfortably in local memory. This tree structure is what makes Path ORAM efficient compared to earlier square-root and hierarchical ORAM constructions: rather than shuffling the entire dataset on every access, it only ever needs to touch a single path, whose length is only logarithmic in the total number of blocks.

The access protocol: read, evict, remap

Every operation, whether a logical read or a logical write, follows the same three-step choreography, and this uniformity is exactly what hides whether the operation was a read or a write. First, the client looks up the current leaf for the target block in its position map and downloads every bucket along the path from the root to that leaf, decrypting them locally to find the target block among the real and dummy entries. Second, the client updates the block if it was a write, or simply keeps its value unchanged if it was a read. Third, before anything goes back to the server, the client assigns the accessed block a brand-new random leaf and then re-encrypts the entire path, greedily pushing every block it is currently holding, including ones fetched from earlier accesses still waiting for eviction, as deep down its own assigned path as legality allows, before writing the whole path back to the server. Because every single access downloads and re-uploads a full path of buckets with fresh encryption regardless of which logical block was requested, an eavesdropper watching bucket addresses sees only a uniformly random leaf on every operation, with no correlation to the block accessed or to whether the operation was a read or write.

Why remapping to a random leaf prevents pattern leakage

The single most important trick in Path ORAM is that the accessed block is always assigned a fresh, independently random leaf immediately after being touched, before it goes back to the server. This means that even if a client requests the same logical block twice in a row, the two accesses touch two independently random paths through the tree, since the position map now points somewhere entirely new after the first access. Without this remapping step, repeated accesses to a popular block would trace out the same path over and over, letting a passive observer immediately spot which block is hot even without decrypting anything. The security proof of Path ORAM formalizes this by showing that the sequence of downloaded and uploaded paths is computationally indistinguishable from a sequence of uniformly random paths chosen independently of the client's actual access pattern, which is precisely the cryptographic definition of obliviousness that the scheme targets.

The stash: a safety net for overflowing blocks

Because bucket capacity is fixed and small, there is no guarantee that every block currently in the client's possession can be pushed all the way back down its assigned path during an eviction, especially since many blocks along overlapping paths compete for the same limited bucket slots. Path ORAM handles this with a client-side stash, a small local buffer that temporarily holds any blocks that could not be placed back into the tree during the current eviction. On the next access, those stashed blocks are eligible again to be pushed down whichever new path happens to be read, and over time the greedy eviction strategy keeps the expected stash size very small, with rigorous analysis showing it stays bounded with overwhelming probability as long as bucket size is chosen appropriately, typically four real slots per bucket. This stash is the price paid for keeping bandwidth logarithmic: rather than forcing every eviction to succeed perfectly, the protocol allows temporary backlog that gets resolved naturally by future accesses touching overlapping paths.

Costs, use cases, and where Path ORAM fits

Path ORAM's overhead is dominated by path length: each logical access transfers O(log N) buckets, each holding a small constant number of blocks, giving an overall bandwidth blowup of O(log N) times the block size rather than the O(N) blowup of naive shuffle-everything approaches or the higher polylogarithmic factors of earlier hierarchical ORAM schemes. This efficiency has made it the workhorse behind secure processor designs like Intel SGX-oriented oblivious memory controllers, encrypted cloud storage systems that want to hide query patterns from the storage provider, and secure multiparty computation protocols that need oblivious memory as a building block. The tradeoffs are real: there is genuine bandwidth and latency overhead compared to plaintext access, the client must maintain nontrivial local state such as the position map and stash, and naive recursion for the position map needs care to avoid becoming a bottleneck itself. Still, for scenarios where leaking access patterns is unacceptable, such as private database queries, encrypted search, or oblivious code execution, Path ORAM remains one of the most practical and widely implemented solutions available.

Frequently asked questions

Try it live

Everything above runs in your browser — open Path ORAM: Hiding Memory Access Patterns and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.