Coded Merkle Tree: Solving Data Availability Attacks in Blockchains

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 byte block hash commitment and randomly sampling bytes, where b is the size of the data block. With the help of only one connected honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.

Original languageEnglish (US)
Title of host publicationFinancial Cryptography and Data Security - 24th International Conference, FC 2020, Revised Selected Papers
EditorsJoseph Bonneau, Nadia Heninger
PublisherSpringer
Pages114-134
Number of pages21
ISBN (Print)9783030512798
DOIs
StatePublished - 2020
Event24th International Conference on Financial Cryptography and Data Security, FC 2020 - Kota Kinabalu, Malaysia
Duration: Feb 10 2020Feb 14 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12059 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Financial Cryptography and Data Security, FC 2020
CountryMalaysia
CityKota Kinabalu
Period2/10/202/14/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Coded Merkle Tree: Solving Data Availability Attacks in Blockchains'. Together they form a unique fingerprint.

Cite this