BlockGraph: a scalable secure distributed ledger that exploits locality

Abstract

Distributed public ledgers, the key to modern cryptocurrencies and the heart of many novel applications, have scalability problems. Ledgers such as the blockchain underlying Bitcoin can process fewer than 10 transactions per second (TPS). The cost of transactions is high, and the time to confirm a transaction is in the minutes. We present the BlockGraph, a scalable distributed public ledger inspired by principles of computer architecture. The BlockGraph exploits the natural locality of transactions to allow publishing independent transactions in parallel. It extends the blockchain with three new transactions to create a unified consistent ledger out of essentially independent blockchains. The most important change is the introduction of the blockstamp transaction, which essentially checkpoints a local blockchain and secures it against attack. The result is a locality-based, simple, secure, sharding protocol which keeps all transactions readable. This paper introduces the BlockGraph protocol, proves that it is consistent and can achieve many thousands of TPS. Using our implementation (a small extension to Bitcoin core) we demonstrate that it, in practice, can significantly improve throughput.