TICK: Tiny Client for blockchains

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

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

In order to be deployed on storage-limited devices, blockchains generally provide lightweight clients which only store all the block headers rather than all the blocks. However, a lightweight client is hard to verify a newly-issued transaction, thus making the zero-confirmation transactions between lightweight clients impossible. In particular, transaction verification needs to verify that each referred output of the transaction is not previously spent. The conventional lightweight client design is unscalable as it can only support such operation in the complexity of O(NT), where NT is the total number of transactions in the system. The latest proposals suggest to summarize all the unspent outputs in an ordered Merkle tree. Therefore, a lightclient 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(NU)), where NU 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 AVLhashtree to store all the unspent outputs. The AVLhashtree can be updated in the time of O(M*log(NU)), where M is the number of elements that need to be inserted or removed from the AVLhashtree. By evaluation, when a new block is generated, the AVLhashtree can be updated within 1 second. Similarly, the proof can also be generated in the time of O(log(NU)). Therefore, TICK is practical and scalable. Benefited by the AVLhashtree, 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.

Original languageEnglish
Number of pages13
JournalIEEE Internet of Things Journal
DOIs
Publication statusAccepted/In press - 10 Aug 2020

Keywords

  • Bitcoin
  • Block chain
  • Data mining
  • History
  • Internet of Things
  • Light client
  • Transaction verification.
  • Vegetation

Cite this