Walker Lib

The Walker lib uses a segment tree to manage fees and liquidity over each node.

Each node's key tells us the liquidity range a given node owns. The keys range is scaled up by the tick spacing and then offset so the center of the tree range matches with tick zero in the pool.

Modify

When modifying liquidity, we walk down first to distribute unpaid and unclaimed fees, and then we walk up to create new unclaim/unpaids, charge accurate fee rates, and update liquidity.

Fee Down

When modifying fees down, we are only concerned about the unclaimed and unpaid fees. These are fees that can be claimed by maker liquidity and paid by taker liquidiy respectively.

On the way down we track all the liquidity values in parent nodes so that at any moment during our walk down, we can say exactly how much liquidity is in the current node's range. We call this column liquidity. If you imagine each level of the tree spanning the entire tick space, and each node in a level spanning an equal portion of that tick space, which each level below spanning the space using twice as many ranges each half as wide then the "column" of a node is all ranges above and below it covering the same range. In other words it's simply the amount of liquidity in a given range as contributed be all nodes in total. We will use this prefix on the way up.

On the way down however, we are just concerned about the subtree liquidity among a node's two children. This tells us how to split the unclaimed/unpaid fees between them. The node itself takes a pro-rata split of the unclaimed/unpaid according to this entire subtree's maker/taker liqs. Then it calculates weights for each children based on their subtree maker/taker liqs. The split rate is used to calculate how the unclaim/unpaid are split into each node and then we recurse.

This is called "distributing unclaimed fees" and this only happens when a node is walked over. So a node can be accumulating a large amount of unclaimed fees over a long period of time, which is only settled once it is actually walked over. Fortunately to modifying liquidity or claim fees from nodes below it, that node must first be walked over.

Toy Distribution Example

Here's a toy example with 3 nodes covering 2 ticks.

[0,2] has 100 liq (per tick). [0, 1] has 100 liq, and borrows 100 with taker liq. [1, 2] has no liq and no borrows.

From subtree values, the root node sees 300 total liq, and 100 borrows, so it charges say 15% for 33% utilization. It says anyone in this subtree borrowing must pay 15%. It sees it has no borrows, so it doesn't charge anything to its borrowers. It sees it has maker liq, so it says 15% of the 100 borrow (15) gets paid pro-rata to my makers, so it gets 10 fees (200 / 300 * 15). Then it splits the rest (5) to its children, which it sees has no borrows on the right, so it gives it all as unclaimed to the left, and all of the 15 charged is given as unpaid to the left and 5 is given as unclaimed to the left.

This distribution might seem unfair here, but in practice the borrow distributions between adjacent nodes will be relatively even since otherwise there is an arbitrage.

Fee Up

When we walk up, the first thing we do is calculate fees since we want to do that before modifying liquidity values. Here we use the prefix and unwind the prefix as we walk up.

Using the prefix and the subtree values stored in the node, we can calculate the column's maker and taker liquidity values and thus its taker utilization. This allows us to calculate the fee rate to charge all takers in this column. We do this calculation at the deepest node we'll visit in a subtree during our walk, and this happens when a node is marked "visit" by RouteLib. This calculation gives us the "fair" rate of borrowing and we charge those fees to the current node. Since this fee rate applies to all liq in its column, we charge it to our subtree and distribute it as unclaim/unpaid fees to our children, and then as we walk up we propogate up that fee rate, joining it with our sibling node's fee rate to get our parent node's fair fee rate, ultimately reaching the root node.

Besides the taker's fee rate calculation, we also need to charge takers the underlying swap fees of the maker to guarantee all maker liquidity earns the same amount as they would in the base AMM, borrowed or not. We simply track inside fee rates (see Uniswap documentation) to calculate this.

Liquidity Up

As we walk up, we also modify the liquidity (maker/taker) at each node. By doing this just as the visit nodes, we'll give users a liquidity range that is equal to their desired overall liquidity range.

Before modifying liquidity however, we must first compound if necessary. The amount of fees available to compound Maker liq is calculated and the node grows its maker liq balance accordingly.

After modifying liquidity, it's possible that a node's liquidity is insufficient for the taker borrows, but it's possible an ancestor node has sufficient liquidity. So the solving step will borrow liquidity from a parent node, split it into our own node's liquidity and our sibling's liquidity, and satisfy the taker borrow. So the node's overall net liquidity is always greater than or equal to zero.

View Walker

The view walker is used to calculate how much a position is worth. It basically does all the fee calculation steps without any state modification and skips the liquidity modification step.

Pool Walker

The pool walker is what finalizes any liquidity changes made by the Modify walk. It looks at which nodes are marked dirty, and updates liquidity values in the actual pool accordingly.

Potential Confusion

The word borrow is unfortunately heavily overloaded in our codebase. It may refer to:

• Taker liquidity, since that borrows liquidity from makers, but we avoid using it as such in code. However in comments we may talk about how it borrows liquidity.

• Token borrows. node.liq.subtreeBorrowX for example refers to the amount of token X that is borrowed by Taker liquidity from the subtree.

• Maker liquidity borrowed from an ancestor. When solving a node's liquidity, liquidity lent by the parent is stored as a borrow in the child node.

Token0 and token1 are interchangeably used as tokenX and tokenY. 0,1 is uniswaps convention, but our notes use X,Y. We use both in our codebase, using 0,1 more when we interact with Uniswap and X,Y in our own accounting.