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