Close Latency--Security Trade-off for the Nakamoto Consensus
This work provides tighter, more practical latency and security guarantees for users and developers of proof-of-work longest-chain cryptocurrencies like Bitcoin, addressing a long-standing gap in understanding their fundamental properties.
This paper develops a continuous-time model for blockchains to analyze the latency-security trade-off of the Nakamoto Consensus. It provides rigorous analysis yielding close upper and lower bounds for this trade-off, showing, for instance, that with a 10% adversary and 10-second propagation delays, a Bitcoin block is secured with <10^-3 error after four hours, or <10^-9 error after ten hours. These confirmation times are approximately two hours from their lower bounds.
Bitcoin is a peer-to-peer electronic cash system invented by Nakamoto in 2008. While it has attracted much research interest, its exact latency and security properties remain open. Existing analyses provide security and latency (or confirmation time) guarantees that are too loose for practical use. In fact the best known upper bounds are several orders of magnitude larger than a lower bound due to a well-known private-mining attack. This paper describes a continuous-time model for blockchains and develops a rigorous analysis that yields close upper and lower bounds for the latency--security trade-off. For example, when the adversary controls 10\% of the total mining power and the block propagation delays are within 10 seconds, a Bitcoin block is secured with less than $10^{-3}$ error probability if it is confirmed after four hours, or with less than $10^{-9}$ error probability if confirmed after ten hours. These confirmation times are about two hours away from their corresponding lower bounds. To establish such close bounds, the blockchain security question is reduced to a race between the Poisson adversarial mining process and a renewal process formed by a certain species of honest blocks. The moment generation functions of relevant renewal times are derived in closed form. The general formulas from the analysis are then applied to study the latency--security trade-off of several well-known proof-of-work longest-chain cryptocurrencies. Guidance is also provided on how to set parameters for different purposes.