Michael.W基于Foundry精读Openzeppelin第50期——ERC20Votes.sol

  • Michael.W
  • 更新于 2024-03-14 16:54
  • 阅读 1138

ERC20Votes库是一个具备类Compound委托投票功能的ERC20拓展库。本库的发行量上限是2^224-1,比Compound更通用。合约内部使用快照结构Checkpoint来记录每个投票目标地址的总票数,每个token持有者可以采用直接或者离线签名两种方式委托投票给任何地址。

0. 版本

[openzeppelin]:v4.8.3,[forge-std]:v1.5.6

0.1 ERC20Votes.sol

Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/token/ERC20/extensions/ERC20Votes.sol

ERC20Votes库是一个具备类Compound委托投票功能的ERC20拓展库。本库的发行量上限是2^224-1,比Compound更通用(COMP是2^96-1)。合约内部使用快照结构Checkpoint来记录每个投票目标地址的总票数,每个token持有者可以采用直接或者离线签名两种方式委托投票给任何地址。每个目标地址得到的总票数和总发行量支持指定区块高度的快照查询。为了节约转账gas,余额计算并不包含本身被委托的票数,但是委托票数会随着用户的转账发生对应目标的转移。

注:如果业务上需要兼容COMP,可以使用拓展库ERC20VotesComp

1. 目标合约

继承ERC20Votes合约:

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/token/ERC20/extensions/MockERC20Votes.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "openzeppelin-contracts/contracts/token/ERC20/extensions/ERC20Votes.sol";

contract MockERC20Votes is ERC20Votes {
    constructor(
        string memory name,
        string memory symbol
    )
    ERC20Permit(name)
    ERC20(name, symbol)
    {}

    function maxSupply() external view returns (uint224){
        return _maxSupply();
    }

    function mint(address account, uint amount) external {
        _mint(account, amount);
    }

    function burn(address account, uint amount) external {
        _burn(account, amount);
    }
}

全部foundry测试合约:

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/token/ERC20/extensions/ERC20Votes.t.sol

2. 代码精读

2.1 checkpoints(address account, uint32 pos) && numCheckpoints(address account) && getVotes(address account) && delegates(address account)

  • checkpoints(address account, uint32 pos):获取account的Checkpoint数组中索引为pos的元素值;
  • numCheckpoints(address account):获取account的Checkpoint数组的元素个数(uint32类型);
  • getVotes(address account):获取account当前已被委托的总票数;
  • delegates(address account):获取当前account地址委托投票的目标地址。
    // 快照结构,用于记录:
    // 1. 委托投票目标地址得到的总票数;
    // 2. token总供应量
    struct Checkpoint {
        // 产生本快照的区块高度
        uint32 fromBlock;
        // 快照内数据
        uint224 votes;
    }

    // 结构化数据Delegation的type hash(用于计算结构化数据的struct hash)
    bytes32 private constant _DELEGATION_TYPEHASH =
        keccak256("Delegation(address delegatee,uint256 nonce,uint256 expiry)");

    // 记录委托投票的映射关系的map。key为委托者地址,value为委托目标地址
    mapping(address => address) private _delegates;
    // 各委托目标地址的Checkpoints记录。key为委托目标地址,value为该目标地址被委托的全部投票票数的快照记录数组
    mapping(address => Checkpoint[]) private _checkpoints;
    // token总发行量的快照记录数组
    Checkpoint[] private _totalSupplyCheckpoints;

    function checkpoints(address account, uint32 pos) public view virtual returns (Checkpoint memory) {
        return _checkpoints[account][pos];
    }

    function numCheckpoints(address account) public view virtual returns (uint32) {
        return SafeCast.toUint32(_checkpoints[account].length);
    }

    function getVotes(address account) public view virtual override returns (uint256) {
        // account的Checkpoint数组长度
        uint256 pos = _checkpoints[account].length;
        // 如果数组长度为0,表示account从未被委托过,返回0。
        // 否则返回Checkpoint数组的队尾元素的votes值
        return pos == 0 ? 0 : _checkpoints[account][pos - 1].votes;
    }

    function delegates(address account) public view virtual override returns (address) {
        return _delegates[account];
    }

