reth_snap_sync/catch_up/
apply.rs

1//! State updates implied by verified block access lists.
2//!
3//! [EIP-8189](https://eips.ethereum.org/EIPS/eip-8189#synchronization-algorithm) advances the
4//! pivot by applying later blocks' lists to the state downloaded so far. Each list records the
5//! final value of every field it changes, so untouched fields come from the downloaded account.
6
7use alloy_eip7928::AccountChanges;
8use alloy_primitives::{keccak256, map::B256Map, Bytes, B256};
9use reth_primitives_traits::Account;
10use reth_trie_common::{HashedPostState, HashedStorage};
11
12/// Changes one block access list makes to the downloaded state.
13#[derive(Clone, Debug, Default, PartialEq, Eq)]
14pub struct BalStateUpdate {
15    // Post-state of every downloaded account, and slots persisted ahead of their range.
16    pub(super) state: HashedPostState,
17    // Final code of accounts whose code changed, keyed by code hash.
18    pub(super) bytecodes: B256Map<Bytes>,
19    // Entries left out because their account is not downloaded yet.
20    pub(super) unresolved: Vec<B256>,
21}
22
23impl BalStateUpdate {
24    /// Post-state of every downloaded account, and slots persisted ahead of their range.
25    pub const fn state(&self) -> &HashedPostState {
26        &self.state
27    }
28
29    /// Final code of accounts whose code changed, keyed by code hash.
30    pub const fn bytecodes(&self) -> &B256Map<Bytes> {
31        &self.bytecodes
32    }
33
34    /// Hashed addresses of entries left out because their account is not downloaded yet.
35    pub fn unresolved(&self) -> &[B256] {
36        &self.unresolved
37    }
38
39    /// Consumes this update into the state it writes, the code it stores and its unresolved
40    /// entries.
41    pub fn into_parts(self) -> (HashedPostState, B256Map<Bytes>, Vec<B256>) {
42        (self.state, self.bytecodes, self.unresolved)
43    }
44
45    // Records the final values of the slots `changes` writes for `hashed_address`.
46    pub(super) fn insert_storage(&mut self, hashed_address: B256, changes: &AccountChanges) {
47        let storage = HashedStorage::from_iter(
48            changes.storage_post_states().map(|(slot, value)| (keccak256(B256::from(slot)), value)),
49        );
50        self.state.storages.insert(hashed_address, storage);
51    }
52}
53
54/// What the downloaded state holds for an account a list changes.
55#[derive(Clone, Debug, PartialEq, Eq)]
56pub enum DownloadedAccount {
57    /// The account's range is not downloaded yet.
58    Unknown,
59    /// The account's range is downloaded and does not hold it.
60    Absent,
61    /// The downloaded account.
62    Present(Account),
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68    use crate::{test_utils::hashed_factory, AccountCoverage, SnapCatchUpStore, StorageProgress};
69    use alloy_consensus::{Header, TxLegacy};
70    use alloy_eip7928::{
71        AccountChanges, BalanceChange, BlockAccessIndex, CodeChange, NonceChange, SlotChanges,
72        StorageChange,
73    };
74    use alloy_eips::{
75        eip2935::{HISTORY_STORAGE_ADDRESS, HISTORY_STORAGE_CODE},
76        eip4788::{BEACON_ROOTS_ADDRESS, BEACON_ROOTS_CODE},
77        eip4895::Withdrawal,
78        eip7002::{WITHDRAWAL_REQUEST_PREDEPLOY_ADDRESS, WITHDRAWAL_REQUEST_PREDEPLOY_CODE},
79    };
80    use alloy_primitives::{bytes, keccak256, Address, Signature, TxKind, U256};
81    use reth_chainspec::ChainSpecBuilder;
82    use reth_db_api::{tables, transaction::DbTxMut};
83    use reth_ethereum_primitives::{Block, BlockBody, Transaction, TransactionSigned};
84    use reth_evm::{execute::BlockExecutor, ConfigureEvm, Evm};
85    use reth_evm_ethereum::EthEvmConfig;
86    use reth_primitives_traits::{Block as _, Recovered};
87    use reth_storage_api::DatabaseProviderFactory;
88    use reth_trie_common::{HashedStorage, KeccakKeyHasher};
89    use revm::{
90        database::{states::bundle_state::BundleRetention, CacheDB, EmptyDB, State},
91        state::{AccountInfo, Bytecode},
92    };
93    use std::{collections::BTreeMap, sync::Arc};
94
95    const ACCOUNT: Address = Address::repeat_byte(0xaa);
96    const SENDER: Address = Address::repeat_byte(0x11);
97
98    fn index(value: u64) -> BlockAccessIndex {
99        BlockAccessIndex::new(value)
100    }
101
102    fn state_update(
103        bal: &[AccountChanges],
104        coverage: AccountCoverage,
105        accounts: impl IntoIterator<Item = (B256, Account)>,
106    ) -> BalStateUpdate {
107        let factory = hashed_factory();
108        let provider = factory.database_provider_rw().unwrap();
109        for (address, account) in accounts {
110            provider.tx_ref().put::<tables::HashedAccounts>(address, account).unwrap();
111        }
112        provider.block_access_list_update(coverage, StorageProgress::START, bal).unwrap()
113    }
114
115    fn apply(changes: &AccountChanges, base: DownloadedAccount) -> BalStateUpdate {
116        let (coverage, account) = match base {
117            DownloadedAccount::Unknown => (AccountCoverage::START, None),
118            DownloadedAccount::Absent => (AccountCoverage::COMPLETE, None),
119            DownloadedAccount::Present(account) => (AccountCoverage::COMPLETE, Some(account)),
120        };
121        state_update(
122            std::slice::from_ref(changes),
123            coverage,
124            account.map(|account| (keccak256(changes.address()), account)),
125        )
126    }
127
128    #[test]
129    fn read_only_entries_write_nothing() {
130        let changes = AccountChanges::new(ACCOUNT).with_storage_read(U256::from(1));
131
132        let update = apply(&changes, DownloadedAccount::Unknown);
133
134        assert_eq!(update, BalStateUpdate::default());
135    }
136
137    #[test]
138    fn empty_slot_entries_write_nothing() {
139        let changes = AccountChanges::new(ACCOUNT)
140            .with_storage_change(SlotChanges::new(U256::from(1), vec![]));
141
142        let update = apply(&changes, DownloadedAccount::Unknown);
143
144        assert_eq!(update, BalStateUpdate::default());
145    }
146
147    #[test]
148    fn account_changes_with_empty_slots_write_no_storage() {
149        let changes = AccountChanges::new(ACCOUNT)
150            .with_balance_change(BalanceChange::new(index(1), U256::from(10)))
151            .with_storage_change(SlotChanges::new(U256::from(1), vec![]));
152
153        let update = apply(&changes, DownloadedAccount::Absent);
154
155        assert_eq!(
156            update.state.accounts[&keccak256(ACCOUNT)].as_ref().unwrap().balance,
157            U256::from(10)
158        );
159        assert!(update.state.storages.is_empty());
160    }
161
162    #[test]
163    fn accounts_not_downloaded_yet_are_left_unresolved() {
164        // Even a fully determined account is left to the download against the later root.
165        let changes = AccountChanges::new(ACCOUNT)
166            .with_balance_change(BalanceChange::new(index(1), U256::from(10)))
167            .with_nonce_change(NonceChange::new(index(1), 1))
168            .with_code_change(CodeChange::new(index(1), bytes!("6001")));
169
170        let update = apply(&changes, DownloadedAccount::Unknown);
171
172        assert_eq!(update.unresolved, vec![keccak256(ACCOUNT)]);
173        assert!(update.state.is_empty());
174        assert!(update.bytecodes.is_empty());
175    }
176
177    #[test]
178    #[allow(clippy::clone_on_copy)]
179    fn untouched_fields_keep_their_downloaded_values() {
180        let existing = Account::new(4, U256::from(9), Some(B256::repeat_byte(1)));
181        let changes = AccountChanges::new(ACCOUNT)
182            .with_balance_change(BalanceChange::new(index(1), U256::from(10)))
183            .with_balance_change(BalanceChange::new(index(2), U256::from(20)));
184
185        let update = apply(&changes, DownloadedAccount::Present(existing.clone()));
186        assert_eq!(
187            update.state.accounts[&keccak256(ACCOUNT)],
188            Some(Account { balance: U256::from(20), ..existing })
189        );
190
191        // An absent account starts from the empty one.
192        let update = apply(&changes, DownloadedAccount::Absent);
193        assert_eq!(
194            update.state.accounts[&keccak256(ACCOUNT)],
195            Some(Account { balance: U256::from(20), ..Default::default() })
196        );
197    }
198
199    #[test]
200    fn zeroed_slots_and_cleared_code_are_written() {
201        let existing = Account::new(1, U256::from(1), Some(B256::repeat_byte(1)));
202        let changes = AccountChanges::new(ACCOUNT)
203            .with_code_change(CodeChange::new(index(1), bytes!("6001")))
204            .with_code_change(CodeChange::new(index(2), Bytes::new()))
205            .with_storage_change(SlotChanges::new(
206                U256::from(1),
207                vec![
208                    StorageChange::new(index(1), U256::from(5)),
209                    StorageChange::new(index(2), U256::ZERO),
210                ],
211            ));
212
213        let update = apply(&changes, DownloadedAccount::Present(existing));
214
215        let hashed_address = keccak256(ACCOUNT);
216        assert_eq!(update.state.accounts[&hashed_address].as_ref().unwrap().bytecode_hash, None);
217        assert_eq!(
218            update.state.storages[&hashed_address],
219            HashedStorage::from_iter([(keccak256(B256::from(U256::from(1))), U256::ZERO)])
220        );
221        assert!(update.bytecodes.is_empty());
222    }
223
224    #[test]
225    fn an_account_the_block_empties_is_removed() {
226        let changes = AccountChanges::new(ACCOUNT)
227            .with_balance_change(BalanceChange::new(index(1), U256::from(100)))
228            .with_balance_change(BalanceChange::new(index(2), U256::ZERO));
229
230        let update = apply(&changes, DownloadedAccount::Absent);
231
232        assert_eq!(update.state.accounts[&keccak256(ACCOUNT)], None);
233    }
234
235    // Final state as a flat map: accounts, and non-zero slots by hashed address and slot.
236    type FlatState = (BTreeMap<B256, Account>, BTreeMap<(B256, B256), U256>);
237
238    fn flatten(db: &CacheDB<EmptyDB>) -> FlatState {
239        let mut state = FlatState::default();
240        for (address, account) in &db.cache.accounts {
241            let hashed_address = keccak256(address);
242            state.0.insert(hashed_address, Account::from(&account.info));
243            for (slot, value) in &account.storage {
244                if !value.is_zero() {
245                    state.1.insert((hashed_address, keccak256(B256::from(*slot))), *value);
246                }
247            }
248        }
249        state
250    }
251
252    #[allow(clippy::clone_on_copy)]
253    fn fold(mut state: FlatState, update: &HashedPostState) -> FlatState {
254        for (hashed_address, storage) in &update.storages {
255            for (slot, value) in &storage.storage {
256                if value.is_zero() {
257                    state.1.remove(&(*hashed_address, *slot));
258                } else {
259                    state.1.insert((*hashed_address, *slot), *value);
260                }
261            }
262        }
263        for (hashed_address, account) in &update.accounts {
264            match account {
265                Some(account) => {
266                    state.0.insert(*hashed_address, account.clone());
267                }
268                None => {
269                    state.0.remove(hashed_address);
270                    state.1.retain(|(address, _), _| address != hashed_address);
271                }
272            }
273        }
274        state
275    }
276
277    #[test]
278    fn flat_state_excludes_zero_slots_and_deleted_account_storage() {
279        let mut db = CacheDB::<EmptyDB>::default();
280        for address in [ACCOUNT, SENDER] {
281            db.insert_account_info(address, AccountInfo::from_balance(U256::from(1)));
282            db.insert_account_storage(address, U256::from(1), U256::from(5)).unwrap();
283            db.insert_account_storage(address, U256::from(2), U256::ZERO).unwrap();
284        }
285        let pre = flatten(&db);
286        assert_eq!(pre.1.len(), 2);
287
288        let mut update = HashedPostState::default();
289        update.accounts.insert(keccak256(ACCOUNT), None);
290        let post = fold(pre, &update);
291
292        assert_eq!(
293            post.0,
294            BTreeMap::from([(
295                keccak256(SENDER),
296                Account { balance: U256::from(1), ..Default::default() },
297            )])
298        );
299        assert_eq!(
300            post.1,
301            BTreeMap::from([(
302                (keccak256(SENDER), keccak256(B256::from(U256::from(1)))),
303                U256::from(5)
304            )])
305        );
306    }
307
308    fn insert(db: &mut CacheDB<EmptyDB>, address: Address, nonce: u64, code: Bytes) {
309        let code = Bytecode::new_raw(code);
310        let info = AccountInfo {
311            nonce,
312            code_hash: code.hash_slow(),
313            code: Some(code),
314            ..Default::default()
315        };
316        db.insert_account_info(address, info);
317    }
318
319    fn tx(nonce: u64, to: TxKind, value: u64, input: Bytes) -> Recovered<TransactionSigned> {
320        let tx = Transaction::Legacy(TxLegacy {
321            nonce,
322            gas_price: 1,
323            gas_limit: 1_000_000,
324            to,
325            value: U256::from(value),
326            input,
327            ..Default::default()
328        });
329        Recovered::new_unchecked(
330            TransactionSigned::new_unhashed(tx, Signature::test_signature()),
331            SENDER,
332        )
333    }
334
335    #[test]
336    #[allow(clippy::clone_on_copy)]
337    fn applying_the_list_matches_execution() {
338        let contract = Address::repeat_byte(0xc0);
339        let beneficiary = Address::repeat_byte(0xbe);
340
341        let mut db = CacheDB::<EmptyDB>::new(Default::default());
342        insert(&mut db, BEACON_ROOTS_ADDRESS, 1, BEACON_ROOTS_CODE.clone());
343        insert(&mut db, HISTORY_STORAGE_ADDRESS, 1, HISTORY_STORAGE_CODE.clone());
344        insert(
345            &mut db,
346            WITHDRAWAL_REQUEST_PREDEPLOY_ADDRESS,
347            1,
348            WITHDRAWAL_REQUEST_PREDEPLOY_CODE.clone(),
349        );
350        db.insert_account_info(SENDER, AccountInfo::from_balance(U256::from(u64::MAX)));
351        // Zeroes slot 1, reads slot 3, stores the block number in slot 2 and the call value in 4.
352        insert(&mut db, contract, 1, bytes!("6000600155600354504360025534600455"));
353        db.insert_account_storage(contract, U256::from(1), U256::from(5)).unwrap();
354        db.insert_account_storage(contract, U256::from(3), U256::from(7)).unwrap();
355        let pre = flatten(&db);
356
357        let txs = [
358            // Repeated writes, the second of slots 1 and 2 being no-ops.
359            tx(0, TxKind::Call(contract), 1, Bytes::new()),
360            tx(1, TxKind::Call(contract), 2, Bytes::new()),
361            // Deploys `INVALID` as runtime code.
362            tx(2, TxKind::Create, 0, bytes!("60fe60005360016000f3")),
363            // Funds an address, then creates and destroys a contract there in one transaction.
364            tx(3, TxKind::Call(SENDER.create(4)), 100, Bytes::new()),
365            tx(
366                4,
367                TxKind::Create,
368                0,
369                [&[0x73][..], beneficiary.as_slice(), &[0xff]].concat().into(),
370            ),
371        ];
372        let header = Header {
373            number: 1,
374            timestamp: 1,
375            gas_limit: 30_000_000,
376            parent_beacon_block_root: Some(B256::repeat_byte(1)),
377            excess_blob_gas: Some(0),
378            blob_gas_used: Some(0),
379            block_access_list_hash: Some(B256::ZERO),
380            ..Default::default()
381        };
382        let withdrawal = Withdrawal { address: beneficiary, amount: 1, ..Default::default() };
383        let block = Block {
384            header,
385            body: BlockBody { withdrawals: Some(vec![withdrawal].into()), ..Default::default() },
386        }
387        .seal_slow();
388
389        let evm_config =
390            EthEvmConfig::new(Arc::new(ChainSpecBuilder::mainnet().amsterdam_activated().build()));
391        let mut state =
392            State::builder().with_database(&mut db).with_bundle_update().with_bal_builder().build();
393        {
394            let mut executor = evm_config.executor_for_block(&mut state, &block).unwrap();
395            executor.apply_pre_execution_changes().unwrap();
396            for tx in txs {
397                executor.evm_mut().db_mut().bump_bal_index();
398                executor.execute_transaction(tx).unwrap();
399            }
400            executor.evm_mut().db_mut().bump_bal_index();
401            executor.apply_post_execution_changes().unwrap();
402        }
403        let bal = state.take_built_alloy_bal().unwrap();
404        state.merge_transitions(BundleRetention::PlainState);
405        let bundle = state.take_bundle();
406
407        let update = state_update(
408            &bal,
409            AccountCoverage::COMPLETE,
410            pre.0.iter().map(|(address, account)| (*address, account.clone())),
411        );
412        let executed = HashedPostState::from_bundle_state::<KeccakKeyHasher>(bundle.state());
413
414        let post = fold(pre.clone(), &update.state);
415        assert!(update.unresolved.is_empty());
416        assert_eq!(post, fold(pre, &executed));
417
418        // The block did what the cases need.
419        let slot = |address: Address, slot: u64| {
420            post.1.get(&(keccak256(address), keccak256(B256::from(U256::from(slot)))))
421        };
422        assert_eq!((slot(contract, 1), slot(contract, 4)), (None, Some(&U256::from(2))));
423        assert!(!post.0.contains_key(&keccak256(SENDER.create(4))));
424        assert_eq!(post.0[&keccak256(beneficiary)].balance, U256::from(100 + 1_000_000_000u64));
425        assert!(post.1.keys().any(|(address, _)| *address == keccak256(BEACON_ROOTS_ADDRESS)));
426        assert_eq!(
427            update.bytecodes,
428            B256Map::from_iter([(keccak256([0xfe]), Bytes::from_static(&[0xfe]))])
429        );
430    }
431}
reth_snap_sync/catch_up/apply.rs

reth_snap_sync/catch_up/
apply.rs
