Paper 2018/1119

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

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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Bitcoinblockchainparallel compositionproof-of-workproof-of-stake
Contact author(s)
matthias fitzi @ iohk io
2018-11-30: last of 2 revisions
2018-11-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matthias Fitzi and Peter Ga{ž}i and Aggelos Kiayias and Alexander Russell},
      title = {Parallel Chains: Improving Throughput and Latency of Blockchain Protocols via Parallel Composition},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1119},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.