Milestone 2. Second Swap

Introduction

Output Amount Calculation

scan page for demonstration or create with LaTeX

Math in Solidity

Tick Bitmap Index

TickBitmap Contract

contract UniswapV3Pool {
    using TickBitmap for mapping(int16 => uint256);
    mapping(int16 => uint256) public tickBitmap;
    ...
}

function position(int24 tick) private pure returns (int16 wordPos, uint8 bitPos) {
    wordPos = int16(tick >> 8);
    bitPos = uint8(uint24(tick % 256));
}

That is: we find its word position and then its bit in this word. >> 8 is identical to integer division by 256. So, word position is the integer part of a tick index divided by 256, and bit position is the remainder.

Why int16 wordPos ? → we shift 8 bits to the right so 24 bits max - 8 = 16 max + int24 means 23 bits and 1 signed bit type(int16).min = -32768 type(int16).max = 32767

Why uint8 bitPos ? → bitPos between 0 and 255

Why uint24 then uint8 ? → I think best to do 1. int to uint 2. convert uint24 to uint8, We can do directly uint8 but not recommended I think

Flipping Flags

function flipTick(
    mapping(int16 => uint256) storage self,
    int24 tick,
    int24 tickSpacing
) internal {
    require(tick % tickSpacing == 0); // ensure that the tick is spaced
    (int16 wordPos, uint8 bitPos) = position(tick / tickSpacing);
    uint256 mask = 1 << bitPos;
    // when tick not initialized 0^1=1
		// when tick  initialized 1^1=0
    self[wordPos] ^= mask;
}

Reminder

• F = 0
• T = 1

Finding Next Tick

Why ?

/// @notice Returns the next initialized tick contained in the same word (or adjacent word) as the tick that is either /// to the left (less than or equal to) or right (greater than) of the given tick

From my understanding (after the milestone 3. - cross swap):

    if (state.sqrtPriceX96 == step.sqrtPriceNextX96) {
                    if (step.initialized) {
                        int128 liquidityDelta = ticks.cross(step.nextTick);

                        if (zeroForOne) liquidityDelta = -liquidityDelta;

                        state.liquidity = LiquidityMath.addLiquidity(
                            state.liquidity,
                            liquidityDelta
                        );

                        if (state.liquidity == 0) revert NotEnoughLiquidity();
                    }

                    state.tick = zeroForOne ? step.nextTick - 1 : step.nextTick;
                } else {
                    state.tick = TickMath.getTickAtSqrtRatio(state.sqrtPriceX96);
                }

When we cross the lower tick of a price range:

• Adding Liquidity: When crossing the lower tick from left to right, we add liquidity. This means that the lower tick contains the liquidity for the price range.
• Finding leastSignificantBit: When searching for the leastSignificantBit, we can include the lower tick, as it contains the liquidity.

If our current tick is the lower tick of the price range and we’re selling (zeroForOne=true):

• Using Remaining Liquidity: After using the remaining liquidity, we cross the tick and then set the next tick.

This logic is illustrated in the following Solidity code:

if (state.sqrtPriceX96 == step.sqrtPriceNextX96) {
    if (step.initialized) {
        int128 liquidityDelta = ticks.cross(step.nextTick);

        if (zeroForOne) liquidityDelta = -liquidityDelta;

        state.liquidity = LiquidityMath.addLiquidity(
            state.liquidity,
            liquidityDelta
        );

        if (state.liquidity == 0) revert NotEnoughLiquidity();
    }

    state.tick = zeroForOne ? step.nextTick - 1 : step.nextTick;
} else {
    state.tick = TickMath.getTickAtSqrtRatio(state.sqrtPriceX96);
}

• step.nextTick - 1: This ensures we are one tick lower than the lower tick of the price range. Thus, we finally cross the lower tick after using the remaining liquidity.

from https://uniswapv3book.com/milestone_3/cross-tick-swaps.html

When updating state.tick, if the price moves down (zeroForOne is true), we need to subtract 1 to step out of the price range. When moving up (zeroForOne is false), the current tick is always excluded in TickBitmap.nextInitializedTickWithinOneWord.

BitMap library

I’m using a uint256 as an example

• mostSignificantBit :

See like if we divised uint 256 (uint256 x) into two uint 128 → uint128 (represent 255 - 128) / uint128 (represent 127 - 0)

Example :

• if x > 2^128 → we focus on uint128 (represent 255 - 128)

• if x > 2^64 → we focus on uint128 (represent 255 - 192)

• ….

• if x < 2^128 → we focus on uint128 (represent 127 - 0)

• if x < 2^64 → we focus on uint128 (represent 63 - 0)

• ….

• leastSignificantBit :

