# Notes on super catchup run logic

### Quick definitions

- Block recap: a block contains a hash of the current ledger, and a `staged_ledger_diff`, which is effectively a list of transactions that change the previous staged ledger to the current block's staged ledger. A transaction is of the form "acct a sends X mina tokens to acct B". It doesn't tell you the balances of acct A and B. The block does not contain the ledger in it's entirety, nor can any account balances be looked up.  https://docs.minaprotocol.com/mina-protocol/whats-in-a-block#staged-ledger-diff

- Breadcrumb: a breadcrumb is a block which has been fully validated and given an attached and connected ledger mask which connects to the previous mask which eventually connects to a ledger, and so an attached mask in essence is a full ledger. Breadcrumbs are the "nodes" in a transition frontier.  Breadcrumbs can only exist if the parent breadcrumb already exists in the transition frontier, because the parent is necessary for validating and of course a fully attached ledger mask can only exist if there exists a previous ledger.  The transition frontier, being made of breadcrumbs, is therefore always fully connected.

- Transition frontier: the transition frontier is a tree of breadcrumbs with max height of `k`, where `k` is a constant defined by the crypto team, currently set at `k = 290`.  The transition frontier is the very most recent `k` number of blocks, as well as all the forks, or sidechains, off of the current longest chain.  The leaf nodes in the transition frontier are referred to as "tips".  The path through the transition frontier (ie a sequence of breadcrumbs from the root to a tip) which is evaluated to be the strongest chain (an evaluation which considers chain-quality and other factors) is considered the current canonical chain, and the tip of this canonical chain is called the best-tip.  

- Bootstrap, high level: bootstrap is the process by which a daemon joins the network, by downloading the believed best tips of other nodes, converging on the new best-tip, and thereby synchronizing to the network's best tip.  This process is altogether similar to the process of staying in sync to the chain on a regular basis

- Catchup, high level: catchup is invoked whenever there is a "gap" in the transition frontier, or more specifically when a new block cannot be connected and added to the transition frontier. bootstrap, when it finishes, should yield us a fully connected transition frontier from the frontier root to the best tip. However there will always be sidechains such that bootstrap almost inevitably creates a number of catchup jobs.  In such a case, the tips of the sidechains are passed to catchup, and catchup needs to fill in the gaps and connect it to a known breadcrumb in the transition frontier.  Catchup jobs are also created whenever the network for whatever reason doesn't deliver to a daemon recent blocks in time, creating a gap in the transition frontier, and as such catchup will be invoked.

- catchup scheduler: the scheduler is not a part of catchup, however it controls the logic of when catchup should be invoked.  When a block that has no parent is received, it gets passed to the scheduler, which then usually waits some time to see if the parent gets gossiped, and if it hasn't been, then the scheduler invokes a catchup job. 

- normal and super catchup: there's two kinds of catchup in the code, normal and super catchup.  They both do the same thing, normal catchup is simply the older deprecated version.  At this moment, by default super catchup is used.  there is a mina flag `--no-super-catchup` which instructs the daemon to use the older normal-catchup, although nearly no one does this.  The already deprecated “normal” catchup will be removed at some point and then “super” catchup will become the only catchup.  Unless otherwise noted, everything in this doc describes super catchup, which at this point is more normal than normal catchup.

### Catchup specifics