2.2 delegate(address delegatee)

msg.sender委托投票给delegatee。

注:如果msg.sender之前已经委托投票给了A,会将对应票从A转移到delegatee。

    function delegate(address delegatee) public virtual override {
        // 调用_delegate(),将msg._msgSender()的票从其原委托目标地址转移给delegatee
        _delegate(_msgSender(), delegatee);
    }

    // 将delegator的投票委托给delegatee
    // 注:如果delegator之前已经委托投票给A,会将对应票从A转移到delegatee
    function _delegate(address delegator, address delegatee) internal virtual {
        // 获取delegator当前委托投票的目标地址
        address currentDelegate = delegates(delegator);
        // 获取delegator的token余额,即持有token与票的比例为1:1
        uint256 delegatorBalance = balanceOf(delegator);
        // 将delegatee设置为delegator的当前委托投票的目标地址
        _delegates[delegator] = delegatee;
        // 抛出事件
        emit DelegateChanged(delegator, currentDelegate, delegatee);
        // 将数量为delegator当前的token余额的票从原委托投票的目标地址身上转到delegatee
        _moveVotingPower(currentDelegate, delegatee, delegatorBalance);
    }

    // 从src身上转移数量为amount的票到dst身上
    function _moveVotingPower(
        address src,
        address dst,
        uint256 amount
    ) private {
        // 如果 src为dst 或 amount为0时,该函数不做任何操作
        if (src != dst && amount > 0) {
            if (src != address(0)) {
                // 如果src不为零地址,将src身上的委托投票总数量减去amount
                (uint256 oldWeight, uint256 newWeight) = _writeCheckpoint(_checkpoints[src], _subtract, amount);
                // 抛出emit
                emit DelegateVotesChanged(src, oldWeight, newWeight);
            }

            if (dst != address(0)) {
                // 如果dst不为零地址,将dst身上的委托投票总数量加上amount
                (uint256 oldWeight, uint256 newWeight) = _writeCheckpoint(_checkpoints[dst], _add, amount);
                // 抛出emit
                emit DelegateVotesChanged(dst, oldWeight, newWeight);
            }
        }
    }

    // 更新某委托目标地址获得的总委托票数的快照记录。
    // 注:更新token的总发行量的快照复用此函数
    function _writeCheckpoint(
        // 委托目标地址的总票数Checkpoint数组的storage引用
        Checkpoint[] storage ckpts,
        // 函数传参,用于区别做加法还是减法
        function(uint256, uint256) view returns (uint256) op,
        // 票数增量
        uint256 delta
    ) private returns (uint256 oldWeight, uint256 newWeight) {
        // 获取Checkpoint数组长度
        uint256 pos = ckpts.length;
        // oldCkpt为Checkpoint数组中最后一个元素。如果数组中无元素,oldCkpt为零值Checkpoint
        Checkpoint memory oldCkpt = pos == 0 ? Checkpoint(0, 0) : _unsafeAccess(ckpts, pos - 1);
        // oldWeight为委托目标地址身上原总票数
        oldWeight = oldCkpt.votes;
        // newWeight为委托目标地址身上更新后的总票数
        newWeight = op(oldWeight, delta);

        if (pos > 0 && oldCkpt.fromBlock == block.number) {
            // 如果委托目标地址身上原来就存在总票数 且 其最近的Checkpoint产生的区块高度为当前区块高度(即当前区块中,本交易之前的交易已为该委托目标创建了一个新的Checkpoint),直接修改该Checkpoint.votes为更新后的总票数
            // 更新后票数以uint224形式存储
            // 注:当前高度的Checkpoint一定是位于Checkpoint数组队尾
            _unsafeAccess(ckpts, pos - 1).votes = SafeCast.toUint224(newWeight);
        } else {
            // 如果委托目标地址身上之前无总票数 或 其最近的Checkpoint产生的区块高度不是当前区块高度(即本区块中第一次修改该委托目标地址身上的票数),在其Checkpoint数组队尾插入一个新的Checkpoint。字段fromBlock为当前区块高度,字段votes为更新后的总票数(以uint224形式存储)
            ckpts.push(Checkpoint({fromBlock: SafeCast.toUint32(block.number), votes: SafeCast.toUint224(newWeight)}));
        }
    }

    // 封装加法到函数function(uint256, uint256) view returns (uint256)中,用于_writeCheckpoint()的传参
    function _add(uint256 a, uint256 b) private pure returns (uint256) {
        return a + b;
    }

    // 封装减法到函数function(uint256, uint256) view returns (uint256)中,用于_writeCheckpoint()的传参
    function _subtract(uint256 a, uint256 b) private pure returns (uint256) {
        return a - b;
    }

    // 无边界检查地获取Checkpoint数组中索引为pos的storage引用
    // 注:由于没有边界检查,所以传参时要保证pos < ckpts.length
    function _unsafeAccess(Checkpoint[] storage ckpts, uint256 pos) private pure returns (Checkpoint storage result) {
        assembly {
            // 将ckpts的slot号存在第1~32字节的内存中
            mstore(0, ckpts.slot)

            // keccak256(0, 0x20): 存在第0~32字节的内存中的内容取hash,即将ckpts的slot号取hash。该值为ckpts中索引为0的元素对应的slot号
            // add(keccak256(0, 0x20), pos): 该值为ckpts中索引为pos的元素对应的slot号
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

foundry代码验证:

contract ERC20VotesTest is Test {
    MockERC20Votes private _testing = new MockERC20Votes("test name", "test symbol");
    address private user1 = address(1);
    address private user2 = address(2);
    address private user3 = address(3);

    event DelegateChanged(address indexed delegator, address indexed fromDelegate, address indexed toDelegate);
    event DelegateVotesChanged(address indexed delegate, uint256 previousBalance, uint256 newBalance);

    function test_Delegate() external {
        // case 1: first delegation without balance
        assertEq(_testing.delegates(address(this)), address(0));
        vm.expectEmit(true, true, true, false, address(_testing));
        emit DelegateChanged(address(this), address(0), user1);

        _testing.delegate(user1);
        assertEq(_testing.delegates(address(this)), user1);
        // no votes in user1
        assertEq(_testing.getVotes(user1), 0);
        // no Checkpoint generated
        assertEq(_testing.numCheckpoints(user1), 0);

        // case 2: first delegate with balance
        _testing.mint(user1, 1024);
        assertEq(_testing.delegates(user1), address(0));

        vm.expectEmit(true, true, true, false, address(_testing));
        emit DelegateChanged(user1, address(0), user2);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user2, 0, 1024);

        vm.prank(user1);
        _testing.delegate(user2);
        assertEq(_testing.delegates(user1), user2);
        // 1024 votes in user2
        assertEq(_testing.getVotes(user2), 1024);
        // 1 Checkpoint generated
        assertEq(_testing.numCheckpoints(user2), 1);
        MockERC20Votes.Checkpoint memory ckpt = _testing.checkpoints(user2, 0);
        assertEq(ckpt.fromBlock, 1);
        assertEq(ckpt.votes, 1024);

        // case 3: delegate with balance not first
        vm.roll(2);
        vm.expectEmit(true, true, true, false, address(_testing));
        emit DelegateChanged(user1, user2, user3);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user2, 1024, 0);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user3, 0, 1024);

        vm.prank(user1);
        _testing.delegate(user3);
        assertEq(_testing.delegates(user1), user3);
        // 1024 votes in user3
        assertEq(_testing.getVotes(user3), 1024);
        // 1 Checkpoint generated
        assertEq(_testing.numCheckpoints(user3), 1);
        ckpt = _testing.checkpoints(user3, 0);
        assertEq(ckpt.fromBlock, 2);
        assertEq(ckpt.votes, 1024);
        // 0 votes in user2
        assertEq(_testing.getVotes(user2), 0);
        // 1 Checkpoint generated
        assertEq(_testing.numCheckpoints(user2), 2);
        ckpt = _testing.checkpoints(user2, 1);
        assertEq(ckpt.fromBlock, 2);
        assertEq(ckpt.votes, 0);
    }
}

