alloy_trie/
root.rs

1use crate::{HashBuilder, EMPTY_ROOT_HASH};
2use alloc::vec::Vec;
3use alloy_primitives::B256;
4use alloy_rlp::Encodable;
5use nybbles::Nibbles;
6
7/// Adjust the index of an item for rlp encoding.
8pub const fn adjust_index_for_rlp(i: usize, len: usize) -> usize {
9    if i > 0x7f {
10        i
11    } else if i == 0x7f || i + 1 == len {
12        0
13    } else {
14        i + 1
15    }
16}
17
18/// Compute a trie root of the collection of rlp encodable items.
19pub fn ordered_trie_root<T: Encodable>(items: &[T]) -> B256 {
20    ordered_trie_root_with_encoder(items, |item, buf| item.encode(buf))
21}
22
23/// Compute a trie root of the collection of items with a custom encoder.
24pub fn ordered_trie_root_with_encoder<T, F>(items: &[T], mut encode: F) -> B256
25where
26    F: FnMut(&T, &mut Vec<u8>),
27{
28    if items.is_empty() {
29        return EMPTY_ROOT_HASH;
30    }
31
32    let mut value_buffer = Vec::new();
33
34    let mut hb = HashBuilder::default();
35    let items_len = items.len();
36    for i in 0..items_len {
37        let index = adjust_index_for_rlp(i, items_len);
38
39        let index_buffer = alloy_rlp::encode_fixed_size(&index);
40
41        value_buffer.clear();
42        encode(&items[index], &mut value_buffer);
43
44        hb.add_leaf(Nibbles::unpack(&index_buffer), &value_buffer);
45    }
46
47    hb.root()
48}
49
50/// Ethereum specific trie root functions.
51#[cfg(feature = "ethereum")]
52pub use ethereum::*;
53#[cfg(feature = "ethereum")]
54mod ethereum {
55    use super::*;
56    use crate::TrieAccount;
57    use alloy_primitives::{keccak256, Address, U256};
58
59    /// Hashes storage keys, sorts them and them calculates the root hash of the storage trie.
60    /// See [`storage_root_unsorted`] for more info.
61    pub fn storage_root_unhashed(storage: impl IntoIterator<Item = (B256, U256)>) -> B256 {
62        storage_root_unsorted(storage.into_iter().map(|(slot, value)| (keccak256(slot), value)))
63    }
64
65    /// Sorts and calculates the root hash of account storage trie.
66    /// See [`storage_root`] for more info.
67    pub fn storage_root_unsorted(storage: impl IntoIterator<Item = (B256, U256)>) -> B256 {
68        let mut v = Vec::from_iter(storage);
69        v.sort_unstable_by_key(|(key, _)| *key);
70        storage_root(v)
71    }
72
73    /// Calculates the root hash of account storage trie.
74    ///
75    /// # Panics
76    ///
77    /// If the items are not in sorted order.
78    pub fn storage_root(storage: impl IntoIterator<Item = (B256, U256)>) -> B256 {
79        let mut hb = HashBuilder::default();
80        for (hashed_slot, value) in storage {
81            hb.add_leaf(
82                Nibbles::unpack(hashed_slot),
83                alloy_rlp::encode_fixed_size(&value).as_ref(),
84            );
85        }
86        hb.root()
87    }
88
89    /// Hashes and sorts account keys, then proceeds to calculating the root hash of the state
90    /// represented as MPT.
91    /// See [`state_root_unsorted`] for more info.
92    pub fn state_root_ref_unhashed<'a, A: Into<TrieAccount> + Clone + 'a>(
93        state: impl IntoIterator<Item = (&'a Address, &'a A)>,
94    ) -> B256 {
95        state_root_unsorted(
96            state.into_iter().map(|(address, account)| (keccak256(address), account.clone())),
97        )
98    }
99
100    /// Hashes and sorts account keys, then proceeds to calculating the root hash of the state
101    /// represented as MPT.
102    /// See [`state_root_unsorted`] for more info.
103    pub fn state_root_unhashed<A: Into<TrieAccount>>(
104        state: impl IntoIterator<Item = (Address, A)>,
105    ) -> B256 {
106        state_root_unsorted(
107            state.into_iter().map(|(address, account)| (keccak256(address), account)),
108        )
109    }
110
111    /// Sorts the hashed account keys and calculates the root hash of the state represented as MPT.
112    /// See [`state_root`] for more info.
113    pub fn state_root_unsorted<A: Into<TrieAccount>>(
114        state: impl IntoIterator<Item = (B256, A)>,
115    ) -> B256 {
116        let mut vec = Vec::from_iter(state);
117        vec.sort_unstable_by_key(|(key, _)| *key);
118        state_root(vec)
119    }
120
121    /// Calculates the root hash of the state represented as MPT.
122    ///
123    /// Corresponds to [geth's `deriveHash`](https://github.com/ethereum/go-ethereum/blob/6c149fd4ad063f7c24d726a73bc0546badd1bc73/core/genesis.go#L119).
124    ///
125    /// # Panics
126    ///
127    /// If the items are not in sorted order.
128    pub fn state_root<A: Into<TrieAccount>>(state: impl IntoIterator<Item = (B256, A)>) -> B256 {
129        let mut hb = HashBuilder::default();
130        let mut account_rlp_buf = Vec::new();
131        for (hashed_key, account) in state {
132            account_rlp_buf.clear();
133            account.into().encode(&mut account_rlp_buf);
134            hb.add_leaf(Nibbles::unpack(hashed_key), &account_rlp_buf);
135        }
136        hb.root()
137    }
138}
alloy_trie/root.rs

alloy_trie/
root.rs
