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)
- 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
-
CC BY