On Trees, Chains and Fast Transactions in the Blockchain

Aggelos Kiayias, Georgios Panagiotakos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProgress in Cryptology – LATINCRYPT 2017
Subtitle of host publication5th International Conference on Cryptology and Information Security in Latin America, Havana, Cuba, September 20–22, 2017, Revised Selected Papers
EditorsTanja Lange, Orr Dunkelman
PublisherSpringer International Publishing
Number of pages25
Edition1st ed. 2019 edition
ISBN (Electronic)978-3-030-25283-0
ISBN (Print)978-3-030-25282-3
Publication statusPublished - 8 Sept 2019
EventLatincrypt 2017, the Fifth International Conference on Cryptology and Information Security in Latin America - La Havana, Cuba
Duration: 20 Sept 201722 Sept 2017
Conference number: 5

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceLatincrypt 2017, the Fifth International Conference on Cryptology and Information Security in Latin America
Abbreviated titleLatincrypt 2017
CityLa Havana
Internet address

Keywords / Materials (for Non-textual outputs)

  • Cryptology


Dive into the research topics of 'On Trees, Chains and Fast Transactions in the Blockchain'. Together they form a unique fingerprint.

Cite this