Original source: Amber Group
first level title
What exactly does "DAG" mean?
"DAG" is an acronym for "Directed Acyclic Graph". For those not familiar with computer science, this may be a mouthful of terms, so we explain each word in detail as follows:
- Directed: The data of this data structure is only transmitted in one direction
- Acyclic (acyclic): In terms of data structure, it is impossible to return from the current state to the previous state, that is, "acyclic"
- Graph: Under data structure visualization, the structure is shown as a set of interrelated relationships between multiple vertices
What exactly does the DAG structure look like? Checking how the data is ordered is the best way to determine whether the data structure is a DAG or a blockchain. This sorting method refers to how transactions are sorted in a timely manner. Because we understand time to be linear, we often think of events as happening in a certain order. Humans agree with the concept of time, and therefore we agree that events happen in sequence.
The figure above is an example of a "total sequence". When it is determined which event occurs first, all events will have an exact order. In a total order of events, we know exactly where each event is in the total order. When using total order as shown in the figure, event A occurs first, then event B, and then event C. This is how events are recorded in the blockchain.
However, the total ordering of distributed ledgers may limit scalability in terms of throughput and latency. Part of the problem can be solved by "partial order" ledger. In a partial order, the exact order of each event relative to all other events is unknown. Instead, only the sequence of related events is known. We are not sure of the order of all events, but we can determine the order of interdependent events.
For example, we can determine that event B happened before event C. However, in a partially ordered system, we are not sure when event A will occur. Event A may occur before, after, or even between these events. Event A has nothing to do with other events.
In general, why do we want to know how these transactions are ordered? Because we want to know how one event caused another to happen. Partial order has no concept of time, so how do we sort events without knowing when each event occurred?
"Causal ordering" is the solution to this problem. Causal ordering is a partial ordering that does not consider the time when events occur, but only considers the causal relationship between events. As long as we can determine which events caused other events, we can order these events.
The figure above is an example of a causal sequence. The events in the image above are not time stamped, so it is impossible to determine exactly when these events occurred. However, we can see that A causes B to happen, and B causes C and E to happen. It can then be concluded that A eventually causes D and F to occur. Since C causes D and E causes F, we can determine the causal order of C and D and E and F. However, we do not need to determine the order of C and E or C and F, nor the order of E relative to C or D. Not all events are partially ordered and causally related to each other, but that's okay because unrelated events don't need to be ordered relative to each other.
By using a causal order, we will no longer be limited to a structure like a "chain of events", and thus will be able to build a DAG structure. Events that have nothing to do with each other don't need to be sorted at all. The distributed ledger structure of transactions in causal order is DAG, while the ledger structure of total order is blockchain. Since causal ordering allows certain transactions to skip ordering entirely, DAG-based ledgers have scalability advantages in terms of throughput and latency compared to blockchain-based ledgers.
first level title
secondary title
How does a fully ordered blockchain use DAG?
text
Fantom: A blockchain based on Gossip protocol using DAG technology
image description
At a high level, nodes create event blocks that form a DAG. Fantom uses this DAG of event blocks and generates a blockchain (a chain of confirmed blocks).
Fantom stores data in event blocks, which contain financial, technical, and other information. An event block is a data structure created by a single node for sharing transactions and user information across the network. In the above figure, what we see is a DAG structure, the circle represents the node, and the event block is generated by the node. It is not shown in the above figure, but each node is actually generating event blocks. Whenever nodes exchange transaction information, a new shared event block is created. Event blocks are shared across the network. When an event block communicates with another event block, the communicated event block will store the transaction information of the previous event block, and then create a new event block. This information is then passed to the next event block. Transaction information is hashed, and each event block contains the hash values of one or more previous event blocks. This makes the data immutable, as previous event blocks cannot be modified or deleted without changing the hash.
As shown in the figure above, the green area in the DAG structure of the Opera chain is the event block, and they communicate with each other until they find an event block called a "Clotho" block (the blue block in the figure above). Clotho blocks contain a "tag table", which is a data structure that holds all connection data between blocks for a particular event. To be considered a Clotho block, the Clotho must have a supermajority connection of more than 2/3 to the previously set event block. Clotho blocks communicate with other Clotho blocks in a DAG structure through a tag table data structure.
Based on the communication information between each other, the Clotho blocks reach a consensus to create another event block, called the "Atropos" block (the green block in the above diagram). Each Clotho block has a specific timestamp when it is created. A Clotho block becomes an Atropos block if at least 2/3 of all nodes have the same node time. These Atropos blocks are chained together to form the "main chain". The main chain can be regarded as a blockchain in the DAG structure. Each Atropos block is connected to other Atropos blocks, sharing information gathered from the Clothos block, which in turn gets its information from all other event blocks.
This main chain contains the total order of all events. All participating nodes have a copy of the main chain, and can search the historical position of their blocks in the Lachesis consensus protocol. Nodes do not need to store all the information for each event block, they only need to refer to the main chain. This allows the system to quickly access previous events.
first level title
DAG with causally ordered outputs
What most people refer to as a "DAG" is actually a causally ordered distributed ledger. How do these DAGs work, and how are they different from a relative total order? Avalanche's X-Chain, IOTA, and Sui are examples of distributed ledgers with causal ordering.
Avalanche X-Chain, a UTXO-based DAG.
Bitcoin introduced the unspent transaction output (UTXO) model to record the transfer status between wallets. Each UTXO is a chain of ownership, and the owner signs a transaction that transfers ownership of the UTXO to the new owner's address. In the context of UTXOs, Bitcoin should be described as a blockchain, and Avalanche's X-Chain should be described as a DAG. X-Chain uses the Avalanche consensus protocol of causal order. When you send AVAX to someone, you are using X-Chain. To understand how Avalanche's DAG works, you first need to know how Avalanche's DAG structure is formed.
The Avalanche consensus is divided into four main phases: Slush, Snowflake, Snowball, and Avalanche. The final stage counterpart to Avalanche consensus is Snowman consensus, which we will explore later. Let's first take a look at how the Slush consensus works. The Avalanche network consists of many nodes. Each node has three states: stateless, true, and false. Below we use colors to express more intuitively: colorless, blue and red.
Each node starts out as colorless, where it faces a vote to decide true or false (blue or red). Once a color is chosen, the node communicates with numerous other nodes in the network. If these nodes don't already have a color, they will take on the same color as the node. If the majority of nodes have the same color, the original node will keep that vote. If the majority of nodes are a different color, the original node inverts its vote to that color.
There will be multiple rounds of communication between nodes until all nodes reach a consensus. The goal is to have each node form a consistent color. When a node leans toward a certain color, this reinforces that leaning and directs the correct outcome to that color. This concept is the foundation upon which Avalanche is built and everything is built upon.
The second building block of Avalanche is the Snowflake protocol. Each node has a counter when the node imports memory. The counter is incremented by 1 each time the Slush protocol communication returns the same color. And every time the node inversion result returns a different color, the counter is reset. Once the counter reaches a large enough number, it locks its state and prevents the node from changing color. This will help solidify the true color.
In the third phase of the Snowball protocol, nodes will record values with larger memory. The Snowball protocol adds confidence to the Snowflake protocol. Nodes in the Snowflake protocol do not change color based on the other nodes they communicate with, but instead review all of their own color change history and change color based on the node's confidence state, which takes into account the node's vote change history data .
All the above stages eventually lead to the Avalanche protocol. Avalanche is an append-only (adding transactions to previous transactions) DAG structure. Avalanche can also run without a DAG structure, as is the case with Avalanche's linear structure on the contract chain (C-Chain) and platform chain (P-Chain). Team Rocket, the development team of the Avalanche consensus, believes that the DAG architecture is superior to the blockchain, because the voting of each transaction in the DAG architecture is linked to all the transactions it adds, so the DAG voting mechanism is more efficient.
The Avalanche consensus consists of multiple Snowball events to build a dynamic DAG of all known transactions - each Snowball event is a vertex in the graph. Vertices are like blocks in a linear blockchain. It contains the hash of its parent, and a list of transactions. The Avalanche consensus is based on Snowball, and the concept of confidence is still valid, but it is applied to each node of the DAG. Different from the red-blue decision discussed before, the nodes in the Avalanche consensus will judge whether a transaction is correct or whether it conflicts with other transactions, and reach a consensus with each other. Every transaction is linked to a parent transaction, and all parent transactions are linked back to a genesis vertex. A transaction can have sub-transactions, and sub-transactions are linked to all parent transactions. Avalanche requires a genesis vertex because it requires a transaction to be the basis of all other transactions (IOTA also has a genesis vertex); the genesis vertex is important because transactions that only support add operations require an add body. However, if Snowball is directly applied to the DAG composed of nodes, this will cause an unresolved problem, which is transaction conflict or double spending. So Avalanche added the concept of "chit" to Snowball. When the confidence reaches a threshold, a counter called chit is added to the transaction with a value of "1". If not assigned, the chit counter is "0". This node will sum the chit values as an additional confidence setting, similar to Snowball's confidence. Nodes then use the sum of chits to determine the confidence of a transaction, and all of its child transactions (new transactions added to the node).
Avalanche is able to integrate Slush, Snowflake and Snowball and adjust them into a linear chain. This is done for the Snowman consensus parallel to the Avalanche consensus, which is quite different. Unlike Avalanche's UTXO model, Snowman consensus is account-based. The Snowman consensus is used for the platform chain (P-chain) and contract chain (C-chain) of the Avalanche network. The protocol works the same as above, but each vertex has only one parent instead of multiple parents. So all vertices form a total order. This also renders the overall structure as a blockchain, rather than a DAG. This is useful for applications that need to know the order of transactions, and Snowman consensus also supports smart contracts.
The Avalanche consensus protocol works amazingly well for currency transfers, and can be applied to a variety of other protocols as well. Avalanche was used as a pre-consensus mechanism for Bitcoin Cash before the hard fork to its own project, Bitcoin ABC. Avalanche's DAG structure improves transaction speed, and since Bitcoin Cash does not require smart contracts, the flaw of DAG incompatibility with smart contracts has no effect on this. In the payment field, Avalanche is able to ignore the need for smart contracts, and only emphasizes how DAG-based ledgers can expand functionality more effectively.
IOTA, a transaction-based DAG using proof-of-work
IOTA's causal order structure is called the Tangle, a network that processes transactions in parallel. Tangle is the data structure that IOTA forms DAG. IOTA's tangle consists of transactions, where each transaction is represented as a vertex in the graph. When a new transaction joins the Tangle, it picks two previous transactions for approval and adds two new links to the graph.
In the diagram below, transaction G approves transactions E and F. Transactions contain information such as "Alice gave Bob ten IOTA coins". Unapproved transactions are called "tips". Transaction G is a tip because it has not yet been approved. Each newly added transaction needs to be linked with two pending tips. There are a few strategies to help with tip selection, but the simplest is to randomly pick two tips to approve. The process of selecting tips for approval is extremely scalable for new transactions.
Red transactions I and G are unapproved tips because they are not linked to any other transactions. All other transactions are already approved because each transaction has other transactions linked to it.
At the same time, IOTA has introduced weight, which is an important concept to strengthen the IOTA DAG architecture. How do we know if a transaction is credible? In a typical blockchain, it is common to see the number of confirmations of the blockchain. IOTA achieves a similar function by looking at transaction weights.
image description
Each transaction has its own weight, and each time a tip is added to the tangle, the cumulative weight increases.
In the diagram above, we can see that transaction D is directly approved by transactions E and H, and also indirectly by G and I. The cumulative weight of D is therefore 3+1+3+1+1=9, which is the sum of its own weight plus the weights of E, H, G, and I.
Transactions with a larger cumulative weight are more important than transactions with a smaller cumulative weight. Each new transaction added to the tangle increases the cumulative weight of previous transactions by the weight of its own transaction. Older transactions become more important over time. Because we can think that no entity can generate transactions with sufficient weight in a short period of time, using cumulative weights can avoid spam attacks and other vector attacks.
Similar to Avalanche's X-Chain, this approach, while highly scalable, makes it nearly impossible to integrate smart contracts. So in order to compete with other smart contract chains, IOTA is launching a separate smart contract layer called "Assembly". Assembly is a fully ordered Layer 2 designed to support EVM and WASM smart contracts.
Sui, a smart contract DAG using Proof of Stake
Although Sui is classified as a causal order in this report, in fact Sui uses both total ordering and causal ordering. Sui's transaction processing architecture can be seen as two parts: one part is a total order, dependent transactions executed in sequence, and the other part is a causal order, independent transactions executed in parallel. Dependent transactions use Sui's Narwhal and Bullshark protocols. Narwhal is a DAG-based mempool, while Bullshark is a consensus protocol that integrates with Narwhal for consensus. Dependent transactions only need to execute in order with other transactions they are associated with. However, Sui takes another approach when the transactions are completely independent. For stand-alone transactions, instead of Narwhal and Bullshark, Sui uses a method called Byzantine Consensus Broadcasting (BCB). This method does not require global consensus, so transactions can be processed and written to the ledger almost instantaneously.
image description
Regardless of how transactions are ordered, all transactions are processed in parallel on the same network.
A transaction is simply a metadata change for a specific instance of an object. A transaction takes objects as input and reads, writes, or alters those input objects to produce a newly created or updated object as output. Each object knows the hash of the previous object that produced it.
image description
Sui's ledger is an "object repository" or "object pool" whose data is stored in a DAG. For example, the act of sending USDC is the act of updating the "owner" property of one object, which has no effect on other objects.
Sui's ledger is an "object repository" or "object pool" whose data is stored in a DAG. In this DAG, nodes are objects, and each arrow in the graph represents a transaction that updates a property of a given object. Not shown in this diagram is the genesis transaction, which accepts no input and produces objects in the initial state of the system.
key points
key points
Causal ordering of transactions seems to have advantages over total ordering in terms of speed and throughput. However, the lack of causal order of ordering creates problems when trying to create applications that require strict chronological ordering, and many projects fail to properly run smart contracts on their DAG architectures. Fantom's fully ordered architecture similar to the blockchain structure supports EVM and smart contracts. Although Fantom has total order output, developers still found ways to optimize Layer 1 under the DAG consensus mechanism. Avalanche chose a different approach, creating a separate consensus mechanism Snowman to support the convenient development of EVM and smart contracts. IOTA has also chosen another approach and is creating a framework to enable easy deployment of blockchain instances on IOTA to support the EVM, effectively creating a fully ordered Layer 2 infrastructure. Sui's unique design is very promising. Transactions can be either fully ordered or causally ordered as needed. It is compatible with smart contracts and can reduce latency.
Sui is the latest DAG-based Layer 1, but Sui has achieved differentiation and improved the defects of the previous architecture, so Sui has realized a structure that makes DAG truly a distributed ledger. Even if causal transactions will not become mainstream in the future, DAG-based technology will help expand existing blockchains. While DAG as a scaling method may not be the best choice for all use cases, on Avalanche's X-Chain and IOTA, DAG seems to perform well in terms of latency and throughput.
secondary title
about the author
disclaimer
disclaimer
The information contained herein (“Information”) is provided for informational purposes only, in summary form and is not exhaustive. These materials are not, and are not intended to be, an offer or the solicitation of an offer to sell or buy any securities or products. Such information is not provided and should not be considered as providing investment advice.
Original link
