Paper 2023/381
Nakamoto Consensus under Bounded Processing Capacity
Abstract
For Nakamoto's longest-chain consensus protocol, whose proof-of-work (PoW) and proof-of-stake (PoS) variants power major blockchains such as Bitcoin and Cardano, we revisit the classic problem of the security--performance tradeoff: Given a network of nodes with finite communication- and computation-resources, against what fraction of adversary power is Nakamoto consensus (NC) secure for a given block production rate? State-of-the-art analyses of NC fail to answer this question, because their bounded-delay model does not capture the rate limits to nodes' processing of blocks, which cause congestion when blocks are released in quick succession. We develop a new analysis technique to prove a refined security--performance tradeoff for PoW NC in a bounded-capacity model. In this model, we show that, in contrast to the classic bounded-delay model, Nakamoto's private attack is no longer the worst attack, and a new attack we call the teasing strategy, that exploits congestion, is strictly worse. In PoS, equivocating blocks can exacerbate congestion, making traditional PoS NC insecure except at very low block production rates. To counter such equivocation spamming, we present a variant of PoS NC we call Blanking NC (BlaNC), which achieves the same resilience as PoW NC.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ACM Conference on Computer and Communications Security (CCS) 2024
- DOI
- 10.1145/3658644.3670347
- Keywords
- Nakamotoconsensusblockchaincapacitybandwidthspamming
- Contact author(s)
-
lkiffer @ ethz ch
jneu @ stanford edu
svatsan @ stanford edu
avivz @ cs huji ac il
dntse @ stanford edu - History
- 2024-06-25: last of 3 revisions
- 2023-03-16: received
- See all versions
- Short URL
- https://ia.cr/2023/381
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/381,
author = {Lucianna Kiffer and Joachim Neu and Srivatsan Sridhar and Aviv Zohar and David Tse},
title = {Nakamoto Consensus under Bounded Processing Capacity},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/381},
year = {2023},
doi = {10.1145/3658644.3670347},
url = {https://eprint.iacr.org/2023/381}
}