Storage Proof Calldata Compression

[tarrencev]

Storage Proofs are a powerful way to incorporate Layer 1 state into Layer 2 execution without having to interact with the base chain. However, storage proofs are quite large, and with the current solution, the entire proof lands on mainnet as calldata.

For example, a full rlp encoded account + storage proof can look like this:

0xf90d9af90bc0f90211a029edd7038feecc4c269348638971adff7afa108cfbcbf3727227f47d788107e7a0c4a0f9f7cda5467ebf454590539938120a8d45cebe0b5ae23baeca9d9ba3db0ea0a1dcd2dceaf2802afb7facc8cf2f479d65237f967590615511e789b87ae0bf49a0ad0cdedba66b8f0b80de76c98ee2204e41a10dd9e39443fb491312b6d7527807a029035da2a943846396521bc2f136c6221ffcdbeccae0dd5505a0217b71f21b9ba05b19bb75c951bf5e2d6e1978081ed32f3b4b896487aefae55115046aa51e84d2a0152d78037b413e82b721c807f9d0e1df40fb2d361a162a22dec8c9ed3a93dd73a037f4bbdd99ec9c3f74f93ebcf009664616eb6097d60ca7dfddd5b50ea85caa66a03472cc19b304a8675cc793e1b599c4b010d8d8292cd23d15c9448b61820e9c21a03cfc225c924e5309e24a43ada22c8962c60123855a2c9886f72d6cb0b33556a2a0c9e702c6e70fffdda008ed2bd15e2a754d608fb281d68022fb269c62ba7bc367a0177eec9fb44f0416573afea03e4c0203049bd4d95f9d80759fb6d5ac8542b2e2a06e3db170b7784d8c64b7bc4008c4e4278431a37abbf870561ea477a480acfde9a0f1a6023fe5c06df9559da1a66b2c5432ffba5e4eda97a2cc3e2931a7c5ed8c58a06a48d5341131d521865f7f6538fcf075bbb1d8d7d19c055711dab9e68f8a7960a0e0c29f34644a7f626a0c00bddff671c19799aee4b8e8cd3f7c0dcddb61a44bfa80f90211a0f69e86b2eb00794dec668daf46b896b5d49f8b73d83e16a4de9685d42d0fba7ba0dc3f272dba8ffbdab4f2fa18f339248424a561e949d7e4983877ff522fd50f82a0225a9299b76bbbbe6d9dde02731efd2e0175e9a8990e111026d7d4d1b39b2ae7a0cf14fa582f1ef73c2148ab1d0e9bb5f21289b8425cd01000bd2e17d20c4ff861a09f461e496dd291e8cd260c92a21637921ba2dd68522b8690e5e847b241452c5fa0823eec4d530f8d7584e4e86d033ab77835cfaec21d859cbe5ff5407d48f940e9a0d63b8f2075190806ef441740057de0bf0bf19277579346b034d4e91bca4359f3a0250c039348e1b65347239279b70e6248de41aec5994dcf69dc9a9413944747a4a04147b9f09be88ca1fba78a3b59bff12591725e3fef9ef2223c9b5fc8afa8553ea0009fc5899cd457f4306496500cf11378fa52fea87e78b711d64ec08dc9ae17a8a0058ab73f1a50c8685383235c6b818e68452c965ccf2b20f71de4c891baa500baa03f368aed38b6cfc384adcd3888d9dee3bbbd3f1baaf5b883524ef1ad63609232a0bc9715153796d4bff293b39e3ec0bf15732664fef46ad86d9d04c83ce6fc6c2da0195daa49758bb60adbd83cc8c32571b9ae7db2dd77133febcb21fbb0b8fc79bfa02e97855056402309c80e4823a85e6f2f7053a0d1cf65793f631fba0ee4b39054a038c9b498afe8cc33a94e414acfe92468dcaaf439855ebb81014717a2737cb80180f90211a0793835d3f67d280ccfea94fb77a002451ea40aac7c0d0f8977077b8906fb721fa0e2b34c0dbde976a8aacfee24ecb131a72b12adc663c84c16d6e4ded909739ff1a0926f07abd5ba871eb351cc569b844f80f701bc02493b3b6da84c4bb44fa22e19a0a0d38ea222c7922462ca4140900ae74d74c1c8299f6d92901a79b54efb83c1e4a030e69ece3caef43b5fecf83bf6e5d589c874c2fabfc93be1ab528474b939c3aca01298a2f528f34b212cb7be9ccf83183f8908833c88740606b7e05e9708bb5aa7a073467fba54d374f1375fe501d832d1671a4f3422df37dc8a41d6246ebea3924da095c589fe2c3ada3f3d4573865dec191f562890a3322b1da33fe886e3322dcaf9a01b6d337f597fd3d62c4d38e29075f73e57d1ca992500461f00b65917e7e9d318a07d4af029257015861e966d6a6762978fe5c6b4f10903548b5eb2dec2ca06cc4ea050809e8e1d4faae7b5f743220b3fb5da7e94c16bdda9bc886784cc18bb2f0ca9a08fe2cff5929d73d8a4c25249de752855b71fc0de2af59d72ea293b1987933af1a0fd7d876885792c808bded38ece51d48c9a056c3151f8fae280552aeb9fd43fa1a06d94fe6fc84407bd72657ad2d009391db7b350198bdd80b75bedddf56e7d94bda0b89a5b479b934adaf78b7d4b9ffdc8d83af37602a6dd85116e8906e405b772b3a0e0d1fbafa5919672c95bdba6004f7635fffba954afeffaa2657cc8d82fe22afe80f90211a0b82150cf0677c7e94e1d454bf2dba09fa3ec54b1f6168c37c19631732c0cbfb3a0150cba04728fec262840715ff233b97d07fe02c1e70dbf5d8df99a29a1798b5ea010241e2b2c69e95b0aed40405559bbbca5768254e4d13d2bcb552e8ccd888ae7a050dedacf65cc949f3d86d684122c1a672a4dc1d69737a544b6f16a50321ef1e5a061efe989f1dd00c89dfba60ecc800a6d59afb275af91eb7ee3887366ab77e238a0867b7d92ed80e37aaa1b7d86dd4bb463c25022ee1aad672a0a08accfb56f4503a045b11b92a37ef4b01abef865de05152fcd2d123170e006b3033bf9b68c860fc0a08cd4e031e8700cfd7cae22b85178875408b7671b39c050ac6fcd4861fdac1720a0f2dc4be714153275f7230ea0a7776eb0ef4188a2db1cbaa3081202521040cddba03e6dcae8954ff2cfd5c7a62cc2a44d505fa0c4104bfcfe9ca47e666ba41c176fa09de1aa5a59c2a2c8496ef4cde266318806d9016c988480d58bb865be9fe74a25a04255f5a458302f839d42b736724fa848dc7f3bb24c1dcd52edfc563be21d0543a06c4570837acf890bb1e995d70ae96170e4ee9bc06fec359b338e1fad3a7f889da07bff804ca9fb2b59eca853c922f2df931fd1b9c8aa550d49c87e0ba3b24590e8a01edc8ee2f11d5325d64e6990e36b498c2f3267b7030a74510ec763c2814f38fda03c9ff2f8cc36373a0fa70c076813acf45c73adbdb3488d3ec17a3870554c606980f90211a07c98b9c2e279f12ec5fc0fa7e5bd4ce7a685fb99235846d3325d777f9316e902a0b218e36ef8a7eb0ab3ff2c06900a6ea9d8dd3bd95d3f81c784a76856f1a22dafa08819618289de6c91da6668b3ee8bae6c0376e9f74c0112f7c3a62cb02fbff2d3a010728b2ad3b5b863b8babfa7bca7ebba5d7110758f28e63102a49432b0eddf04a01598e6e76fa7214b1c87dd0fe1760501a3c74d4645644b567f227fd2b7153427a03d044abc5d43411f1373496f2152cfecc475981f4f4d114820cd5a540bc3b5cca02573aea2df9932e3d5c4b11febf2d8693524975364e435fbdc32dfdc0b729638a03928b0ba1b7b736596424134b1b5f1d705a1e22892b0e18d03b4ddafb463dd5ba04e6e41f0b175aaaec806ce40a70f933f587a16b3a6ce1feae841af0ffe8c0667a05ab67fe076b55dc26725d2fb921092052d1240be82ccde6be63403c3e5fbf1efa0ba00828b4ac258e003eba6a54108307851a57b4359f9f54d5d2904f2572224c2a04257075802d22472172069f0d21bbf9607272e34b1845166066ef01b1e3dc9b7a0c99642d23efb3d1dd3c7a57dce3358c6eb0ae432a7df23da2ebc73b8b6fe2286a097166a0e2d40e6fa5ddb8d53c30efdc5d4f6da3836d1cca57644606b8a19316ca01b15e27269696aa57c3cec1ab6f30a529721a05387fe97a10adca18f08d5f90da0e235eaee4954c2a02c16a3263d85878541ac16d7433f3250ccc516305969bdaf80f8f180808080a034d2fd55746f26145c1d0a8c4c8af17dc8623938b0be2187c066a006100e89c1a040da6dd2b2097361a787fc580f0ed3ed281dc249a747c722bf1b8448bc32b265a0fbb731509bc1d9524f0cbadbadb8b504236a4c7271a2dd090799aef10337a185a0fb87bb71ecd27849cb09febc7329c44aaaf1ee57f297b74be153e16fe32fa3baa0880a08e7e48290e186c3712b339ad0c383af51bdf7071948c78b83833f1c2a9a80808080a0f55dd6e0c903a036a2efca2b7fc01a8eca0b6c56530acc99aeab9b22e77e8f9c80a017f604cf8efd444598534cbe5e195866ecd1ff3fe17590e17b85c430ee4eef8580f8679e2085db771d97f23346ce3c5461f59b5e12bf68258d2256efd780602cf203b846f8440180a07f1828894eeb71c717c719f912004f1989a9b9127f672fd48a9aad92ee97cec4a0f49272d0068734117bf6e17e9b5032f79e7ff6c882e460a81e191df52a108224f901d4f901d180a06c174d6d7c965453de5f0823cbae8243fc8accbd9b439b0c2b64e5f1e79f0005a05c7c03200af6cb1e11216f9211c85d03ac76a948bf4a562628111c0cc042957ea09a54d18f52431aae5f81e9fb4c8a5d1e71630d7e8230678a25b828830cb3ce2ca06fd111ede78d878bb912493cdebbde0dacadf130924b6179f2c0a1742c974139a096b3361e5fa2b190cd2c5941340ff5f28737394e21b3f9890cf166f59d331b50a0ee5de06cf0597b56ddf0201791d7e235a8c40bac9a86d13f5ea26447e2215b6f80a0a9b4d277ee45b8f111b211fac84320f2675f2631f3c1589f52209fd29044415aa0a37ce952344caf36e01dca035c649d5f2cdca0d98a4ef71ffbb054cde3329b7aa01ca7c9586ca9dfa78703d7c732c3c10c203e8e16218d5cddce37ea08ebfba51aa0be88f7bdb514e6fe5edd8ef30e22b18b06341a952652436c972c321445f4209ba00f479d24f8d1edba4dc509caf5002b915401e7eab6e92e5b453341f001670266a01e035c590b5f07496f5b3592bf5b0b81df93c0072b420719b20bc07a89cff8aaa0801f9ba073c5c3e04533a364790867edbb4cfeaf5945f8f006f50943be2b8ba8a0d5982526e350388b5581a626aa1d68e5da6dedd273132e3b52d115c240fa337d80

