abhi shelat

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 new analysis provides a tighter guarantee on the consistency property of Nakamoto’s protocol, including for parameter regimes which Pass et al 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 system;

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

UpdatedConsistency

  • Updates: I believe Ling Ren has a [simpler analysis of our result(https://eprint.iacr.org/2019/943.pdf)] with the same outcome. Zhao et al also provide a different analysis, but seemingly the same resulting graph.

  • Garay et al also include an updated analysis that takes into consideration the change in mining difficulty. They also have an updated adversarial graph, but I have not mapped the result into this framework.

AFT 2019 slides