Incremental Swaps

[kayabaNerve]

In low-depth pools, large swaps can incur significant slippage. One solution is to split the swap into a series of ticks, executed however often, so that each individual tick is small compared to the pool depth.

The naive solution for this has O(n) complexity. Simply push the swap to tick into a queue, and at the end of each block, tick each swap in the queue. This is unacceptable.

We can create an unbalanced binary tree of all swaps, where each branch stores:

• The sum amount of all children
• The amount already successfully swapped by that node (inclusive to all children)
• The effective slippage allowance for all children
• The slippage rate executed at thus far

Insertion of a new swap is a two-step process:

1. Find the position in the tree to insert into (leftmost being most slippage tolerant, rightmost being least slippage tolerant)
2. Push onto a queue for block current + n

At the start of each block, we'd find the right-most node able to be swapped without exceeding the effective slippage allowance. This gives us a logarithmic-size list of swappable nodes. We'd then swap each node in reverse order. This means no nodes have their slippage allowance exceeded. This does give the best prices to the node's with the least tolerance for slippage, yet they're the least likely to be executed. The other option would be to swap all nodes at once, giving a fair price (with less complexity on our end) yet including less nodes. Each node included and their parents would then have its amount successfully swapped incremented.

For a binary tree of 256 leaves, where leaf 255 (0-indexed) is the right-most swappable node, the path to the right-most swappable node would be 128 .. 256, 192 .. 256, 224 .. 256, 240 .. 256, 248 .. 256, 252 .. 256, 254 .. 256, 255. We'd execute ticks for 0 .. 128, 128 .. 192, 192 .. 224, 224 .. 240, 240 .. 248, 248 .. 252, 252 .. 254, and 255 (the last element in the path and the neighbors of all prior path elements). We'd then update all nodes which had ticks executed and parents 254 .. 256, 252 .. 256, 248 .. 256, 240 .. 256, 224 .. 256, 192 .. 256, 128 .. 256 (making the total amount of updated nodes 2 log(n)).

We'd also drain the queue for the current block. All swaps present in the queue would be considered completed, regardless of how many ticks successfully executed, and removed from the tree. When a swap is removed, it is greedy and takes as much of the amount successfully swapped from all parents as it can (and should).

This achieves O(log n) complexity to execute all active swaps with O(log n) insertion and O(log n) removal. The use of an unbalanced binary tree does risk griefing with tree extension attacks however (causing an O(log n) path to be O(n)). This still needs to be solved.

[kayabaNerve]

Bucketing slippage into preset options may be the best solution to the DoS.

[kayabaNerve]

A binary tree, with fixed slippage, would simply do a right-most insertion with left-most removal. That's a bit wonky to manage yet can reasonably be done. We wouldn't rebalance, just set more and more left nodes to None.

We can do a sparse binary tree of binary trees? One binary tree per slippage allowance, with a sparse binary tree of all possible slippage allowances? If we define slippage in hundredths of a percent, the sparse tree would only have the overhead for 2**14. This would never need to be rebalanced as all leafs would already be in their predeclared position.

[kayabaNerve]

If we use a sparse binary tree for the various slippage parameters, we don't need a tree of trees. The leaves of the sparse tree can simply be the summed swaps. While the summed swaps may not be wholly executable, we don't need to grain to the individually executable swap. We can just grain to the executable amount and only swap that partial amount.