See like if we divised uint 256 (uint256 x) into two uint 128 → uint128 (represent 255 - 128) / uint128 (represent 127 - 0)

Example :

• x & type(uint128).max operator will only keep the bits between 127 - 0

• if x & type(uint128).max > 0 → we focus on uint128 (represent 127 - 0)

• if x & type(uint64).max > 0 → we focus on uint128 (represent 64 - 0)

• ….

• if x & type(uint128).max = 0 → we focus on uint128 (represent 255 - 128)

• if x & type(uint64).max = 0 → we focus on uint128 (represent 255 - 192)

• ….

What returns nextInitializedTickWithinOneWord ?

First of all, we return the next initialized tick and not his bitPos

(example don’t care about value) tick : 676 → word 1 and bitPos 27 It mean that tick 686 → word 1 and bitPos 37 (bitPos 0 is at the right of the uint256)

Be careful

Be aware that, in the code, the direction is flipped: when buying token x, we search for initialized ticks to the left of the current; when selling token x, we search ticks to the right. But this is only true within a word; words are ordered from left to right.

bitPos start from the right (bitPos : 0) to the left (bitPos : 255)

The lowest tick of the word is on the right.

The highest tick of the word is on the left.

• if(lte)

  • we use BitMath.mostSignificantBit to have the largest tick between current tick and bitPos 0, in order to have the closest to our current tick

  if (lte) {
      (int16 wordPos, uint8 bitPos) = position(compressed);
      uint256 mask = (1 << bitPos) - 1 + (1 << bitPos);
      uint256 masked = self[wordPos] & mask;
      ...
  

  • self[wordPos] = 01001011 (binary representation)
  • bitPos = 2 (starting from the left, so bit 7 is the first bit on the left)
  • 1 << bitPos shifts the number 1 to the left by 3 bits: 00000100
  • (1 << bitPos) - 1 gives us: 00001000 - 1 = 00000011
  • Adding (1 << bitPos) back: 00000111 + 00001000 = 00000111
  • masked = self[wordPos] & mask; ⇒ 00000011

  next = initialized
      ? (compressed - int24(uint24(bitPos - BitMath.mostSignificantBit(masked)))) * tickSpacing
      : (compressed - int24(uint24(bitPos))) * tickSpacing;
  

  • BitMath.mostSignificantBit(masked) = 1
  • means that we need to sub 2 to go to the next initialized tick
  • * tickSpacing because at the beginning

  int24 compressed = tick / tickSpacing;
  

  (compressed - int24(uint24(bitPos))) * tickSpacing;
  

  • return the lowest tick (at bisPos 0) of the word - it can be initialized or not

• else

    ...
} else {
    (int16 wordPos, uint8 bitPos) = position(compressed + 1);
    uint256 mask = ~((1 << bitPos) - 1);
    uint256 masked = self[wordPos] & mask;
    ...

    ...
    initialized = masked != 0;
    // overflow/underflow is possible, but prevented externally by limiting both tickSpacing and tick
    next = initialized
        ? (compressed + 1 + int24(uint24((BitMath.leastSignificantBit(masked) - bitPos)))) * tickSpacing
        : (compressed + 1 + int24(uint24((type(uint8).max - bitPos)))) * tickSpacing;

Don’t forget that bitPos is for compress+1 and not compress

example :

• (BitMath.leastSignificantBit(masked) - bitPos) = 254 - 251 (bitPos of compres +1) = 3 but in reality bitPos of compress is 250 so we need to add +1
• not initialized
  • it means that we return the lowest tick of the word n+1
  • uint24((type(uint8).max = 256 - bitPos (compress+1) = 251
  • we move to 5, but with compress the bitPos of next will be 255 - that’s why +1 in order to go to the next word.

Generalized Minting

Token Amounts Calculation

The first step is to sort the prices to ensure we don’t underflow when subtracting. Next, we convert liquidity to a Q96.64 number by multiplying it by 2**96. Next, according to the formula, we multiply it by the difference of the prices and divide it by the bigger price. Then, we divide by the smaller price. The order of division doesn’t matter, but we want to have two divisions because the multiplication of prices can overflow.

Generalized Swapping

You can think of a swap as of filling of an order: a user submits an order to buy a specified amount of tokens from a pool. The pool will use the available liquidity to “convert” the input amount into an output amount of the other token. If there’s not enough liquidity in the current price range, it’ll try to find liquidity in other price ranges (using the function we implemented in the previous chapter).

SwapState maintains the current swap’s state. amountSpecifiedRemaining tracks the remaining amount of tokens that need to be bought by the pool. When it’s zero, the swap is done. amountCalculated is the out amount calculated by the contract. sqrtPriceX96 and tick are the new current price and tick after a swap is done.

StepState maintains the current swap step’s state. This structure tracks the state of one iteration of an “order filling”. sqrtPriceStartX96 tracks the price the iteration begins with. nextTick is the next initialized tick that will provide liquidity for the swap and sqrtPriceNextX96 is the price at the next tick. amountIn and amountOut are amounts that can be provided by the liquidity of the current iteration.

SwapMath Contract

function getNextSqrtPriceFromAmount0RoundingUp(
        uint160 sqrtPriceX96,
        uint128 liquidity,
        uint256 amountIn
    ) internal pure returns (uint160) {
        uint256 numerator = uint256(liquidity) << FixedPoint96.RESOLUTION;
        uint256 product = amountIn * sqrtPriceX96; //it can overflow

        if (product / amountIn == sqrtPriceX96) { // check no overflow
            uint256 denominator = numerator + product;
            if (denominator >= numerator) {
                return
                    uint160(
                        mulDivRoundingUp(numerator, sqrtPriceX96, denominator) //most precise formula
                    );
            }
        }
        // If overflow
        return
            uint160(
                divRoundingUp(numerator, (numerator / sqrtPriceX96) + amountIn)
            );
    }

In this function, we’re implementing two formulas. At the first return, it implements the same formula we implemented in Python. This is the most precise formula, but it can overflow when multiplying amountIn by sqrtPriceX96. The formula is (we discussed it in “Output Amount Calculation”):

When it overflows, we use an alternative formula, which is less precise:

Which is simply the previous formula with the numerator and the denominator divided by $√P$ to get rid of the multiplication in the numerator.

https://atiselsts.github.io/pdfs/uniswap-v3-liquidity-math.pdf

2.2.1 Price range boundaries

function getNextSqrtPriceFromAmount1RoundingDown(
    uint160 sqrtPriceX96,
    uint128 liquidity,
    uint256 amountIn
) internal pure returns (uint160) {
    return
        sqrtPriceX96 +
        uint160((amountIn << FixedPoint96.RESOLUTION) / liquidity);
}

Quoter Contract

assembly {
    let ptr := mload(0x40)
    mstore(ptr, amountOut)
    mstore(add(ptr, 0x20), sqrtPriceX96After)
    mstore(add(ptr, 0x40), tickAfter)
    revert(ptr, 96)
}

For gas optimization, this piece is implemented in Yul, the language used for inline assembly in Solidity. Let’s break it down:

1. mload(0x40) reads the pointer of the next available memory slot (memory in EVM is organized in 32-byte slots);
2. at that memory slot, mstore(ptr, amountOut) writes amountOut;
3. mstore(add(ptr, 0x20), sqrtPriceX96After) writes sqrtPriceX96After right after amountOut;
4. mstore(add(ptr, 0x40), tickAfter) writes tickAfter after sqrtPriceX96After;
5. revert(ptr, 96) reverts the call and returns 96 bytes (total length of the values we wrote to memory) of data at address ptr (start of the data we wrote above).

So, we’re concatenating the bytes representations of the values we need (exactly what abi.encode() does). Notice that the offsets are always 32 bytes, even though sqrtPriceX96After takes 20 bytes (uint160) and tickAfter takes 3 bytes (int24). This is so we could use abi.decode() to decode the data: its counterpart, abi.encode(), encodes all integers as 32-byte words.

Recap

Let’s recap to better understand the algorithm:

1. quote calls swap of a pool with input amount and swap direction;
2. swap performs a real swap, it runs the loop to fill the input amount specified by the user;
3. to get tokens from the user, swap calls the swap callback on the caller;
4. the caller (Quote contract) implements the callback, in which it reverts with output amount, new price, and new tick;
5. the revert bubbles up to the initial quote call;
6. in quote, the revert is caught, revert reason is decoded and returned as the result of calling quote.

I hope this is clear!

Quoter Limitation

This design has one significant limitation: since quote calls the swap function of the Pool contract, and the swap function is not a pure or view function (because it modifies contract state), quote cannot also be pure or view. swap modifies state and so does quote, even if not in Quoter contract. But we treat quote as a getter, a function that only reads contract data. This inconsistency means that EVM will use CALL opcode instead of STATICCALL when quote is called. This is not a big problem since Quoter reverts in the swap callback, and reverting resets the state modified during a call–this guarantees that quote won’t modify the state of the Pool contract (no actual trade will happen).

Another inconvenience that comes from this issue is that calling quote from a client library (Ethers.js, Web3.js, etc.) will trigger a transaction. To fix this, we’ll need to force the library to make a static call. We’ll see how to do this in Ethers.js later in this milestone.

it’s at the end of the static call that the EM will check if anything was updated if not it’s good

Code

Check repo