reth_engine_tree/tree/payload_processor/
bal.rs

1//! BAL (Block Access List, EIP-7928) related functionality.
2
3use crate::tree::cached_state::CachedStateProvider;
4use alloy_consensus::constants::KECCAK_EMPTY;
5use alloy_eip7928::BlockAccessList;
6use alloy_primitives::{keccak256, Address, StorageKey, U256};
7use reth_primitives_traits::Account;
8use reth_provider::{AccountReader, ProviderError};
9use reth_trie::{HashedPostState, HashedStorage};
10use std::ops::Range;
11
12/// Returns the total number of storage slots (both changed and read-only) across all accounts in
13/// the BAL.
14pub fn total_slots(bal: &BlockAccessList) -> usize {
15    bal.iter().map(|account| account.storage_changes.len() + account.storage_reads.len()).sum()
16}
17
18/// Iterator over storage slots in a [`BlockAccessList`], with range-based filtering.
19///
20/// Iterates over all `(Address, StorageKey)` pairs representing both changed and read-only
21/// storage slots across all accounts in the BAL. For each account, changed slots are iterated
22/// first, followed by read-only slots. The iterator intelligently skips accounts and slots
23/// outside the specified range for efficient traversal.
24#[derive(Debug)]
25pub(crate) struct BALSlotIter<'a> {
26    bal: &'a BlockAccessList,
27    range: Range<usize>,
28    current_index: usize,
29    account_idx: usize,
30    /// Index within the current account's combined slots (changed + read-only).
31    /// If `slot_idx < storage_changes.len()`, we're in changed slots.
32    /// Otherwise, we're in read-only slots at index `slot_idx - storage_changes.len()`.
33    slot_idx: usize,
34}
35
36impl<'a> BALSlotIter<'a> {
37    /// Creates a new iterator over storage slots within the specified range.
38    pub(crate) fn new(bal: &'a BlockAccessList, range: Range<usize>) -> Self {
39        let mut iter = Self { bal, range, current_index: 0, account_idx: 0, slot_idx: 0 };
40        iter.skip_to_range_start();
41        iter
42    }
43
44    /// Skips to the first item within the range.
45    fn skip_to_range_start(&mut self) {
46        while self.account_idx < self.bal.len() {
47            let account = &self.bal[self.account_idx];
48            let slots_in_account = account.storage_changes.len() + account.storage_reads.len();
49
50            // Check if this account contains items in our range
51            let account_end = self.current_index + slots_in_account;
52
53            if account_end <= self.range.start {
54                // Entire account is before range, skip it
55                self.current_index = account_end;
56                self.account_idx += 1;
57                self.slot_idx = 0;
58            } else if self.current_index < self.range.start {
59                // Range starts somewhere in this account
60                let skip_slots = self.range.start - self.current_index;
61                self.slot_idx = skip_slots;
62                self.current_index = self.range.start;
63                break;
64            } else {
65                // We're at or past range start
66                break;
67            }
68        }
69    }
70}
71
72impl<'a> Iterator for BALSlotIter<'a> {
73    type Item = (Address, StorageKey);
74
75    fn next(&mut self) -> Option<Self::Item> {
76        // Check if we've exceeded the range
77        if self.current_index >= self.range.end {
78            return None;
79        }
80
81        // Find the next valid slot
82        while self.account_idx < self.bal.len() {
83            let account = &self.bal[self.account_idx];
84            let changed_len = account.storage_changes.len();
85            let total_len = changed_len + account.storage_reads.len();
86
87            if self.slot_idx < total_len {
88                let address = account.address;
89                let slot = if self.slot_idx < changed_len {
90                    // We're in changed slots
91                    account.storage_changes[self.slot_idx].slot
92                } else {
93                    // We're in read-only slots
94                    account.storage_reads[self.slot_idx - changed_len]
95                };
96
97                self.slot_idx += 1;
98                self.current_index += 1;
99
100                // Check if we've reached the end of range
101                if self.current_index > self.range.end {
102                    return None;
103                }
104
105                return Some((address, slot));
106            }
107
108            // Move to next account
109            self.account_idx += 1;
110            self.slot_idx = 0;
111        }
112
113        None
114    }
115}
116
117/// Converts a Block Access List into a [`HashedPostState`] by extracting the final state
118/// of modified accounts and storage slots.
119pub(crate) fn bal_to_hashed_post_state<P>(
120    bal: &BlockAccessList,
121    provider: &CachedStateProvider<P>,
122) -> Result<HashedPostState, ProviderError>
123where
124    P: AccountReader,
125{
126    let mut hashed_state = HashedPostState::with_capacity(bal.len());
127
128    for account_changes in bal {
129        let address = account_changes.address;
130
131        // Always fetch the account; even if we don't need the db account to construct the final
132        // `Account`, doing this fills the cache.
133        let existing_account = provider.basic_account(&address)?;
134
135        // Get the latest balance (last balance change if any)
136        let balance = account_changes.balance_changes.last().map(|change| change.post_balance);
137
138        // Get the latest nonce (last nonce change if any)
139        let nonce = account_changes.nonce_changes.last().map(|change| change.new_nonce);
140
141        // Get the latest code (last code change if any)
142        let code_hash = if let Some(code_change) = account_changes.code_changes.last() {
143            if code_change.new_code.is_empty() {
144                Some(Some(KECCAK_EMPTY))
145            } else {
146                Some(Some(keccak256(&code_change.new_code)))
147            }
148        } else {
149            None
150        };
151
152        // If the account was only read then don't add it to the HashedPostState
153        if balance.is_none() &&
154            nonce.is_none() &&
155            code_hash.is_none() &&
156            account_changes.storage_changes.is_empty()
157        {
158            continue
159        }
160
161        // Build the final account state
162        let account = Account {
163            balance: balance.unwrap_or_else(|| {
164                existing_account.as_ref().map(|acc| acc.balance).unwrap_or(U256::ZERO)
165            }),
166            nonce: nonce
167                .unwrap_or_else(|| existing_account.as_ref().map(|acc| acc.nonce).unwrap_or(0)),
168            bytecode_hash: code_hash.unwrap_or_else(|| {
169                existing_account.as_ref().and_then(|acc| acc.bytecode_hash).or(Some(KECCAK_EMPTY))
170            }),
171        };
172
173        let hashed_address = keccak256(address);
174        hashed_state.accounts.insert(hashed_address, Some(account));
175
176        // Process storage changes
177        if !account_changes.storage_changes.is_empty() {
178            let mut storage_map = HashedStorage::new(false);
179
180            for slot_changes in &account_changes.storage_changes {
181                let hashed_slot = keccak256(slot_changes.slot);
182
183                // Get the last change for this slot
184                if let Some(last_change) = slot_changes.changes.last() {
185                    storage_map
186                        .storage
187                        .insert(hashed_slot, U256::from_be_bytes(last_change.new_value.0));
188                }
189            }
190
191            hashed_state.storages.insert(hashed_address, storage_map);
192        }
193    }
194
195    Ok(hashed_state)
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201    use crate::tree::cached_state::{ExecutionCache, ExecutionCacheBuilder};
202    use alloy_eip7928::{
203        AccountChanges, BalanceChange, CodeChange, NonceChange, SlotChanges, StorageChange,
204    };
205    use alloy_primitives::{Address, Bytes, StorageKey, B256};
206    use reth_revm::test_utils::StateProviderTest;
207
208    fn new_cache() -> ExecutionCache {
209        ExecutionCacheBuilder::default().build_caches(1000)
210    }
211
212    #[test]
213    fn test_bal_to_hashed_post_state_basic() {
214        let provider = StateProviderTest::default();
215
216        let address = Address::random();
217        let account_changes = AccountChanges {
218            address,
219            storage_changes: vec![],
220            storage_reads: vec![],
221            balance_changes: vec![BalanceChange::new(0, U256::from(100))],
222            nonce_changes: vec![NonceChange::new(0, 1)],
223            code_changes: vec![],
224        };
225
226        let bal = vec![account_changes];
227        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
228        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
229
230        assert_eq!(result.accounts.len(), 1);
231
232        let hashed_address = keccak256(address);
233        let account_opt = result.accounts.get(&hashed_address).unwrap();
234        assert!(account_opt.is_some());
235
236        let account = account_opt.as_ref().unwrap();
237        assert_eq!(account.balance, U256::from(100));
238        assert_eq!(account.nonce, 1);
239        assert_eq!(account.bytecode_hash, Some(KECCAK_EMPTY));
240    }
241
242    #[test]
243    fn test_bal_with_storage_changes() {
244        let provider = StateProviderTest::default();
245
246        let address = Address::random();
247        let slot = StorageKey::random();
248        let value = B256::random();
249
250        let slot_changes = SlotChanges { slot, changes: vec![StorageChange::new(0, value)] };
251
252        let account_changes = AccountChanges {
253            address,
254            storage_changes: vec![slot_changes],
255            storage_reads: vec![],
256            balance_changes: vec![BalanceChange::new(0, U256::from(500))],
257            nonce_changes: vec![NonceChange::new(0, 2)],
258            code_changes: vec![],
259        };
260
261        let bal = vec![account_changes];
262        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
263        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
264
265        let hashed_address = keccak256(address);
266        assert!(result.storages.contains_key(&hashed_address));
267
268        let storage = result.storages.get(&hashed_address).unwrap();
269        let hashed_slot = keccak256(slot);
270
271        let stored_value = storage.storage.get(&hashed_slot).unwrap();
272        assert_eq!(*stored_value, U256::from_be_bytes(value.0));
273    }
274
275    #[test]
276    fn test_bal_with_code_change() {
277        let provider = StateProviderTest::default();
278
279        let address = Address::random();
280        let code = Bytes::from(vec![0x60, 0x80, 0x60, 0x40]); // Some bytecode
281
282        let account_changes = AccountChanges {
283            address,
284            storage_changes: vec![],
285            storage_reads: vec![],
286            balance_changes: vec![BalanceChange::new(0, U256::from(1000))],
287            nonce_changes: vec![NonceChange::new(0, 1)],
288            code_changes: vec![CodeChange::new(0, code.clone())],
289        };
290
291        let bal = vec![account_changes];
292        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
293        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
294
295        let hashed_address = keccak256(address);
296        let account_opt = result.accounts.get(&hashed_address).unwrap();
297        let account = account_opt.as_ref().unwrap();
298
299        let expected_code_hash = keccak256(&code);
300        assert_eq!(account.bytecode_hash, Some(expected_code_hash));
301    }
302
303    #[test]
304    fn test_bal_with_empty_code() {
305        let provider = StateProviderTest::default();
306
307        let address = Address::random();
308        let empty_code = Bytes::default();
309
310        let account_changes = AccountChanges {
311            address,
312            storage_changes: vec![],
313            storage_reads: vec![],
314            balance_changes: vec![BalanceChange::new(0, U256::from(1000))],
315            nonce_changes: vec![NonceChange::new(0, 1)],
316            code_changes: vec![CodeChange::new(0, empty_code)],
317        };
318
319        let bal = vec![account_changes];
320        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
321        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
322
323        let hashed_address = keccak256(address);
324        let account_opt = result.accounts.get(&hashed_address).unwrap();
325        let account = account_opt.as_ref().unwrap();
326
327        assert_eq!(account.bytecode_hash, Some(KECCAK_EMPTY));
328    }
329
330    #[test]
331    fn test_bal_multiple_changes_takes_last() {
332        let provider = StateProviderTest::default();
333
334        let address = Address::random();
335
336        // Multiple balance changes - should take the last one
337        let account_changes = AccountChanges {
338            address,
339            storage_changes: vec![],
340            storage_reads: vec![],
341            balance_changes: vec![
342                BalanceChange::new(0, U256::from(100)),
343                BalanceChange::new(1, U256::from(200)),
344                BalanceChange::new(2, U256::from(300)),
345            ],
346            nonce_changes: vec![
347                NonceChange::new(0, 1),
348                NonceChange::new(1, 2),
349                NonceChange::new(2, 3),
350            ],
351            code_changes: vec![],
352        };
353
354        let bal = vec![account_changes];
355        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
356        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
357
358        let hashed_address = keccak256(address);
359        let account_opt = result.accounts.get(&hashed_address).unwrap();
360        let account = account_opt.as_ref().unwrap();
361
362        // Should have the last values
363        assert_eq!(account.balance, U256::from(300));
364        assert_eq!(account.nonce, 3);
365    }
366
367    #[test]
368    fn test_bal_uses_provider_for_missing_fields() {
369        let mut provider = StateProviderTest::default();
370
371        let address = Address::random();
372        let code_hash = B256::random();
373        let existing_account =
374            Account { balance: U256::from(999), nonce: 42, bytecode_hash: Some(code_hash) };
375        provider.insert_account(address, existing_account, None, Default::default());
376
377        // Only change balance, nonce and code should come from provider
378        let account_changes = AccountChanges {
379            address,
380            storage_changes: vec![],
381            storage_reads: vec![],
382            balance_changes: vec![BalanceChange::new(0, U256::from(1500))],
383            nonce_changes: vec![],
384            code_changes: vec![],
385        };
386
387        let bal = vec![account_changes];
388        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
389        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
390
391        let hashed_address = keccak256(address);
392        let account_opt = result.accounts.get(&hashed_address).unwrap();
393        let account = account_opt.as_ref().unwrap();
394
395        // Balance should be updated
396        assert_eq!(account.balance, U256::from(1500));
397        // Nonce and bytecode_hash should come from provider
398        assert_eq!(account.nonce, 42);
399        assert_eq!(account.bytecode_hash, Some(code_hash));
400    }
401
402    #[test]
403    fn test_bal_multiple_storage_changes_per_slot() {
404        let provider = StateProviderTest::default();
405
406        let address = Address::random();
407        let slot = StorageKey::random();
408
409        // Multiple changes to the same slot - should take the last one
410        let slot_changes = SlotChanges {
411            slot,
412            changes: vec![
413                StorageChange::new(0, B256::from(U256::from(100).to_be_bytes::<32>())),
414                StorageChange::new(1, B256::from(U256::from(200).to_be_bytes::<32>())),
415                StorageChange::new(2, B256::from(U256::from(300).to_be_bytes::<32>())),
416            ],
417        };
418
419        let account_changes = AccountChanges {
420            address,
421            storage_changes: vec![slot_changes],
422            storage_reads: vec![],
423            balance_changes: vec![BalanceChange::new(0, U256::from(100))],
424            nonce_changes: vec![NonceChange::new(0, 1)],
425            code_changes: vec![],
426        };
427
428        let bal = vec![account_changes];
429        let provider = CachedStateProvider::new(provider, new_cache(), Default::default());
430        let result = bal_to_hashed_post_state(&bal, &provider).unwrap();
431
432        let hashed_address = keccak256(address);
433        let storage = result.storages.get(&hashed_address).unwrap();
434        let hashed_slot = keccak256(slot);
435
436        let stored_value = storage.storage.get(&hashed_slot).unwrap();
437
438        // Should have the last value
439        assert_eq!(*stored_value, U256::from(300));
440    }
441
442    #[test]
443    fn test_bal_slot_iter() {
444        // Create test data with multiple accounts and slots (both changed and read-only)
445        let addr1 = Address::repeat_byte(0x01);
446        let addr2 = Address::repeat_byte(0x02);
447        let addr3 = Address::repeat_byte(0x03);
448
449        // Account 1: 2 changed slots + 1 read-only = 3 total slots (indices 0, 1, 2)
450        let account1 = AccountChanges {
451            address: addr1,
452            storage_changes: vec![
453                SlotChanges {
454                    slot: StorageKey::from(U256::from(100)),
455                    changes: vec![StorageChange::new(0, B256::ZERO)],
456                },
457                SlotChanges {
458                    slot: StorageKey::from(U256::from(101)),
459                    changes: vec![StorageChange::new(0, B256::ZERO)],
460                },
461            ],
462            storage_reads: vec![StorageKey::from(U256::from(102))],
463            balance_changes: vec![],
464            nonce_changes: vec![],
465            code_changes: vec![],
466        };
467
468        // Account 2: 1 changed slot + 1 read-only = 2 total slots (indices 3, 4)
469        let account2 = AccountChanges {
470            address: addr2,
471            storage_changes: vec![SlotChanges {
472                slot: StorageKey::from(U256::from(200)),
473                changes: vec![StorageChange::new(0, B256::ZERO)],
474            }],
475            storage_reads: vec![StorageKey::from(U256::from(201))],
476            balance_changes: vec![],
477            nonce_changes: vec![],
478            code_changes: vec![],
479        };
480
481        // Account 3: 2 changed slots + 1 read-only = 3 total slots (indices 5, 6, 7)
482        let account3 = AccountChanges {
483            address: addr3,
484            storage_changes: vec![
485                SlotChanges {
486                    slot: StorageKey::from(U256::from(300)),
487                    changes: vec![StorageChange::new(0, B256::ZERO)],
488                },
489                SlotChanges {
490                    slot: StorageKey::from(U256::from(301)),
491                    changes: vec![StorageChange::new(0, B256::ZERO)],
492                },
493            ],
494            storage_reads: vec![StorageKey::from(U256::from(302))],
495            balance_changes: vec![],
496            nonce_changes: vec![],
497            code_changes: vec![],
498        };
499
500        let bal = vec![account1, account2, account3];
501
502        // Test 1: Iterate over all slots (range 0..8)
503        let items: Vec<_> = BALSlotIter::new(&bal, 0..8).collect();
504        assert_eq!(items.len(), 8);
505        // Account 1: changed slots first (100, 101), then read-only (102)
506        assert_eq!(items[0], (addr1, StorageKey::from(U256::from(100))));
507        assert_eq!(items[1], (addr1, StorageKey::from(U256::from(101))));
508        assert_eq!(items[2], (addr1, StorageKey::from(U256::from(102))));
509        // Account 2: changed slot (200), then read-only (201)
510        assert_eq!(items[3], (addr2, StorageKey::from(U256::from(200))));
511        assert_eq!(items[4], (addr2, StorageKey::from(U256::from(201))));
512        // Account 3: changed slots (300, 301), then read-only (302)
513        assert_eq!(items[5], (addr3, StorageKey::from(U256::from(300))));
514        assert_eq!(items[6], (addr3, StorageKey::from(U256::from(301))));
515        assert_eq!(items[7], (addr3, StorageKey::from(U256::from(302))));
516
517        // Test 2: Range that skips first account (range 3..6)
518        let items: Vec<_> = BALSlotIter::new(&bal, 3..6).collect();
519        assert_eq!(items.len(), 3);
520        assert_eq!(items[0], (addr2, StorageKey::from(U256::from(200))));
521        assert_eq!(items[1], (addr2, StorageKey::from(U256::from(201))));
522        assert_eq!(items[2], (addr3, StorageKey::from(U256::from(300))));
523
524        // Test 3: Range within first account (range 1..2)
525        let items: Vec<_> = BALSlotIter::new(&bal, 1..2).collect();
526        assert_eq!(items.len(), 1);
527        assert_eq!(items[0], (addr1, StorageKey::from(U256::from(101))));
528
529        // Test 4: Range spanning multiple accounts (range 2..5)
530        let items: Vec<_> = BALSlotIter::new(&bal, 2..5).collect();
531        assert_eq!(items.len(), 3);
532        // Last slot from account 1 (read-only)
533        assert_eq!(items[0], (addr1, StorageKey::from(U256::from(102))));
534        // Account 2 (changed + read-only)
535        assert_eq!(items[1], (addr2, StorageKey::from(U256::from(200))));
536        assert_eq!(items[2], (addr2, StorageKey::from(U256::from(201))));
537
538        // Test 5: Empty range
539        let items: Vec<_> = BALSlotIter::new(&bal, 5..5).collect();
540        assert_eq!(items.len(), 0);
541
542        // Test 6: Range beyond end (starts at index 6)
543        let items: Vec<_> = BALSlotIter::new(&bal, 6..100).collect();
544        assert_eq!(items.len(), 2);
545        assert_eq!(items[0], (addr3, StorageKey::from(U256::from(301))));
546        assert_eq!(items[1], (addr3, StorageKey::from(U256::from(302))));
547
548        // Test 7: Range that starts in read-only slots (index 2 is the read-only slot of account 1)
549        let items: Vec<_> = BALSlotIter::new(&bal, 2..4).collect();
550        assert_eq!(items.len(), 2);
551        assert_eq!(items[0], (addr1, StorageKey::from(U256::from(102))));
552        assert_eq!(items[1], (addr2, StorageKey::from(U256::from(200))));
553    }
554}
reth_engine_tree/tree/payload_processor/bal.rs

reth_engine_tree/tree/payload_processor/
bal.rs
