Uniswap v3-Part III

一、Tick Bitmap

Tick

1. tick 为什么不能直接存数组？

tick 的范围是 int24，大约 -8,388,608, 8,388,607，总共 1677 万个 tick。
如果直接用数组存一个 bool（1 byte），就要 16 MB；如果用 mapping(int24 => bool)，存储上也非常浪费 gas。
所以 V3 用了 bitmap 压缩存储。

2. tick bitmap

用一个 mapping(uint16 => uint256) 来存储。
每个 uint256 有 256 位，每一位可以表示一个 tick 的占用状态。
这样，一个 uint16 的 key，就能覆盖 256 个 tick。

3. tick 是 int24，怎么分解？

tick 是 int24（24 位），分成两部分来映射：

前 16 位 → 作为 map 的 key（bucket id）。
后 8 位 → 作为 uint256 里的 bit index。

这样，tickBitmap[key] 是一个 256 位的整数，tick 的最后 8 位（0~255）表示它在这个 bucket 里的哪个位置。

寻找 next tick

1.背景

Uniswap V3 里所有的 tick（价格刻度）不会全都存链上，只会存 有流动性提供者 LP 注入的 tick。

这些 tick 被压缩存储在一个 bitmap 里：

每个 word = 256 bits（uint256）
每一位代表一个 tick 是否被初始化（有 LP）
通过 tickSpacing 归约，避免 tick 太稠密

所以问题是：

给定当前 tick，怎么高效地找到 下一个被初始化的 tick？

2. 核心优化思路

传统方法：从当前位置逐个 tick 往前/往后扫描，直到找到一个被初始化的 tick。

👉 时间复杂度 = O(n)（n = 相隔的 tick 数量）。

Uniswap 方法：

先用 position() 算出所在 word 和 bit 位置
用 掩码(mask) 把 bitmap 剪裁到 需要的区间
用 bitScan (O(1)) 算法定位到第一个 1
👉 时间复杂度 = O(1) 常数级。

3. 代码逐步解读

(1) tick 压缩

int24 compressed = tick / tickSpacing;
if (tick < 0 && tick % tickSpacing != 0) compressed--;

将 tick 转换为压缩后的索引（对应 bitmap 的 bit）
向负无穷取整，避免负数 tick 出错

(2) 定位 word & bit

(int16 wordPos, uint8 bitPos) = position(compressed);

wordPos = compressed >> 8 （除以 256，定位到第几个 uint256）
bitPos = compressed % 256 （在 word 内的第几位）

(3) 当 (lte = true)

当 Lte=true 时说明使用 token0=>token1 那么池子中的 token1 数量变少，token1/token0 的比值减少，意味着 tick 减小，要寻找的 next tick 小于等于当前的 tick

uint256 mask = (1 << bitPos) - 1 + (1 << bitPos);
uint256 masked = self[wordPos] & mask;

mask 生成一个 从 bitPos 向右全是 1 的掩码
masked 表示当前位置及其右边所有 tick 的状态

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

如果找到 1：用 BitMath.mostSignificantBit(masked) 定位到最右边的 1
如果没找到：直接返回 word 边界的 tick

🔹 mostSignificantBit(uint256 x)核心逻辑就是 二分缩小范围：

if (x >= 2^128) { x >>= 128; r += 128; }
if (x >= 2^64)  { x >>= 64;  r += 64; }
if (x >= 2^32)  { x >>= 32;  r += 32; }
if (x >= 2^16)  { x >>= 16;  r += 16; }
if (x >= 2^8)   { x >>= 8;   r += 8; }
if (x >= 2^4)   { x >>= 4;   r += 4; }
if (x >= 2^2)   { x >>= 2;   r += 2; }
if (x >= 2)     r += 1;

每次比较，把候选范围折半。
最多 8 次判断 + 位移 就能确定 MSB。
时间复杂度：O(1)（常数时间，不依赖 256 位的大小）。

(4) 当要寻找的 next tick 大于当前的 tick 时 (lte = false)

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

mask 生成 bitPos 左边全是 1 的掩码
masked 表示当前位置左边所有 tick 的状态

initialized = masked != 0;
next = initialized
    ? (compressed + 1 + int24(BitMath.leastSignificantBit(masked) - bitPos)) * tickSpacing
    : (compressed + 1 + int24(type(uint8).max - bitPos)) * tickSpacing;

如果找到 1：用 BitMath.leastSignificantBit(masked) 定位到最近的 1
如果没找到：返回 word 的边界 tick

