reth_engine_tree/tree/payload_processor/
bal.rs

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

reth_engine_tree/tree/payload_processor/
bal.rs
