  Blockchains use peer-to-peer networks for disseminating information among
peers, but these networks currently do not have any provable guarantees for
desirable properties such as Byzantine fault tolerance, good connectivity and
small diameter. This is not just a theoretical problem, as recent works have
exploited unsafe peer connection policies and weak network synchronization to
mount partitioning attacks on Bitcoin. Cryptocurrency blockchains are safety
critical systems, so we need principled algorithms to maintain their networks.
  Our key insight is that we can leverage the blockchain itself to share
information among the peers, and thus simplify the network maintenance process.
Given that the peers have restricted computational resources, and at most a
constant fraction of them are Byzantine, we provide communication-efficient
protocols to maintain a hypercubic network for blockchains, where peers can
join and leave over time. Interestingly, we discover that our design can
\emph{recover} from substantial adversarial failures. Moreover, these
properties hold despite significant churn.
  A key contribution is a secure mechanism for joining the network that uses
the blockchain to help new peers to contact existing peers. Furthermore, by
examining how peers join the network, i.e., the "bootstrapping service," we
give a lower bound showing that (within log factors) our network tolerates the
maximum churn rate possible. In fact, we can give a lower bound on churn for
any fully distributed service that requires connectivity.