2.3 delegateBySig(address delegatee, uint256 nonce, uint256 expiry, uint8 v, bytes32 r, bytes32 s)

使用线下签名的方式,signer委托投票给delegatee(msg.sender可以是任何人)。

注:结构化数据的链下签名+链上验证详解,参见:https://learnblockchain.cn/article/6464

    function delegateBySig(
        // 委托投票的接受者地址
        address delegatee,
        // signer本次的线下签名nonce值
        uint256 nonce,
        // 该签名的过期时间戳
        uint256 expiry,
        // v, r, s构成整个签名
        uint8 v,
        bytes32 r,
        bytes32 s
    ) public virtual override {
        // 要求当前时间戳不可大于签名过期时间
        require(block.timestamp <= expiry, "ERC20Votes: signature expired");
        // 还原格式化数据签名的signer地址
        // 结构化数据为:
        // struct Delegation {
        //      address delegatee;
        //      uint256 nonce;
        //      uint256 expiry;
        // }
        // keccak256(abi.encode(_DELEGATION_TYPEHASH, delegatee, nonce, expiry))为struct hash
        // 注:结构化数据签名详解参见https://learnblockchain.cn/article/6464
        address signer = ECDSA.recover(
            _hashTypedDataV4(keccak256(abi.encode(_DELEGATION_TYPEHASH, delegatee, nonce, expiry))),
            v,
            r,
            s
        );
        // 要求合约内记录的signer签名nonce值与传入的nonce值一致
        require(nonce == _useNonce(signer), "ERC20Votes: invalid nonce");
        // signer委托投票给delegatee
        _delegate(signer, delegatee);
    }