This proposal is for a special case calldata compression for storage proofs. Rather than landing the full storage proof on mainnet, it should be sufficient to land only the state root, state key, and state value. With those, a fault prover would still be able to contest an invalid proof executed (by showing prove(root, key, proof) != committed value) on Optimism and the cost of using storage proofs on Optimism would be significantly less expensive.

Heres a quick example of what this could look like as a predeploy that proxies calls to the underlying contract and provides a getter for retrieving the proof value, not sure if it is possible to only land the internal target.call's calldata on mainnet + state root/key/value

// SPDX-License-Identifier: MIT
pragma solidity 0.6.12;

import {iOVM_L1StateRoot} from "../interfaces/iOVM_L1StateRoot.sol";

import {RLPReader} from "./RLPReader.sol";
import {StateProofVerifier as Verifier} from "./StateProofVerifier.sol";

contract OVM_L1StorageProverProxy {
    using RLPReader for bytes;
    using RLPReader for RLPReader.RLPItem;

    mapping(address => mapping(bytes32 => Verifier.SlotValue)) private _slots;

    // @param abi encoded function selector with calldata
    // @param proofRlp RLP encoded storage proofs provided
    function callWithProof(
        address target,
        bytes calldata call,
        address[] accounts,
        bytes32[] slots,
        uint256 block,
        bytes calldata proofRlp
    ) external {
        require(accounts.length == slots.length, "accounts slots length mismatch");
        bytes32[] memory values;
        RLPReader.RLPItem[] memory proofs = proofRlp.toRlpItem().toList();
        require(accounts.length == proofs.length, "accounts proofs length mismatch");

        for (uint256 i = 0; i < proofs.length; i++) {
            Verifier.Account memory account = Verifier.extractAccountFromProof(
                keccak256(abi.encodePacked(accounts[i])),
                iOVM_L1StateRoot(0x42069).getL1StateRoot(block),
                proofs[i][0].toList()
            );

            require(account.exists, "storage prover: account doesnt exist");

            Verifier.SlotValue memory value = Verifier
                .extractSlotValueFromProof(
                    slots[i],
                    account.storageRoot,
                    proofs[i][1].toList()
                );

            _slots[accounts[i]][slots[i]] = value;
        }

        (bool success, bytes memory returndata) = target.call(call);
    }

    function getSlotValue(address account, bytes32 slot) external returns (Verifier.SlotValue) {
        return _slots[account][slot];
    }
}

