reth_trie_common/
proofs.rs

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

reth_trie_common/
proofs.rs
