Path ORAM: Ocultando Acessos à Memória

Path ORAM, proposto por Stefanov, van Dijk, Shi, Fletcher, Ren, Yu e Devadas (2013), é a construção de ORAM mais influente na prática. Ela organiza o armazenamento no servidor como uma árvore binária de compartimentos, com cada folha correspondendo a uma posição para um bloco de dados. Path ORAM alcança uma sobrecarga de comunicação O(log^2 N) por acesso em sua forma básica e é simples o suficiente para ser implementada em algumas centenas de linhas de código.

O mapa de posições é uma estrutura de dados no cliente que associa cada endereço lógico de bloco a um nó folha na árvore binária. Para um banco de dados com N blocos e uma árvore de altura L = log N, o mapa de posições é uma matriz de N índices de folhas. Antes de acessar o bloco b, o cliente consulta sua folha atualmente atribuída no mapa de posições e atribui a ele uma nova folha aleatória. O caminho da folha antiga será lido do servidor e gravado de volta nele.

O buffer temporário é uma pequena área de armazenamento no cliente (normalmente com 20 a 40 blocos) que mantém temporariamente os blocos lidos do servidor, mas ainda não gravados de volta. Quando um bloco é lido, ele é removido do caminho e colocado no buffer temporário. Depois de acessá-lo e possivelmente modificá-lo, todos os blocos do buffer temporário que podem ser colocados no novo caminho são gravados de volta. Os blocos que não cabem em um caminho permanecem no buffer temporário.

O armazenamento no servidor é uma árvore binária completa com L+1 níveis (L = log N). Cada nó (compartimento) contém Z blocos (normalmente Z = 5). As folhas correspondem às posições dos blocos de dados. Há N nós folha, portanto há 2N-1 nós no total e O(NZ) de armazenamento total no servidor. Cada caminho da folha até a raiz tem log N nós e pode conter Z*log N blocos, fornecendo a capacidade necessária para a estratégia de despejo por caminho.

Para ler o bloco b: (1) consulte a folha atual l de b no mapa de posições; (2) atribua a b uma nova folha aleatória l' e atualize o mapa de posições; (3) leia todos os compartimentos do caminho da folha l até a raiz (log N compartimentos); (4) encontre o bloco b no caminho lido ou no buffer temporário; (5) grave de volta todos os blocos que podem ser atribuídos ao novo caminho l' e preencha os espaços restantes dos compartimentos com blocos fictícios. O servidor vê uma leitura de caminho aleatória a cada acesso.

Path ORAM mantém a obliviedade porque cada acesso lê e grava exatamente um caminho da raiz até uma folha, independentemente do bloco acessado. O caminho é determinado por uma atribuição de folha uniformemente aleatória, não pelo conteúdo ou pelo endereço do bloco. Blocos fictícios preenchem os espaços vazios dos compartimentos para que todos os caminhos tenham o mesmo número de espaços ocupados. Um adversário que observa o servidor vê apenas acessos a caminhos aleatórios.

Cada acesso ao Path ORAM exige ler e gravar um caminho da raiz até uma folha: O(log N) compartimentos, cada um com Z blocos. Com tamanho de bloco B e tamanho de compartimento Z, cada acesso transfere O(Z * log N * B) bits. Para parâmetros típicos (N = 2^20, Z = 5, B = 4KB), isso corresponde a cerca de 400KB por acesso, em comparação com 4KB para um acesso em texto claro — uma sobrecarga de 100 vezes. Mapas de posições recursivos reduzem isso para uma comunicação O(log^2 N) em termos de blocos.

O mapa de posições ingênuo exige N entradas armazenadas no cliente, ou seja, armazenamento O(N) no cliente — tão grande quanto o banco de dados inteiro. O mapa de posições recursivo reduz o armazenamento no cliente para O(log^2 N), armazenando o próprio mapa de posições em uma ORAM menor, de forma recursiva. A recursão termina quando a ORAM fica pequena o suficiente para caber no buffer temporário. Essa é a técnica padrão para tornar o Path ORAM prático em conjuntos de dados grandes.

O tamanho do buffer temporário no Path ORAM aumenta quando os blocos não podem ser despejados em seus caminhos atribuídos devido a conflitos entre caminhos. Stefanov e colaboradores provaram que o buffer temporário transborda (ultrapassa R blocos) com probabilidade exponencialmente pequena em R — especificamente, no máximo 14 * (0.6002)^R na análise padrão. Definir R = 40 resulta em uma probabilidade de falha de aproximadamente 2^{-38}, e isso vale para todas as sequências de acesso, inclusive as escolhidas por um adversário.

Antes do Path ORAM, as melhores construções práticas de ORAM tinham uma sobrecarga O(log^3 N) (Shi et al. 2011, "RAM Oblívia com custo O((log N)^3) no pior caso"). Path ORAM reduziu isso para O(log^2 N) com uma estrutura muito mais simples. Trabalhos posteriores (Circuit ORAM, OptORAMa) aprimoraram ainda mais as constantes e os limites assintóticos, mas Path ORAM continua sendo a construção mais amplamente implementada devido à sua simplicidade.

Path ORAM foi implementado em dezenas de sistemas de pesquisa e produção. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM sobre armazenamento em nuvem) e Opaque (Path ORAM sobre Apache Spark) são implementações notáveis. O grupo de computação segura de Stanford mantém uma implementação de Path ORAM em C++ de código aberto. AWS oferece Path ORAM como parte de seus protótipos de pesquisa do Nitro Enclaves para análise de dados com preservação da privacidade.

Path ORAM organiza o armazenamento no servidor como uma árvore binária em que cada acesso lê ou grava um caminho da raiz até uma folha. O mapa de posições acompanha a atribuição atual de folha de cada bloco; o buffer temporário armazena temporariamente os blocos acessados recentemente. Cada acesso é aleatorizado pela atribuição de novas posições de folha aleatórias, fazendo com que todos os acessos visíveis ao servidor tenham a mesma distribuição. A sobrecarga de comunicação é O(Z * log N) por acesso. Mapas de posições recursivos reduzem o armazenamento no cliente para O(log^2 N). Path ORAM é a construção de ORAM mais amplamente implementada.