reth_trie_common/
proofs.rs

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                let TrieNode::Leaf(leaf) = TrieNode::decode(&mut &last[..])? &&
234                nibbles.ends_with(&leaf.key)
235            {
236                let account = TrieAccount::decode(&mut &leaf.value[..])?;
237                break 'info Some(Account {
238                    balance: account.balance,
239                    nonce: account.nonce,
240                    bytecode_hash: (account.code_hash != KECCAK_EMPTY).then_some(account.code_hash),
241                })
242            }
243            None
244        };
245
246        // Retrieve proofs for requested storage slots.
247        let storage_multiproof = self.storages.get(&hashed_address);
248        let storage_root = storage_multiproof.map(|m| m.root).unwrap_or(EMPTY_ROOT_HASH);
249        let mut storage_proofs = Vec::with_capacity(slots.len());
250        for slot in slots {
251            let proof = if let Some(multiproof) = &storage_multiproof {
252                multiproof.storage_proof(*slot)?
253            } else {
254                StorageProof::new(*slot)
255            };
256            storage_proofs.push(proof);
257        }
258        Ok(AccountProof { address, info, proof, storage_root, storage_proofs })
259    }
260
261    /// Extends this multiproof with another one, merging both account and storage
262    /// proofs.
263    pub fn extend(&mut self, other: Self) {
264        self.account_subtree.extend_from(other.account_subtree);
265
266        self.branch_node_hash_masks.extend(other.branch_node_hash_masks);
267        self.branch_node_tree_masks.extend(other.branch_node_tree_masks);
268
269        for (hashed_address, storage) in other.storages {
270            match self.storages.entry(hashed_address) {
271                hash_map::Entry::Occupied(mut entry) => {
272                    debug_assert_eq!(entry.get().root, storage.root);
273                    let entry = entry.get_mut();
274                    entry.subtree.extend_from(storage.subtree);
275                    entry.branch_node_hash_masks.extend(storage.branch_node_hash_masks);
276                    entry.branch_node_tree_masks.extend(storage.branch_node_tree_masks);
277                }
278                hash_map::Entry::Vacant(entry) => {
279                    entry.insert(storage);
280                }
281            }
282        }
283    }
284
285    /// Create a [`MultiProof`] from a [`StorageMultiProof`].
286    pub fn from_storage_proof(hashed_address: B256, storage_proof: StorageMultiProof) -> Self {
287        Self {
288            storages: B256Map::from_iter([(hashed_address, storage_proof)]),
289            ..Default::default()
290        }
291    }
292}
293
294/// This is a type of [`MultiProof`] that uses decoded proofs, meaning these proofs are stored as a
295/// collection of [`TrieNode`]s instead of RLP-encoded bytes.
296#[derive(Clone, Default, Debug, PartialEq, Eq)]
297pub struct DecodedMultiProof {
298    /// State trie multiproof for requested accounts.
299    pub account_subtree: DecodedProofNodes,
300    /// The hash masks of the branch nodes in the account proof.
301    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
302    /// The tree masks of the branch nodes in the account proof.
303    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
304    /// Storage trie multiproofs.
305    pub storages: B256Map<DecodedStorageMultiProof>,
306}
307
308impl DecodedMultiProof {
309    /// Returns true if the multiproof is empty.
310    pub fn is_empty(&self) -> bool {
311        self.account_subtree.is_empty() &&
312            self.branch_node_hash_masks.is_empty() &&
313            self.branch_node_tree_masks.is_empty() &&
314            self.storages.is_empty()
315    }
316
317    /// Return the account proof nodes for the given account path.
318    pub fn account_proof_nodes(&self, path: &Nibbles) -> Vec<(Nibbles, TrieNode)> {
319        self.account_subtree.matching_nodes_sorted(path)
320    }
321
322    /// Return the storage proof nodes for the given storage slots of the account path.
323    pub fn storage_proof_nodes(
324        &self,
325        hashed_address: B256,
326        slots: impl IntoIterator<Item = B256>,
327    ) -> Vec<(B256, Vec<(Nibbles, TrieNode)>)> {
328        self.storages
329            .get(&hashed_address)
330            .map(|storage_mp| {
331                slots
332                    .into_iter()
333                    .map(|slot| {
334                        let nibbles = Nibbles::unpack(slot);
335                        (slot, storage_mp.subtree.matching_nodes_sorted(&nibbles))
336                    })
337                    .collect()
338            })
339            .unwrap_or_default()
340    }
341
342    /// Construct the account proof from the multiproof.
343    pub fn account_proof(
344        &self,
345        address: Address,
346        slots: &[B256],
347    ) -> Result<DecodedAccountProof, alloy_rlp::Error> {
348        let hashed_address = keccak256(address);
349        let nibbles = Nibbles::unpack(hashed_address);
350
351        // Retrieve the account proof.
352        let proof = self
353            .account_proof_nodes(&nibbles)
354            .into_iter()
355            .map(|(_, node)| node)
356            .collect::<Vec<_>>();
357
358        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
359        // then the node contains the encoded trie account.
360        let info = 'info: {
361            if let Some(TrieNode::Leaf(leaf)) = proof.last() &&
362                nibbles.ends_with(&leaf.key)
363            {
364                let account = TrieAccount::decode(&mut &leaf.value[..])?;
365                break 'info Some(Account {
366                    balance: account.balance,
367                    nonce: account.nonce,
368                    bytecode_hash: (account.code_hash != KECCAK_EMPTY).then_some(account.code_hash),
369                })
370            }
371            None
372        };
373
374        // Retrieve proofs for requested storage slots.
375        let storage_multiproof = self.storages.get(&hashed_address);
376        let storage_root = storage_multiproof.map(|m| m.root).unwrap_or(EMPTY_ROOT_HASH);
377        let mut storage_proofs = Vec::with_capacity(slots.len());
378        for slot in slots {
379            let proof = if let Some(multiproof) = &storage_multiproof {
380                multiproof.storage_proof(*slot)?
381            } else {
382                DecodedStorageProof::new(*slot)
383            };
384            storage_proofs.push(proof);
385        }
386        Ok(DecodedAccountProof { address, info, proof, storage_root, storage_proofs })
387    }
388
389    /// Extends this multiproof with another one, merging both account and storage
390    /// proofs.
391    pub fn extend(&mut self, other: Self) {
392        self.account_subtree.extend_from(other.account_subtree);
393
394        self.branch_node_hash_masks.extend(other.branch_node_hash_masks);
395        self.branch_node_tree_masks.extend(other.branch_node_tree_masks);
396
397        for (hashed_address, storage) in other.storages {
398            match self.storages.entry(hashed_address) {
399                hash_map::Entry::Occupied(mut entry) => {
400                    debug_assert_eq!(entry.get().root, storage.root);
401                    let entry = entry.get_mut();
402                    entry.subtree.extend_from(storage.subtree);
403                    entry.branch_node_hash_masks.extend(storage.branch_node_hash_masks);
404                    entry.branch_node_tree_masks.extend(storage.branch_node_tree_masks);
405                }
406                hash_map::Entry::Vacant(entry) => {
407                    entry.insert(storage);
408                }
409            }
410        }
411    }
412
413    /// Create a [`DecodedMultiProof`] from a [`DecodedStorageMultiProof`].
414    pub fn from_storage_proof(
415        hashed_address: B256,
416        storage_proof: DecodedStorageMultiProof,
417    ) -> Self {
418        Self {
419            storages: B256Map::from_iter([(hashed_address, storage_proof)]),
420            ..Default::default()
421        }
422    }
423}
424
425impl TryFrom<MultiProof> for DecodedMultiProof {
426    type Error = alloy_rlp::Error;
427
428    fn try_from(multi_proof: MultiProof) -> Result<Self, Self::Error> {
429        let account_subtree = DecodedProofNodes::try_from(multi_proof.account_subtree)?;
430        let storages = multi_proof
431            .storages
432            .into_iter()
433            .map(|(address, storage)| Ok((address, storage.try_into()?)))
434            .collect::<Result<B256Map<_>, alloy_rlp::Error>>()?;
435        Ok(Self {
436            account_subtree,
437            branch_node_hash_masks: multi_proof.branch_node_hash_masks,
438            branch_node_tree_masks: multi_proof.branch_node_tree_masks,
439            storages,
440        })
441    }
442}
443
444/// The merkle multiproof of storage trie.
445#[derive(Clone, Debug, PartialEq, Eq)]
446pub struct StorageMultiProof {
447    /// Storage trie root.
448    pub root: B256,
449    /// Storage multiproof for requested slots.
450    pub subtree: ProofNodes,
451    /// The hash masks of the branch nodes in the storage proof.
452    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
453    /// The tree masks of the branch nodes in the storage proof.
454    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
455}
456
457impl StorageMultiProof {
458    /// Create new storage multiproof for empty trie.
459    pub fn empty() -> Self {
460        Self {
461            root: EMPTY_ROOT_HASH,
462            subtree: ProofNodes::from_iter([(
463                Nibbles::default(),
464                Bytes::from([EMPTY_STRING_CODE]),
465            )]),
466            branch_node_hash_masks: HashMap::default(),
467            branch_node_tree_masks: HashMap::default(),
468        }
469    }
470
471    /// Return storage proofs for the target storage slot (unhashed).
472    pub fn storage_proof(&self, slot: B256) -> Result<StorageProof, alloy_rlp::Error> {
473        let nibbles = Nibbles::unpack(keccak256(slot));
474
475        // Retrieve the storage proof.
476        let proof = self
477            .subtree
478            .matching_nodes_iter(&nibbles)
479            .sorted_by(|a, b| a.0.cmp(b.0))
480            .map(|(_, node)| node.clone())
481            .collect::<Vec<_>>();
482
483        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
484        // then the node contains the encoded slot value.
485        let value = 'value: {
486            if let Some(last) = proof.last() &&
487                let TrieNode::Leaf(leaf) = TrieNode::decode(&mut &last[..])? &&
488                nibbles.ends_with(&leaf.key)
489            {
490                break 'value U256::decode(&mut &leaf.value[..])?
491            }
492            U256::ZERO
493        };
494
495        Ok(StorageProof { key: slot, nibbles, value, proof })
496    }
497}
498
499/// The decoded merkle multiproof for a storage trie.
500#[derive(Clone, Debug, PartialEq, Eq)]
501pub struct DecodedStorageMultiProof {
502    /// Storage trie root.
503    pub root: B256,
504    /// Storage multiproof for requested slots.
505    pub subtree: DecodedProofNodes,
506    /// The hash masks of the branch nodes in the storage proof.
507    pub branch_node_hash_masks: HashMap<Nibbles, TrieMask>,
508    /// The tree masks of the branch nodes in the storage proof.
509    pub branch_node_tree_masks: HashMap<Nibbles, TrieMask>,
510}
511
512impl DecodedStorageMultiProof {
513    /// Create new storage multiproof for empty trie.
514    pub fn empty() -> Self {
515        Self {
516            root: EMPTY_ROOT_HASH,
517            subtree: DecodedProofNodes::from_iter([(Nibbles::default(), TrieNode::EmptyRoot)]),
518            branch_node_hash_masks: HashMap::default(),
519            branch_node_tree_masks: HashMap::default(),
520        }
521    }
522
523    /// Return storage proofs for the target storage slot (unhashed).
524    pub fn storage_proof(&self, slot: B256) -> Result<DecodedStorageProof, alloy_rlp::Error> {
525        let nibbles = Nibbles::unpack(keccak256(slot));
526
527        // Retrieve the storage proof.
528        let proof = self
529            .subtree
530            .matching_nodes_iter(&nibbles)
531            .sorted_by(|a, b| a.0.cmp(b.0))
532            .map(|(_, node)| node.clone())
533            .collect::<Vec<_>>();
534
535        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
536        // then the node contains the encoded slot value.
537        let value = 'value: {
538            if let Some(TrieNode::Leaf(leaf)) = proof.last() &&
539                nibbles.ends_with(&leaf.key)
540            {
541                break 'value U256::decode(&mut &leaf.value[..])?
542            }
543            U256::ZERO
544        };
545
546        Ok(DecodedStorageProof { key: slot, nibbles, value, proof })
547    }
548}
549
550impl TryFrom<StorageMultiProof> for DecodedStorageMultiProof {
551    type Error = alloy_rlp::Error;
552
553    fn try_from(multi_proof: StorageMultiProof) -> Result<Self, Self::Error> {
554        let subtree = DecodedProofNodes::try_from(multi_proof.subtree)?;
555        Ok(Self {
556            root: multi_proof.root,
557            subtree,
558            branch_node_hash_masks: multi_proof.branch_node_hash_masks,
559            branch_node_tree_masks: multi_proof.branch_node_tree_masks,
560        })
561    }
562}
563
564/// The merkle proof with the relevant account info.
565#[derive(Clone, PartialEq, Eq, Debug)]
566#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
567#[cfg_attr(any(test, feature = "serde"), serde(rename_all = "camelCase"))]
568pub struct AccountProof {
569    /// The address associated with the account.
570    pub address: Address,
571    /// Account info, if any.
572    pub info: Option<Account>,
573    /// Array of rlp-serialized merkle trie nodes which starting from the root node and
574    /// following the path of the hashed address as key.
575    pub proof: Vec<Bytes>,
576    /// The storage trie root.
577    pub storage_root: B256,
578    /// Array of storage proofs as requested.
579    pub storage_proofs: Vec<StorageProof>,
580}
581
582#[cfg(feature = "eip1186")]
583impl AccountProof {
584    /// Convert into an EIP-1186 account proof response
585    pub fn into_eip1186_response(
586        self,
587        slots: Vec<alloy_serde::JsonStorageKey>,
588    ) -> alloy_rpc_types_eth::EIP1186AccountProofResponse {
589        let info = self.info.unwrap_or_default();
590        alloy_rpc_types_eth::EIP1186AccountProofResponse {
591            address: self.address,
592            balance: info.balance,
593            code_hash: info.get_bytecode_hash(),
594            nonce: info.nonce,
595            storage_hash: self.storage_root,
596            account_proof: self.proof,
597            storage_proof: self
598                .storage_proofs
599                .into_iter()
600                .filter_map(|proof| {
601                    let input_slot = slots.iter().find(|s| s.as_b256() == proof.key)?;
602                    Some(proof.into_eip1186_proof(*input_slot))
603                })
604                .collect(),
605        }
606    }
607
608    /// Converts an
609    /// [`EIP1186AccountProofResponse`](alloy_rpc_types_eth::EIP1186AccountProofResponse) to an
610    /// [`AccountProof`].
611    ///
612    /// This is the inverse of [`Self::into_eip1186_response`]
613    pub fn from_eip1186_proof(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
614        let alloy_rpc_types_eth::EIP1186AccountProofResponse {
615            nonce,
616            address,
617            balance,
618            code_hash,
619            storage_hash,
620            account_proof,
621            storage_proof,
622            ..
623        } = proof;
624        let storage_proofs = storage_proof.into_iter().map(Into::into).collect();
625
626        let (storage_root, info) = if nonce == 0 &&
627            balance.is_zero() &&
628            storage_hash.is_zero() &&
629            code_hash == KECCAK_EMPTY
630        {
631            // Account does not exist in state. Return `None` here to prevent proof
632            // verification.
633            (EMPTY_ROOT_HASH, None)
634        } else {
635            (storage_hash, Some(Account { nonce, balance, bytecode_hash: code_hash.into() }))
636        };
637
638        Self { address, info, proof: account_proof, storage_root, storage_proofs }
639    }
640}
641
642#[cfg(feature = "eip1186")]
643impl From<alloy_rpc_types_eth::EIP1186AccountProofResponse> for AccountProof {
644    fn from(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
645        Self::from_eip1186_proof(proof)
646    }
647}
648
649impl Default for AccountProof {
650    fn default() -> Self {
651        Self::new(Address::default())
652    }
653}
654
655impl AccountProof {
656    /// Create new account proof entity.
657    pub const fn new(address: Address) -> Self {
658        Self {
659            address,
660            info: None,
661            proof: Vec::new(),
662            storage_root: EMPTY_ROOT_HASH,
663            storage_proofs: Vec::new(),
664        }
665    }
666
667    /// Verify the storage proofs and account proof against the provided state root.
668    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
669        // Verify storage proofs.
670        for storage_proof in &self.storage_proofs {
671            storage_proof.verify(self.storage_root)?;
672        }
673
674        // Verify the account proof.
675        let expected = if self.info.is_none() && self.storage_root == EMPTY_ROOT_HASH {
676            None
677        } else {
678            Some(alloy_rlp::encode(
679                self.info.unwrap_or_default().into_trie_account(self.storage_root),
680            ))
681        };
682        let nibbles = Nibbles::unpack(keccak256(self.address));
683        verify_proof(root, nibbles, expected, &self.proof)
684    }
685}
686
687/// The merkle proof with the relevant account info.
688#[derive(Clone, PartialEq, Eq, Debug)]
689pub struct DecodedAccountProof {
690    /// The address associated with the account.
691    pub address: Address,
692    /// Account info.
693    pub info: Option<Account>,
694    /// Array of merkle trie nodes which starting from the root node and following the path of the
695    /// hashed address as key.
696    pub proof: Vec<TrieNode>,
697    /// The storage trie root.
698    pub storage_root: B256,
699    /// Array of storage proofs as requested.
700    pub storage_proofs: Vec<DecodedStorageProof>,
701}
702
703impl Default for DecodedAccountProof {
704    fn default() -> Self {
705        Self::new(Address::default())
706    }
707}
708
709impl DecodedAccountProof {
710    /// Create new account proof entity.
711    pub const fn new(address: Address) -> Self {
712        Self {
713            address,
714            info: None,
715            proof: Vec::new(),
716            storage_root: EMPTY_ROOT_HASH,
717            storage_proofs: Vec::new(),
718        }
719    }
720}
721
722/// The merkle proof of the storage entry.
723#[derive(Clone, PartialEq, Eq, Default, Debug)]
724#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
725pub struct StorageProof {
726    /// The raw storage key.
727    pub key: B256,
728    /// The hashed storage key nibbles.
729    pub nibbles: Nibbles,
730    /// The storage value.
731    pub value: U256,
732    /// Array of rlp-serialized merkle trie nodes which starting from the storage root node and
733    /// following the path of the hashed storage slot as key.
734    pub proof: Vec<Bytes>,
735}
736
737impl StorageProof {
738    /// Create new storage proof from the storage slot.
739    pub fn new(key: B256) -> Self {
740        let nibbles = Nibbles::unpack(keccak256(key));
741        Self { key, nibbles, ..Default::default() }
742    }
743
744    /// Create new storage proof from the storage slot and its pre-hashed image.
745    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
746        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
747    }
748
749    /// Create new storage proof from the storage slot and its pre-hashed image.
750    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
751        Self { key, nibbles, ..Default::default() }
752    }
753
754    /// Set proof nodes on storage proof.
755    pub fn with_proof(mut self, proof: Vec<Bytes>) -> Self {
756        self.proof = proof;
757        self
758    }
759
760    /// Verify the proof against the provided storage root.
761    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
762        let expected =
763            if self.value.is_zero() { None } else { Some(encode_fixed_size(&self.value).to_vec()) };
764        verify_proof(root, self.nibbles, expected, &self.proof)
765    }
766}
767
768#[cfg(feature = "eip1186")]
769impl StorageProof {
770    /// Convert into an EIP-1186 storage proof
771    pub fn into_eip1186_proof(
772        self,
773        slot: alloy_serde::JsonStorageKey,
774    ) -> alloy_rpc_types_eth::EIP1186StorageProof {
775        alloy_rpc_types_eth::EIP1186StorageProof { key: slot, value: self.value, proof: self.proof }
776    }
777
778    /// Convert from an
779    /// [`EIP1186StorageProof`](alloy_rpc_types_eth::EIP1186StorageProof)
780    ///
781    /// This is the inverse of [`Self::into_eip1186_proof`].
782    pub fn from_eip1186_proof(storage_proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
783        Self {
784            value: storage_proof.value,
785            proof: storage_proof.proof,
786            ..Self::new(storage_proof.key.as_b256())
787        }
788    }
789}
790
791#[cfg(feature = "eip1186")]
792impl From<alloy_rpc_types_eth::EIP1186StorageProof> for StorageProof {
793    fn from(proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
794        Self::from_eip1186_proof(proof)
795    }
796}
797
798/// The merkle proof of the storage entry, using decoded proofs.
799#[derive(Clone, PartialEq, Eq, Default, Debug)]
800pub struct DecodedStorageProof {
801    /// The raw storage key.
802    pub key: B256,
803    /// The hashed storage key nibbles.
804    pub nibbles: Nibbles,
805    /// The storage value.
806    pub value: U256,
807    /// Array of merkle trie nodes which starting from the storage root node and following the path
808    /// of the hashed storage slot as key.
809    pub proof: Vec<TrieNode>,
810}
811
812impl DecodedStorageProof {
813    /// Create new storage proof from the storage slot.
814    pub fn new(key: B256) -> Self {
815        let nibbles = Nibbles::unpack(keccak256(key));
816        Self { key, nibbles, ..Default::default() }
817    }
818
819    /// Create new storage proof from the storage slot and its pre-hashed image.
820    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
821        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
822    }
823
824    /// Create new storage proof from the storage slot and its pre-hashed image.
825    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
826        Self { key, nibbles, ..Default::default() }
827    }
828
829    /// Set proof nodes on storage proof.
830    pub fn with_proof(mut self, proof: Vec<TrieNode>) -> Self {
831        self.proof = proof;
832        self
833    }
834}
835
836/// Implementation of hasher using our keccak256 hashing function
837/// for compatibility with `triehash` crate.
838#[cfg(any(test, feature = "test-utils"))]
839pub mod triehash {
840    use alloy_primitives::{keccak256, B256};
841    use alloy_rlp::RlpEncodable;
842    use hash_db::Hasher;
843    use plain_hasher::PlainHasher;
844
845    /// A [Hasher] that calculates a keccak256 hash of the given data.
846    #[derive(Default, Debug, Clone, PartialEq, Eq, RlpEncodable)]
847    #[non_exhaustive]
848    pub struct KeccakHasher;
849
850    #[cfg(any(test, feature = "test-utils"))]
851    impl Hasher for KeccakHasher {
852        type Out = B256;
853        type StdHasher = PlainHasher;
854
855        const LENGTH: usize = 32;
856
857        fn hash(x: &[u8]) -> Self::Out {
858            keccak256(x)
859        }
860    }
861}
862
863#[cfg(test)]
864mod tests {
865    use super::*;
866
867    #[test]
868    fn test_multiproof_extend_account_proofs() {
869        let mut proof1 = MultiProof::default();
870        let mut proof2 = MultiProof::default();
871
872        let addr1 = B256::random();
873        let addr2 = B256::random();
874
875        proof1.account_subtree.insert(
876            Nibbles::unpack(addr1),
877            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
878        );
879        proof2.account_subtree.insert(
880            Nibbles::unpack(addr2),
881            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
882        );
883
884        proof1.extend(proof2);
885
886        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr1)));
887        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr2)));
888    }
889
890    #[test]
891    fn test_multiproof_extend_storage_proofs() {
892        let mut proof1 = MultiProof::default();
893        let mut proof2 = MultiProof::default();
894
895        let addr = B256::random();
896        let root = B256::random();
897
898        let mut subtree1 = ProofNodes::default();
899        subtree1.insert(
900            Nibbles::from_nibbles(vec![0]),
901            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
902        );
903        proof1.storages.insert(
904            addr,
905            StorageMultiProof {
906                root,
907                subtree: subtree1,
908                branch_node_hash_masks: HashMap::default(),
909                branch_node_tree_masks: HashMap::default(),
910            },
911        );
912
913        let mut subtree2 = ProofNodes::default();
914        subtree2.insert(
915            Nibbles::from_nibbles(vec![1]),
916            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
917        );
918        proof2.storages.insert(
919            addr,
920            StorageMultiProof {
921                root,
922                subtree: subtree2,
923                branch_node_hash_masks: HashMap::default(),
924                branch_node_tree_masks: HashMap::default(),
925            },
926        );
927
928        proof1.extend(proof2);
929
930        let storage = proof1.storages.get(&addr).unwrap();
931        assert_eq!(storage.root, root);
932        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![0])));
933        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![1])));
934    }
935
936    #[test]
937    fn test_multi_proof_retain_difference() {
938        let mut empty = MultiProofTargets::default();
939        empty.retain_difference(&Default::default());
940        assert!(empty.is_empty());
941
942        let targets = MultiProofTargets::accounts((0..10).map(B256::with_last_byte));
943
944        let mut diffed = targets.clone();
945        diffed.retain_difference(&MultiProofTargets::account(B256::with_last_byte(11)));
946        assert_eq!(diffed, targets);
947
948        diffed.retain_difference(&MultiProofTargets::accounts((0..5).map(B256::with_last_byte)));
949        assert_eq!(diffed, MultiProofTargets::accounts((5..10).map(B256::with_last_byte)));
950
951        diffed.retain_difference(&targets);
952        assert!(diffed.is_empty());
953
954        let mut targets = MultiProofTargets::default();
955        let (account1, account2, account3) =
956            (1..=3).map(B256::with_last_byte).collect_tuple().unwrap();
957        let account2_slots = (1..5).map(B256::with_last_byte).collect::<B256Set>();
958        targets.insert(account1, B256Set::from_iter([B256::with_last_byte(1)]));
959        targets.insert(account2, account2_slots.clone());
960        targets.insert(account3, B256Set::from_iter([B256::with_last_byte(1)]));
961
962        let mut diffed = targets.clone();
963        diffed.retain_difference(&MultiProofTargets::accounts((1..=3).map(B256::with_last_byte)));
964        assert_eq!(diffed, targets);
965
966        // remove last 3 slots for account 2
967        let mut account2_slots_expected_len = account2_slots.len();
968        for slot in account2_slots.iter().skip(1) {
969            diffed.retain_difference(&MultiProofTargets::account_with_slots(account2, [*slot]));
970            account2_slots_expected_len -= 1;
971            assert_eq!(
972                diffed.get(&account2).map(|slots| slots.len()),
973                Some(account2_slots_expected_len)
974            );
975        }
976
977        diffed.retain_difference(&targets);
978        assert!(diffed.is_empty());
979    }
980
981    #[test]
982    fn test_multi_proof_retain_difference_no_overlap() {
983        let mut targets = MultiProofTargets::default();
984
985        // populate some targets
986        let (addr1, addr2) = (B256::random(), B256::random());
987        let (slot1, slot2) = (B256::random(), B256::random());
988        targets.insert(addr1, std::iter::once(slot1).collect());
989        targets.insert(addr2, std::iter::once(slot2).collect());
990
991        let mut retained = targets.clone();
992        retained.retain_difference(&Default::default());
993        assert_eq!(retained, targets);
994
995        // add a different addr and slot to fetched proof targets
996        let mut other_targets = MultiProofTargets::default();
997        let addr3 = B256::random();
998        let slot3 = B256::random();
999        other_targets.insert(addr3, B256Set::from_iter([slot3]));
1000
1001        // check that the prefetch proof targets are the same because the fetched proof targets
1002        // don't overlap with the prefetch targets
1003        let mut retained = targets.clone();
1004        retained.retain_difference(&other_targets);
1005        assert_eq!(retained, targets);
1006    }
1007
1008    #[test]
1009    fn test_get_prefetch_proof_targets_remove_subset() {
1010        // populate some targets
1011        let mut targets = MultiProofTargets::default();
1012        let (addr1, addr2) = (B256::random(), B256::random());
1013        let (slot1, slot2) = (B256::random(), B256::random());
1014        targets.insert(addr1, B256Set::from_iter([slot1]));
1015        targets.insert(addr2, B256Set::from_iter([slot2]));
1016
1017        // add a subset of the first target to other proof targets
1018        let other_targets = MultiProofTargets::account_with_slots(addr1, [slot1]);
1019
1020        let mut retained = targets.clone();
1021        retained.retain_difference(&other_targets);
1022
1023        // check that the prefetch proof targets do not include the subset
1024        assert_eq!(retained.len(), 1);
1025        assert!(!retained.contains_key(&addr1));
1026        assert!(retained.contains_key(&addr2));
1027
1028        // now add one more slot to the prefetch targets
1029        let slot3 = B256::random();
1030        targets.get_mut(&addr1).unwrap().insert(slot3);
1031
1032        let mut retained = targets.clone();
1033        retained.retain_difference(&other_targets);
1034
1035        // check that the prefetch proof targets do not include the subset
1036        // but include the new slot
1037        assert_eq!(retained.len(), 2);
1038        assert!(retained.contains_key(&addr1));
1039        assert_eq!(retained.get(&addr1), Some(&B256Set::from_iter([slot3])));
1040        assert!(retained.contains_key(&addr2));
1041        assert_eq!(retained.get(&addr2), Some(&B256Set::from_iter([slot2])));
1042    }
1043
1044    #[test]
1045    #[cfg(feature = "eip1186")]
1046    fn eip_1186_roundtrip() {
1047        let mut acc = AccountProof {
1048            address: Address::random(),
1049            info: Some(
1050                // non-empty account
1051                Account { nonce: 100, balance: U256::ZERO, bytecode_hash: Some(KECCAK_EMPTY) },
1052            ),
1053            proof: vec![],
1054            storage_root: B256::ZERO,
1055            storage_proofs: vec![],
1056        };
1057
1058        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1059        let inverse: AccountProof = rpc_proof.into();
1060        assert_eq!(acc, inverse);
1061
1062        // make account empty
1063        acc.info.as_mut().unwrap().nonce = 0;
1064        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1065        let inverse: AccountProof = rpc_proof.into();
1066        acc.info.take();
1067        acc.storage_root = EMPTY_ROOT_HASH;
1068        assert_eq!(acc, inverse);
1069    }
1070}
reth_trie_common/proofs.rs

reth_trie_common/
proofs.rs
