Honeybee: Decentralized Peer Sampling with Verifiable Random Walks for Blockchain Data Sharding
<|reference_start|>Honeybee: Decentralized Peer Sampling with Verifiable Random Walks for Blockchain Data Sharding: 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.<|reference_end|>
@article{zhang2024honeybee:,
    title={Honeybee: Decentralized Peer Sampling with Verifiable Random Walks for
  Blockchain Data Sharding},
    author={Yunqi Zhang and Shaileshh Bojja Venkatakrishnan},
    journal={arXiv preprint arXiv:2402.16201},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16201},
    primaryClass={cs.NI cs.CR cs.DC cs.DS cs.MA}
}