Distributed ledger technologies are powerful, disruptive innovations that could transform our society and enhance productivity of applications. According to the famous N. Virt formula “Algorithms + Data Structures = Programs” the main ingredients of every computer program are algorithms and data structures. Our previous post was devoted to consensus algorithm used in Enecuum Platform and in this post we are going to discuss data structures that Enecuum Trinity Algorithm operate on.
Blockchain has emerged as a system with decentralized structure where a linked list plays the role of the base data structure for blocks of transactions. Decisions on which blocks of transactions should be appended to it are made by consensus algorithms. Sometimes the choice the base data structure has much more impact on speed, throughput, scalability, and transaction cost than a choice of a particular consensus algorithm.
Most of existing blockchain solutions are not able to scale their throughput even with increased resources because they are based on linked list data structure with some security additions to make it immutable and append-only. Researchers and practitioners came to conclusion that the most natural data structure for transaction storage is Directed Acyclic Graph (DAG) — a finite directed graph with no directed cycles. Strictly speaking DAG-based distributed ledgers are not blockchains itself, but projects with such structure are getting popular due to their ability to overcome blockchain design limitations. Let’s discuss existing DAG-based approaches in chronological ordering.
IOTA published a DAG-based technology called Tangle. The concept was used to address scalability issues with the limitations of the Internet of Things. Also, a nonce by using weight level was composed to achieve the transaction consensus by setting the user’s difficulty. To solve the double spending problem and parasite attack, they used the Markov Chain Monte Carlo tip selection algorithm, which randomly selects the tips based on the size of the accumulated transaction weights. However, if a transaction conflicts with another, there is still a need to examine all past transaction history to find the conflict.
Byteball uses an internal payments system called bytes. This is used to pay for adding data to the distributed database. Each storage unit is linked to each other that includes one or more hashes of earlier storage units. In particular, the consensus ordering is composed by selecting a single main chain, which is determined as a root consisting of the most roots. A majority of roots detects the double-spend attempts through consensus time of main chain. The fee is charged according to the size of the bytes, and the list of all units should be searched and updated in the process of determining the roots.
Hashgraph is an asynchronous DAG-based distributed ledger. Each node is connected by its own ancestor and randomly communicates known events through a gossip protocol. At this time, any famous node can be determined by the see and strong see relationship at each round to reach consensus quickly. They state that if more than 2/3 of the nodes reach consensus for an event, it will be assigned consensus position.
Phantom consensus algorithm is based on Lachesis Protocol operating with wide DAG. The nodes of this graph are events which contain information about transactions, their authors and Lamport timestamps to define a topological ordering of the events. The state of a process can be obtained from its initial state and the sequence of actions or events that have occurred up to the current state. Consensus algorithm appends event block to the DAG if the event block is dominated (is aware of) by 2n/3 nodes. A position in graph where to append event block are selected by some mechanism based on cost functions.
Perlin provides scalable DAG-based distributed ledger protocol using Avalanche consensus protocol. valanche claims to be different from these two families by not needing to elect a leader in any form (hence leaderless), but rather the protocol simply ‘steers’ all nodes to consensus. This approach is partially achieved by Avalanche’s metastable mechanism. Metastability essentially refers to the concept that the system is designed to bring an answer (i.e. all nodes vote one way or the other) and so will not stay in balance (because if the system remains in balance then consensus cannot be reached). These protocols provide a strong probabilistic safety guarantee in the presence of Byzantine adversaries, while their concurrent nature enables them to achieve high throughput and scalability.
Our own approach HyperDAG generalizes Nakamoto’s blockchain to a DAG of blocks taking best practices from some other solution utilizing DAGs. Similar to Hashgraph the DAG is wide to take maximum advantage from appending history while deciding what transactions are valid and reliable. Using HyperDAG to store transactions enables creating branches (chains of blocks) containing only homogeneous transactions. Each branch is, in essence, a separate blockchain, and, at the same time, is a part of the whole system.
Each branch may set its own specific rules for creation and confirmation of new blocks. Nodes do not have to duplicate and store all auxiliary Enecuum branches. HyperDAG supports the creation of separate branches where the rules can be tailored to solve numerous potential business problems including the ability to handle a large number of transactions cheaply and quickly. Furthermore, this solution allows to integrate the “sharding” technology that is successful in solving the scalability problem.