## 介绍

在智能合约开发中，当需要验证签名时，通常会有nonce字段，用于防止签名重放攻击。而我们常常会直接设计成nonce从小到大，按顺序增长。然而在高频交易的场景下，这样会存在着缺陷，而另一个更好实现是 —— 无序nonce。

<br>

## 顺序nonce

示例：

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

contract TraditionalNonceExample {
    // 每个地址的当前 nonce（从 0 开始递增）
    mapping(address => uint256) public nonceOf;

    error InvalidNonce(uint256 expected, uint256 provided);

    // 模拟一个需要签名授权的操作（比如 permit）
    function doSomethingImportant(
        address user,
        uint256 amount,
        uint256 deadline,
        uint256 providedNonce,    // 用户在签名里填的 nonce
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external {
        require(block.timestamp <= deadline, "Expired");
        
        // 关键：检查 nonce 必须等于当前期望值（顺序递增），并且+1
        uint256 expectedNonce = nonceOf[user]++;
        if (providedNonce != expectedNonce) {
            revert InvalidNonce(expectedNonce, providedNonce);
        }

        // 验证签名
        bytes32 messageHash = keccak256(
            abi.encode(
                keccak256("DoSomething(address user,uint256 amount,uint256 deadline,uint256 nonce)"), // EIP-712 type hash
                user,
                amount,
                deadline,
                providedNonce
            )
        );
        bytes32 ethSignedMessageHash = keccak256(abi.encodePacked("\x19\x01", block.chainid, address(this), messageHash));
        address signer = ecrecover(ethSignedMessageHash, v, r, s);
        require(signer == user, "Invalid signature");

        // 执行你的业务逻辑（比如转账、swap 等）
        // _doYourThing(user, amount);
    }

    // 让用户可以主动跳过一些坏掉的 nonce
    function advanceNonce(uint256 amountToSkip) external {
        nonceOf[msg.sender] += amountToSkip;
    }
}

假设该nonce模块是应用在高频交易上，同一时刻提交了20笔交易，对应着0 ～ 19 nonce。那么这20笔交易必须按nonce的顺序去执行，如果nonce 1的交易排在nonce 0的交易前面，则nonce 1的交易会报错无法执行。更严重的，nonce 1交易的失败，也会导致后面nonce的交易失败。

而为了应对这种情况，出现了无序nonce的机制。

<br>

## 无序nonce

这里参考Uniswap的Permit2合约中的无序nonce实现来讲解：

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

contract TraditionalNonceExample {
    
    mapping(address user => mapping(uint256 wordPos => uint256)) public nonceBitmap;

    error InvalidNonce();

    // 模拟一个需要签名授权的操作（比如 permit）
    function doSomethingImportant(
        address user,
        uint256 amount,
        uint256 deadline,
        uint256 providedNonce,    // 用户在签名里填的 nonce
        uint8 v,
        bytes32 r,
        bytes32 s
    ) external {
        require(block.timestamp <= deadline, "Expired");
        
        // 关键：检查 nonce 
        _useUnorderedNonce(user, providedNonce);

        // 验证签名
        bytes32 messageHash = keccak256(
            abi.encode(
                keccak256("DoSomething(address user,uint256 amount,uint256 deadline,uint256 nonce)"), // EIP-712 type hash
                user,
                amount,
                deadline,
                providedNonce
            )
        );
        bytes32 ethSignedMessageHash = keccak256(abi.encodePacked("\x19\x01", block.chainid, address(this), messageHash));
        address signer = ecrecover(ethSignedMessageHash, v, r, s);
        require(signer == user, "Invalid signature");

        // 执行你的业务逻辑（比如转账、swap 等）
        // _doYourThing(user, amount);
    }
		
		/// ============ Uniswap Permit2 unordered nonce ============
    /// @inheritdoc ISignatureTransfer
    function invalidateUnorderedNonces(uint256 wordPos, uint256 mask) external {
        nonceBitmap[msg.sender][wordPos] |= mask;

        emit UnorderedNonceInvalidation(msg.sender, wordPos, mask);
    }

    /// @notice Returns the index of the bitmap and the bit position within the bitmap. Used for unordered nonces
    /// @param nonce The nonce to get the associated word and bit positions
    /// @return wordPos The word position or index into the nonceBitmap
    /// @return bitPos The bit position
    /// @dev The first 248 bits of the nonce value is the index of the desired bitmap
    /// @dev The last 8 bits of the nonce value is the position of the bit in the bitmap
    function bitmapPositions(uint256 nonce) private pure returns (uint256 wordPos, uint256 bitPos) {
        wordPos = uint248(nonce >> 8);
        bitPos = uint8(nonce);
    }

    /// @notice Checks whether a nonce is taken and sets the bit at the bit position in the bitmap at the word position
    /// @param from The address to use the nonce at
    /// @param nonce The nonce to spend
    function _useUnorderedNonce(address from, uint256 nonce) internal {
        (uint256 wordPos, uint256 bitPos) = bitmapPositions(nonce);
        uint256 bit = 1 << bitPos;
        uint256 flipped = nonceBitmap[from][wordPos] ^= bit;

        if (flipped & bit == 0) revert InvalidNonce();
    }
}

在上述无序nonce的实现中，nonce的存储数据结构为：`mapping(address user => mapping(uint256 wordPos => uint256 bitPos)) public nonceBitmap;`

这里的wordPos实际上是个248bit的值，容量为 2^248。而每个wordPos会对应一个256大小的bitmap，这也就是代表着实际的nonce。

可以想象为：每个用户都有2^248个抽屉，而每个抽屉中都有256个位置，每个位置代表着一个nonce。位置原本是空的（bit值为0），当该nonce被使用后，位置会被填充（bit值为1）。

<br>

1. 在调用需要验证签名的函数时，会传一个准备使用的nonce，数据类型为uint256。该nonce值中包含着wordPos和bitPos数据，可通过`bitmapPositions()`函数进行解析。


2.在`_useUnorderedNonce()`函数中，会对wordPos和bitPos进行验证，nonce是否已经使用了。使用过了则报错会滚，没使用过，则设该nonce为已被使用。


3. 而`invalidateUnorderedNonces(uint256 wordPos, uint256 mask)`函数可以将某wordPos中某些未使用的nonce设为已使用。因此在实际使用时，如果某些交易可能需要同时取消，那么这些交易最好用同一个wordPos中的nonce，这样在取消时会更加方便。