Path ORAM：隐藏内存访问

路径 ORAM 由 Stefanov、van Dijk、Shi、Fletcher、Ren、Yu 和 Devadas 于 2013 年提出，是实践影响最广泛的 ORAM 构造。它将服务器存储组织成由桶组成的二叉树，每个叶节点对应一个数据块的位置。路径 ORAM 在基本形式下每次访问具有 O(log^2 N) 的通信开销，而且结构足够简单，可以用几百行代码实现。

位置映射是客户端一侧的数据结构，用于将每个逻辑块地址映射到二叉树中的一个叶节点。对于包含 N 个块且树高为 L = log N 的数据库，位置映射是一个包含 N 个叶索引的数组。在访问块 b 之前，客户端会在位置映射中查找它当前分配的叶节点，并为它分配一个新的随机叶节点。随后，客户端会从服务器读取旧叶节点对应的路径，并将其写回服务器。

暂存区是客户端一侧的小型缓冲区（通常容纳 20–40 个块），用于临时保存已经从服务器读取但尚未写回的块。读取块时，会将其从所在路径中移出并放入暂存区。访问该块并可能对其进行修改后，暂存区中所有能够放置到新路径上的块都会被写回。无法放入路径的块会继续留在暂存区中。

服务器存储是一棵具有 L+1 层的完整二叉树（L = log N）。每个节点（桶）容纳 Z 个块（通常 Z = 5）。叶节点对应数据块的位置。树中有 N 个叶节点，因此总共有 2N-1 个节点，服务器存储总量为 O(NZ)。每条从叶节点到根节点的路径包含 log N 个节点，并且可以容纳 Z*log N 个块，为路径驱逐策略提供容量。

读取块 b 的步骤如下：(1) 在位置映射中查找 b 当前对应的叶节点 l；(2) 为 b 分配新的随机叶节点 l'，并更新位置映射；(3) 读取从叶节点 l 到根节点路径上的所有桶（共 log N 个桶）；(4) 在读取的路径或暂存区中查找块 b；(5) 写回所有可以分配到新路径 l' 的块，并用虚拟块填充剩余的桶槽位。服务器每次看到的都是随机路径读取。

路径 ORAM 通过让每次访问都恰好读取并写入一条从根节点到叶节点的路径来保持不经意性，无论访问的是哪个块。路径由均匀随机的叶节点分配决定，而不是由块内容或地址决定。虚拟块会填充所有空的桶槽位，使每条路径拥有相同数量的已占用槽位。观察服务器的对手只能看到随机的路径访问。

每次路径 ORAM 访问都需要读取并写入一条从根节点到叶节点的路径：其中包含 O(log N) 个桶，每个桶有 Z 个块。块大小为 B、桶大小为 Z 时，每次访问传输 O(Z * log N * B) 位。对于典型参数（N = 2^20、Z = 5、B = 4KB），每次访问约传输 400KB，而明文访问只需 4KB，开销约为 100 倍。递归位置映射可以将按块计算的通信开销降至 O(log^2 N)。

朴素位置映射需要在客户端存储 N 个条目，也就是 O(N) 的客户端存储量，大小相当于整个数据库。递归位置映射通过将位置映射本身递归地存储在更小的 ORAM 中，把客户端存储量降至 O(log^2 N)。当 ORAM 小到足以放入暂存区时，递归终止。这是使路径 ORAM 适用于大型数据集的标准技术。

如果由于路径冲突，块无法被驱逐到其分配的路径上，路径 ORAM 中暂存区的大小就会增长。Stefanov 等人证明，暂存区溢出（超过 R 个块）的概率会随 R 增大而指数级减小；根据标准分析，该概率最多为 14 * (0.6002)^R。令 R = 40 时，失败概率约为 2^{-38}；而且这一结论适用于所有访问序列，包括由对手选择的访问序列。

在路径 ORAM 之前，最佳的实用 ORAM 构造具有 O(log^3 N) 的开销（Shi 等人，2011 年，《最坏情况开销为 O((log N)^3) 的不经意 RAM》）。路径 ORAM 将开销降至 O(log^2 N)，同时大幅简化了结构。后续研究（电路 ORAM、OptORAMa）进一步改进了常数和渐近界，但由于结构简单，路径 ORAM 仍然是实现最广泛的构造。

路径 ORAM 已经在数十个研究和生产系统中实现。ZeroTrace（Intel SGX + 路径 ORAM）、Obladi（基于云存储的路径 ORAM）和 Opaque（基于 Apache Spark 的路径 ORAM）都是具有代表性的实现。斯坦福安全计算小组维护着一个开源的 C++ 路径 ORAM 实现。AWS 在其 Nitro Enclaves 隐私保护数据分析研究原型中提供了路径 ORAM。

位置映射在路径 ORAM 中起什么作用？

路径 ORAM 将服务器存储组织成一棵二叉树，每次访问都会读取并写入一条从根节点到叶节点的路径。位置映射跟踪每个块当前分配的叶节点；暂存区则缓存最近访问的块。每次访问都会通过分配新的随机叶节点位置进行随机化，使所有服务器可见的访问具有相同的分布。每次访问的通信开销为 O(Z * log N)。递归位置映射将客户端存储量降至 O(log^2 N)。路径 ORAM 是实现最广泛的 ORAM 构造。