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

reth_trie_common/
proofs.rs
