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 greater topoheight are considered to be later in the order.
The 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

The BlockDAG implementation allows reorganizing the topological order of the chain.

A stable height is set where blocks with a lower topological order can not be reorganized. This is done to prevent deep reorganization of the chain by attackers or dishonest miners trying to mine and inject older blocks into the chain. The topological order of the chain will never change from the genesis block to the stable height.

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

Block Types

Four different types of blocks are used in the BlockDAG, each with their own purpose.

Side Block

A side block is found when the block A loses the race against another block where block A's 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 rewards 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. This block should also have the higher cumulative difficulty compared to the previous STABLE_LIMIT height ordered blocks.

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, a few blocks can exist at same height and thus, up to 3 previous blocks hashes per block.

During the PoW process, up to 3 heaviest TIPs are selected as previous blocks hashes.

Between TIPS selected in the same block, they shouldn't have more than 9% difficulty difference.

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 exist in current chain by using the top topoheight.