Merge chains flowchart

merge-chains-flow.md

Merge chains logical flow

Rules

Section A (main loop)

1. Iterate both original and update chains backward from the tip
2. If both are None goto B
3. Compare heights
   • If the update is greater, add to changeset, and advance the update chain
   • If the original is greater, mark the original block ID as potentially invalid, and advance the original chain
     • If the update is exhausted, goto B
   • If equal height, compare block hashes
     • If equal hash
       • If we have not yet found an agreement height after traversing elements of both sides, throw CannotConnectError due to ambiguity
       • Store the agreement height. Return early if the update is a superset of the original and the Arc pointers match
     • If unequal hash
       • Evict all of the blocks marked potentially invalid as indicated by a None at that height in the changeset
       • Add the new block to the changeset
     • Advance both iterators

Section B (resolution)

1. If no agreement height is found, and no explicit invalidation occurred after traversing items of the original chain, throw a CannotConnectError
2. Try to apply the changeset to the original chain, propagating the error if any
3. On success return the new tip and the resulting changeset

How does the behavior change once ToBlockHash::prev_blockhash is introduced?

• We have another tracking variable for each of original and update prev_blockhash_original, prev_blockhash_update
• Enables implicit connection between adjacent heights (2 cases)
  1. Original block hash agrees with the previous prev_blockhash_update
  2. Update block hash agrees with previous prev_blockhash_original
• Since an agreement height is found we avoid the error that would otherwise be caused by ambiguity or lack of agreement. Note that while the implicit connection is allowed, we still mandate the explicit invalidation, that is, we don't allow "implicit invalidation".

Flowchart

                    START merge_chains
                           |
                           v
            Initialize iterators and tracking variables
                           |
                           v
                ┌─────────────────────────────┐
                │        Section A            │
                │       (Main Loop)           │
                └─────────────────────────────┘
                           |
                           v
                ┌─────────────────────────────┐
                │ Iterators have items?       │
                │                             │
                │ original_iter.peek()        │<───────────────────────────────────┐
                │ update_iter.peek()          │                                    │
                └─────────────────────────────┘                                    │
                           |                                                       │
                ┌────NO───────────────┐                                            │
                │                     │                                            │
                v                     │                                            │
      ┌─────────────────┐             │                                            │
      │  Goto Section B │             │                                            │
      │                 │             │                                            │
      └─────────────────┘             │                                            │
                |                     │                                            │
                │                     │                                            │
                │               YES   │                                            │
                │                     v                                            │
                │         ┌─────────────────────────────┐                          │
                │         │     Compare Heights         │                          │
                │         │                             │                          │
                │         │ update_height vs            │                          │
                │         │ original_height             │                          │
                │         └─────────────────────────────┘                          │
                │                     |                                            │
                │        ┌────────────┼────────────┐                               │
                │        │            │            │                               │
                │  UPDATE > ORIG  ORIG > UPDATE  EQUAL                             │
                │        │            │            │                               │
                │        v            v            v                               │
                │ ┌─────────────┐ ┌──────────────┐ ┌─────────────────┐             │
                │ │Add to       │ │Mark as       │ │Compare          │             │
                │ │changeset    │ │potentially   │ │block hashes     │             │
                │ │             │ │invalid       │ │                 │             │
                │ │Advance      │ │              │ │                 │             │
                │ │update iter  │ │Advance       │ │                 │             │
                │ └─────────────┘ │original iter │ │                 │             │
                │        │        └──────────────┘ └─────────────────┘             │
                │        │               │                          │              │
                │        │               v                          │              │
                │        │        ┌──────────────┐                  │              │
                │        │        │Update        │                  │              │
                │        │        │exhausted?    │                  │              │
                │        │        └──────────────┘     NO           │              │
                │        │               |         (continue)       │              │
                │        └────────────── ┼──────────────────────────┼────────────> ┘
                │                   YES  │                          │              ^
                │                        v                          │              │
                │                 ┌──────────────┐                  │              │
                │                 │Goto Section B│                  │              │
                │                 └──────────────┘                  │              │
                │                        │                          │              │
                │                        │                          │              │
                │                        │                          │              │
                ┌ < ─────────────────────┘                          │              │
                │                                                   │              │
                │                                                   v              │
                │                                         ┌─────────────────┐      │
                │                                         │   EQUAL HASH?   │      │
                │                                         └─────────────────┘      │
                │                                                   |              │
                │                                         ┌─────────┼              │
                │                                         │         │              │
                │                                       YES        NO              │
                │                                         │         │              │
                │        ┌────────────────────┐           v         v              │
                │        │        ERROR       │ ┌─────────────┐ ┌──────────────┐   │
                │        │ CannotConnectError │ │Check for    │ │Explicit      │   │
                │        └───────────── ^ ────┘ │ambiguity    │ │invalidation  │   │
                │                       └───────│             │ │              │   │
                │                               │             │ │Evict all     │   │
                │                               │Agreement    │ │potentially   │   │
                │                               │height       │ │invalid blocks│   │
                │        ┌────────────────────┐ │found!       │ │              │   │
                │        │      SUCCESS       │ │             │ │Add new block │   │
                │        │(new_tip, changeset)│ │Early return │ │to changeset  │   │
                │        └──────────── ^ ─────┘ │if superset  │ │              │   │
                │                      └─────── │& Arc match  │ │              │   │
                │                               └─────────────┘ └──────────────┘   │
                │                                         │         │              │ 
                │                                         │         │              │ 
                │                                         v         v              │
                │                               ┌─────────────────────────────┐    │
                │                               │Advance both iterators       │    │
                │                               │                             │    │
                │                               │Continue main loop           │    │
                │                               └─────────────────────────────┘    │
                │                                         │                        │
                │                                         │                        │
                └──────────┐                              └────────────────────────┘
                           |
                           v
                ┌─────────────────────────────┐
                │        Section B            │
                │     (Reconciliation)        │
                └─────────────────────────────┘
                           |
                           v
                ┌─────────────────────────────┐
                │ No agreement found AND      │
                │ no explicit invalidation?   │
                └─────────────────────────────┘
                           |
                ┌─────────YES─────────┐
                │                     │
                v                    NO
      ┌─────────────────┐             │
      │       ERROR     │             │
      │CannotConnectError             │
      └─────────────────┘             │
                ^                     │
                │                     v
                │         ┌─────────────────────────────┐
                │         │Apply changeset to original  │
                │         │chain tip                    │
                │         └─────────────────────────────┘
                │                     |
                │              ┌──────┼──────┐
                │              │             │
                │           ERROR            │
                │              │             │
                │              v             │
                └──────────────┘             │
                                         SUCCESS
                                             │
                                             │
                                             │
                                             │
                                             v
                                ┌─────────────────────────────┐
                                │Return (new_tip, changeset)  │
                                │                             │
                                └─────────────────────────────┘