EPIC: Sumtree/LOOT

[AlpinYukseloglu]

Overview

This Epic covers the open fronts related to our sumtree-based orderbook implementation.

Sumtree

• [Sumtree]: High level sumtree spec #46
• [Sumtree]: Implement Tree Structure and State #54
• [Sumtree]: Consider using larger capacity type than u32 to track sumtree values #63
• [Sumtree]: Sumtree Insertion  #55
• [Sumtree]: Non-happy-path sumtree tests #57
• [Sumtree]: Node Deletion #58
• [Sumtree]: Create tick struct with all important values set up #51
• [Sumtree]: Rebalancing #60
• [Sumtree]: Change sumtree to operate on Decimal256 instead of u128 #74
• [Sumtree]: Implement prefix sum query for sumtree #76
• [Sumtree]: Implement fuzz tests for core sumtree logic #96

Core Orderbook

• [Sumtree]: Set up sumtree/LOOT contract & directory #45
• [Sumtree]: Limit Order Placing #66
• [Sumtree]: Limit Order Cancelling #67
• [Sumtree]: Implement market order & tick filling logic #80
• [Sumtree]: Make amount_to_value take in rounding direction and fix input consumption rounding #85
• [Sumtree]: Add second set of tick state values to handle order direction #88
• [Sumtree]: Implement tick syncing logic #77
• [Sumtree]: Update Tick pointers during Market Order filling logic #101
• [Sumtree]: Fix tick sync to work for both order directions #108
• [Sumtree]: Implement order claiming logic #78
• [Sumtree]: Remove auto triggering of market orders in place_limit #117
• [Sumtree]: Allow for cancellation of partially filled orders #75

Peripheral Features

• [Sumtree]: Spec out auto claiming #65
• [Sumtree]: Implement auto claiming #114
• [Sumtree]: Add 1% cap to claim bounty #128
• [Sumtree]: Create message that allows for batch auto claiming #115
• [punted][Sumtree]: Consider implementing auto cancel bounties #124
• [Sumtree]: Determine specifics around contract admin and upgradability #138
• [Sumtree]: Implement contract admin setup #140
• [Sumtree]: Implement moderator for freeze ability #141
• [Sumtree]: Implement active/inactive switch for contract #111
• [Sumtree]: Implement maker fee switch #134
• [Sumtree]: Implement SudoMsg for market order up to a tick #170
• [Sumtree]: Add query for mapping address to orders #173
• [Sumtree]: Implement maker fee query #178

CW Pool and SQS Integration

• [Sumtree]: Wire up high level functions into execute #98
• [Sumtree]: Adapt contract to conform to CW pool interface #71
  • [Sumtree]: Implement CW Pool Swap Interface #131
  • [Sumtree]: Implement CW Pool Create Pool Interface #132
• [Sumtree]: Implement CW pool queries #136
  • [Sumtree]: CosmWasm Pool Query Interface Implementation #135
• [Sumtree]: Track total bid and ask liquidity in state for queries #139
• [Sumtree]: Ensure market orders only work through CW pool interface #120
• [Sumtree]: Implement additional GetAllTicks query for SQS #125
• [Sumtree]: Set up script for setting up contracts with in-place testnet #149
• [Sumtree][SQS]: Set up and debug CW pool and SQS ingestion so SQS picks up new orderbook pools #169
• [Sumtree][SQS]: Integrate orderbook CW pool into SQS and test manually #150
• [Sumtree]: Spec out ingesting orderbook data into SQS #152
• [Sumtree]: Spec SQS market order implementation #153
• [Sumtree][SQS]: Test custom SQS integration with in-place testnet #154
• [Sumtree]: Explore how much market order logic can be exported for SQS #126

Testing and QA Related Tasks

• [Sumtree][minor]: Return error at end of insertion logic #92
• [Sumtree]: Cleanup Insertion Logic #79
• [Sumtree]: Make run_market_order return consumed input amount as well #86
• [Sumtree]: Implement more complex tick sync tests #104
• [Sumtree]: Ensure tree insertion boundary checks are correct #91
• [Sumtree]: Improve readability of sumtree insertion logic by abstracting out min/max range logic #93
• [Sumtree][bug]: Market orders do not properly terminate due to rounding #127
• [Sumtree]: Return error if market order is not fully filled #118
• [Sumtree]: Handle claim overflows by lowering max spot price drastically #123
• [Sumtree]: Create invariant check that asserts sibling nodes do not overlap #94
• [Sumtree]: Test edge case to ensure safety of mutating internal node ranges #62
• [Sumtree]: Add tests for multiple trees on independent ticks/books #64
• [Sumtree]: Investigate and clear up range bounds for nodes #68
• [Sumtree]: Test edge case of insertions below left child range and above right child range #69
• [Sumtree]: Split function should have more explicit ordering logic #70
• [Sumtree]: Consider adding scaling factors #52
• [Sumtree]: Explore solutions to precision issues #53
• [Sumtree]: Consider Tick State Causing Overflow #99
• [Sumtree]: Test for moving tick sumtree integrity #103

Pushed to V2

• [Sumtree]: Explore implementing tick batching algorithm for MVP #84
• [Sumtree]: Tick State Cleanup #160