Close Latency--Security Trade-off for the Nakamoto Consensus

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 guarantees have not been rigorously established. Previous analyses of Bitcoin either focus on specific attacks or provide asymptotic bounds that are too loose for practical use. This paper describes a continuous-time model for blockchains and develops a rigorous analysis that yields very close latency (or confirmation time) and security bounds. 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 after 5 hours 20 minutes of confirmation time, or with less than $10^{-10}$ error probability after 12 hours 15 minutes. These confirmation times are close to lower bounds due to a simple private attack. To establish the tight results, the mining of some special blocks are shown to be renewal processes. Moment generation functions of the inter-arrival times of those processes are derived in closed form. The general results are used 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.