Full Knowledge User Proofs: working with storage without paying for gas
· Problem statement
· Standard approach
· Let’s get schwifty
· Limitations
· Bonus 1: cheaper hash computation
· Conclusion
· Acknowledgments
One of the problems the Yield mentorship program offers you to solve is building a multi-collateral vault. It casually mentions gas efficiency but doesn’t set any goals. Naturally, I had to see how low I can push the gas usage.
Problem statement
Here’s a simplified version of it: a (single user) vault, the user can deposit tokens from the ‘blessed’ list as collateral, and borrow DAI against it.
Let’s try to optimize for borrow() gas efficiency! To make things interesting, we’ll assume the user has 100 different collateral types added to the vault.
Standard approach
A standard approach with gas efficiency in mind might look like this (leaving out access control and multi-user support):
borrow() simply iterates over all collaterals the user deposited, adds up their prices, and allows the user to borrow up to that amount.
We can’t afford to call an external oracle for every deposit the user has (each *CALL uses at least 2600 gas), so we’ll store asset prices in Assets struct and have an off-chain process that triggers another contract that calls the oracles and then setAssetPrices() every 10 minutes. No external calls in borrow() -> lower gas cost for users.
We could task the same off-chain process with recomputing the user’s borrow limit, but this doesn’t scale to multi-user vaults.
All in all, each call to borrow() costs us ~600k gas with 100 assets and 53k with 1 asset.
Let’s get schwifty
Accessing the contract storage is one of the most expensive operations in Ethereum. And we do that quite a lot in our borrow() function: at least 100 times to fetch deposit balance/asset ID and another 100 times to fetch asset prices. Every storage read costs us 2100, so that’s 2100 * 200 = 400k gas. We can squeeze Asset and Deposit structures a bit and maybe reduce that by half, but 200k is still a lot.
Fortunately, borrow() doesn’t have to access storage at all. If assets and deposits are available in calldata, we can just read them from there. Accessing calldata costs just 3 gas, it doesn’t get lower than that.
It is trivial to implement, borrow() looks almost identical to the initial version:
The client side:
We simply ask the user to give us the full data our function needs to operate.
Now, there’s one obvious problem: the user can lie about their deposits and we can’t blindly trust them. We need the user to provide us proof that _deposits and _assets are identical todeposits and assets. There’s an easy way to do this: compare hashes of the stored and user-provided values
Full Knowledge User Proof (FKUP) brings down the gas usage of borrow() from ~600k to 285k with 100 assets and from 53k to 52k with 1 asset.
Limitations
FKUP is not a silver bullet and has a bit of limitation:
- if the user of your contract is another contract, gas savings are gone. Unless they adopt the same pattern and make
Asset[] calldata _assets, Deposit[] calldata _depositpart of their interface and simply pass that data to you - if your function does significantly more than just crunch some numbers from storage (imagine
borrow()calling external oracle for prices), gas savings will still be there, but they’ll be shadowed by the cost of external calls - every time
_assetsor_depositchanges, their hashes need to be recomputed. If your data changes often,borrow()will still be gas-efficient, butdeposit()andsetAssetPrices()might offset these savings. - If the data changes often, there’s a chance user’s data won’t match with the recent contract data. If that’s not desirable,
borrow()can fall back to reading from storage in case of hash mismatch, instead of reverting.
Bonus 1: cheaper hash computation
function x(uint256 amount, Asset[] calldata _assets) public {
require(keccak256(abi.encode(_assets)) == assetsChecksum, "assets checksum");
}We don’t need abi.encode() call here. Why? _assets is in calldata and it’s already serialized with abi.encode() on the client side. The only challenge is that keccak256 can’t read from calldata, so we use a bit of assembly to copy _assets to memory first. In total, we save another 50k gas:
234k gas with 100 assets, 51k gas with 1 asset.
There is a way to bring down total gas usage to 150k, I’ll save it for the next post.
Conclusion
We tested 3 versions of the borrow() function:
- Vanilla one, easy to understand, uses almost 600k gas
- Vanilla FKUP: still easy to understand, uses 285k gas
- Lightly optimized FKUP: a bit harder to understand, but still OK, 234k gas
Vanilla FKUP is probably the best bang for the buck as it doesn’t use Yul and offers 2x gas savings.
Due to limitations, it’s not a one-size-fits-all pattern, but it could be handy.
The next post will add one more version in mix of Solidity and Yul and go into a bit of detail with dapptools and a comparison to C++.
Acknowledgments
Big thanks to the Yield protocol for smart contracts mentorship and Alberto for being an awesome mentor. Check out the EthernautDAO if you’re interested in being a mentor or a mentee.
devtooligan for helping to hash out the early version of this idea and editing this post.
