Path Weaver ORAM: Improving ORAM Throughput via Random Path Scheduling

Oblivious RAM (ORAM) hides memory access patterns but imposes high bandwidth and latency overheads. Prior work (e.g., Hitchhiker) introduced path diversion to serve multiple logical requests in one traversal, yet diversion rarely triggers because it requires requests to lie on the same ancestor–descendant chain.

We present Path Weaver, an ORAM that turns diversion into the common case via random-path scheduling. Instead of a rigid root-to-leaf path, each traversal selects one uniformly random bucket per level; the controller then “stitches” per-level picks so different outstanding requests can be satisfied at different levels of the same traversal. A Tail-Widening scheme fetches a few additional buckets at the dense bottom levels, substantially increasing match opportunities with constant overhead. To keep hardware small, Path Weaver uses a compact position map and regenerates per-level choices on the fly with a pipelined pseudorandom function (PRF) overlapped with DRAM access; we micro-profile these stages to quantify their cost. The design targets random-access main memory (DRAM) and requires no changes to the software stack.

Path Weaver preserves the Path-style invariant of one legitimate bucket per level, thereby retaining indistinguishability and the same stash-overflow guarantees as Path ORAM. Evaluated in gem5 on SPEC CPU 2017, Path Weaver processes 2.32× more requests per traversal than Hitchhiker, reduces single-core ORAM latency by 2.1×, and accelerates four-core workloads by 3.3×. By making path diversion a core architectural feature, Path Weaver brings ORAM significantly closer to practical, ’deployonce” secure memory.