KaRoot

On-chain orderbooks are not widely used as most matching algorithms have linear matching, which makes it almost impossible to execute onchain. For this reason we implement radix trie in cairo, that can be used to efficiently implement on-chain matching with logarithmic complexity.

Binary radix trie is constructed separately for bid and ask orders. Key is constructed as a combination of price and order number, which helps to maintain price-time priority. Each leaf of the trie is an order, each node contains sum_value and sum_coins of its children. In order to acknowledge actual distribution of orders, we additionally optimize rightmost-branch of the trie, so that it keeps only sums of left children. This allows us to skip going up across the rightmost branch of the trie each time we change an order on the rightmost branch.