foundry代码验证:

contract ERC20VotesTest is Test {
    using ECDSA for bytes32;

    MockERC20Votes private _testing = new MockERC20Votes("test name", "test symbol");
    address private user1 = address(1);
    address private user2 = address(2);
    bytes32 private constant _DELEGATION_TYPEHASH = keccak256("Delegation(address delegatee,uint256 nonce,uint256 expiry)");

    function test_DelegateBySig() external {
        // case 1: the signer has no balance
        uint privateKey = 1;
        address signer = vm.addr(privateKey);
        address delegatee = user1;
        uint nonce = 0;
        uint expiry = 1024;
        (uint8 v, bytes32 r, bytes32 s) = _getTypedDataSignature(privateKey, delegatee, nonce, expiry);

        vm.expectEmit(true, true, true, false, address(_testing));
        emit DelegateChanged(signer, address(0), delegatee);

        _testing.delegateBySig(delegatee, nonce, expiry, v, r, s);
        assertEq(_testing.delegates(signer), delegatee);
        assertEq(_testing.getVotes(delegatee), 0);

        // case 2: the signer has a balance
        _testing.mint(signer, 100);
        delegatee = user2;
        nonce++;
        (v, r, s) = _getTypedDataSignature(privateKey, delegatee, nonce, expiry);

        vm.expectEmit(true, true, true, false, address(_testing));
        emit DelegateChanged(signer, user1, delegatee);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user1, 100, 0);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(delegatee, 0, 100);

        _testing.delegateBySig(delegatee, nonce, expiry, v, r, s);
        assertEq(_testing.delegates(signer), delegatee);

        // revert with invalid nonce
        vm.expectRevert("ERC20Votes: invalid nonce");
        _testing.delegateBySig(delegatee, nonce, expiry, v, r, s);

        // revert with expired signature
        nonce++;
        (v, r, s) = _getTypedDataSignature(privateKey, delegatee, nonce, expiry);

        vm.warp(expiry + 1);
        vm.expectRevert("ERC20Votes: signature expired");
        _testing.delegateBySig(delegatee, nonce, expiry, v, r, s);
    }

        // get signature of the structural data
    function _getTypedDataSignature(
        uint signerPrivateKey,
        address delegatee,
        uint nonce,
        uint expiry
    ) private view returns (uint8, bytes32, bytes32){
        bytes32 structHash = keccak256(abi.encode(
            _DELEGATION_TYPEHASH,
            delegatee,
            nonce,
            expiry
        ));

        bytes32 digest = _testing.DOMAIN_SEPARATOR().toTypedDataHash(structHash);
        return vm.sign(signerPrivateKey, digest);
    }
}

