reth_trie/verify/
compare.rs

1//! Depth-first comparison of persisted trie nodes against recomputed nodes.
2
3use super::Output;
4use crate::{
5    trie_cursor::{
6        depth_first::{self, DepthFirstTrieIterator},
7        TrieCursor,
8    },
9    Nibbles,
10};
11use alloy_primitives::B256;
12use alloy_trie::BranchNodeCompact;
13use reth_storage_errors::db::DatabaseError;
14use std::cmp::Ordering;
15use tracing::trace;
16
17/// Verifies the contents of a trie table against some other data source which is able to produce
18/// stored trie nodes.
19#[derive(Debug)]
20pub(super) struct SingleVerifier<I> {
21    account: Option<B256>, // None for accounts trie
22    trie_iter: I,
23    curr: Option<(Nibbles, BranchNodeCompact)>,
24}
25
26impl<C: TrieCursor> SingleVerifier<DepthFirstTrieIterator<C>> {
27    pub(super) fn new(account: Option<B256>, trie_cursor: C) -> Result<Self, DatabaseError> {
28        let mut trie_iter = DepthFirstTrieIterator::new(trie_cursor);
29        let curr = trie_iter.next().transpose()?;
30        Ok(Self { account, trie_iter, curr })
31    }
32}
33
34impl<I> SingleVerifier<I>
35where
36    I: Iterator<Item = Result<(Nibbles, BranchNodeCompact), DatabaseError>>,
37{
38    const fn output_extra(&self, path: Nibbles, node: BranchNodeCompact) -> Output {
39        if let Some(account) = self.account {
40            Output::StorageExtra(account, path, node)
41        } else {
42            Output::AccountExtra(path, node)
43        }
44    }
45
46    const fn output_wrong(
47        &self,
48        path: Nibbles,
49        expected: BranchNodeCompact,
50        found: BranchNodeCompact,
51    ) -> Output {
52        if let Some(account) = self.account {
53            Output::StorageWrong { account, path, expected, found }
54        } else {
55            Output::AccountWrong { path, expected, found }
56        }
57    }
58
59    const fn output_missing(&self, path: Nibbles, node: BranchNodeCompact) -> Output {
60        if let Some(account) = self.account {
61            Output::StorageMissing(account, path, node)
62        } else {
63            Output::AccountMissing(path, node)
64        }
65    }
66
67    /// Called with the next path and node in the canonical sequence of stored trie nodes. Will
68    /// emit findings immediately if walking the trie cursor produces inconsistent data.
69    /// Returning `false` from the callback cancels comparison before advancing the cursor again.
70    ///
71    /// `next` must be called with paths in depth-first order. Returns `true` on completion and
72    /// `false` on cancellation. The verifier must not be reused after cancellation.
73    pub(super) fn next(
74        &mut self,
75        emit: &mut impl FnMut(Output) -> bool,
76        path: Nibbles,
77        node: BranchNodeCompact,
78    ) -> Result<bool, DatabaseError> {
79        loop {
80            // `curr` is None only if the end of the iterator has been reached. Any further nodes
81            // found must be considered missing.
82            if self.curr.is_none() {
83                return Ok(emit(self.output_missing(path, node)))
84            }
85
86            let (curr_path, curr_node) = self.curr.as_ref().expect("not None");
87            trace!(target: "trie::verify", account=?self.account, ?curr_path, ?path, "Current cursor node");
88
89            // Use depth-first ordering for comparison
90            match depth_first::cmp(&path, curr_path) {
91                Ordering::Less => {
92                    // If the given path comes before the cursor's current path in depth-first
93                    // order, then the given path was not produced by the cursor.
94                    return Ok(emit(self.output_missing(path, node)))
95                }
96                Ordering::Equal => {
97                    // If the current path matches the given one (happy path) but the nodes
98                    // aren't equal then we produce a wrong node. Either way we want to move the
99                    // iterator forward.
100                    if *curr_node != node && !emit(self.output_wrong(path, node, curr_node.clone()))
101                    {
102                        return Ok(false)
103                    }
104                    self.curr = self.trie_iter.next().transpose()?;
105                    return Ok(true);
106                }
107                Ordering::Greater => {
108                    // If the given path comes after the current path in depth-first order,
109                    // it means the cursor's path was not found by the caller (otherwise it would
110                    // have hit the equal case) and so is extraneous.
111                    if !emit(self.output_extra(*curr_path, curr_node.clone())) {
112                        return Ok(false);
113                    }
114                    self.curr = self.trie_iter.next().transpose()?;
115                    // back to the top of the loop to check the latest `self.curr` value against the
116                    // given path/node.
117                }
118            }
119        }
120    }
121
122    /// Must be called once there are no more calls to `next` to be made. All further nodes produced
123    /// by the iterator will be considered extraneous and emitted individually. Returning `false`
124    /// from the callback stops comparison immediately; the verifier must not be reused after
125    /// cancellation. Returns `true` on completion and `false` on cancellation.
126    pub(super) fn finalize(
127        &mut self,
128        emit: &mut impl FnMut(Output) -> bool,
129    ) -> Result<bool, DatabaseError> {
130        loop {
131            if let Some((curr_path, curr_node)) = self.curr.take() {
132                if !emit(self.output_extra(curr_path, curr_node)) {
133                    return Ok(false);
134                }
135                self.curr = self.trie_iter.next().transpose()?;
136            } else {
137                return Ok(true);
138            }
139        }
140    }
141}
reth_trie/verify/compare.rs

reth_trie/verify/
compare.rs
