[prev: Provisioning a Local Private Ethereum Network with Puppeth] [home]

An Explicit Example of Recursion in Tree-Based ORAM Simulators

The intent of this post to clarify any confusion concerning recursion
in tree-based ORAM simulators such as Path ORAM (Stefanov et al).

Let's store N=7 blocks of bitsize B=4>C*log(7), where C=2.

0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110

We will have Z=1 bucket size in a binary tree of depth 2 and dummy blocks.

                        [0:0000]
        [1:0001]                        [4:0100]
[2:0010]        [3:0011]        [5:0101]        [6:0110]

The client index map
0 - 00
1 - 00
2 - 00
3 - 01
4 - 10
5 - 10
6 - 11

We want to store the index map in a recursive ORAM of the same block size.
Since there are at most NlogN bits stored in the index map, we will need
at most N(logN-1)/B ≥ 8(log8-1)/4 = 4 blocks to store this data. Compare
with the original necessity of storing 7 blocks, and note 4 = ceil 7/C. Explicitly,

We store the grouped index map 
0 - 0000
1 - 0001
2 - 1010
3 - 11__

where to get an original index i, we instead look up floor i/2 and get the i%2'th slice.

We will have Z=1 bucket size in a binary tree of depth 2 and dummy blocks.

                        [0:0000]
        [1:0001]                        [_:____]
[2:1010]        [3:11__]        [_:____]        [_:____]

Note we are only off-by-one from reducing the size of the tree.

The client index map
0 - 00
1 - 00
2 - 00
3 - 01
4 - __
5 - __
6 - __

Finally, recurse again. We have N'logN'≥(N/C)log(N/C)≥8 bits to store, which will fit in 2 blocks.
Note 2 = ceil 7/C/C. Explicitly,

We store the grouped index map 
0 - 0000
1 - 0001

where to get for an original index i, we instead look up floor i/4 and get the i%4'th slice.

We will have Z=1 bucket size in a binary tree of depth 1 and dummy blocks.

                        [0:0000]
        [1:0001]                        [_:____]

Note we are only off-by-one from reducing the size of the tree.

The client index map
0 - 0
1 - 0
2 - _

Thus, the size of the client storage has been reduced by a C^2 factor in exchange
for two more lookups in recursive ORAMs. 

Now, say we wanted the data corresponding to index 5 in the original ORAM.
Then we'd need to look floor5/2=2 in the second ORAM, which means
we'd need to look up floor2/2=1 in the third ORAM.

Check the index map for 1, which corresponds to path 0.
We query the third ORAM for path 0, and we get the answer 0011. Since 2%2=0, we obtain
the slice 00.

Now query the second ORAM for the path 00 (looking for index 2), and we get 1010. Since 5%2=1,
we get the slice 10.

Finally query the first ORAM for the path 10 (looking for index 5), and we get 0101, the original
data.

For further clarification, please e-mail surya at [this domain name].