Expand description

One of the main ideas in PathORAM is to use a position map, which is recursively an ORAM. The position map is built on top of an ORAM implementation.

Tuning the characteristics of the position map is important for overall performance, and the PathORAM doesn’t really care about those details. So in this implementation, PathORAM contains Box, which allows for sizing and tuning to be done at runtime.

PositionMap also has slightly different initialization from ORAM. You want the PositionMap to begin in a random state, not a zeroed state. But writing random values to all the position maps on initialization is slow. To avoid the need for this, we “implicitly” initialize each position to a value which is the output of a secure block cipher.

The core PathORAM implementation, using PositionMap as a block box, appears in the path_oram module. PathORAM must also use the ORAMStorage to fetch, scan, and return branches in the storage and execute the path ORAM eviction algorithm.


A position map implemented on top of an ORAM Positions are represented as 32 bytes inside a page in an ORAM.

An implementation of PathORAM, using u64 to represent leaves in metadata.

Creator for PathORAM based on 4096-sized blocks of storage and bucket size (Z) of 4, and a basic recursive position map implementation

A trivial position map implemented via linear scanning. Positions are represented as 32 bytes inside a page.

Creates U32 Position Maps, either the trivial one or recursively on top of ORAMs. The value size times the Z value determines the size of an ORAM bucket