Handling Deep Reorg in Reorg Scanner

[0xsuryansh]

Background

The current reorg scanner is fairly simplistic and lacks the ability to handle "deep" reorgs that extend beyond a single block. In scenarios like these, it merely displays each consecutive block number as partaking in a reorg. Enhancements to this tool could include the ability to consolidate these into grouped deep reorgs, as well as possibly showcasing instances where multiple branches exist at each reorg junction.

Current implimentation of the reorg sanner

The current scanner works by going through the "Header" table, which stores information about each block. Each entry in the table includes the block number and the block hash. The scanner looks for entries with the same block number but different hashes, which signify a reorg.

Here's a simplified breakdown of the code :

Function FindReorgs:

    Initialize RemoteCursor for Header table in blockchain database

    Call findReorgsInternally function with RemoteCursor

    Output total blocks set and blocks with reorgs (wrong blocks)

End Function


Function findReorgsInternally:

    Initialize empty set map for blocks and empty slice for wrong blocks

    For each entry in Header table using Next method:

        If scanning is interrupted:
            Return error
        End If

        Skip if entry is empty

        Extract block number from entry

        If block number is already in set (meaning it's a reorg):
            Add block number to wrongBlocks slice
        End If

        Add block number to set

    End For

    Return set, wrongBlocks and any errors occurred

End Function

Approach towards scanning deep reorg

Here's a high level idea towards how we can approach this

1. Fetch Header Information: From the Headers table, fetch block header records. These will contain the necessary details about the block, like the block number and hash.
2. Identify Reorgs: The first step to identifying reorgs is to locate blocks with the same block height but different hashes. We can do this by running a query that groups all blocks by block height and then identifies groups with more than one distinct hash. These groups are the reorg points.
3. Classify Deep Reorgs: Now we need to identify 'deep' reorgs, or reorgs that span more than one block. You can do this by checking for consecutive block numbers in the set of reorg points. If a reorg point's block number is one more than the previous reorg point's block number, then these points are part of a 'deep' reorg.
4. Identify Branches: To identify if there are more than one branch at each reorg point, check if there are more than two distinct hashes for a single block number. If so, it indicates multiple branches at that reorg point.
5. Visualize the Data: Building a visualization tool can be very useful for understanding the reorgs and their depths. You could plot the block numbers on the x-axis and the number of distinct hashes on the y-axis to visually represent reorg depth and the number of branches at each point.

Iteration 1 : Identifying deep reorgs

To modify this existing code to scan for deep reorgs, we need to keep track of consecutive block numbers that are part of the same reorg. Additionally, we need to store not just a single block hash for each block number in the set map, but all block hashes for that block number.

Here's a modification of the findReorgsInternally function:

func (c *NodeClient) findReorgsInternally(ctx context.Context,
	template *template.Template,
	rc *RemoteCursor,
) (map[uint64][][]byte, []uint64, []error) {
	var errors []error
	// Map of block number to slice of block hashes
	set := make(map[uint64][][]byte)
	// Keeps track of deep reorgs, i.e., consecutive block numbers with multiple block hashes
	var deepReorgs []uint64

	var k []byte

	var iterator int
	var err error
	for k, _, err = rc.Next(); err == nil && k != nil; k, _, err = rc.Next() {
		select {
		case <-ctx.Done():
			return nil, nil, []error{fmt.Errorf("Interrupted\n")}
		default:
		}

		if len(k) == 0 {
			continue
		}

		bn := binary.BigEndian.Uint64(k[:8])
		blockHashes, found := set[bn]
		if found {
			// If there's more than one block hash for this block number,
			// check if the previous block number is in deepReorgs.
			// If it is, append this block number too.
			// If it isn't, append both the previous block number and this one.
			if len(blockHashes) > 1 {
				if len(deepReorgs) > 0 && deepReorgs[len(deepReorgs)-1] == bn-1 {
					deepReorgs = append(deepReorgs, bn)
				} else {
					deepReorgs = append(deepReorgs, bn-1, bn)
				}
			}
		}
		// Append the block hash to the slice of block hashes for this block number
		set[bn] = append(set[bn], k)

		iterator++
		if iterator%maxCount == 0 {
			if template != nil {
				if err := c.executeFlush(nil, template, "reorg_block.html", bn); err != nil {
					errors = append(errors, fmt.Errorf("Executing reorg_spacer template: %v\n", err))
				}
			}
		}
	}
	if err != nil {
		errors = append(errors, err)
	}

	return set, deepReorgs, errors
}

Now the deepReorgs slice will contain the block numbers of deep reorgs.

Note that int this case block numbers will be repeated if they are part of different deep reorgs.

Limitations of the above approach (iteration 1)

The above approach for identifying deep reorgs does not distinguish between deep reorgs and their respective forks.
The code provided detects deep reorgs by identifying when there is a change in the block hash for the same block number over consecutive blocks. However, it does not track the different branches that might be created during a fork.

Iteration 2 : Identifying deep reorgs and branches

When a reorg occurs, the parent hash of the new blocks will not match the hash of the previous block at the same height. By keeping track of parent-child relationships between blocks, we can determine when a reorg has occurred and also trace the separate branches of the blockchain.

Here's how the code for identifying branches would look like

type BlockInfo struct {
    Hash       []byte
    ParentHash []byte
}

func (c *NodeClient) findDeepReorgsWithBranches(ctx context.Context,
	rc *RemoteCursor,
) (map[uint64][]BlockInfo, []uint64, []error) {
    ...
    // Initialize a map to hold the block numbers that had reorgs and their respective block hashes and parent hashes.
    deepReorgs := make(map[uint64][]BlockInfo)
    ...

    // Extract the block number, hash, and parent hash from the key and value.
    // Where k and v are key and value, fetched from table named headers, using next method of remote cursor.
    bn := binary.BigEndian.Uint64(k[:8])
    hash := k[8:40]
    parentHash := v[4:36]

    ...

    // Check if we've seen this block number before.
    if blockInfos, found := deepReorgs[bn]; found {
        ...
        // Add the current hash and parent hash to the list of block info for this block number.
        deepReorgs[bn] = append(deepReorgs[bn], BlockInfo{Hash: hash, ParentHash: parentHash})
        ...
    } else {
        // We haven't seen this block number before, so add it to the map with its hash and parent hash.
        deepReorgs[bn] = []BlockInfo{{Hash: hash, ParentHash: parentHash}}
    }

    ...
}

The deepReorgs map, represents a sort of "inverted" tree or forest structure where each key is associated with multiple values (hashes of blocks and their parents)
This data structure can help us keep track of all the different versions of a block.

Iteration 3 : Representing the Reorgs as a DAG

Creating a DAG to represent a blockchain, including reorganizations, involves structuring each block as a node and each parent-child relationship between blocks as a directed edge. We will be maintaining a DAG where each block points to its parent block, and forks in the blockchain are represented as nodes in the DAG with more than one child.

type BlockNode struct {
	Hash       []byte
	ParentHash []byte
	Children   []*BlockNode
}

func (c *NodeClient) findDeepReorgsWithBranches(ctx context.Context,
	rc *RemoteCursor,
) (map[uint64][]*BlockNode, []uint64, []error) {
	// Initialize a map to hold the block numbers that had reorgs and their respective block hashes and parent hashes.
	deepReorgs := make(map[uint64][]*BlockNode)
    var errors []error
	...

	// Extract the block number, hash, and parent hash from the key and value.
        // Where k and v are key and value, fetched from table named headers, using next method of remote cursor.
	bn := binary.BigEndian.Uint64(k[:8])
	hash := k[8:40]
	parentHash := v[4:36]

    newNode := &BlockNode{
        Hash:       hash,
        ParentHash: parentHash,
        Children:   []*BlockNode{},
    }

	// Check if we've seen this block number before.
	if blockInfos, found := deepReorgs[bn]; found {
        // This block number has been seen before, indicating a potential reorg.
        // Look for the parent block in the DAG.
        for _, node := range blockInfos {
            if bytes.Equal(node.Hash, newNode.ParentHash) {
                // This node is the parent block of the new node.
                // Add the new node as a child of the parent node.
                node.Children = append(node.Children, newNode)
                break
            }
        }
		deepReorgs[bn] = append(deepReorgs[bn], newNode)
	} else {
		// We haven't seen this block number before, so add it to the map.
		deepReorgs[bn] = []*BlockNode{newNode}
	}
	...

	return deepReorgs, wrongBlocks, errors
}

Each block is represented as a node in a Directed Acyclic Graph (DAG). Each node points to its parent node, and also contains a list of its children nodes, representing blocks that are directly built upon it. A reorganization (or a fork in the blockchain) is represented as a node with more than one child.

This is the updated code for DAG approach:

type BlockNode struct {
	Height     uint64
	Hash       uint64
	ParentHash uint64
	Children   []*BlockNode
}

func (c *NodeClient) findDeepReorgsInternally1(ctx context.Context,
	template *template.Template,
	rc *RemoteCursor,
) map[uint64]map[uint64]uint64 {
	// mapping to store information of blocks on particular height 
	deepReorgs := make(map[uint64][]*BlockNode)
	// store key and value fetched from DB
	var k []byte
	var v []byte
	var err error
	// stores maximum block height in order to find main chain
	var max uint64 = 0
	// store block-height, block-hash, and block's parent hash
	var height, hash, parentHash uint64
	// mapping to store block information corresponding to their block hash
	blocks := make(map[uint64]*BlockNode)
	// bool to avoid adding 1st node as children to a nil node
	var isFirst = true

	// loop to iterate over all blocks as key value pairs and store their info
	for k, v, err = rc.Next(); err == nil && k != nil; k, v, err = rc.Next() {
		// fetch block height, hash, and parentHash from key vlaue pair
		height = binary.BigEndian.Uint64(k[:8])
		hash = binary.BigEndian.Uint64(k[8:40])
		parentHash = binary.BigEndian.Uint64(v[4:36])

		// initialize new block info
		newNode := &BlockNode{
			Height:     height,
			Hash:       hash,
			ParentHash: parentHash,
			Children:   []*BlockNode{},
		}

		// map block info corresponding to its hash
		blocks[hash] = newNode

		// condition to append block info to existing blockInfos according to their block height
		if _, found := deepReorgs[height]; found {
			// add block address as its parent's children
			blocks[newNode.ParentHash].Children = append(blocks[newNode.ParentHash].Children, newNode)
			deepReorgs[height] = append(deepReorgs[height], newNode)
		} else {
			if isFirst {
				isFirst = false
			} else {
				// add block address as its parent's children
				blocks[newNode.ParentHash].Children = append(blocks[newNode.ParentHash].Children, newNode)
			}
			deepReorgs[height] = []*BlockNode{newNode}
		}
		
		// helps in finding longest chain
		if height > max {
			max = height
		}
	}

	// returns empty mapping when no block info is available
	if len(blocks) == 0 {
		return make(map[uint64]map[uint64]uint64)
	}

	// block to iterate over to find main chain
	var node *BlockNode
	var found bool = true
	// mapping to store main block corresponding to its height
	mainChain := make(map[uint64]*BlockNode)
	// maps main block according to its height
	for node = deepReorgs[max][0]; found; node, found = blocks[node.ParentHash] {
		mainChain[node.Height] = node
	}

	// mapping to store info for blockHeight of block from which reorgs are originating -> length of reorgs -> number of reorgs of corresponding length 
	allReorgs := make(map[uint64]map[uint64]uint64)
	for _, node := range mainChain {
		// only iterate when there is a reorg initiating from that block
		if len(node.Children) > 1 {
			// initialize mapping for a particular node height
			allReorgs[node.Height] = make(map[uint64]uint64)
			// iterate over child blocks of node with reorg chains
			for _, block := range node.Children {
				// only iterate if it is not a part of main chain
				if mainChain[block.Height].Hash != block.Hash {
					allReorgs = appendDeepReorgInfo(1, block, allReorgs, node.Height)
				}
			}
		}
	}
	return allReorgs
}

// function to be called upon finding reorgs to store number of reorgs on that height corresponding to that reorg height
func appendDeepReorgInfo(reorgHeight uint64, node *BlockNode, allReorgs map[uint64]map[uint64]uint64, nodeHeight uint64) map[uint64]map[uint64]uint64 {
	// reorg count to be incremented only when node is a leaf node
	if len(node.Children) == 0 {
		// increment reorg count for that reorg height reorg height
		allReorgs[nodeHeight][reorgHeight]++
	} else {
		// iterate over all other blocks to find reorgs of increased length
		for _, block := range node.Children {
			appendDeepReorgInfo(reorgHeight+1, block, allReorgs, nodeHeight)
		}
	}
	return allReorgs
}

The allReorgs map, contains information about reorganizations at different heights and their lengths.

In summary, this function analyzes the blocks in a blockchain to identify deep reorganizations. It constructs a map to represent the main chain and another map to store information about reorganizations at different heights and their lengths.