Sum Trees

Advanced Order Cancellation System Using Segment Trees and Sum Trees in DeFi Trading

In the ever-evolving landscape of Decentralized Finance (DeFi), the ability to manage a high volume of order cancellations efficiently is crucial for maintaining the integrity and fluidity of trading platforms. Our protocol introduces a groundbreaking solution to this challenge. By innovatively utilizing segmented segment trees and sum trees, we dramatically increase the cancellation capacity for each price point in our order book. This introduction outlines how our system revolutionizes cancellation management, ensuring scalability and efficiency in a high-volume trading environment, setting a new standard in the DeFi space.

Sequential Cancellation Storage and Tree Segmentation

Initial Cancellation Storage in Tree #1

• Our system begins by storing cancelled orders in Tree #1, with a specific capacity of 32,768 cancellations.

• This approach aligns with the operational and gas fee efficiencies within Ethereum's smart contract framework.

• Cancelled orders are sequentially recorded in Tree #1 until it reaches its full capacity.

In a bustling DeFi trading environment, where tens of thousands of daily orders are the norm, the capacity to handle only 32,768 cancellations per price point is a significant limitation. This constraint is not viable for a high-volume, production environment. Our protocol revolutionizes this aspect by scaling the cancellation capacity to over a billion per price point. This groundbreaking enhancement paves the way for an infinitely scalable, fully on-chain order book, a milestone in DeFi trading platforms.

Transition to Additional Cancellation Trees and Sum Tree Introduction

• Once Tree #1 is filled, the system transitions to Tree #2 to continue the storage of additional cancellations.

• Simultaneously, the sum tree is introduced, aggregating cumulative cancellation values across all segmented trees.

While adding new trees for every 32,768 cancellations effectively solves the storage issue, it introduces a challenge in efficiently reading data. Without an additional system, accessing cancellation data would require iterating through each tree, increasing complexity with each new tree. For instance, with 2 trees, the complexity is O(2log n), and with 10 trees, it becomes O(10log n). Hence, this solution alone isn't sufficient for maintaining efficiency in data retrieval.

Total Cancellation Capacity Per Price Point

• Each price point in our system is allocated 32,768 cancellation trees, plus an additional sum tree, amounting to a total of 32,769 trees per price point.

• The total storage capacity per price point is therefore 32,768^2, which is 1,073,741,824 cancellations.

• This immense capacity significantly elevates our protocol's ability to manage a large volume of cancellations for each price point.

With our advanced structure, we significantly expand the cancellation capacity per price point to 1,073,741,824, while efficiently managing the complexity of sum range queries. Initially, our system maintains an O(log n) complexity for these queries. However, as we surpass 32,768 cancellations and begin utilizing multiple segment trees, the complexity marginally increases to O(2log n). This increase is a minor trade-off considering the vast improvement in handling cancellations. By iterating through the specific order's tree, like Tree #32,768, and the sum tree for aggregate calculations, we ensure scalability and efficiency in a high-volume trading environment.

Efficient Total Cancellation Computation

• Each segmented tree holds the data for cancelled orders, while the sum tree provides an aggregate total.

• This architecture enables quick and efficient computation of the total sum of cancellations below any specific order.

Scalability and Complexity Management

• As the number of cancellations grows, additional segmented trees are added, and the sum tree is dynamically updated.

• This methodology ensures the system remains scalable and maintains complexity management efficiently, even with a substantial increase in cancellations.

Practical Application and Examples

To illustrate the system's functionality, consider a scenario in the ETH/USDT trading pair. Imagine three orders are placed, each for 100 USDT at a price point of 2,400 USDT/ETH. These orders are stored sequentially: the first order in the range 0-100, the second from 100-200, and the third from 200-300. If the second order is canceled, it impacts only subsequent orders, like the third one.

When assessing if the third order is filled, we check all cancellations below this order in the cancellation tree. In this example, the cancellation value is 100 USDT, signifying that only one order (the second one) was canceled. To determine the actual fill point for a price point, say 2,400 USDT/ETH, we add the value of cancellations to the order book's fill point. For instance, a 150 USDT market order would fully fill the first order. Ordinarily, this would also partially fill the second order, but since it's canceled, the fill point moves to 250 USDT, indicating that the first order is fully filled, the second is canceled, and the third is filled 50%.

Scaling and Implications for the Ethereum Blockchain

Our system’s architecture allows us to handle up to 1,073,741,824 cancellations for each price point in the order book. This capacity is not just per trading pair but extends to each individual price point, such as different prices within the ETH/USDT pair. Given the Ethereum blockchain's current average of around 1 million transactions per day, reaching this cancellation limit is highly improbable, ensuring robustness and scalability for our protocol without incurring prohibitive gas fees for users.