Coded Merkle tree: solving data availability attacks in blockchains

DOI10.1007/978-3-030-51280-4_8MaRDI QIDQ2226580zbMATH OpenOpenAlexFDO

Authors Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, P. Viswanath

Publication date 8 February 2021

Full work available at URL https://arxiv.org/abs/1910.01247

zbMATH Keywords

data availability attacks in blockchainssparse erasure codes

Mathematics Subject Classification ID

Macroeconomic theory (monetary models, models of taxation) (91B64) Financial applications of other theories (91G80) Cryptography (94A60)

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(logb)$ 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 $Theta(logb)$ bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.

Recommendations

• Fraud and data availability proofs: detecting invalid blocks in light clients
• Merkle trees optimized for stateless clients in bitcoin
• scientific article; zbMATH DE number 1962159
• An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol Based on Merkle Trees
• Nearly optimal verifiable data streaming

Cited in

(8)

• Assessing security of cryptocurrencies with attack-defense trees: proof of concept and future directions
• SoK: communication across distributed ledgers
• Fraud and data availability proofs: detecting invalid blocks in light clients
• Merkle trees optimized for stateless clients in bitcoin
• Merkle Tree Traversal Revisited
• Proof of availability and retrieval in a modular blockchain architecture
• Cryptoeconomic security for data availability committees
• Foundations of data availability sampling

This page was built for publication: Coded Merkle tree: solving data availability attacks in blockchains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226580)