reth_trie_common/
proofs.rs

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

reth_trie_common/
proofs.rs
