Contract: deterministic O(1) batch/ladder insertion (book-order sequence + position threading + ladder anchor hint)

PlasticDigits commented

2026-06-01 04:18:53 +00:00

(Migrated from gitlab.com)

Summary

Make on-chain batch/ladder limit-order insertion deterministically cheap on deep books by (1) inserting rungs in book-sort order instead of input order, (2) threading the resolved insert position from one rung to the next so interior rungs avoid redundant verify loads, and (3) accepting a single optional anchor hint on LimitOrderLadderSpec so the first/boundary rung does not pay a full head walk.

These three changes are bundled because they all live in the pair contract's batch placement path and share the same insertion loop, the same steps/max_adjust_steps budget, and the same correctness invariants (L5/L12/L14).

Current codebase

Batch placement loops over orders in input order, chaining the previous successfully placed rung id as the hint for the next rung:

smartcontracts/contracts/pair/src/limit_placement.rs — execute_place_limit_orders_batch (loop ~L126–L195). let hint_after = item.hint_after_order_id.or(last_placed_hint); then insert_bid_with_id / insert_ask_with_id; on success last_placed_hint = Some(id); on LimitInsertStepsExceeded the rung is skipped (skipped_count += 1).
execute_place_limit_order_ladder (~L42–L57) expands the spec via expand_limit_ladder and calls the same batch fn.
smartcontracts/packages/dex-common/src/limit_placement.rs — LimitOrderPlacementItem (~L18–L29, has hint_after_order_id), LimitOrderLadderSpec (~L36–L47, no hint field), expand_limit_ladder (~L60–L97) sets hint_after_order_id: None on every rung.
smartcontracts/contracts/pair/src/orderbook.rs — find_insert_bid / find_insert_ask (~L666–L721) and try_insert_after_hint_*, walk_insert_*_toward_head, walk_insert_*_from, walk_insert_*_from_head (~L408–L662). Ids are pre-reserved by reserve_order_id_block; insert_*_with_id accepts hint_after, max_adjust_steps, update_escrow: false.
smartcontracts/contracts/pair/src/contract.rs — hook dispatch (~L701–L712); UpdateLimitOrderPrice handler (~L1178–L1201) already accepts hint_after_order_id.

Why chaining is weak today

Rung 1 always head-walks (last_placed_hint is None). On a deep book this scales with head→first-rung distance.
Bid ladders near-miss every interior rung: input is ascending price, but later bid rungs sort before earlier ones, so the chained hint (previous rung) is a valid anchor in the wrong slot → WalkTowardHead instead of O(1) (see limit_order_tests::limit_batch_chained_near_miss_hint_directional_walk_succeeds ~L3934). With a tight max_adjust_steps interior rungs get skipped (the 0.99/1.0/0.98 batch ~L3793).
Even when chaining is exact, each rung re-loads the hint (+ its next) to re-verify the position it could have inherited from the previous insert.

Why this is needed

Deep, actively-traded books are exactly where ladders are most useful and most expensive. Without these changes, a routine bid ladder degrades to N directional walks (gas blowup) or partial skips (silent rung loss), and there is no way for a client to cheaply anchor the first rung. This is the on-chain half of the deep-book ladder effort (frontend half: companion issue; indexer half: companion issue).

Constraints / guardrails

