Book head-clog of expired orders can force hybrid takers into the scan-step cap

Brouie commented

2026-06-03 07:19:55 +00:00

(Migrated from gitlab.com)

Severity: Low
Reachability: Attacker places many short-expiry orders at the book head; cost is escrow + gas, reclaimable after expiry.
Affected: matcher scan cap interaction (smartcontracts/contracts/pair/src/orderbook.rs, MAX_SCAN_STEPS / MAX_EXPIRED_PARKS_PER_SWAP in dex-common/src/pair.rs).

Summary

(Re-examined after an earlier pass leaned toward refuting this — I think there's a real, if minor, griefing vector.)

The matcher walks at most MAX_SCAN_STEPS = 500 nodes per swap, and parks at most MAX_EXPIRED_PARKS_PER_SWAP = 15 expired orders per swap; beyond 15 it just skips-and-advances (still burning a scan step). So if an attacker clogs the head with more than ~500 expired (or otherwise skipped) orders, a hybrid taker hits the 500-step cap before reaching real liquidity, while only 15 of the clog get cleared per swap. The book leg then under-fills — the taker degrades to pool-only or reverts on slippage — and it takes many swaps (≈ clog size / 15) to grind the clog down.

No funds are stolen (the taker falls back or reverts), and the auto-park (#264) plus permissionless clean do eventually clear it — but the clear is slow, and clean_limit_book has its own traversal issue (see the clean unbounded-scan report), so "just clean it" isn't free either. Net: a capital+gas griefing vector that degrades hybrid fills for a while. Filing it Low.

Current codebase

dex-common/src/pair.rs: MAX_SCAN_STEPS = 500, MAX_EXPIRED_PARKS_PER_SWAP = 15.
orderbook.rs matcher: book_walk_step breaks at MAX_SCAN_STEPS; expired orders past the 15-park cap are skipped (expired_parks_skipped) but still advance and consume a step.

Recommended direction

Raise the per-swap park budget, or let the matcher skip past a contiguous expired run more cheaply (e.g. unlink-in-bulk) so a clog can't sit in front of live liquidity.
Once book_start_hint is side-validated (the cross-escrow report), a legit taker can use it to start past a clogged head — but that depends on that fix landing first.
Consider a small min-rest-time or anti-spam cost on order placement to make head-clogging less cheap.

Acceptance criteria

A head clog of expired orders larger than the scan cap can't keep hybrid takers from reaching live liquidity across a small number of swaps.
Clearing a clog doesn't depend on an unbounded clean traversal.

Test plan (attack / abuse)

case	expect
>500 expired orders at head, then hybrid taker	taker still reaches live liquidity within a bounded number of swaps
repeated swaps grind the clog	clog cleared without unbounded gas

**Severity:** Low **Reachability:** Attacker places many short-expiry orders at the book head; cost is escrow + gas, reclaimable after expiry. **Affected:** matcher scan cap interaction (`smartcontracts/contracts/pair/src/orderbook.rs`, `MAX_SCAN_STEPS` / `MAX_EXPIRED_PARKS_PER_SWAP` in `dex-common/src/pair.rs`). ## Summary (Re-examined after an earlier pass leaned toward refuting this — I think there's a real, if minor, griefing vector.) The matcher walks at most `MAX_SCAN_STEPS = 500` nodes per swap, and parks at most `MAX_EXPIRED_PARKS_PER_SWAP = 15` expired orders per swap; beyond 15 it just skips-and-advances (still burning a scan step). So if an attacker clogs the head with more than ~500 expired (or otherwise skipped) orders, a hybrid taker hits the 500-step cap before reaching real liquidity, while only 15 of the clog get cleared per swap. The book leg then under-fills — the taker degrades to pool-only or reverts on slippage — and it takes many swaps (≈ clog size / 15) to grind the clog down. No funds are stolen (the taker falls back or reverts), and the auto-park (#264) plus permissionless clean do eventually clear it — but the clear is slow, and `clean_limit_book` has its own traversal issue (see the clean unbounded-scan report), so "just clean it" isn't free either. Net: a capital+gas griefing vector that degrades hybrid fills for a while. Filing it Low. ## Current codebase - `dex-common/src/pair.rs`: `MAX_SCAN_STEPS = 500`, `MAX_EXPIRED_PARKS_PER_SWAP = 15`. - `orderbook.rs` matcher: `book_walk_step` breaks at `MAX_SCAN_STEPS`; expired orders past the 15-park cap are skipped (`expired_parks_skipped`) but still advance and consume a step. ## Recommended direction 1. Raise the per-swap park budget, or let the matcher skip past a contiguous expired run more cheaply (e.g. unlink-in-bulk) so a clog can't sit in front of live liquidity. 2. Once `book_start_hint` is side-validated (the cross-escrow report), a legit taker can use it to start past a clogged head — but that depends on that fix landing first. 3. Consider a small min-rest-time or anti-spam cost on order placement to make head-clogging less cheap. ## Acceptance criteria - [ ] A head clog of expired orders larger than the scan cap can't keep hybrid takers from reaching live liquidity across a small number of swaps. - [ ] Clearing a clog doesn't depend on an unbounded clean traversal. ## Test plan (attack / abuse) | case | expect | |---|---| | >500 expired orders at head, then hybrid taker | taker still reaches live liquidity within a bounded number of swaps | | repeated swaps grind the clog | clog cleared without unbounded gas |

PlasticDigits commented

2026-06-03 11:04:07 +00:00

(Migrated from gitlab.com)

1 & 2 approved for now. Document that if this attack does occur in the future, we may need to add a small LUNC fee per order (say 10 LUNC) that is transferred to treasury. But at this time not likely to be needed.

Brouie commented

2026-06-04 06:30:07 +00:00

(Migrated from gitlab.com)

Implementation plan (your approved dirs 1+2). Medium, contract-only. Gated on #274.

Dir 1: make the matcher clear a contiguous expired head-run cheaply — bulk-unlink a contiguous expired prefix in one splice instead of 15 individual unlinks, and/or raise MAX_EXPIRED_PARKS_PER_SWAP. Apply symmetrically to BOTH match_bids and match_asks (structurally identical), and keep execute/simulate scan_steps_capped parity. Files: orderbook.rs (expired branch, both legs), dex-common/pair.rs (budget const + gas-envelope justification like #254).
Dir 2: needs NO new code — book_start_hint is already side-validated (#272/dd70ea3), so a legit taker can already start past a clogged head; it's just a matter of the frontend/indexer supplying a live-side hint.
Dir 3 (per-order ~10 LUNC anti-spam fee to treasury): document as future-only, not implemented, per your note.

Precedent: book_walk_step scan-cap + match_bids_scan_steps_cap_bounds_expired_prefix_walk (orderbook.rs:3557) + simulate parity (3602); unlink_order/detach_limit_order_from_book splice for the bulk-unlink; the place_expired_bids harness (limit_order_tests.rs:1742). Gated on #274 — full closure ("clearing a clog doesn't depend on an unbounded clean traversal") needs #274's bounded clean to land first. Tests: >MAX_SCAN_STEPS expired head + one live order past it → single swap reaches+fills the live order. @PlasticDigits

Implementation plan (your approved dirs 1+2). Medium, contract-only. Gated on #274. - Dir 1: make the matcher clear a contiguous expired head-run cheaply — bulk-unlink a contiguous expired prefix in one splice instead of 15 individual unlinks, and/or raise `MAX_EXPIRED_PARKS_PER_SWAP`. Apply symmetrically to BOTH `match_bids` and `match_asks` (structurally identical), and keep execute/simulate `scan_steps_capped` parity. Files: orderbook.rs (expired branch, both legs), dex-common/pair.rs (budget const + gas-envelope justification like #254). - Dir 2: needs NO new code — `book_start_hint` is already side-validated (#272/dd70ea3), so a legit taker can already start past a clogged head; it's just a matter of the frontend/indexer supplying a live-side hint. - Dir 3 (per-order ~10 LUNC anti-spam fee to treasury): document as future-only, not implemented, per your note. Precedent: `book_walk_step` scan-cap + `match_bids_scan_steps_cap_bounds_expired_prefix_walk` (orderbook.rs:3557) + simulate parity (3602); `unlink_order`/`detach_limit_order_from_book` splice for the bulk-unlink; the `place_expired_bids` harness (limit_order_tests.rs:1742). **Gated on #274** — full closure ("clearing a clog doesn't depend on an unbounded clean traversal") needs #274's bounded clean to land first. Tests: >MAX_SCAN_STEPS expired head + one live order past it → single swap reaches+fills the live order. @PlasticDigits

Brouie commented

2026-06-05 02:19:53 +00:00

(Migrated from gitlab.com)

Picking this back up now that #274 landed (it was the gate). Where #289 actually stands after reading the matcher park path closely:

Dir 2 (no code) is the real mitigation and it's already in place. A hybrid taker skips a head clog by passing a live-side book_start_hint — the matcher seeds its walk from resolve_match_start_hint (orderbook.rs:1376/1545/1701), which since #272/dd70ea3 only accepts a SAME-side hint. So a taker can start past the expired clog: no parks, no scan-step exhaustion. As long as the frontend/indexer hands a live-side hint, the taker isn't stuck behind the clog.

#274 (MR !753) now covers the keeper path. A keeper clears an arbitrarily long expired clog in bounded, resumable chunks (max_steps + resume_cursor), without the old unbounded-traversal risk.

Dir 1 (matcher change) — honest assessment. The per-expired-order cost is dominated by the EXPIRED_LIMIT_CLAIMS.save (the maker's refund row) + event, NOT the DLL pointer rewrites. So "bulk-unlink the contiguous expired prefix in one splice" only saves the pointer cost, which isn't the expensive part — it wouldn't let MAX_EXPIRED_PARKS_PER_SWAP go meaningfully higher. And raising that cap (15 -> N) is a gas-envelope tradeoff I don't want to size by guessing; it needs a live gas benchmark like #254/#262, on a redeploy.

So between dir-2 (taker skips the clog) and #274 (keeper clears it, bounded), the clog is mitigated from both sides without touching the hot matcher path. My recommendation: treat #289 as covered by dir-2 + #274; if you still want a cap raise, I'll size it against a fresh gas benchmark on the next redeploy rather than guess. Dir-3 (per-order ~10 LUNC fee) stays future-only per your note. @PlasticDigits

Picking this back up now that #274 landed (it was the gate). Where #289 actually stands after reading the matcher park path closely: **Dir 2 (no code) is the real mitigation and it's already in place.** A hybrid taker skips a head clog by passing a live-side `book_start_hint` — the matcher seeds its walk from `resolve_match_start_hint` (orderbook.rs:1376/1545/1701), which since #272/dd70ea3 only accepts a SAME-side hint. So a taker can start past the expired clog: no parks, no scan-step exhaustion. As long as the frontend/indexer hands a live-side hint, the taker isn't stuck behind the clog. **#274 (MR !753) now covers the keeper path.** A keeper clears an arbitrarily long expired clog in bounded, resumable chunks (`max_steps` + `resume_cursor`), without the old unbounded-traversal risk. **Dir 1 (matcher change) — honest assessment.** The per-expired-order cost is dominated by the `EXPIRED_LIMIT_CLAIMS.save` (the maker's refund row) + event, NOT the DLL pointer rewrites. So "bulk-unlink the contiguous expired prefix in one splice" only saves the pointer cost, which isn't the expensive part — it wouldn't let `MAX_EXPIRED_PARKS_PER_SWAP` go meaningfully higher. And raising that cap (15 -> N) is a gas-envelope tradeoff I don't want to size by guessing; it needs a live gas benchmark like #254/#262, on a redeploy. So between dir-2 (taker skips the clog) and #274 (keeper clears it, bounded), the clog is mitigated from both sides without touching the hot matcher path. My recommendation: treat #289 as covered by dir-2 + #274; if you still want a cap raise, I'll size it against a fresh gas benchmark on the next redeploy rather than guess. Dir-3 (per-order ~10 LUNC fee) stays future-only per your note. @PlasticDigits

PlasticDigits commented

2026-06-05 04:08:27 +00:00

(Migrated from gitlab.com)

mentioned in issue #309

PlasticDigits commented

2026-06-05 04:08:27 +00:00

(Migrated from gitlab.com)

marked as related to #309

PlasticDigits commented

2026-06-05 09:46:33 +00:00

(Migrated from gitlab.com)

Yes should check for cap raise on redeploy

PlasticDigits commented

2026-06-05 10:38:37 +00:00

(Migrated from gitlab.com)

mentioned in merge request !794

ghost1 commented

2026-06-05 11:02:54 +00:00

(Migrated from gitlab.com)

mentioned in commit 4c4c26846b

mentioned in commit 4c4c26846bff977763c2d66c787473c6627bbfc5

PlasticDigits commented

2026-06-05 11:03:24 +00:00

(Migrated from gitlab.com)

Verification summary (#289)

Threat model: CONFIRMED (low). MAX_SCAN_STEPS (500) + MAX_EXPIRED_PARKS_PER_SWAP (15) allow a capital+gas griefing vector: a deep expired head prefix can exhaust the scan budget before live liquidity on a head-only hybrid swap (scan_steps_capped=true; book leg under-fills; pool spillover or slippage revert). No fund theft.

Accepted mitigations (per issue discussion + PlasticDigits approval): no matcher change in this pass; document operational defenses.

Acceptance criteria

Item	Result	Evidence
Head clog > scan cap cannot block takers reaching live liquidity in a small number of swaps	PASS (operational)	L17 / #272: same-side `book_start_hint` seeds walk past expired prefix — `hybrid_same_side_book_start_hint_still_matches`. Without hint: `hybrid_walk_scan_steps_cap_bounds_expired_prefix_and_spills_to_pool` (degraded book, pool spillover). Small clog: `hybrid_walk_three_expired_bids_all_parked_then_fills_live_bid`.
Clearing clog does not use unbounded clean traversal	PASS	#274: `MAX_CLEAN_SCAN_STEPS` (500) + `resume_cursor` — `clean_limit_book_scan_cap_resume_reaches_tail`; `dex-common/limit_clean.rs`.

Test plan (issue table)

Case	Result	Command
>500 expired at head, hybrid taker	PASS with same-side hint; degraded head-only	`cargo test -p cl8y-dex-tests hybrid_walk_scan_steps_cap`; `cargo test -p cl8y-dex-tests hybrid_same_side_book_start_hint`; `cargo test -p cl8y-dex-pair match_bids_scan_steps_cap`
Repeated swaps grind clog	PASS (bounded: ≤15 parks/swap + resumable clean)	`cargo test -p cl8y-dex-tests expired_parks_benchmark`; `cargo test -p cl8y-dex-tests clean_limit_book_scan_cap`

Repo changes (docs/guardrails)

MR documents mitigations in docs/limit-orders.md, docs/contracts-security-audit.md (L5/L15/L17), skills/AGENTS_BOOK_MATCH_HINT_SECURITY.md, skills/AGENTS_TERRACLASSIC_GAS.md.

Follow-ups (not blocking)

Indexer route optimizer still emits book_start_hint: null (hybrid_route_opt.rs) — product hardening to pass first live-side id.
Re-benchmark MAX_EXPIRED_PARKS_PER_SWAP on next pair wasm redeploy (PlasticDigits note).
Future-only: ~10 LUNC per-order placement fee to treasury if spam materializes.

## Verification summary ([#289](https://gitlab.com/PlasticDigits/cl8y-dex-terraclassic/-/work_items/289)) **Threat model:** CONFIRMED (low). `MAX_SCAN_STEPS` (500) + `MAX_EXPIRED_PARKS_PER_SWAP` (15) allow a capital+gas griefing vector: a deep expired head prefix can exhaust the scan budget before live liquidity on a **head-only** hybrid swap (`scan_steps_capped=true`; book leg under-fills; pool spillover or slippage revert). No fund theft. **Accepted mitigations (per issue discussion + PlasticDigits approval):** no matcher change in this pass; document operational defenses. ### Acceptance criteria | Item | Result | Evidence | |------|--------|----------| | Head clog > scan cap cannot block takers reaching live liquidity in a **small** number of swaps | **PASS** (operational) | **L17 / #272:** same-side `book_start_hint` seeds walk past expired prefix — `hybrid_same_side_book_start_hint_still_matches`. **Without hint:** `hybrid_walk_scan_steps_cap_bounds_expired_prefix_and_spills_to_pool` (degraded book, pool spillover). **Small clog:** `hybrid_walk_three_expired_bids_all_parked_then_fills_live_bid`. | | Clearing clog does not use unbounded clean traversal | **PASS** | **#274:** `MAX_CLEAN_SCAN_STEPS` (500) + `resume_cursor` — `clean_limit_book_scan_cap_resume_reaches_tail`; `dex-common/limit_clean.rs`. | ### Test plan (issue table) | Case | Result | Command | |------|--------|---------| | >500 expired at head, hybrid taker | **PASS** with same-side hint; **degraded** head-only | `cargo test -p cl8y-dex-tests hybrid_walk_scan_steps_cap`; `cargo test -p cl8y-dex-tests hybrid_same_side_book_start_hint`; `cargo test -p cl8y-dex-pair match_bids_scan_steps_cap` | | Repeated swaps grind clog | **PASS** (bounded: ≤15 parks/swap + resumable clean) | `cargo test -p cl8y-dex-tests expired_parks_benchmark`; `cargo test -p cl8y-dex-tests clean_limit_book_scan_cap` | ### Repo changes (docs/guardrails) MR documents mitigations in `docs/limit-orders.md`, `docs/contracts-security-audit.md` (L5/L15/L17), `skills/AGENTS_BOOK_MATCH_HINT_SECURITY.md`, `skills/AGENTS_TERRACLASSIC_GAS.md`. ### Follow-ups (not blocking) - Indexer route optimizer still emits `book_start_hint: null` (`hybrid_route_opt.rs`) — product hardening to pass first live-side id. - Re-benchmark `MAX_EXPIRED_PARKS_PER_SWAP` on next pair wasm redeploy (PlasticDigits note). - Future-only: ~10 LUNC per-order placement fee to treasury if spam materializes.

PlasticDigits commented

2026-06-05 11:03:25 +00:00

(Migrated from gitlab.com)

mentioned in merge request !795

PlasticDigits commented

2026-06-05 11:04:15 +00:00

(Migrated from gitlab.com)

mentioned in commit c179fa92fb

mentioned in commit c179fa92fb7b003c69f1b9567eb094bf45e11373

PlasticDigits commented

2026-06-05 13:43:26 +00:00

(Migrated from gitlab.com)

Verification summary (#289)

Agent: verify automation (2026-06-05)
Branch verified: main @ 9d7331c

Threat model: CONFIRMED (low severity). A deep expired head prefix (> MAX_SCAN_STEPS = 500) can exhaust the hybrid book walk on a head-only swap (book_start_hint: null), setting scan_steps_capped=true and under-filling the book leg (pool spillover or slippage revert). No fund theft.

Accepted mitigations (per issue discussion): no matcher change in this pass; operational defenses documented.

Acceptance criteria

Item	Result	Evidence
Head clog > scan cap cannot block takers reaching live liquidity in a small number of swaps	PASS (operational)	Same-side `book_start_hint` seeds walk past expired prefix — `hybrid_same_side_book_start_hint_still_matches`. Without hint: degraded but bounded — `hybrid_walk_scan_steps_cap_bounds_expired_prefix_and_spills_to_pool`. Small clog (≤15): `hybrid_walk_three_expired_bids_all_parked_then_fills_live_bid`.
Clearing clog does not use unbounded clean traversal	PASS	`#274`: `MAX_CLEAN_SCAN_STEPS` (500) + `resume_cursor` — `clean_limit_book_scan_cap_resume_reaches_tail`; `dex-common/limit_clean.rs`.

Test plan (issue table)

Case	Result	Command / output
>500 expired at head, hybrid taker	PASS with same-side hint; degraded head-only	`cargo test -p cl8y-dex-tests scan_steps_cap` → 1 passed; `cargo test -p cl8y-dex-tests hybrid_same_side_book_start_hint` → 1 passed; `cargo test -p cl8y-dex-pair scan_steps_cap` → 2 passed
Repeated swaps grind clog	PASS (bounded: ≤15 parks/swap + resumable clean)	`cargo test -p cl8y-dex-tests expired_parks` → 1 passed; `cargo test -p cl8y-dex-tests clean_limit_book_scan_cap` → 1 passed

Docs / guardrails (no repo changes this run)

Mitigations already documented in docs/limit-orders.md § Expiry (head-clog griefing), docs/contracts-security-audit.md (L5/L15/L17), skills/AGENTS_BOOK_MATCH_HINT_SECURITY.md, skills/AGENTS_TERRACLASSIC_GAS.md.

Follow-ups (not blocking closure)

Indexer route optimizer still emits book_start_hint: null (hybrid_route_opt.rs) — product hardening to pass first live-side id.
Re-benchmark MAX_EXPIRED_PARKS_PER_SWAP on next pair wasm redeploy (PlasticDigits note).
Future-only: ~10 LUNC per-order placement fee to treasury if spam materializes.

Closing: all acceptance criteria met via accepted operational mitigations + bounded clean path; no code/docs changes required in this verification pass.

## Verification summary ([#289](https://gitlab.com/PlasticDigits/cl8y-dex-terraclassic/-/work_items/289)) **Agent:** `verify` automation (2026-06-05) **Branch verified:** `main` @ `9d7331c` **Threat model:** CONFIRMED (low severity). A deep expired head prefix (> `MAX_SCAN_STEPS` = 500) can exhaust the hybrid book walk on a **head-only** swap (`book_start_hint: null`), setting `scan_steps_capped=true` and under-filling the book leg (pool spillover or slippage revert). No fund theft. **Accepted mitigations (per issue discussion):** no matcher change in this pass; operational defenses documented. ### Acceptance criteria | Item | Result | Evidence | |------|--------|----------| | Head clog > scan cap cannot block takers reaching live liquidity in a **small** number of swaps | **PASS** (operational) | Same-side `book_start_hint` seeds walk past expired prefix — `hybrid_same_side_book_start_hint_still_matches`. Without hint: degraded but bounded — `hybrid_walk_scan_steps_cap_bounds_expired_prefix_and_spills_to_pool`. Small clog (≤15): `hybrid_walk_three_expired_bids_all_parked_then_fills_live_bid`. | | Clearing clog does not use unbounded clean traversal | **PASS** | `#274`: `MAX_CLEAN_SCAN_STEPS` (500) + `resume_cursor` — `clean_limit_book_scan_cap_resume_reaches_tail`; `dex-common/limit_clean.rs`. | ### Test plan (issue table) | Case | Result | Command / output | |------|--------|------------------| | >500 expired at head, hybrid taker | **PASS** with same-side hint; **degraded** head-only | `cargo test -p cl8y-dex-tests scan_steps_cap` → 1 passed; `cargo test -p cl8y-dex-tests hybrid_same_side_book_start_hint` → 1 passed; `cargo test -p cl8y-dex-pair scan_steps_cap` → 2 passed | | Repeated swaps grind clog | **PASS** (bounded: ≤15 parks/swap + resumable clean) | `cargo test -p cl8y-dex-tests expired_parks` → 1 passed; `cargo test -p cl8y-dex-tests clean_limit_book_scan_cap` → 1 passed | ### Docs / guardrails (no repo changes this run) Mitigations already documented in `docs/limit-orders.md` § Expiry (head-clog griefing), `docs/contracts-security-audit.md` (L5/L15/L17), `skills/AGENTS_BOOK_MATCH_HINT_SECURITY.md`, `skills/AGENTS_TERRACLASSIC_GAS.md`. ### Follow-ups (not blocking closure) - Indexer route optimizer still emits `book_start_hint: null` (`hybrid_route_opt.rs`) — product hardening to pass first live-side id. - Re-benchmark `MAX_EXPIRED_PARKS_PER_SWAP` on next pair wasm redeploy (PlasticDigits note). - Future-only: ~10 LUNC per-order placement fee to treasury if spam materializes. **Closing:** all acceptance criteria met via accepted operational mitigations + bounded clean path; no code/docs changes required in this verification pass.

PlasticDigits (Migrated from gitlab.com) closed this issue

2026-06-05 13:43:30 +00:00

PlasticDigits commented

2026-06-05 13:44:36 +00:00

(Migrated from gitlab.com)

mentioned in issue #332