[DeFi][FIN-13] Authenticated sparse tick index with complete next-boundary proofs #63

Umbrella: #43 · Proposed application capability · FIN work-item FIN-13. No milestone, implementer, reviewer or release approval is implied.

What problem does this solve? — In plain English

A trading client may supply the next ticks to cross, but the verifier must prove none were skipped. A well-formed list alone does not prove completeness.

Visual explanation

flowchart LR
A["Committed tick root and pages"] --> B["Builder supplies bounded path"]
B --> C{"Prove next tick and absence in between"}
A --> C
C -- Invalid --> X["Reject"]
C -- Valid --> D["Verify state transition + new root"]

Primary implementation layer: Persistent on-chain protocol data structures.

Dependencies / start conditions: FIN-11 state identity; closed #13 authenticated commitment principles and #24 CKB views; #49 only for a proven general selection gap.

Detailed design and security review

Why ordinary membership checks are insufficient

A builder may give valid pages for ticks 100 and 120 while omitting an initialized tick 110. To prevent a price jump across hidden liquidity, the verifier needs both membership for supplied ticks and non-membership of any nearer initialized tick. The commitment must therefore authenticate complete bounded intervals, not only individual entries.

State design candidates and selection gate

Evaluate an authenticated sparse bitmap/page index or an ordered authenticated set with equivalent absence proofs. Freeze tick identity, key ordering, page width, root/hash domain, the representation of empty ranges, neighbour lookup semantics and treatment of the final tick removed from a page. Compare witness and on-chain cost for sparse/dense states, then choose one before treating positive lowering as accepted.

The pool must bind the index root and actual state-version; each touched page must have authentic input/output correspondence and exactly one permitted update. Define how a transaction proves all pages and tick changes relevant to the bounded path. #47 temporary Map/Set does not supply persistent index storage. #49 foreign observations do not grant lifecycle authority.

Implementation phases

1. Single-page insertion, deletion and exact next/previous lookup with independent full-map oracle.
2. Adjacent-page lookup including authenticated empty-page and no-nearer-tick evidence.
3. Bounded multi-page traversal with signed liquidity-net updates, root update and unrelated page preservation.
4. Competing-root/reorg/stale state handling through current CKB inputs and generated builder rebuild.

Mandatory negative evidence

Scaling constraint

Freeze bounds per transaction: touched pages, crossed ticks, proof bytes, index lookups and VM cycles. Do not implement a hidden cap on all positions or all tick history. Publish exact state schema/root vectors, worst-case transaction capacity and CKB-VM evidence.

Security flow

flowchart TD
    R["Committed tick root"] --> P["Authenticate page proof and neighbours"]
    P --> A{"Next tick complete?"}
    A -- No --> X["Reject omitted or forged boundary"]
    A -- Yes --> T["Update tick and liquidity"]
    T --> C["Verify all successor pages/root"]

Source-contract and release discipline

• Reuse the existing CellScript transaction-view, resource-lifecycle, exact Script-handle, ProtocolBundle and generated-builder contracts. Do not invent a finance-specific parser/IR/codegen branch, implicit cross-Script call or a second transaction serializer.
• Freeze the semantic support matrix, named implementation owner, explicit reviewer/waiver disposition, transaction and byte budgets before acceptance. An arbitrary unchecked witness is not execution evidence.
• Full-transaction CKB-VM adversarial negatives must fail at the intended enforcing Script with otherwise-valid signatures and correctly constructed participating groups. Maintain source/ELF/CellDep/transaction/node identities, independent reference vectors, full gates and disclosed unknown outcomes.
• These issues do not assert public deployment or a new compiler release.

Implementation scope

• Define authenticated sparse tick/page or bitmap representation with canonical tick ordering, next/previous lookup, page ownership and state root/version.
• Prove membership and absence between boundaries; bind tick init/delete/gross/net changes and every modified page to one real predecessor/successor state.
• Bound per-transaction pages/tick steps/proof bytes and runtime without imposing a hidden global maximum on lifetime positions.

Acceptance checklist

• Insertion, deletion and cross-page next/previous search agree with an independent full index for maximum supported bounds.
• Skipped middle tick, forged empty interval/page, duplicate identity, stale roots, reordered proof and mismatched successor root reject.
• Sparse/dense/adversarial layouts demonstrate exact CKB-VM, all required Script groups and reproducible resource/capacity measurements.
• No use of invocation-local [0.33][Runtime] Add bounded allocation-backed value collections and deterministic Map/Set #47 Map/Set is presented as durable authenticated tick storage.

Explicit boundary: Persistent tick structure belongs to protocol state; missing general selection semantics require a separate narrowly scoped runtime issue.

General scope and evidence gate

• This is application/protocol/SDK work, not a new CellScript grammar feature, VM opcode or finance-name-specific code generation.
• Before acceptance: freeze semantic contract, threat model, limits, role/authority boundary and accountable implementer/review disposition (unassigned initially).
• Run independently modelled positives and targeted adversarial cases in actual CKB-VM with all required Script groups, pinned sources/artifact/CellDep/transaction identities and the applicable dev/CI/backend gates. Distinguish node and public deployment evidence.
• A demonstrably missing business-neutral language capability needs a separate general-purpose issue and independent-checker/ABI/diagnostic acceptance. Opening this issue is not release authorisation.

Verified GitHub dependency links

Core: #61, closed #13/#24. Optional demonstrated generic selection gap: #49. Next: #64, #65.

These are explicit planning links, not evidence of completed implementation or automatic GitHub blocking relationships. See umbrella #43 for programme stages.

Verified dependencies and implementation sequencing

Hard prerequisites: #61 pool/root identity; closed #13 committed-state principles and #24 typed views.

Unblocks: #64 positions, #65 cross-tick swaps.

Conditional general-language work: #49 only upon a demonstrated general heterogeneous-selection gap. #47 is temporary local collection memory, not a tick database.

Status: These are explanatory GitHub cross-links and do not set native GitHub blocking relationships, authorise a compiler change, or certify dependent implementation.