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.
---
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
Usually in comments to accompany the relevant code. In this case it's not documented...
