A blockchain network decides which block to consider valid through a process called consensus. Bitcoin uses Nakamoto consensus which determines the correct chain by the one with the most amount of work done on it. Ethereum uses modified GHOST consensus which factors in the production of stale or “uncle” blocks into the consideration of longest chain.
Hierarchical Longest Chain Rule follows similar mechanisms to Nakamoto & GHOST with additional constraints of child chain organization. This set of decisions comes down to a fairly simple outcome: the parent chain always wins.
HLCR derives its usefulness through coordinating decision making in hierarchical distributed systems. To illustrate the multi-ploy process in a more familiar domain, consider the allocation of a companies budget to various departments, which in turn allocate to individual employees. In this scenario the company must consider the immediate gains of the top-down decision with the known input of the individual employees. The approach to solving the above type of multi-ploy decision problem is known as multi-level programming.
In the event of conflicting decisions within the hierarchy, tie-breaking between subgraphs occurs through performing a branch and bound algorithm on the known space. In HLCR this branch and bound algorithm is a maximization function of the work performed within the subtree. This multi-ploy optimization function allows for coordinated finality across the hierarchy since a dominant chain can flip between decision states based on knowledge of greater subordinate work up until the point a block has been built upon it.
Head Choice Resolution Examples
Let’s consider the scenario of a single parent and child chain relationship. Here two different blocks are competing to be included in the Z1 chain.
The two blocks have been created such that Z1* #8 is also a block in Region while the Z1 #8 is a sole Zone block. Following the ruleset that the parent chain always wins, the canonical block would become Z1* #8 since it is a subordinate of R1 #3. This in turn uncles the Z1 #8 block.
Consider a fork within a dominant chain at block #2 for R1 and R1*. The fork has subordinate extensions up to Z1 #4 and Z1* #7 respectively. HLCR dictates that R1* #2 would be canonical due to the heavier subordinate extension at Z1* #7.
Based on network latencies and the extent to which R1 #2 was perceived as canonical, there exists a non-zero subset of blockchain nodes that will need to synchronize to the R1* #2 and Z1* #7 chains. In this process of synchronization the R1 #2 block and its subordinate extension to Z1 #4 will be marked as uncles and considered non-canonical.
Conclusion
The rulesets defined in BlockReduce and HLCR can be generalized across a multi-level hierarchy such that many shards can individually achieve consistency as network level consensus is delayed. Along with individual consistency, strict topological ordering is applied via HLCR such that shards have proper global order while running in parallel. The decoupling of consistency and consensus allows for a multi-threaded approach to blockchain scalability that is truly one of a kind.