Cryptology ePrint Archive: Report 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 optimal solution (in terms of efficiency, security) 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 both a provable security and attack susceptibility point of view the problem of transaction processing time for both \GHOST and Bitcoin.

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. Our proof follows a novel methodology which may be of independent interest.

Given this, we then ask whether \GHOST is a better alternative. We focus on the liveness property of both Bitcoin and \GHOST, i.e., the worst-case transaction confirmation time that can be expected when playing against an adversary. We present a general attack methodology against liveness and we instantiate it with two attacks for Bitcoin and \GHOST. We prove (i) our attack for Bitcoin is optimal and (ii) \GHOST, when under our attack, performs, in expectation, {\em worse} than Bitcoin under the optimal attack, for various parameter choices.

With the above results, our work provides a first example of comparative study between different blockchain designs from a provable security perspective.

Category / Keywords: cryptographic protocols / Bitcoin, GHOST, confirmation time, blockchain, robust public transaction ledger, security

Date: received 1 Jun 2016, last revised 13 Oct 2016

Contact author: g panagiotakos at di uoa gr

Available format(s): PDF | BibTeX Citation

Version: 20161013:185140 (All versions of this report)

Short URL: ia.cr/2016/545

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]