reth_trie_common/
proofs.rs

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

reth_trie_common/
proofs.rs
