A Tale of Two Trees: One Writes, and Other Reads

In three numbers

What the split buys

All three come straight from the paper's evaluation: a tree of $N=2^{24}$ ORAM blocks of 544 bytes, over the 58,156,895 unspent outputs of Bitcoin blocks 0 to 551,731.

All latencies were measured in SGX simulation mode on an Intel Xeon Silver 4116 (not SGX-enabled). The paper reports that a smaller tree run in hardware mode on an SGX-enabled Core i7 showed no noticeable difference from simulation.

The problem

Light clients leak their wallets

A phone cannot store the Bitcoin blockchain (230 GB unindexed as of October 2018), so it runs a simplified payment verification (SPV) client. Under BIP37 it loads its addresses into a Bloom filter and hands the filter to a full node, which returns matching transactions with Merkle proofs. Gervais et al. showed that a malicious node can recover several of the client's addresses from that filter with high probability, and many more once it sees two filters from the same client.

$T^3$ starts from two observations. First, each tree-based ORAM access is a read-path followed by an eviction, and the two can happen on different copies of the tree. Second, Bitcoin produces a block roughly every 10 minutes, and a rational SPV client has no reason to ask for the same outputs twice before the next block. So one tree only serves reads, in parallel and without write-back. A second tree absorbs every eviction and every block update. At each new block the updated tree becomes the new read tree.

Interactive · Figures 1, 4 and 5 of the paper

Follow one query through both trees

A client asks for the outputs of one address, A. Step through the read protocol (blue) and then a new Bitcoin block arriving (amber). Turn on the irrational client to see the one case the design gives up, and how long it lasts.

The trees here are toy trees of 8 leaves so the paths are visible; the evaluated trees hold $2^{20}$ to $2^{24}$ blocks. Leaf numbers are illustrative. In the prototype all enclaves are threads of one enclave (§5.2).

Interactive · Table 1 of the paper

Read-once versus a standard ORAM access

Pick a tree size. Growing $N$ shrinks each block (fewer outputs per block), and smaller blocks mean a smaller stash to scan with cmov, so every access gets cheaper. The read-once access skips eviction entirely. Average of 10,000 accesses.

Only the five measured tree sizes are selectable. Ratios in the readouts are computed here from Table 1; they do not appear in the paper.

Interactive · Table 2 of the paper

Reads in parallel

A read-once access writes nothing back to the tree. Each thread keeps its own stash and only reads the shared position map, so there is no memory region two threads can write at once (Claim 5). Slide to add read threads on the $N=2^{24}$, 544-byte tree.

Interactive · Figures 2, 3 and 6 of the paper

From an address to an ORAM block

The client only knows its addresses (public-key hashes, $pkh$). Inside the enclave a PRF with a secret key $k_b$ maps each $pkh$ to a block ID, $\mathsf{bid} \leftarrow \mathsf{OBlockMap}(pkh, k_b)$. Only the enclave knows the mapping. Each block has room for a fixed number of outputs per address. How many is enough?

Figures 7 and 8 of the paper

Against Bloom-filter SPV and BITE

For the Bloom-filter baseline, a "request" is the full node scanning one block and building Merkle proofs. For $T^3$ and BITE it is one ORAM access. BITE was re-implemented from its description with non-recursive Path ORAM and 32 kB blocks ($N=2^{17}$). An "improved BITE" uses recursive Path ORAM with $T^3$'s parameters.

Reproduced from the paper's figure files. The underlying data series are not in the paper's source repository, so this page does not read values off these plots.

Guarantees

What $T^3$ promises, and why

The six security claims (§6.1)

Out of scope: speculative-execution attacks, which the paper leaves to Intel's patches. Denial of service by a client that floods requests is also out of scope; the paper suggests fees or a cuckoo filter of unspent addresses.

Table 3 · Capabilities of oblivious systems

Measured

Setup and results

C++ on the Intel SGX SDK v2.1.3. The ORAM controller is built on ZeroTrace, and libjson-rpc-cpp talks to bitcoind from inside the enclave. Recursive Path ORAM ($Z=4$) and recursive Circuit ORAM ($Z=2$), single address into single block, up to 2 outputs per address. Intel Xeon Silver 4116 @ 2.10 GHz, 128 GB RAM, simulation mode.

Table 1 · Read-once vs standard ORAM access

Dataset and storage

Reference

Cite this work

@article{le2020tale,
  title   = {A Tale of Two Trees: One Writes, and Other Reads.
             {O}ptimized Oblivious Accesses to {B}itcoin and other
             {UTXO}-based Blockchains},
  author  = {Le, Duc V. and Tengana Hurtado, Lizzy and Ahmad, Adil and
             Minaei, Mohsen and Lee, Byoungyoung and Kate, Aniket},
  journal = {Proceedings on Privacy Enhancing Technologies},
  year    = {2020}
}

Volume, issue and pages are omitted because the source PDF leaves them as placeholders. The year is from the author's publication list.

Source code. The paper states that the prototype implementation is available at github.com/TEE-3/T3. It builds on the ZeroTrace source code, which its authors shared with the paper's authors.