International Association
for Cryptologic Research

Transaction processing speed is one of the major considerations

in cryptocurrencies that are based on proof of work (POW) such as Bitcoin. At an intuitive level it is widely understood that processing speed is at odds with the security aspects of the underlying POW based consensus mechanism of such protocols, nevertheless the tradeoff between the two properties is still not well understood.

In this work, motivated by recent work \\cite{GKL15}

in the formal analysis of the Bitcoin backbone protocol,

we investigate the tradeoff between provable security and transaction processing speed viewing the latter as a function of the block generation rate.

%

We introduce a new formal property of blockchain protocols,

called {\\em chain growth}, and we show it is fundamental

for arguing the security of a robust transaction ledger.

%

We strengthen the results of \\cite{GKL15} showing for the

first time that reasonable security bounds hold even for the faster (than Bitcoin\'s) block

generation rates that have been adopted by several major ``alt-coins\'\' (including Litecoin, Dogecoin etc.).

%

We then provide a first formal security proof of the GHOST rule for blockchain protocols. The GHOST rule was put forth in \\cite{SZ13} as a mechanism to improve transaction processing speed and a variant of the rule is adopted by Ethereum.

Our security analysis of the ``GHOST backbone\'\' matches our new analysis for Bitcoin in terms of the common prefix property but falls short in terms of chain growth where we provide an attack that substantially

reduces the chain speed compared to Bitcoin. While our results establish the GHOST variant as a provably secure alternative to standard Bitcoin-like transaction ledgers they also highlight potential shortcomings in terms of processing speed compared to Bitcoin.

%

We finally present attacks and simulation results against blockchain protocols (both for Bitcoin and GHOST) that present natural upper barriers for the speed-security tradeoff.

By combining our positive and negative results we map the speed/security domain for blockchain protocols and list open problems for future work.