An Analysis of Blockchain Consistency in Asynchronous Networks: Deriving a Neat Bound
This provides a foundational improvement for blockchain protocol analysis, addressing consistency guarantees for decentralized systems in asynchronous settings.
The paper tackles the problem of ensuring consistency in Nakamoto's blockchain protocol in asynchronous networks, proving that it suffices to have the parameter c slightly greater than 2μ / ln(μ/ν), which is a neater and stronger bound than prior results.
Formal analyses of blockchain protocols have received much attention recently. Consistency results of Nakamoto's blockchain protocol are often expressed in a quantity $c$, which denotes the expected number of network delays before some block is mined. With $μ$ (resp., $ν$) denoting the fraction of computational power controlled by benign miners (resp., the adversary), where $μ+ ν= 1$, we prove for the first time that to ensure the consistency property of Nakamoto's blockchain protocol in an asynchronous network, it suffices to have $c$ to be just slightly greater than $\frac{2μ}{\ln (μ/ν)}$. Such a result is both neater and stronger than existing ones. In the proof, we formulate novel Markov chains which characterize the numbers of mined blocks in different rounds.