Menese DeFi Team evaluation, Part 1/2: bounding work and state under load

[KYounesMercatura]

Menese DeFi Team evaluation of MULTI/DEX, Part 1/2: bounding work and state under load

We evaluated the MULTI/DEX release as invited in the README, working from the published
tip (commit 0241cbafb779415e45dc56f0fabc1bbbb6ba9a5d) against a local replica. This is a
useful piece of infrastructure and genuinely nice work by whoever shipped it; we are glad
to help harden it. We did not find an existing issue for any of the items below. Below is the first of two
grouped write-ups; each finding is reproduced on an unmodified build with the exact steps
included. We grouped by theme rather than filing a separate issue for every item.

For context on scope: today was a quiet day, so only a couple of our team went through
the code. The rest of the team will review over the coming week, so we may follow up with
more as they do.

One heads-up before the findings, since it affects how to report anything sensitive:
the "report a vulnerability" link in SECURITY.md points to
github.com/dfinity/multidex/security/advisories/new, but this repository is
dfinity/public-multidex, so the link 404s. There is currently no working private
channel, which is why we are posting publicly. You may want to fix that link first.

Theme of this issue: several code paths do work, or hold state, that grows with load
without a hard ceiling. Your own comments record that this class already caused a
production incident once (the 2026-06-10 order-map memory event), so we expect it will
land.

---

1. A same-instant expiry cohort can wedge the maintenance heartbeat (highest impact)

Where: processDeferredExpiry (src/backend/main.mo:2759-2810) calls releaseDeferred
per expired entry with no per-message cap. Each release runs the full matcher, whose
inner findBestMatchExcluding (src/backend/lib/OrderBook.mo:439-467) re-scans the price
level on every iteration, giving an O(K squared) term.

