  Spamming attacks are a serious concern for consensus protocols, as witnessed
by recent outages of a major blockchain, Solana. They cause congestion and
excessive message delays in a real network due to its bandwidth constraints. In
contrast, longest chain (LC), an important family of consensus protocols, has
previously only been proven secure assuming an idealized network model in which
all messages are delivered within bounded delay. This model-reality mismatch is
further aggravated for Proof-of-Stake (PoS) LC where the adversary can spam the
network with equivocating blocks. Hence, we extend the network model to capture
bandwidth constraints, under which nodes now need to choose carefully which
blocks to spend their limited download budget on. To illustrate this point, we
show that 'download along the longest header chain', a natural download rule
for Proof-of-Work (PoW) LC, is insecure for PoS LC. We propose a simple rule
'download towards the freshest block', formalize two common heuristics 'not
downloading equivocations' and 'blocklisting', and prove in a unified framework
that PoS LC with any one of these download rules is secure in
bandwidth-constrained networks. In experiments, we validate our claims and
showcase the behavior of these download rules under attack. By composing
multiple instances of a PoS LC protocol with a suitable download rule in
parallel, we obtain a PoS consensus protocol that achieves a constant fraction
of the network's throughput limit even under worst-case adversarial strategies.
