At the core of this approach is a three-level binary tree designed to store 24-bit IDs. Each level of the tree caters to 8 bits of the ID, with the entire structure allowing for efficient categorization and retrieval of data. Our smart contracts use this tree to store whether orders exist against a price point (ID). It is important to note that we use the tree to only identify whether an order exists at a price point and not to store the actual orders. The actual orders are stored in a doubly linked list(insertions and deletions can be done in constant gas).

• Level 0 (bytes32): Represents the most significant 8 bits of the IDs. Each bit in this level can indicate the presence of IDs in the corresponding 8-bit segment of the ID space.
• Level 1 (mapping(bytes32) => bytes32): Represents the middle 8 bits of the IDs. It is structured as a mapping from a segment identified at Level 0 to a bytes32 value, where each bit signifies the presence of IDs within that segment.
• Level 2 (mapping(bytes32) => bytes32): Represents the least significant 8 bits of the IDs, directly storing the presence of specific IDs as bits within a bytes32 value.

To understand how we achieve placing orders in constant gas it is important to understand how we can add an ID to the tree in a constant number of operations. As mentioned earlier, each level of the tree corresponds to an 8-bit segment of the ID. In other words, level0 has no key, the key for level1 is the first 8 bits and the key for level2 is the first 16 bits.

1. First we right shift the identifier by 8 bits, leaving the 16 most significant bits(MSB). This is the key for level2. Suppose the 8 LSBs are 10000001, which is 129 in the decimal system, then we flip the 130th LSB in the value of the mapping to one(if it is not already flipped), signifying that $ABC10000001$ exists. ABC is the 16 MSB which is the key.
2. Then we right-shift the identifier by 16 bits, leaving the 8 MSBs. This is the key for level1. Similar to the previous step we flip a bit in the value based on the middle 8 bits of the uin24 identifier.
3. Similarly we also flip a bit in level0 based on the 8 MSBs.

This is how we can add a price point to the orderbook in at most 3 SSTORE operations. After adding the price point, we store the actual order in a doubly linked list by performing additional SSTOREs.

Navigating the Tree

The tree structure supports efficient traversal to find the largest and smallest ID:

• Finding the First Right ID: To find the first ID in the tree that is less than or equal to a given ID, the process starts at the root (Level 0) and navigates down. It uses the right shift to partially decode the ID's position in the tree and bitwise OR operations to update and check the presence of IDs at each level. This method ensures a direct path is followed from the root to the relevant leaf, minimising the operations needed. This is used to find the largest ID.
• Finding the First Left ID: Conversely, to find the first ID that is greater than or equal to a given ID, the traversal starts similarly at the root. However, the process looks to the left, employing bitwise AND operations in conjunction with left shifts to ensure that only the relevant segments of the tree are explored. This is used to find the smallest ID.

This allows us to find matches for taker orders in constant gas.