# Nero: A Deterministic Leaderless Consensus Algorithm for DAG-Based Cryptocurrencies
## 1 Introduction  
The consensus problem was first introduced in [1]. It can be described as a set of entities that wish to agree on something, which could be a value, an action or a statement. At first glance, it appears a simple problem to solve, especially if all parties are honest. However, it becomes complex when some subset of those entities can behave unexpectedly, such as by not participating and leaving the consensus process without revealing their choice to the other parties or by acting maliciously by actively trying to sabotage the consensus scheme so that no consensus is reached or such that honest parties decide differently instead of arriving at a consensus. This problem is typically studied in the context of computer science, where the entities are processes on computers and where the computers communicate with each other through an unreliable network such as the internet. However, this problem and the underlying principles can be applied to other areas, such as politics and game theory. In fact, one of the seminal works in this area is a metaphor for a group of generals on the battlefield who need to decide if they attack or not [2], and this is where the term \"byzantine\" comes from, meaning any type of faulty behavior, also called \"arbitrary\" faults. Ever since, it has become one of the most studied problems in computer science due to its both theoretical and practical importance. From a theoretical standpoint, it has been shown to be equivalent to other problems, such as atomic broadcast and state machine replication, meaning that if you can solve one, you can also solve the others. From a practical standpoint, it is very useful in the deployment of real-world distributed systems. It started with leaderless synchronous consensus algorithms [2, 3], but these had limited application in practice since distributed systems in the real world are not synchronous. This has led to the study of asynchronous distributed systems and to one of the most important theorems in the field: the FLP impossibility theorem [4]. According to this theorem, it is not possible to have agreement and termination in the asynchronous model if one of the processes crash. Throughout the years, there have been many ways to circumvent this, such as randomization [5], modifying the model [6] or the properties [7] of the problem and byzantine fault detectors [8; 9]. Despite being an important field of research in computer science, distributed systems and particularly consensus algorithms gained new momentum with the emergence of Bitcoin [10], the first decentralized-permissionless network that uses a blockchain as a ledger to store the transactions. Its consensus mechanism, the Nakamoto consensus [11], led to the development of a whole new family of consensus algorithms based on Proof of Work (PoW). However, soon the limitations of a design based on PoW became evident, such as the low throughput and high latency, and new alternatives started to appear, such as Proof of Stake (PoS) [12; 13; 14] and PoS with a ledger structure based on directed graphs instead of a linear, chronological order. Despite improving on the limitations of Bitcoin, new alternatives based on proof of stake also solved state machine replication [15] by sequentially executing consensus instances for agreeing on each block of transactions to append to the blockchain. In order to improve scalability, another ledger structure called directed acyclic graph has gained popularity. This allows for consensus instances to be executed concurrently instead of sequentially and thereby improves the latency and throughput of the system [16]. Examples are [17; 18; 19; 20]. A DAG is a graph that is made up of a set of vertices (or nodes) connected by directed edges (or arcs) such that a closed chain is not possible. A blockchain is a type of acyclic graph where each vertex is a block of transactions and is connected to only another vertex sequentially.