[mejango]

+1

[ben-chain]

This is great thinking and I really love the direction! The concept is closely related to the desire to read (or even subscribe to) L1 event logs from within the L2 VM.

What's awesome is that we understand pretty well how to do both--your intuition here is right, but it turns out it can be done without even providing any proposed values--shifting absolutely everything into the fault proof. You could basically just provide devs with a regular (static) call function into L1.

In cannon, we give the L2 VM a function, effectively a "get_known_preimage(bytes32 hash)", which allows it to place the preimage of any known hash into memory. It turns out this is an extremely powerful function, and it is why our new fault proofs require no merkle branches even for L2 trie access.

The L2 VM uses this oracle function to unpack the block body from a block hash, then unpack a transaction or state root's children from that, and so on, fetching preimages until it's reached the key at the bottom of the trie. This is already how cannon reads trie state during the fault proof, using just the block root as an input, and there's no reason it can't execute the same strategy for both L1 and L2 state roots alike. In this model, you would be able to expose a new STATICCALL which can effectively eth_call directly into an L1 contract. Devs would not even need to propose values or know what keys would end up being hit!

So the main thing preventing this from being implemented is actually not the fault proof, but downstream effects on node software itself. It's nice to be able to run L1 and L2 nodes on different machines. This would mean that we must run L1 and L2 nodes in the same process, or else face a huge number of asyncronous API calls in the middle of EVM execution. How to gas meter is another related problem, especially if asyncronous.