Why it matters: entries staged after the last price update share an expiry instant (your
comment: "entries staged together expire together; one stalled price-refresh window
expires the whole queue at once"). When a large enough cohort expires into one finalise
tick, that single message exceeds the ~40B instruction limit and traps. The IC rolls the
message back, so the entries are still expired and the next tick repeats identically; the
wedge is self-perpetuating. The heartbeat keeps stamping (it is decoupled from the
finalise sub-message), so the canister looks alive while maintenance (releases, refunds,
liquidations, requotes, history shipping) silently stops, and the funds reserved behind
the stuck queue stay locked. A cycle top-up does not recover it; only a redeploy does.

Reproduction (local replica, instrumented copy for observability only, logic unchanged):

1. Add a per-tick instruction counter and a finaliseStarts/finaliseDone pair around
   processDeferredExpiry, exposed via a debug query (we measured with
   performanceCounter(0)).

2. Bootstrap a market, disable the AMM so the mark stays fixed, and stage a deep
   single-price book plus one crossing order that expires against it.

3. Cost per expiry tick, reinstall-per-K, isolated:

   K (crossing depth)	instructions / tick	completes?
   512	2.045 B	yes
   1024	6.235 B	yes
   2048	20.49 B	yes
   3072	(rolls back)	no, traps

   Fit: cost(K) ~ 2.17e6*K + 3825*K^2, back-predicting every point to under 3%. Solving
   cost(K) = 40e9 puts the trap at K ~ 2,970.

4. At K=3072 the sustained signature is clear: finaliseDone frozen for 30s while the
   heartbeat stamp advances, the crossing order and its reservation stuck, the resting
   asks rolled back, and the effective heartbeat cadence degrading from ~2s to ~15s
   (round-budget starvation).

One refinement on the trigger, since the condition is specific: the O(K squared) term is
in the number of DISTINCT resting orders at ONE price level (findBestMatchExcluding
scans a level's order map per fill), not in order size or total book depth. So the
condition is ~K distinct orders resting at a single price, swept in one message. A shallow
cohort spread across many levels does not trap (each level is cheap), and one large order
is K=1. Where it concentrates organically: a pegged or stablecoin pair (orders pile at the
~1.0 peg instead of churning) and round-number price magnets; it does not arise on a
volatile pair where the mark keeps moving. It is also directly constructible as a
deliberate denial of service (~K/32 funded principals stacking one price). Your
SHED_HARD_STAGED = 5000 already anticipates staged depths in this range.

Suggested direction: cap the matcher's iterations per call (return the unfilled remainder
through the existing remainingQty channel), and cap the batch with a
MAX_RELEASES_PER_PASS in processDeferred/processDeferredExpiry plus a re-arm when
entries remain. lib/Shard.mo already implements this bounded-slice pattern for the
leaderboard and tier sweeps; the same shape applies here.

---

2. A busy market's per-market trade list never trims within 24h

Where: src/backend/main.mo:154-161 (TRADES_PER_MARKET_CAP/TRIM_AT) and the trim at
main.mo:11390-11401.

Why it matters: the trim is gated on r.cursor > 0 and clamped to
min(excess, r.cursor), where cursor counts trades that have aged out of the 24h
window. A market doing more than the cap inside 24h never has anything age out, so
cursor stays 0 and the list never trims; it grows to the memory wall. The comment at
:155 ("memory stops growing without bound") reads as an invariant; the real bound is
max(cap, 24h of volume).

Reproduction: in a copy, lower TRADES_PER_MARKET_CAP/TRIM_AT to 3/5, drive more than
5 trades in one market inside 24h, and read the per-market list length; it reaches 18
with cursor = 0 throughout and never trims. The identical short-circuit holds at the
shipped 200k/250k; we lowered the constants only to make the test quick.

Suggested direction: trim by absolute cap independent of the cursor, keeping only trades
still inside the window plus a bounded tail.

---

3. Spawned archive canisters inherit the small default memory limit and never arm lowmemory()

Where: archives are spawned at main.mo:7134/7282/7374 with only controllers set;
apply_memory_settings (scripts/deploy.sh) targets backend only, and
ArchiveCanister.mo has no lowmemory() hook at all.

Why it matters: the archive holds the durable history and its three offset indexes live
on the heap, which grows with events. On a local spawn we read the child's settings
directly (backend is its controller): wasm_memory_limit = 3_221_225_472 (the 3 GiB
default) and wasm_memory_threshold = 0. So the early-warning hook you built into the
backend can never fire on an archive, and the child can quietly reach the wall and start
rejecting appends, which is the failure mode that backs up the shipper.

Reproduction: deploy, let an archive spawn, and read its canister_status from the
backend identity (or any controller); threshold 0, limit 3 GiB, no lowmemory.

Suggested direction: apply memory settings (limit and threshold) to each spawned archive
at creation, and add a lowmemory() hook to ArchiveCanister.mo.

---

4. The closed-order reaper re-walks all open orders every sweep

Where: reapClosedOrders (main.mo:6553-6595).

Why it matters: REAP_SWEEP_CAP bounds marks and deletes, but the scan iterates
orderStore.orders from the start every sweep and continues past open orders without
counting them toward the cap. Long-lived open orders with low ids sit at the front of the
id-ordered map and get re-walked on every 10s sweep, giving O(live open orders) forever.
Low-drama today, a steady cost as adoption grows.

Reproduction: add a per-sweep visited counter; with N resting open orders and no closed
ones, visited = N every sweep, constant across sweeps.

Suggested direction: shard the scan with lib/Shard.mo, as the tier and leaderboard
sweeps already do.

---

We are happy to open PRs for any of these; the fixes are small and mostly reuse patterns
already in the tree (Shard.mo, the remainingQty channel). A companion write-up
follows on value and integrity guarantees.

Housekeeping, while we were in here: mops test does not pass on the published tip:
tests/MatchingEngine.test.mo fails to compile (M0151, a ProtectionCtx record is
missing the beneficialOwner field added in lib/MatchingEngine.mo). The pre-push gate
(scripts/lint-ratchet.sh:58) globs src/backend only, so it never type-checks tests/
and reports green while the suite is red; the self-trade-prevention assertions in that
file have not run since the field was added. Widening the glob to include tests/ closes
the gap.

Filed by the Menese DeFi Team.

[dominicwilliams]

Confirmed and fixed — and then fixed again more thoroughly, because your framing turned out to describe a shape that appears in more places than the one you found.

#2.1 — processDeferredExpiry releases an uncapped same-instant cohort through an O(K²) matcher. Confirmed, including the observation that the codebase already shards for exactly this reason elsewhere, which is what made it an inconsistency rather than an oversight.

The first fix capped the cohort at 256 releases per pass. That fenced this path and nothing else — and your team's later report (#22) showed why that was insufficient: a single large taker reaches the same quadratic with no expiry queue involved at all. The complete fix is now in:

• the price-level index is keyed by (timestamp, id), so a level's time-priority head is its first entry and the per-fill re-scan disappears — O(K²) becomes O(K·log K);
• MAX_MATCH_ITERATIONS_PER_CALL = 256 bounds matcher work per message regardless of book shape, with the fill-or-kill pre-check budgeted to half that so a passed pre-check always completes;
• MAX_ORDERS_PER_PRICE_LEVEL = 512 bounds the attacker-chosen input at placement;
• the AMM sweep and the expiry pass each gained their own budget.

So your finding is closed twice over: once at the site you reported, once at the shape underneath it. Details are in the reply to #22.

One deduction. The report quotes an in-code comment about staged cohorts that does not appear verbatim anywhere in the tree. The mechanism the quote describes is real and the finding stands on its own; the quotation does not. In a report whose value rests on precise citation, that is worth flagging.

On the rest of the report: the remaining findings — the trade trim that never fires, the unconfigured archive memory, the reaper rescan, the dead test suite — were verified and swept into the same change set. Our published triage itemises only #2.1 by name, which under-serves the other four; they were fixed, they simply did not get individual write-ups. That is a gap in our record, not a comment on the findings.

The code is in #30, the first push to this mirror since the July snapshot; your line numbers against 0241cba still resolve. The SECURITY.md advisory link that 404'd — the reason this report is public — is fixed in the same drop.