feat(mpt): Don't seal MPT in place by default

[clabby]

Overview

The current behavior of the TrieNode when computing the root is to do it in-place by default. This prevents a good deal of copies of intermediate nodes while computing the hash.

However, the method we currently use hinges on an assumption that the block we're processing is actually canonical. In order to compute the output root of the block (or fetch the L2ToL1MessagePasser storage root for the Isthmus fork), we first seal the trie, and then re-open it via an MPT proof we fetch from a remote node. If the remote node has a different block at the given height, which can be the case for the interop proof's first sub-problem, execution would fail.

To allow for non-canonical blocks to be processed by kona, we need to keep a cache of the intermediates we generate. To do this, do not seal the trie up in place, but instead copy nodes as they're being encoded for hashing, leaving the originals in their place. Upon the traversal to the L2ToL1MessagePasser account in the state root after it has been computed, new trie nodes won't need to be fetched from the remote node, just existing ones that went un-changed in the worst case.

Bonus Points

For programs that use kona for multi-block range proofs, leaving the entire trie open and having to re-hash intermediates that may have not been touched in the current block is fairly inefficient. While not a requirement to get the interop proof working, adding a copy-on-write cache for trie nodes when they're hashed would prevent unnecessary inefficiencies during state root computation, especially in projects like op-succinct.

Context

kona/crates/mpt/src/node.rs

Lines 121 to 130 in 71a02cc

	/// Blinds the [TrieNode] if its encoded length is longer than an encoded [B256] string in
	/// length. Alternatively, if the [TrieNode] is a [TrieNode::Blinded] node already, it
	/// is left as-is.
	pub fn blind(&mut self) {
	if self.length() >= B256::ZERO.len() && !matches!(self, Self::Blinded { .. }) {
	let mut rlp_buf = Vec::with_capacity(self.length());
	self.encode_in_place(&mut rlp_buf);
	*self = Self::Blinded { commitment: keccak256(rlp_buf) }
	}
	}

kona/crates/executor/src/executor/mod.rs

Lines 78 to 92 in 71a02cc

	/// Fetches the L2 to L1 message passer account from the cache or underlying trie.
	fn message_passer_account(
	db: &mut TrieDB<F, H>,
	block_number: u64,
	) -> Result<B256, TrieDBError> {
	match db.storage_roots().get(&L2_TO_L1_BRIDGE) {
	Some(storage_root) => {
	storage_root.blinded_commitment().ok_or(TrieDBError::RootNotBlinded)
	}
	None => Ok(db
	.get_trie_account(&L2_TO_L1_BRIDGE, block_number)?
	.ok_or(TrieDBError::MissingAccountInfo)?
	.storage_root),
	}
	}

kona/crates/executor/src/db/mod.rs

Lines 175 to 183 in 71a02cc

	pub fn get_trie_account(
	&mut self,
	address: &Address,
	block_number: u64,
	) -> TrieDBResult<Option<TrieAccount>> {
	// Send a hint to the host to fetch the account proof.
	self.hinter
	.hint_account_proof(*address, block_number)
	.map_err(|e| TrieDBError::Provider(e.to_string()))?;

kona/bin/host/src/interop/fetcher.rs

Lines 532 to 551 in 71a02cc

	HintType::L2AccountProof => {
	if hint_data.len() != 8 + 20 {
	anyhow::bail!("Invalid hint data length: {}", hint_data.len());
	}
	let block_number = u64::from_be_bytes(
	hint_data.as_ref()[..8]
	.try_into()
	.map_err(|e| anyhow!("Error converting hint data to u64: {e}"))?,
	);
	let address = Address::from_slice(&hint_data.as_ref()[8..28]);
	let proof_response = self
	.l2_providers
	.get(&self.active_l2_chain_id)
	.ok_or(anyhow!("No active L2 chain ID"))?
	.get_proof(address, Default::default())
	.block_id(BlockId::Number(BlockNumberOrTag::Number(block_number)))
	.await
	.map_err(|e| anyhow!("Failed to fetch account proof: {e}"))?;