2.4 _maxSupply() internal && _mint(address account, uint256 amount) internal && _burn(address account, uint256 amount) internal

  • _maxSupply() internal:获取本token的最大供应量。由于Checkpoint中的votes为uint224,而votes与token的兑换比例为1:1。所以,token的最大供应量也不能超过uint224的最大值;
  • _mint(address account, uint256 amount) internal:为account地址增发数量为amount的token;
  • _burn(address account, uint256 amount) internal:销毁掉account名下数量为amount的token。
    function _maxSupply() internal view virtual returns (uint224) {
        // 最大供应量为uint224类型的最大值,即2^224-1
        return type(uint224).max;
    }

    function _mint(address account, uint256 amount) internal virtual override {
        // 调用ERC20._mint()为account增发token
        super._mint(account, amount);
        // 要求增发后,token总供应量不能大于上限值,即type(uint224).max
        require(totalSupply() <= _maxSupply(), "ERC20Votes: total supply risks overflowing votes");
        // 更新token总发行量的快照,增量为account,方式为增加
        _writeCheckpoint(_totalSupplyCheckpoints, _add, amount);
    }

    function _burn(address account, uint256 amount) internal virtual override {
        // 调用ERC20._burn()来销毁account名下数量为amount的token
        super._burn(account, amount);
        // 更新token总发行量的快照,增量为account,方式为减少
        _writeCheckpoint(_totalSupplyCheckpoints, _subtract, amount);
    }

foundry代码验证:

contract ERC20VotesTest is Test {
    MockERC20Votes private _testing = new MockERC20Votes("test name", "test symbol");
    address private user1 = address(1);

    function test_MintAndBurnAndMaxSupply() external {
        // test for {_maxSupply}
        assertEq(_testing.maxSupply(), type(uint224).max);

        // test for {_mint}
        // case 1: receiver has no delegatee
        assertEq(_testing.totalSupply(), 0);
        _testing.mint(address(this), 1);
        assertEq(_testing.totalSupply(), 1);
        assertEq(_testing.balanceOf(address(this)), 1);

        // revert if total supply exceeds the ceiling
        vm.expectRevert("ERC20Votes: total supply risks overflowing votes");
        _testing.mint(user1, type(uint224).max);

        // case 2: receiver has a delegatee
        vm.prank(user1);
        _testing.delegate(address(this));
        assertEq(_testing.getVotes(address(this)), 0);

        _testing.mint(user1, 2);
        assertEq(_testing.totalSupply(), 1 + 2);
        assertEq(_testing.balanceOf(user1), 0 + 2);
        // delegatee's votes increased
        assertEq(_testing.getVotes(address(this)), 0 + 2);

        // revert if total supply exceeds the ceiling (happens in {_afterTokenTransfer})
        vm.expectRevert("SafeCast: value doesn't fit in 224 bits");
        _testing.mint(user1, type(uint224).max);

        // test for {_burn}
        // case 3: receiver has no delegatee
        _testing.burn(address(this), 1);
        assertEq(_testing.totalSupply(), 3 - 1);

        // case 4: receiver has a delegatee
        _testing.burn(user1, 1);
        assertEq(_testing.totalSupply(), 2 - 1);
        // delegatee's votes decreased
        assertEq(_testing.getVotes(address(this)), 2 - 1);
    }
}

2.5 _afterTokenTransfer( address from, address to, uint256 amount) internal

重写ERC20._afterTokenTransfer(),在每次底层出现token转移后自动触发。

    function _afterTokenTransfer(
        address from,
        address to,
        uint256 amount
    ) internal virtual override {
        // 调用ERC20._afterTokenTransfer()
        super._afterTokenTransfer(from, to, amount);
        // 将from的委托投票目标地址名下数量为amount的票转移给to的委托投票目标地址
        // 即转移token数量与转移投票的比例为1:1
        _moveVotingPower(delegates(from), delegates(to), amount);
    }

foundry代码验证:

