  Recent works have proposed new Byzantine consensus algorithms for blockchains
based on epidemics, a design which enables highly scalable performance at a low
cost. These methods however critically depend on a secure random peer sampling
service: a service that provides a stream of random network nodes where no
attacking entity can become over-represented. To ensure this security property,
current epidemic platforms use a Proof-of-Stake system to select peer samples.
However such a system limits the openness of the system as only nodes with
significant stake can participate in the consensus, leading to an oligopoly
situation. Moreover, this design introduces a complex interdependency between
the consensus algorithm and the cryptocurrency built upon it. In this paper, we
propose a radically different security design for the peer sampling service,
based on the distribution of IP addresses to prevent Sybil attacks. We propose
a new algorithm, $\scriptstyle{BASALT}$, that implements our design using a
stubborn chaotic search to counter attackers' attempts at becoming
over-represented. We show in theory and using Monte Carlo simulations that
$\scriptstyle{BASALT}$ provides samples which are extremely close to the
optimal distribution even in adversarial scenarios such as tentative Eclipse
attacks. Live experiments on a production cryptocurrency platform confirm that
the samples obtained using $\scriptstyle{BASALT}$ are equitably distributed
amongst nodes, allowing for a system which is both open and where no single
entity can gain excessive power.
