CAD-4199 Anti-diff prototype for `SeqUtxoDiff`.

[jorisdral]

NOTE: This PR description is under continuous construction.

Description

This PR resolves #3946. In summary, this PR:

• (1) Implements a prototype for an alternative way of keeping track of sequences of (UTxO) diffs, which uses abstract algebra (i.e., Group properties) as a means for optimisation.
• (2) Implements a benchmark suite that measures and compares the performance of the "legacy" and "new" implementations.

(1) Prototyping the anti-diff approach

See commit history.

(2) Comparing performance

Tentative benchmarking results warrant cautious positivity: The anti-diff approach shows a ~0.42x improvement over the legacy approach. Some variation in the improvement factor across runs of the benchmark suite could be explained by the fact that there is some randomness in the construction of the benchmarking scenario. Nonetheless, I have observed that the improvement factor is often in the range [0.40, 0.50].

Additional experimentation should show whether these results hold up when we change the configuration of the benchmarks. Examples of configuration options are the length of the command sequence, how many key-value pairs are deleted/inserted on a push, the probability distribution for rollback sizes, the security parameter k, and more. See GenConfig in the benchmarking code for more information about configuration options.

$ cabal run ouroboros-consensus-test:bench-storage
Up to date
All
  Ouroboros
    Consensus
      Storage
        LedgerDB
          HD
            DiffSeq/Diff operations
              Comparative performance analysis
                AntiDiff
                  Benchmark interpret:                                       OK (1.12s)
                    34.2 ms ± 1.9 ms, 0.43x
                  Sanity check:                                              OK (0.03s)
                    +++ OK, passed 1 test.
                LegacyDiff
                  Benchmark interpret:                                       OK (1.23s)
                    79.0 ms ± 2.0 ms
                  Sanity check:                                              OK (0.07s)
                    +++ OK, passed 1 test.
                interpret AntiDiff == interpret LegacyDiff:                  OK (0.11s)
                  +++ OK, passed 1 test.
              deterministic: interpret AntiDiff == interpret LegacyDiff:     OK (20.28s)
                +++ OK, passed 100 tests.
              non-deterministic: interpret AntiDiff == interpret LegacyDiff: OK (18.87s)
                +++ OK, passed 100 tests.

All 7 tests passed (41.92s)

Checklist

• Branch
  • [x] Commit sequence broadly makes sense
  • [x] Commits have useful messages
  • [x] New tests are added if needed and existing tests are updated
  • [x] If this branch changes Consensus and has any consequences for downstream repositories or end users, said changes must be documented in interface-CHANGELOG.md
  • [x] If this branch changes Network and has any consequences for downstream repositories or end users, said changes must be documented in interface-CHANGELOG.md
  • [x] If serialization changes, user-facing consequences (e.g. replay from genesis) are confirmed to be intentional.
• Pull Request
  • [x] Self-reviewed the diff
  • [x] Useful pull request description at least containing the following information:
    • What does this PR change?
    • Why these changes were needed?
    • How does this affect downstream repositories and/or end-users?
    • Which ticket does this PR close (if any)? If it does, is it linked?
  • [x] Reviewer requested