Paper 2021/1545

Longest Chain Consensus Under Bandwidth Constraint

Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse, and Mohammad Alizadeh


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
jneu @ stanford edu
svatsan @ stanford edu
leiy @ csail mit edu
dntse @ stanford edu
alizadeh @ csail mit edu
2022-05-18: last of 2 revisions
2021-11-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joachim Neu and Srivatsan Sridhar and Lei Yang and David Tse and Mohammad Alizadeh},
      title = {Longest Chain Consensus Under Bandwidth Constraint},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1545},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.