  A key performance metric in blockchains is the latency between when a
transaction is broadcast and when it is confirmed (the so-called, confirmation
latency). While improvements in consensus techniques can lead to lower
confirmation latency, a fundamental lower bound on confirmation latency is the
propagation latency of messages through the underlying peer-to-peer (p2p)
network (inBitcoin, the propagation latency is several tens of seconds). The de
facto p2p protocol used by Bitcoin and other blockchains is based on random
connectivity: each node connects to a random subset of nodes. The induced p2p
network topology can be highly suboptimal since it neglects geographical
distance, differences in bandwidth, hash-power and computational abilities
across peers. We present Perigee, a decentralized algorithm that automatically
learns an efficient p2p topology tuned to the aforementioned network
heterogeneities, purely based on peers' interactions with their neighbors.
Motivated by the literature on the multi-armed bandit problem, Perigee
optimally balances the tradeoff between retaining connections to known
well-connected neighbors, and exploring new connections to previously-unseen
neighbors. Experimental evaluations show that Perigee reduces the latency to
broadcast by $33\%$. Lastly Perigee is simple, computationally lightweight,
adversary-resistant, and compatible with the selfish interests of peers, making
it an attractive p2p protocol for blockchains.
