Honeybee: Byzantine Tolerant Decentralized Peer Sampling with Verifiable Random Walks

Popular blockchains today have hundreds of thousands of nodes and need to be able to support sophisticated scaling solutions$\unicode{x2013}$such as sharding, data availability sampling, and layer-2 methods. Designing secure and efficient peer-to-peer (p2p) networking protocols at these scales to support the tight demands of the upper layer crypto-economic primitives is a highly non-trivial endeavor. We identify decentralized, uniform random sampling of nodes as a fundamental capability necessary for building robust p2p networks in emerging blockchain networks. Sampling algorithms used in practice today (primarily for address discovery) rely on either distributed hash tables (e.g., Kademlia) or sharing addresses with neighbors (e.g., GossipSub), and are not secure in a Sybil setting. We present Honeybee, a decentralized algorithm for sampling nodes that uses verifiable random walks and table consistency checks. Honeybee is secure against attacks even in the presence of an overwhelming number of Byzantine nodes (e.g., $\geq50\%$ 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 network design in both full nodes and light nodes.