In this article, I will tell you about DAG (Directed Acyclic Graph) and its application in distributed registries, and we will compare it with blockchain.
DAG is nothing new in the world of cryptocurrencies. You may have heard of it as a solution to blockchain scalability issues. But today we will not talk about scalability, but about what makes cryptocurrencies different from everything else: decentralization, lack of intermediaries and resistance to censorship.
I will also show you that the DAG is actually more resistant to censorship, and there are no intermediaries to access the registry.
In the blockchains we are used to, 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, aka "miner") to do so. It is the miners who decide which transaction to add to the next block and which not to. It is the miners who have exclusive access to the blocks and the right to decide whose transaction to accept to be added to the ledger.
Miners are intermediaries that stand between you and the distributed ledger.
In practice, usually a small number of pools of miners collectively control more than half of the computing power of the network. For Bitcoin, these are four pools, for Ethereum, two. If they collude, they can block any transactions they want.
Over the past few years, many variations of blockchains have been proposed, differing in the principles for choosing block producers. But the block producers themselves do not go anywhere, they are still βstanding on the barrierβ: each transaction must go through the block producer, and if he does not accept it, then the transaction, in fact, does not exist.
This is an inevitable problem with blockchain. And if we want to solve it, we must radically change the design and completely get rid of blocks and block producers. And instead of building a chain of blocks, we will connect the transactions themselves, including the hashes of several previous ones in each transaction. As a result, we get 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 ledger, you simply add it. Select multiple parent transactions, add your details, sign and send your transaction to peers on the network. Ready. There is no one to stop you from doing this, so your transaction is already on the ledger.
This is the most decentralized, most censorship-resistant way to add transactions to the ledger without intermediaries. Because everyone just adds their transactions to the ledger without asking 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, which already had several controllers who recorded transactions in the ledger. And finally, there are no controllers in the DAG at all, users add their transactions directly.
Now that we have that freedom, it shouldn't lead to chaos. We must agree on the state of the registry. And this agreement, or consensus, usually means agreement on two things:
- What happened?
- In what order did it happen?
We can easily answer the first question: as soon as a correctly created transaction was added to the ledger, it happened. And point. Information about this may reach all participants at different times, but in the end all nodes will receive this transaction and know that it happened.
If it were a blockchain, the miners would decide what happens. Whatever the miner decides to include in a block happens. Anything that it does not include in the block does not happen.
On blockchains, miners also solve the second consensus problem: order. They are allowed to order transactions within a block however they like.
How to determine the order of transactions in DAG?
Just because our graph is directed, we already have some order. Each transaction refers to one or more previous parent transactions. Parents, in turn, refer to their parents, and so on. Parents obviously appear before child transactions. If any of the transactions can be reached by parent-child links, we know exactly the order between transactions in that chain of transactions.
But the order between transactions cannot always be determined from the shape of the graph alone. 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 call them "witnesses". These are ordinary users whose task is to constantly send transactions to the network in order, i.e. so that each of their previous transactions can be reached by parent-child links. Order providers are trusted users, and the entire network relies on them not to violate this rule. In order to rationally trust them, we require that each order provider be a well-known (non-anonymous) person or organization and have something to lose if they break the rules, such as reputation or business based on trust.
Order providers are chosen by users, and each user includes a list of his trusted providers in every transaction he sends to the network. This list consists of 12 providers. This is a fairly small number so that a person can verify the identities and reputations of each of them, and enough to ensure that the network continues to work in the event of inevitable problems with a minority of order providers.
This list of providers varies from user to user, but the lists of neighboring transactions may differ by at most one provider.
Now that we have order providers, we can isolate their transactions in the DAG and order all other transactions around the order they create. It is possible to create such an algorithm (cf. for technical details).
But the order in the entire network cannot be determined instantly, we need time for order providers to send enough of their transactions to make sure the final order of past transactions.
And, since the order is determined only by the positions of the providers' transactions in the DAG, all nodes in the network will sooner or later receive all the transactions and come to the same conclusion regarding the order of the transactions.
So, we have agreement on what we consider to have happened: any transaction that got into the DAG happened. We also agree on the order of events: this is either inferred from the relationships of the transactions, or it is inferred from the order of the transactions sent by the order providers. So we have a consensus.
This version of the consensus we have in Obyte. Even though access to the Obyte ledger is completely decentralized, the consensus on the order of transactions is still 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 who want to be one of the independent order providers to help us decentralize registry ordering.
Recently, a third independent candidate emerged wishing 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 are found that spend the same coin, the transaction that appeared earlier in the final order of all transactions wins. The second one is invalidated by the consensus algorithm.
In the event that it is possible to establish an order between two transactions spending one coin (through parent-child links), then all nodes immediately reject such an attempt to double spend.
In case the order is not visible from the parent relationships between two such transactions, they are both accepted into the ledger, and we will need to wait for consensus and order between them using the order providers. Then the earlier transaction will win, and the second one will become invalid.
Although the second transaction becomes invalid, it still remains in the ledger, because it already has subsequent transactions that refer to it, which did not violate anything and did not know that this transaction would become invalid in the future. Otherwise, we would have to remove the parent of good subsequent transactions, which would violate the main principle of the network - any correct transaction is accepted into the ledger.
This is a very important rule that allows the entire system to be resistant to censorship attempts.
Let's imagine that all order providers collude in an attempt to "censor" one particular transaction. They can ignore it and never choose a "parent" for their transactions, but that's not enough, this transaction can still be included indirectly as a parent of some other transaction issued by any network user who is not colluding. Over time, such a transaction will receive more and more children, grandchildren and great-grandchildren from ordinary users, growing like a snowball, and all agreed providers of order will have to ignore these transactions too. In the end, they will have to censor the entire network, which is tantamount to sabotage.
In this way, DAG remains censor-resistant even if order providers collude, thus surpassing blockchain in censorship resistance, in which we can do nothing if the miners decide not to include any of the transactions. And this follows from the main property of the DAG: participation in the registry is absolutely independent and without intermediaries, and transactions are irreversible.
Source: habr.com