L2 output-root bonus: embed L2 history merkle accumulator

[protolambda]

When constructing the output root, we can include many useful things, such as:

• Latest L2 block (fully merkleized)
• State-root of L2 (account trie)
• Withdrawal contract storage tree (elevate it to avoid MPT proof cost into L2 account trie)
• Empty spots for upgradeability (to substitute with sub-trees of information later)
• L2 block history accumulator (new idea! what this issue is about)
  • Block-hash accumulator
  • State-root accumulator

There is one bottleneck for introducing more of these though: as a user that wants to create a proof for any of these, all the sibling data needs to be easily accessible. E.g. for a withdrawal proof we do not want to merkleize the full L2 history, but just look it up (like calling a smart-contract or reading a specific storage slot).

The first 4 are directly accessible:

• Latest L2 block is retrievable by hash/number
• Latest state-root is in that block
• Withdrawal storage tree root is a single lookup in the account-trie
• Empty slots are just zeroed

The history accumulator is more difficult: to have instant access, we need to actively keep track of the accumulator root. And preferably without modifying the execution-engine.

So how can we do this? By modifying the L1Info predeploy to become a more generic RollupInfo predeploy: we run this transaction every time, and implement a merkle-accumulator. This can be stack based to save storage, just like the formally-verified Beacon deposit contract does.

This would change the contract to look more like:

    bytes32 public historyRoot;

    function updateRollupInfo(
        uint256 _l1number,
        uint256 _l1timestamp,
        uint256 _l1basefee,
        bytes32 _l1hash,
        bytes32 _l2stateroot,
    ) external {
        if (msg.sender != DEPOSITOR_ACCOUNT) {
            revert OnlyDepositor();
        }
        setL1BlockValues(_l1number, _l1timestamp, _l1basefee, _l1hash);  // TODO: l1 stateroot may be useful too, why not add it?

        // state-root of L2 is not exposed with opcode, but we can fault-proof it just like L1 info. Whereas blockhash is easily accessed
        bytes32 memory nextHistoryItem = keccak256(abi.encodePacked(_l2stateroot, block.hash));
        updateL2HistoryAccumulator(nextHistoryItem);
        historyRoot = getL2HistoryAccumulatorRoot()  // cache the result (pay gas to make lookups for everyone else cheaper)
    }

// based on formally verified merkle updater:
// SPDX-License-Identifier: CC0-1.0
// see https://github.com/ethereum/consensus-specs/blob/master/solidity_deposit_contract/deposit_contract.sol

 // TODO: might want deeper tree, since we add 1 for every block, forever
    uint constant MAX_TREE_DEPTH = 32; 
    uint constant MAX_ITEM_COUNT = 2**MAX_TREE_DEPTH - 1;

    bytes32[MAX_TREE_DEPTH] branch;
    uint256 deposit_count;

    bytes32[MAX_TREE_DEPTH] zero_hashes;

    constructor() public {
        // Compute hashes in empty sparse Merkle tree
        for (uint height = 0; height < DEPOSIT_CONTRACT_TREE_DEPTH - 1; height++)
            zero_hashes[height + 1] = keccak256(abi.encodePacked(zero_hashes[height], zero_hashes[height]));
    }

    function getL2HistoryAccumulatorRoot() override external view returns (bytes32) {
        bytes32 node;
        uint size = block.number;
        for (uint height = 0; height < MAX_TREE_DEPTH; height++) {
            if ((size & 1) == 1)
                node = keccak256(abi.encodePacked(branch[height], node));
            else
                node = keccak256(abi.encodePacked(node, zero_hashes[height]));
            size /= 2;
        }
        // important: mix-in the length, so we know how many slots are used in the binary tree (left to right on bottom depth) 
        return keccak256(abi.encodePacked(
            node,
            to_little_endian_64(uint64(size)),
            bytes24(0)
        ));
    }

    function updateL2HistoryAccumulator(bytes32 _root) internal {

        // Add root to Merkle tree (update a single `branch` node)
        uint size = block.number;  // use L2 block number as index, since we only call this once for every L2 block
        for (uint height = 0; height < MAX_TREE_DEPTH; height++) {
            if ((size & 1) == 1) {
                branch[height] = node;
                return;
            }
            node = keccak256(abi.encodePacked(branch[height], node));
            size /= 2;
        }
        // As the loop should always end prematurely with the `return` statement,
        // this code should be unreachable. We assert `false` just to be safe.
        assert(false);
    }

