Paper 2019/792

TICK: Tiny Client for Blockchains

Wei Zhang, Jiangshan Yu, Qingqiang He, Nan Zhang, and Nan Guan

Abstract

In Bitcoin-like systems, when a payee chooses to accept zero-confirmation transactions, it needs to verify the validity of the transaction. In particular, one of the steps is to verify that each referred output of the transaction is not previously spent. The conventional lightweight client design can only support such operation in the complexity of O($N_T$), where $N_T$ is the total number of transactions in the system. This is impractical for lightweight clients. The latest proposals suggest to summarize all the unspent outputs in an ordered Merkle tree. Therefore, a light client can request proof of presence and/or absence of an element in it to prove whether a referred output is previously spent or not, in the complexity of O(log($N_U$)), where $N_U$ is the total number of unspent output in the system. However, updating such ordered Merkle tree is slow, thus making the system impractical --- by our evaluation, when a new block is generated in Bitcoin, it takes more than one minute to update the ordered Merkle tree. We propose a practical client, TICK, to solve this problem. TICK uses the AVL hash tree to store all the unspent outputs. The AVL hash tree can be update in the time of O(M*log($N_U$)), where $M$ is the number of elements that need to be inserted or removed from the AVL hash tree. By evaluation, when a new block is generated, the AVL hash tree can be updated within $1$ second. Similarly, the proof can also be generated in the time of O(log($N_U$)). Therefore, TICK brings negligible run-time overhead, and thus it is practical. Benefited by the AVL hash tree, a storage-limited device can efficiently and cryptographically verify transactions. In addition, rather than requiring new miners to download the entire blockchain before mining, TICK allows new miners to download only a small portion of data to start mining. We implement TICK for Bitcoin and provide an experimental evaluation on its performance by using the current Bitcoin blockchain data. Our result shows that the proof for verifying whether an output of a transaction is spent or not is only several KB. The verification is very fast -- generating a proof generally takes less than $1$ millisecond, and verifying a proof even takes much less time. In addition, to start mining, new miners only need to download several GB data, rather than downloading over 230 GB data.