🔹 leastSignificantBit(uint256 x)

逻辑稍微绕一点，它不是用 x & (-x)（也能做到），而是用 分组掩码 + 左右缩小范围：

r = 255;
if (x & type(uint128).max > 0) { r -= 128; } else { x >>= 128; }
if (x & type(uint64).max > 0)  { r -= 64;  } else { x >>= 64; }
if (x & type(uint32).max > 0)  { r -= 32;  } else { x >>= 32; }
if (x & type(uint16).max > 0)  { r -= 16;  } else { x >>= 16; }
if (x & type(uint8).max > 0)   { r -= 8;   } else { x >>= 8; }
if (x & 0xf > 0)               { r -= 4;   } else { x >>= 4; }
if (x & 0x3 > 0)               { r -= 2;   } else { x >>= 2; }
if (x & 0x1 > 0)               r -= 1;

先看 低 128 位有没有非零，若有则最低位一定在 [0..127]；否则一定在 [128..255]。
再继续缩小到 64 位、32 位、16 位……一直到 1 位。
r 从 255 开始往下减，最终就是 LSB 的位置。

同样最多 8 步。
时间复杂度：O(1)。

二、Fee

三、Twap

1.Math Twap

2.Math Swap token X Y

3.code

tick
Uniswap V3 不直接存价格，而是存储 tick（价格 log 的离散化形式）。
- 价格 P = 1.0001^tick
- tick 累积（tickCumulative）用于计算时间加权价格。
Observation
每个 observation 存的是：
- blockTimestamp（记录的时间点）
- tickCumulative（从池子初始化以来，累加 tick * 时间）
- secondsPerLiquidityCumulativeX128（从池子初始化以来，累加秒 / 流动性）
- initialized 标志位
可以理解为：
在某个时间点的累计账本
TWAP 的本质
TWAP = (tickCumulative_now - tickCumulative_past) / 时间间隔
也就是：
tick 在时间维度上的平均值。
（然后再把 tick 转换成价格）

📌 Uniswap V3 TWAP 更新流程

用户发起 swap / mint / burn
          │
          ▼
  UniswapV3Pool.sol
     _update()
          │
          ▼
    Oracle.sol
  write(observation)
   └─ 记录当前 tick, 时间戳
   └─ 维护 observation 环（环形数组）

📌 Uniswap V3 TWAP 获取流程

外部调用者 (合约/用户/Uniswap V3 Periphery)
          │
          ▼
  UniswapV3Pool.sol
    observe(uint32[] secondsAgos)
          │
          ▼
    Oracle.sol
   observe(...)
   ├─ 读取当前 observation 数据
   ├─ 回溯 N 秒前的 observation
   └─ 计算 Δtick 累积值 / Δ时间
          │
          ▼
   返回平均价格 (TWAP)

   注：Uniswap V3 Periphery调用 pool.observe([secondsAgo, 0])真正把 observation 数据转化为 TWAP 结果（即把 tickCumulative → 平均价格）

🔄 逻辑流程

初始化
- initialize() 在池子第一次创建时写入第一个 observation（时间戳=当前，累计量=0）。
每次 swap 时写 observation
- 在 pool swap 时，调用 Oracle.write()，往 observation 数组里写入一个新的 observation。
- 写入内容：
  - tickCumulative = last.tickCumulative + tick * Δt
  - secondsPerLiquidityCumulativeX128 += Δt / liquidity
  - 时间戳更新到当前块
- 这样，每个 observation 代表：
  从上一个 observation 到这次，tick 与流动性如何随时间演变。

/// @notice Writes an oracle observation to the array
    /// @dev Writable at most once per block. Index represents the most recently written element. cardinality and index must be tracked externally.
    /// If the index is at the end of the allowable array length (according to cardinality), and the next cardinality
    /// is greater than the current one, cardinality may be increased. This restriction is created to preserve ordering.
    /// @param self The stored oracle array
    /// @param index The index of the observation that was most recently written to the observations array
    /// @param blockTimestamp The timestamp of the new observation
    /// @param tick The active tick at the time of the new observation
    /// @param liquidity The total in-range liquidity at the time of the new observation
    /// @param cardinality The number of populated elements in the oracle array
    /// @param cardinalityNext The new length of the oracle array, independent of population
    /// @return indexUpdated The new index of the most recently written element in the oracle array
    /// @return cardinalityUpdated The new cardinality of the oracle array
    function write(
        Observation[65535] storage self,
        uint16 index,
        uint32 blockTimestamp,
        int24 tick,
        uint128 liquidity,
        uint16 cardinality,
        uint16 cardinalityNext
    ) internal returns (uint16 indexUpdated, uint16 cardinalityUpdated) {
        Observation memory last = self[index];

        // early return if we've already written an observation this block
        if (last.blockTimestamp == blockTimestamp) return (index, cardinality);

        // if the conditions are right, we can bump the cardinality
        if (cardinalityNext > cardinality && index == (cardinality - 1)) {
            cardinalityUpdated = cardinalityNext;
        } else {
            cardinalityUpdated = cardinality;
        }

        indexUpdated = (index + 1) % cardinalityUpdated;
        self[indexUpdated] = transform(last, blockTimestamp, tick, liquidity);
    }

