reth_trie_db/
verify.rs

1//! Database-backed trie verification.
2
3use crate::{
4    DatabaseAccountTrieCursor, DatabaseHashedAccountCursor, DatabaseHashedCursorFactory,
5    DatabaseTrieCursorFactory, TrieTableAdapter,
6};
7use alloy_primitives::B256;
8use reth_db_api::{
9    cursor::{DbCursorRO, DbDupCursorRO},
10    database::Database,
11    tables,
12    transaction::{CursorTy, DbTx, DupCursorTy},
13    DatabaseError,
14};
15use reth_execution_errors::StateRootError;
16use reth_trie::{
17    hashed_cursor::HashedCursorFactory,
18    trie_cursor::TrieCursorFactory,
19    verify::{Output, StorageJob, StorageWorker, Verifier},
20};
21use std::fmt;
22
23/// [`Verifier`] reading database tables through cursors of a `TX` transaction.
24type TxVerifier<TX, A> = Verifier<
25    DatabaseAccountTrieCursor<CursorTy<TX, <A as TrieTableAdapter>::AccountTrieTable>, A>,
26    DatabaseHashedAccountCursor<CursorTy<TX, tables::HashedAccounts>>,
27>;
28
29/// Checks the trie tables against the hashed state tables of a database, yielding an [`Output`]
30/// for every inconsistency found. See [`Verifier`] for details.
31pub struct DatabaseVerifier<TX: DbTx, A: TrieTableAdapter> {
32    verifier: TxVerifier<TX, A>,
33    // Backs the cursors held by `verifier`, so it's declared, and dropped, after it.
34    _txs: [TX; 2],
35}
36
37impl<TX, A> DatabaseVerifier<TX, A>
38where
39    TX: DbTx + 'static,
40    A: TrieTableAdapter,
41{
42    /// Starts verification over read transactions opened through `db`.
43    ///
44    /// Prevent commits while this constructor opens the transactions so they read the same database
45    /// version. Each storage worker owns a separate transaction. For long-running verification,
46    /// configure `db` to disable long-lived read transaction safety. `storage_lookahead` bounds
47    /// storage jobs whose requested roots have not yet been consumed, including storage without a
48    /// hashed account row.
49    ///
50    /// # Panics
51    ///
52    /// Panics if `storage_workers` or `storage_lookahead` is zero.
53    pub fn new(
54        db: &impl Database<TX = TX>,
55        storage_workers: usize,
56        storage_lookahead: usize,
57    ) -> Result<Self, DatabaseError> {
58        assert!(storage_workers > 0, "at least one storage worker is required");
59        let account_tx = db.tx()?;
60        let lookahead_tx = db.tx()?;
61        let storage_workers = (0..storage_workers)
62            .map(|_| {
63                let tx = db.tx()?;
64                Ok(StorageWorker {
65                    trie: DatabaseTrieCursorFactory::<_, A>::new(&tx)
66                        .storage_trie_cursor(B256::ZERO)?,
67                    hashed: DatabaseHashedCursorFactory::new(&tx)
68                        .hashed_storage_cursor(B256::ZERO)?,
69                    tx,
70                })
71            })
72            .collect::<Result<Vec<_>, DatabaseError>>()?;
73        let verifier = Verifier::new(
74            DatabaseTrieCursorFactory::<_, A>::new(&account_tx).account_trie_cursor()?,
75            DatabaseHashedCursorFactory::new(&account_tx).hashed_account_cursor()?,
76            StorageAddresses::<TX, A> {
77                hashed: lookahead_tx.cursor_dup_read::<tables::HashedStorages>()?,
78                trie: lookahead_tx.cursor_dup_read::<A::StorageTrieTable>()?,
79                next_hashed: None,
80                next_trie: None,
81                initialized: false,
82            },
83            storage_workers,
84            storage_lookahead,
85        )?;
86        Ok(Self { verifier, _txs: [account_tx, lookahead_tx] })
87    }
88}
89
90impl<TX: DbTx, A: TrieTableAdapter> Iterator for DatabaseVerifier<TX, A> {
91    type Item = Result<Output, StateRootError>;
92
93    fn next(&mut self) -> Option<Self::Item> {
94        self.verifier.next()
95    }
96}
97
98impl<TX: DbTx, A: TrieTableAdapter> fmt::Debug for DatabaseVerifier<TX, A> {
99    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
100        f.debug_struct("DatabaseVerifier").finish_non_exhaustive()
101    }
102}
103
104/// Merges the distinct addresses in hashed storage and stored storage tries, including orphan
105/// tries.
106struct StorageAddresses<TX: DbTx, A: TrieTableAdapter> {
107    hashed: DupCursorTy<TX, tables::HashedStorages>,
108    trie: DupCursorTy<TX, A::StorageTrieTable>,
109    next_hashed: Option<B256>,
110    next_trie: Option<B256>,
111    initialized: bool,
112}
113
114impl<TX: DbTx, A: TrieTableAdapter> StorageAddresses<TX, A> {
115    fn next_address(&mut self) -> Result<Option<StorageJob>, DatabaseError> {
116        if !self.initialized {
117            self.next_hashed = self.hashed.first()?.map(|(address, _)| address);
118            self.next_trie = self.trie.first()?.map(|(address, _)| address);
119            self.initialized = true;
120        }
121        let address = match (self.next_hashed, self.next_trie) {
122            (Some(hashed), Some(trie)) => hashed.min(trie),
123            (Some(address), None) | (None, Some(address)) => address,
124            (None, None) => return Ok(None),
125        };
126        // Request roots for hashed storage; the account worker discards orphan roots.
127        let has_storage = self.next_hashed == Some(address);
128        if has_storage {
129            self.next_hashed = self.hashed.next_no_dup()?.map(|(address, _)| address);
130        }
131        if self.next_trie == Some(address) {
132            self.next_trie = self.trie.next_no_dup()?.map(|(address, _)| address);
133        }
134        Ok(Some(StorageJob { address, root_required: has_storage }))
135    }
136}
137
138impl<TX: DbTx, A: TrieTableAdapter> Iterator for StorageAddresses<TX, A> {
139    type Item = Result<StorageJob, DatabaseError>;
140
141    fn next(&mut self) -> Option<Self::Item> {
142        self.next_address().transpose()
143    }
144}
reth_trie_db/verify.rs

reth_trie_db/
verify.rs
