All About Directed Acyclic Graphs

Sui's record-breaking transactions-per-second performance comes partially due to a mathematical construct, the directed acyclic graph (DAG). This construct speeds up network transactions by processing them in the most efficient manner, rather than a first-come, first served linear progression.

Combining the non-linear nature of a DAG with a blockchain, a distributed ledger designed to ensure data integrity, entwines the virtues of two technologies. As a blockchain network, Sui preserves historicity and custody of data objects, while its DAG-based consensus system makes manipulation of those data objects nimble.

What is a DAG?

A DAG is a type of data structure differing from the linear chain structure of traditional blockchains. Unlike blockchains, which consist of blocks linked together in a linear fashion, DAGs are more like a web of interconnected nodes. To understand DAGs, let's first break down the acronym in reverse order. 

In the context of distributed ledger technology, a graph database organizes data using interconnected structures akin to a web of relationships. The relationships between each individual data entry, or transaction, with others is used to form a network of information based on causal relationships. Through this approach, complex transactional relationships and dependencies are captured in the network.

Adding acyclic to the definition means there is no way to create a loop or cycle within the ledger or database. In other words, it is impossible to create a path within the database that leads to a situation where an earlier transaction relies on a later transaction. This property ensures that information flows in a one-way direction, bringing us to the final part of the acronym, directed. Being a directed graph, each relationship has a defined direction indicating the flow of information within the database. The directed nature allows for clear and unambiguous data flow, crucial for maintaining integrity and facilitating efficient processing of transactions.

In summary, a DAG is a database structured as a network of interconnected pieces of information, or transactions, that are linked together based on their dependencies forming a graph that expands with each new transaction.

Blockchains and DAGs

Blockchains typically batch a group of transactions into a block which then go through a consensus process as a single entity. Blocks are linked together in a linear fashion which requires that the network’s state changes in a stepwise manner, block by block. On the other hand, transactions within a DAG are able to achieve consensus independently, bypassing the process of grouping many transactions into a block for the consensus process. 

In a blockchain, all the network validators have an agreed upon network state that they all work from. Validators assess a single group of transactions at the same time and cannot progress until a supermajority has come to an agreement on the validity of the block. For a block to be considered valid and be cemented into the blockchain, all of the transactions within that block must be valid. If a single transaction within the block is not valid, the entire block is discarded and must be recreated without the invalid transaction. Achieving consensus in a blockchain requires the validators to operate in lockstep, approving transactions block by block.

Similar to how consensus is achieved in a blockchain, transactions within a DAG achieve consensus once signed-off by a supermajority of the network validators. A key difference lies in the fact that each validator within a DAG has a different subset of the network state. In other words, the entire network state is not stored in each validator but instead can only be observed by cumulating individual validators' understanding of the network. 

There is no block of transactions that is validated at once by all validators, instead individual transactions are propagated throughout the network gaining signatures from individual validators that have knowledge of the network state needed to validate the transaction. Once the transaction obtains signatures from a supermajority of the network validators, it has achieved consensus and is considered finalized.

As a result of this structure, utilizing a DAG for transaction propagation and consensus allows for transactions to be confirmed asynchronously and concurrently, offering a more flexible and scalable approach compared to blockchains.

From DAG to Sui blockchain

Sui utilizes a DAG for transaction propagation and consensus and then, in a separate process, orders transactions into checkpoints, which are similar to blocks. Checkpoints are linked together and ordered in a linear fashion, similar to the structure of a typical blockchain. The main difference about Sui's blockchain structure is that transactions grouped into checkpoints are already finalized, in contrast to typical blockchains structures which group transactions not yet finalized into blocks. 

The main difference about Sui's blockchain structure is that transactions grouped into checkpoints are already finalized, in contrast to typical blockchains structures which group transactions not yet finalized into blocks.

Linking it all together

Sui's innovative approach combines the best features of both DAGs and blockchains, creating a network that offers unparalleled speed and flexibility. By utilizing a DAG for transaction propagation and consensus, Sui ensures that transactions can be confirmed asynchronously and concurrently, allowing for a more scalable and efficient system compared to traditional blockchains. However, to maintain the integrity and order of historical information, Sui employs a separate process to organize transactions into checkpoints, akin to blocks in a blockchain.  

These checkpoints are then linked together and ordered in a linear fashion, providing a familiar structure for storing and accessing historical data. Unlike traditional blockchains where transactions are grouped into blocks before consensus, in Sui transactions included in checkpoints are already finalized, offering a streamlined and efficient approach to transaction validation and storage. 

This hybrid architecture allows Sui to harness the benefits of both DAGs and blockchains, creating a robust and adaptable platform for decentralized applications and smart contracts.

Note: This content is for general educational and informational purposes only and should not be construed or relied upon as an endorsement or recommendation to buy, sell, or hold any asset, investment or financial product and does not constitute financial, legal, or tax advice.