Blockchain Models and Latency-Security Guarantees for the Nakamoto Consensus

Li, Jing

doi:https://doi.org/10.21985/n2-6a1e-gy91

Work

Blockchain Models and Latency-Security Guarantees for the Nakamoto Consensus

Public

Download PDF

Download All Files (.zip)

Bitcoin is a decentralized payment system proposed in 2008 by Nakamoto, who remains anonymous to date. It offers an effective alternative to fiat money or centralized payment systems with advantages on privacy, anonymity, and low international remittance fees. The transactions in Bitcoin payment system are sent through a peer-to-peer network, verified by network nodes, and recorded in a public ledger called blockchain. The security of the Bitcoin payment system cannot be fully guaranteed without a rigorous mathematical proof. Due to the unpredictability of adversarial miners, it is challenging to characterize the behavior of miners and the synchronization status of blockchains in a concise way. Unlike classic Byzantine fault tolerant protocols, the Bitcoin protocol only admits probabilistic guarantees. For the sake of security, it is important to derive an explicit formula for the security guarantee as a function of the latency, which will lead to a concrete latency--security trade-off for the Nakamoto consensus. Since Bitcoin's rise to fame, many altcoins and Bitcoin hard forks have adopted the Nakamoto consensus protocol with very different parameters. Their parameters are mostly determined in an ad-hoc or empirical manner. This calls for theoretical results on parameter selection with the goal of optimizing some performance metrics. Properties of the Bitcoin blockchain have been investigated in some depth. The liveness property of Bitcoin is reflected by the blockchain growth theorem and blockchain quality theorem: the blockchain growth theorem quantifies the number of blocks added to the blockchain during any time intervals; the blockchain quality theorem ensures the honest miners always contribute at least a certain fraction of the blockchain. The consistency property of Bitcoin is reflected by the common prefix theorem, which states if a block is deep enough, it will eventually be adopted by all honest miners with high probability.The liveness and consistency properties of the Bitcoin backbone protocol have been established by assuming either explicitly or implicitly that the blockchains have finite lifespan. Also, previous probabilistic security guarantees for the Bitcoin were expressed in terms of exponential order results. As such, the asymptotic bounds are very loose for practical use. This thesis provides a streamlined and strengthened framework to analyze the properties of the Bitcoin protocol under several different models. Under discrete-time model, our results include a blockchain growth theorem, a blockchain quality theorem, and a common prefix theorem of the Bitcoin backbone protocol regardless of whether the blockchains have a finite lifespan. We also express the properties of the Bitcoin protocol in explicit expressions rather than order optimal results. A new notion of ``r-credible blockchains'' is introduced, which, together with some carefully defined ``typical'' events concerning block production over time intervals, is crucial to establish probabilisitic security guarantees. Under continuous-time model, we develop a rigorous analysis of the liveness and consistency of the Bitcoin protocol. Moreover, our analyses yield practical latency and security bounds. For example, when the adversary controls 10% of the total mining power, a Bitcoin block is secured with $10^{-3}$ error probability after 5 hours 20 minutes of confirmation time, or with $10^{-10}$ error probability after 12 hours 15 minutes of confirmation time (assuming all block propagation delays are within 10 seconds). To establish the tight analysis, the arrivals of some special blocks are shown to be renewal processes, where the moment generation functions of the inter-arrival times are rigorously derived. The analysis is then applied to several proof-of-work longest-chain cryptocurrencies to bound their latency and security trade-off. Guidance is also provided for parameter selection with the goal of optimizing some performance metrics. Following the spirit of decoupling various functionalities of the blockchain, the Prism protocol is proposed by Bagaria, Kannan, Tse, Fanti, and Viswanath in 2018 to dramatically improve the throughput while maintaining the same level of security. In addition to Bitcoin, this thesis also extends the analyses to the liveness and consistency of Prism blockchains.

Creator