This way we have a binary-merkle-tree of all L2 block hashes and state-roots (hashed together as leaf value), to proof any L2 history, and make it readable to other EVM users (public historyRoot contract storage var), and directly readable to those that need it as merkle sibling data in a proof for other L2 output contents.

[protolambda]

More advanced extension of this idea: include a 2nd tree accumulator, of all historical receipts (each receipt merkleized nicely as well) for easy consumption of L2 events on other chains/L1. That way users do not have to present a long complex proof like historical block -> receipts_root in header -> receipt entry, but can instead just present a binary merkle proof to a historical receipt.

[norswap]

// TODO: l1 stateroot may be useful too, why not add it?

Yes! I was thinking about that myself.

Regarding the code, node is not defined in updateL2HistoryAccumulator.

Read the deposit contract, I'm not surprised it needs formal verification, it's a really tight, but super tricky piece of code.

[maurelian]

When constructing the output root, we can include many useful things, such as...

How would the fault proof account for a fault in one of these output 'components'? Would we need to modify the proof to allow for a challenge against (for example) the withdrawal storage tree root, or is there an elegant way to incorporate that in the general challenge flow?

The first 4 are directly accessible:
Latest L2 block is retrievable by hash/number
Latest state-root is in that block
Withdrawal storage tree root is a single lookup in the account-trie

This L2 related data would be generated by the execution engine, and included in what is currently referred to as the "L1 attributes deposited transaction"?

This way we have a binary-merkle-tree of all L2 block hashes and state-roots...

So, this would be a storage efficient alternative to just keeping an array of L2 block hashes and state roots.

Assuming I got all that, what's the motivation? I suppose it's a utility service we're providing, that facilitates the creation of a things like storage oracles (ie. the uniswap-oracle)?

[protolambda]

How would the fault proof account for a fault in one of these output 'components'?

Instead of stopping the execution trace as soon as we have the state root, we continue the processing with construction of the L2 output-root. No additional challenges/games required.

This L2 related data would be generated by the execution engine, and included in what is currently referred to as the "L1 attributes deposited transaction"?

Basically yes, we want to expose information like the history accumulator in the EVM, and can do so by deriving a system deposit that calls a contract that maintains + stores it. And instead of an additional one, we can just combine it with the L1 info deposit work.

So, this would be a storage efficient alternative to just keeping an array of L2 block hashes and state roots.

Indeed, to limit state growth, and since we want a binary merkle tree (for efficient history proofs) without recomputing the merkle-root over all data every block.

Assuming I got all that, what's the motivation?

Enabling more interesting applications, a history proof can enable a trustless oracle of a block header (includes receipt root) or state root. And we can use it on both L1 and L2. The uniswap-oracle you linked is one example, but now it's not limited to the last 256 blocks anymore. After the Eth2 Merge we will have a history-accumulator in the BeaconState to retrieve execution payloads and state roots from, but we do not share the consensus-layer, so we would be missing out on that if we do not implement our own version.

[maurelian]

OK, this is interesting, and the effort required to create uniswap-oracle is indicative of how useful a generalized state oracle would be.

A natural question then is, should we also provide an L1 history accumulator?

[tynes]

I am generally in favor of these ideas although we do need to take into account the fact that the more computation that happens during these transactions, the less gas there is in a block for other transactions, since this transaction must be the very first transaction in each block.

Making common operations convenient for developers could make a huge difference in adoption vs other chains