查询历史 observation

调用 observe(secondsAgos[]) 时，会去算：
- 当前时刻的累计值
- 过去指定秒数的累计值
再用差值 / 时间 = 平均值。

function observe(
        Observation[65535] storage self,
        uint32 time,
        uint32[] memory secondsAgos,
        int24 tick,
        uint16 index,
        uint128 liquidity,
        uint16 cardinality
    ) internal view returns (int56[] memory tickCumulatives, uint160[] memory secondsPerLiquidityCumulativeX128s) {
        require(cardinality > 0, 'I');

        tickCumulatives = new int56[](secondsAgos.length);
        secondsPerLiquidityCumulativeX128s = new uint160[](secondsAgos.length);
        for (uint256 i = 0; i < secondsAgos.length; i++) {
            (tickCumulatives[i], secondsPerLiquidityCumulativeX128s[i]) = observeSingle(
                self,
                time,
                secondsAgos[i],
                tick,
                index,
                liquidity,
                cardinality
            );
        }
    }

4.fork 主网测试

// SPDX-License-Identifier: MIT
pragma solidity 0.8.24;

import {TickMath} from "../src/uniswap-v3/TickMath.sol";
import {FullMath} from "../src/uniswap-v3/FullMath.sol";
import {IUniswapV3Pool} from "../src/interfaces/uniswap-v3/IUniswapV3Pool.sol";

contract UniswapV3Twap {
    IUniswapV3Pool public immutable pool;
    address public immutable token0;
    address public immutable token1;

    constructor(address _pool) {
        pool = IUniswapV3Pool(_pool);
        token0 = pool.token0();
        token1 = pool.token1();
    }

    // Copied from
    // https://github.com/Uniswap/v3-periphery/blob/0.8/contracts/libraries/OracleLibrary.sol
    /// @notice Given a tick and a token amount, calculates the amount of token received in exchange
    function getQuoteAtTick(int24 tick, uint128 baseAmount, address baseToken, address quoteToken)
        internal
        pure
        returns (uint256 quoteAmount)
    {
        uint160 sqrtRatioX96 = TickMath.getSqrtRatioAtTick(tick);

        // Calculate quoteAmount with better precision if it doesn't overflow when multiplied by itself
        if (sqrtRatioX96 <= type(uint128).max) {
            uint256 ratioX192 = uint256(sqrtRatioX96) * sqrtRatioX96;
            quoteAmount = baseToken < quoteToken
                ? FullMath.mulDiv(ratioX192, baseAmount, 1 << 192)
                : FullMath.mulDiv(1 << 192, baseAmount, ratioX192);
        } else {
            uint256 ratioX128 = FullMath.mulDiv(sqrtRatioX96, sqrtRatioX96, 1 << 64);
            quoteAmount = baseToken < quoteToken
                ? FullMath.mulDiv(ratioX128, baseAmount, 1 << 128)
                : FullMath.mulDiv(1 << 128, baseAmount, ratioX128);
        }
    }

    function getTwapAmountOut(address tokenIn, uint128 amountIn, uint32 dt) external view returns (uint256 amountOut) {
        // Task 1 - Require tokenIn is token0 or token1
        // Task 2 - Assign tokenOut
        require(tokenIn == token0 || tokenIn == token1, "Invalid token");
        address tokenOut = tokenIn == token0 ? token1 : token0;

        // Task 3 - Fill out timeDeltas with dt and 0
        uint32[] memory timeDeltas = new uint32[](2);
        timeDeltas[0] = dt;
        timeDeltas[1] = 0;

        // Task 4 - Call pool.observe
        // Task 5 - Calculate tickCumulativeDelta
        (int56[] memory tickCumulatives, uint160[] memory secondsPerLiquidityCumulativeX128s) = pool.observe(timeDeltas);
        int56 tickCumulativeDelta = tickCumulatives[1] - tickCumulatives[0];

        // Task 6 - Calculate average tick
        int24 tick = int24(tickCumulativeDelta / int56(int32(dt)));

        // Always round to negative infinity
        if (tickCumulativeDelta < 0 && (tickCumulativeDelta % int56(uint56(dt)) != 0)) {
            tick--;
        }

        // Task 7 - Call getQuoteAtTick
        return getQuoteAtTick(tick, amountIn, tokenIn, tokenOut);
    }
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.24;

import {Test, console2} from "forge-std/Test.sol";
import {WETH, USDC, UNISWAP_V3_POOL_USDC_WETH_500} from "../src/Constants.sol";
import {UniswapV3Twap} from "./UniswapV3Twap.sol";

contract UniswapV3TwapTest is Test {
    UniswapV3Twap private twap;

    function setUp() public {
        twap = new UniswapV3Twap(UNISWAP_V3_POOL_USDC_WETH_500);
    }

    function test_twap() public {
        uint256 usdcOut = twap.getTwapAmountOut({tokenIn: WETH, amountIn: 1e18, dt: 3600});

        console2.log("USDC out %e", usdcOut);
    }
}

九、Flash

fork 主网测试

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.24;

import {IERC20} from "../src/interfaces/IERC20.sol";
import {IUniswapV3Pool} from "../src/interfaces/uniswap-v3/IUniswapV3Pool.sol";

contract UniswapV3Flash {
    error UniswapV3Flash__NotAuthorized();

    struct FlashCallbackData {
        uint256 amount0;
        uint256 amount1;
        address caller;
    }

    IUniswapV3Pool private immutable pool;
    IERC20 private immutable token0;
    IERC20 private immutable token1;

    constructor(address _pool) {
        pool = IUniswapV3Pool(_pool);
        token0 = IERC20(pool.token0());
        token1 = IERC20(pool.token1());
    }

    function flash(uint256 amount0, uint256 amount1) external {
        // Task 1 - ABI encode FlashCallbackData
        // Task 2 - Call IUniswapV3Pool.flash
        FlashCallbackData memory callbackData =
            FlashCallbackData({amount0: amount0, amount1: amount1, caller: msg.sender});
        bytes memory data = abi.encode(callbackData);
        pool.flash(address(this), amount0, amount1, data);
    }

    function uniswapV3FlashCallback(
        // Pool fee x amount requested
        uint256 fee0,
        uint256 fee1,
        bytes calldata data
    ) external {
        // Task 3 - Check msg.sender is pool
        // Task 4 - Decode data into FlashCallbackData
        // Task 5  - Transfer fees from FlashCallbackData.caller
        // Task 6 - Repay pool, amount borrowed + fee
        if (msg.sender != address(pool)) revert UniswapV3Flash__NotAuthorized();
        FlashCallbackData memory callbackData = abi.decode(data, (FlashCallbackData));
        if (fee0 > 0) token0.transferFrom(callbackData.caller, address(this), fee0);
        if (fee1 > 0) token1.transferFrom(callbackData.caller, address(this), fee1);
        if (callbackData.amount0 > 0) token0.transfer(address(pool), callbackData.amount0 + fee0);
        if (callbackData.amount1 > 0) token1.transfer(address(pool), callbackData.amount1 + fee1);
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.24;

import {Test, console2} from "forge-std/Test.sol";
import {IERC20} from "../src/interfaces/IERC20.sol";
import {UNISWAP_V3_POOL_DAI_WETH_3000, DAI, WETH} from "../src/Constants.sol";
import {UniswapV3Flash} from "./UniswapV3Flash.sol";

contract UniswapV3FlashTest is Test {
    IERC20 private constant weth = IERC20(WETH);
    IERC20 private constant dai = IERC20(DAI);
    UniswapV3Flash private uni;

    function setUp() public {
        uni = new UniswapV3Flash(UNISWAP_V3_POOL_DAI_WETH_3000);

        deal(DAI, address(this), 1e3 * 1e18);
        dai.approve(address(uni), type(uint256).max);
    }

    function test_flash() public {
        uint256 daiBefore = dai.balanceOf(address(this));
        uni.flash(1e3 * 1e18, 0);
        uint256 daiAfter = dai.balanceOf(address(this));

        uint256 fee = daiBefore - daiAfter;
        console2.log("DAI fee", fee);
    }
}