## 3 Background: Merkle Patricia Tries in Ethereum State Management
### State Management in Ethereum  
State management in Ethereum represents a fundamental challenge in blockchain technology [24; 25]. The system must maintain a mapping \(\sigma:A\to S\) where \(A\) is the set of 160-bit addresses and \(S\) represents account states. Each state \(s\in S\) contains a tuple \((n,b,h,c)\) representing the account's nonce, balance, storage root, and code hash, respectively [26; 27]. The Modified Merkle Patricia Trie (MPT) in Ethereum combines cryptographic verification with efficient key-value storage. For an address \(a\in A\), each nibble (4 bits) of \(a\) determines a path through the trie. Formally, a path \(P(a)\) is a sequence of nodes:  
\[P(a)=(n_{0},n_{1},\ldots,n_{k}),\]  
where \(n_{0}\) is the root node and \(n_{k}\) contains the state data. Each non-leaf node \(n_{i}\) contains up to 16 children, corresponding to possible nibble values. The node structure ensures the following:  
\[H(n_{i})=hash(H(c):c\in children(n_{i}))\]  
where \(H(n)\) represents the node's hash and \(children(n)\) denotes its set of child nodes. Three types of nodes exist in the trie:  
1. Branch nodes: \(n_{branch}=(c_{0},\ldots,c_{15},v)\) where \(c_{i}\) are child references and \(v\) is an optional value;
2. Extension nodes: \(n_{ext}=(path,next)\) encoding shared path segments;
3. Leaf nodes: \(n_{leaf}=(path,value)\) containing actual state data. The path length \(PL(a)\) for an address \(a\) is defined as follows: \[PL(a)= |n_{i}:n_{i}\in P(a)|.\] This directly impacts proof sizes as each node in the path must be included in state verification proofs. The scaling storage requirements directly impact Ethereum's operational costs and efficiency. With the current state size exceeding 200 million addresses and growing, this scaling behavior leads to significant practical implications. For example, with an average path length of 7.72 nodes at the current scale (\(3\times 10^{8}\) addresses), each new address requires storing approximately eight nodes worth of data, contributing to the state bloat challenge highlighted by Ethereum's core developers. [PERSON] has highlighted that current MPT implementations can produce proofs up to 300 MB in worst cases [4]. For a stateless client verifying block \(B\), the total proof size \(S(B)\) is as follows:  
\[S(B)=\sum_{tx\in B}\sum_{a\in Access(tx)}|P(a)|\cdot NodeSize,\]  
where \(Access(tx)\) represents addresses accessed by transaction \(tx\). The dynamic nature of Ethereum's state presents additional challenges for our model. During periods of high transaction volume, certain DeFi protocols or trending applications can create temporary \"hot spots\" in the state tree, where specific address clusters experience intensified activity. Our analysis shows that these dynamic patterns affect path length distributions in two ways:  
1. Short-term fluctuations: High-frequency trading or viral DeFi applications can temporarily skew access patterns, leading to localized optimization opportunities. Our adaptive approach can accommodate these changes through periodic restructuring, maintaining efficiency even during volatile periods;  
2. Long-term evolution: The gradual accumulation of state changes and new addresses leads to organic growth in the trie structure. The logarithmic nature of our path length scaling ensures that the system remains efficient even as the state size increases, with restructuring costs growing sub-linearly with the number of addresses. Our empirical analysis of Ethereum mainnet data shows that while short-term volatility can cause temporary deviations of \(\pm 5\%\) in path length distributions, the overall structural properties remain stable over longer timeframes, validating the robustness of our probabilistic model. Our research provides the first precise characterization of path length distributions. For a trie containing \(N\) addresses, we prove that path lengths follow the distribution: \(P(PL=k)\). This formula enables accurate prediction of proof sizes and guides optimization strategies for state management.