The canonical chain discovery algorithm takes a list of precomputed block paths and classifies them into 3 distinct categories:
- Deep Canoinical Blocks: These are blocks that form a canonical chain from the genesis block up to the witness root.
- Recent Blocks: These are blocks that extend the deep canonical blocks but do not meet the threshold criteria to be classified as deep canonical.
- Orphaned Blocks: These are blocks that aren’t part of the deep canonical chain or recent blocks.
Witness Root: The highest block in the lowest contiguous chain with a sufficient number of ancestors.
Canonical Threshold: The minimum number of consecutive ancestors blocks that a block must have to be consideredd part of the deep canonical chain.
- Sort blocks by length: Sort block paths in ascending order based on their heights.
- Identify contiguous sequences: Identify the starting indices and differences in heights between contiguous sequences of blocks.
- Find the Witness Tree Root: Determine the root block of the deep canonical chain, which has the required number of ancestors (canonical threshold).
- Backtrack to Genesis: From the witness tree root, backtrack to the genesis block to collect all deep canonical blocks.
- Categorize Remaining Blocks: Classify blocks higher than the witness tree root as recent blocks and the remaining blocks as orphaned blocks.
It's conceptually simple, the devil is in the details.