Hints stay advisory (L14). No change may let a malicious/stale hint corrupt book order. Worst case must remain a bounded head walk.
Preserve id assignment order (L12 / #247). batch_placement_order_ids_match_sequential_singles must still pass: rung order_ids must map to input index (ascending, contiguous from reserve_order_id_block), even if the insertion traversal is reordered. Reorder traversal only — never the id-to-input mapping.
FIFO at equal price unchanged. Equal-price rungs must still resolve to ascending order_id (composite key (price, order_id)). The traversal sort key must be the full composite key so equal-price rungs insert in id order.
Single steps budget per rung (L5). Position threading must not let one rung borrow another rung's budget; each rung still bounded by its own max_adjust_steps (min with hard cap).
One ORDER_NEXT_ID write + one PENDING_ESCROW_* write per token side (L12). Storage-collapse semantics must be preserved.
Partial-batch semantics preserved (#206). A rung that exhausts steps is still skipped + refunded; if none place, tx reverts (LimitBatchNoRungsPlaced).
Emitted wasm attributes must stay in a stable order (indexer columnar zip in parse_limit_order_placements_columnar). Emit place_limit_order events in id/input order regardless of insertion traversal order.
Ladder anchor hint is optional and, when supplied, applies to the boundary rung only (head-most in book order). It must be validated exactly like hint_after_order_id (exists, correct side, linked) and fall back to head walk otherwise.
Any frontend-supplied anchor value is sourced from the indexer, never a direct LCD/RPC call from the dApp (see companion issues).

Relevant files

smartcontracts/contracts/pair/src/limit_placement.rs
smartcontracts/contracts/pair/src/orderbook.rs
smartcontracts/packages/dex-common/src/limit_placement.rs
smartcontracts/contracts/pair/src/contract.rs
smartcontracts/contracts/pair/src/msg.rs (Cw20HookMsg::PlaceLimitOrderLadder)
smartcontracts/tests/src/limit_order_tests.rs
Docs to update: docs/limit-orders.md, docs/contracts-security-audit.md (L5/L12/L14), docs/integrators.md, skills/AGENTS_LIMIT_ORDER_BATCH_LADDER.md

Recommended direction

Book-order insertion sequence. After reserve_order_id_block, build (input_index, id, price) tuples, assign id by input index (unchanged), then compute a traversal order sorted by the side's composite key (bid_before / ask_before semantics; equal price → ascending id). Iterate inserts in that traversal order. Chain last_placed_hint along the traversal so each new rung's predecessor is the previously inserted rung → exact O(1) verify. Collect results and emit place_limit_order attributes in input/id order.
Insert-position threading. Extend find_insert_* (or add a sibling entrypoint) to optionally accept the previous insert's resolved (prev, next) neighbors as a verified cursor. When the new rung's composite key falls between that cursor's prev and next, insert without re-loading the hint. Falls back to the existing hint/anchor/head path when the cursor does not bracket the new key. Keep steps accounting honest (cursor reuse costs 0 extra loads).
Ladder anchor hint. Add hint_after_order_id: Option<u64> to LimitOrderLadderSpec (default None, #[serde(default)]). In expand_limit_ladder, set the boundary rung's hint_after_order_id to the anchor (head-most rung in book order); leave other rungs None so on-chain chaining fills them. Validate via the existing try_insert_after_hint_* path.

Acceptance criteria

Bid ladder of N rungs on an empty book places all N with interior rungs using O(1) verify (no WalkTowardHead), measured by a step counter / gas assertion.
Ask ladder of N rungs behaves identically (already mostly O(1); must not regress).
batch_placement_order_ids_match_sequential_singles still passes — ids map to input order.
Equal-price rungs within one batch resolve to ascending order_id.
A valid LimitOrderLadderSpec.hint_after_order_id lets the boundary rung place under a tight max_adjust_steps on a deep book where it would otherwise be skipped.
An invalid/stale/wrong-side ladder anchor falls back to head walk and still places (no revert solely due to bad anchor).
Storage writes unchanged: one ORDER_NEXT_ID, one PENDING_ESCROW_* per touched side.
Wasm attribute order (per-rung place_limit_order columns) unchanged for the indexer.

Test plan — all paths

Empty book, bid ladder (ascending input prices): assert all rungs placed, step count per interior rung ≈ O(1).
Empty book, ask ladder: assert no regression vs current.
Deep book, ladder fully past existing depth: rung 1 walks; interior rungs O(1) via threaded cursor.
Deep book, foreign orders interleaved between rung prices: interior rungs do short directional walks bounded by max_adjust_steps; assert placed vs skipped counts match a hand-computed expectation.
Equal-price rungs in one batch: FIFO order = ascending id.
Ladder anchor hint valid: boundary rung O(1); compare to same ladder without anchor (skipped under tight steps).
Ladder anchor hint stale/wrong-side/unlinked: falls back to head walk; still places.
Skip path: a rung exhausts max_adjust_steps, is skipped + refunded; later rungs still attempt; chaining continues from last success.
All rungs skipped: tx reverts LimitBatchNoRungsPlaced.
Id-sequence equivalence: batch vs sequential singles produce identical id→price mapping.
Single-rung batch (orders.len()==1) unaffected.
UpdateLimitOrderPrice still honors hint_after_order_id (regression).

Test plan — attack / abuse / hack vectors

Malicious anchor pointing to a far/other-side order: must fall back to head walk; book ordering invariant holds; no extra unbudgeted loads.
Anchor pointing at an order that gets skipped earlier in the same batch: chain must not adopt a non-inserted id; only successfully inserted ids advance the cursor/chain.
Crafted ladder that maximizes interior walks (alternating foreign depth): assert total work stays within sum of per-rung max_adjust_steps; no single rung exceeds its own budget via threaded cursor.
Equal-price flood: many same-price rungs cannot cause O(n^2) verify; cursor threading keeps it linear.
Reordering vs FIFO fairness: prove an attacker cannot use traversal reordering to jump FIFO queue position at equal price (id-order tie-break enforced).
Step-budget exhaustion griefing: confirm a hostile book layout cannot force more than the documented bounded work, and cannot make a victim's later rungs silently mis-link.
Id overflow / reserve block edge: reserve_order_id_block boundary unchanged.
Property test: orderbook::prop_escrow_dll_after_random_inserts extended with reordered-traversal inserts — DLL stays well-formed (no cycles, head/tail consistent, every node reachable).

Verification criteria

cd smartcontracts && cargo test -p cl8y-dex-tests limit_batch place_limit_order_ladder -- --nocapture green, including new step-count/gas assertions.
cargo test -p cl8y-dex-tests batch_placement_order_ids_match_sequential_singles green.
Property tests for DLL well-formedness green.
cargo clippy --all-targets -- -D warnings and schema regen clean.
Docs L5/L12/L14 + limit-orders.md + AGENTS_LIMIT_ORDER_BATCH_LADDER.md updated to describe book-order traversal, cursor threading, and the ladder anchor field.
Gas benchmark on LocalTerra: N-rung bid ladder cost grows ~linearly in N (not N²) and is bounded by head-walk(rung1) + Σ per-rung steps.

## Summary Make on-chain batch/ladder limit-order insertion deterministically cheap on deep books by (1) inserting rungs in **book-sort order** instead of input order, (2) **threading the resolved insert position** from one rung to the next so interior rungs avoid redundant verify loads, and (3) accepting a **single optional anchor hint** on `LimitOrderLadderSpec` so the first/boundary rung does not pay a full head walk. These three changes are bundled because they all live in the pair contract's batch placement path and share the same insertion loop, the same `steps`/`max_adjust_steps` budget, and the same correctness invariants (L5/L12/L14). --- ## Current codebase Batch placement loops over `orders` in **input order**, chaining the previous successfully placed rung id as the hint for the next rung: - `smartcontracts/contracts/pair/src/limit_placement.rs` — `execute_place_limit_orders_batch` (loop ~L126–L195). `let hint_after = item.hint_after_order_id.or(last_placed_hint);` then `insert_bid_with_id` / `insert_ask_with_id`; on success `last_placed_hint = Some(id)`; on `LimitInsertStepsExceeded` the rung is skipped (`skipped_count += 1`). - `execute_place_limit_order_ladder` (~L42–L57) expands the spec via `expand_limit_ladder` and calls the same batch fn. - `smartcontracts/packages/dex-common/src/limit_placement.rs` — `LimitOrderPlacementItem` (~L18–L29, has `hint_after_order_id`), `LimitOrderLadderSpec` (~L36–L47, **no** hint field), `expand_limit_ladder` (~L60–L97) sets `hint_after_order_id: None` on every rung. - `smartcontracts/contracts/pair/src/orderbook.rs` — `find_insert_bid` / `find_insert_ask` (~L666–L721) and `try_insert_after_hint_*`, `walk_insert_*_toward_head`, `walk_insert_*_from`, `walk_insert_*_from_head` (~L408–L662). Ids are pre-reserved by `reserve_order_id_block`; `insert_*_with_id` accepts `hint_after`, `max_adjust_steps`, `update_escrow: false`. - `smartcontracts/contracts/pair/src/contract.rs` — hook dispatch (~L701–L712); `UpdateLimitOrderPrice` handler (~L1178–L1201) already accepts `hint_after_order_id`. ### Why chaining is weak today - **Rung 1 always head-walks** (`last_placed_hint` is `None`). On a deep book this scales with head→first-rung distance. - **Bid ladders near-miss every interior rung**: input is ascending price, but later bid rungs sort *before* earlier ones, so the chained hint (previous rung) is a valid anchor in the wrong slot → `WalkTowardHead` instead of O(1) (see `limit_order_tests::limit_batch_chained_near_miss_hint_directional_walk_succeeds` ~L3934). With a tight `max_adjust_steps` interior rungs get **skipped** (the 0.99/1.0/0.98 batch ~L3793). - Even when chaining is exact, each rung re-loads the hint (+ its `next`) to re-verify the position it could have inherited from the previous insert. --- ## Why this is needed Deep, actively-traded books are exactly where ladders are most useful and most expensive. Without these changes, a routine bid ladder degrades to N directional walks (gas blowup) or partial skips (silent rung loss), and there is no way for a client to cheaply anchor the first rung. This is the on-chain half of the deep-book ladder effort (frontend half: companion issue; indexer half: companion issue). --- ## Constraints / guardrails - **Hints stay advisory (L14).** No change may let a malicious/stale hint corrupt book order. Worst case must remain a bounded head walk. - **Preserve id assignment order (L12 / #247).** `batch_placement_order_ids_match_sequential_singles` must still pass: rung `order_id`s must map to **input index** (ascending, contiguous from `reserve_order_id_block`), even if the *insertion traversal* is reordered. Reorder traversal only — never the id-to-input mapping. - **FIFO at equal price unchanged.** Equal-price rungs must still resolve to ascending `order_id` (composite key `(price, order_id)`). The traversal sort key must be the full composite key so equal-price rungs insert in id order. - **Single `steps` budget per rung (L5).** Position threading must not let one rung borrow another rung's budget; each rung still bounded by its own `max_adjust_steps` (min with hard cap). - **One `ORDER_NEXT_ID` write + one `PENDING_ESCROW_*` write per token side (L12).** Storage-collapse semantics must be preserved. - **Partial-batch semantics preserved (#206).** A rung that exhausts steps is still skipped + refunded; if none place, tx reverts (`LimitBatchNoRungsPlaced`). - **Emitted wasm attributes must stay in a stable order** (indexer columnar zip in `parse_limit_order_placements_columnar`). Emit `place_limit_order` events in id/input order regardless of insertion traversal order. - **Ladder anchor hint is optional** and, when supplied, applies to the **boundary rung** only (head-most in book order). It must be validated exactly like `hint_after_order_id` (exists, correct side, linked) and fall back to head walk otherwise. - Any frontend-supplied anchor value is sourced from the **indexer**, never a direct LCD/RPC call from the dApp (see companion issues). --- ## Relevant files - `smartcontracts/contracts/pair/src/limit_placement.rs` - `smartcontracts/contracts/pair/src/orderbook.rs` - `smartcontracts/packages/dex-common/src/limit_placement.rs` - `smartcontracts/contracts/pair/src/contract.rs` - `smartcontracts/contracts/pair/src/msg.rs` (`Cw20HookMsg::PlaceLimitOrderLadder`) - `smartcontracts/tests/src/limit_order_tests.rs` - Docs to update: `docs/limit-orders.md`, `docs/contracts-security-audit.md` (L5/L12/L14), `docs/integrators.md`, `skills/AGENTS_LIMIT_ORDER_BATCH_LADDER.md` --- ## Recommended direction 1. **Book-order insertion sequence.** After `reserve_order_id_block`, build `(input_index, id, price)` tuples, assign `id` by input index (unchanged), then compute a traversal order sorted by the side's composite key (`bid_before` / `ask_before` semantics; equal price → ascending id). Iterate inserts in that traversal order. Chain `last_placed_hint` along the traversal so each new rung's predecessor is the previously inserted rung → exact O(1) verify. Collect results and emit `place_limit_order` attributes in **input/id order**. 2. **Insert-position threading.** Extend `find_insert_*` (or add a sibling entrypoint) to optionally accept the previous insert's resolved `(prev, next)` neighbors as a verified cursor. When the new rung's composite key falls between that cursor's `prev` and `next`, insert without re-loading the hint. Falls back to the existing hint/anchor/head path when the cursor does not bracket the new key. Keep `steps` accounting honest (cursor reuse costs 0 extra loads). 3. **Ladder anchor hint.** Add `hint_after_order_id: Option<u64>` to `LimitOrderLadderSpec` (default `None`, `#[serde(default)]`). In `expand_limit_ladder`, set the boundary rung's `hint_after_order_id` to the anchor (head-most rung in book order); leave other rungs `None` so on-chain chaining fills them. Validate via the existing `try_insert_after_hint_*` path. --- ## Acceptance criteria - Bid ladder of N rungs on an **empty** book places all N with interior rungs using O(1) verify (no `WalkTowardHead`), measured by a step counter / gas assertion. - Ask ladder of N rungs behaves identically (already mostly O(1); must not regress). - `batch_placement_order_ids_match_sequential_singles` still passes — ids map to input order. - Equal-price rungs within one batch resolve to ascending `order_id`. - A valid `LimitOrderLadderSpec.hint_after_order_id` lets the boundary rung place under a tight `max_adjust_steps` on a deep book where it would otherwise be skipped. - An invalid/stale/wrong-side ladder anchor falls back to head walk and still places (no revert solely due to bad anchor). - Storage writes unchanged: one `ORDER_NEXT_ID`, one `PENDING_ESCROW_*` per touched side. - Wasm attribute order (per-rung `place_limit_order` columns) unchanged for the indexer. --- ## Test plan — all paths - **Empty book, bid ladder (ascending input prices)**: assert all rungs placed, step count per interior rung ≈ O(1). - **Empty book, ask ladder**: assert no regression vs current. - **Deep book, ladder fully past existing depth**: rung 1 walks; interior rungs O(1) via threaded cursor. - **Deep book, foreign orders interleaved between rung prices**: interior rungs do short directional walks bounded by `max_adjust_steps`; assert placed vs skipped counts match a hand-computed expectation. - **Equal-price rungs in one batch**: FIFO order = ascending id. - **Ladder anchor hint valid**: boundary rung O(1); compare to same ladder without anchor (skipped under tight steps). - **Ladder anchor hint stale/wrong-side/unlinked**: falls back to head walk; still places. - **Skip path**: a rung exhausts `max_adjust_steps`, is skipped + refunded; later rungs still attempt; chaining continues from last success. - **All rungs skipped**: tx reverts `LimitBatchNoRungsPlaced`. - **Id-sequence equivalence**: batch vs sequential singles produce identical id→price mapping. - **Single-rung batch** (`orders.len()==1`) unaffected. - **`UpdateLimitOrderPrice`** still honors `hint_after_order_id` (regression). ## Test plan — attack / abuse / hack vectors - **Malicious anchor pointing to a far/other-side order**: must fall back to head walk; book ordering invariant holds; no extra unbudgeted loads. - **Anchor pointing at an order that gets skipped earlier in the same batch**: chain must not adopt a non-inserted id; only successfully inserted ids advance the cursor/chain. - **Crafted ladder that maximizes interior walks** (alternating foreign depth): assert total work stays within sum of per-rung `max_adjust_steps`; no single rung exceeds its own budget via threaded cursor. - **Equal-price flood**: many same-price rungs cannot cause O(n^2) verify; cursor threading keeps it linear. - **Reordering vs FIFO fairness**: prove an attacker cannot use traversal reordering to jump FIFO queue position at equal price (id-order tie-break enforced). - **Step-budget exhaustion griefing**: confirm a hostile book layout cannot force more than the documented bounded work, and cannot make a victim's later rungs silently mis-link. - **Id overflow / reserve block** edge: `reserve_order_id_block` boundary unchanged. - **Property test**: `orderbook::prop_escrow_dll_after_random_inserts` extended with reordered-traversal inserts — DLL stays well-formed (no cycles, head/tail consistent, every node reachable). ## Verification criteria - `cd smartcontracts && cargo test -p cl8y-dex-tests limit_batch place_limit_order_ladder -- --nocapture` green, including new step-count/gas assertions. - `cargo test -p cl8y-dex-tests batch_placement_order_ids_match_sequential_singles` green. - Property tests for DLL well-formedness green. - `cargo clippy --all-targets -- -D warnings` and schema regen clean. - Docs L5/L12/L14 + `limit-orders.md` + `AGENTS_LIMIT_ORDER_BATCH_LADDER.md` updated to describe book-order traversal, cursor threading, and the ladder anchor field. - Gas benchmark on LocalTerra: N-rung bid ladder cost grows ~linearly in N (not N²) and is bounded by head-walk(rung1) + Σ per-rung steps.

PlasticDigits commented

2026-06-01 04:19:15 +00:00

(Migrated from gitlab.com)

Companion issues for the deep-book ladder/hinting effort:

#267 — Indexer insert-hint resolution API (provides the anchor/hint values; frontend uses indexer, not LCD/RPC)
#268 — Frontend deep-book ladder placement (consumes #266 book-order insertion + #267 endpoints)

Dependency: #266 (this) and #267 are foundational; #268 depends on both. The ladder anchor field added here is resolved client-side via #267.

Companion issues for the deep-book ladder/hinting effort: - #267 — Indexer insert-hint resolution API (provides the anchor/hint values; frontend uses indexer, not LCD/RPC) - #268 — Frontend deep-book ladder placement (consumes #266 book-order insertion + #267 endpoints) Dependency: #266 (this) and #267 are foundational; #268 depends on both. The ladder anchor field added here is resolved client-side via #267.

PlasticDigits commented

2026-06-01 04:19:17 +00:00

(Migrated from gitlab.com)

mentioned in issue #267

PlasticDigits commented

2026-06-01 04:19:19 +00:00

(Migrated from gitlab.com)

mentioned in issue #268

PlasticDigits commented

2026-06-01 04:33:52 +00:00

(Migrated from gitlab.com)

mentioned in commit 5b171675b0

mentioned in commit 5b171675b07b7889e8d9270f80c9265be66473d1

PlasticDigits commented

2026-06-01 04:34:04 +00:00

(Migrated from gitlab.com)

Implementation summary (merged to `main` @ `5b17167`)

Implemented deterministic O(1) batch/ladder limit-order insertion for deep books:

Book-order traversal — execute_place_limit_orders_batch assigns ids by input index, sorts inserts by composite book key (bid_before / ask_before), and emits place_limit_order wasm attrs in input/id order (indexer columnar zip unchanged).
Insert-position threading — new InsertThreadCursor in orderbook.rs; insert_*_with_id_for_batch threads resolved (prev, next, next_price) from each successful insert so interior rungs verify in O(0) loads when bracketed. Falls back to existing hint / directional / head-walk paths per L14.
Ladder anchor hint — optional LimitOrderLadderSpec.hint_after_order_id (#[serde(default)]) applied to the head-most rung in book order via expand_limit_ladder; validated through existing try_insert_after_hint_* path.

Docs / invariants updated

L12 / L14 in docs/contracts-security-audit.md
docs/limit-orders.md, docs/integrators.md
skills/AGENTS_LIMIT_ORDER_BATCH_LADDER.md (new invariant §11 + crosslinks to #267/#268)
Frontend wire type: LimitOrderLadderSpecWire.hint_after_order_id?

Tests added / updated

limit_batch_bid_ladder_book_order_traversal_places_all_on_empty_book
limit_batch_equal_price_fifo_by_order_id
limit_batch_ladder_anchor_hint_places_boundary_on_deep_book
limit_batch_ladder_stale_anchor_still_places
Updated near-miss deep-book test for book-order semantics
expand_ladder_anchor_on_boundary_rung_ascending_bid (dex-common)

Verification checklist

cd smartcontracts && cargo test -p cl8y-dex-tests limit_batch batch_placement_order_ids place_limit_order_ladder
cargo test -p cl8y-dex-pair prop_escrow
cargo clippy --all-targets -- -D warnings
Empty-book bid ladder (ascending input prices): all rungs placed; interior rungs O(1) via thread cursor
Ask ladder on empty book: no regression
Deep book + ladder anchor hint: boundary rung places under tight max_adjust_steps
Stale/wrong-side ladder anchor: falls back to head walk, tx still succeeds
Equal-price batch rungs: FIFO = ascending order_id; book head = lowest id
Partial batch skip path unchanged (#206): skipped rung refunded; LimitBatchNoRungsPlaced when none place
batch_placement_order_ids_match_sequential_singles green (L12 id mapping)
Wasm attr order matches input index (not traversal order) for indexer columnar parser
One ORDER_NEXT_ID + one PENDING_ESCROW_* write per side per batch (L12)

Follow-ups (companion issues)

#267 — indexer insert-hint resolution API (source for ladder/batch anchor values; frontend must not use raw LCD for hints)
#268 — frontend deep-book ladder placement consuming #266 + #267

Requesting verification from the QA agent team when convenient.

## Implementation summary (merged to `main` @ 5b17167) Implemented deterministic O(1) batch/ladder limit-order insertion for deep books: 1. **Book-order traversal** — `execute_place_limit_orders_batch` assigns ids by input index, sorts inserts by composite book key (`bid_before` / `ask_before`), and emits `place_limit_order` wasm attrs in **input/id order** (indexer columnar zip unchanged). 2. **Insert-position threading** — new `InsertThreadCursor` in `orderbook.rs`; `insert_*_with_id_for_batch` threads resolved `(prev, next, next_price)` from each successful insert so interior rungs verify in O(0) loads when bracketed. Falls back to existing hint / directional / head-walk paths per L14. 3. **Ladder anchor hint** — optional `LimitOrderLadderSpec.hint_after_order_id` (`#[serde(default)]`) applied to the **head-most rung in book order** via `expand_limit_ladder`; validated through existing `try_insert_after_hint_*` path. ### Docs / invariants updated - L12 / L14 in `docs/contracts-security-audit.md` - `docs/limit-orders.md`, `docs/integrators.md` - `skills/AGENTS_LIMIT_ORDER_BATCH_LADDER.md` (new invariant §11 + crosslinks to #267/#268) - Frontend wire type: `LimitOrderLadderSpecWire.hint_after_order_id?` ### Tests added / updated - `limit_batch_bid_ladder_book_order_traversal_places_all_on_empty_book` - `limit_batch_equal_price_fifo_by_order_id` - `limit_batch_ladder_anchor_hint_places_boundary_on_deep_book` - `limit_batch_ladder_stale_anchor_still_places` - Updated near-miss deep-book test for book-order semantics - `expand_ladder_anchor_on_boundary_rung_ascending_bid` (dex-common) --- ## Verification checklist - [ ] `cd smartcontracts && cargo test -p cl8y-dex-tests limit_batch batch_placement_order_ids place_limit_order_ladder` - [ ] `cargo test -p cl8y-dex-pair prop_escrow` - [ ] `cargo clippy --all-targets -- -D warnings` - [ ] Empty-book bid ladder (ascending input prices): all rungs placed; interior rungs O(1) via thread cursor - [ ] Ask ladder on empty book: no regression - [ ] Deep book + ladder anchor hint: boundary rung places under tight `max_adjust_steps` - [ ] Stale/wrong-side ladder anchor: falls back to head walk, tx still succeeds - [ ] Equal-price batch rungs: FIFO = ascending `order_id`; book head = lowest id - [ ] Partial batch skip path unchanged (#206): skipped rung refunded; `LimitBatchNoRungsPlaced` when none place - [ ] `batch_placement_order_ids_match_sequential_singles` green (L12 id mapping) - [ ] Wasm attr order matches input index (not traversal order) for indexer columnar parser - [ ] One `ORDER_NEXT_ID` + one `PENDING_ESCROW_*` write per side per batch (L12) --- ## Follow-ups (companion issues) - **#267** — indexer insert-hint resolution API (source for ladder/batch anchor values; frontend must not use raw LCD for hints) - **#268** — frontend deep-book ladder placement consuming #266 + #267 --- Requesting verification from the QA agent team when convenient.

Brouie commented

2026-06-01 14:12:49 +00:00

(Migrated from gitlab.com)

mentioned in merge request !733

Brouie commented

2026-06-01 15:44:54 +00:00

(Migrated from gitlab.com)

Verified #266 on d6701c4 (deterministic O(1) batch/ladder insertion). Contract-only.

Tests (in make test-contracts = 402/0):

limit_batch_bid_ladder_book_order_traversal_places_all_on_empty_book (interior rungs O(1) via thread cursor),
limit_batch_equal_price_fifo_by_order_id (FIFO = ascending order_id), batch_placement_order_ids_match_sequential_singles
(L12 id→input mapping preserved), limit_batch_ladder_anchor_hint_places_boundary_on_deep_book +
limit_batch_ladder_stale_anchor_still_places (anchor valid/stale), limit_batch_partial_success_skips_book_walk_failures
(#206 partial skip), place_limit_order_ladder_five_rungs, limit_batch_item_explicit_hint_places_on_deep_book — 11/11.
dex-common expand_ladder_anchor_on_boundary_rung_ascending_bid; orderbook::prop_escrow_dll_after_random_inserts (DLL well-formed).
cargo clippy --all-targets -- -D warnings: clean (0 warnings).
L12/L14 (contracts-security-audit.md), limit-orders.md, AGENTS_LIMIT_ORDER_BATCH_LADDER.md updated.

Live ladder gas on LocalTerra (empty/near-empty book, one tx):

5-rung bid ladder = 467,117 gas (93k/rung); 20-rung = 915,187 gas (46k/rung).
Per-rung gas DROPS as N grows (fixed overhead amortizes) -> gas sublinear in N, confirms NOT O(N^2)
(book-order traversal + InsertThreadCursor giving O(1)-bracketed interior rungs).
40-rung correctly rejected: "ladder count 40 exceeds pair max_batch_rungs 20" (governance cap enforced).

Good to close from my side once !733 merges. @PlasticDigits

Verified #266 on d6701c4 (deterministic O(1) batch/ladder insertion). Contract-only. Tests (in make test-contracts = 402/0): - limit_batch_bid_ladder_book_order_traversal_places_all_on_empty_book (interior rungs O(1) via thread cursor), limit_batch_equal_price_fifo_by_order_id (FIFO = ascending order_id), batch_placement_order_ids_match_sequential_singles (L12 id→input mapping preserved), limit_batch_ladder_anchor_hint_places_boundary_on_deep_book + limit_batch_ladder_stale_anchor_still_places (anchor valid/stale), limit_batch_partial_success_skips_book_walk_failures (#206 partial skip), place_limit_order_ladder_five_rungs, limit_batch_item_explicit_hint_places_on_deep_book — 11/11. - dex-common expand_ladder_anchor_on_boundary_rung_ascending_bid; orderbook::prop_escrow_dll_after_random_inserts (DLL well-formed). - cargo clippy --all-targets -- -D warnings: clean (0 warnings). - L12/L14 (contracts-security-audit.md), limit-orders.md, AGENTS_LIMIT_ORDER_BATCH_LADDER.md updated. Live ladder gas on LocalTerra (empty/near-empty book, one tx): - 5-rung bid ladder = 467,117 gas (93k/rung); 20-rung = 915,187 gas (46k/rung). - Per-rung gas DROPS as N grows (fixed overhead amortizes) -> gas sublinear in N, confirms NOT O(N^2) (book-order traversal + InsertThreadCursor giving O(1)-bracketed interior rungs). - 40-rung correctly rejected: "ladder count 40 exceeds pair max_batch_rungs 20" (governance cap enforced). Good to close from my side once !733 merges. @PlasticDigits

Brouie commented

2026-06-01 16:29:50 +00:00

(Migrated from gitlab.com)

mentioned in issue #263

PlasticDigits (Migrated from gitlab.com) closed this issue

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

PlasticDigits commented

2026-08-17 10:26:07 +00:00

(Migrated from gitlab.com)

mentioned in issue #546