Plateau: A Secure and Scalable Overlay Network for Large Distributed Trust Applications

We propose a novel two-tiered overlay network design called plateau. It has two levels: a small upper-level that regulates entry of new nodes into the network, and a lower-level comprising all nodes. The lower level is a well-connected expander that is ideal for building peer-to-peer distributed trust applications. It is designed to be secure despite the presence of adversarial Byzantine nodes and resilient to large amounts of churn. The good nodes only need to communicate with their neighbors in the network, thus making plateau fully distributed. Membership in the network must be earned through proof-of-work that is verified by the upper-level nodes. Plateau is robust despite heavy churn controlled by an adversary, i.e., up to C= poly (n) number of nodes can join and leave the network per round without disrupting the network structure; n is the total number of good nodes in the network. As long as the compute power controlled by the Byzantine adversary is bounded, the number of Byzantine nodes in the network is kept in check and, more importantly, they will not be able to disrupt the structure or functioning of the overlay network. Additionally, we show that all resources needed to operate this network is bounded polylogarithmically with respect to n.