reth_trie_db/
state.rs

1use crate::{DatabaseHashedCursorFactory, DatabaseTrieCursorFactory};
2use alloy_primitives::{keccak256, map::B256Map, BlockNumber, B256};
3use reth_db_api::{
4    models::{AccountBeforeTx, BlockNumberAddress},
5    transaction::DbTx,
6};
7use reth_execution_errors::StateRootError;
8use reth_storage_api::{
9    BlockNumReader, ChangeSetReader, DBProvider, StorageChangeSetReader, StorageSettingsCache,
10};
11use reth_storage_errors::provider::ProviderError;
12use reth_trie::{
13    hashed_cursor::HashedPostStateCursorFactory, trie_cursor::InMemoryTrieCursorFactory,
14    updates::TrieUpdates, HashedPostStateSorted, HashedStorageSorted, StateRoot, StateRootProgress,
15    TrieInputSorted,
16};
17use std::{
18    collections::HashSet,
19    ops::{Bound, RangeBounds, RangeInclusive},
20};
21use tracing::{debug, instrument};
22
23/// Extends [`StateRoot`] with operations specific for working with a database transaction.
24pub trait DatabaseStateRoot<'a, TX>: Sized {
25    /// Create a new [`StateRoot`] instance.
26    fn from_tx(tx: &'a TX) -> Self;
27
28    /// Given a block number range, identifies all the accounts and storage keys that
29    /// have changed.
30    ///
31    /// # Returns
32    ///
33    /// An instance of state root calculator with account and storage prefixes loaded.
34    fn incremental_root_calculator(
35        provider: &'a (impl ChangeSetReader
36                 + StorageChangeSetReader
37                 + StorageSettingsCache
38                 + DBProvider<Tx = TX>),
39        range: RangeInclusive<BlockNumber>,
40    ) -> Result<Self, StateRootError>;
41
42    /// Computes the state root of the trie with the changed account and storage prefixes and
43    /// existing trie nodes.
44    ///
45    /// # Returns
46    ///
47    /// The updated state root.
48    fn incremental_root(
49        provider: &'a (impl ChangeSetReader
50                 + StorageChangeSetReader
51                 + StorageSettingsCache
52                 + DBProvider<Tx = TX>),
53        range: RangeInclusive<BlockNumber>,
54    ) -> Result<B256, StateRootError>;
55
56    /// Computes the state root of the trie with the changed account and storage prefixes and
57    /// existing trie nodes collecting updates in the process.
58    ///
59    /// Ignores the threshold.
60    ///
61    /// # Returns
62    ///
63    /// The updated state root and the trie updates.
64    fn incremental_root_with_updates(
65        provider: &'a (impl ChangeSetReader
66                 + StorageChangeSetReader
67                 + StorageSettingsCache
68                 + DBProvider<Tx = TX>),
69        range: RangeInclusive<BlockNumber>,
70    ) -> Result<(B256, TrieUpdates), StateRootError>;
71
72    /// Computes the state root of the trie with the changed account and storage prefixes and
73    /// existing trie nodes collecting updates in the process.
74    ///
75    /// # Returns
76    ///
77    /// The intermediate progress of state root computation.
78    fn incremental_root_with_progress(
79        provider: &'a (impl ChangeSetReader
80                 + StorageChangeSetReader
81                 + StorageSettingsCache
82                 + DBProvider<Tx = TX>),
83        range: RangeInclusive<BlockNumber>,
84    ) -> Result<StateRootProgress, StateRootError>;
85
86    /// Calculate the state root for this [`HashedPostStateSorted`].
87    /// Internally, this method retrieves prefixsets and uses them
88    /// to calculate incremental state root.
89    ///
90    /// # Example
91    ///
92    /// ```
93    /// use alloy_primitives::U256;
94    /// use reth_db::test_utils::create_test_rw_db;
95    /// use reth_db_api::database::Database;
96    /// use reth_primitives_traits::Account;
97    /// use reth_trie::{updates::TrieUpdates, HashedPostState, StateRoot};
98    /// use reth_trie_db::{DatabaseStateRoot, LegacyKeyAdapter};
99    ///
100    /// // Initialize the database
101    /// let db = create_test_rw_db();
102    ///
103    /// // Initialize hashed post state
104    /// let mut hashed_state = HashedPostState::default();
105    /// hashed_state.accounts.insert(
106    ///     [0x11; 32].into(),
107    ///     Some(Account { nonce: 1, balance: U256::from(10), bytecode_hash: None }),
108    /// );
109    ///
110    /// // Calculate the state root
111    /// let tx = db.tx().expect("failed to create transaction");
112    /// let state_root = <StateRoot<
113    ///     reth_trie_db::DatabaseTrieCursorFactory<_, LegacyKeyAdapter>,
114    ///     reth_trie_db::DatabaseHashedCursorFactory<_>,
115    /// > as DatabaseStateRoot<_>>::overlay_root(&tx, &hashed_state.into_sorted());
116    /// ```
117    ///
118    /// # Returns
119    ///
120    /// The state root for this [`HashedPostStateSorted`].
121    fn overlay_root(tx: &'a TX, post_state: &HashedPostStateSorted)
122        -> Result<B256, StateRootError>;
123
124    /// Calculates the state root for this [`HashedPostStateSorted`] and returns it alongside trie
125    /// updates. See [`Self::overlay_root`] for more info.
126    fn overlay_root_with_updates(
127        tx: &'a TX,
128        post_state: &HashedPostStateSorted,
129    ) -> Result<(B256, TrieUpdates), StateRootError>;
130
131    /// Calculates the state root for provided [`HashedPostStateSorted`] using cached intermediate
132    /// nodes.
133    fn overlay_root_from_nodes(tx: &'a TX, input: TrieInputSorted) -> Result<B256, StateRootError>;
134
135    /// Calculates the state root and trie updates for provided [`HashedPostStateSorted`] using
136    /// cached intermediate nodes.
137    fn overlay_root_from_nodes_with_updates(
138        tx: &'a TX,
139        input: TrieInputSorted,
140    ) -> Result<(B256, TrieUpdates), StateRootError>;
141}
142
143/// Extends [`HashedPostStateSorted`] with operations specific for working with a database
144/// transaction.
145pub trait DatabaseHashedPostState: Sized {
146    /// Initializes [`HashedPostStateSorted`] from reverts. Iterates over state reverts in the
147    /// specified range and aggregates them into sorted hashed state.
148    fn from_reverts(
149        provider: &(impl ChangeSetReader + StorageChangeSetReader + BlockNumReader + DBProvider),
150        range: impl RangeBounds<BlockNumber>,
151    ) -> Result<HashedPostStateSorted, ProviderError>;
152}
153
154impl<'a, TX: DbTx, A: crate::TrieTableAdapter> DatabaseStateRoot<'a, TX>
155    for StateRoot<DatabaseTrieCursorFactory<&'a TX, A>, DatabaseHashedCursorFactory<&'a TX>>
156{
157    fn from_tx(tx: &'a TX) -> Self {
158        Self::new(DatabaseTrieCursorFactory::new(tx), DatabaseHashedCursorFactory::new(tx))
159    }
160
161    fn incremental_root_calculator(
162        provider: &'a (impl ChangeSetReader
163                 + StorageChangeSetReader
164                 + StorageSettingsCache
165                 + DBProvider<Tx = TX>),
166        range: RangeInclusive<BlockNumber>,
167    ) -> Result<Self, StateRootError> {
168        let loaded_prefix_sets =
169            crate::prefix_set::load_prefix_sets_with_provider(provider, range)?;
170        Ok(Self::from_tx(provider.tx_ref()).with_prefix_sets(loaded_prefix_sets))
171    }
172
173    fn incremental_root(
174        provider: &'a (impl ChangeSetReader
175                 + StorageChangeSetReader
176                 + StorageSettingsCache
177                 + DBProvider<Tx = TX>),
178        range: RangeInclusive<BlockNumber>,
179    ) -> Result<B256, StateRootError> {
180        debug!(target: "trie::loader", ?range, "incremental state root");
181        Self::incremental_root_calculator(provider, range)?.root()
182    }
183
184    fn incremental_root_with_updates(
185        provider: &'a (impl ChangeSetReader
186                 + StorageChangeSetReader
187                 + StorageSettingsCache
188                 + DBProvider<Tx = TX>),
189        range: RangeInclusive<BlockNumber>,
190    ) -> Result<(B256, TrieUpdates), StateRootError> {
191        debug!(target: "trie::loader", ?range, "incremental state root");
192        Self::incremental_root_calculator(provider, range)?.root_with_updates()
193    }
194
195    fn incremental_root_with_progress(
196        provider: &'a (impl ChangeSetReader
197                 + StorageChangeSetReader
198                 + StorageSettingsCache
199                 + DBProvider<Tx = TX>),
200        range: RangeInclusive<BlockNumber>,
201    ) -> Result<StateRootProgress, StateRootError> {
202        debug!(target: "trie::loader", ?range, "incremental state root with progress");
203        Self::incremental_root_calculator(provider, range)?.root_with_progress()
204    }
205
206    fn overlay_root(
207        tx: &'a TX,
208        post_state: &HashedPostStateSorted,
209    ) -> Result<B256, StateRootError> {
210        let prefix_sets = post_state.construct_prefix_sets().freeze();
211        StateRoot::new(
212            DatabaseTrieCursorFactory::<_, A>::new(tx),
213            HashedPostStateCursorFactory::new(DatabaseHashedCursorFactory::new(tx), post_state),
214        )
215        .with_prefix_sets(prefix_sets)
216        .root()
217    }
218
219    fn overlay_root_with_updates(
220        tx: &'a TX,
221        post_state: &HashedPostStateSorted,
222    ) -> Result<(B256, TrieUpdates), StateRootError> {
223        let prefix_sets = post_state.construct_prefix_sets().freeze();
224        StateRoot::new(
225            DatabaseTrieCursorFactory::<_, A>::new(tx),
226            HashedPostStateCursorFactory::new(DatabaseHashedCursorFactory::new(tx), post_state),
227        )
228        .with_prefix_sets(prefix_sets)
229        .root_with_updates()
230    }
231
232    fn overlay_root_from_nodes(tx: &'a TX, input: TrieInputSorted) -> Result<B256, StateRootError> {
233        StateRoot::new(
234            InMemoryTrieCursorFactory::new(
235                DatabaseTrieCursorFactory::<_, A>::new(tx),
236                input.nodes.as_ref(),
237            ),
238            HashedPostStateCursorFactory::new(
239                DatabaseHashedCursorFactory::new(tx),
240                input.state.as_ref(),
241            ),
242        )
243        .with_prefix_sets(input.prefix_sets.freeze())
244        .root()
245    }
246
247    fn overlay_root_from_nodes_with_updates(
248        tx: &'a TX,
249        input: TrieInputSorted,
250    ) -> Result<(B256, TrieUpdates), StateRootError> {
251        StateRoot::new(
252            InMemoryTrieCursorFactory::new(
253                DatabaseTrieCursorFactory::<_, A>::new(tx),
254                input.nodes.as_ref(),
255            ),
256            HashedPostStateCursorFactory::new(
257                DatabaseHashedCursorFactory::new(tx),
258                input.state.as_ref(),
259            ),
260        )
261        .with_prefix_sets(input.prefix_sets.freeze())
262        .root_with_updates()
263    }
264}
265
266/// Calls [`HashedPostStateSorted::from_reverts`].
267pub fn from_reverts_auto(
268    provider: &(impl ChangeSetReader
269          + StorageChangeSetReader
270          + BlockNumReader
271          + DBProvider
272          + StorageSettingsCache),
273    range: impl RangeBounds<BlockNumber>,
274) -> Result<HashedPostStateSorted, ProviderError> {
275    HashedPostStateSorted::from_reverts(provider, range)
276}
277
278impl DatabaseHashedPostState for HashedPostStateSorted {
279    /// Builds a sorted hashed post-state from reverts.
280    ///
281    /// Reads MDBX data directly into Vecs, using `HashSet`s only to track seen keys.
282    /// This avoids intermediate `HashMap` allocations since MDBX data is already sorted.
283    ///
284    /// - Reads the first occurrence of each changed account/storage slot in the range.
285    /// - Addresses are always keccak256-hashed.
286    /// - Storage keys are always plain and are hashed via `keccak256`.
287    /// - Returns keys already ordered for trie iteration.
288    #[instrument(target = "trie::db", skip(provider), fields(range))]
289    fn from_reverts(
290        provider: &(impl ChangeSetReader + StorageChangeSetReader + BlockNumReader + DBProvider),
291        range: impl RangeBounds<BlockNumber>,
292    ) -> Result<Self, ProviderError> {
293        // Extract concrete start/end values to use for both account and storage changesets.
294        let start = match range.start_bound() {
295            Bound::Included(&n) => n,
296            Bound::Excluded(&n) => n + 1,
297            Bound::Unbounded => 0,
298        };
299
300        let end = match range.end_bound() {
301            Bound::Included(&n) => n + 1,
302            Bound::Excluded(&n) => n,
303            Bound::Unbounded => BlockNumber::MAX,
304        };
305
306        // Iterate over account changesets and record value before first occurring account change
307        let mut accounts = Vec::new();
308        let mut seen_accounts = HashSet::new();
309        for entry in provider.account_changesets_range(start..end)? {
310            let (_, AccountBeforeTx { address, info }) = entry;
311            if seen_accounts.insert(address) {
312                accounts.push((keccak256(address), info));
313            }
314        }
315        accounts.sort_unstable_by_key(|(hash, _)| *hash);
316
317        // Read storages into B256Map<Vec<_>> with HashSet to track seen keys.
318        // Only keep the first (oldest) occurrence of each (address, slot) pair.
319        let mut storages = B256Map::<Vec<_>>::default();
320        let mut seen_storage_keys = HashSet::new();
321
322        if start < end {
323            let end_inclusive = end.saturating_sub(1);
324            for (BlockNumberAddress((_, address)), storage) in
325                provider.storage_changesets_range(start..=end_inclusive)?
326            {
327                if seen_storage_keys.insert((address, storage.key)) {
328                    let hashed_address = keccak256(address);
329                    storages
330                        .entry(hashed_address)
331                        .or_default()
332                        .push((keccak256(storage.key), storage.value));
333                }
334            }
335        }
336
337        // Sort storage slots and convert to HashedStorageSorted
338        let hashed_storages = storages
339            .into_iter()
340            .map(|(address, mut slots)| {
341                slots.sort_unstable_by_key(|(slot, _)| *slot);
342                (address, HashedStorageSorted { storage_slots: slots, wiped: false })
343            })
344            .collect();
345
346        Ok(Self::new(accounts, hashed_storages))
347    }
348}
349
350#[cfg(test)]
351mod tests {
352    use super::*;
353    use alloy_primitives::{hex, keccak256, map::HashMap, Address, B256, U256};
354    use reth_db_api::{
355        models::{AccountBeforeTx, BlockNumberAddress},
356        tables,
357        transaction::DbTxMut,
358    };
359    use reth_execution_errors::StateRootError;
360    use reth_primitives_traits::{Account, StorageEntry};
361    use reth_provider::test_utils::create_test_provider_factory;
362    use reth_storage_api::StorageSettingsCache;
363    use reth_trie::{
364        HashedPostState, HashedPostStateSorted, HashedStorage, KeccakKeyHasher, StateRoot,
365    };
366    use revm::{database::BundleState, state::AccountInfo};
367
368    fn overlay_root_for_provider<TX: reth_db_api::transaction::DbTx>(
369        provider: &impl StorageSettingsCache,
370        tx: &TX,
371        sorted: &HashedPostStateSorted,
372    ) -> Result<B256, StateRootError> {
373        crate::with_adapter!(provider, |A| {
374            type S<'a, TX> = StateRoot<
375                crate::DatabaseTrieCursorFactory<&'a TX, A>,
376                crate::DatabaseHashedCursorFactory<&'a TX>,
377            >;
378            S::overlay_root(tx, sorted)
379        })
380    }
381
382    /// Overlay root calculation works with sorted state.
383    #[test]
384    fn overlay_root_with_sorted_state() {
385        let factory = create_test_provider_factory();
386        let provider = factory.provider_rw().unwrap();
387
388        let mut hashed_state = HashedPostState::default();
389        hashed_state.accounts.insert(
390            B256::from(U256::from(1)),
391            Some(Account { nonce: 1, balance: U256::from(10), bytecode_hash: None }),
392        );
393        hashed_state.accounts.insert(B256::from(U256::from(2)), None);
394        hashed_state.storages.insert(
395            B256::from(U256::from(1)),
396            HashedStorage::from_iter(false, [(B256::from(U256::from(3)), U256::from(30))]),
397        );
398
399        let sorted = hashed_state.into_sorted();
400        let overlay_root =
401            overlay_root_for_provider(&*provider, provider.tx_ref(), &sorted).unwrap();
402
403        // Just verify it produces a valid root
404        assert!(!overlay_root.is_zero());
405    }
406
407    /// Builds hashed state from a bundle and checks the known state root.
408    #[test]
409    fn from_bundle_state_with_rayon() {
410        let address1 = Address::with_last_byte(1);
411        let address2 = Address::with_last_byte(2);
412        let slot1 = U256::from(1015);
413        let slot2 = U256::from(2015);
414
415        let account1 = AccountInfo { nonce: 1, ..Default::default() };
416        let account2 = AccountInfo { nonce: 2, ..Default::default() };
417
418        let bundle_state = BundleState::builder(2..=2)
419            .state_present_account_info(address1, account1)
420            .state_present_account_info(address2, account2)
421            .state_storage(address1, HashMap::from_iter([(slot1, (U256::ZERO, U256::from(10)))]))
422            .state_storage(address2, HashMap::from_iter([(slot2, (U256::ZERO, U256::from(20)))]))
423            .build();
424        assert_eq!(bundle_state.reverts.len(), 1);
425
426        let post_state = HashedPostState::from_bundle_state::<KeccakKeyHasher>(&bundle_state.state);
427        assert_eq!(post_state.accounts.len(), 2);
428        assert_eq!(post_state.storages.len(), 2);
429
430        let factory = create_test_provider_factory();
431        let provider = factory.provider_rw().unwrap();
432        let sorted = post_state.into_sorted();
433        assert_eq!(
434            overlay_root_for_provider(&*provider, provider.tx_ref(), &sorted).unwrap(),
435            hex!("b464525710cafcf5d4044ac85b72c08b1e76231b8d91f288fe438cc41d8eaafd")
436        );
437    }
438
439    /// Verifies `from_reverts` keeps first occurrence per key and preserves ordering guarantees.
440    #[test]
441    fn from_reverts_keeps_first_occurrence_and_ordering() {
442        let factory = create_test_provider_factory();
443        let provider = factory.provider_rw().unwrap();
444
445        let address1 = Address::with_last_byte(1);
446        let address2 = Address::with_last_byte(2);
447        let slot1 = B256::from(U256::from(11));
448        let slot2 = B256::from(U256::from(22));
449
450        // Account changesets: only first occurrence per address should be kept.
451        provider
452            .tx_ref()
453            .put::<tables::AccountChangeSets>(
454                1,
455                AccountBeforeTx {
456                    address: address1,
457                    info: Some(Account { nonce: 1, ..Default::default() }),
458                },
459            )
460            .unwrap();
461        provider
462            .tx_ref()
463            .put::<tables::AccountChangeSets>(
464                2,
465                AccountBeforeTx {
466                    address: address1,
467                    info: Some(Account { nonce: 2, ..Default::default() }),
468                },
469            )
470            .unwrap();
471        provider
472            .tx_ref()
473            .put::<tables::AccountChangeSets>(3, AccountBeforeTx { address: address2, info: None })
474            .unwrap();
475
476        // Storage changesets: only first occurrence per slot should be kept, and slots sorted.
477        provider
478            .tx_ref()
479            .put::<tables::StorageChangeSets>(
480                BlockNumberAddress((1, address1)),
481                StorageEntry { key: slot2, value: U256::from(200) },
482            )
483            .unwrap();
484        provider
485            .tx_ref()
486            .put::<tables::StorageChangeSets>(
487                BlockNumberAddress((2, address1)),
488                StorageEntry { key: slot1, value: U256::from(100) },
489            )
490            .unwrap();
491        provider
492            .tx_ref()
493            .put::<tables::StorageChangeSets>(
494                BlockNumberAddress((3, address1)),
495                StorageEntry { key: slot1, value: U256::from(999) }, // should be ignored
496            )
497            .unwrap();
498
499        let sorted = HashedPostStateSorted::from_reverts(&*provider, 1..=3).unwrap();
500
501        // Verify first occurrences were kept (nonce 1, not 2)
502        assert_eq!(sorted.accounts.len(), 2);
503        let hashed_addr1 = keccak256(address1);
504        let account1 = sorted.accounts.iter().find(|(addr, _)| *addr == hashed_addr1).unwrap();
505        assert_eq!(account1.1.unwrap().nonce, 1);
506
507        // Ordering guarantees - accounts sorted by hashed address
508        assert!(sorted.accounts.windows(2).all(|w| w[0].0 <= w[1].0));
509
510        // Ordering guarantees - storage slots sorted by hashed slot
511        for storage in sorted.storages.values() {
512            assert!(storage.storage_slots.windows(2).all(|w| w[0].0 <= w[1].0));
513        }
514    }
515
516    /// Empty block range returns empty state.
517    #[test]
518    fn from_reverts_empty_range() {
519        let factory = create_test_provider_factory();
520        let provider = factory.provider_rw().unwrap();
521
522        // Insert data outside the query range
523        provider
524            .tx_ref()
525            .put::<tables::AccountChangeSets>(
526                100,
527                AccountBeforeTx {
528                    address: Address::with_last_byte(1),
529                    info: Some(Account { nonce: 1, ..Default::default() }),
530                },
531            )
532            .unwrap();
533
534        // Query a range with no data
535        let sorted = HashedPostStateSorted::from_reverts(&*provider, 1..=10).unwrap();
536        assert!(sorted.accounts.is_empty());
537        assert!(sorted.storages.is_empty());
538    }
539
540    #[test]
541    fn from_reverts_with_hashed_state() {
542        use reth_db_api::models::{StorageBeforeTx, StorageSettings};
543        use reth_provider::{StaticFileProviderFactory, StaticFileSegment, StaticFileWriter};
544
545        let factory = create_test_provider_factory();
546
547        factory.set_storage_settings_cache(StorageSettings::v2());
548
549        let provider = factory.provider_rw().unwrap();
550
551        let address1 = Address::with_last_byte(1);
552        let address2 = Address::with_last_byte(2);
553
554        let plain_slot1 = B256::from(U256::from(11));
555        let plain_slot2 = B256::from(U256::from(22));
556        let hashed_slot1 = keccak256(plain_slot1);
557        let hashed_slot2 = keccak256(plain_slot2);
558
559        {
560            let sf = factory.static_file_provider();
561
562            // Write account changesets to static files (v2 reads from here)
563            let mut aw = sf.latest_writer(StaticFileSegment::AccountChangeSets).unwrap();
564            aw.append_account_changeset(vec![], 0).unwrap();
565            aw.append_account_changeset(
566                vec![AccountBeforeTx {
567                    address: address1,
568                    info: Some(Account { nonce: 1, ..Default::default() }),
569                }],
570                1,
571            )
572            .unwrap();
573            aw.append_account_changeset(
574                vec![AccountBeforeTx {
575                    address: address1,
576                    info: Some(Account { nonce: 2, ..Default::default() }),
577                }],
578                2,
579            )
580            .unwrap();
581            aw.append_account_changeset(vec![AccountBeforeTx { address: address2, info: None }], 3)
582                .unwrap();
583            aw.commit().unwrap();
584
585            let mut writer = sf.latest_writer(StaticFileSegment::StorageChangeSets).unwrap();
586            writer.append_storage_changeset(vec![], 0).unwrap();
587            writer
588                .append_storage_changeset(
589                    vec![StorageBeforeTx {
590                        address: address1,
591                        key: plain_slot2,
592                        value: U256::from(200),
593                    }],
594                    1,
595                )
596                .unwrap();
597            writer
598                .append_storage_changeset(
599                    vec![StorageBeforeTx {
600                        address: address1,
601                        key: plain_slot1,
602                        value: U256::from(100),
603                    }],
604                    2,
605                )
606                .unwrap();
607            writer
608                .append_storage_changeset(
609                    vec![StorageBeforeTx {
610                        address: address1,
611                        key: plain_slot1,
612                        value: U256::from(999),
613                    }],
614                    3,
615                )
616                .unwrap();
617            writer.commit().unwrap();
618        }
619
620        let sorted = HashedPostStateSorted::from_reverts(&*provider, 1..=3).unwrap();
621
622        assert_eq!(sorted.accounts.len(), 2);
623
624        let hashed_addr1 = keccak256(address1);
625        let hashed_addr2 = keccak256(address2);
626
627        let account1 = sorted.accounts.iter().find(|(addr, _)| *addr == hashed_addr1).unwrap();
628        assert_eq!(account1.1.unwrap().nonce, 1);
629
630        let account2 = sorted.accounts.iter().find(|(addr, _)| *addr == hashed_addr2).unwrap();
631        assert!(account2.1.is_none());
632
633        assert!(sorted.accounts.windows(2).all(|w| w[0].0 <= w[1].0));
634
635        let storage = sorted.storages.get(&hashed_addr1).expect("storage for address1");
636        assert_eq!(storage.storage_slots.len(), 2);
637
638        let found_slot1 = storage.storage_slots.iter().find(|(k, _)| *k == hashed_slot1).unwrap();
639        assert_eq!(found_slot1.1, U256::from(100));
640
641        let found_slot2 = storage.storage_slots.iter().find(|(k, _)| *k == hashed_slot2).unwrap();
642        assert_eq!(found_slot2.1, U256::from(200));
643
644        assert_ne!(hashed_slot1, plain_slot1);
645        assert_ne!(hashed_slot2, plain_slot2);
646
647        assert!(storage.storage_slots.windows(2).all(|w| w[0].0 <= w[1].0));
648    }
649
650    #[test]
651    fn from_reverts_legacy_keccak_hashes_all_keys() {
652        let factory = create_test_provider_factory();
653        let provider = factory.provider_rw().unwrap();
654
655        let address1 = Address::with_last_byte(1);
656        let address2 = Address::with_last_byte(2);
657        let plain_slot1 = B256::from(U256::from(11));
658        let plain_slot2 = B256::from(U256::from(22));
659
660        provider
661            .tx_ref()
662            .put::<tables::AccountChangeSets>(
663                1,
664                AccountBeforeTx {
665                    address: address1,
666                    info: Some(Account { nonce: 10, ..Default::default() }),
667                },
668            )
669            .unwrap();
670        provider
671            .tx_ref()
672            .put::<tables::AccountChangeSets>(
673                2,
674                AccountBeforeTx {
675                    address: address2,
676                    info: Some(Account { nonce: 20, ..Default::default() }),
677                },
678            )
679            .unwrap();
680        provider
681            .tx_ref()
682            .put::<tables::AccountChangeSets>(
683                3,
684                AccountBeforeTx {
685                    address: address1,
686                    info: Some(Account { nonce: 99, ..Default::default() }),
687                },
688            )
689            .unwrap();
690
691        provider
692            .tx_ref()
693            .put::<tables::StorageChangeSets>(
694                BlockNumberAddress((1, address1)),
695                StorageEntry { key: plain_slot1, value: U256::from(100) },
696            )
697            .unwrap();
698        provider
699            .tx_ref()
700            .put::<tables::StorageChangeSets>(
701                BlockNumberAddress((2, address1)),
702                StorageEntry { key: plain_slot2, value: U256::from(200) },
703            )
704            .unwrap();
705        provider
706            .tx_ref()
707            .put::<tables::StorageChangeSets>(
708                BlockNumberAddress((3, address2)),
709                StorageEntry { key: plain_slot1, value: U256::from(300) },
710            )
711            .unwrap();
712
713        let sorted = HashedPostStateSorted::from_reverts(&*provider, 1..=3).unwrap();
714
715        let expected_hashed_addr1 = keccak256(address1);
716        let expected_hashed_addr2 = keccak256(address2);
717        assert_eq!(sorted.accounts.len(), 2);
718
719        let account1 =
720            sorted.accounts.iter().find(|(addr, _)| *addr == expected_hashed_addr1).unwrap();
721        assert_eq!(account1.1.unwrap().nonce, 10);
722
723        let account2 =
724            sorted.accounts.iter().find(|(addr, _)| *addr == expected_hashed_addr2).unwrap();
725        assert_eq!(account2.1.unwrap().nonce, 20);
726
727        assert!(sorted.accounts.windows(2).all(|w| w[0].0 <= w[1].0));
728
729        let expected_hashed_slot1 = keccak256(plain_slot1);
730        let expected_hashed_slot2 = keccak256(plain_slot2);
731
732        assert_ne!(expected_hashed_slot1, plain_slot1);
733        assert_ne!(expected_hashed_slot2, plain_slot2);
734
735        let storage1 = sorted.storages.get(&expected_hashed_addr1).expect("storage for address1");
736        assert_eq!(storage1.storage_slots.len(), 2);
737        assert!(storage1
738            .storage_slots
739            .iter()
740            .any(|(k, v)| *k == expected_hashed_slot1 && *v == U256::from(100)));
741        assert!(storage1
742            .storage_slots
743            .iter()
744            .any(|(k, v)| *k == expected_hashed_slot2 && *v == U256::from(200)));
745        assert!(storage1.storage_slots.windows(2).all(|w| w[0].0 <= w[1].0));
746
747        let storage2 = sorted.storages.get(&expected_hashed_addr2).expect("storage for address2");
748        assert_eq!(storage2.storage_slots.len(), 1);
749        assert_eq!(storage2.storage_slots[0].0, expected_hashed_slot1);
750        assert_eq!(storage2.storage_slots[0].1, U256::from(300));
751    }
752}
reth_trie_db/state.rs

reth_trie_db/
state.rs
