A Better Method to Analyze Blockchain Consistency

Lucianna Kiffer; Rajmohan Rajaraman; abhi shelat

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/601

A Better Method to Analyze Blockchain Consistency

Lucianna Kiffer, Rajmohan Rajaraman, and abhi shelat

Abstract

The celebrated Nakamoto consensus protocol ushered in several new consensus applications including cryptocurrencies. A few recent works 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 required a careful counting of certain combinatorial events that was difficult to apply to variations of Nakamoto. The work of Garay, Kiayas, and Leonardas provides another method of analyzing the blockchain under both a synchronous and partially synchronous setting. 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 previous work could not consider; • We analyze a family of delaying attacks 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 under the partially synchronous setting and also analyze a folklore "balancing"-attack. In each case, we use our framework to experimentally analyze the consensus bounds for various network delay parameters and adversarial computing percentages. We hope our techniques enable authors of future blockchain proposals to provide a more rigorous analysis of their schemes.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. 2018 ACM SIGSAC Conference on Computer and Communications Security(CCS'18)
DOI: 10.1145/3243734.3243814
Keywords: Blockchain consensus
Contact author(s): lkiffer @ ccs neu edu
History: 2022-05-17: received
Short URL: https://ia.cr/2022/601
License: CC BY

BibTeX

@misc{cryptoeprint:2022/601,
      author = {Lucianna Kiffer and Rajmohan Rajaraman and abhi shelat},
      title = {A Better Method to Analyze Blockchain Consistency},
      howpublished = {Cryptology ePrint Archive, Paper 2022/601},
      year = {2022},
      doi = {10.1145/3243734.3243814},
      note = {\url{https://eprint.iacr.org/2022/601}},
      url = {https://eprint.iacr.org/2022/601}
}