IntersectMBO / IntersectMBO/ouroboros-consensus

Leios: the tx cache table fits 58 full EBs, but the node keeps 128

Open
#2,290 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
67
Forks
43
Avg merge
5d 13h
Merged PRs (30d)
43

Description

The tx cache table holds [4194304 entries](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus-diffusion/src/ouroboros-consensus-diffusion/Ouroboros/Consensus/Node.hs#L546). The node keeps the [128 most recent EBs](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/API.hs#L125-L128), and [each reference of each kept EB takes one entry](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/Optimized.hs#L100-L105). 128 EBs at [`maxTxsPerEb` = 71428](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosDemoTypes.hs#L2136-L2146) references need 9142784 entries, so the table fits 58 full EBs, not 128.

Each EB is individually legal: the codec [caps a `MsgLeiosBlock` at 2500000 bytes](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosDemoOnlyTestFetch.hs#L204) and `maxTxsPerEb` is the most references that fits. So no per-message check helps, and the [per-peer fetch buffers](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosDemoLogic.hs#L239-L240) sized at `maxTxsPerEb` are fine. Only the aggregate is unbounded.

## Filling the table costs no transactions

[`insertBody` bumps a refcount for every hash in an EB body](https://github.com/IntersectMBO/ouroboros-consensus/blob/b56977baae0740f563060a8a9171c78be865b357/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/Optimized.hs#L91-L114). It does not check that the hash names a real transaction, and the only content check on a received body is the intra-body duplicate test. So 59 endorser blocks carrying 71428 random 32-byte hashes each fill the table. The attacker never serves a closure.

Announcements gate this. Each one needs a header that passes the election proof and the KES check, so the slots have to be won. 59 fits inside `maxAnnouncementCount` = 128 with room to spare. I did not work out the stake needed to win 59 slots in one window.

## Eviction never looks at the table

There are [two eviction entrypoints](https://github.com/IntersectMBO/ouroboros-consensus/blob/b56977baae0740f563060a8a9171c78be865b357/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/Optimized.hs#L76-L90), and neither is driven by occupancy:

- `insertAnnouncement` evicts while `hsCount > maxAnnouncementCount`.
- `evictOlderThan` evicts while the oldest announcement is older than the GC boundary.

So a resident window of 128 large announcements sits at 9142784 entries against 4194304 slots and nothing fires. There is no back-pressure.

## Overflow leaks slots permanently

[`error "table full"`](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/Optimized/MutableHashTable.hs#L235) fires only at 100% occupancy, and the table never grows. Linear probing degrades first. Unsuccessful search costs about `1/2(1 + 1/(1-a)^2)` probes: 2.5 at load 0.5, 8.5 at 0.75, 50.5 at 0.9. `bumpTx` does a lookup and an insert per reference, so the node is slow well before the error.

When the error fires, the slots already taken are not recoverable. `insertBody` folds `bumpTx` inside `MVar.modifyMVar`, and `bumpTx` writes into the mutable table. If the insert raises at reference k, references 1 to k-1 stay in the table, and `modifyMVar` restores the old state, so the body stays `BodyNotYetInserted`. [Eviction then skips those entries](https://github.com/IntersectMBO/ouroboros-consensus/blob/b56977baae0740f563060a8a9171c78be865b357/ouroboros-consensus/src/ouroboros-consensus/LeiosTxCache/Optimized.hs#L236-L241):

```haskell
evTxs <- case bs of
BodyNotYetInserted _ -> pure Set.empty -- no decref
BodyAlreadyInserted _ b -> decBodyTxs ht b
```

They are orphaned for the life of the process. Each overflow takes slots that never come back.

The node does not crash. `ErrorCall` matches no clause of [`consensusRethrowPolicy`](https://github.com/IntersectMBO/ouroboros-consensus/blob/b56977baae0740f563060a8a9171c78be865b357/ouroboros-consensus-diffusion/src/ouroboros-consensus-diffusion/Ouroboros/Consensus/Node/RethrowPolicy.hs#L53), and an unmatched type yields `ShutdownPeer`, so the connection manager drops that peer and allows a reconnect after 10 to 20 seconds. The peer retries the same body, bumps the surviving entries again, and fails again.

## What a fix needs

More slots alone does not work. Sizing against a load factor concedes the worst case. That is sound for honest traffic and wrong here, because the fill is cheap to drive on purpose. A larger table raises the cost linearly and changes nothing structural.

That leaves a smaller `maxAnnouncementCount`, a residency bound that does not follow `maxTxsPerEb`, or making a failed `insertBody` reclaim what it wrote. The last one is worth doing whatever the sizing decision turns out to be.

Predates #2280, which corrects `maxTxsPerEb` from 13888 to 71428. The old value understated the codec limit by 5x, and the [table's "never fills" claim](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus-diffusion/src/ouroboros-consensus-diffusion/Ouroboros/Consensus/Node.hs#L540-L545) rested on it. The codec limit itself did not change, so a node on the old constant already accepted a 71428-reference EB into the cache.

Nothing in the tree reaches the ceiling: `leios-txcache-bench` hardcodes [`txsPerEb = 15_058`](https://github.com/IntersectMBO/ouroboros-consensus/blob/6423a842504c2b4148d76313bb8708b633ef7907/ouroboros-consensus/bench/leios-txcache-bench/Main.hs#L61) and fills 1.93M entries, a load factor of 0.46.

Contributor guide

Open the contributing guide

Research direction

Start with insertBody, bumpTx, the eviction entrypoints, and MutableHashTable.hs around the cited lines; compare their behavior with the leios-txcache-bench setup. Trace a failed body insertion and the BodyNotYetInserted eviction case. Done should include a bounded cache policy or reliable cleanup after failure, with regression coverage showing that failed inserts do not permanently orphan slots.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
blockchain, distributed-systems
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.