Paper 2019/1139

Coded Merkle Tree: Solving Data Availability Attacks in Blockchains

Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath

Abstract

In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a $\Theta(1)$ byte block hash commitment and randomly sampling $\Theta(\log b)$ bytes, where $b$ is the size of the data block. With the help of only one honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading $\Theta(\log b)$ bytes. We provide a modular library for CMT in {\sf Rust} and {\sf Python} and demonstrate its efficacy inside the {\sf Parity Bitcoin} client.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
blockchainslight nodesfraud proofsMerkle treeinformation theory
Contact author(s)
songzeli8824 @ gmail com
History
2019-10-03: received
Short URL
https://ia.cr/2019/1139
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1139,
      author = {Mingchao Yu and Saeid Sahraei and Songze Li and Salman Avestimehr and Sreeram Kannan and Pramod Viswanath},
      title = {Coded Merkle Tree: Solving Data Availability Attacks in Blockchains},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1139},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1139}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.