You are looking at a specific version 20161013:185140 of this paper. See the latest version.

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 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
BitcoinGHOSTconfirmation timeblockchainrobust public transaction ledgersecurity
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.