All you can cache
When using rollups the cost of a byte in the transaction is a lot more expensive than the cost of a storage slot. Therefore, it makes sense to cache as much information as possible on chain.
In this article you learn how to create and use a caching contract in such a way that any parameter value that is likely to be used multiple times will be cached and available for use (after the first time) with a much smaller number of bytes, and how to write off chain code that uses this cache.
If you want to skip the article and just see the source code, it is here. The development stack is Foundry.
Overall design
For the sake of simplicity we'll assume all transaction parameters are uint256
, 32 bytes long. When we receive a transaction, we'll parse each parameter like this:
If the first byte is
0xFF
, take the next 32 bytes as a parameter value and write it to the cache.If the first byte is
0xFE
, take the next 32 bytes as a parameter value but do not write it to the cache.For any other value, take the top four bits as the number of additional bytes, and the bottom four bits as the most significant bits of the cache key. Here are some examples:
Bytes in calldata Cache key 0x0F 0x0F 0x10,0x10 0x10 0x12,0xAC 0x02AC 0x2D,0xEA, 0xD6 0x0DEAD6
Cache manipulation
The cache is implemented in Cache.sol
. Let's go over it line by line.
1// SPDX-License-Identifier: UNLICENSED2pragma solidity ^0.8.13;345contract Cache {67 bytes1 public constant INTO_CACHE = 0xFF;8 bytes1 public constant DONT_CACHE = 0xFE;9Kopiera
These constants are used to interpret the special cases where we provide all the information and either want it written into the cache or not. Writing into the cache requires two SSTORE
operations into previously unused storage slots at a cost of 22100 gas each, so we make it optional.
12 mapping(uint => uint) public val2key;3Kopiera
A mapping between the values and their keys. This information is necessary to encode values before you send out the transaction.
1 // Location n has the value for key n+1, because we need to preserve2 // zero as "not in the cache".3 uint[] public key2val;4Kopiera
We can use an array for the mapping from keys to values because we assign the keys, and for simplicity we do it sequentially.
1 function cacheRead(uint _key) public view returns (uint) {2 require(_key <= key2val.length, "Reading uninitialize cache entry");3 return key2val[_key-1];4 } // cacheRead5Kopiera
Read a value from the cache.
1 // Write a value to the cache if it's not there already2 // Only public to enable the test to work3 function cacheWrite(uint _value) public returns (uint) {4 // If the value is already in the cache, return the current key5 if (val2key[_value] != 0) {6 return val2key[_value];7 }8Kopiera
There is no point in putting the same value in the cache more than once. If the value is already there, just return the existing key.
1 // Since 0xFE is a special case, the largest key the cache can2 // hold is 0x0D followed by 15 0xFF's. If the cache length is already that3 // large, fail.4 // 1 2 3 4 5 6 7 8 9 A B C D E F5 require(key2val.length+1 < 0x0DFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,6 "cache overflow");7Kopiera
I don't think we'll ever get a cache that big (approximately 1.8*1037 entries, which would require about 1027 TB to store). However, I'm old enough to remember "640kB would always be enough". This test is very cheap.
1 // Write the value using the next key2 val2key[_value] = key2val.length+1;3Kopiera
Add the reverse lookup (from the value to the key).
1 key2val.push(_value);2Kopiera
Add the forward lookup (from the key to the value). Because we assign values sequentially we can just add it after the last array value.
1 return key2val.length;2 } // cacheWrite3Kopiera
Return the new length of key2val
, which is the cell where the new value is stored.
1 function _calldataVal(uint startByte, uint length)2 private pure returns (uint)3Kopiera
This function reads a value from the calldata of arbitrary length (up to 32 bytes, the word size).
1 {2 uint _retVal;34 require(length < 0x21,5 "_calldataVal length limit is 32 bytes");6 require(length + startByte <= msg.data.length,7 "_calldataVal trying to read beyond calldatasize");8Kopiera
This function is internal, so if the rest of the code is written correctly these tests are not required. However, they don't cost much so we might as well have them.
1 assembly {2 _retVal := calldataload(startByte)3 }4Kopiera
This code is in Yul. It reads a 32 byte value from the calldata. This works even if the calldata stops before startByte+32
because uninitialized space in EVM is considered to be zero.
1 _retVal = _retVal >> (256-length*8);2