contract ERC20VotesTest is Test {
    MockERC20Votes private _testing = new MockERC20Votes("test name", "test symbol");
    address private user1 = address(1);
    address private user2 = address(2);
    address private user3 = address(3);
    address private user4 = address(4);

    event DelegateChanged(address indexed delegator, address indexed fromDelegate, address indexed toDelegate);
    event DelegateVotesChanged(address indexed delegate, uint256 previousBalance, uint256 newBalance);

    function test_AfterTokenTransfer() external {
        _testing.mint(address(this), 100);
        _testing.delegate(user1);

        assertEq(_testing.delegates(address(this)), user1);
        assertEq(_testing.numCheckpoints(user1), 1);

        // test for {transfer}
        // case 1: 'to' has no delegatee
        vm.roll(2);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user1, 100, 100 - 1);

        _testing.transfer(user2, 1);
        assertEq(_testing.getVotes(user1), 100 - 1);

        // case 2: 'to' has a delegatee
        _testing.mint(user3, 100);
        vm.prank(user3);
        _testing.delegate(user4);

        vm.roll(3);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user1, 99, 99 - 1);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user4, 100, 100 + 1);

        _testing.transfer(user3, 1);
        assertEq(_testing.getVotes(user1), 99 - 1);
        assertEq(_testing.getVotes(user4), 100 + 1);

        // test for {transferFrom}
        // case 3: 'to' has no delegatee
        vm.roll(4);
        assertEq(_testing.delegates(user2), address(0));

        _testing.approve(user1, 100);
        vm.startPrank(user1);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user1, 98, 98 - 1);

        _testing.transferFrom(address(this), user2, 1);

        // case 4: 'to' has a delegatee
        vm.roll(5);
        assertEq(_testing.delegates(user3), user4);

        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user1, 97, 97 - 1);
        vm.expectEmit(true, false, false, true, address(_testing));
        emit DelegateVotesChanged(user4, 101, 101 + 1);

        _testing.transferFrom(address(this), user3, 1);
    }
}

2.6 getPastVotes(address account, uint256 blockNumber) && getPastTotalSupply(uint256 blockNumber)

  • getPastVotes(address account, uint256 blockNumber):获取account地址在blockNumber区块高度时的总票数;
  • getPastTotalSupply(uint256 blockNumber):获取在blockNumber区块高度时的token总发行量。注:该值为在blockNumber区块高度时所有token的余额之和,而并非所有委托投票数之和。
    function getPastVotes(address account, uint256 blockNumber) public view virtual override returns (uint256) {
        // 要求传入的blockNumber不可大于当前区块高度
        require(blockNumber < block.number, "ERC20Votes: block not yet mined");
        // 返回account的Checkpoint数组中fromBlock最小于等于blockNumber的元素的votes值
        return _checkpointsLookup(_checkpoints[account], blockNumber);
    }

    function getPastTotalSupply(uint256 blockNumber) public view virtual override returns (uint256) {
        // 要求传入的blockNumber不可大于当前区块高度
        require(blockNumber < block.number, "ERC20Votes: block not yet mined");
        // 返回token总供应量Checkpoint数组中fromBlock最小于等于blockNumber的元素的votes值
        return _checkpointsLookup(_totalSupplyCheckpoints, blockNumber);
    }

    // 从按照fromBlock字段升序排列的Checkpoint数组中,找到小于等于blockNumber区块高度且
    function _checkpointsLookup(Checkpoint[] storage ckpts, uint256 blockNumber) private view returns (uint256) {        
        // 获取Checkpoint数组的长度
        uint256 length = ckpts.length;
        // 二分法下边界为0
        uint256 low = 0;
        // 二分法上边界为Checkpoint数组的长度
        uint256 high = length;

        if (length > 5) {
            // 如果Checkpoint数组的长度>5时
            // mid为数组总长度 - length的平方根
            uint256 mid = length - Math.sqrt(length);
            if (_unsafeAccess(ckpts, mid).fromBlock > blockNumber) {
                // 如果Checkpoint数组中索引为mid元素的fromBlock>blockNumber
                // 将high缩小到mid
                high = mid;
            } else {
                // 如果Checkpoint数组中索引为mid元素的fromBlock<=blockNumber
                // 将low提高到mid+1
                low = mid + 1;
            }
        }

        // 开始二分查找
        while (low < high) {
            // 如果low<high保持循环,否则跳出循环
            // mid为当前low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(ckpts, mid).fromBlock > blockNumber) {
                // 如果Checkpoint数组中索引为mid元素的fromBlock>blockNumber
                // 将high缩小到mid
                high = mid;
            } else {
                // 如果Checkpoint数组中索引为mid元素的fromBlock<=blockNumber
                // 将low提高到mid+1
                low = mid + 1;
            }
        }

        // 如果此时high为0,表示整个Checkpoint数组各元素的fromBlock都大于blockNumber。直接返回0;
        // 否则表示整个Checkpoint数组中有存在fromBlock<=blockNumber的元素且该元素在high索引对应的元素左边。返回索引为high-1的元素的votes值
        return high == 0 ? 0 : _unsafeAccess(ckpts, high - 1).votes;
    }

