Alternating Nonce Bitmap
Overview
To allow for more flexibility and easier future integrations with different solver networks we allow multiple solver quotes to land in the same block, but only the first one gets discounted execution.
Alternating Nonce Bitmap is a gas-efficient mechanism to prevent the replay of HOT attacks on chain.
Simple Solution to Replay Attacks
The simple solution to this problem is to just store the hash of each solver quote in a mapping onchain. Every time a new quotes comes in, you check if this hash has already been used.
Another variation of this solution is to use unordered nonces, and store these nonces onchain whenever any one of them is used.
These solutions are great because they are simple and quick to implement, but they come with a major gas tradeoff.
Storing the nonce/hash on chain would require a cold storage write of a non-zero storage slot, which costs around 22,000 gas.
One of our main design goals for the HOT swaps was to minimize gas, while providing a substantial amount of protection against mispriced HOT quotes, so that we can be competitive with cheaper AMMs like UniV2 and even some OTC RFQ smart contracts. Adding this cold storage write could be a substantial deviation from that goal.
It would also be cheaper for a liquidity manager to just update the oracle price in a separate transaction because the fixed cost of making a new transaction is 21,000 gas.
To solve this problem of adding a cold storage write to each solver swap, we aim to design a new replay protection mechanism with the following goal:
No additional cold storage writes.
As simple as possible to implement onchain
Does not add any new trust assumptions on the manager.
Alternating Bitmap Nonce Solution
It is a fundamental principle that if the quotes persisted forever, then to make sure that no quote is replayed on chain, we would have to store the hashes of all processed quotes to date in a mapping, and check that mapping before any new quote is processed.
But our system has 2 unique properties, that allow us to bypass this:
All quotes will definitely expire within the expiry time signed by the manager. This expiry time is bounded to be less than a maximum value ( currently 10 minutes ) by the smart contract checks.
Each block will only process a maximum of N HOT quotes each block.
This means that we only have to store the nonce for the active quotes in the smart contract, all expired quotes can anyway never be replayed.
Therefore we can reduce the storage requirements of our nonce algorithm to just 1 slot, which is large enough to account for all active quotes currently in the system.
Note: By active quotes, we mean all quotes signed by the liquidity manager which have not expired yet. It does not matter if they have been put onchain or not, as long as the current time < expiry time of the quote, the quote is considered to be active.
We know for sure that a manager would never sign more than 256 quotes that haven’t expired, it won’t make any sense to do so, since only a few quotes can go on chain in the same block, and signing more than 3-4 quotes at the same time will most likely not happen in practice.
HOT Storage
We maintain a bitmap of 1 storage slot ( i.e 256 bits ) in the smart contract. Out of these, 56 bits are reserved for the Alternating Nonce Bitmap.
HOT Struct
We also add the following fields to the HOT quote struct:
Nonce Value: N ( in the range 0 to 55 )
Expected Flag: F ( {0,1} )
Processing of Quotes
When a new quote is put onchain, the HOT contract makes all necessary checks and ensures that the quote has not expired.
Check that the Nth bit should be equal to F. If this is true, then the quote is valid, otherwise, it is considered to be a replay and tx reverts.
Flip the Nth bit.
Signer Nonce Selection
At the time of signing a new quote, the backend first checks its list of all active quotes according to the current time.
Using this list it finds a free nonce value and assigns it to the new quote.
Note: A free nonce value means that either this nonce value was never used before, or the quote that was assigned this nonce value before has already expired.
It is trivial to make these checks on the backend because in practice we will never have more than 3-4 active quotes at the same time.
Once a free nonce ( N ) has been found for the new quote, the manager checks the current state of the bitmap onchain, and finds the flag value at the Nth bit.
It then assigns this flag value to the Expected Flag field in the HOT quote, and signs the quote to send to the solver.
Using this mechanism, we can guarantee that no solver quotes will be replayed on chain, under one assumption - The backend chooses the nonce correctly.
Also note that in practice this bitmap won’t require any new storage writes, because we will reduce the bitmap size to 56 bits ( a maximum of 56 active quotes is still more than enough for our current system ), and then tight pack it with the Solver Write Slot.
Last updated
