In this article, I will explain DAG (Directed Acyclic Graph) and its application in distributed ledgers, and we will compare it to blockchain.
DAG is not something new in the cryptocurrency world. You may have heard of it as a solution to blockchain scalability issues. But today, we will not focus on scalability; instead, we will discuss what makes cryptocurrencies unique: decentralization, absence of intermediaries, and resistance to censorship.
I will also demonstrate that DAG is actually more resistant to censorship, and it eliminates intermediaries for accessing the ledger.
In traditional blockchains, users do not have direct access to the ledger itself. When you want to add a transaction to the ledger, you have to 'ask' the block producer (block producer, or 'miner') to do it. Miners decide which transaction to add to the next block and which to ignore. They have exclusive access to blocks and the power to determine whose transaction gets accepted for inclusion in the ledger.
Miners are the intermediaries standing between you and the distributed ledger.
In practice, usually a small number of mining pools collectively control more than half of the network's computational power. For Bitcoin, this is four pools; for Ethereum, it’s two. In case of collusion, they can block any transactions they wish.
Over the past few years, numerous variations of blockchains have been proposed, differing in their methods of selecting block producers. But the block producers themselves are still present; they continue to 'stand at the gate': every transaction has to go through a block producer, and if they do not accept it, then the transaction, in effect, does not exist.
This is an inevitable problem with blockchain. And if we want to solve it, we need to radically change the design and completely eliminate blocks and block producers. Instead of building a chain of blocks, we will connect the transactions themselves, including hashes of several previous transactions in each transaction. As a result, we will obtain a structure known in mathematics as a Directed Acyclic Graph - DAG.
Now everyone has direct access to the registry, without intermediaries. When you want to add a transaction to the registry, you simply add it. Select several parent transactions, add your data, sign it, and send your transaction to the network. Done. There is no one to stop you from doing this, so your transaction is already in the registry.
This is the most decentralized, most censorship-resistant way to add transactions to the registry without intermediaries. Anyone can simply add their transactions to the registry without seeking permission from anyone.
DAG can be considered the third stage in the evolution of registries. First, there were centralized registries where one party controlled access to them. Then came blockchains, where there were several controllers recording transactions in the registry. Finally, in DAG, there are no controllers at all; users add their transactions directly.
Now that we have such freedom, it should not lead to chaos. We must have consensus on the state of the registry. And this consensus, or agreement, usually means agreement on two things:
- What happened?
- In what order did this happen?
To the first question, we can easily answer: as soon as a correctly created transaction has been added to the registry, it has occurred. Period. The information about it may reach all participants at different times, but eventually, all nodes will receive this transaction and will know that it has occurred.
If this were a blockchain, miners would decide what happens. Everything that the miner decides to include in the block happens. Everything they do not include in the block does not happen.
In blockchains, miners also solve the second problem of consensus: order. They are allowed to order transactions within the block however they like.
So how do we determine the order of transactions in DAG?
It's only because we have a directed graph that we already have some order. Each transaction references one or more previous parent transactions. The parents, in turn, reference their own parents, and so on. Parents, of course, appear before child transactions. If any transaction can be reached through the 'parent-child' links, we can clearly determine the order between transactions in this transaction chain.
However, the order between transactions is not always discernible just from the structure of the graph. For example, when two transactions lie on parallel branches of the graph.
To resolve ambiguity in such cases, we rely on so-called order providers. We also refer to them as 'witnesses.' These are ordinary users whose task is to continuously send transactions to the network in an orderly manner, i.e., such that each of their previous transactions can be reached through 'parent-child' links. The order providers are trusted users, and the entire network relies on them not to violate this rule. To trust them rationally , we require that each order provider be a known (non-anonymous) individual or organization and have something to lose if they break the rules, such as reputation or a trust-based business.
Order providers are selected by users, and each user includes a list of their trusted providers in every transaction they send to the network. This list consists of 12 providers. This is a small enough number for a person to verify the identity and reputation of each of them, yet sufficient for the network to continue functioning in the event of inevitable issues with a minority of order providers.
This list of providers varies from user to user, but the lists for neighboring transactions can differ by at most one provider.
Now that we have order providers, we can isolate their transactions in the DAG and arrange all other transactions around the order established by them. There is potential for creating such an algorithm (see for technical details).
However, the order throughout the network cannot be determined instantaneously; we require time for the order providers to send a sufficient number of their transactions to verify the final order of past transactions.
And since the order is determined solely by the positions of the transactions of the providers in the DAG, all nodes in the network will sooner or later receive all the transactions and arrive at the same conclusion regarding the order of the transactions.
So, we have consensus regarding what we consider to have happened: any transaction that has entered the DAG has occurred. We also have consensus on the order of events: this is either visible from the parent-child relationships of the transactions or inferred from the order of transactions submitted by the order providers. Thus, we have consensus.
This consensus variant is present in Obyte. Despite the fact that access to the Obyte ledger is entirely decentralized, the consensus on the order of transactions remains centralized, as 10 out of 12 providers are controlled by the creator (Anton Churyumov), and only two of them are independent. We are looking for candidates willing to become one of the independent order providers to help us decentralize the establishment of order in the ledger.
Recently, a third independent candidate has emerged wanting to establish and maintain an order provider node – the University of Nicosia.
Now, how do we control double spends?
According to the rules, when two transactions spending the same coin are detected, the transaction that appeared first in the final order of all transactions wins. The second one is invalidated by the consensus algorithm.
In cases where it is possible to establish an order between two transactions spending the same coin (based on parent-child relationships), all nodes immediately reject such a double spend attempt.
However, if the order is not visible from the parent relationships between the two such transactions, both are accepted into the ledger, and we will need to wait for consensus and order establishment between them through the order providers. Then, the earlier transaction will win, and the second will become invalid.
Although the second transaction becomes invalid, it still remains in the ledger because it already has subsequent transactions referencing it that did not violate anything and were unaware that this transaction would become invalid in the future. Otherwise, we would have to remove the parent from the valid subsequent transactions, which would violate the main principle of the network – any valid transaction is accepted into the ledger.
This is a very important rule that allows the entire system to be resilient against attempts at censorship.
Let's imagine that all order providers collude in an attempt to censor a specific transaction. They may ignore it and never select it as the 'parent' for their transactions, but that is not enough; this transaction can still be indirectly included as a parent of some other transaction issued by any user in the network who is not part of the collusion. Over time, such a transaction will gather more and more children, grandchildren, and great-grandchildren from regular users, growing like a snowball, and all the colluding order providers will have to ignore these transactions as well. Ultimately, they will have to censor the entire network, which is equivalent to sabotage.
Thus, DAG remains resistant to censorship even in the event of a collusion of order providers, thereby surpassing blockchain in its resistance to censorship, where we cannot do anything if miners decide not to include any of the transactions. This follows from the main property of DAG: participation in the ledger is completely independent and without intermediaries, and transactions are irreversible.
Source: habr.com
