IntersectMBO / IntersectMBO/ouroboros-consensus
Leios: the tx cache table fits 58 full EBs, but the node keeps 128
- 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
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