Skip to main content

DAG structure

DAG (Directed Acyclic Graph), is proposed again as a new underlying ledger structure. "Directed" refers to directional, "Acyclic" refers tonot cyclic，no return.

DAG model​

image

It’s obvious that the Merkle tree belongs to a type of directed tree structure, where each vertex in the tree can only point to one previous vertex, and the entire data has an obvious flow direction.DAG structure allows each vertex to point to multiple previous vertices, and the entire data flow has an obvious direction.Another data structure is directed graph, which is different from a DAG in that a directed graph allows data to flow back, and the data flow in the entire structure is not very clear. The differences among the three are shown in the figure.

Advantages of DAG structure​

In DAG, there is no concept of block. Its constituent unit is a single transaction, which records the transaction of a single user. This eliminates the time needed to package blocks.The verification method depends on the verification of the previous transaction by the next transaction. In other words, to make a transaction, and the number of transactions to be verified depends on different rules. This verification method enables DAG to write many transactions asynchronously and concurrently, and ultimately forms a topological tree structure, which can greatly improve scalability.

In the context of blockchain, it is difficult to significantly improve scalability while ensuring decentralization and security, making it difficult to commercialize. DAG is decentralized in theory. If the network is powerful enough, the security can also be guaranteed, and more importantly, the scalability can be greatly improved.Distributed database with DAG technology can greatly improve transaction throughput and reduce transaction fees to a minimum.

DAG in Blockchain​

Blockchain is a special kind of DAG structure[^10]. In From Blockchain to DAG (I) - Blockchain's Ledger Structure and Consensus Mechanism, it is said that whether a blockchain forks or not is related to the block out speed and the broadcast speed. When the outgoing block speed exceeds the broadcasting speed, there will be a situation where multiple blocks are broadcasting at the same time, and forks are created. The more forks there are, the less secure it is. Bitcoin has found a balance between performance and security in order to reduce forks: one block every ten minutes. Now let's assume that each block is out for a long enough period of time that there is no chance of a new block being mined before the previous block has finished broadcasting. Then the structure of this blockchain is a single chain.

image.png In practice, forks are inevitable due to network delays and other reasons, so the actual blockchain structure will be as shown in the diagram, and then only one of the valid main chains (yellow) will be taken through the ledger consensus, and the transaction information in the rest of the blocks (red) will be invalid and won't be adopted.

image Transformers adopts DAG structure to avoid packing out blocks in traditional blockchain which cannot be executed concurrently. If you change the chain storage structure of blocks into a DAG mesh topology can be written concurrently. In the case of block packing time remains unchanged, the network can pack N blocks in parallel, and the transactions in the network can accommodate N times. the combination of DAG and blockchain is to solve the efficiency problem, after the transaction is initiated to broadcast the network directly to confirm. From the macro view of the graph theory topology model, the evolution from single chain to tree and mesh, the refinement from block granularity to transaction granularity, and the leap from single-point to concurrent writes have all led to a qualitative leap in Transformers efficiency.