reth_engine_tree/tree/
trie_updates.rs

1use alloy_primitives::{map::HashMap, B256};
2use reth_db::DatabaseError;
3use reth_trie::{
4    trie_cursor::{TrieCursor, TrieCursorFactory},
5    updates::{StorageTrieUpdates, TrieUpdates},
6    BranchNodeCompact, Nibbles,
7};
8use std::collections::BTreeSet;
9use tracing::warn;
10
11#[derive(Debug)]
12struct EntryDiff<T> {
13    task: T,
14    regular: T,
15    database: T,
16}
17
18#[derive(Debug, Default)]
19struct TrieUpdatesDiff {
20    account_nodes: HashMap<Nibbles, EntryDiff<Option<BranchNodeCompact>>>,
21    removed_nodes: HashMap<Nibbles, EntryDiff<bool>>,
22    storage_tries: HashMap<B256, StorageTrieUpdatesDiff>,
23}
24
25impl TrieUpdatesDiff {
26    fn has_differences(&self) -> bool {
27        !self.account_nodes.is_empty() ||
28            !self.removed_nodes.is_empty() ||
29            !self.storage_tries.is_empty()
30    }
31
32    pub(super) fn log_differences(mut self) {
33        if self.has_differences() {
34            for (path, EntryDiff { task, regular, database }) in &mut self.account_nodes {
35                warn!(target: "engine::tree", ?path, ?task, ?regular, ?database, "Difference in account trie updates");
36            }
37
38            for (
39                path,
40                EntryDiff {
41                    task: task_removed,
42                    regular: regular_removed,
43                    database: database_not_exists,
44                },
45            ) in &self.removed_nodes
46            {
47                warn!(target: "engine::tree", ?path, ?task_removed, ?regular_removed, ?database_not_exists, "Difference in removed account trie nodes");
48            }
49
50            for (address, storage_diff) in self.storage_tries {
51                storage_diff.log_differences(address);
52            }
53        }
54    }
55}
56
57#[derive(Debug, Default)]
58struct StorageTrieUpdatesDiff {
59    is_deleted: Option<EntryDiff<bool>>,
60    storage_nodes: HashMap<Nibbles, EntryDiff<Option<BranchNodeCompact>>>,
61    removed_nodes: HashMap<Nibbles, EntryDiff<bool>>,
62}
63
64impl StorageTrieUpdatesDiff {
65    fn has_differences(&self) -> bool {
66        self.is_deleted.is_some() ||
67            !self.storage_nodes.is_empty() ||
68            !self.removed_nodes.is_empty()
69    }
70
71    fn log_differences(&self, address: B256) {
72        if let Some(EntryDiff {
73            task: task_deleted,
74            regular: regular_deleted,
75            database: database_not_exists,
76        }) = self.is_deleted
77        {
78            warn!(target: "engine::tree", ?address, ?task_deleted, ?regular_deleted, ?database_not_exists, "Difference in storage trie deletion");
79        }
80
81        for (path, EntryDiff { task, regular, database }) in &self.storage_nodes {
82            warn!(target: "engine::tree", ?address, ?path, ?task, ?regular, ?database, "Difference in storage trie updates");
83        }
84
85        for (
86            path,
87            EntryDiff {
88                task: task_removed,
89                regular: regular_removed,
90                database: database_not_exists,
91            },
92        ) in &self.removed_nodes
93        {
94            warn!(target: "engine::tree", ?address, ?path, ?task_removed, ?regular_removed, ?database_not_exists, "Difference in removed storage trie nodes");
95        }
96    }
97}
98
99/// Compares the trie updates from state root task, regular state root calculation and database,
100/// and logs the differences if there's any.
101pub(super) fn compare_trie_updates(
102    trie_cursor_factory: impl TrieCursorFactory,
103    task: TrieUpdates,
104    regular: TrieUpdates,
105) -> Result<(), DatabaseError> {
106    let mut task = adjust_trie_updates(task);
107    let mut regular = adjust_trie_updates(regular);
108
109    let mut diff = TrieUpdatesDiff::default();
110
111    // compare account nodes
112    let mut account_trie_cursor = trie_cursor_factory.account_trie_cursor()?;
113    for key in task
114        .account_nodes
115        .keys()
116        .chain(regular.account_nodes.keys())
117        .copied()
118        .collect::<BTreeSet<_>>()
119    {
120        let (task, regular) = (task.account_nodes.remove(&key), regular.account_nodes.remove(&key));
121        let database = account_trie_cursor.seek_exact(key)?.map(|x| x.1);
122
123        if !branch_nodes_equal(task.as_ref(), regular.as_ref(), database.as_ref())? {
124            diff.account_nodes.insert(key, EntryDiff { task, regular, database });
125        }
126    }
127
128    // compare removed nodes
129    let mut account_trie_cursor = trie_cursor_factory.account_trie_cursor()?;
130    for key in task
131        .removed_nodes
132        .iter()
133        .chain(regular.removed_nodes.iter())
134        .copied()
135        .collect::<BTreeSet<_>>()
136    {
137        let (task_removed, regular_removed) =
138            (task.removed_nodes.contains(&key), regular.removed_nodes.contains(&key));
139        let database_not_exists = account_trie_cursor.seek_exact(key)?.is_none();
140        // If the deletion is a no-op, meaning that the entry is not in the
141        // database, do not add it to the diff.
142        if task_removed != regular_removed && !database_not_exists {
143            diff.removed_nodes.insert(
144                key,
145                EntryDiff {
146                    task: task_removed,
147                    regular: regular_removed,
148                    database: database_not_exists,
149                },
150            );
151        }
152    }
153
154    // compare storage tries
155    for key in task
156        .storage_tries
157        .keys()
158        .chain(regular.storage_tries.keys())
159        .copied()
160        .collect::<BTreeSet<_>>()
161    {
162        let (mut task, mut regular) =
163            (task.storage_tries.remove(&key), regular.storage_tries.remove(&key));
164        if task != regular {
165            #[expect(clippy::or_fun_call)]
166            let storage_diff = compare_storage_trie_updates(
167                || trie_cursor_factory.storage_trie_cursor(key),
168                // Compare non-existent storage tries as empty.
169                task.as_mut().unwrap_or(&mut Default::default()),
170                regular.as_mut().unwrap_or(&mut Default::default()),
171            )?;
172            if storage_diff.has_differences() {
173                diff.storage_tries.insert(key, storage_diff);
174            }
175        }
176    }
177
178    // log differences
179    diff.log_differences();
180
181    Ok(())
182}
183
184fn compare_storage_trie_updates<C: TrieCursor>(
185    trie_cursor: impl Fn() -> Result<C, DatabaseError>,
186    task: &mut StorageTrieUpdates,
187    regular: &mut StorageTrieUpdates,
188) -> Result<StorageTrieUpdatesDiff, DatabaseError> {
189    let database_not_exists = trie_cursor()?.next()?.is_none();
190    let mut diff = StorageTrieUpdatesDiff {
191        // If the deletion is a no-op, meaning that the entry is not in the
192        // database, do not add it to the diff.
193        is_deleted: (task.is_deleted != regular.is_deleted && !database_not_exists).then_some(
194            EntryDiff {
195                task: task.is_deleted,
196                regular: regular.is_deleted,
197                database: database_not_exists,
198            },
199        ),
200        ..Default::default()
201    };
202
203    // compare storage nodes
204    let mut storage_trie_cursor = trie_cursor()?;
205    for key in task
206        .storage_nodes
207        .keys()
208        .chain(regular.storage_nodes.keys())
209        .copied()
210        .collect::<BTreeSet<_>>()
211    {
212        let (task, regular) = (task.storage_nodes.remove(&key), regular.storage_nodes.remove(&key));
213        let database = storage_trie_cursor.seek_exact(key)?.map(|x| x.1);
214        if !branch_nodes_equal(task.as_ref(), regular.as_ref(), database.as_ref())? {
215            diff.storage_nodes.insert(key, EntryDiff { task, regular, database });
216        }
217    }
218
219    // compare removed nodes
220    let mut storage_trie_cursor = trie_cursor()?;
221    for key in
222        task.removed_nodes.iter().chain(regular.removed_nodes.iter()).collect::<BTreeSet<_>>()
223    {
224        let (task_removed, regular_removed) =
225            (task.removed_nodes.contains(key), regular.removed_nodes.contains(key));
226        if task_removed == regular_removed {
227            continue;
228        }
229        let database_not_exists = storage_trie_cursor.seek_exact(*key)?.map(|x| x.1).is_none();
230        // If the deletion is a no-op, meaning that the entry is not in the
231        // database, do not add it to the diff.
232        if !database_not_exists {
233            diff.removed_nodes.insert(
234                *key,
235                EntryDiff {
236                    task: task_removed,
237                    regular: regular_removed,
238                    database: database_not_exists,
239                },
240            );
241        }
242    }
243
244    Ok(diff)
245}
246
247/// Filters the removed nodes of both account trie updates and storage trie updates, so that they
248/// don't include those nodes that were also updated.
249fn adjust_trie_updates(trie_updates: TrieUpdates) -> TrieUpdates {
250    TrieUpdates {
251        removed_nodes: trie_updates
252            .removed_nodes
253            .into_iter()
254            .filter(|key| !trie_updates.account_nodes.contains_key(key))
255            .collect(),
256        storage_tries: trie_updates
257            .storage_tries
258            .into_iter()
259            .map(|(address, updates)| {
260                (
261                    address,
262                    StorageTrieUpdates {
263                        removed_nodes: updates
264                            .removed_nodes
265                            .into_iter()
266                            .filter(|key| !updates.storage_nodes.contains_key(key))
267                            .collect(),
268                        ..updates
269                    },
270                )
271            })
272            .collect(),
273        ..trie_updates
274    }
275}
276
277/// Compares the branch nodes from state root task and regular state root calculation.
278///
279/// If one of the branch nodes is [`None`], it means it's not updated and the other is compared to
280/// the branch node from the database.
281///
282/// Returns `true` if they are equal.
283fn branch_nodes_equal(
284    task: Option<&BranchNodeCompact>,
285    regular: Option<&BranchNodeCompact>,
286    database: Option<&BranchNodeCompact>,
287) -> Result<bool, DatabaseError> {
288    Ok(match (task, regular) {
289        (Some(task), Some(regular)) => {
290            task.state_mask == regular.state_mask &&
291                task.tree_mask == regular.tree_mask &&
292                task.hash_mask == regular.hash_mask &&
293                task.hashes == regular.hashes &&
294                task.root_hash == regular.root_hash
295        }
296        (None, None) => true,
297        _ => {
298            if task.is_some() {
299                task == database
300            } else {
301                regular == database
302            }
303        }
304    })
305}