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(), where 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()), where 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()), where 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 second. Similarly, the proof can also be generated in the
time of O(log()). 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 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.