On Trees, Chains and Fast Transactions in the Blockchain

Aggelos Kiayias; Giorgos Panagiotakos

Paper 2016/545

On Trees, Chains and Fast Transactions in the Blockchain

Aggelos Kiayias and Giorgos Panagiotakos

Abstract

A fundamental open problem in the area of blockchain protocols is whether the Bitcoin protocol is the only solution for building a secure transaction ledger. A recently proposed and widely considered alternative is the \GHOST protocol which, notably, was proposed to be at the core of Ethereum as well as other recent proposals for improved Bitcoin-like systems. % The \GHOST variant is touted as offering superior performance compared to Bitcoin (potentially offering block production speed up by a factor of more than 40) without a security loss. Motivated by this, in this work, we study from a provable security point of view the \GHOST protocol. We introduce a new formal framework for the analysis of blockchain protocols that relies on trees (rather than chains) and we showcase the power of the framework by providing a unified description of the \GHOST and Bitcoin protocols, the former of which we extract and formally describe. We then prove that \GHOST implements a ``robust transaction ledger'' (i.e., possesses liveness and persistence) and hence it is a provably secure alternative to Bitcoin; moreover, our bound for the liveness parameter is superior to that proven for the bitcoin backbone in line with the original expectation for \GHOST. Our proof follows a novel methodology for establishing that \GHOST is a robust transaction ledger compared to previous works, which may be of independent interest and can be applicable to other blockchain variants.

Note: Found a mistake in the liveness attack.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Bitcoin GHOST confirmation time blockchain robust public transaction ledger security
Contact author(s): g panagiotakos @ di uoa gr
History: 2017-07-05: last of 4 revisions; 2016-06-01: received; See all versions
Short URL: https://ia.cr/2016/545
License: CC BY

BibTeX

@misc{cryptoeprint:2016/545,
      author = {Aggelos Kiayias and Giorgos Panagiotakos},
      title = {On Trees, Chains and Fast Transactions in the Blockchain},
      howpublished = {Cryptology ePrint Archive, Paper 2016/545},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/545}},
      url = {https://eprint.iacr.org/2016/545}
}