Blockchain and Distributed Ledgers

Abstract

Distributed Ledger Technology (DLT) stores data in a shared form. One form of DLT, the blockchain, was first perceived upon Satoshi Nakamoto’s proposal for Bitcoin as an electronic cash. As a peer-to-peer open ledger, Bitcoin provided an idea and an application for decentralizing trust. As the core data structure, blockchain provided means to store data in a cryptographically secure and transparent manner that is computationally hard to tamper with. The protocol, proof-of-work (PoW), an extended version of Hashcash, provided the network with consensus rules upon which the globally data structure is accepted. Directed acyclic graphs (DAGs) are another form of distributed ledgers that is becoming increasingly used as a blockchain alternative with different topologies and protocols. As blockchains proved several challenges in throughput, scalability, consensus, security, and others, DAGs were proposed to overcome some of them. One challenge facing the security assumptions behind DLT, and hence the integrity of the stored data, is the reliance on cryptographic primitives as traditional digital signature schemes and cryptographic hash functions. The underlying problems of such primitives are believed to be intractable. However, as quantum computers are advancing, they pose an imminent risk on the security of DLT. On hash functions, Grover's search algorithm provides a quadratic speed-up on its known classical counterparts, and on digital signatures, specifically those based on the discrete log and factoring problems, Shor's algorithm solves them in random quantum polynomial (RQP) time. In summary, we survey on different DLT structures mentioning the challenges they try to solve and their security assumptions. We then describe quantum attacks on ledgers with focus on a prominent form that utilizes proof-of-stake (PoS) protocol. To do that, we implement Shor's algorithm on publicly available quantum machines using small integers, namely 15 and 35, highlight the differences between PoW and PoS usage of the standard digital signature schemes and hence find attack vectors that are uniquely applicable to PoS systems. We then propose defenses as design considerations for existing and new systems. As the most critical attack we mention is on digital signatures, we extend the design considerations for quantum-resilient blockchains by providing an up-to-date analysis of post-quantum signature schemes to find their expediency for blockchain systems. We conclude by finding that the lattice-based and hash-based signatures are the most suitable.