foundry代码验证:

contract ERC20VotesTest is Test {
    MockERC20Votes private _testing = new MockERC20Votes("test name", "test symbol");
    address private user1 = address(1);

    function test_GetPastVotesAndGetPastTotalSupply() external {
        // 6 Checkpoints of user1:
        //       block             votes             index
        //          2                10                0
        //          3                15                1
        //          6                19                2
        //          10               20                3
        //          11               23                4
        //          13               31                5
        //
        // 6 Checkpoints of total supply:
        //       block          total supply         index
        //          2                10                0
        //          3                15                1
        //          6                19                2
        //          10               20                3
        //          11               23                4
        //          13               31                5

        _testing.delegate(user1);
        vm.roll(2);
        _testing.mint(address(this), 10);
        vm.roll(3);
        _testing.mint(address(this), 15 - 10);
        vm.roll(6);
        _testing.mint(address(this), 19 - 15);
        vm.roll(10);
        _testing.mint(address(this), 20 - 19);
        vm.roll(11);
        _testing.mint(address(this), 23 - 20);
        vm.roll(13);
        _testing.mint(address(this), 31 - 23);
        vm.roll(20);

        // check {getPastVotes} && {getPastTotalSupply}
        assertEq(_testing.numCheckpoints(user1), 6);

        assertEq(_testing.getPastVotes(user1, 1), 0);
        assertEq(_testing.getPastTotalSupply(1), 0);

        assertEq(_testing.getPastVotes(user1, 2), 10);
        assertEq(_testing.getPastTotalSupply(2), 10);

        assertEq(_testing.getPastVotes(user1, 4), 15);
        assertEq(_testing.getPastTotalSupply(4), 15);

        assertEq(_testing.getPastVotes(user1, 6), 19);
        assertEq(_testing.getPastTotalSupply(6), 19);

        assertEq(_testing.getPastVotes(user1, 9), 19);
        assertEq(_testing.getPastTotalSupply(9), 19);

        assertEq(_testing.getPastVotes(user1, 10), 20);
        assertEq(_testing.getPastTotalSupply(10), 20);

        assertEq(_testing.getPastVotes(user1, 12), 23);
        assertEq(_testing.getPastTotalSupply(12), 23);

        assertEq(_testing.getPastVotes(user1, 13), 31);
        assertEq(_testing.getPastTotalSupply(13), 31);

        assertEq(_testing.getPastVotes(user1, 19), 31);
        assertEq(_testing.getPastTotalSupply(19), 31);

        // revert if block not mined
        vm.expectRevert("ERC20Votes: block not yet mined");
        _testing.getPastVotes(user1, 9999);
        vm.expectRevert("ERC20Votes: block not yet mined");
        _testing.getPastTotalSupply(9999);
    }
}

ps: 本人热爱图灵,热爱中本聪,热爱V神。 以下是我个人的公众号,如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章,喜欢的小伙伴或者老伙计可以支持一下! 如果需要转发,麻烦注明作者。十分感谢!

1.jpeg

公众号名称:后现代泼痞浪漫主义奠基人

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
Michael.W
Michael.W
0x93E7...0000
狂热的区块链爱好者