Welcome to the resource topic for 2019/792
Title:
TICK: Tiny Client for Blockchains
Authors: Wei Zhang, Jiangshan Yu, Qingqiang He, Nan Zhang, 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.
ePrint: https://eprint.iacr.org/2019/792
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .