Uniswap V2 源码学习 (四). 签名和路由

UniswapV2Pair 的 permit函数和签名算法.

上次我们在研究 router合约的时候, 有一个 removeLiquidityWithPermit 函数, 今天讲讲它和 Pair 的permit方法

UnitSwapPair 合约是一种ERC20, 实现了一个 permit方法, permit功能与 approve类似 但是 permit 允许第三方代为执行, 例如 用户 A需要向 B授权, 但是 A 没有ETH做gas, 它可以用自己的私钥签名, 让 C 来执行permit. permit函数定义如下:

function permit(address owner, address spender, uint value, uint deadline, uint8 v, bytes32 r, bytes32 s) external {
    require(deadline >= block.timestamp, 'UniswapV2: EXPIRED');
    bytes32 digest = keccak256(
        abi.encodePacked(
            '\x19\x01',
            DOMAIN_SEPARATOR,
            keccak256(abi.encode(PERMIT_TYPEHASH, owner, spender, value, nonces[owner]++, deadline))
        )
    );
    address recoveredAddress = ecrecover(digest, v, r, s);
    require(recoveredAddress != address(0) && recoveredAddress == owner, 'UniswapV2: INVALID_SIGNATURE');
    _approve(owner, spender, value);
}

这个函数首先会将授权的信息, 例如授权方 owner, 被授权方spender, 授权数量, nonce, 截止日期等信息打包后进行hash. 然后使用ecrecover( hash , v, r,s ) , 算出签名者的公钥, 如果签名者就是 owner, 那么同意授权(实际上还是调用 _approve() ).

注意这里为了避免重放攻击, 在hash过程中还附加了很多信息, 例如 DOMAIN_SEPARATOR 和 PERMIT_TYPEHASH,

其中 DOMAIN_SEPARATOR 包含了本条链的 chainId, 当前合约名称, 版本, 合约地址等信息, 它的初始化实在构造函数进行. 而 PERMIT_TYPEHASH 的值 = keccak256("Permit(address owner,address spender,uint256 value,uint256 nonce,uint256 deadline)")

这两个变量被添加到签名信息中, 目的是让这个签名只能用于本条链, 本合约, 本功能(Permit)使用, 从而避免这个签名被拿到其他合约或者其他链的合约实施重放攻击

这个 permit函数 遵循的是eip-2612, 具体信息参考这个网址: https://eips.ethereum.org/EIPS/eip-2612 (eip-2612目前处于draft状态, 并不是官方标准).

那么用户如果想要委托别人帮自己授权, 首先需要生成签名, 这个签名这么生成的呢? 我们只要按照 permit的检验流程相同的算法进行hash, 然后对 hash 后的数据用自己的私钥签名就可以了.

首先我们看看 DOMAIN_SEPARATOR 的计算方法: (DOMAIN_SEPARATOR 并不是必须在本地计算, 就可以调用 pair合约.DOMAIN_SEPARATOR() 获取, 但是为了提高签名速度, 我们接下来要在本地把它算出, 省掉访问节点的时间)

constructor() public {
    uint chainId;
    assembly {
        chainId := chainid
    }
    DOMAIN_SEPARATOR = keccak256(
        abi.encode(
            keccak256('EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)'),
            keccak256(bytes(name)),
            keccak256(bytes('1')),
            chainId,
            address(this)
        )
    );
}

上面的 name 是本代币的名称: string public constant name = 'Uniswap V2';

好了, 有了以上信息, 我们可以写python代码按照相同的流程, 自己生成签名:

def sign(pair_addr, owner, spender, permit_value, nonce, deadline, private_key):
    chainId = w3.eth.chainId
    ###########################################################################################
    # DOMAIN_SEPERATOR
    # 此值可以通过 pair.DOMAIN_SEPERATOR().call() 获得, 但是此处采用本地计算
    ###########################################################################################
    DOMAIN_SEPARATOR = Web3.keccak(eth_abi.encode_abi(
        ['bytes32', 'bytes32', 'bytes32', 'uint256', 'address'], [
            Web3.keccak(b'EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)'),
            Web3.keccak(b'Uniswap V2'),
            Web3.keccak(b'1'),
            chainId,
            pair_addr
        ]
    ))

    ###########################################################################################
    # PERMIT_TYPEHASH = Web3.keccak('Permit(address owner,address spender,'
    #                           'uint256 value,uint256 nonce,uint256 deadline)'.encode())
    # 此值可以通过 pair.PERMIT_TYPEHASH().call() 获得
    ###########################################################################################
    # PERMIT_TYPEHASH = bytes.fromhex('6e71edae12b1b97f4d1f60370fef10105fa2faae0126114a169c64845d6126c9')

    PERMIT_TYPEHASH = Web3.keccak(b'Permit(address owner,address spender,uint256 value,uint256 nonce,uint256 deadline)')

    DETAIL_HASH = Web3.keccak(eth_abi.encode_abi(
        ['bytes32', 'address', 'address', 'uint256', 'uint256', 'uint256'],[
            PERMIT_TYPEHASH,
            owner,
            spender,
            permit_value,
            nonce,
            deadline
        ]))

    # 最终的 hash.
    final_hash = Web3.solidityKeccak(['bytes','bytes','bytes'], [
        b'\x19\x01',
        DOMAIN_SEPARATOR,
        DETAIL_HASH
    ])

    signature = w3.eth.account.signHash(final_hash, private_key)
    return signature

经过测试, 以上代码签名后 用它调用合约的 permit函数能够通过验证, 证明我们的签名算法是正确的.

既然成功通过了 permit的验证, 我们就可以用它执行router的removeLiquidityWithPermit了,流程如下:

pair_addr = factory.getPair(WBTC.address, USDT.address)
pair = w3.eth.contract(address = pair_addr, abi = pair_abi)

nonce = pair.functions.nonces(public_key).call()
signature = sign(pair_addr, public_key, router.address, permit_value, nonce, deadline, private_key)
invocation = router.functions.removeLiquidityWithPermit(
                                            WBTC.address, USDT.address,
                                            permit_value,
                                            0, 0,
                                            public_key,
                                            deadline,
                                            False,
                                            signature.v,  Web3.toBytes(signature.r),  Web3.toBytes(signature.s)
                                        )
tx = invocation.buildTransaction({
    'from': public_key,
    'nonce':  w3.eth.get_transaction_count(public_key)
})
signed_tx = w3.eth.account.sign_transaction(tx, private_key = private_key)
tx_hash = w3.eth.send_raw_transaction(signed_tx.rawTransaction)
tx_receipt = w3.eth.wait_for_transaction_receipt(tx_hash)

这样, 我们不需要授权 lp代币 给router就可以移除流动性了.

目前这个方法只能在后端实现, 不能在web端实现, nodejs的版本可以参考以下网址: https://github.com/1inch/permit-signed-approvals-utils

由于本文作者不懂nodejs, 请读者自行实验

关于重放攻击, 我思考了一下, 这个签名函数附加了很多不可重复信息避免签名被拿到其他地方重放, 但是不能阻止用户在其他合约被钓鱼, 例如黑客可以发布一个合约, 使用相同的 DOMAIN_SEPARATOR, PERMIT_TYPEHASH, 将 nonce指向 Uniswap某个交易对的 nonce, spender设置为黑客控制的地址, 要求用户签名, 再将用户的签名拿到 Uniswap执行 permit, 获取授权后转走用户的 LP 代币. 因此我们在 dapp上签名的时候应该注意, 不要随便签署没有公开源码的合约, 避免被钓鱼.

eip-2612 相关参考链接:

"5 Tips & Tricks for DeFi Developers from the UniswapV2 Contracts Review" https://dev.to/francisldn/5-tips-tricks-in-uniswapv2-contracts-for-defi-developers-32oa

"EIP-2612: permit – 712-signed approvals " https://eips.ethereum.org/EIPS/eip-2612

"A Long Way To Go: On Gasless Tokens and ERC20-Permit" https://soliditydeveloper.com/erc20-permit

"Openzeppelin ERC-20-Permit (in draft status)" https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/token/ERC20/extensions/draft-ERC20Permit.sol

"Why is ERC20Permit better than approve/transferFrom?" https://forum.openzeppelin.com/t/why-is-erc20permit-better-than-approve-transferfrom/7478

Uniswap 的路由算法:

在前面的交易算法中我们注意到, Router的每个 swapXXX 函数中, 指定的不是 输入币种和输出币种, 而是一地址的数组 path[], 例如:

function swapExactTokensForTokens(
        uint amountIn,
        uint amountOutMin,
        address[] calldata path,
        address to,
        uint deadline
    )

上面的第三个参数 path是token地址的数组, 它制定了兑换的路径, 其中的每个 path[i],path[i+1] 对应了一个交易对,

很多同学很好奇这个路径数组是怎么计算出来的, 下面我们简单介绍一下

应该说这个计算路径的方法才是路由算法, 但是在合约里面没有实现, 而是在链下完成的, 代码库是uniswap下的alpha-router: https://github.com/Uniswap/smart-order-router/blob/main/src/routers/alpha-router/

下面代码是计算从输入token到输出token路由的所有路径: https://github.com/Uniswap/smart-order-router/blob/main/src/routers/alpha-router/functions/compute-all-routes.ts

export function computeAllV2Routes(
  tokenIn: Token,
  tokenOut: Token,
  pools: Pair[],
  maxHops: number
): V2Route[] {
  return computeAllRoutes<Pair, V2Route>(
    tokenIn,
    tokenOut,
    (route: Pair[], tokenIn: Token, tokenOut: Token) => {
      return new V2Route(route, tokenIn, tokenOut);
    },
    pools,
    maxHops
  );
}

export function computeAllRoutes<
  TPool extends Pair | Pool,
  TRoute extends V3Route | V2Route
>(
  tokenIn: Token,
  tokenOut: Token,
  buildRoute: (route: TPool[], tokenIn: Token, tokenOut: Token) => TRoute,
  pools: TPool[],
  maxHops: number
): TRoute[] {
  const poolsUsed = Array<boolean>(pools.length).fill(false);
  const routes: TRoute[] = [];

  const computeRoutes = (
    tokenIn: Token,
    tokenOut: Token,
    currentRoute: TPool[],
    poolsUsed: boolean[],
    _previousTokenOut?: Token
  ) => {
    if (currentRoute.length > maxHops) {
      return;
    }

    if (
      currentRoute.length > 0 &&
      currentRoute[currentRoute.length - 1]!.involvesToken(tokenOut)
    ) {
      routes.push(buildRoute([...currentRoute], tokenIn, tokenOut));
      return;
    }

    for (let i = 0; i < pools.length; i++) {
      if (poolsUsed[i]) {
        continue;
      }

      const curPool = pools[i]!;
      const previousTokenOut = _previousTokenOut ? _previousTokenOut : tokenIn;

      if (!curPool.involvesToken(previousTokenOut)) {
        continue;
      }

      const currentTokenOut = curPool.token0.equals(previousTokenOut)
        ? curPool.token1
        : curPool.token0;

      currentRoute.push(curPool);
      poolsUsed[i] = true;
      computeRoutes(
        tokenIn,
        tokenOut,
        currentRoute,
        poolsUsed,
        currentTokenOut
      );
      poolsUsed[i] = false;
      currentRoute.pop();
    }
  };

这个路由非常简单, 它使用了一个深度优先的遍历算法, 在 computeAllRoutes中递归调用 computeRoutes 完成遍历所有可能性. 上面的内部函数 computeRoutes 是递归函数, 他的参数中有一个 currentRoute 记录当前的 route 路径.

computeAllRoutes 函数接收的 pools[] 参数 是市场上所有的交易对, 可以使用api获取, 具体代码在: https://github.com/Uniswap/smart-order-router/blob/main/src/providers/v2/subgraph-provider.ts

...
const SUBGRAPH_URL_BY_CHAIN: { [chainId in ChainId]?: string } = {
  [ChainId.MAINNET]:
    'https://api.thegraph.com/subgraphs/name/ianlapham/uniswapv2',
  [ChainId.RINKEBY]:
    'https://api.thegraph.com/subgraphs/name/ianlapham/uniswap-v2-rinkeby',
};
...

export class V2SubgraphProvider implements IV2SubgraphProvider {
  private client: GraphQLClient;

  constructor(
    private chainId: ChainId,
    private retries = 2,
    private timeout = 360000,
    private rollback = true
  ) {
    const subgraphUrl = SUBGRAPH_URL_BY_CHAIN[this.chainId];
    if (!subgraphUrl) {
      throw new Error(`No subgraph url for chain id: ${this.chainId}`);
    }
    this.client = new GraphQLClient(subgraphUrl);
  }

  public async getPools(
    _tokenIn?: Token,
    _tokenOut?: Token,
    providerConfig?: ProviderConfig
  ): Promise<V2SubgraphPool[]> {

    /***********************************************************************
     * 访问 API ,得到所有pool
     ***********************************************************************/
     ...
     ...
  }

上面的 V2SubgraphProvider 中的 gepPools函数 就是获取所有pool的具体实现, 有兴趣的同学请自行研究.

• 得到了所有可能路径之后, 会使用 getBestSwapRoute() 获取最优路径,

调用代码 alpha-router.ts 的 912行: https://github.com/Uniswap/smart-order-router/blob/main/src/routers/alpha-router/alpha-router.ts

// Given all the quotes for all the amounts for all the routes, find the best combination.
const beforeBestSwap = Date.now();
const swapRouteRaw = await getBestSwapRoute(
  amount,
  percents,
  allRoutesWithValidQuotes,
  tradeType,
  this.chainId,
  routingConfig,
  gasModel
);

getBestSwapRoute() 的具体实现代码: https://github.com/Uniswap/smart-order-router/blob/main/src/routers/alpha-router/functions/best-swap-route.ts

这里就不展开了, 因为这个实现并不难(笔者觉得这个 getBestSwapRoute() 应该20行代码可以完成, 实际上写了560行)

好了, 经过这几期的学习, 相信大家对 Uniswap V2 有了更深刻的理解, 接下来让我们继续在 crypto 的世界一起探索吧.