In https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/Checkpoints.sol , used in https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/governance/utils/Votes.sol there is a while loop in _upperBinaryLookup .

That seems like a potential vulnerability. What if a grief attacker delegates enough times that searching through it in log(n) still exceeds the block gas limit?

Thanks in advance?

Antoine

This is really not feasible. With 1 million checkpoints gas will not even be 100k gas and with recent optimizations it will be half that. See the benchmarks in this PR:

`OpenZeppelin:master`

← `frangio:optim-recent`

opened 01:12AM - 02 Sep 22 UTC

This PR optimizes `getPastVotes` so that for recent checkpoints it has lower gas… cost than the worst case.
The worst case runs in O(log n) time, but delegates can have large numbers of checkpoints: a quick search led us to find one with 8500 checkpoints, which adds around 43k gas to a vote.
In the context of governance, since there is a voting period, `getPastVotes` will be invoked with a relatively recent block which will be near the end of the checkpoints array.
We modify `getPastVotes` so that it first checks to see if the sought checkpoint is a recent checkpoint, if so does a binary search among those, and otherwise does a binary search on the rest of the array. We define the recent checkpoints as the last sqrt(n), where n is the number of checkpoints. Thus, the best case cost of `getPastVotes` is half that of the worst case, though it remains logarithmic.
![](https://user-images.githubusercontent.com/481465/188224225-a6e1507a-1f0b-4c30-8367-bdef1c7e00c5.png)
---
Some other changes bundled here:
- Changed ERC20Votes to use unsafe array accesses to save on bounds checks.
- Renamed `getAtRecentBlock` to `getAtProbablyRecentBlock`, to indicate that the function works even for non-recent blocks.
- Removed `upperLookupRecent` for other Trace/Checkpoints types, since we won't be using it and if the keys are not block numbers or timestamps it is not clear that they are worth it.

2 Likes

Okay thank you for the benchmark
Is there a place where you document all these security considerations for future audits?

Usually in comments to accompany the relevant code. In this case it's not documented...