Trade-off of Security, Latency, and Throughput of the Nakamoto Consensus
- URL: http://arxiv.org/abs/2312.05506v3
- Date: Wed, 22 May 2024 21:36:18 GMT
- Title: Trade-off of Security, Latency, and Throughput of the Nakamoto Consensus
- Authors: Shu-Jie Cao, Dongning Guo,
- Abstract summary: This paper delves into the fundamental trade-off between security, latency, and throughput in proof-of-work longest-chain-wins protocols, also known as the Nakamoto consensus.
New upper and lower bounds on the probability of violating transaction safety are derived as a function of honest and adversarial mining rates, an upper bound on block propagation delays, and transaction confirmation latency, both in time and in block depth.
The paper reveals a fundamental trade-off between transaction throughput and confirmation latency, ultimately determined by the desired fault tolerance and the growth of block propagation delay as block size increases.
- Score: 4.738177482027387
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper delves into the fundamental trade-off between security, latency, and throughput in proof-of-work longest-chain-wins protocols, also known as the Nakamoto consensus. New upper and lower bounds on the probability of violating transaction safety are derived as a function of honest and adversarial mining rates, an upper bound on block propagation delays, and transaction confirmation latency, both in time and in block depth. The results include a first closed-form finite-latency bound applicable to all delays and mining rates up to the ultimate fault tolerance. Notably, for most parameters relevant to Bitcoin and proof-of-work Ethereum, the gap between the upper and lower bounds is significantly narrower than the best gaps previously established in the literature. Furthermore, the paper reveals a fundamental trade-off between transaction throughput and confirmation latency, ultimately determined by the desired fault tolerance and the growth of block propagation delay as block size increases.
Related papers
- The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols.
Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol.
We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
arXiv Detail & Related papers (2024-07-16T20:53:04Z) - Maximizing Blockchain Performance: Mitigating Conflicting Transactions through Parallelism and Dependency Management [0.18641315013048293]
"Conflicting transactions" contribute to high network latency and transaction failures.
We present a novel scheme that integrates transaction parallelism and an intelligent dependency manager.
Results show that our scheme outperforms both existing parallel and non-parallel Hyperledger Fabric blockchain networks.
arXiv Detail & Related papers (2024-07-01T16:17:33Z) - PoW Security-Latency under Random Delays and the Effect of Transaction Fees [33.689236895881216]
Recent studies have shown that PoW protocol is secure under random delay models as well.
We analyze the security-latency problem, i.e., how secure a block is, after it becomes k-deep in the blockchain.
arXiv Detail & Related papers (2024-05-07T17:57:31Z) - Larger-scale Nakamoto-style Blockchains Don't Necessarily Offer Better Security [1.2644625435032817]
Research on Nakamoto-style consensus protocols has shown that network delays degrade the security of these protocols.
This contradicts the very foundation of blockchains, namely that decentralization improves security.
We take a closer look at how the network scale affects security of Nakamoto-style blockchains.
arXiv Detail & Related papers (2024-04-15T16:09:41Z) - Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling.
Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
arXiv Detail & Related papers (2024-02-19T03:08:02Z) - Transaction Capacity, Security and Latency in Blockchains [35.16231062731263]
We analyze how secure a block is after the block becomes k-deep, i.e., security-latency, for Nakamoto consensus.
We compare our results for Nakamoto consensus under bounded network delay models and obtain analogous bounds for safety violation threshold.
arXiv Detail & Related papers (2024-02-15T17:43:13Z) - Short Paper: Accountable Safety Implies Finality [10.589723476970443]
Two key desiderata have been studied for Byzantine-fault tolerant (BFT) state-machine replication (SMR) consensus protocols.
We show that accountable safety implies finality, thereby unifying earlier results.
arXiv Detail & Related papers (2023-08-31T17:58:38Z) - Blockchain Large Language Models [65.7726590159576]
This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions.
The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System.
arXiv Detail & Related papers (2023-04-25T11:56:18Z) - Over-the-Air Federated Learning with Privacy Protection via Correlated
Additive Perturbations [57.20885629270732]
We consider privacy aspects of wireless federated learning with Over-the-Air (OtA) transmission of gradient updates from multiple users/agents to an edge server.
Traditional perturbation-based methods provide privacy protection while sacrificing the training accuracy.
In this work, we aim at minimizing privacy leakage to the adversary and the degradation of model accuracy at the edge server.
arXiv Detail & Related papers (2022-10-05T13:13:35Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task.
In this work, we examine the hardness of finding such chain of PoWs against quantum strategies.
We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
arXiv Detail & Related papers (2020-12-30T18:03:56Z) - Stochastic bandits with arm-dependent delays [102.63128271054741]
We propose a simple but efficient UCB-based algorithm called the PatientBandits.
We provide both problems-dependent and problems-independent bounds on the regret as well as performance lower bounds.
arXiv Detail & Related papers (2020-06-18T12:13:58Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.