Introduction

A BlockDAG (Directed Acyclic Graph) is a data structure used in blockchain technology that differs from traditional linear blockchains. This structure allows for multiple blocks to be created and accepted simultaneously instead of selecting one for the same height, enhancing scalability and potentially reducing confirmation times compared to linear blockchains.

BlockDAG aim to reduce centralization by being flexible in blocks added and increasing security and scalability of the chain.

Topological Order

In the BlockDAG, we use the topological order where each block is assigned a topological height (named topoheight) based on its position in the directed acyclic graph.

The topological height represents the block's order in the partial order defined by the DAG. Blocks with higher topoheight are considered to be later in the order.
This topological order helps establish a consistent and deterministic sequence for the blocks, facilitating a clear understanding of the chronological relationships in the DAG.

The block topological height set in chain is like a dynamic pointer and can be changed at any moment a reorganization occurs until its block height pass in the chain stable height.
In case of more than one branch available in DAG, the order determined is based on the cumulative difficulty (which is the sum of the total difficulty of all its tips) of each block to determine which block is first.

Topological order is a linear arrangement of nodes in a directed acyclic graph (DAG) such that for every directed edge (u, v), node u comes before node v in the sequence. It provides a systematic way to represent dependencies, ensuring that tasks or events are executed or processed in the correct order without encountering cycles in the graph.

Stable Height

BlockDAG implementation allow to reorganize the chain topological order.

To prevent too deep reorganization of the chain in case of attacks or dishonest miners trying to mine older blocks and inject them in chain, a stable height is set to ensure that the topological order will never change from genesis block to the stable height.

Stable height is at minimum 8 blocks height of distance from the main chain top height.

Block Types

It exists differents block types in BlockDAG depending on specific criteria.

Side Block

A side block is when the block A lose the race against another block where block A height is lower or equal to the other block that got ordered before it. It is checking up to STABLE_LIMIT (currently set to 8) past topological ordered blocks. This block is ordered and executed in chain.

Example
Block A is ordered at topoheight 100 and has a height of 95.
Block B is ordered at topoheight 99 and has a height of 96.
Block A is a side block.

Side block reward are 30% of the expected block reward still integrated in main chain, its transactions are verified and executed if not already.

Sync Block

A sync block must be ordered in chain and be in the stable height and should be the only block ordered at its height. Block should also have the higher cumulative difficulty compared to the ordered blocks from STABLE_LIMIT previous blocks height.

Normal Block

It is a block that is neither side or sync. Normal block is ordered and executed correctly.

Orphaned Block

A block can be orphaned when it doesn't meet the difficulty requirements or if it has to deviated from the main chain. If a block was previously ordered it can still be orphaned as long as its in unstable height.

None of its transactions are executed and the miner is not rewarded.

Consensus Rules

Because height is not unique anymore, you can have few blocks at same height and thus, up to 3 previous blocks hashes per block.

During PoW process, you have to select up to 3 heaviest TIPs as previous blocks hashes. They shouldn't have more than 9% of difficulty difference between TIPS selected in the same block.

The same transaction can be added in more than a block if they are not in the same TIP branch.
Client Protocol will handle it by executing it only one time.

Circulating supply, and miner rewards are stored based on the topoheight, which means, each time it changes, those are re-computed.

Transactions are also executed using the topological order and can be re-verified and re-computed if a reorganisation occurs.

Longest chain is the one selected by nodes. But for tips branches conflicts, block cumulative difficulty is used to select the main chain.

Using topological order, you can easily count how many blocks there is in current chain by using the top topoheight.