reth_trie_common/
proofs.rs

1//! Merkle trie proofs.
2
3use crate::{BranchNodeMasksMap, Nibbles, ProofTrieNode, 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<ProofTrieNode>,
452    /// Storage trie proof nodes indexed by account
453    pub storage_proofs: B256Map<Vec<ProofTrieNode>>,
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            self.storage_proofs.entry(hashed_address).or_default().extend(other_storage_proofs);
469        }
470    }
471}
472
473/// The merkle multiproof of storage trie.
474#[derive(Clone, Debug, PartialEq, Eq)]
475pub struct StorageMultiProof {
476    /// Storage trie root.
477    pub root: B256,
478    /// Storage multiproof for requested slots.
479    pub subtree: ProofNodes,
480    /// Consolidated branch node masks (`hash_mask`, `tree_mask`) for each path in the storage
481    /// proof.
482    pub branch_node_masks: BranchNodeMasksMap,
483}
484
485impl StorageMultiProof {
486    /// Create new storage multiproof for empty trie.
487    pub fn empty() -> Self {
488        Self {
489            root: EMPTY_ROOT_HASH,
490            subtree: ProofNodes::from_iter([(
491                Nibbles::default(),
492                Bytes::from([EMPTY_STRING_CODE]),
493            )]),
494            branch_node_masks: BranchNodeMasksMap::default(),
495        }
496    }
497
498    /// Return storage proofs for the target storage slot (unhashed).
499    pub fn storage_proof(&self, slot: B256) -> Result<StorageProof, alloy_rlp::Error> {
500        let nibbles = Nibbles::unpack(keccak256(slot));
501
502        // Retrieve the storage proof.
503        let proof = self
504            .subtree
505            .matching_nodes_iter(&nibbles)
506            .sorted_by(|a, b| a.0.cmp(b.0))
507            .map(|(_, node)| node.clone())
508            .collect::<Vec<_>>();
509
510        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
511        // then the node contains the encoded slot value.
512        let value = 'value: {
513            if let Some(last) = proof.last() &&
514                let TrieNode::Leaf(leaf) = TrieNode::decode(&mut &last[..])? &&
515                nibbles.ends_with(&leaf.key)
516            {
517                break 'value U256::decode(&mut &leaf.value[..])?
518            }
519            U256::ZERO
520        };
521
522        Ok(StorageProof { key: slot, nibbles, value, proof })
523    }
524}
525
526/// The decoded merkle multiproof for a storage trie.
527#[derive(Clone, Debug, PartialEq, Eq)]
528pub struct DecodedStorageMultiProof {
529    /// Storage trie root.
530    pub root: B256,
531    /// Storage multiproof for requested slots.
532    pub subtree: DecodedProofNodes,
533    /// Consolidated branch node masks (`hash_mask`, `tree_mask`) for each path in the storage
534    /// proof.
535    pub branch_node_masks: BranchNodeMasksMap,
536}
537
538impl DecodedStorageMultiProof {
539    /// Create new storage multiproof for empty trie.
540    pub fn empty() -> Self {
541        Self {
542            root: EMPTY_ROOT_HASH,
543            subtree: DecodedProofNodes::from_iter([(Nibbles::default(), TrieNode::EmptyRoot)]),
544            branch_node_masks: BranchNodeMasksMap::default(),
545        }
546    }
547
548    /// Return storage proofs for the target storage slot (unhashed).
549    pub fn storage_proof(&self, slot: B256) -> Result<DecodedStorageProof, alloy_rlp::Error> {
550        let nibbles = Nibbles::unpack(keccak256(slot));
551
552        // Retrieve the storage proof.
553        let proof = self
554            .subtree
555            .matching_nodes_iter(&nibbles)
556            .sorted_by(|a, b| a.0.cmp(b.0))
557            .map(|(_, node)| node.clone())
558            .collect::<Vec<_>>();
559
560        // Inspect the last node in the proof. If it's a leaf node with matching suffix,
561        // then the node contains the encoded slot value.
562        let value = 'value: {
563            if let Some(TrieNode::Leaf(leaf)) = proof.last() &&
564                nibbles.ends_with(&leaf.key)
565            {
566                break 'value U256::decode(&mut &leaf.value[..])?
567            }
568            U256::ZERO
569        };
570
571        Ok(DecodedStorageProof { key: slot, nibbles, value, proof })
572    }
573}
574
575impl TryFrom<StorageMultiProof> for DecodedStorageMultiProof {
576    type Error = alloy_rlp::Error;
577
578    fn try_from(multi_proof: StorageMultiProof) -> Result<Self, Self::Error> {
579        let subtree = DecodedProofNodes::try_from(multi_proof.subtree)?;
580        Ok(Self {
581            root: multi_proof.root,
582            subtree,
583            branch_node_masks: multi_proof.branch_node_masks,
584        })
585    }
586}
587
588/// The merkle proof with the relevant account info.
589#[derive(Clone, PartialEq, Eq, Debug)]
590#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
591#[cfg_attr(any(test, feature = "serde"), serde(rename_all = "camelCase"))]
592pub struct AccountProof {
593    /// The address associated with the account.
594    pub address: Address,
595    /// Account info, if any.
596    pub info: Option<Account>,
597    /// Array of rlp-serialized merkle trie nodes which starting from the root node and
598    /// following the path of the hashed address as key.
599    pub proof: Vec<Bytes>,
600    /// The storage trie root.
601    pub storage_root: B256,
602    /// Array of storage proofs as requested.
603    pub storage_proofs: Vec<StorageProof>,
604}
605
606#[cfg(feature = "eip1186")]
607impl AccountProof {
608    /// Convert into an EIP-1186 account proof response
609    pub fn into_eip1186_response(
610        self,
611        slots: Vec<alloy_serde::JsonStorageKey>,
612    ) -> alloy_rpc_types_eth::EIP1186AccountProofResponse {
613        let info = self.info.unwrap_or_default();
614        alloy_rpc_types_eth::EIP1186AccountProofResponse {
615            address: self.address,
616            balance: info.balance,
617            code_hash: info.get_bytecode_hash(),
618            nonce: info.nonce,
619            storage_hash: self.storage_root,
620            account_proof: self.proof,
621            storage_proof: self
622                .storage_proofs
623                .into_iter()
624                .filter_map(|proof| {
625                    let input_slot = slots.iter().find(|s| s.as_b256() == proof.key)?;
626                    Some(proof.into_eip1186_proof(*input_slot))
627                })
628                .collect(),
629        }
630    }
631
632    /// Converts an
633    /// [`EIP1186AccountProofResponse`](alloy_rpc_types_eth::EIP1186AccountProofResponse) to an
634    /// [`AccountProof`].
635    ///
636    /// This is the inverse of [`Self::into_eip1186_response`]
637    pub fn from_eip1186_proof(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
638        let alloy_rpc_types_eth::EIP1186AccountProofResponse {
639            nonce,
640            address,
641            balance,
642            code_hash,
643            storage_hash,
644            account_proof,
645            storage_proof,
646            ..
647        } = proof;
648        let storage_proofs = storage_proof.into_iter().map(Into::into).collect();
649
650        let (storage_root, info) = if nonce == 0 &&
651            balance.is_zero() &&
652            storage_hash.is_zero() &&
653            code_hash == KECCAK_EMPTY
654        {
655            // Account does not exist in state. Return `None` here to prevent proof
656            // verification.
657            (EMPTY_ROOT_HASH, None)
658        } else {
659            (storage_hash, Some(Account { nonce, balance, bytecode_hash: code_hash.into() }))
660        };
661
662        Self { address, info, proof: account_proof, storage_root, storage_proofs }
663    }
664}
665
666#[cfg(feature = "eip1186")]
667impl From<alloy_rpc_types_eth::EIP1186AccountProofResponse> for AccountProof {
668    fn from(proof: alloy_rpc_types_eth::EIP1186AccountProofResponse) -> Self {
669        Self::from_eip1186_proof(proof)
670    }
671}
672
673impl Default for AccountProof {
674    fn default() -> Self {
675        Self::new(Address::default())
676    }
677}
678
679impl AccountProof {
680    /// Create new account proof entity.
681    pub const fn new(address: Address) -> Self {
682        Self {
683            address,
684            info: None,
685            proof: Vec::new(),
686            storage_root: EMPTY_ROOT_HASH,
687            storage_proofs: Vec::new(),
688        }
689    }
690
691    /// Verify the storage proofs and account proof against the provided state root.
692    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
693        // Verify storage proofs.
694        for storage_proof in &self.storage_proofs {
695            storage_proof.verify(self.storage_root)?;
696        }
697
698        // Verify the account proof.
699        let expected = if self.info.is_none() && self.storage_root == EMPTY_ROOT_HASH {
700            None
701        } else {
702            Some(alloy_rlp::encode(
703                self.info.unwrap_or_default().into_trie_account(self.storage_root),
704            ))
705        };
706        let nibbles = Nibbles::unpack(keccak256(self.address));
707        verify_proof(root, nibbles, expected, &self.proof)
708    }
709}
710
711/// The merkle proof with the relevant account info.
712#[derive(Clone, PartialEq, Eq, Debug)]
713pub struct DecodedAccountProof {
714    /// The address associated with the account.
715    pub address: Address,
716    /// Account info.
717    pub info: Option<Account>,
718    /// Array of merkle trie nodes which starting from the root node and following the path of the
719    /// hashed address as key.
720    pub proof: Vec<TrieNode>,
721    /// The storage trie root.
722    pub storage_root: B256,
723    /// Array of storage proofs as requested.
724    pub storage_proofs: Vec<DecodedStorageProof>,
725}
726
727impl Default for DecodedAccountProof {
728    fn default() -> Self {
729        Self::new(Address::default())
730    }
731}
732
733impl DecodedAccountProof {
734    /// Create new account proof entity.
735    pub const fn new(address: Address) -> Self {
736        Self {
737            address,
738            info: None,
739            proof: Vec::new(),
740            storage_root: EMPTY_ROOT_HASH,
741            storage_proofs: Vec::new(),
742        }
743    }
744}
745
746/// The merkle proof of the storage entry.
747#[derive(Clone, PartialEq, Eq, Default, Debug)]
748#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
749pub struct StorageProof {
750    /// The raw storage key.
751    pub key: B256,
752    /// The hashed storage key nibbles.
753    pub nibbles: Nibbles,
754    /// The storage value.
755    pub value: U256,
756    /// Array of rlp-serialized merkle trie nodes which starting from the storage root node and
757    /// following the path of the hashed storage slot as key.
758    pub proof: Vec<Bytes>,
759}
760
761impl StorageProof {
762    /// Create new storage proof from the storage slot.
763    pub fn new(key: B256) -> Self {
764        let nibbles = Nibbles::unpack(keccak256(key));
765        Self { key, nibbles, ..Default::default() }
766    }
767
768    /// Create new storage proof from the storage slot and its pre-hashed image.
769    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
770        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
771    }
772
773    /// Create new storage proof from the storage slot and its pre-hashed image.
774    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
775        Self { key, nibbles, ..Default::default() }
776    }
777
778    /// Set proof nodes on storage proof.
779    pub fn with_proof(mut self, proof: Vec<Bytes>) -> Self {
780        self.proof = proof;
781        self
782    }
783
784    /// Verify the proof against the provided storage root.
785    pub fn verify(&self, root: B256) -> Result<(), ProofVerificationError> {
786        let expected =
787            if self.value.is_zero() { None } else { Some(encode_fixed_size(&self.value).to_vec()) };
788        verify_proof(root, self.nibbles, expected, &self.proof)
789    }
790}
791
792#[cfg(feature = "eip1186")]
793impl StorageProof {
794    /// Convert into an EIP-1186 storage proof
795    pub fn into_eip1186_proof(
796        self,
797        slot: alloy_serde::JsonStorageKey,
798    ) -> alloy_rpc_types_eth::EIP1186StorageProof {
799        alloy_rpc_types_eth::EIP1186StorageProof { key: slot, value: self.value, proof: self.proof }
800    }
801
802    /// Convert from an
803    /// [`EIP1186StorageProof`](alloy_rpc_types_eth::EIP1186StorageProof)
804    ///
805    /// This is the inverse of [`Self::into_eip1186_proof`].
806    pub fn from_eip1186_proof(storage_proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
807        Self {
808            value: storage_proof.value,
809            proof: storage_proof.proof,
810            ..Self::new(storage_proof.key.as_b256())
811        }
812    }
813}
814
815#[cfg(feature = "eip1186")]
816impl From<alloy_rpc_types_eth::EIP1186StorageProof> for StorageProof {
817    fn from(proof: alloy_rpc_types_eth::EIP1186StorageProof) -> Self {
818        Self::from_eip1186_proof(proof)
819    }
820}
821
822/// The merkle proof of the storage entry, using decoded proofs.
823#[derive(Clone, PartialEq, Eq, Default, Debug)]
824pub struct DecodedStorageProof {
825    /// The raw storage key.
826    pub key: B256,
827    /// The hashed storage key nibbles.
828    pub nibbles: Nibbles,
829    /// The storage value.
830    pub value: U256,
831    /// Array of merkle trie nodes which starting from the storage root node and following the path
832    /// of the hashed storage slot as key.
833    pub proof: Vec<TrieNode>,
834}
835
836impl DecodedStorageProof {
837    /// Create new storage proof from the storage slot.
838    pub fn new(key: B256) -> Self {
839        let nibbles = Nibbles::unpack(keccak256(key));
840        Self { key, nibbles, ..Default::default() }
841    }
842
843    /// Create new storage proof from the storage slot and its pre-hashed image.
844    pub fn new_with_hashed(key: B256, hashed_key: B256) -> Self {
845        Self { key, nibbles: Nibbles::unpack(hashed_key), ..Default::default() }
846    }
847
848    /// Create new storage proof from the storage slot and its pre-hashed image.
849    pub fn new_with_nibbles(key: B256, nibbles: Nibbles) -> Self {
850        Self { key, nibbles, ..Default::default() }
851    }
852
853    /// Set proof nodes on storage proof.
854    pub fn with_proof(mut self, proof: Vec<TrieNode>) -> Self {
855        self.proof = proof;
856        self
857    }
858}
859
860/// Implementation of hasher using our keccak256 hashing function
861/// for compatibility with `triehash` crate.
862#[cfg(any(test, feature = "test-utils"))]
863pub mod triehash {
864    use alloy_primitives::{keccak256, B256};
865    use alloy_rlp::RlpEncodable;
866    use hash_db::Hasher;
867    use plain_hasher::PlainHasher;
868
869    /// A [Hasher] that calculates a keccak256 hash of the given data.
870    #[derive(Default, Debug, Clone, PartialEq, Eq, RlpEncodable)]
871    #[non_exhaustive]
872    pub struct KeccakHasher;
873
874    #[cfg(any(test, feature = "test-utils"))]
875    impl Hasher for KeccakHasher {
876        type Out = B256;
877        type StdHasher = PlainHasher;
878
879        const LENGTH: usize = 32;
880
881        fn hash(x: &[u8]) -> Self::Out {
882            keccak256(x)
883        }
884    }
885}
886
887#[cfg(test)]
888mod tests {
889    use super::*;
890
891    #[test]
892    fn test_multiproof_extend_account_proofs() {
893        let mut proof1 = MultiProof::default();
894        let mut proof2 = MultiProof::default();
895
896        let addr1 = B256::random();
897        let addr2 = B256::random();
898
899        proof1.account_subtree.insert(
900            Nibbles::unpack(addr1),
901            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
902        );
903        proof2.account_subtree.insert(
904            Nibbles::unpack(addr2),
905            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
906        );
907
908        proof1.extend(proof2);
909
910        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr1)));
911        assert!(proof1.account_subtree.contains_key(&Nibbles::unpack(addr2)));
912    }
913
914    #[test]
915    fn test_multiproof_extend_storage_proofs() {
916        let mut proof1 = MultiProof::default();
917        let mut proof2 = MultiProof::default();
918
919        let addr = B256::random();
920        let root = B256::random();
921
922        let mut subtree1 = ProofNodes::default();
923        subtree1.insert(
924            Nibbles::from_nibbles(vec![0]),
925            alloy_rlp::encode_fixed_size(&U256::from(42)).to_vec().into(),
926        );
927        proof1.storages.insert(
928            addr,
929            StorageMultiProof {
930                root,
931                subtree: subtree1,
932                branch_node_masks: BranchNodeMasksMap::default(),
933            },
934        );
935
936        let mut subtree2 = ProofNodes::default();
937        subtree2.insert(
938            Nibbles::from_nibbles(vec![1]),
939            alloy_rlp::encode_fixed_size(&U256::from(43)).to_vec().into(),
940        );
941        proof2.storages.insert(
942            addr,
943            StorageMultiProof {
944                root,
945                subtree: subtree2,
946                branch_node_masks: BranchNodeMasksMap::default(),
947            },
948        );
949
950        proof1.extend(proof2);
951
952        let storage = proof1.storages.get(&addr).unwrap();
953        assert_eq!(storage.root, root);
954        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![0])));
955        assert!(storage.subtree.contains_key(&Nibbles::from_nibbles(vec![1])));
956    }
957
958    #[test]
959    fn test_multi_proof_retain_difference() {
960        let mut empty = MultiProofTargets::default();
961        empty.retain_difference(&Default::default());
962        assert!(empty.is_empty());
963
964        let targets = MultiProofTargets::accounts((0..10).map(B256::with_last_byte));
965
966        let mut diffed = targets.clone();
967        diffed.retain_difference(&MultiProofTargets::account(B256::with_last_byte(11)));
968        assert_eq!(diffed, targets);
969
970        diffed.retain_difference(&MultiProofTargets::accounts((0..5).map(B256::with_last_byte)));
971        assert_eq!(diffed, MultiProofTargets::accounts((5..10).map(B256::with_last_byte)));
972
973        diffed.retain_difference(&targets);
974        assert!(diffed.is_empty());
975
976        let mut targets = MultiProofTargets::default();
977        let (account1, account2, account3) =
978            (1..=3).map(B256::with_last_byte).collect_tuple().unwrap();
979        let account2_slots = (1..5).map(B256::with_last_byte).collect::<B256Set>();
980        targets.insert(account1, B256Set::from_iter([B256::with_last_byte(1)]));
981        targets.insert(account2, account2_slots.clone());
982        targets.insert(account3, B256Set::from_iter([B256::with_last_byte(1)]));
983
984        let mut diffed = targets.clone();
985        diffed.retain_difference(&MultiProofTargets::accounts((1..=3).map(B256::with_last_byte)));
986        assert_eq!(diffed, targets);
987
988        // remove last 3 slots for account 2
989        let mut account2_slots_expected_len = account2_slots.len();
990        for slot in account2_slots.iter().skip(1) {
991            diffed.retain_difference(&MultiProofTargets::account_with_slots(account2, [*slot]));
992            account2_slots_expected_len -= 1;
993            assert_eq!(
994                diffed.get(&account2).map(|slots| slots.len()),
995                Some(account2_slots_expected_len)
996            );
997        }
998
999        diffed.retain_difference(&targets);
1000        assert!(diffed.is_empty());
1001    }
1002
1003    #[test]
1004    fn test_multi_proof_retain_difference_no_overlap() {
1005        let mut targets = MultiProofTargets::default();
1006
1007        // populate some targets
1008        let (addr1, addr2) = (B256::random(), B256::random());
1009        let (slot1, slot2) = (B256::random(), B256::random());
1010        targets.insert(addr1, std::iter::once(slot1).collect());
1011        targets.insert(addr2, std::iter::once(slot2).collect());
1012
1013        let mut retained = targets.clone();
1014        retained.retain_difference(&Default::default());
1015        assert_eq!(retained, targets);
1016
1017        // add a different addr and slot to fetched proof targets
1018        let mut other_targets = MultiProofTargets::default();
1019        let addr3 = B256::random();
1020        let slot3 = B256::random();
1021        other_targets.insert(addr3, B256Set::from_iter([slot3]));
1022
1023        // check that the prefetch proof targets are the same because the fetched proof targets
1024        // don't overlap with the prefetch targets
1025        let mut retained = targets.clone();
1026        retained.retain_difference(&other_targets);
1027        assert_eq!(retained, targets);
1028    }
1029
1030    #[test]
1031    fn test_get_prefetch_proof_targets_remove_subset() {
1032        // populate some targets
1033        let mut targets = MultiProofTargets::default();
1034        let (addr1, addr2) = (B256::random(), B256::random());
1035        let (slot1, slot2) = (B256::random(), B256::random());
1036        targets.insert(addr1, B256Set::from_iter([slot1]));
1037        targets.insert(addr2, B256Set::from_iter([slot2]));
1038
1039        // add a subset of the first target to other proof targets
1040        let other_targets = MultiProofTargets::account_with_slots(addr1, [slot1]);
1041
1042        let mut retained = targets.clone();
1043        retained.retain_difference(&other_targets);
1044
1045        // check that the prefetch proof targets do not include the subset
1046        assert_eq!(retained.len(), 1);
1047        assert!(!retained.contains_key(&addr1));
1048        assert!(retained.contains_key(&addr2));
1049
1050        // now add one more slot to the prefetch targets
1051        let slot3 = B256::random();
1052        targets.get_mut(&addr1).unwrap().insert(slot3);
1053
1054        let mut retained = targets.clone();
1055        retained.retain_difference(&other_targets);
1056
1057        // check that the prefetch proof targets do not include the subset
1058        // but include the new slot
1059        assert_eq!(retained.len(), 2);
1060        assert!(retained.contains_key(&addr1));
1061        assert_eq!(retained.get(&addr1), Some(&B256Set::from_iter([slot3])));
1062        assert!(retained.contains_key(&addr2));
1063        assert_eq!(retained.get(&addr2), Some(&B256Set::from_iter([slot2])));
1064    }
1065
1066    #[test]
1067    #[cfg(feature = "eip1186")]
1068    fn eip_1186_roundtrip() {
1069        let mut acc = AccountProof {
1070            address: Address::random(),
1071            info: Some(
1072                // non-empty account
1073                Account { nonce: 100, balance: U256::ZERO, bytecode_hash: Some(KECCAK_EMPTY) },
1074            ),
1075            proof: vec![],
1076            storage_root: B256::ZERO,
1077            storage_proofs: vec![],
1078        };
1079
1080        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1081        let inverse: AccountProof = rpc_proof.into();
1082        assert_eq!(acc, inverse);
1083
1084        // make account empty
1085        acc.info.as_mut().unwrap().nonce = 0;
1086        let rpc_proof = acc.clone().into_eip1186_response(Vec::new());
1087        let inverse: AccountProof = rpc_proof.into();
1088        acc.info.take();
1089        acc.storage_root = EMPTY_ROOT_HASH;
1090        assert_eq!(acc, inverse);
1091    }
1092
1093    #[test]
1094    fn test_multiproof_targets_chunking_length() {
1095        let mut targets = MultiProofTargets::default();
1096        targets.insert(B256::with_last_byte(1), B256Set::default());
1097        targets.insert(
1098            B256::with_last_byte(2),
1099            B256Set::from_iter([B256::with_last_byte(10), B256::with_last_byte(20)]),
1100        );
1101        targets.insert(
1102            B256::with_last_byte(3),
1103            B256Set::from_iter([
1104                B256::with_last_byte(30),
1105                B256::with_last_byte(31),
1106                B256::with_last_byte(32),
1107            ]),
1108        );
1109
1110        let chunking_length = targets.chunking_length();
1111        for size in 1..=targets.clone().chunks(1).count() {
1112            let chunk_count = targets.clone().chunks(size).count();
1113            let expected_count = chunking_length.div_ceil(size);
1114            assert_eq!(
1115                chunk_count, expected_count,
1116                "chunking_length: {}, size: {}",
1117                chunking_length, size
1118            );
1119        }
1120    }
1121}
reth_trie_common/proofs.rs

reth_trie_common/
proofs.rs
