  A popular method in practice offloads computation and storage in blockchains
by relying on committing only hashes of off-chain data into the blockchain.
This mechanism is acknowledged to be vulnerable to a stalling attack: the
blocks corresponding to the committed hashes may be unavailable at any honest
node. The straightforward solution of broadcasting all blocks to the entire
network sidesteps this data availability attack, but it is not scalable. In
this paper, we propose ACeD, a scalable solution to this data availability
problem with $O(1)$ communication efficiency, the first to the best of our
knowledge.
  The key innovation is a new protocol that requires each of the $N$ nodes to
receive only $O(1/N)$ of the block, such that the data is guaranteed to be
available in a distributed manner in the network. Our solution creatively
integrates coding-theoretic designs inside of Merkle tree commitments to
guarantee efficient and tamper-proof reconstruction; this solution is distinct
from Asynchronous Verifiable Information Dispersal (in guaranteeing efficient
proofs of malformed coding) and Coded Merkle Tree (which only provides
guarantees for random corruption as opposed to our guarantees for worst-case
corruption). We implement ACeD with full functionality in 6000 lines of Rust
code, integrate the functionality as a smart contract into Ethereum via a
high-performance implementation demonstrating up to 10,000 transactions per
second in throughput and 6000x reduction in gas cost on the Ethereum testnet
Kovan.
