  Data sharding$\unicode{x2013}$in which block data is sharded without sharding
compute$\unicode{x2013}$is at the present the favored approach for scaling
Ethereum and other popular blockchains. A key challenge toward implementing
data sharding is verifying whether the entirety of a block's data is available
in the network (across its shards). A central technique proposed to conduct
this verification uses erasure-coded blocks and is called data availability
sampling (DAS). While the high-level protocol details of DAS have been well
discussed in the community, discussions around how such a protocol will be
implemented at the peer-to-peer layer are lacking. We identify random sampling
of nodes as a fundamental primitive necessary to carry out DAS and present
Honeybee, a decentralized algorithm for sampling nodes that uses verifiable
random walks. Honeybee is secure against attacks even in the presence of a
large number of Byzantine nodes (e.g., 50% of the network). We evaluate
Honeybee through experiments and show that the quality of sampling achieved by
Honeybee is significantly better compared to the state-of-the-art. Our proposed
algorithm has implications for DAS functions in both full nodes and light
nodes.
