Convert nonce storage to a bitmap to reduce gas consumption

[ilikesymmetry]

I wasn't able to DM @wilsoncusack directly on twitter/warpcast so I guess this thought will go here! Sharing in case the team has not considered this change before and hope this can be helpful :).

There is an opportunity to further optimize the gas cost of using withdraw request nonces without compromising on the ability to process requests in parallel per-account or changing any interfaces. We can do this through a BitMap where instead of the storage being keyed by uint256 nonce and storing a bool, we key by a uint256 bucket and store 256 bits that let us pack 256 nonces into one slot. By reusing the same slot for multiple nonces, we are able to reduce gas cost by converting writing of new state (setting mapping value to true) into updating of existing state (flipping a bit within the word of one bucket).

---

Some napkin math on savings:

For every 256 nonces, we have to write 1 new word and can update 255 bits thereafter. Writing a new word is ~20k gas and updating an existing word is ~5k gas. The amortized cost of using a nonce becomes (1 • 20k + 255 • 5k) / 256 => 5.06k, which is basically the same ~15k gas savings difference between writing/updating. Of course there are other places of gas consumption in the paymaster flow that will make the net improvement less visible, but I generally rank storage-writing related optimizations worthwhile, especially for the scale of these Coinbase smart accounts.

Note that gas savings will only come if nonces are ordered sequentially by whatever offchain code is preparing withdraw requests to be able to re-use writing to the same slot many times.

---

Code changes:

The simplest approach is to just use the BitMap library offered by OpenZeppelin (linked above) and update the storage, external view function, and internal validation function:

mapping(address => BitMap) internal _nonceUsed;

function nonceUsed(address account, uint256 nonce) external view returns (bool) {
    return _nonceUsed[account].get(nonce);
}

function _validateRequest(address account, WithdrawRequest memory withdrawRequest) internal {
    BitMap storage bitMap = _nonceUsed[account];
    if (bitMap.get(withdrawRequest.nonce)) {
        revert InvalidNonce(withdrawRequest.nonce);
    }

    bitMap.set(withdrawRequest.nonce);

    // This is emitted ahead of fund transfer, but allows a consolidated code path
    emit MagicSpendWithdrawal(account, withdrawRequest.asset, withdrawRequest.amount, withdrawRequest.nonce);
}

If it's preferable to minimize dependencies or extra code unused from the library, one can also copy the logic in-line. Existing test cases will catch an incorrect copy+paste and auditors should also be able to follow.

---

Happy to make this contribution directly in a new PR if helpful and otherwise thanks for reading this!

[wilsoncusack]

This is a cool idea, thanks for the well written issue. I am hesitant that the gas (especially as we're focused on L2) is worth the added complexity. Open to reviewing a PR and seeing the gas savings if you want to put one up, though.

[ilikesymmetry]

I don't have permissions to post a new branch/PR so I just made a new repo on my github with the new commits on my branch. If I get perms to make a branch here, I can push my PR for an easy merge if you think it's worth it!

Change summary:

1. Add new test to do 256 validations
2. Add new gas snapshot on the current implementation
3. Made the proposed changes to the paymaster contract

If you run forge snapshot --diff .gas-snapshot, you'll see the gas savings from the change which look like ~50% on validatePaymasterUserOp.

Saving 5,607,028 gas over 256 evaluations averages out to 21,902 gas saved on validatePaymasterUserOp with this change. Note that the first validation per-account will not experience any savings, but subsequent validations will leverage the re-used slot if the offchain nonce preparation just increments per-account.

[wilsoncusack]

you can fork it and if you PR it'll show up here :) and ok thanks we'll consider

[ilikesymmetry]

Oh cool I didn't know I could do that. Just made a new PR here

[wilsoncusack]

Thanks for this! I don't think we're going to adopt just due to scope of change, but will consider for future.