This paper is a Systematization of Knowledge (SoK) that focuses on Directed Acyclic Graph (DAG)-based consensus protocols in Distributed Ledger Technologies (DLTs). Our study evaluates their impact on performance and their tradeoffs concerning consistency, availability, and partition tolerance, as postulated by the CAP theorem. We delineate the key functionalities and tradeoffs of DAGbased consensus protocols, highlighting iterative improvements and deviations from foundational models. Additionally, we identify research gaps and suggest directions for future work to refine DAG-based consensus mechanisms.

The robust construction of the ledger data structure is an essential ingredient for the safe operation of a distributed ledger. While in traditional linear blockchain systems, permission to append to the structure is leader-based, in Directed Acyclic Graph-based ledgers, the writing access can be organised leaderless. However, this leaderless approach relies on fair treatment of non-referenced blocks, i.e. tips, by honest block issuers. We study the impact of a deviation from the standard tip selection by a subset of block issuers with the aim of halting the confirmation of honest blocks entirely. W e provide models on this so-called orphanage of blocks and validate these through open-sourced simulation studies. A critical threshold for the adversary issuance rate is shown to exist, above which the tip pool becomes unstable, while for values below the orphanage decrease exponentially. We study the robustness of the protocol with an expiration time on tips, also called garbage collection, and modification of the parent references per block.

DAG-based DLTs allow for parallel, asynchronous writing access to a ledger. Consequently, the perception of the most recent blocks may differ considerably between nodes, and the underlying network properties of the P2P layer have a direct impact on the performance of the protocol. Moreover, the stronger inter-dependencies of several core components demand a more complex and complete approach to studying such DLTs. This paper presents an agent-based, open-sourced simulator for large-scale networks that implement the leaderless Tangle 2.0 consensus protocol. Its scope includes modelling the underlying peer-to-peer communication with network topology, package loss, heterogeneous latency, the gossip protocol with reliable broadcast qualities, the underlying DAG-based data structure, and the consensus protocol. The simulator allows us to explore the performance of the protocol in different network environments, as well as different attack scenarios.

The Unspent Transaction Output (UTXO) model is commonly used in the field of Distributed Ledger Technology (DLT) to transfer value between participants. One of its advantages is that it allows parallel processing of transactions, as independent transactions can be added in any order. This property of order invariance and parallelisability has potential benefits in terms of scalability. However, since the UTXO Ledger is an append-only data structure, this advantage is compromised through the presence of conflicting transactions. We propose an extended UTXO Ledger model that optimistically updates the ledger and keeps track of the dependencies of the possible conflicts. In the presence of a conflict resolution mechanism, we propose a method to reduce the extended ledger back to a consistent UTXO Ledger.

This paper investigates several voting consensus protocols with low computational complexity in noisy Byzantine infrastructures. Using computer simulations, we show that explicit randomization of the consensus protocol can significantly increase the robustness towards faulty and malicious nodes. We identify the optimal amount of randomness for various Byzantine attack strategies on different kinds of network topologies.