Cryptology ePrint Archive: Report 2018/1119

Parallel Chains: Improving Throughput and Latency of Blockchain Protocols via Parallel Composition

Matthias Fitzi and Peter Ga{ž}i and Aggelos Kiayias and Alexander Russell

Abstract: Two of the most significant challenges in the design of blockchain protocols is increasing their transaction processing throughput and minimising latency in terms of transaction settlement. In this work we put forth for the first time a formal execution model that enables to express transaction throughput while supporting formal security arguments regarding safety and liveness. We then introduce parallel-chains, a simple yet powerful non-black-box composition technique for blockchain protocols. We showcase our technique by providing two parallel-chains protocol variants, one for the PoS and one for PoW setting, that exhibit optimal throughput under adaptive fail-stop corruptions while they retain their resiliency in the face of Byzantine adversity assuming honest majority of stake or computational power, respectively. We also apply our parallel-chains composition method to improve settlement latency; combining parallel composition with a novel transaction weighing mechanism we show that it is possible to scale down the time required for a transaction to settle by any given constant while maintaining the same level of security.

Category / Keywords: cryptographic protocols / Bitcoin, blockchain, parallel composition, proof-of-work, proof-of-stake

Date: received 17 Nov 2018, last revised 30 Nov 2018

Contact author: matthias fitzi at iohk io

Available format(s): PDF | BibTeX Citation

Version: 20181130:165620 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]