Change implementation of ticking in the HFC to tick-then-translate-then-tick

[amesgen]

Status quo

Currently, when ticking a ledger state across an era boundary in the HFC, we use the translate-then-tick strategy.

Click to see current implementation details

HFC ticking is implemented here:
https://github.com/input-output-hk/ouroboros-consensus/blob/0ca9ca08f41b04619dc9ed1df692102ef9ba3c0e/ouroboros-consensus/src/ouroboros-consensus/Ouroboros/Consensus/HardFork/Combinator/Ledger.hs#L121-L154

Note that we first translate in extendToSlot if the target slot is in a new era:
https://github.com/input-output-hk/ouroboros-consensus/blob/0ca9ca08f41b04619dc9ed1df692102ef9ba3c0e/ouroboros-consensus/src/ouroboros-consensus/Ouroboros/Consensus/HardFork/Combinator/State.hs#L212
https://github.com/input-output-hk/ouroboros-consensus/blob/0ca9ca08f41b04619dc9ed1df692102ef9ba3c0e/ouroboros-consensus/src/ouroboros-consensus/Ouroboros/Consensus/HardFork/Combinator/State.hs#L226-L228

This means that when we tick a ledger state s in era FromEra (which arose by applying a block with slot x) to a slot y in the next era ToEra, we

• first translate the FromEra ledger state s to a ToEra ledger state s' (s' is now a FromEra ledger state, even though its tip slot x hasn't moved, so is still before the era boundary), and
• then tick s' to slot y,

yielding the ledger state s''' we can use to validate blocks in slot y.

In the following diagram, this means that we start at s, first go right and then down.

╔══════════════╦═════════════════════════════════════╗
║ Time \ Era   ║ FromEra ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌⇢ ToEra ║
╠══════════════╬═════════════════════════════════════╣
║  Start - x   ║     s ──── translate ────────→ s'   ║
║      ┊       ║     │╲                         │    ║
║      ┊       ║  tick ╲tick                    tick ║
║   Boundary ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ ║
║      ┊       ║     │   s' ── translate ─→ s'' │    ║
║      ┊       ║     │                      ╲   │    ║
║      ┊       ║     │                   tick╲  │    ║
║      ┊       ║     │                        ╲ │    ║
║      ⇣       ║     ↓                         ↘↓    ║
║  Target - y  ║     s' ─── translate ────────→ s''' ║
╚══════════════╩═════════════════════════════════════╝

Why the status quo is problematic

The current behavior is causing IntersectMBO/cardano-ledger#3491; we need some context how Ledger handles updates to the on-chain protocol parameters before Voltaire (ie in all Shelley-based eras before Conway):

• At every epoch boundary, the protocol parameters can change if sufficiently many Genesis keys submit the same update proposal.
• This logic is handled by the UPEC rule, which is executed when eg ticking.

This mechanism changed completely in Conway; in particular, there is no direct analogue to update proposals signed by Genesis keys. This means that all such proposals are discarded when translating a Babbage ledger state to a Conway ledger state.

Hence, as we currently first translate and then tick, the Conway logic responsible for ticking has no way of knowing that it should update the protocol version (or any other updateable parameter).

Proposed change

In this issue, we suggest to change the HFC cross-era ticking to the tick-then-translate-then-tick approach, ie first tick to the epoch boundary, then translate the ledger state, and then tick to the requested slot.

In more detail: In order to tick a ledger state s (with tip x) in era FromEra to a slot y in the next era ToEra, we

• first tick the ledger state s to the first slot in FromEra, yielding a ledger state s',
• then translate the FromEra ledger state s' to a ToEra ledger state s'', and
• finally tick the ledger state s'' to slot y

again yielding the desired ledger state s'''.

In the diagram above, we again start at s, tick by moving diagonally to s', then translate by moving horizontally to s'', and finally tick again by moving diagonally to s'''.

This way, we use the FromEra logic to tick across the era/epoch boundary, which can then execute the UPEC rule in the example above.

Slogan: Cross-era ticking is fundamentally something that happens at the end of an era, so it should be done using the logic of that ending era.

Alternatives

We considered the following alternatives:

1. Use the tick-then-translate apprach, ie tick directly to the target slot, and then translate.

   While this would probably work fine with existing any likely also with future eras, it seems wrong to use the ticking logic of the old era to let time pass across slots that lie purely within the new era. Also, we again have (just before translating) a ledger state in the "wrong" era as with the current translate-then-tick approach.

2. Don't change the HFC logic at all, but rather introduce an ad-hoc field in the Conway ledger state that records the Babbage update proposals, such that they can be preserved by translating.

   This seems quite ugly, ie this field would only be present in the first Voltaire era, and it would require ledger rule logic that is purely related to era transitions, which is something that the ledger rules usually do not have to handle explicitly.

Remarks

Note that the HFC mechanism that detects whether we should transition in the first place (see singleEraTransition) is not affected by this bug; we still properly transition from Babbage to Conway.

[nfrisby]

A hypothetical scenario that would conflict with tick-then-translate:

Suppose the first epoch (or every, but at least the first) of an era involves some big calculation that is incrementalized by the ledger rules. If we use the previous era's rules to tick across some of the first slots of that era, then the new era's incrementalized calculation wouldn't happen in those slots, unless the translation function anticipated this and therefore also invoked that aspect of the ticking logic.

A comparable criticism can be made against tick-translate-tick, but I think it requires more niche assumptions.

Suppose some new era expects that its epoch-transition logic is invoked at the very beginning of the era. If we only tick across that epoch transition using the previous era's rules, then this logic won't be invoked, unless the translation function anticipates this and explicitly duplicates/invokves that desired epoch-transition logic.

I claimed that is more niche, since, as far as I know, all of the epoch-transition logic in the existing Cardano eras would have no effect if it were executed at the epoch-transition that demarcates the beginning of that era.

Relatedly, it's notable that the initial Byron ledger state considers the first slot to be the "latest slot" (... there is assumed to be an EBB in it :/) and the first epoch to be the "current epoch". So, at least for the Cardano eras so far, it seems all epoch-transition logic is assumed to happen only at the end of an epoch, which is compatible with the proposed tick-translate-tick semantics (and any desired exceptions to that assumption could be snuck into the translation functions). See here.

It's also notable that our intuitive rule for when the HFC actually transitions to the next era is whenever a Cardano era's rules increase the major protocol version. Those governance rules have typically been considered to happen at the end of the epoch. Though once you think carefully, it seems like that moment cannot actually be distinguished from the beginning of the next epoch, until you consider an era transition that has entirely different governance structure (such as Byron-to-Shelley or Babbage-to-Conway)!