Soon^TM, we really want this and are thinking about it a lot!

[tarrencev]

@ben-chain this is really cool to hear! Being able to perform an eth_call directly to L1 from L2 would be super powerful. One question I have, in this approach would it be possible to provide a L1 block for the eth_call? It seems that probably introduces a lot of overhead, since now the L1 node needs to run an archive node or would have to be limited to the last n blocks.

I'm curious if it will support both the super nice abstraction of "call L1 contract from L2 contract" as well as lower level "give me this slot from this block". The latter enables an additional set of uses cases, for example, state snapshots for token voting or accessing L1 state that isn't exposed through a public interface.

I wonder if it is interesting to explore how this could interact with EIP-3668. Perhaps it is possible to provide an EIP-3668 interface for performing the L1 calls async, then you might be able to avoid the L1 in same process as L2 requirement?

[norswap]

@tarrencev We will need an archive node anyway if we want to run historical L2 blocks with the capability to read from the latest L1 block (at the time).

Regarding EIP-3668, it's a really interesting notion! Thinking through the implications:

• it does not supply a guarantee that the "callback" will be made, but it's not impossible to add that in the rollup node
• it specifies that the contract should verify the data passed with the callback, which in this case would mean a merkle proof, which would put us back to square one, so nodes would also need to validate that data

Honestly, I like the original idea a lot also. We could also remove the value if we want to save a little bit of calldata, validators would still be able to prefetch the data from L1.

[tarrencev]

@norswap thank you for responding! ah yeah that makes sense re: archive nodes.

EIP-3668 could be nice for a standardized interface but, as you suggested, doesn't really add much to the solution here.

Glad you like the original idea! Would love to keep chatting to understand if/when something like this could land on Optimism. I feel like it could enable many interesting use cases