Checkpoint Mechanism in ERC20Votes

Support Contracts
1

How ERC20Votes contract checkpoints are working? Because as I can see in _checkpointsLookup it is using binary search to get past votes (getPastVotes) of an address. So if there are too many checkpoints (user is transferring tokens many times, which sounds practical), we will encounter out of gas error. What is the possible solution for this?

2

It's unlikely to run out of gas because the cost of the binary search grows logarithmically. If it ever runs out of gas, it can be recovered by transferring the tokens to a new address.

That said, we're likely introducing a change in ERC20Votes soon that will prioritize the lookup of more recent checkpoints, and make it less likely to run out of gas in that scenario.

1 Like
3

It would be great if lookup limit is known and we set low=(length-limit) instead of low=0. (e.g. lookup is working upto 1M checkpoints and then we are encountering out of gas then instead of starting from 0 to length, by slicing the array to recent 1M checkpoints would work as per my guess if we don't want to search beyond limit)

function _checkpointsLookup(Checkpoint[] storage ckpts, uint256 blockNumber, uint256 limit) private view returns (uint256) {
        // We run a binary search to look for the earliest checkpoint taken after `blockNumber`.
        //
        // During the loop, the index of the wanted checkpoint remains in the range [low-1, high).
        // With each iteration, either `low` or `high` is moved towards the middle of the range to maintain the invariant.
        // - If the middle checkpoint is after `blockNumber`, we look in [low, mid)
        // - If the middle checkpoint is before or equal to `blockNumber`, we look in [mid+1, high)
        // Once we reach a single value (when low == high), we've found the right checkpoint at the index high-1, if not
        // out of bounds (in which case we're looking too far in the past and the result is 0).
        // Note that if the latest checkpoint available is exactly for `blockNumber`, we end up with an index that is
        // past the end of the array, so we technically don't find a checkpoint after `blockNumber`, but it works out
        // the same.
        uint256 high = ckpts.length;
        uint256 low = 0;

        if (ckpts.length > limit && ckpts[ckpts.length-limit].fromBlock < blockNumber) {  
            low = ckpts.length - limit;
        }
        
        while (low < high) {
            uint256 mid = Math.average(low, high);
            if (ckpts[mid].fromBlock > blockNumber) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return high == 0 ? 0 : ckpts[high - 1].balance;
    }
4

We want to search through the entire array.