Weighted chain comparisons and weighted chain selection

[amesgen]

The goal of this ticket is to make all chain comparisons weighted in the abstract Consensus layer, which in particular will give us weighted chain selection.

This excludes standalone chain selection for new certificates, see

[amesgen]

Notes on weighted chain comparisons

Current usage of preferAnchoredCandidate/compareAnchoredFragments

• ChainSel

  Rough overview of ChainSel: For a new block B:

  • Construct all fragments forking off from the current selection involving B.

  • Only keep those fragments that are preferrable to our currently selection according to preferAnchoredCandidate.

  • Sort the remaining candidates based on compareAnchoredFragments.

  • Adopt the first valid such candidate.

• BlockFetchConsensusInterface

  • In Praos mode:

    Similar to ChainSel: only keep candidates preferrable (preferAnchoredCandidate) to our selection, prioritize downloading their blocks based on compareAnchoredFragments.

  • In Genesis mode (DevotedBlockFetch):

    Always download along the best (according to compareAnchoredFragments) chain preferrable to our selection (according preferAnchoredCandidate).

• GSM

  Uses preferAnchoredCandidate to make sure that no candidate header chain is preferrable to our selection when we transition to CaughtUp from Syncing.

• ChainSync client

  We use it to disconnect if we are stuck at the forecast horizon and the candidate is not better than the selection.

  This is relevant for an edge case in Ouroboros Genesis, see here and here.

Currently, the precondition of preferAnchoredCandidate/compareAnchoredFragments is that the two fragments either are both non-empty or that they intersect. This precondition is currently established in the following ways:

• ChainSel

  • preferAnchoredCandidate: We only construct candidates that are connected to our selection, so they intersect with it.

  • compareAnchoredFragments: All candidates intersect because they contain the block that is currently being processed.

• BlockFetchConsensusInterface:

  • preferAnchoredCandidate: Rather involved (and requires further case distinctions), see the plausibleCandidateChain implementation.

  • compareAnchoredFragments: Only non-empty candidates are interesting for BlockFetch (which is ensured by plausibleCandidateChain).

• GSM

  • preferAnchoredCandidate: The precondition that the fragments intersect is established explicitly (cf CandidateDoesNotIntersect)

• ChainSync client

  • ourFrag and theirFrag always intersect by construction.

Proposed change

The functions preferAnchoredCandidate/compareAnchoredFragments would take an additional argument (PerasWeightSnapshot or similar), and the precondition would be tightened to "the fragments must intersect" (as now the entire respective suffixes after the common intersection are relevant).

Apart from type tetris, this change has the following implications:

• The stronger precondition needs to be argued for at call sites.

  This is straightforward in almost all cases, with the exception of triggering ChainSel for LoE-postponed blocks in the context of Genesis (ChainSel.ReprocessLoEBlocks: ensure trigger block is not on chain IntersectMBO/ouroboros-consensus#1598), as well as in the BlockFetchConsensusInterface:

  • plausibleCandidateChain can categorically consider candidates that do not intersect with our volatile candidate as implausible (as it is already doing today in the case where the candidate is empty).

  • compareAnchoredFragments: The precondition is currently not true as it is invoked on chain suffixes (see ChainSuffix in the BlockFetch decision logic) which might not intersect. However, this is easy to fix, namely by also storing the candidate prefixed with the corresponding prefix of the selection.

• Call sites that previously woke up whenever the selection/candidate fragments changed and invoked preferAnchoredCandidate/compareAnchoredFragments need to be changed to also wake up when the Peras weights changed (because a new certificate arrived).

  This is trivial to do in all cases but the ChainSync client, see ChainSync client: remove checkPreferTheirsOverOurs (instead enriching the GDD) #64.

• As preferAnchoredCandidate/compareAnchoredFragments perform an intersection underneath, AF.intersect might need to be optimized. See Speed up AF.intersect IntersectMBO/ouroboros-network#5157

Reminder: Genesis

Of course, the Genesis Density Governor needs to be adapted, but this will happen later. It will also not directly involve preferAnchoredCandidate/compareAnchoredFragments (as those involve candidate fragments).

[amesgen]

Note though that something we definitely need already now (even if we don't do #71 for now) is the property that switching to a shorter chain must not cause the immutable tip (defined as the anchor of the getCurrentChain fragment) to recede.

This requires changes to the current definition of getCurrentChain, which right now just returns the k most recent blocks on the internal cdbChain fragment (which can be longer than k if some blocks have not yet been garbage-collected).

An ad-hoc way to achieve this would be:

• Store the most recent immutable tip in a TVar, and only update it when we switch to a longer chain (but not when we switch to a shorter one).
• In getCurrentChain, if the k most recent blocks still contain the immutable tip from that TVar, only return the suffix after it.

This way, we ensure that the immutable tip never recedes, at the (unavoidable) cost that getCurrentChain returns less than k blocks in more cases. Previously, it did this only near Genesis or after a restart when there was data loss in the VolatileDB; these scenarios mean that we already handle this case correctly (see eg here for an (innocent) exception).

This also requires adapting the LedgerDB; ideally by making it unaware of which states are immutable (and rather handling this in the ChainDB when wrapping certain operations of the LedgerDB). This has synergies with IntersectMBO/ouroboros-consensus#1513.