## 4 Probabilistic Model for Path Length Distribution  
A general design considers addresses in Ethereum to be a 20-byte (160-bit) identifier conventionally represented in an address by a 40-character-long hexadecimal string. So, by using the nodes that each represent a nibble-4-bit fraction of this address, some mapping or connection of these addresses can be seen through a whole series of such nodes toward the state data across this MPT structure [3]. The number of nodes from the root to the given leaf representing an address path length could be defined in this. Figure 1 presents a simplified representation of this structure, using a quaternary (4-ary) branching pattern for clarity, as opposed to the hexadecimal (16-ary) branching used in Ethereum. This visualization illustrates the key concepts of path compression and hierarchical storage that make Merkle Patricia Tries efficient for managing large state spaces. Each level in the tree corresponds to a part of the Ethereum address, with leaf nodes at the bottom representing full addresses or account states. This structure allows for efficient insertions, lookups, and proof generation, which are critical for Ethereum's performance and scalability. Let \(T\) be a Merkle Patricia Trie and \(a\) be a key (address) stored in \(T\). The path length \(PL(a,T)\) is formally defined as follows:  
\[PL(a,T)=|n_{i}:n_{i}\in Path(root_{T},leaf_{a})|,\]  
where \(Path(root_{T},leaf_{a})\) is the set of nodes in the path from root to leaf. For a trie containing \(N\) random addresses, we derive the probability of a specific path length \(k\) by analyzing the conditions that create paths of length \(k\). The key insight is that path length is determined by the longest common prefix shared with other addresses in the trie. Let \(T\) be a Merkle Patricia Trie containing \(N\) randomly generated Ethereum addresses. We aim to determine \(P(PL(k,T)=k)\), the probability that a randomly chosen key \(k\) in \(T\) has a path length of exactly \(k\). This event can be decomposed into two sub-events:  
1. Event A: The first \(k-1\) symbols of the key match with at least one other key in the trie;
2. Event B: The \(k\)-th symbol of the key does not match with any other key that shared the first \(k-1\) symbols. Thus, we can express our target probability as follows:  
\[P(PL(k,T)=k)=P(A\cap B).\]  
Figure 1: Simplified hierarchical structure of a Merkle Patricia Trie. To calculate this probability, we utilize the concept of complementary events:  
1. Let \(E_{k-1}\) be the event that the first \(k-1\) symbols match with at least one other key;
2. Let \(E_{k}\) be the event that the first \(k\) symbols match with at least one other key. We can then express our target probability as the difference between these two events: \[P(PL(k,T)=k)=P(E_{k-1})-P(E_{k})\]  
For a given prefix length \(k\), the probability that it matches with no other key is as follows:  
\[P(\text{no match in first $k$ symbols})=\left(1-\left(\frac{1}{16}\right)^{k} \cdot\frac{15}{16}\right)^{N}.\]  
Therefore:  
\[P(E_{k})=1-\left(1-\left(\frac{1}{16}\right)^{k}\cdot\frac{15}{16}\right)^{N}.\]  
Combining these elements, we obtain the complete path length distribution:  
\[P(PL(a,T)=k)=\left(1-\left(\frac{1}{16}\right)^{k}\cdot\frac{15}{16}\right)^{ N}-\left(1-\left(\frac{1}{16}\right)^{k-1}\cdot\frac{15}{16}\right)^{N}. \tag{1}\]  
This formula is valid for \(2\leq k\leq 41\), where 41 represents the maximum possible path length for Ethereum addresses (40 nibbles plus root node). The expected path length \(E[PL]\) for a trie with \(N\) addresses is as follows:  
\[E[PL]=\sum_{k=2}^{41}k\cdot P(PL=k). \tag{2}\]  
This sum can be approximated for large \(N\) as:  
\[E[PL]\approx 0.36\ln(N)+c, \tag{3}\]  
where \(c\) is a small constant (\(\approx 0.696\)) representing the overhead from the trie structure.