BITE

BITE is a SEC’19 paper which uses Intel SGX to archieve privacy for simplied payment verfication in the Bitcoin network. It has two variants, the first one is using sliding window and the second one is to build a oblivious database. The second variant leverages PATH ORAM. In this post, I reviewed the PATH ORAM first and then discussed the paper.

PATH ORAM

In the outsourced storage applications, data can be leaked by access patterns. The obliviousness is a way to archieve privacy. An naive way to archive oblivious is to scan all the data in the server for each data access, but this method is not pratical and losts the point of data outsourcing.

PATH ORAM is a practical protocol which aims to hide the access pattern in outsourced storage applications. In the protocol, the server is untrusted and the client is trusted. The goal is to ensure that the following information is not leaked during the read/write operations: 1) which data is being accessed, 2) how old it is, 3) whether the same data is being accssed, 4) access pattern and 5) wether the access is a read or a write.

The storage in the server side is a binary tree where each node is a bucket holding a fixed number of blocks. The blocks can be real blocks that store user data or dummy blocks that are used for padding. The number of blocks in the node can be a small number, such as 4. The total number of data blocks is N and the height of tree is then L=LogN. The client stores a small number of blocks in its local storage called stash. The client also stores a position map which maps a data block to its current path in the tree. Note that the block can also be in the stash. For each read or write operation, the client reads a path of ZlogN blocks from the server and writes them block (to obfuscate the read/write operation). Because each bucket in the position path stores a number between 0 and 2^L-1, and there are N such buckets (blocks), the storage size for client is NlogN bits, this storage cost can be optimized to (logN)^2/logX.

The OPATH ORAM protocol can be described in the following procedure ACESS written in pseudocode. The ACCESS is executed by the client. L denotes the level in the tree where 0 means root and L means the leaf level. P(x) means the path from node x in the leaf level to the root. P(x,l) means the bucket in P(x) at the level l in the tree. The read and update code in line 3-7 are straight forward. The tricky code lines are 8-12. In line 8, the block is assigned to a new position, and the block is written to the new path. In line 9, the blocks are collected to S’ from S if the new path have overlaps with the old path. Then, as many as Z blocks are selected from S’ and written to the path. Noted that the loops followings a inversed order from L to 0, it means that the blocks will push to the deep level in the tree. Also note that the ReadBucket function reads all Z blocks from the server. The client also decrypts them. In the WriteBucket procedure, all the blocks ( including the dummy blocks) are re-encrypted.

ACCESS(op,a,data*)
x <- position(a)
position(a) <- UniformRandom {0..2^L-1}

for l in 0..L do
  S <- S U ReadBucket(P(x,l))

data <- Read block a from S
if op = write then
  S <- S -  U 

for l in L..0 do
  S' <- {(a',data') in S: P(x,l) = P(position(a'),l)}
 S' <- Select min(|S'|,Z) blocks from S'
 S  <- S - S'
 WriteBucket(P(x,l),S')

return data

Intuitively, the security of the algorithm comes from the fact that the server only sees the below sequence of data access {position_m[a_m], position_m-1[a_m-1], … position1[a1]}. The sequence cannot be distingushed from a randomized encryption.

Becasue the client side storage NlogN is too big, there is optimization for the algorithm, that is to use another PATH ORAM to store the position map, and then use another PATH ORAM to store the position map of the previous PATH ORAM, by this means, the client side storage can be reduced with the cost of extra network traffic (communicating cost).

BITE

To verify the transaction (check double-spending violation), the participants in the Bitcoin network essentially needs to download the full chain data, a task which is impossible for mobile devices. In practice, this task is often offloaded to the full node, and the client need to present the node with its public addresses and transaction data. In this procedure, the privacy of the user is disclosed.

The paper proposes to use SGX enclaves to solve the issue.