alloy_trie/hash_builder/
mod.rs

1//! The implementation of the hash builder.
2
3use super::{
4    BranchNodeCompact, EMPTY_ROOT_HASH, Nibbles, TrieMask,
5    nodes::{BranchNodeRef, ExtensionNodeRef, LeafNodeRef},
6    proof::ProofRetainer,
7};
8use crate::{HashMap, nodes::RlpNode, proof::ProofNodes};
9use alloc::vec::Vec;
10use alloy_primitives::{B256, keccak256};
11use alloy_rlp::EMPTY_STRING_CODE;
12use core::cmp;
13use tracing::trace;
14
15mod value;
16pub use value::{HashBuilderValue, HashBuilderValueRef};
17
18/// A component used to construct the root hash of the trie.
19///
20/// The primary purpose of a Hash Builder is to build the Merkle proof that is essential for
21/// verifying the integrity and authenticity of the trie's contents. It achieves this by
22/// constructing the root hash from the hashes of child nodes according to specific rules, depending
23/// on the type of the node (branch, extension, or leaf).
24///
25/// Here's an overview of how the Hash Builder works for each type of node:
26///  * Branch Node: The Hash Builder combines the hashes of all the child nodes of the branch node,
27///    using a cryptographic hash function like SHA-256. The child nodes' hashes are concatenated
28///    and hashed, and the result is considered the hash of the branch node. The process is repeated
29///    recursively until the root hash is obtained.
30///  * Extension Node: In the case of an extension node, the Hash Builder first encodes the node's
31///    shared nibble path, followed by the hash of the next child node. It concatenates these values
32///    and then computes the hash of the resulting data, which represents the hash of the extension
33///    node.
34///  * Leaf Node: For a leaf node, the Hash Builder first encodes the key-path and the value of the
35///    leaf node. It then concatenates the encoded key-path and value, and computes the hash of this
36///    concatenated data, which represents the hash of the leaf node.
37///
38/// The Hash Builder operates recursively, starting from the bottom of the trie and working its way
39/// up, combining the hashes of child nodes and ultimately generating the root hash. The root hash
40/// can then be used to verify the integrity and authenticity of the trie's data by constructing and
41/// verifying Merkle proofs.
42#[derive(Debug, Clone, Default)]
43#[allow(missing_docs)]
44pub struct HashBuilder {
45    pub key: Nibbles,
46    pub value: HashBuilderValue,
47    pub stack: Vec<RlpNode>,
48
49    pub state_masks: Vec<TrieMask>,
50    pub tree_masks: Vec<TrieMask>,
51    pub hash_masks: Vec<TrieMask>,
52
53    pub stored_in_database: bool,
54
55    pub updated_branch_nodes: Option<HashMap<Nibbles, BranchNodeCompact>>,
56    pub proof_retainer: Option<ProofRetainer>,
57
58    pub rlp_buf: Vec<u8>,
59}
60
61impl HashBuilder {
62    /// Enables the Hash Builder to store updated branch nodes.
63    ///
64    /// Call [HashBuilder::split] to get the updates to branch nodes.
65    pub fn with_updates(mut self, retain_updates: bool) -> Self {
66        self.set_updates(retain_updates);
67        self
68    }
69
70    /// Enable specified proof retainer.
71    pub fn with_proof_retainer(mut self, retainer: ProofRetainer) -> Self {
72        self.proof_retainer = Some(retainer);
73        self
74    }
75
76    /// Enables the Hash Builder to store updated branch nodes.
77    ///
78    /// Call [HashBuilder::split] to get the updates to branch nodes.
79    pub fn set_updates(&mut self, retain_updates: bool) {
80        if retain_updates {
81            self.updated_branch_nodes = Some(HashMap::default());
82        }
83    }
84
85    /// Splits the [HashBuilder] into a [HashBuilder] and hash builder updates.
86    pub fn split(mut self) -> (Self, HashMap<Nibbles, BranchNodeCompact>) {
87        let updates = self.updated_branch_nodes.take();
88        (self, updates.unwrap_or_default())
89    }
90
91    /// Take and return retained proof nodes.
92    pub fn take_proof_nodes(&mut self) -> ProofNodes {
93        self.proof_retainer.take().map(ProofRetainer::into_proof_nodes).unwrap_or_default()
94    }
95
96    /// The number of total updates accrued.
97    /// Returns `0` if [Self::with_updates] was not called.
98    pub fn updates_len(&self) -> usize {
99        self.updated_branch_nodes.as_ref().map(|u| u.len()).unwrap_or(0)
100    }
101
102    /// Print the current stack of the Hash Builder.
103    #[cfg(feature = "std")]
104    pub fn print_stack(&self) {
105        println!("============ STACK ===============");
106        for item in &self.stack {
107            println!("{}", alloy_primitives::hex::encode(item));
108        }
109        println!("============ END STACK ===============");
110    }
111
112    /// Adds a new leaf element and its value to the trie hash builder.
113    ///
114    /// # Panics
115    ///
116    /// Panics if the new key does not come after the current key.
117    pub fn add_leaf(&mut self, key: Nibbles, value: &[u8]) {
118        assert!(key > self.key, "add_leaf key {:?} self.key {:?}", key, self.key);
119        self.add_leaf_unchecked(key, value);
120    }
121
122    /// Adds a new leaf element and its value to the trie hash builder,
123    /// without checking the order of the new key. This is only for
124    /// performance-critical usage that guarantees keys are inserted
125    /// in sorted order.
126    pub fn add_leaf_unchecked(&mut self, key: Nibbles, value: &[u8]) {
127        debug_assert!(key > self.key, "add_leaf_unchecked key {:?} self.key {:?}", key, self.key);
128        if !self.key.is_empty() {
129            self.update(&key);
130        }
131        self.set_key_value(key, HashBuilderValueRef::Bytes(value));
132    }
133
134    /// Adds a new branch element and its hash to the trie hash builder.
135    pub fn add_branch(&mut self, key: Nibbles, value: B256, stored_in_database: bool) {
136        assert!(
137            key > self.key || (self.key.is_empty() && key.is_empty()),
138            "add_branch key {:?} self.key {:?}",
139            key,
140            self.key
141        );
142        if !self.key.is_empty() {
143            self.update(&key);
144        } else if key.is_empty() {
145            self.stack.push(RlpNode::word_rlp(&value));
146        }
147        self.set_key_value(key, HashBuilderValueRef::Hash(&value));
148        self.stored_in_database = stored_in_database;
149    }
150
151    /// Returns the current root hash of the trie builder.
152    pub fn root(&mut self) -> B256 {
153        // Clears the internal state
154        if !self.key.is_empty() {
155            self.update(&Nibbles::default());
156            self.key.clear();
157            self.value.clear();
158        }
159        let root = self.current_root();
160        if root == EMPTY_ROOT_HASH {
161            if let Some(proof_retainer) = self.proof_retainer.as_mut() {
162                proof_retainer.retain(&Nibbles::default(), &[EMPTY_STRING_CODE])
163            }
164        }
165        root
166    }
167
168    #[inline]
169    fn set_key_value(&mut self, key: Nibbles, value: HashBuilderValueRef<'_>) {
170        self.log_key_value("old value");
171        self.key = key;
172        self.value.set_from_ref(value);
173        self.log_key_value("new value");
174    }
175
176    fn log_key_value(&self, msg: &str) {
177        trace!(target: "trie::hash_builder",
178            key = ?self.key,
179            value = ?self.value,
180            "{msg}",
181        );
182    }
183
184    fn current_root(&self) -> B256 {
185        if let Some(node_ref) = self.stack.last() {
186            if let Some(hash) = node_ref.as_hash() { hash } else { keccak256(node_ref) }
187        } else {
188            EMPTY_ROOT_HASH
189        }
190    }
191
192    /// Given a new element, it appends it to the stack and proceeds to loop through the stack state
193    /// and convert the nodes it can into branch / extension nodes and hash them. This ensures
194    /// that the top of the stack always contains the merkle root corresponding to the trie
195    /// built so far.
196    fn update(&mut self, succeeding: &Nibbles) {
197        let mut build_extensions = false;
198        // current / self.key is always the latest added element in the trie
199        let mut current = self.key;
200        debug_assert!(!current.is_empty());
201
202        trace!(target: "trie::hash_builder", ?current, ?succeeding, "updating merkle tree");
203
204        let mut i = 0usize;
205        loop {
206            let _span = tracing::trace_span!(target: "trie::hash_builder", "loop", i, ?current, build_extensions).entered();
207
208            let preceding_exists = !self.state_masks.is_empty();
209            let preceding_len = self.state_masks.len().saturating_sub(1);
210
211            let common_prefix_len = succeeding.common_prefix_length(&current);
212            let len = cmp::max(preceding_len, common_prefix_len);
213            assert!(len < current.len(), "len {} current.len {}", len, current.len());
214
215            trace!(
216                target: "trie::hash_builder",
217                ?len,
218                ?common_prefix_len,
219                ?preceding_len,
220                preceding_exists,
221                "prefix lengths after comparing keys"
222            );
223
224            // Adjust the state masks for branch calculation
225            let extra_digit = current.get_unchecked(len);
226            if self.state_masks.len() <= len {
227                let new_len = len + 1;
228                trace!(target: "trie::hash_builder", new_len, old_len = self.state_masks.len(), "scaling state masks to fit");
229                self.state_masks.resize(new_len, TrieMask::default());
230            }
231            self.state_masks[len] |= TrieMask::from_nibble(extra_digit);
232            trace!(
233                target: "trie::hash_builder",
234                ?extra_digit,
235                state_masks = ?self.state_masks,
236            );
237
238            // Adjust the tree masks for exporting to the DB
239            if self.tree_masks.len() < current.len() {
240                self.resize_masks(current.len());
241            }
242
243            let mut len_from = len;
244            if !succeeding.is_empty() || preceding_exists {
245                len_from += 1;
246            }
247            trace!(target: "trie::hash_builder", "skipping {len_from} nibbles");
248
249            // The key without the common prefix
250            let short_node_key = current.slice(len_from..);
251            trace!(target: "trie::hash_builder", ?short_node_key);
252
253            // Concatenate the 2 nodes together
254            if !build_extensions {
255                match self.value.as_ref() {
256                    HashBuilderValueRef::Bytes(leaf_value) => {
257                        let leaf_node = LeafNodeRef::new(&short_node_key, leaf_value);
258                        self.rlp_buf.clear();
259                        let rlp = leaf_node.rlp(&mut self.rlp_buf);
260
261                        let path = current.slice(..len_from);
262                        trace!(
263                            target: "trie::hash_builder",
264                            ?path,
265                            ?leaf_node,
266                            ?rlp,
267                            "pushing leaf node",
268                        );
269                        self.stack.push(rlp);
270                        self.retain_proof_from_buf(&path);
271                    }
272                    HashBuilderValueRef::Hash(hash) => {
273                        trace!(target: "trie::hash_builder", ?hash, "pushing branch node hash");
274                        self.stack.push(RlpNode::word_rlp(hash));
275
276                        if self.stored_in_database {
277                            self.tree_masks[current.len() - 1] |=
278                                TrieMask::from_nibble(current.last().unwrap());
279                        }
280                        self.hash_masks[current.len() - 1] |=
281                            TrieMask::from_nibble(current.last().unwrap());
282
283                        build_extensions = true;
284                    }
285                }
286            }
287
288            if build_extensions && !short_node_key.is_empty() {
289                self.update_masks(&current, len_from);
290                let stack_last = self.stack.pop().expect("there should be at least one stack item");
291                let extension_node = ExtensionNodeRef::new(&short_node_key, &stack_last);
292
293                self.rlp_buf.clear();
294                let rlp = extension_node.rlp(&mut self.rlp_buf);
295
296                let path = current.slice(..len_from);
297                trace!(
298                    target: "trie::hash_builder",
299                    ?path,
300                    ?extension_node,
301                    ?rlp,
302                    "pushing extension node",
303                );
304                self.stack.push(rlp);
305                self.retain_proof_from_buf(&path);
306                self.resize_masks(len_from);
307            }
308
309            if preceding_len <= common_prefix_len && !succeeding.is_empty() {
310                trace!(target: "trie::hash_builder", "no common prefix to create branch nodes from, returning");
311                return;
312            }
313
314            // Insert branch nodes in the stack
315            if !succeeding.is_empty() || preceding_exists {
316                // Pushes the corresponding branch node to the stack
317                let children = self.push_branch_node(&current, len);
318                // Need to store the branch node in an efficient format outside of the hash builder
319                self.store_branch_node(&current, len, children);
320            }
321
322            self.state_masks.resize(len, TrieMask::default());
323            self.resize_masks(len);
324
325            if preceding_len == 0 {
326                trace!(target: "trie::hash_builder", "0 or 1 state masks means we have no more elements to process");
327                return;
328            }
329
330            current.truncate(preceding_len);
331            trace!(target: "trie::hash_builder", ?current, "truncated nibbles to {} bytes", preceding_len);
332
333            trace!(target: "trie::hash_builder", state_masks = ?self.state_masks, "popping empty state masks");
334            while self.state_masks.last() == Some(&TrieMask::default()) {
335                self.state_masks.pop();
336            }
337
338            build_extensions = true;
339
340            i += 1;
341        }
342    }
343
344    /// Given the size of the longest common prefix, it proceeds to create a branch node
345    /// from the state mask and existing stack state, and store its RLP to the top of the stack,
346    /// after popping all the relevant elements from the stack.
347    ///
348    /// Returns the hashes of the children of the branch node, only if `updated_branch_nodes` is
349    /// enabled.
350    fn push_branch_node(&mut self, current: &Nibbles, len: usize) -> Vec<B256> {
351        let state_mask = self.state_masks[len];
352        let hash_mask = self.hash_masks[len];
353        let branch_node = BranchNodeRef::new(&self.stack, state_mask);
354        // Avoid calculating this value if it's not needed.
355        let children = if self.updated_branch_nodes.is_some() {
356            branch_node.child_hashes(hash_mask).collect()
357        } else {
358            vec![]
359        };
360
361        self.rlp_buf.clear();
362        let rlp = branch_node.rlp(&mut self.rlp_buf);
363        let path = current.slice(..len);
364        trace!(
365            target: "trie::hash_builder",
366            ?path,
367            ?branch_node,
368            ?rlp,
369            "pushing branch node",
370        );
371        self.retain_proof_from_buf(&path);
372
373        // Clears the stack from the branch node elements
374        let first_child_idx = self.stack.len() - state_mask.count_ones() as usize;
375        trace!(
376            target: "trie::hash_builder",
377            new_len = first_child_idx,
378            old_len = self.stack.len(),
379            "resizing stack to prepare branch node"
380        );
381        self.stack.resize_with(first_child_idx, Default::default);
382
383        self.stack.push(rlp);
384        children
385    }
386
387    /// Given the current nibble prefix and the highest common prefix length, proceeds
388    /// to update the masks for the next level and store the branch node and the
389    /// masks in the database. We will use that when consuming the intermediate nodes
390    /// from the database to efficiently build the trie.
391    fn store_branch_node(&mut self, current: &Nibbles, len: usize, children: Vec<B256>) {
392        if len > 0 {
393            let parent_index = len - 1;
394            self.hash_masks[parent_index] |=
395                TrieMask::from_nibble(current.get_unchecked(parent_index));
396        }
397
398        let store_in_db_trie = !self.tree_masks[len].is_empty() || !self.hash_masks[len].is_empty();
399        if store_in_db_trie {
400            if len > 0 {
401                let parent_index = len - 1;
402                self.tree_masks[parent_index] |=
403                    TrieMask::from_nibble(current.get_unchecked(parent_index));
404            }
405
406            if self.updated_branch_nodes.is_some() {
407                let common_prefix = current.slice(..len);
408                let node = BranchNodeCompact::new(
409                    self.state_masks[len],
410                    self.tree_masks[len],
411                    self.hash_masks[len],
412                    children,
413                    (len == 0).then(|| self.current_root()),
414                );
415                self.updated_branch_nodes.as_mut().unwrap().insert(common_prefix, node);
416            }
417        }
418    }
419
420    fn retain_proof_from_buf(&mut self, prefix: &Nibbles) {
421        if let Some(proof_retainer) = self.proof_retainer.as_mut() {
422            proof_retainer.retain(prefix, &self.rlp_buf)
423        }
424    }
425
426    fn update_masks(&mut self, current: &Nibbles, len_from: usize) {
427        if len_from > 0 {
428            let flag = TrieMask::from_nibble(current.get_unchecked(len_from - 1));
429
430            self.hash_masks[len_from - 1] &= !flag;
431
432            if !self.tree_masks[current.len() - 1].is_empty() {
433                self.tree_masks[len_from - 1] |= flag;
434            }
435        }
436    }
437
438    fn resize_masks(&mut self, new_len: usize) {
439        trace!(
440            target: "trie::hash_builder",
441            new_len,
442            old_tree_mask_len = self.tree_masks.len(),
443            old_hash_mask_len = self.hash_masks.len(),
444            "resizing tree/hash masks"
445        );
446        self.tree_masks.resize(new_len, TrieMask::default());
447        self.hash_masks.resize(new_len, TrieMask::default());
448    }
449}
450
451#[cfg(test)]
452mod tests {
453    use super::*;
454    use crate::{nodes::LeafNode, triehash_trie_root};
455    use alloc::collections::BTreeMap;
456    use alloy_primitives::{U256, b256, hex};
457    use alloy_rlp::Encodable;
458
459    // Hashes the keys, RLP encodes the values, compares the trie builder with the upstream root.
460    fn assert_hashed_trie_root<'a, I, K>(iter: I)
461    where
462        I: Iterator<Item = (K, &'a U256)>,
463        K: AsRef<[u8]> + Ord,
464    {
465        let hashed = iter
466            .map(|(k, v)| (keccak256(k.as_ref()), alloy_rlp::encode(v).to_vec()))
467            // Collect into a btree map to sort the data
468            .collect::<BTreeMap<_, _>>();
469
470        let mut hb = HashBuilder::default();
471
472        hashed.iter().for_each(|(key, val)| {
473            let nibbles = Nibbles::unpack(key);
474            hb.add_leaf(nibbles, val);
475        });
476
477        assert_eq!(hb.root(), triehash_trie_root(&hashed));
478    }
479
480    // No hashing involved
481    fn assert_trie_root<I, K, V>(iter: I)
482    where
483        I: IntoIterator<Item = (K, V)>,
484        K: AsRef<[u8]> + Ord,
485        V: AsRef<[u8]>,
486    {
487        let mut hb = HashBuilder::default();
488
489        let data = iter.into_iter().collect::<BTreeMap<_, _>>();
490        data.iter().for_each(|(key, val)| {
491            let nibbles = Nibbles::unpack(key.as_ref());
492            hb.add_leaf(nibbles, val.as_ref());
493        });
494
495        assert_eq!(hb.root(), triehash_trie_root(data));
496    }
497
498    #[test]
499    fn empty() {
500        assert_eq!(HashBuilder::default().root(), EMPTY_ROOT_HASH);
501    }
502
503    #[test]
504    #[cfg(feature = "arbitrary")]
505    #[cfg_attr(miri, ignore = "no proptest")]
506    fn arbitrary_hashed_root() {
507        use proptest::prelude::*;
508        proptest!(|(state: BTreeMap<B256, U256>)| {
509            assert_hashed_trie_root(state.iter());
510        });
511    }
512
513    #[test]
514    fn test_generates_branch_node() {
515        let mut hb = HashBuilder::default().with_updates(true);
516
517        // We have 1 branch node update to be stored at 0x01, indicated by the first nibble.
518        // That branch root node has 4 children:
519        // - Leaf at nibble `0`: It has an empty value.
520        // - Branch at nibble `1`: It has 2 leaf nodes with empty values at nibbles `0` and `1`.
521        // - Branch at nibble `2`: It has 2 leaf nodes with empty values at nibbles `0` and `2`.
522        // - Leaf at nibble `3`: It has an empty value.
523        //
524        // This is enough information to construct the intermediate node value:
525        // 1. State Mask: 0b1111. All children of the branch node set at nibbles `0`, `1`, `2` and
526        //    `3`.
527        // 2. Hash Mask: 0b0110. Of the above items, nibbles `1` and `2` correspond to children that
528        //    are branch nodes.
529        // 3. Tree Mask: 0b0000. None of the children are stored in the database (yet).
530        // 4. Hashes: Hashes of the 2 sub-branch roots, at nibbles `1` and `2`. Calculated by
531        //    hashing the 0th and 1st element for the branch at nibble `1` , and the 0th and 2nd
532        //    element for the branch at nibble `2`. This basically means that every
533        //    BranchNodeCompact is capable of storing up to 2 levels deep of nodes (?).
534        let data = BTreeMap::from([
535            (
536                // Leaf located at nibble `0` of the branch root node that doesn't result in
537                // creating another branch node
538                hex!("1000000000000000000000000000000000000000000000000000000000000000").to_vec(),
539                Vec::new(),
540            ),
541            (
542                hex!("1100000000000000000000000000000000000000000000000000000000000000").to_vec(),
543                Vec::new(),
544            ),
545            (
546                hex!("1110000000000000000000000000000000000000000000000000000000000000").to_vec(),
547                Vec::new(),
548            ),
549            (
550                hex!("1200000000000000000000000000000000000000000000000000000000000000").to_vec(),
551                Vec::new(),
552            ),
553            (
554                hex!("1220000000000000000000000000000000000000000000000000000000000000").to_vec(),
555                Vec::new(),
556            ),
557            (
558                // Leaf located at nibble `3` of the branch root node that doesn't result in
559                // creating another branch node
560                hex!("1320000000000000000000000000000000000000000000000000000000000000").to_vec(),
561                Vec::new(),
562            ),
563        ]);
564        data.iter().for_each(|(key, val)| {
565            let nibbles = Nibbles::unpack(key);
566            hb.add_leaf(nibbles, val.as_ref());
567        });
568        let _root = hb.root();
569
570        let (_, updates) = hb.split();
571
572        let update = updates.get(&Nibbles::from_nibbles_unchecked(hex!("01"))).unwrap();
573        // Nibbles 0, 1, 2, 3 have children
574        assert_eq!(update.state_mask, TrieMask::new(0b1111));
575        // None of the children are stored in the database
576        assert_eq!(update.tree_mask, TrieMask::new(0b0000));
577        // Children under nibbles `1` and `2` are branch nodes with `hashes`
578        assert_eq!(update.hash_mask, TrieMask::new(0b0110));
579        // Calculated when running the hash builder
580        assert_eq!(update.hashes.len(), 2);
581
582        assert_eq!(_root, triehash_trie_root(data));
583    }
584
585    #[test]
586    fn test_root_raw_data() {
587        let data = [
588            (hex!("646f").to_vec(), hex!("76657262").to_vec()),
589            (hex!("676f6f64").to_vec(), hex!("7075707079").to_vec()),
590            (hex!("676f6b32").to_vec(), hex!("7075707079").to_vec()),
591            (hex!("676f6b34").to_vec(), hex!("7075707079").to_vec()),
592        ];
593        assert_trie_root(data);
594    }
595
596    #[test]
597    fn test_root_rlp_hashed_data() {
598        let data: HashMap<_, _, _> = HashMap::from([
599            (B256::with_last_byte(1), U256::from(2)),
600            (B256::with_last_byte(3), U256::from(4)),
601        ]);
602        assert_hashed_trie_root(data.iter());
603    }
604
605    #[test]
606    fn test_root_known_hash() {
607        let root_hash = b256!("45596e474b536a6b4d64764e4f75514d544577646c414e684271706871446456");
608        let mut hb = HashBuilder::default();
609        hb.add_branch(Nibbles::default(), root_hash, false);
610        assert_eq!(hb.root(), root_hash);
611    }
612
613    #[test]
614    fn manual_branch_node_ok() {
615        let raw_input = vec![
616            (hex!("646f").to_vec(), hex!("76657262").to_vec()),
617            (hex!("676f6f64").to_vec(), hex!("7075707079").to_vec()),
618        ];
619        let expected = triehash_trie_root(raw_input.clone());
620
621        // We create the hash builder and add the leaves
622        let mut hb = HashBuilder::default();
623        for (key, val) in &raw_input {
624            hb.add_leaf(Nibbles::unpack(key), val);
625        }
626
627        // Manually create the branch node that should be there after the first 2 leaves are added.
628        // Skip the 0th element given in this example they have a common prefix and will
629        // collapse to a Branch node.
630        let leaf1 = LeafNode::new(Nibbles::unpack(&raw_input[0].0[1..]), raw_input[0].1.clone());
631        let leaf2 = LeafNode::new(Nibbles::unpack(&raw_input[1].0[1..]), raw_input[1].1.clone());
632        let mut branch: [&dyn Encodable; 17] = [b""; 17];
633        // We set this to `4` and `7` because that matches the 2nd element of the corresponding
634        // leaves. We set this to `7` because the 2nd element of Leaf 1 is `7`.
635        branch[4] = &leaf1;
636        branch[7] = &leaf2;
637        let mut branch_node_rlp = Vec::new();
638        alloy_rlp::encode_list::<_, dyn Encodable>(&branch, &mut branch_node_rlp);
639        let branch_node_hash = keccak256(branch_node_rlp);
640
641        let mut hb2 = HashBuilder::default();
642        // Insert the branch with the `0x6` shared prefix.
643        hb2.add_branch(Nibbles::from_nibbles_unchecked([0x6]), branch_node_hash, false);
644
645        assert_eq!(hb.root(), expected);
646        assert_eq!(hb2.root(), expected);
647    }
648}
alloy_trie/hash_builder/mod.rs

alloy_trie/hash_builder/
mod.rs
