code/cl8y-dex-terraclassic

Fork 0

Hybrid reverse simulation: reduce redundant book walks in query #257

New issue

Closed

opened 2026-05-31 13:45:54 +00:00 by PlasticDigits · 4 comments

PlasticDigits commented

2026-05-31 13:45:54 +00:00

(Migrated from gitlab.com)

Summary

Optimize HybridReverseSimulation so it does not re-walk the limit book on every exponential/binary-search iteration; seed search bounds from closed-form pool math and minimize full simulate_hybrid_swap_with_fee calls.

Current codebase

Query entry: query_hybrid_reverse_simulation in smartcontracts/contracts/pair/src/contract.rs.
Algorithm today:
1. Hoist fee discount once (effective_fee_bps_for_sim) — good (#238 guardrail).
2. Exponential search: hi doubles up to 128 iterations, each calling simulate_hybrid_swap_with_fee with scale_hybrid_template(&hybrid, hi).
3. Binary search on lo..r_hi, each iteration another full simulation.
4. Final simulation at r_hi.
Each simulate_hybrid_swap_with_fee can invoke simulate_match_bids / simulate_match_asks (full book walk up to max_maker_fills) plus pool AMM math.
Router reverse multi-hop calls pair HybridReverseSimulation per hop (smartcontracts/contracts/router/src/contract.rs) — cost multiplies by hops (≤ 4).
Tests: smartcontracts/tests/src/lib.rs, limit_order_tests.rs (reverse sim cases).

Why this is needed

Query gas / latency: Worst case ≈ (128 + log₂(hi) + 2) full hybrid simulations; deep books + book leg can exceed node query limits or timeout indexers/wallets.
Redundant work: Pool-only portion of reverse offer has a direct constant-product inverse; book leg monotonicity allows tighter bounds without re-walking from scratch each iteration.
Execute path unchanged; this is read-only optimization but critical for routing quotes and dApp reverse quotes.

Constraints and guardrails

Correctness: offer_amount must remain minimal offer achieving ask_target return (same as today’s search invariant); rounding must not under-quote vs execute.
Discount: Keep single discount resolution per query (#238); do not re-query registry per iteration.
Parity: When book leg = 0, result must match pool-only reverse (existing pool_only_hybrid_template paths).
Book + pool split: scale_hybrid_template preserves pool_input : book_input ratio — any optimizer must respect hybrid scaling semantics.
Related work: If GitLab #254 (MAX_SCAN_STEPS) lands first, simulation must use identical book walk bounds as execute.
Migration: none.

Relevant files

Area	Path
Reverse query	`smartcontracts/contracts/pair/src/contract.rs` (`query_hybrid_reverse_simulation`, `simulate_hybrid_swap_with_fee`)
Book sim	`smartcontracts/contracts/pair/src/orderbook.rs` (`simulate_match_*`)
Types	`smartcontracts/packages/dex-common/src/pair.rs` (`HybridReverseSimulationResponse`, `HybridSwapParams`)
Router	`smartcontracts/contracts/router/src/contract.rs`
Docs	`docs/limit-orders.md`, `skills/AGENTS_HYBRID_QUOTING.md`
Tests	`smartcontracts/tests/src/lib.rs`, `limit_order_tests.rs`

Recommended direction

Pool-only bound: Compute upper/lower offer from constant-product reverse on pool_input slice only (existing reserve math in swap/sim helpers) to seed hi / shrink 128-iteration ramp.
Book monotonicity: For fixed hybrid ratio, book return is non-decreasing in offer; binary search remains valid — reduce iterations by better initial hi (e.g. pool quote + book quote separately, sum).
Optional: Separate “book contribution at offer X” cache inside single query to avoid re-walking identical offers if iterations repeat (unlikely with binary search).
Cap iterations: Hard max sim calls (e.g. ≤ 32) with documented failure if liquidity insufficient.
Add regression tests comparing old vs new offer_amount on grid of pool/book splits.

Acceptance criteria

HybridReverseSimulation returns identical offer_amount (and fee breakdown fields) as baseline on existing test vectors.
Worst-case wasm query gas measurably lower on book+pool case (document benchmark in MR).
Still handles insufficient liquidity error when no offer suffices.
Router reverse sim multi-hop still passes integration tests.

Test plan (functional paths)

Path	Expectation
Pool-only reverse	Unchanged offer
Book-only reverse	Unchanged vs brute reference
Hybrid 50/50 split	Match prior implementation
With fee discount / trader	Same effective fee
`ask_target` = 0	Zero offer
Insufficient depth	Same error string class

Test plan (attack / abuse / hack vectors)

Vector	Verification
Caller passes huge `ask_target`	Bounded iterations; no OOM
Manipulated `hybrid` ratio	`HybridSplitMismatch` / validation unchanged
Quote below execute reality	Min-offer invariant tests (no under-quote)
DoS via repeated LCD query	Per-query work cap

Verification criteria

All hybrid reverse tests green (cargo test).
Optional: property test — forward sim at reverse offer ≥ target return.
Document iteration bounds in docs/contracts-terraclassic.md or limit-orders quoting section.

## Summary Optimize `HybridReverseSimulation` so it does not re-walk the limit book on every exponential/binary-search iteration; seed search bounds from closed-form pool math and minimize full `simulate_hybrid_swap_with_fee` calls. ## Current codebase - **Query entry:** `query_hybrid_reverse_simulation` in `smartcontracts/contracts/pair/src/contract.rs`. - **Algorithm today:** 1. Hoist fee discount once (`effective_fee_bps_for_sim`) — good (#238 guardrail). 2. Exponential search: `hi` doubles up to **128** iterations, each calling `simulate_hybrid_swap_with_fee` with `scale_hybrid_template(&hybrid, hi)`. 3. Binary search on `lo..r_hi`, each iteration another full simulation. 4. Final simulation at `r_hi`. - Each `simulate_hybrid_swap_with_fee` can invoke `simulate_match_bids` / `simulate_match_asks` (full book walk up to `max_maker_fills`) plus pool AMM math. - **Router** reverse multi-hop calls pair `HybridReverseSimulation` per hop (`smartcontracts/contracts/router/src/contract.rs`) — cost multiplies by hops (≤ 4). - **Tests:** `smartcontracts/tests/src/lib.rs`, `limit_order_tests.rs` (reverse sim cases). ## Why this is needed - **Query gas / latency:** Worst case ≈ (128 + log₂(hi) + 2) full hybrid simulations; deep books + book leg can exceed node query limits or timeout indexers/wallets. - **Redundant work:** Pool-only portion of reverse offer has a **direct** constant-product inverse; book leg monotonicity allows tighter bounds without re-walking from scratch each iteration. - Execute path unchanged; this is read-only optimization but critical for routing quotes and dApp reverse quotes. ## Constraints and guardrails - **Correctness:** `offer_amount` must remain **minimal** offer achieving `ask_target` return (same as today’s search invariant); rounding must not under-quote vs execute. - **Discount:** Keep single discount resolution per query (#238); do not re-query registry per iteration. - **Parity:** When book leg = 0, result must match pool-only reverse (existing `pool_only_hybrid_template` paths). - **Book + pool split:** `scale_hybrid_template` preserves `pool_input : book_input` ratio — any optimizer must respect hybrid scaling semantics. - **Related work:** If GitLab #254 (`MAX_SCAN_STEPS`) lands first, simulation must use identical book walk bounds as execute. - **Migration:** none. ## Relevant files | Area | Path | |------|------| | Reverse query | `smartcontracts/contracts/pair/src/contract.rs` (`query_hybrid_reverse_simulation`, `simulate_hybrid_swap_with_fee`) | | Book sim | `smartcontracts/contracts/pair/src/orderbook.rs` (`simulate_match_*`) | | Types | `smartcontracts/packages/dex-common/src/pair.rs` (`HybridReverseSimulationResponse`, `HybridSwapParams`) | | Router | `smartcontracts/contracts/router/src/contract.rs` | | Docs | `docs/limit-orders.md`, `skills/AGENTS_HYBRID_QUOTING.md` | | Tests | `smartcontracts/tests/src/lib.rs`, `limit_order_tests.rs` | ## Recommended direction 1. **Pool-only bound:** Compute upper/lower offer from constant-product reverse on `pool_input` slice only (existing reserve math in swap/sim helpers) to seed `hi` / shrink 128-iteration ramp. 2. **Book monotonicity:** For fixed `hybrid` ratio, book return is non-decreasing in offer; binary search remains valid — reduce iterations by better initial `hi` (e.g. pool quote + book quote separately, sum). 3. **Optional:** Separate “book contribution at offer X” cache inside single query to avoid re-walking identical offers if iterations repeat (unlikely with binary search). 4. **Cap iterations:** Hard max sim calls (e.g. ≤ 32) with documented failure if liquidity insufficient. 5. Add regression tests comparing old vs new offer_amount on grid of pool/book splits. ## Acceptance criteria - [ ] `HybridReverseSimulation` returns identical `offer_amount` (and fee breakdown fields) as baseline on existing test vectors. - [ ] Worst-case wasm query gas measurably lower on book+pool case (document benchmark in MR). - [ ] Still handles insufficient liquidity error when no offer suffices. - [ ] Router reverse sim multi-hop still passes integration tests. ## Test plan (functional paths) | Path | Expectation | |------|-------------| | Pool-only reverse | Unchanged offer | | Book-only reverse | Unchanged vs brute reference | | Hybrid 50/50 split | Match prior implementation | | With fee discount / trader | Same effective fee | | `ask_target` = 0 | Zero offer | | Insufficient depth | Same error string class | ## Test plan (attack / abuse / hack vectors) | Vector | Verification | |--------|----------------| | Caller passes huge `ask_target` | Bounded iterations; no OOM | | Manipulated `hybrid` ratio | `HybridSplitMismatch` / validation unchanged | | Quote below execute reality | Min-offer invariant tests (no under-quote) | | DoS via repeated LCD query | Per-query work cap | ## Verification criteria - All hybrid reverse tests green (`cargo test`). - Optional: property test — forward sim at reverse offer ≥ target return. - Document iteration bounds in `docs/contracts-terraclassic.md` or limit-orders quoting section.

PlasticDigits commented

2026-05-31 14:05:37 +00:00

(Migrated from gitlab.com)

mentioned in commit 777ac45db4

mentioned in commit 777ac45db4e3a89c888379dee07935cbb6aea985

PlasticDigits commented

2026-05-31 14:05:50 +00:00

(Migrated from gitlab.com)

Implemented (main @ `777ac45`)

Optimized HybridReverseSimulation to reduce redundant full hybrid simulations on LCD/indexer reverse quotes.

Code

New module smartcontracts/contracts/pair/src/hybrid_reverse.rs: pool CP reverse math seeds the upper offer bound; MAX_HYBRID_REVERSE_SIM_CALLS = 32 caps full simulate_hybrid_swap_with_fee calls per query.
query_hybrid_reverse_simulation uses seeded upper bound + binary search (replaces 128-step exponential ramp). Fee discount still resolved once per query (#238 guardrail).
Regression: limit_order_tests::hybrid_reverse_sim_minimal_offer_invariant (pool-only, book-only, 40/60, 50/50 splits).

Docs / agent playbooks

Invariant L8 updated: docs/contracts-security-audit.md
docs/limit-orders.md, docs/contracts-terraclassic.md, docs/adr/0001-hybrid-quoting-and-routing.md
Third-party agents: skills/AGENTS_HYBRID_QUOTING.md

Verification checklist

cd smartcontracts && cargo test -p cl8y-dex-pair hybrid_reverse
cd smartcontracts && cargo test -p cl8y-dex-tests limit_order_tests::hybrid_reverse_sim_minimal_offer_invariant
cd smartcontracts && cargo test -p cl8y-dex-tests test_reverse_simulation test_router_reverse_simulate
cd smartcontracts && cargo test -p cl8y-dex-tests hybrid_pool_and_book hybrid_simulation_matches_execute
After wasm redeploy: router reverse_simulate_swap_operations on a book+pool hop matches pre-deploy quotes for same snapshot

Follow-up (optional)

Wasm query gas benchmark on deep book + hybrid split (document % reduction vs pre-#257) — not run in this MR.

@qa-agent-team — please verify on main (777ac45): minimal-offer invariant tests above, router reverse multi-hop, and that discounted trader reverse quotes still match execute after deploy.

Issue left open until QA sign-off.

## Implemented (main @ 777ac45) Optimized `HybridReverseSimulation` to reduce redundant full hybrid simulations on LCD/indexer reverse quotes. ### Code - New module `smartcontracts/contracts/pair/src/hybrid_reverse.rs`: pool CP reverse math seeds the upper offer bound; `MAX_HYBRID_REVERSE_SIM_CALLS = 32` caps full `simulate_hybrid_swap_with_fee` calls per query. - `query_hybrid_reverse_simulation` uses seeded upper bound + binary search (replaces 128-step exponential ramp). Fee discount still resolved **once** per query (#238 guardrail). - Regression: `limit_order_tests::hybrid_reverse_sim_minimal_offer_invariant` (pool-only, book-only, 40/60, 50/50 splits). ### Docs / agent playbooks - Invariant **L8** updated: `docs/contracts-security-audit.md` - `docs/limit-orders.md`, `docs/contracts-terraclassic.md`, `docs/adr/0001-hybrid-quoting-and-routing.md` - Third-party agents: `skills/AGENTS_HYBRID_QUOTING.md` --- ### Verification checklist - [ ] `cd smartcontracts && cargo test -p cl8y-dex-pair hybrid_reverse` - [ ] `cd smartcontracts && cargo test -p cl8y-dex-tests limit_order_tests::hybrid_reverse_sim_minimal_offer_invariant` - [ ] `cd smartcontracts && cargo test -p cl8y-dex-tests test_reverse_simulation test_router_reverse_simulate` - [ ] `cd smartcontracts && cargo test -p cl8y-dex-tests hybrid_pool_and_book hybrid_simulation_matches_execute` - [ ] After wasm redeploy: router `reverse_simulate_swap_operations` on a book+pool hop matches pre-deploy quotes for same snapshot ### Follow-up (optional) - Wasm query gas benchmark on deep book + hybrid split (document % reduction vs pre-#257) — not run in this MR. --- **@qa-agent-team** — please verify on `main` (777ac45): minimal-offer invariant tests above, router reverse multi-hop, and that discounted `trader` reverse quotes still match execute after deploy. Issue left **open** until QA sign-off.

Brouie commented

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

(Migrated from gitlab.com)

Verified #257 on main @ 6b22feb (777ac45, live on LocalTerra). Source + the reverse-sim test suite + live router equivalence and a discounted reverse↔execute round-trip. This is a read-only optimization, so the bar is correctness — minimal offer, no under-quote — and that holds.

Headline — no under-quote + sim↔execute parity, proven live

On a deep book (300+ resting orders), reverse-quoted a discounted trader (test1, 95% tier) for target return 50,000,000 T1, hybrid 50/50 book+pool:

reverse offer = 44,579,693 T0, predicted return (book+pool) = 50,000,000 (exactly the target → minimal offer)
forward-executed at that offer → code=0, return_amount=50,000,000 (≥ target), effective_fee_bps=9 (base 180 × 5% after the 95% discount)
realized == predicted, to the unit — the offer the optimized reverse sim returns actually achieves the target when executed, and the discount matches execute

Discount is applied in the reverse path too: discounted offer 44,579,693 < undiscounted 45,340,115 for the same target.

Acceptance criteria

AC1 — identical offer_amount + breakdown vs baseline: source — query_hybrid_reverse_simulation keeps the same search invariant (minimal offer where the full sim's return ≥ target) and ends on a final validating run_sim(r_hi); the new pool-CP seed (seed_upper_offer_from_pool_math, ceil_div conservative) only changes how the upper bound is found, not the convergence target. Tests hybrid_reverse_sim_minimal_offer_invariant (pool-only / book-only / 40-60 / 50-50), test_reverse_simulation(_b_to_a), hybrid_simulation_matches_execute_with_fee_discount. Live: minimal offer (return == target exactly). (layer note below)
AC3 — insufficient-liquidity preserved: source — InsufficientLiquidity from the sim + an offer-overflow guard in the doubling loop. Tests test_reverse_simulation_with_100_pct_fee_rejected, test_reverse_simulation_with_wrong_asset_rejected.
AC4 — router reverse multi-hop: test test_router_reverse_simulate. Live: router reverse_simulate_swap_operations (book+pool hop) offer 45,340,115 == pair HybridReverseSimulation 45,340,115 — identical (router delegates to the pair per hop).

(AC2 is the one open item — see below.)

Functional + attack plans

Functional (pool-only, book-only, 50/50, with discount/trader, ask_target=0, insufficient depth): ask_target==0→zero offer and book_input==0→pool-only-parity seed (source) + the invariant test grid + live discounted 50/50.
Attack: huge ask_target → bounded by MAX_HYBRID_REVERSE_SIM_CALLS=32 (source + live, queries completed); manipulated hybrid ratio → scale_hybrid_template validation (source); quote-below-execute → min-offer invariant test + live no-under-quote (executed at the quote, realized ≥ target); DoS via repeated LCD query → per-query 32-call cap.

Guardrails confirmed (source)

Fee discount resolved once per query (effective_fee_bps_for_sim before the search, reused across iterations) — the #238 guardrail, not re-queried per iteration.
Sim uses simulate_match_* → the same MAX_SCAN_STEPS (288) book-walk bounds as execute (#254), so reverse quotes can't out-walk the execute path.

Dev checklist

cargo test -p cl8y-dex-pair hybrid_reverse — 2/0
hybrid_reverse_sim_minimal_offer_invariant — pass
test_reverse_simulation + test_router_reverse_simulate — pass
hybrid_pool_and_book + hybrid_simulation_matches_execute* — pass
Router reverse_simulate_swap_operations on a book+pool hop — live, matches the pair reverse exactly

Layer honesty

AC2 (worst-case query gas number) is OPEN — there's no pre-#257 build deployed to contrast against, so I can't report a numeric % reduction (same structural baseline gap as #252/#254/#255/#256). What I can report is the bounded behavior: the MAX_HYBRID_REVERSE_SIM_CALLS=32 cap + pool-seeded binary search complete and return a quote on a 300+-order deep book — exactly the case where the old 128-step exponential ramp (≈128 + log₂ + 2 full sims) could blow the query-gas / indexer-timeout budget.
"Identical to baseline" is test-encoded (the invariant regression vectors carry the expected offers), not a live before/after. Live instead proves the stronger pair of properties: minimality (return == target) and sim↔execute parity (realized == predicted, exact).
Router: multi-hop (≥2 hops) is test-covered (test_router_reverse_simulate); live I confirmed single-hop router↔pair equivalence (the router calls the pair HybridReverseSimulation per hop, so multi-hop is that, composed).

@PlasticDigits — verified and signed off from my side, no issues found (minimal offer, no under-quote, discounted reverse↔execute parity exact, bounded query work); over to you to close.

Verified #257 on `main` @ `6b22feb` (`777ac45`, live on LocalTerra). Source + the reverse-sim test suite + live router equivalence and a discounted reverse↔execute round-trip. This is a read-only optimization, so the bar is correctness — minimal offer, no under-quote — and that holds. ## Headline — no under-quote + sim↔execute parity, proven live On a deep book (300+ resting orders), reverse-quoted a discounted trader (test1, 95% tier) for target return **50,000,000 T1**, hybrid 50/50 book+pool: - reverse offer = **44,579,693** T0, predicted return (book+pool) = **50,000,000** (exactly the target → minimal offer) - forward-executed at that offer → `code=0`, **`return_amount=50,000,000`** (≥ target), `effective_fee_bps=9` (base 180 × 5% after the 95% discount) - **realized == predicted, to the unit** — the offer the optimized reverse sim returns actually achieves the target when executed, and the discount matches execute Discount is applied in the reverse path too: discounted offer 44,579,693 < undiscounted 45,340,115 for the same target. ## Acceptance criteria - **AC1 — identical `offer_amount` + breakdown vs baseline:** source — `query_hybrid_reverse_simulation` keeps the same search invariant (minimal offer where the full sim's return ≥ target) and ends on a **final validating `run_sim(r_hi)`**; the new pool-CP seed (`seed_upper_offer_from_pool_math`, `ceil_div` conservative) only changes *how* the upper bound is found, not the convergence target. Tests `hybrid_reverse_sim_minimal_offer_invariant` (pool-only / book-only / 40-60 / 50-50), `test_reverse_simulation(_b_to_a)`, `hybrid_simulation_matches_execute_with_fee_discount`. Live: minimal offer (return == target exactly). *(layer note below)* - **AC3 — insufficient-liquidity preserved:** source — `InsufficientLiquidity` from the sim + an offer-overflow guard in the doubling loop. Tests `test_reverse_simulation_with_100_pct_fee_rejected`, `test_reverse_simulation_with_wrong_asset_rejected`. - **AC4 — router reverse multi-hop:** test `test_router_reverse_simulate`. Live: router `reverse_simulate_swap_operations` (book+pool hop) offer 45,340,115 == pair `HybridReverseSimulation` 45,340,115 — identical (router delegates to the pair per hop). (AC2 is the one open item — see below.) ## Functional + attack plans - Functional (pool-only, book-only, 50/50, with discount/trader, `ask_target=0`, insufficient depth): `ask_target==0`→zero offer and `book_input==0`→pool-only-parity seed (source) + the invariant test grid + live discounted 50/50. - Attack: huge `ask_target` → bounded by `MAX_HYBRID_REVERSE_SIM_CALLS=32` (source + live, queries completed); manipulated hybrid ratio → `scale_hybrid_template` validation (source); quote-below-execute → min-offer invariant test + **live no-under-quote** (executed at the quote, realized ≥ target); DoS via repeated LCD query → per-query 32-call cap. ## Guardrails confirmed (source) - Fee discount resolved **once** per query (`effective_fee_bps_for_sim` before the search, reused across iterations) — the #238 guardrail, not re-queried per iteration. - Sim uses `simulate_match_*` → the same `MAX_SCAN_STEPS` (288) book-walk bounds as execute (#254), so reverse quotes can't out-walk the execute path. ## Dev checklist - [x] `cargo test -p cl8y-dex-pair hybrid_reverse` — 2/0 - [x] `hybrid_reverse_sim_minimal_offer_invariant` — pass - [x] `test_reverse_simulation` + `test_router_reverse_simulate` — pass - [x] `hybrid_pool_and_book` + `hybrid_simulation_matches_execute*` — pass - [x] Router `reverse_simulate_swap_operations` on a book+pool hop — live, matches the pair reverse exactly ## Layer honesty - **AC2 (worst-case query gas number) is OPEN** — there's no pre-#257 build deployed to contrast against, so I can't report a numeric % reduction (same structural baseline gap as #252/#254/#255/#256). What I can report is the **bounded behavior**: the `MAX_HYBRID_REVERSE_SIM_CALLS=32` cap + pool-seeded binary search complete and return a quote on a 300+-order deep book — exactly the case where the old 128-step exponential ramp (≈128 + log₂ + 2 full sims) could blow the query-gas / indexer-timeout budget. - **"Identical to baseline" is test-encoded** (the invariant regression vectors carry the expected offers), not a live before/after. Live instead proves the stronger pair of properties: *minimality* (return == target) and *sim↔execute parity* (realized == predicted, exact). - **Router:** multi-hop (≥2 hops) is test-covered (`test_router_reverse_simulate`); live I confirmed single-hop router↔pair equivalence (the router calls the pair `HybridReverseSimulation` per hop, so multi-hop is that, composed). @PlasticDigits — verified and signed off from my side, no issues found (minimal offer, no under-quote, discounted reverse↔execute parity exact, bounded query work); over to you to close.

PlasticDigits (Migrated from gitlab.com) closed this issue

2026-06-01 04:23:25 +00:00

Brouie commented

2026-06-01 05:25:47 +00:00

(Migrated from gitlab.com)

mentioned in issue #258