reth_trie_common/
root.rs

1//! Common root computation functions.
2
3use crate::TrieAccount;
4use alloy_primitives::{keccak256, Address, B256};
5use alloy_rlp::Encodable;
6use alloy_trie::HashBuilder;
7use itertools::Itertools;
8use nybbles::Nibbles;
9use revm_primitives::FlaggedStorage;
10
11/// Hashes and sorts account keys, then proceeds to calculating the root hash of the state
12/// represented as MPT.
13/// See [`state_root_unsorted`] for more info.
14pub fn state_root_ref_unhashed<'a, A: Into<TrieAccount> + Clone + 'a>(
15    state: impl IntoIterator<Item = (&'a Address, &'a A)>,
16) -> B256 {
17    state_root_unsorted(
18        state.into_iter().map(|(address, account)| (keccak256(address), account.clone())),
19    )
20}
21
22/// Hashes and sorts account keys, then proceeds to calculating the root hash of the state
23/// represented as MPT.
24/// See [`state_root_unsorted`] for more info.
25pub fn state_root_unhashed<A: Into<TrieAccount>>(
26    state: impl IntoIterator<Item = (Address, A)>,
27) -> B256 {
28    state_root_unsorted(state.into_iter().map(|(address, account)| (keccak256(address), account)))
29}
30
31/// Sorts the hashed account keys and calculates the root hash of the state represented as MPT.
32/// See [`state_root`] for more info.
33pub fn state_root_unsorted<A: Into<TrieAccount>>(
34    state: impl IntoIterator<Item = (B256, A)>,
35) -> B256 {
36    state_root(state.into_iter().sorted_unstable_by_key(|(key, _)| *key))
37}
38
39/// Calculates the root hash of the state represented as MPT.
40///
41/// Corresponds to [geth's `deriveHash`](https://github.com/ethereum/go-ethereum/blob/6c149fd4ad063f7c24d726a73bc0546badd1bc73/core/genesis.go#L119).
42///
43/// # Panics
44///
45/// If the items are not in sorted order.
46pub fn state_root<A: Into<TrieAccount>>(state: impl IntoIterator<Item = (B256, A)>) -> B256 {
47    let mut hb = HashBuilder::default();
48    let mut account_rlp_buf = Vec::new();
49    for (hashed_key, account) in state {
50        account_rlp_buf.clear();
51        account.into().encode(&mut account_rlp_buf);
52        hb.add_leaf(Nibbles::unpack(hashed_key), &account_rlp_buf);
53    }
54    hb.root()
55}
56
57/// Hashes storage keys, sorts them and them calculates the root hash of the storage trie.
58/// See [`storage_root_unsorted`] for more info.
59pub fn storage_root_unhashed(storage: impl IntoIterator<Item = (B256, FlaggedStorage)>) -> B256 {
60    storage_root_unsorted(storage.into_iter().map(|(slot, value)| (keccak256(slot), value)))
61}
62
63/// Sorts and calculates the root hash of account storage trie.
64/// See [`storage_root`] for more info.
65pub fn storage_root_unsorted(storage: impl IntoIterator<Item = (B256, FlaggedStorage)>) -> B256 {
66    storage_root(storage.into_iter().sorted_by_key(|(key, _)| *key))
67}
68
69/// Calculates the root hash of account storage trie.
70///
71/// # Panics
72///
73/// If the items are not in sorted order.
74pub fn storage_root(storage: impl IntoIterator<Item = (B256, FlaggedStorage)>) -> B256 {
75    let mut hb = HashBuilder::default();
76    for (hashed_slot, value) in storage {
77        hb.add_leaf(
78            Nibbles::unpack(hashed_slot),
79            alloy_rlp::encode_fixed_size(&value.value).as_ref(),
80        );
81    }
82    hb.root()
83}
reth_trie_common/root.rs

reth_trie_common/
root.rs
