Internal state of the ledger DB

The ledger DB looks like

anchor |> snapshots <| current

where anchor records the oldest known snapshot and current the most recent. The anchor is the oldest point we can roll back to.

We take a snapshot after each block is applied and keep in memory a window of the last k snapshots. We have verified empirically (#1936) that the overhead of keeping @k snapshots in memory is small, i.e., about 5% compared to keeping a snapshot every 100 blocks. This is thanks to sharing between consecutive snapshots.

As an example, suppose we have k = 6. The ledger DB grows as illustrated below, where we indicate the anchor number of blocks, the stored snapshots, and the current ledger.

anchor |> #   [ snapshots ]                   <| tip
---------------------------------------------------------------------------
G      |> (0) [ ]                             <| G
G      |> (1) [ L1]                           <| L1
G      |> (2) [ L1,  L2]                      <| L2
G      |> (3) [ L1,  L2,  L3]                 <| L3
G      |> (4) [ L1,  L2,  L3,  L4]            <| L4
G      |> (5) [ L1,  L2,  L3,  L4,  L5]       <| L5
G      |> (6) [ L1,  L2,  L3,  L4,  L5,  L6]  <| L6
L1     |> (6) [ L2,  L3,  L4,  L5,  L6,  L7]  <| L7
L2     |> (6) [ L3,  L4,  L5,  L6,  L7,  L8]  <| L8
L3     |> (6) [ L4,  L5,  L6,  L7,  L8,  L9]  <| L9   (*)
L4     |> (6) [ L5,  L6,  L7,  L8,  L9,  L10] <| L10
L5     |> (6) [*L6,  L7,  L8,  L9,  L10, L11] <| L11
L6     |> (6) [ L7,  L8,  L9,  L10, L11, L12] <| L12
L7     |> (6) [ L8,  L9,  L10, L12, L12, L13] <| L13
L8     |> (6) [ L9,  L10, L12, L12, L13, L14] <| L14

The ledger DB must guarantee that at all times we are able to roll back k blocks. For example, if we are on line (*), and roll back 6 blocks, we get

L3 |> []

Default parameters

Ledger DB starting at the specified ledger state

Summary of the chain at a particular point in time

The ledger state at the tip of the chain

Reference to the block at the tip of the chain

Information about the state of the ledger before

Get a past ledger state

\( O(\log n * \log n) \).

When no Checkpoint (or anchor) has the given WithOrigin r, Nothing is returned.

To avoid a linear search on the checkpoints (typically 2160 of them), we do a binary search benefitting from the cheap splits of the underlying StrictSeq \( O(\log n) \).

For a binary search, the checkpoints have to be ordered by r. In practice, we'll use RealPoint for r, which, because of the existence of EBBs, doesn't have a reliable ordering: it orders first on SlotNo, which is correct. But in case of a tie, it will look at the hash, which is not what we need: an EBB has the same slot as the block after it, so we'd want the RealPoint of an EBB to be less than the RealPoint of the regular block in the same slot. But the decision is made based on the hash, so we won't get a reliable answer.

Therefore, we take a projection refOrder :: r -> ro as an argument. The ro type should have a correct ordering, so that the list below is correctly ordered:

map (refOrder . cpBlock) $ Seq.toList (ledgerDbCheckpoints db)

When instantiating r to RealPoint, one should use realPointSlot as refOrder.

Note: we don't use fingertree for the checkpoints (with its search operation we could use here) because we'd have to impose more constraints on the r type. We could do an interpolation search if we assume more about the ro parameter (SlotNo), but that would be more complicated.

Apply the given function to all past ledgers in the LedgerDB, including the one stored at the anchor.

\( O(n) \)

Ap is used to pass information about blocks to ledger DB updates

The constructors serve two purposes:

• Specify the various parameters a. Are we passing the block by value or by reference? b. Are we applying or reapplying the block?
• Compute the constraint c on the monad m in order to run the query: a. If we are passing a block by reference, we must be able to resolve it. b. If we are applying rather than reapplying, we might have ledger errors.

Annotated ledger errors

Resolve a block

Resolving a block reference to the actual block lives in m because it might need to read the block from disk (and can therefore not be done inside an STM transaction).

NOTE: The ledger DB will only ask the ChainDB for blocks it knows must exist. If the ChainDB is unable to fulfill the request, data corruption must have happened and the ChainDB should trigger validation mode.

Monads in which we can resolve blocks

To guide type inference, we insist that we must be able to infer the type of the block we are resolving from the type of the monad.

Exceeded maximum rollback supported by the current ledger DB state

Under normal circumstances this will not arise. It can really only happen in the presence of data corruption (or when switching to a shorter fork, but that is disallowed by all currently known Ouroboros protocols).

Records both the supported and the requested rollback.

Switch to a fork

Total length of the chain (in terms of number of blocks)

References to blocks and corresponding ledger state (from old to new)

How many blocks can we currently roll back?

All snapshots currently stored by the ledger DB (new to old)

This also includes the snapshot at the anchor. For each snapshot we also return the distance from the tip.

Have we seen at least k blocks?

Internal: count number of checkpoints to prune, given total number of checkpoints

This is exposed for the benefit of tests only.

Get a past ledger state

\( O(n) \)

Straightforward implementation of ledgerDbPast using a linear search.

Can be used in tests to compare against ledgerDbPast.