--- id: TIP-1087 title: V2 DEX order storage with book indexes description: Introduce a V2 Stablecoin DEX order layout that stores a compact orderbook index instead of repeating the full book key. authors: Arsenii Kulikov (@klkvr), @0xrusowsky status: Draft related: TIP-1062, TIP-1056 protocolVersion: T8 --- # TIP-1087: V2 DEX order storage with book indexes ## Abstract This TIP reduces indexed Stablecoin DEX orders from 4 storage slots to 3 by replacing each order's repeated 32-byte `bookKey` with a 4-byte `bookIndex` pointer into the append-only `book_keys` vector. The compact pointer fits in unused bytes in the first order word, eliminating the dedicated book-key slot while preserving ABI compatibility by resolving `bookKey` as `book_keys[bookIndex]` on reads. At activation, orderbooks gain a persisted index, newly indexed orderbooks track that index, and new orders use `V2Order` whenever the target orderbook has an index. ## Motivation TIP-1062 introduces versioned DEX order storage and a `V1Order` layout that reduces the legacy 6-slot order to 4 slots. A separate `V2Order` gives another slot reduction while preserving V1 as its own layout. It uses the existing versioned dispatch path for a normal forward-compatible order format upgrade: legacy orders remain version `0`, TIP-1062 orders remain version `1`, and indexed orders created after activation use version `2`. The DEX already maintains an append-only `book_keys` vector. Storing the vector index in indexed new orders avoids repeating the full `bytes32 bookKey` while allowing the existing order ABI to recover `bookKey` as `book_keys[bookIndex]`. Because the chain is already live and existing orderbooks do not have a persisted index, post-activation writes fall back to `V1Order` until an offchain migration persists the orderbook's index. ## Assumptions - Versioned order-storage abstraction, as defined in TIP-1062, is active before this TIP. If order reads and writes bypass that abstraction, mixed-version linked lists can be corrupted. - `book_keys` is append-only and indexes are stable for the lifetime of the DEX. Reordering or removing entries would make existing `V2Order.bookIndex` values decode to the wrong orderbook. - Every initialized orderbook has exactly one entry in `book_keys`. If a pre-activation orderbook key is missing from `book_keys`, `setBookIndex` MUST fail instead of assigning a synthetic index. - Off-chain migration tooling can derive each pre-activation orderbook's `book_keys` index. If an orderbook remains unmigrated after activation, new orders for that book continue to use `V1Order` until its index is persisted. ## Threat Model - DEX users may place, cancel, and match orders across legacy, V1, and V2 linked lists. They are untrusted and MUST NOT be able to make pointer updates use the wrong layout version. - DEX users may create many orderbooks before activation in an attempt to make migration expensive or DoS V2 adoption. The fallback-to-V1 write path and explicit `setBookIndex` migration keep the optimization opt-in per orderbook: unmigrated books remain functional without forcing onchain scans or blocking indexed books from using V2. - DEX implementation code is trusted to route all order field reads, writes, deletions, and flip rewrites through the versioned order-storage abstraction. --- # Specification The top-level storage slot of `orders` is unchanged. The mapping key remains `uint128 orderId`, and `orderId` is not stored inside `V2Order` values. ## Existing layouts Version `0` is the legacy 6-slot order layout. Version `1` is the TIP-1062 `V1Order` layout. This TIP does not change either layout. All order reads MUST continue to read byte offset `31` of slot `0` as the order version and dispatch by version. Unknown versions MUST fail. ## V2Order layout Indexed orders created after activation use version `2`, stored at byte offset `31` of slot `0`. ```text slot 0: offset 0 maker address 20 bytes offset 20 metadata uint8 1 byte bit 0 isBid bool 1 bit bit 1 isFlip bool 1 bit offset 21 tick int16 2 bytes offset 23 flipTick int16 2 bytes offset 25 bookIndex uint32 4 bytes offset 29 unused 2 bytes offset 31 version uint8 1 byte slot 1: offset 0 amount uint128 16 bytes offset 16 remaining uint128 16 bytes slot 2: offset 0 prev uint128 16 bytes offset 16 next uint128 16 bytes ``` `bookIndex` is the index into the Stablecoin DEX `book_keys` vector. The corresponding `bookKey` is recovered as `book_keys[bookIndex]` when decoding a `V2Order`. ## Orderbook layout Orderbooks keep their existing logical shape and gain a persisted book index in the existing unused bytes of slot `4`: ```text slot 0: offset 0 base address 20 bytes offset 20 unused 12 bytes slot 1: offset 0 quote address 20 bytes offset 20 unused 12 bytes slot 2: bids mapping(int16 => TickLevel) slot 3: asks mapping(int16 => TickLevel) slot 4: offset 0 bestBidTick int16 2 bytes offset 2 bestAskTick int16 2 bytes offset 4 bookKeyIdx uint32 4 bytes offset 8 unused 24 bytes slot 5: bidBitmap mapping(int16 => uint256) slot 6: askBitmap mapping(int16 => uint256) ``` `bookKeyIdx` is the 1-based `book_keys` vector index for this orderbook. A value of `0` means no active index is set, distinguishing the unset state from the active `book_keys[0]` index. This field is packed in slot `4`, so this TIP does not increase the orderbook slot count or move any existing orderbook fields. Starting at activation, newly created orderbooks MUST store `bookKeyIdx = book_keys.length + 1` in slot `4` on the orderbook record before appending the key to `book_keys`. Orderbooks created before activation have `bookKeyIdx = 0` and no active stored index. Pre-activation orderbooks MUST NOT be migrated by linearly scanning `book_keys` onchain. The DEX already has hundreds of thousands of orderbooks on testnet, so an onchain full-array scan cannot fit within the transaction execution budget. Instead, migration tooling MUST derive the index offchain and submit it to the DEX for verification and persistence. The DEX MUST expose: ```solidity function setBookIndex(uint32 index) external; function bookIndexForKey(bytes32 bookKey) external view returns (bool set, uint32 index); function bookKeyForIndex(uint32 index) external view returns (bytes32 bookKey); ``` `setBookIndex` MUST resolve `bookKey = book_keys[index]`, verify that `bookKey` is initialized, and verify that the corresponding orderbook exists. If verification succeeds, it MUST store `bookKeyIdx = index + 1` on the orderbook record. If the orderbook already has `bookKeyIdx != 0`, `setBookIndex` MUST be idempotent when the supplied `index + 1` matches the existing value and MUST NOT rewrite `bookKeyIdx`. If the supplied `index + 1` differs from the existing value, it MUST revert with `IndexAlreadySet` and MUST NOT rewrite `bookKeyIdx`. `bookIndexForKey` is a view helper and MUST NOT scan `book_keys`. It MUST fail with `PairDoesNotExist` if `bookKey` does not identify an initialized orderbook. For an initialized orderbook, it returns `(false, 0)` when `bookKeyIdx == 0`; otherwise it returns `(true, bookKeyIdx - 1)`. `bookKeyForIndex` MUST fail with `PairDoesNotExist` if the requested index is not present in `book_keys`. ## Read behavior All order reads MUST use the order storage abstraction. Starting at activation, reads MUST support the following dispatch: 1. Compute the existing mapping value base slot from `orderId`. 2. Read slot `0`. 3. Decode byte offset `31` as `version`. 4. If `version == 0`, decode the legacy layout. 5. If `version == 1`, decode the TIP-1062 `V1Order` layout. 6. If `version == 2`, decode the `V2Order` layout, recover `bookKey` from `bookIndex`, and synthesize `orderId` from the mapping key. 7. Unknown versions MUST fail. `getOrder(uint128)` keeps returning the existing ABI shape for compatibility. The returned `orderId` is synthesized from the function argument for V1 and V2 layouts. ## Write behavior Before activation, new orders MUST be written using the latest already-active layout. Starting at activation, new orders MUST use the best available layout for the target orderbook: - if the orderbook has `bookKeyIdx != 0`, write `V2Order` using `bookKeyIdx - 1` as `bookIndex` - if the orderbook has `bookKeyIdx == 0`, fall back to writing `V1Order` Mutations to active order fields (`remaining`, `prev`, `next`) MUST go through version-aware order storage methods. Once an orderbook's `bookKeyIdx` becomes nonzero, all later orders for that orderbook MUST use `V2Order`. Existing version `0` and version `1` orders are not migrated in place. Mixed-version linked lists are valid. Updating a neighbor's `prev` or `next` pointer MUST use the neighbor order's version, not the current order's version. ## Interaction with TIP-1056 flip rewrites TIP-1056 rewrites fully filled flip orders in place under the same mapping key. Starting at activation: - user-submitted orders, including `placeFlip` orders, MUST be written as version `2` when the orderbook has `bookKeyIdx != 0` - user-submitted orders, including `placeFlip` orders, MUST fall back to version `1` when the orderbook has `bookKeyIdx == 0` - a version `0` or version `1` flip order that flips after activation MUST be rewritten under the same `orderId` as version `2` when the orderbook has `bookKeyIdx != 0`, or version `1` otherwise - a version `2` flip order that flips MUST remain version `2` A `V2Order` flip rewrite MUST encode the post-flip order state as follows: - slot `0`: preserved `maker`, `metadata` encoding inverted `isBid` and `isFlip = true`, swapped `tick` / `flipTick`, the correct `bookIndex`, zeroed unused bytes, and `version = 2`. For a version `2` flip rewrite, `bookIndex` MUST be preserved from the existing order. For a version `0` or version `1` flip rewrite upgraded to version `2`, `bookIndex` MUST be set from the target orderbook's persisted `bookKeyIdx - 1` after asserting that `bookKeyIdx != 0` and `book_keys[bookKeyIdx - 1] == bookKey`. - slot `1`: preserved `amount` and `remaining = amount` - slot `2`: post-reinsertion `prev` / `next` pointers, after resetting them before insertion - slots used only by the previous version MUST be cleared when upgrading from version `0` or `1` The storage-version upgrade preserves TIP-1056 order identity: the mapping key remains the canonical `orderId`, and the flipped order still receives fresh queue priority at its destination tick. ## Deletion Deleting an order clears the storage slots used by that order's versioned layout. After deletion, `getOrder` continues to report `OrderDoesNotExist` because the decoded maker is zero. # Tooling Operators need an offchain migration workflow that enumerates existing `book_keys`, derives indexes offchain, calls `setBookIndex(index)`, and verifies that each corresponding orderbook has the expected 1-based `bookKeyIdx = index + 1`. The workflow MUST avoid onchain linear scans over `book_keys`. Tools that decode raw DEX storage MUST add support for the 1-based orderbook `bookKeyIdx` field packed in slot `4`, version `2` orders, and resolving `bookIndex` through `book_keys`. Existing tools that consume order events or call `getOrder(uint128)` can continue using the same interface. # Observability No new order lifecycle events are required. Existing DEX order events and `getOrder(uint128)` remain sufficient to observe user-visible order behavior. The migration workflow MUST produce an operator-verifiable report with the total `book_keys` count, migrated orderbook count, and any failed `setBookIndex` calls. This report tracks V2 coverage, but activation does not require every pre-activation orderbook to be migrated because unmigrated books fall back to `V1Order` writes. # Invariants - Order identity is stable: the `orders` mapping slot and key type are unchanged, and the mapping key remains the canonical `orderId` for every order layout. - Versioned decoding is stable: existing version `0` and version `1` bytes keep their existing meaning, and a stored order's version discriminator is the only source of truth for its layout. - Book indexes are stable references: `book_keys` is append-only, and any nonzero persisted orderbook `bookKeyIdx` or `V2Order.bookIndex` MUST resolve to the orderbook's canonical `bookKey`. - Index association is monotonic: an orderbook may move from `bookKeyIdx == 0` to `bookKeyIdx != 0`, but once indexed its `bookKeyIdx` MUST NOT change to a different value. - V2 writes are gated by index availability: an orderbook without an active index MUST continue to use the latest non-indexed order layout for new writes. - Mixed-version linked lists remain valid: `prev` and `next` pointers always reference canonical order IDs, and pointer updates are encoded according to the target order's own storage version. - External order reads remain logically stable: `getOrder(uint128)` returns the same ABI shape and logical fields regardless of whether the underlying order is version `0`, `1`, or `2`. ## Backwards Compatibility Existing onchain orders remain readable and cancellable. Existing clients using `getOrder(uint128)` continue to receive the same return fields. Indexers that reconstruct orders solely from events are unaffected by the storage layout. Tools that read raw storage must add V2-aware decoding.