DLT design and robustness verification based on random graph theory

Abstract

Distributed Ledger Technology (DLT), commonly referred to as blockchains, provide a new approach to security. Rather than securing items by blocking access, data is made immutable by creating a massively distributed data structure. Entries are secured using cryptographic primitives. Coordination is done using consensus algorithms. We start by introducing random graph theory and presenting its major result: the emergence of a giant component. We explain how and when giant components arise. We explain why the existence, or not, of giant components result in the presence, or not, of graph properties of interest. We then introduce the most widely used consensus algorithms, concentrating on potential problems. We then describe a simple light weight mining (LWM) alternative. We use Erdös's random graph theory to prove the effectiveness and efficiency of LWM. This is an example of how random graph theory can be used to design and implement robust DLT systems