- super catchup uses a data structure called `full_catchup_tree`.  Each node of this tree basically represents a block that needs to be downloaded, verified, validated, and turned into a breadcrumb and added to the transition frontier (arguably it would be better to name them "jobs" instead of "nodes").  Each job goes through those phases.
    - the catchup tree is a trees of hashes of blocks, which are in a pending state and need to be downloaded and processed into the transition frontier. (it's actually a forest and not one tree, but this is just because the scheduler passes to catchup a bunch of blocks in a tree minus their common root, so it becomes a forest)
- within the `run` function of super catchup, first it sets up a number of dependencies and creates a few aux functions.
    - there is a very important interior function defined within the super_catchup run function called `run_state_machine`. `run_state_machine` is a state machine which puts each node (ie a block we want to perform catchup on) of the catchup tree through it's phases.  For each block we want to perform catchup on, we call `run_state_machine` on it.  The function looks like a big match-case expression that handles all the stages of a node by waiting for conditions and triggering actions, and then recursively calling itself to enact a state transition on that catchup-tree node, and thusly progress that catchup-tree node to a subsequent stage. The states can be `To_download`, `To_initial_validate`, `To_verify`, `Wait_for_parent`, or `To_build_breadcrumb`.  `run_state_machine` thereby moves a catchup-tree node through these states until the function eventually exits when the node reaches either `Finished` when it is fully processed, or the `Failed` state.  
    - the downloader is also created in the beginning of the `run` function. has a list of blocks that need to be downloaded. super-catchup downloads in a more forward order towards the target, as opposed to the deprecated normal-catchup which did it backwards
- the main operative line in super catchup starts with `Strict_pipe.Reader.iter_without_pushback catchup_job_reader ~f:(fun (target_parent_hash, forest) -> <......> )`. The large anonymous function defined in `~f` has all the real business logic in catchup.  This line uses Strict_pipe to define the reader end of a pipe.
    - the scheduler has the writer end of this pipe.  The scheduler will bundle up node/jobs(/ie connected blocks that don't connected further) into a forest structure and pass it into the pipe.  The `catchup_job_reader` reads from this pipe, passes the following arguments to the aforementioned large anonymous function of-- 1: a `target_parent_hash`, and 2: a `forest` of catchup jobs. the `target_parent_hash` input argument is relevant for the downloader.  `target_parent_hash` is the parent of the oldest missing block we have received through gossip (though this oldest missing block is not necessarily all that we need).  the `forest` contains the blocks that were received but have `target_parent_hash` as their parent, so on other words if `target_parent_hash` was added to the forest, then the `forest` would become a simple tree with `target_parent_hash` as the root.
    - the first `don't_wait_for` interacts with a pipe that connects to the downloader.  It updates some context info for the downloader
    - the second `don't_wait_for` is by far the bulk of the work in super catchup.
        - first, the `state_hashes` var is obtained.  A part of this involves checking using the function `try_to_connect_hash_chain` to see if `target_parent_hash` is the oldest block the daemon is missing— ie that the parent of `target_parent_hash` is already in the daemon's transition frontier.  If so, then we're good to go; but if not, then that means there are further missing blocks, and the downloader is called with function `download_state_hashes`, which makes sure to contact peers over the network in order to download the whole chain of block hashes going back to a block who's parent is in the daemon's existing transition frontier.
        - what `state_hashes` actually is, is a tuple where the first member is the root (of the forest/tree segment i think), and the second member is a list of block hashes of the blocks in the forest (i think).  A result type takes 2 arguments-- the first is the Ok type, the second is the Error type.  the Ok type is a tuple of (the node or breadcrumb, a list of hashes).  the Error type is a list of ad-hoc error codes.  state_hashes is of type:
        
        ```ocaml
        ([> Breadcrumb of Breadcrumb.t | Node of Node.t ] * (Marlin_plonk_bindings_pasta_fp.t list),
         [> Failed_to_download_transition_chain_proof | Invalid_transition_chain_proof | No_common_ancestor | Peer_moves_too_fast ] list
        ) result
        ```
        
        - the next thing that happens is that `run_state_machine` gets called on every catchup node.  this state machine will, through recursion and blocking, automatically attempt to build jobs into breadcrumbs and add to transition frontier.  if jobs get run out of order, then they will enter the `Wait_for_parent` state and block, and then unblock when the parent job is completed.  as such it doesn't really matter what order jobs get called with `run_state_machine` on.  eventually this state machine will run through all the phases, and finish.  If the full block hasn't been downloaded, it gets downloaded in the `To_download` state.  Otherwise, the most important phases are `To_verify` where the verifier (an external golang process) will be called, and `To_build_breadcrumb` which builds the catchup job/node into a breadcrumb, and then connects it to the transition frontier, thereby finishing catchup for that block.
