reth_trie_common/
proofs.rs

Help
1//! Merkle trie proofs.
2
3use crate::{Nibbles, TrieAccount};
4use alloc::{borrow::Cow, vec::Vec};
5use alloy_consensus::constants::KECCAK_EMPTY;
6use alloy_primitives::{
7    keccak256,
8    map::{hash_map, B256Map, B256Set, HashMap},
9    Address, Bytes, B256, U256,
10};
11use alloy_rlp::{encode_fixed_size, Decodable, EMPTY_STRING_CODE};
12use alloy_trie::{
13    nodes::TrieNode,
14    proof::{verify_proof, DecodedProofNodes, ProofNodes, ProofVerificationError},
15    TrieMask, EMPTY_ROOT_HASH,
16};
17use derive_more::{Deref, DerefMut, IntoIterator};
18use itertools::Itertools;
19use reth_primitives_traits::Account;
20
21/// Proof targets map.
22#[derive(Deref, DerefMut, IntoIterator, Clone, PartialEq, Eq, Default, Debug)]
23pub struct MultiProofTargets(B256Map<B256Set>);
24
25impl FromIterator<(B256, B256Set)> for MultiProofTargets {
26    fn from_iter<T: IntoIterator<Item = (B256, B256Set)>>(iter: T) -> Self {
27        Self(B256Map::from_iter(iter))
28    }
29}
30
31impl MultiProofTargets {
32    /// Creates an empty `MultiProofTargets` with at least the specified capacity.
33    pub fn with_capacity(capacity: usize) -> Self {
34        Self(B256Map::with_capacity_and_hasher(capacity, Default::default()))
35    }
36
37    /// Create `MultiProofTargets` with a single account as a target.
38    pub fn account(hashed_address: B256) -> Self {
39        Self::accounts([hashed_address])
40    }
41
42    /// Create `MultiProofTargets` with a single account and slots as targets.
43    pub fn account_with_slots<I: IntoIterator<Item = B256>>(
44        hashed_address: B256,
45        slots_iter: I,
46    ) -> Self {
47        Self(B256Map::from_iter([(hashed_address, slots_iter.into_iter().collect())]))
48    }
49
50    /// Create `MultiProofTargets` only from accounts.
51    pub fn accounts<I: IntoIterator<Item = B256>>(iter: I) -> Self {
52        Self(iter.into_iter().map(|hashed_address| (hashed_address, Default::default())).collect())
53    }
54
55    /// Retains the targets representing the difference,
56    /// i.e., the values that are in `self` but not in `other`.
57    pub fn retain_difference(&mut self, other: &Self) {
58        self.0.retain(|hashed_address, hashed_slots| {
59            if let Some(other_hashed_slots) = other.get(hashed_address) {
60                hashed_slots.retain(|hashed_slot| !other_hashed_slots.contains(hashed_slot));
61                !hashed_slots.is_empty()
62            } else {
63                true
64            }
65        });
66    }
67
68    /// Extend multi proof targets with contents of other.
69    pub fn extend(&mut self, other: Self) {
70        self.extend_inner(Cow::Owned(other));
71    }
72
73    /// Extend multi proof targets with contents of other.
74    ///
75    /// Slightly less efficient than [`Self::extend`], but preferred to `extend(other.clone())`.
76    pub fn extend_ref(&mut self, other: &Self) {
77        self.extend_inner(Cow::Borrowed(other));
78    }
79
80    fn extend_inner(&mut self, other: Cow<'_, Self>) {
81        for (hashed_address, hashed_slots) in other.iter() {
82            self.entry(*hashed_address).or_default().extend(hashed_slots);
83        }
84    }
85
86    /// Returns an iterator that yields chunks of the specified size.
87    ///
88    /// See [`ChunkedMultiProofTargets`] for more information.
89    pub fn chunks(self, size: usize) -> ChunkedMultiProofTargets {
90        ChunkedMultiProofTargets::new(self, size)
91    }
92}
93
94/// An iterator that yields chunks of the proof targets of at most `size` account and storage
95/// targets.
96///
97/// For example, for the following proof targets:
98/// ```text
99/// - 0x1: [0x10, 0x20, 0x30]
100/// - 0x2: [0x40]
101/// - 0x3: []
102/// ```
103///
104/// and `size = 2`, the iterator will yield the following chunks:
105/// ```text
106/// - { 0x1: [0x10, 0x20] }
107/// - { 0x1: [0x30], 0x2: [0x40] }
108/// - { 0x3: [] }
109/// ```
110///
111/// It follows two rules:
112/// - If account has associated storage slots, each storage slot is counted towards the chunk size.
113/// - If account has no associated storage slots, the account is counted towards the chunk size.
114#[derive(Debug)]
115pub struct ChunkedMultiProofTargets {
116    flattened_targets: alloc::vec::IntoIter<(B256, Option<B256>)>,
117    size: usize,
118}
119
120impl ChunkedMultiProofTargets {
121    fn new(targets: MultiProofTargets, size: usize) -> Self {
122        let flattened_targets = targets
123            .into_iter()
124            .flat_map(|(address, slots)| {
125                if slots.is_empty() {
126                    // If the account has no storage slots, we still need to yield the account
127                    // address with empty storage slots. `None` here means that
128                    // there's no storage slot to fetch.
129                    itertools::Either::Left(core::iter::once((address, None)))
130                } else {
131                    itertools::Either::Right(
132                        slots.into_iter().map(move |slot| (address, Some(slot))),
133                    )
134                }
135            })
136            .sorted();
137        Self { flattened_targets, size }
138    }
139}
140
141impl Iterator for ChunkedMultiProofTargets {
142    type Item = MultiProofTargets;
143
144    fn next(&mut self) -> Option<Self::Item> {
145        let chunk = self.flattened_targets.by_ref().take(self.size).fold(
146            MultiProofTargets::default(),
147            |mut acc, (address, slot)| {
148                let entry = acc.entry(address).or_default();
149                if let Some(slot) = slot {
150                    entry.insert(slot);
151                }
152                acc
153            },
154        );
155
156        if chunk.is_empty() {
157            None
158        } else {
159            Some(chunk)
160        }
161    }
162}
163
164/// The state multiproof of target accounts and multiproofs of their storage tries.
165/// Multiproof is effectively a state subtrie that only contains the nodes
166/// in the paths of target accounts.
167#[derive(Clone, Default, Debug, PartialEq, Eq)]
168pub struct MultiProof {
169    /// State trie multiproof for requested accounts.
170    pub account_subtree: ProofNodes,
171    /// The hash masks of the branch nodes in the account proof.
172    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
173    /// The tree masks of the branch nodes in the account proof.
174    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
175    /// Storage trie multiproofs.
176    pub storages: B256Map<StorageMultiProof>,
177}
178
179impl MultiProof {
180    /// Returns true if the multiproof is empty.
181    pub fn is_empty(&self) -> bool {
182        self.account_subtree.is_empty() &&
183            self.branch_node_hash_masks.is_empty() &&
184            self.branch_node_tree_masks.is_empty() &&
185            self.storages.is_empty()
186    }
187
188    /// Return the account proof nodes for the given account path.
189    pub fn account_proof_nodes(&self, path: &Nibbles) -> Vec<(Nibbles, Bytes)> {
190        self.account_subtree.matching_nodes_sorted(path)
191    }
192
193    /// Return the storage proof nodes for the given storage slots of the account path.
194    pub fn storage_proof_nodes(
195        &self,
196        hashed_address: B256,
197        slots: impl IntoIterator<Item = B256>,
198    ) -> Vec<(B256, Vec<(Nibbles, Bytes)>)> {
199        self.storages
200            .get(&hashed_address)
201            .map(|storage_mp| {
202                slots
203                    .into_iter()
204                    .map(|slot| {
205                        let nibbles = Nibbles::unpack(slot);
206                        (slot, storage_mp.subtree.matching_nodes_sorted(&nibbles))
207                    })
208                    .collect()
209            })
210            .unwrap_or_default()
211    }
212
213    /// Construct the account proof from the multiproof.
214    pub fn account_proof(
215        &self,
216        address: Address,
217        slots: &[B256],
218    ) -> Result<AccountProof, alloy_rlp::Error> {
219        let hashed_address = keccak256(address);
220        let nibbles = Nibbles::unpack(hashed_address);
221
222        // Retrieve the account proof.
223        let proof = self
224            .account_proof_nodes(&nibbles)
225            .into_iter()
226            .map(|(_, node)| node)
227            .collect::<Vec<_>>();
228
229        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
230        // then the node contains the encoded trie account.
231        let info = 'info: {
232            if let Some(last) = proof.last() {
233                if let TrieNode::Leaf(leaf) = TrieNode::decode(&mut &last[..])? {
234                    if nibbles.ends_with(&leaf.key) {
235                        let account = TrieAccount::decode(&mut &leaf.value[..])?;
236                        break 'info Some(Account {
237                            balance: account.balance,
238                            nonce: account.nonce,
239                            bytecode_hash: (account.code_hash != KECCAK_EMPTY)
240                                .then_some(account.code_hash),
241                        })
242                    }
243                }
244            }
245            None
246        };
247
248        // Retrieve proofs for requested storage slots.
249        let storage_multiproof = self.storages.get(&hashed_address);
250        let storage_root = storage_multiproof.map(|m| m.root).unwrap_or(EMPTY_ROOT_HASH);
251        let mut storage_proofs = Vec::with_capacity(slots.len());
252        for slot in slots {
253            let proof = if let Some(multiproof) = &storage_multiproof {
254                multiproof.storage_proof(*slot)?
255            } else {
256                StorageProof::new(*slot)
257            };
258            storage_proofs.push(proof);
259        }
260        Ok(AccountProof { address, info, proof, storage_root, storage_proofs })
261    }
262
263    /// Extends this multiproof with another one, merging both account and storage
264    /// proofs.
265    pub fn extend(&mut self, other: Self) {
266        self.account_subtree.extend_from(other.account_subtree);
267
268        self.branch_node_hash_masks.extend(other.branch_node_hash_masks);
269        self.branch_node_tree_masks.extend(other.branch_node_tree_masks);
270
271        for (hashed_address, storage) in other.storages {
272            match self.storages.entry(hashed_address) {
273                hash_map::Entry::Occupied(mut entry) => {
274                    debug_assert_eq!(entry.get().root, storage.root);
275                    let entry = entry.get_mut();
276                    entry.subtree.extend_from(storage.subtree);
277                    entry.branch_node_hash_masks.extend(storage.branch_node_hash_masks);
278                    entry.branch_node_tree_masks.extend(storage.branch_node_tree_masks);
279                }
280                hash_map::Entry::Vacant(entry) => {
281                    entry.insert(storage);
282                }
283            }
284        }
285    }
286
287    /// Create a [`MultiProof`] from a [`StorageMultiProof`].
288    pub fn from_storage_proof(hashed_address: B256, storage_proof: StorageMultiProof) -> Self {
289        Self {
290            storages: B256Map::from_iter([(hashed_address, storage_proof)]),
291            ..Default::default()
292        }
293    }
294}
295
296/// This is a type of [`MultiProof`] that uses decoded proofs, meaning these proofs are stored as a
297/// collection of [`TrieNode`]s instead of RLP-encoded bytes.
298#[derive(Clone, Default, Debug, PartialEq, Eq)]
299pub struct DecodedMultiProof {
300    /// State trie multiproof for requested accounts.
301    pub account_subtree: DecodedProofNodes,
302    /// The hash masks of the branch nodes in the account proof.
303    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
304    /// The tree masks of the branch nodes in the account proof.
305    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
306    /// Storage trie multiproofs.
307    pub storages: B256Map<DecodedStorageMultiProof>,
308}
309
310impl DecodedMultiProof {
311    /// Return the account proof nodes for the given account path.
312    pub fn account_proof_nodes(&self, path: &Nibbles) -> Vec<(Nibbles, TrieNode)> {
313        self.account_subtree.matching_nodes_sorted(path)
314    }
315
316    /// Return the storage proof nodes for the given storage slots of the account path.
317    pub fn storage_proof_nodes(
318        &self,
319        hashed_address: B256,
320        slots: impl IntoIterator<Item = B256>,
321    ) -> Vec<(B256, Vec<(Nibbles, TrieNode)>)> {
322        self.storages
323            .get(&hashed_address)
324            .map(|storage_mp| {
325                slots
326                    .into_iter()
327                    .map(|slot| {
328                        let nibbles = Nibbles::unpack(slot);
329                        (slot, storage_mp.subtree.matching_nodes_sorted(&nibbles))
330                    })
331                    .collect()
332            })
333            .unwrap_or_default()
334    }
335
336    /// Construct the account proof from the multiproof.
337    pub fn account_proof(
338        &self,
339        address: Address,
340        slots: &[B256],
341    ) -> Result<DecodedAccountProof, alloy_rlp::Error> {
342        let hashed_address = keccak256(address);
343        let nibbles = Nibbles::unpack(hashed_address);
344
345        // Retrieve the account proof.
346        let proof = self
347            .account_proof_nodes(&nibbles)
348            .into_iter()
349            .map(|(_, node)| node)
350            .collect::<Vec<_>>();
351
352        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
353        // then the node contains the encoded trie account.
354        let info = 'info: {
355            if let Some(TrieNode::Leaf(leaf)) = proof.last() {
356                if nibbles.ends_with(&leaf.key) {
357                    let account = TrieAccount::decode(&mut &leaf.value[..])?;
358                    break 'info Some(Account {
359                        balance: account.balance,
360                        nonce: account.nonce,
361                        bytecode_hash: (account.code_hash != KECCAK_EMPTY)
362                            .then_some(account.code_hash),
363                    })
364                }
365            }
366            None
367        };
368
369        // Retrieve proofs for requested storage slots.
370        let storage_multiproof = self.storages.get(&hashed_address);
371        let storage_root = storage_multiproof.map(|m| m.root).unwrap_or(EMPTY_ROOT_HASH);
372        let mut storage_proofs = Vec::with_capacity(slots.len());
373        for slot in slots {
374            let proof = if let Some(multiproof) = &storage_multiproof {
375                multiproof.storage_proof(*slot)?
376            } else {
377                DecodedStorageProof::new(*slot)
378            };
379            storage_proofs.push(proof);
380        }
381        Ok(DecodedAccountProof { address, info, proof, storage_root, storage_proofs })
382    }
383
384    /// Extends this multiproof with another one, merging both account and storage
385    /// proofs.
386    pub fn extend(&mut self, other: Self) {
387        self.account_subtree.extend_from(other.account_subtree);
388
389        self.branch_node_hash_masks.extend(other.branch_node_hash_masks);
390        self.branch_node_tree_masks.extend(other.branch_node_tree_masks);
391
392        for (hashed_address, storage) in other.storages {
393            match self.storages.entry(hashed_address) {
394                hash_map::Entry::Occupied(mut entry) => {
395                    debug_assert_eq!(entry.get().root, storage.root);
396                    let entry = entry.get_mut();
397                    entry.subtree.extend_from(storage.subtree);
398                    entry.branch_node_hash_masks.extend(storage.branch_node_hash_masks);
399                    entry.branch_node_tree_masks.extend(storage.branch_node_tree_masks);
400                }
401                hash_map::Entry::Vacant(entry) => {
402                    entry.insert(storage);
403                }
404            }
405        }
406    }
407}
408
409/// The merkle multiproof of storage trie.
410#[derive(Clone, Debug, PartialEq, Eq)]
411pub struct StorageMultiProof {
412    /// Storage trie root.
413    pub root: B256,
414    /// Storage multiproof for requested slots.
415    pub subtree: ProofNodes,
416    /// The hash masks of the branch nodes in the storage proof.
417    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
418    /// The tree masks of the branch nodes in the storage proof.
419    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
420}
421
422impl StorageMultiProof {
423    /// Create new storage multiproof for empty trie.
424    pub fn empty() -> Self {
425        Self {
426            root: EMPTY_ROOT_HASH,
427            subtree: ProofNodes::from_iter([(
428                Nibbles::default(),
429                Bytes::from([EMPTY_STRING_CODE]),
430            )]),
431            branch_node_hash_masks: HashMap::default(),
432            branch_node_tree_masks: HashMap::default(),
433        }
434    }
435
436    /// Return storage proofs for the target storage slot (unhashed).
437    pub fn storage_proof(&self, slot: B256) -> Result<StorageProof, alloy_rlp::Error> {
438        let nibbles = Nibbles::unpack(keccak256(slot));
439
440        // Retrieve the storage proof.
441        let proof = self
442            .subtree
443            .matching_nodes_iter(&nibbles)
444            .sorted_by(|a, b| a.0.cmp(b.0))
445            .map(|(_, node)| node.clone())
446            .collect::<Vec<_>>();
447
448        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
449        // then the node contains the encoded slot value.
450        let value = 'value: {
451            if let Some(last) = proof.last() {
452                if let TrieNode::Leaf(leaf) = TrieNode::decode(&mut &last[..])? {
453                    if nibbles.ends_with(&leaf.key) {
454                        break 'value U256::decode(&mut &leaf.value[..])?
455                    }
456                }
457            }
458            U256::ZERO
459        };
460
461        Ok(StorageProof { key: slot, nibbles, value, proof })
462    }
463}
464
465/// The decoded merkle multiproof for a storage trie.
466#[derive(Clone, Debug, PartialEq, Eq)]
467pub struct DecodedStorageMultiProof {
468    /// Storage trie root.
469    pub root: B256,
470    /// Storage multiproof for requested slots.
471    pub subtree: DecodedProofNodes,
472    /// The hash masks of the branch nodes in the storage proof.
473    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
474    /// The tree masks of the branch nodes in the storage proof.
475    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
476}
477
478impl DecodedStorageMultiProof {
479    /// Create new storage multiproof for empty trie.
480    pub fn empty() -> Self {
481        Self {
482            root: EMPTY_ROOT_HASH,
483            subtree: DecodedProofNodes::from_iter([(Nibbles::default(), TrieNode::EmptyRoot)]),
484            branch_node_hash_masks: HashMap::default(),
485            branch_node_tree_masks: HashMap::default(),
486        }
487    }
488
489    /// Return storage proofs for the target storage slot (unhashed).
490    pub fn storage_proof(&self, slot: B256) -> Result<DecodedStorageProof, alloy_rlp::Error> {
491        let nibbles = Nibbles::unpack(keccak256(slot));
492
493        // Retrieve the storage proof.
494        let proof = self
495            .subtree
496            .matching_nodes_iter(&nibbles)
497            .sorted_by(|a, b| a.0.cmp(b.0))
498            .map(|(_, node)| node.clone())
499            .collect::<Vec<_>>();
500
501        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
502        // then the node contains the encoded slot value.
503        let value = 'value: {
504            if let Some(TrieNode::Leaf(leaf)) = proof.last() {
505                if nibbles.ends_with(&leaf.key) {
506                    break 'value U256::decode(&mut &leaf.value[..])?
507                }
508            }
509            U256::ZERO
510        };
511
512        Ok(DecodedStorageProof { key: slot, nibbles, value, proof })
513    }
514}
515
516/// The merkle proof with the relevant account info.
517#[derive(Clone, PartialEq, Eq, Debug)]
518#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
519#[cfg_attr(any(test, feature = "serde"), serde(rename_all = "camelCase"))]
520pub struct AccountProof {
521    /// The address associated with the account.
522    pub address: Address,
523    /// Account info, if any.
524    pub info: Option<Account>,
525    /// Array of rlp-serialized merkle trie nodes which starting from the root node and
526    /// following the path of the hashed address as key.
527    pub proof: Vec<Bytes>,
528    /// The storage trie root.
529    pub storage_root: B256,
530    /// Array of storage proofs as requested.
531    pub storage_proofs: Vec<StorageProof>,
532}
533
534#[cfg(feature = "eip1186")]
535impl AccountProof {
536    /// Convert into an EIP-1186 account proof response
537    pub fn into_eip1186_response(
538        self,
539        slots: Vec<alloy_serde::JsonStorageKey>,
540    ) -> alloy_rpc_types_eth::EIP1186AccountProofResponse {
541        let info = self.info.unwrap_or_default();
542        alloy_rpc_types_eth::EIP1186AccountProofResponse {
543            address: self.address,
544            balance: info.balance,
545            code_hash: info.get_bytecode_hash(),
546            nonce: info.nonce,
547            storage_hash: self.storage_root,
548            account_proof: self.proof,
549            storage_proof: self
550                .storage_proofs
551                .into_iter()
552                .filter_map(|proof| {
553                    let input_slot = slots.iter().find(|s| s.as_b256() == proof.key)?;
554                    Some(proof.into_eip1186_proof(*input_slot))
555                })
556                .collect(),
557        }
558    }
559
560    /// Converts an
561    /// [`EIP1186AccountProofResponse`](alloy_rpc_types_eth::EIP1186AccountProofResponse) to an
562    /// [`AccountProof`].
563    ///
564    /// This is the inverse of [`Self::into_eip1186_response`]
565    pub fn from_eip1186_proof(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
566        let alloy_rpc_types_eth::EIP1186AccountProofResponse {
567            nonce,
568            address,
569            balance,
570            code_hash,
571            storage_hash,
572            account_proof,
573            storage_proof,
574            ..
575        } = proof;
576        let storage_proofs = storage_proof.into_iter().map(Into::into).collect();
577
578        let (storage_root, info) = if nonce == 0 &&
579            balance.is_zero() &&
580            storage_hash.is_zero() &&
581            code_hash == KECCAK_EMPTY
582        {
583            // Account does not exist in state. Return `None` here to prevent proof
584            // verification.
585            (EMPTY_ROOT_HASH, None)
586        } else {
587            (storage_hash, Some(Account { nonce, balance, bytecode_hash: code_hash.into() }))
588        };
589
590        Self { address, info, proof: account_proof, storage_root, storage_proofs }
591    }
592}
593
594#[cfg(feature = "eip1186")]
595impl From<alloy_rpc_types_eth::EIP1186AccountProofResponse> for AccountProof {
596    fn from(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
597        Self::from_eip1186_proof(proof)
598    }
599}
600
601impl Default for AccountProof {
602    fn default() -> Self {
603        Self::new(Address::default())
604    }
605}
606
607impl AccountProof {
608    /// Create new account proof entity.
609    pub const fn new(address: Address) -> Self {
610        Self {
611            address,
612            info: None,
613            proof: Vec::new(),
614            storage_root: EMPTY_ROOT_HASH,
615            storage_proofs: Vec::new(),
616        }
617    }
618
619    /// Verify the storage proofs and account proof against the provided state root.
620    #[expect(clippy::result_large_err)]
621    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
622        // Verify storage proofs.
623        for storage_proof in &self.storage_proofs {
624            storage_proof.verify(self.storage_root)?;
625        }
626
627        // Verify the account proof.
628        let expected = if self.info.is_none() && self.storage_root == EMPTY_ROOT_HASH {
629            None
630        } else {
631            Some(alloy_rlp::encode(
632                self.info.unwrap_or_default().into_trie_account(self.storage_root),
633            ))
634        };
635        let nibbles = Nibbles::unpack(keccak256(self.address));
636        verify_proof(root, nibbles, expected, &self.proof)
637    }
638}
639
640/// The merkle proof with the relevant account info.
641#[derive(Clone, PartialEq, Eq, Debug)]
642pub struct DecodedAccountProof {
643    /// The address associated with the account.
644    pub address: Address,
645    /// Account info.
646    pub info: Option<Account>,
647    /// Array of merkle trie nodes which starting from the root node and following the path of the
648    /// hashed address as key.
649    pub proof: Vec<TrieNode>,
650    /// The storage trie root.
651    pub storage_root: B256,
652    /// Array of storage proofs as requested.
653    pub storage_proofs: Vec<DecodedStorageProof>,
654}
655
656impl Default for DecodedAccountProof {
657    fn default() -> Self {
658        Self::new(Address::default())
659    }
660}
661
662impl DecodedAccountProof {
663    /// Create new account proof entity.
664    pub const fn new(address: Address) -> Self {
665        Self {
666            address,
667            info: None,
668            proof: Vec::new(),
669            storage_root: EMPTY_ROOT_HASH,
670            storage_proofs: Vec::new(),
671        }
672    }
673}
674
675/// The merkle proof of the storage entry.
676#[derive(Clone, PartialEq, Eq, Default, Debug)]
677#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
678pub struct StorageProof {
679    /// The raw storage key.
680    pub key: B256,
681    /// The hashed storage key nibbles.
682    pub nibbles: Nibbles,
683    /// The storage value.
684    pub value: U256,
685    /// Array of rlp-serialized merkle trie nodes which starting from the storage root node and
686    /// following the path of the hashed storage slot as key.
687    pub proof: Vec<Bytes>,
688}
689
690impl StorageProof {
691    /// Create new storage proof from the storage slot.
692    pub fn new(key: B256) -> Self {
693        let nibbles = Nibbles::unpack(keccak256(key));
694        Self { key, nibbles, ..Default::default() }
695    }
696
697    /// Create new storage proof from the storage slot and its pre-hashed image.
698    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
699        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
700    }
701
702    /// Create new storage proof from the storage slot and its pre-hashed image.
703    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
704        Self { key, nibbles, ..Default::default() }
705    }
706
707    /// Set proof nodes on storage proof.
708    pub fn with_proof(mut self, proof: Vec<Bytes>) -> Self {
709        self.proof = proof;
710        self
711    }
712
713    /// Verify the proof against the provided storage root.
714    #[expect(clippy::result_large_err)]
715    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
716        let expected =
717            if self.value.is_zero() { None } else { Some(encode_fixed_size(&self.value).to_vec()) };
718        verify_proof(root, self.nibbles.clone(), expected, &self.proof)
719    }
720}
721
722#[cfg(feature = "eip1186")]
723impl StorageProof {
724    /// Convert into an EIP-1186 storage proof
725    pub fn into_eip1186_proof(
726        self,
727        slot: alloy_serde::JsonStorageKey,
728    ) -> alloy_rpc_types_eth::EIP1186StorageProof {
729        alloy_rpc_types_eth::EIP1186StorageProof { key: slot, value: self.value, proof: self.proof }
730    }
731
732    /// Convert from an
733    /// [`EIP1186StorageProof`](alloy_rpc_types_eth::EIP1186StorageProof)
734    ///
735    /// This is the inverse of [`Self::into_eip1186_proof`].
736    pub fn from_eip1186_proof(storage_proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
737        Self {
738            value: storage_proof.value,
739            proof: storage_proof.proof,
740            ..Self::new(storage_proof.key.as_b256())
741        }
742    }
743}
744
745#[cfg(feature = "eip1186")]
746impl From<alloy_rpc_types_eth::EIP1186StorageProof> for StorageProof {
747    fn from(proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
748        Self::from_eip1186_proof(proof)
749    }
750}
751
752/// The merkle proof of the storage entry, using decoded proofs.
753#[derive(Clone, PartialEq, Eq, Default, Debug)]
754pub struct DecodedStorageProof {
755    /// The raw storage key.
756    pub key: B256,
757    /// The hashed storage key nibbles.
758    pub nibbles: Nibbles,
759    /// The storage value.
760    pub value: U256,
761    /// Array of merkle trie nodes which starting from the storage root node and following the path
762    /// of the hashed storage slot as key.
763    pub proof: Vec<TrieNode>,
764}
765
766impl DecodedStorageProof {
767    /// Create new storage proof from the storage slot.
768    pub fn new(key: B256) -> Self {
769        let nibbles = Nibbles::unpack(keccak256(key));
770        Self { key, nibbles, ..Default::default() }
771    }
772
773    /// Create new storage proof from the storage slot and its pre-hashed image.
774    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
775        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
776    }
777
778    /// Create new storage proof from the storage slot and its pre-hashed image.
779    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
780        Self { key, nibbles, ..Default::default() }
781    }
782
783    /// Set proof nodes on storage proof.
784    pub fn with_proof(mut self, proof: Vec<TrieNode>) -> Self {
785        self.proof = proof;
786        self
787    }
788}
789
790/// Implementation of hasher using our keccak256 hashing function
791/// for compatibility with `triehash` crate.
792#[cfg(any(test, feature = "test-utils"))]
793pub mod triehash {
794    use alloy_primitives::{keccak256, B256};
795    use alloy_rlp::RlpEncodable;
796    use hash_db::Hasher;
797    use plain_hasher::PlainHasher;
798
799    /// A [Hasher] that calculates a keccak256 hash of the given data.
800    #[derive(Default, Debug, Clone, PartialEq, Eq, RlpEncodable)]
801    #[non_exhaustive]
802    pub struct KeccakHasher;
803
804    #[cfg(any(test, feature = "test-utils"))]
805    impl Hasher for KeccakHasher {
806        type Out = B256;
807        type StdHasher = PlainHasher;
808
809        const LENGTH: usize = 32;
810
811        fn hash(x: &[u8]) -> Self::Out {
812            keccak256(x)
813        }
814    }
815}
816
817#[cfg(test)]
818mod tests {
819    use super::*;
820
821    #[test]
822    fn test_multiproof_extend_account_proofs() {
823        let mut proof1 = MultiProof::default();
824        let mut proof2 = MultiProof::default();
825
826        let addr1 = B256::random();
827        let addr2 = B256::random();
828
829        proof1.account_subtree.insert(
830            Nibbles::unpack(addr1),
831            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
832        );
833        proof2.account_subtree.insert(
834            Nibbles::unpack(addr2),
835            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
836        );
837
838        proof1.extend(proof2);
839
840        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr1)));
841        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr2)));
842    }
843
844    #[test]
845    fn test_multiproof_extend_storage_proofs() {
846        let mut proof1 = MultiProof::default();
847        let mut proof2 = MultiProof::default();
848
849        let addr = B256::random();
850        let root = B256::random();
851
852        let mut subtree1 = ProofNodes::default();
853        subtree1.insert(
854            Nibbles::from_nibbles(vec![0]),
855            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
856        );
857        proof1.storages.insert(
858            addr,
859            StorageMultiProof {
860                root,
861                subtree: subtree1,
862                branch_node_hash_masks: HashMap::default(),
863                branch_node_tree_masks: HashMap::default(),
864            },
865        );
866
867        let mut subtree2 = ProofNodes::default();
868        subtree2.insert(
869            Nibbles::from_nibbles(vec![1]),
870            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
871        );
872        proof2.storages.insert(
873            addr,
874            StorageMultiProof {
875                root,
876                subtree: subtree2,
877                branch_node_hash_masks: HashMap::default(),
878                branch_node_tree_masks: HashMap::default(),
879            },
880        );
881
882        proof1.extend(proof2);
883
884        let storage = proof1.storages.get(&addr).unwrap();
885        assert_eq!(storage.root, root);
886        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![0])));
887        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![1])));
888    }
889
890    #[test]
891    fn test_multi_proof_retain_difference() {
892        let mut empty = MultiProofTargets::default();
893        empty.retain_difference(&Default::default());
894        assert!(empty.is_empty());
895
896        let targets = MultiProofTargets::accounts((0..10).map(B256::with_last_byte));
897
898        let mut diffed = targets.clone();
899        diffed.retain_difference(&MultiProofTargets::account(B256::with_last_byte(11)));
900        assert_eq!(diffed, targets);
901
902        diffed.retain_difference(&MultiProofTargets::accounts((0..5).map(B256::with_last_byte)));
903        assert_eq!(diffed, MultiProofTargets::accounts((5..10).map(B256::with_last_byte)));
904
905        diffed.retain_difference(&targets);
906        assert!(diffed.is_empty());
907
908        let mut targets = MultiProofTargets::default();
909        let (account1, account2, account3) =
910            (1..=3).map(B256::with_last_byte).collect_tuple().unwrap();
911        let account2_slots = (1..5).map(B256::with_last_byte).collect::<B256Set>();
912        targets.insert(account1, B256Set::from_iter([B256::with_last_byte(1)]));
913        targets.insert(account2, account2_slots.clone());
914        targets.insert(account3, B256Set::from_iter([B256::with_last_byte(1)]));
915
916        let mut diffed = targets.clone();
917        diffed.retain_difference(&MultiProofTargets::accounts((1..=3).map(B256::with_last_byte)));
918        assert_eq!(diffed, targets);
919
920        // remove last 3 slots for account 2
921        let mut account2_slots_expected_len = account2_slots.len();
922        for slot in account2_slots.iter().skip(1) {
923            diffed.retain_difference(&MultiProofTargets::account_with_slots(account2, [*slot]));
924            account2_slots_expected_len -= 1;
925            assert_eq!(
926                diffed.get(&account2).map(|slots| slots.len()),
927                Some(account2_slots_expected_len)
928            );
929        }
930
931        diffed.retain_difference(&targets);
932        assert!(diffed.is_empty());
933    }
934
935    #[test]
936    fn test_multi_proof_retain_difference_no_overlap() {
937        let mut targets = MultiProofTargets::default();
938
939        // populate some targets
940        let (addr1, addr2) = (B256::random(), B256::random());
941        let (slot1, slot2) = (B256::random(), B256::random());
942        targets.insert(addr1, vec![slot1].into_iter().collect());
943        targets.insert(addr2, vec![slot2].into_iter().collect());
944
945        let mut retained = targets.clone();
946        retained.retain_difference(&Default::default());
947        assert_eq!(retained, targets);
948
949        // add a different addr and slot to fetched proof targets
950        let mut other_targets = MultiProofTargets::default();
951        let addr3 = B256::random();
952        let slot3 = B256::random();
953        other_targets.insert(addr3, B256Set::from_iter([slot3]));
954
955        // check that the prefetch proof targets are the same because the fetched proof targets
956        // don't overlap with the prefetch targets
957        let mut retained = targets.clone();
958        retained.retain_difference(&other_targets);
959        assert_eq!(retained, targets);
960    }
961
962    #[test]
963    fn test_get_prefetch_proof_targets_remove_subset() {
964        // populate some targets
965        let mut targets = MultiProofTargets::default();
966        let (addr1, addr2) = (B256::random(), B256::random());
967        let (slot1, slot2) = (B256::random(), B256::random());
968        targets.insert(addr1, B256Set::from_iter([slot1]));
969        targets.insert(addr2, B256Set::from_iter([slot2]));
970
971        // add a subset of the first target to other proof targets
972        let other_targets = MultiProofTargets::account_with_slots(addr1, [slot1]);
973
974        let mut retained = targets.clone();
975        retained.retain_difference(&other_targets);
976
977        // check that the prefetch proof targets do not include the subset
978        assert_eq!(retained.len(), 1);
979        assert!(!retained.contains_key(&addr1));
980        assert!(retained.contains_key(&addr2));
981
982        // now add one more slot to the prefetch targets
983        let slot3 = B256::random();
984        targets.get_mut(&addr1).unwrap().insert(slot3);
985
986        let mut retained = targets.clone();
987        retained.retain_difference(&other_targets);
988
989        // check that the prefetch proof targets do not include the subset
990        // but include the new slot
991        assert_eq!(retained.len(), 2);
992        assert!(retained.contains_key(&addr1));
993        assert_eq!(retained.get(&addr1), Some(&B256Set::from_iter([slot3])));
994        assert!(retained.contains_key(&addr2));
995        assert_eq!(retained.get(&addr2), Some(&B256Set::from_iter([slot2])));
996    }
997
998    #[test]
999    #[cfg(feature = "eip1186")]
1000    fn eip_1186_roundtrip() {
1001        let mut acc = AccountProof {
1002            address: Address::random(),
1003            info: Some(
1004                // non-empty account
1005                Account { nonce: 100, balance: U256::ZERO, bytecode_hash: Some(KECCAK_EMPTY) },
1006            ),
1007            proof: vec![],
1008            storage_root: B256::ZERO,
1009            storage_proofs: vec![],
1010        };
1011
1012        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1013        let inverse: AccountProof = rpc_proof.into();
1014        assert_eq!(acc, inverse);
1015
1016        // make account empty
1017        acc.info.as_mut().unwrap().nonce = 0;
1018        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1019        let inverse: AccountProof = rpc_proof.into();
1020        acc.info.take();
1021        acc.storage_root = EMPTY_ROOT_HASH;
1022        assert_eq!(acc, inverse);
1023    }
1024}
reth_trie_common/proofs.rs

reth_trie_common/
proofs.rs
