A better method to analyze blockchain consistency

@inproceedings{LRS18,
 title = {A better method to analyze  blockchain consistency},
 author = {Lucianna Kiffer and Rajmohan Rajaraman and abhi shelat},
 booktitle = {ACM CCS 2018},
 year = {2018},
 month = {October}
}

The celebrated Nakamoto consensus protocol ushered in several new consensus applications including cryptocurrencies. A few recent works [GKL15, PSS17] have analyzed important properties of blockchains, including most significantly, {consistency}, which is a guarantee that all honest parties output the same sequence of blocks throughout the execution of the protocol.

To establish consistency, the prior analysis of Pass, Seeman and shelat [PSS] required a careful counting of certain combinatorial events that was difficult to apply to variations of Nakamoto. The work of Garay, Kiayas, and Leonardas [GKL] provides another method of analyzing the blockchain under the simplifying assumption that the network was synchronous.

The contribution of this paper is the development of a simple Markov-chain based method for analyzing consistency properties of blockchain protocols. The method includes a formal way of stating strong concentration bounds as well as easy ways to concretely compute the bounds. We use our new method to answer a number of basic questions about consistency of blockchains:

  • Our method identifies an error in the original analysis of Pass et al. Our new analysis provides a tighter guarantee on the consistency property of Nakamoto’s protocol, including for parameter regimes which PSS could not consider;

  • We analyze a family of delaying attacks first presented in PSS, and extend them to other protocols;

  • We analyze how long a participant should wait before considering a high-value transaction confirmed;

  • We analyze the consistency of CliqueChain, a variation of the Chainweb \cite{chainweb} system;

  • We provide the first rigorous consistency analysis of GHOST and also analyze a folklore “balancing”-attack.