evm_fork_cache/
access_set.rs

1//! Compact account/storage touch sets captured from EVM execution.
2//!
3//! This is intentionally smaller than an EIP-2930 transaction access list:
4//! it keeps accounts and `(account, slot)` pairs as sets so callers can merge
5//! simulation traces, estimate EIP-2929 warm-access savings, and prefetch cache
6//! entries without committing to a transaction encoding.
7
8use std::collections::HashSet;
9
10use alloy_eips::eip2930::{AccessList, AccessListItem};
11use alloy_primitives::{Address, B256, U256};
12use serde::{Deserialize, Serialize};
13
14/// Accounts and storage slots touched during EVM execution.
15///
16/// The shape is optimized for simulation bookkeeping: set union, overlap
17/// checks, warm-access gas estimation, and storage prefetching.
18#[derive(Clone, Debug, Default, Serialize, Deserialize)]
19pub struct StorageAccessList {
20    /// Contract addresses touched during execution.
21    pub accounts: HashSet<Address>,
22    /// Runtime-code hashes requested during execution.
23    #[serde(default)]
24    pub code_hashes: HashSet<B256>,
25    /// `(contract, slot)` pairs read or written during execution.
26    pub slots: HashSet<(Address, U256)>,
27    /// Historical block numbers requested through the `BLOCKHASH` opcode.
28    #[serde(default)]
29    pub block_numbers: HashSet<u64>,
30}
31
32impl StorageAccessList {
33    /// Returns true when no accounts or storage slots were captured.
34    pub fn is_empty(&self) -> bool {
35        self.accounts.is_empty()
36            && self.code_hashes.is_empty()
37            && self.slots.is_empty()
38            && self.block_numbers.is_empty()
39    }
40
41    /// Number of distinct accounts touched by the execution.
42    pub fn account_count(&self) -> usize {
43        self.accounts.len()
44    }
45
46    /// Number of distinct storage slots touched by the execution.
47    pub fn slot_count(&self) -> usize {
48        self.slots.len()
49    }
50
51    /// Number of distinct runtime-code hashes touched by the execution.
52    pub fn code_hash_count(&self) -> usize {
53        self.code_hashes.len()
54    }
55
56    /// Number of distinct historical block hashes touched by the execution.
57    pub fn block_hash_count(&self) -> usize {
58        self.block_numbers.len()
59    }
60
61    /// Merge another touch set into this one (set union of accounts and slots).
62    ///
63    /// Duplicate accounts and `(account, slot)` pairs already present are not
64    /// counted twice, so [`StorageAccessList::account_count`] and
65    /// [`StorageAccessList::slot_count`] reflect distinct entries after merging.
66    ///
67    /// # Examples
68    ///
69    /// ```
70    /// use evm_fork_cache::StorageAccessList;
71    /// use alloy_primitives::{Address, U256};
72    ///
73    /// let acct_a = Address::repeat_byte(0x01);
74    /// let acct_b = Address::repeat_byte(0x02);
75    ///
76    /// let mut base = StorageAccessList::default();
77    /// base.accounts.insert(acct_a);
78    /// base.slots.insert((acct_a, U256::from(1)));
79    ///
80    /// let mut other = StorageAccessList::default();
81    /// other.accounts.insert(acct_a); // overlaps `base`, not double-counted
82    /// other.accounts.insert(acct_b);
83    /// other.slots.insert((acct_b, U256::from(2)));
84    ///
85    /// base.extend(&other);
86    ///
87    /// assert_eq!(base.account_count(), 2);
88    /// assert_eq!(base.slot_count(), 2);
89    /// assert!(!base.is_empty());
90    /// ```
91    pub fn extend(&mut self, other: &Self) {
92        self.accounts.extend(&other.accounts);
93        self.code_hashes.extend(&other.code_hashes);
94        self.slots.extend(&other.slots);
95        self.block_numbers.extend(&other.block_numbers);
96    }
97
98    /// Return the subset of this required read set absent from `available`.
99    pub fn missing_from(&self, available: &Self) -> Self {
100        Self {
101            accounts: self
102                .accounts
103                .difference(&available.accounts)
104                .copied()
105                .collect(),
106            code_hashes: self
107                .code_hashes
108                .difference(&available.code_hashes)
109                .copied()
110                .collect(),
111            slots: self.slots.difference(&available.slots).copied().collect(),
112            block_numbers: self
113                .block_numbers
114                .difference(&available.block_numbers)
115                .copied()
116                .collect(),
117        }
118    }
119
120    /// Whether every account and slot in this read set is present in
121    /// `available`.
122    pub fn is_covered_by(&self, available: &Self) -> bool {
123        self.accounts.is_subset(&available.accounts)
124            && self.code_hashes.is_subset(&available.code_hashes)
125            && self.slots.is_subset(&available.slots)
126            && self.block_numbers.is_subset(&available.block_numbers)
127    }
128
129    /// Compute EIP-2929 gas saved when this touch set runs after `warm`.
130    ///
131    /// Cold account access costs 2600 gas versus 100 gas when warm, saving
132    /// 2500 gas. Cold SLOAD costs 2100 gas versus 100 gas when warm, saving
133    /// 2000 gas.
134    pub fn marginal_gas_savings(&self, warm: &Self) -> u64 {
135        let shared_accounts = self.accounts.intersection(&warm.accounts).count() as u64;
136        let shared_slots = self.slots.intersection(&warm.slots).count() as u64;
137        shared_accounts * 2500 + shared_slots * 2000
138    }
139
140    /// Convert this touch set into an EIP-2930 transaction access list.
141    pub fn to_eip2930(&self) -> AccessList {
142        let mut by_address: std::collections::BTreeMap<Address, Vec<B256>> = self
143            .accounts
144            .iter()
145            .copied()
146            .map(|addr| (addr, Vec::new()))
147            .collect();
148
149        for (address, slot) in &self.slots {
150            by_address
151                .entry(*address)
152                .or_default()
153                .push(B256::from(*slot));
154        }
155
156        AccessList(
157            by_address
158                .into_iter()
159                .map(|(address, mut storage_keys)| {
160                    storage_keys.sort_unstable();
161                    storage_keys.dedup();
162                    AccessListItem {
163                        address,
164                        storage_keys,
165                    }
166                })
167                .collect(),
168        )
169    }
170}
171
172impl From<&StorageAccessList> for AccessList {
173    fn from(value: &StorageAccessList) -> Self {
174        value.to_eip2930()
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181
182    #[test]
183    fn marginal_gas_savings_counts_only_overlap() {
184        let account_a = Address::repeat_byte(0x01);
185        let account_b = Address::repeat_byte(0x02);
186        let slot_1 = U256::from(1);
187        let slot_2 = U256::from(2);
188
189        let al = StorageAccessList {
190            accounts: [account_a, account_b].into_iter().collect(),
191            slots: [(account_a, slot_1), (account_b, slot_2)]
192                .into_iter()
193                .collect(),
194            ..Default::default()
195        };
196        let warm = StorageAccessList {
197            accounts: [account_a].into_iter().collect(),
198            slots: [(account_b, slot_2)].into_iter().collect(),
199            ..Default::default()
200        };
201
202        assert_eq!(al.marginal_gas_savings(&warm), 4500);
203    }
204
205    #[test]
206    fn eip2930_conversion_includes_address_only_entries() {
207        let account = Address::repeat_byte(0x01);
208        let storage_contract = Address::repeat_byte(0x02);
209        let mut al = StorageAccessList::default();
210        al.accounts.insert(account);
211        al.slots.insert((storage_contract, U256::from(4)));
212
213        let encoded = al.to_eip2930();
214
215        assert_eq!(encoded.0.len(), 2);
216        assert!(
217            encoded
218                .0
219                .iter()
220                .any(|item| item.address == account && item.storage_keys.is_empty())
221        );
222        assert!(encoded.0.iter().any(|item| item.address == storage_contract
223            && item.storage_keys == vec![B256::from(U256::from(4))]));
224    }
225
226    #[test]
227    fn missing_from_returns_only_unwarmed_accounts_and_slots() {
228        let warm_account = Address::repeat_byte(0x01);
229        let cold_account = Address::repeat_byte(0x02);
230        let warm_slot = (warm_account, U256::from(1));
231        let cold_slot = (cold_account, U256::from(2));
232        let required = StorageAccessList {
233            accounts: [warm_account, cold_account].into_iter().collect(),
234            slots: [warm_slot, cold_slot].into_iter().collect(),
235            ..Default::default()
236        };
237        let available = StorageAccessList {
238            accounts: [warm_account].into_iter().collect(),
239            slots: [warm_slot].into_iter().collect(),
240            ..Default::default()
241        };
242
243        let missing = required.missing_from(&available);
244
245        assert_eq!(missing.accounts, [cold_account].into_iter().collect());
246        assert_eq!(missing.slots, [cold_slot].into_iter().collect());
247        assert!(!required.is_covered_by(&available));
248        assert!(available.is_covered_by(&required));
249    }
250
251    #[test]
252    fn missing_from_includes_code_and_block_hash_dependencies() {
253        let warm_code = B256::repeat_byte(0x11);
254        let cold_code = B256::repeat_byte(0x22);
255        let required = StorageAccessList {
256            code_hashes: [warm_code, cold_code].into_iter().collect(),
257            block_numbers: [90, 91].into_iter().collect(),
258            ..Default::default()
259        };
260        let available = StorageAccessList {
261            code_hashes: [warm_code].into_iter().collect(),
262            block_numbers: [90].into_iter().collect(),
263            ..Default::default()
264        };
265
266        let missing = required.missing_from(&available);
267
268        assert_eq!(missing.code_hashes, [cold_code].into_iter().collect());
269        assert_eq!(missing.block_numbers, [91].into_iter().collect());
270        assert!(!required.is_covered_by(&available));
271    }
272}
evm_fork_cache/access_set.rs

evm_fork_cache/
access_set.rs
