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
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
-
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} }