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(opens in a new tab). The development stack is Foundry(opens in a new tab).
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
(opens in a new tab). 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;9Copiar
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
(opens in a new tab) operations into previously unused storage slots at a cost of 22100 gas each, so we make it optional.
12 mapping(uint => uint) public val2key;3Copiar
A mapping(opens in a new tab) 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;4Copiar
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 } // cacheRead5Copiar
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 }8Copiar
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");7Copiar
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"(opens in a new tab). This test is very cheap.
1 // Write the value using the next key2 val2key[_value] = key2val.length+1;3Copiar
Add the reverse lookup (from the value to the key).
1 key2val.push(_value);2Copiar
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 } // cacheWrite3Copiar
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)3Copiar
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");8Copiar
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 }4Copiar
This code is in Yul(opens in a new tab). 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);2Copiar
We don't necessarily want a 32 byte value. This gets rid of the excess bytes.
1 return _retVal;2 } // _calldataVal345 // Read a single parameter from the calldata, starting at _fromByte6 function _readParam(uint _fromByte) internal7 returns (uint _nextByte, uint _parameterValue)8 {9Copiar
Read a single parameter from the calldata. Note that we need to return not just the value we read, but also the location of the next byte because parameters can range from 1 byte long to 33 bytes.
1 // The first byte tells us how to interpret the rest2 uint8 _firstByte;34 _firstByte = uint8(_calldataVal(_fromByte, 1));5Copiar
Solidity tries to reduce the number of bugs by forbidding potentially dangerous implicit type conversions(opens in a new tab). A downgrade, for example from 256 bits to 8 bits, needs to be explicit.
12 // Read the value, but do not write it to the cache3 if (_firstByte == uint8(DONT_CACHE))4 return(_fromByte+33, _calldataVal(_fromByte+1, 32));56 // Read the value, and write it to the cache7 if (_firstByte == uint8(INTO_CACHE)) {8 uint _param = _calldataVal(_fromByte+1, 32);9 cacheWrite(_param);10 return(_fromByte+33, _param);11 }1213 // If we got here it means that we need to read from the cache1415 // Number of extra bytes to read16 uint8 _extraBytes = _firstByte / 16;17Exibir tudoCopiar
Take the lower nibble(opens in a new tab) and combine it with the other bytes to read the value from the cache.
1 uint _key = (uint256(_firstByte & 0x0F) << (8*_extraBytes)) +2 _calldataVal(_fromByte+1, _extraBytes);34 return (_fromByte+_extraBytes+1, cacheRead(_key));56 } // _readParam789 // Read n parameters (functions know how many parameters they expect)10 function _readParams(uint _paramNum) internal returns (uint[] memory) {11Exibir tudoCopiar
We could get the number of parameters we have from the calldata itself, but the functions that call us know how many parameters they expect. It's easier to let them tell us.
1 // The parameters we read2 uint[] memory params = new uint[](_paramNum);34 // Parameters start at byte 4, before that it's the function signature5 uint _atByte = 4;67 for(uint i=0; i<_paramNum; i++) {8 (_atByte, params[i]) = _readParam(_atByte);9 }10Exibir tudoCopiar
Read the parameters until you have the number you need. If we go past the end of the calldata, _readParams
will revert the call.
12 return(params);3 } // readParams45 // For testing _readParams, test reading four parameters6 function fourParam() public7 returns (uint256,uint256,uint256,uint256)8 {9 uint[] memory params;10 params = _readParams(4);11 return (params[0], params[1], params[2], params[3]);12 } // fourParam13Exibir tudoCopiar
One big advantage of Foundry is that it allows tests to be written in Solidity (see Testing the cache below). This makes unit tests a lot easier. This is a function that reads four parameters and returns them so the test can verify they were correct.
1 // Get a value, return bytes that will encode it (using the cache if possible)2 function encodeVal(uint _val) public view returns(bytes memory) {3Copiar
encodeVal
is a function that off-chain code calls to help create calldata that uses the cache. It receives a single value and returns the bytes that encode it. This function is a view
, so it does not require a transaction and when called externally does not cost any gas.
1 uint _key = val2key[_val];23 // The value isn't in the cache yet, add it4 if (_key == 0)5 return bytes.concat(INTO_CACHE, bytes32(_val));6Copiar
In the EVM(opens in a new tab) all uninitialized storage is assumed to be zeros. So if we look for the key for a value that isn't there, we get a zero. In that case the bytes that encode it are INTO_CACHE
(so it will be cached next time), followed by the actual value.
1 // If the key is <0x10, return it as a single byte2 if (_key < 0x10)3 return bytes.concat(bytes1(uint8(_key)));4Copiar
Single bytes are the easiest. We just use bytes.concat
(opens in a new tab) to turn a bytes<n>
type into a byte array which can be any length. Despite the name, it works fine when provided with just one argument.
1 // Two byte value, encoded as 0x1vvv2 if (_key < 0x1000)3 return bytes.concat(bytes2(uint16(_key) | 0x1000));4Copiar
When we have a key that is less than 163, we can express it in two bytes. We first convert _key
, which is a 256 bit value, to a 16 bit value and use logical or to add the number of extra bytes to the first byte. Then we just it into a bytes2
value, which can be converted to bytes
.
1 // There is probably a clever way to do the following lines as a loop,2 // but it's a view function so I'm optimizing for programmer time and3 // simplicity.45 if (_key < 16*256**2)6 return bytes.concat(bytes3(uint24(_key) | (0x2 * 16 * 256**2)));7 if (_key < 16*256**3)8 return bytes.concat(bytes4(uint32(_key) | (0x3 * 16 * 256**3)));9 .10 .11 .12 if (_key < 16*256**14)13 return bytes.concat(bytes15(uint120(_key) | (0xE * 16 * 256**14)));14 if (_key < 16*256**15)15 return bytes.concat(bytes16(uint128(_key) | (0xF * 16 * 256**15)));16Exibir tudoCopiar
The other values (3 bytes, 4 bytes, etc.) are handled the same way, just with different field sizes.
1 // If we get here, something is wrong.2 revert("Error in encodeVal, should not happen");3