InvalidRollForward exception should be unreachable

[nfrisby]

While reviewing PR IntersectMBO/ouroboros-network#773 for Issue IntersectMBO/ouroboros-network#231, @nc6 observed and I agreed that a ForkTooDeep exception should be raised prior to the mini protocol reaching a state where InvalidRollForward could be raised. PR IntersectMBO/ouroboros-network#773 introduces InvalidRollForward, because otherwise the RealPBFT tests fail. We're merging with this Issue as a follow-up obligation.

[nfrisby]

On commit 73b5ce40 from PR 773 plus some extra debugging/tracing messages, I see the following scenario play out, given this RealPBFt test case:

TestConfig
            { numCoreNodes = NumCoreNodes 3
            , numSlots = NumSlots 24
            , nodeJoinPlan = NodeJoinPlan $ Map.fromList
              [ (CoreNodeId 0,SlotNo 0)
              , (CoreNodeId 1,SlotNo 20)
              , (CoreNodeId 2,SlotNo 22)
              ]}

From the perspective of the c0 ChainSync client communicating with the c2 ChainSync server:

Send MsgFindIntersect
  [ Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 22}, blockPointHash = AbstractHash f50d2a28})}
  , Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 21}, blockPointHash = AbstractHash 0fa7f4b0})}
  , Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 18}, blockPointHash = AbstractHash 702888ee})}
  , Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 15}, blockPointHash = AbstractHash 772b862c})}
  , Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 9}, blockPointHash = AbstractHash 48fa98c1})}
  , Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 0}, blockPointHash = AbstractHash 3c2a8234})}
  ]
Recv MsgIntersectNotFound Point {getPoint = Origin}
Send MsgRequestNext
-- the dual mini protocol now sends MsgIntersectFound Origin, indirectly prompting:
Recv MsgRollBackward Point {getPoint = Origin} Point {getPoint = Origin}
Send MsgRequestNext
Recv MsgAwaitReply
-- the dual mini protocol now sends MsgRollForward Point 0 3c2a8234 (the Epoch 0 EBB), indirectly prompting:
Recv MsgRollForward Left (ABoundaryHeader ...) Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 0}, blockPointHash = AbstractHash 3c2a8234})}
throw InvalidRollForward
    {- requested point -} (Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 0}, blockPointHash = AbstractHash 3c2a8234})})
    {- their head      -} (Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 0}, blockPointHash = AbstractHash 3c2a8234})})
    {- our ledger tip  -} (Point {getPoint = At (Block {blockPointSlot = SlotNo {unSlotNo = 22}, blockPointHash = AbstractHash f50d2a28})})

Note that the inclusion of 3c2a8234 in the MsgFindIntersect demonstrates that that block is within k of our current tip (ie f50d2a28).

At this point, I'm suspecting that anachronisticProtocolLedgerView @(ByronBlockOrEBB cfg) should not be returning Left TooFarBehind here (which is the throw InvalidRollForward case alternative) -- is the chain not as dense as that function expects? For example, on the current tip of master, this lower bound seems to assume something around a 50% density threshold? https://github.com/input-output-hk/ouroboros-network/blob/6c937ec0d65d5df5f44ce9f496ebcfcd07762f56/ouroboros-consensus/src/Ouroboros/Consensus/Ledger/Byron.hs#L974-L978

[nc6]

There is an issue with low-density chains, potentially. As you say, anything below a 50% density threshold will not give a ledger view, even if it's within k blocks.

The solution to this might be to track the lower bound in the ledger state, but this would entail keeping the slot numbers for the last k blocks around, which is potentially expensive. How much do we care about chains below 50% density, given that this is our threshold for a "healthy" chain?

[edsko]

As part of the work on IntersectMBO/ouroboros-network#1942, we now maintain an explicit intersection point between the two chains (our own and the candidate one), and moreover verify that this intersection point is indeed the intersection between the two fragments. Since we in addition also know that our fragment is always at most k long, this guarantees the intersection must indeed be within k blocks. If we nonetheless get a TooFarBehind (in the new setup, corresponding to ledgerViewForecastAt returning Nothing), it can only mean that the chain density is so poor that those k blocks span more than 2k slots. We still disconnected, as before, but this should not happen under normal circumstances. I have changed the docstring for InvalidRollForward to

      -- | We were unable to get a ledger view for the intersection point
      -- between the candidate's chain and our chain.
      --
      -- This can only happen in the case of very low density chains, where
      -- the @k@ blocks on our chain span more than @2k@ slots. Note that
      -- producing a block on top of a chain while the distance from the tip
      -- of that chain to the current slot (in terms of wallblock) is very
      -- large will also result in such a low density chain.

This does arise in the current consensus tests for Byron, which (very) occasionally result in such low density chains.

Semi-related: #668.

So this ticket would only be an improvement to the testing infrastructure.