This is a talk I gave on October 31 at Decentralized conference in Athens. I believe it is the best introduction to DAG so far that clearly shows what DAG stands for and why it excels blockchain.
Special thanks goes out to the University of Nicosia for organizing Decentralized, and for their work in promoting DLT as a whole. In fact, we are very pleased to announce that Obyte and the Institute for the Future of the University of Nicosia have agreed a partnership in which UNIC will be a candidate to become the next independent witness on the Obyte network, and their research department will be studying, testing and validating the Obyte network and consensus mechanism.
Below is a transcript of the talk.
I’ll tell you about using Directed Acyclic Graph (DAG) for building distributed ledgers and how it compares to blockchain.
DAG is not a new thing in crypto. You perhaps have already heard about it and most likely it was praised as a solution to blockchain’s scalability problems.
But I will not talk about scalability. I’ll talk about what makes crypto different from what was before crypto: about decentralization, disintermediation, censorship resistance.
And I’ll show that DAG is more disintermediated and more censorship resistant than blockchain.
In blockchains, you as a user do not have direct access to the ledger. When you want to add a transaction to the ledger, you can’t do it yourself, you have to go through the block producers, the miners. It is miners who get to decide if your transaction gets into the next block. It is miners who have exclusive access to blocks and have the power to accept or not accept your transaction.
Miners are middlemen that stand between you and the ledger.
And in practice, there is usually a small number of miners or mining pools that collectively control more than half of the mining power. It is only 4 pools in Bitcoin and 2 pools in Ethereum. Should they collude, they could block any individual transaction from entering the blocks.
Over the years, many blockchain designs have been proposed that vary in how the block producers are selected. But block producers still serve as gatekeepers: every transaction has to pass through a block producer and if a block producer didn’t accept it, it doesn’t exist.
This is a problem that is inevitable in blockchains. And in order to solve it, rather than inventing another way to select block producers, we have to radically change the design and get rid of blocks and block producers completely. And instead of connecting blocks, we connect transactions directly by having each transaction include a hash of one or more previous transactions. As a result, the transactions get connected into a structure that is known in mathematics as a Directed Acyclic Graph — DAG.
Now, the access to the ledger is completely direct, disintermediated. It doesn’t depend on any third parties, any middlemen. When you want to add a transaction to the ledger, you just add it. Select a few parent transactions, add your own data, sign, and broadcast to peers. Done. There is nobody who could stop you from doing so, and your transaction is already in the ledger.
It is the most decentralized, most disintermediated, most censorship resistant way of accepting transactions into a ledger. Because everybody just adds his transactions to the ledger without asking for anybody’s permission.
You can think of DAG as the 3rd stage of the evolution of ledgers. First, there were centralized ledgers where a single party was a gatekeeper. Then, came blockchains, where a few gatekeepers accept transactions into the ledger. Finally, in DAG, there are no gatekeepers at all, users add their transactions directly.
Now, with so much freedom, it should not be chaos, all nodes should still agree about the state of the ledger. And agreement, or consensus, generally means an agreement about two things:
- what happened;
- in what order.
The first part is easy: once a properly composed transaction is added to the ledger by anybody, it happened. Period. It can reach different nodes at different moments in time but still it will eventually reach all nodes and all nodes will know that the transaction did happen.
If it were a blockchain, the miners would decide what happened. Whatever a miner decides to include into a block, did happen. What he didn’t include into his block — didn’t happen.
In blockchains, miners also decide about the second part of consensus: the order. They are allowed to order transactions within a block as they like.
How do we determine order in a DAG?
Just because it is a DAG, we already have a lot of order. Every transaction references one or more parents. Parents, in turn, reference their own parents, and so on. Parents obviously come before children. If one transaction can be reached from the other through parent-child links, we know the order between those two transactions.
The order doesn’t directly follow from the DAG structure when two transactions lie on parallel branches of the DAG.
To resolve this ambiguity, we rely on so called order providers. We also call them witnesses. Order providers are regular users who are supposed to post their own transactions frequently enough and only in order, that is their previous transaction can be reached through child-parent links from their next transaction. Order providers are trusted to not break this rule, and in order to rationally trust them, we require them to be individuals or organizations with known identities and to have something to lose in case they misbehave, such as reputation or a business that is based on trust.
Order providers are selected by users and every user includes a list of order providers he trusts in every transaction he posts. The list includes 12 order providers, the number is small enough so that users can realistically know the identities of all 12, and the number is large enough so that the system survives random failures of a minority of the order providers.
The lists of order providers can vary from user to user but the lists in the neighboring transactions can only differ by one position.
Now that we have order providers, we can highlight their transactions on the DAG and order all other transactions around the order created by the order providers. It is possible to create such an algorithm (see the white paper for technical details).
However the order is not established immediately, we have to wait for some time until the order providers post enough transactions to be certain about the order of the past transactions.
And since the order is determined solely by positions of order provider transactions on the DAG, all nodes will eventually receive all transactions and arrive at the same view of the order of transactions.
So, we have an agreement about what happened: we agree that every posted transaction is accepted, and we have an agreement about the order of events: it is either evident from the shape of the DAG or is established by looking at transactions posted by order providers. Therefore, we have a consensus.
This is the type of consensus we have in Obyte. And although the admission into the ledger is totally decentralized, order provision in Obyte is currently still centralized as 10 out of 12 order providers are still controlled by the founder, that is me, only 2 are independent. And we are looking for candidates willing to serve as order providers and help us decentralize order provision. (Update of July 2020: order provision is also decentralized now with 7 out of 12 order providers being independent, see our blog article Obyte Achieves Full Decentralization by Adding University of Nicosia as an Independent Order Provider.)
And I’m happy to say that the University of Nicosia is currently setting up their order provider node and is going to be a candidate.
Next, how do we resolve double-spends?
We agree that when there are two transactions trying to spend the same coin, the one that comes earlier in the established consensus order, wins. The other is invalidated by the consensus algorithm.
In case there is a partial order between two double-spends, the order is immediately obvious and everyone just rejects the double-spend attempt.
In case there is no partial order between them, their order is not immediately obvious. The protocol prescribes to accept both and wait until it becomes possible to establish their order relative to transactions from order providers. Then, the earlier one wins, and the later one becomes invalidated.
Although invalidated, the failed double-spend transaction still stays on the ledger because it is already connected to neighboring transactions that didn’t break any rules and didn’t know that this transaction would become a double-spend, and orphaning these innocent transactions would break our fundamental rule that every valid transaction is accepted.
This is again a very important rule that makes the whole system strongly censorship resistant.
Indeed, assume that all the order providers collude in an attempt to censor a specific transaction. They can refuse to accept it as a parent in their own transactions. But it’s not enough, the transaction can still be included indirectly, as a parent of some other transaction issued by some other user who does not participate in censorship. And once the unwelcome transaction is posted, it quickly acquires a lot of children and grandchildren, their number grows like a snowball, and the colluding order providers would also have to censor all those transactions in order to censor a single victim transaction. Ultimately, the entire network would have to be censored, and instead of censorship the conspirators commit sabotage.
To conclude, DAG stays censorship resistant even in case order providers collude and is therefore more censorship resistant than a blockchain, which fails in similar conditions. And this follows from the main property of DAG: that admission into the ledger is totally disintermediated and irreversible.
