## 8 Average Path Length Scaling  
Our experiments conclusively demonstrate that the average path length in Merkle Patricia Tries follows a logarithmic scaling law with respect to the number of addresses. Figure 3 presents this relationship across six orders of magnitude from \(10^{2}\) to \(3\times 10^{8}\) addresses.  
The empirical results fit the theoretical prediction with exceptional accuracy:  
\[E[PL]\approx 0.36\ln(N)+0.696,\]  
\begin{table}
\begin{tabular}{l l l l} \hline
**Addresses (N)** & **Theoretical Avg.** & **Experimental Avg.** & **Difference** \\ \hline
100 & 2.33 & 2.33 & 0.00 \\
1000 & 3.19 & 3.20 & 0.01 \\
10,000 & 4.04 & 4.04 & 0.00 \\
100,000 & 4.85 & 4.85 & 0.00 \\
1,000,000 & 5.65 & 5.65 & 0.00 \\
10,000,000 & 6.46 & 6.47 & 0.01 \\
100,000,000 & 7.31 & 7.32 & 0.01 \\
300,000,000 & 7.72 & 7.72 & 0.00 \\ \hline \end{tabular}
\end{table}
Table 2: Average path length scaling.  
Figure 3: Theoretical prediction of the average path length scaling behavior in Merkle Patricia Tries.  
\begin{table}
\begin{tabular}{l l l l} \hline
**Trie Size** & **\(\chi^{2}\) Statistic** & **\(p\)-Value** & **Result** \\ \hline \(10^{2}\) & 0.011423 & 1.000 & Accept H\({}_{0}\) \\ \(10^{3}\) & 0.014662 & 1.000 & Accept H\({}_{0}\) \\ \(10^{4}\) & 0.009664 & 1.000 & Accept H\({}_{0}\) \\ \hline \end{tabular}
\end{table}
Table 3: Statistical validation results.  
where \(E[PL]\) is the expected path length and \(N\) is the number of addresses. The fit achieves \(R^{2}=0.9999\), indicating nearly perfect agreement between theory and experiment.  
The graph demonstrates the logarithmic relationship between the number of addresses (\(x\)-axis, logarithmic scale) and average path length (\(y\)-axis). The empirical measurements (dots) align remarkably well with the theoretical prediction (dotted line), achieving an R\({}^{2}\) value of 0.9999. This strong correlation validates our model across six orders of magnitude, from small-scale tries (100 addresses) to Ethereum-scale implementations (300 million addresses). The consistent logarithmic growth confirms that path lengths remain manageable even as the network expands exponentially, providing crucial insights for scalability planning and optimization strategies.  
This scaling behavior has several important implications:  
* Scalability: The logarithmic relationship ensures that path lengths remain manageable even as Ethereum's state grows exponentially. At the current scale (\(3\times 10^{8}\) addresses), the average path length is only 7.72 nodes;
* Proof Size: Since Merkle proofs must include all nodes along a path, the logarithmic scaling directly translates to proof size efficiency. This validates Ethereum's design choice of using MPTs for state management;
* Performance Bounds: The tight correlation between theoretical and experimental results (difference \(\leq\) 0.01) allows precise performance predictions for future network growth. For example, even a 1000-fold increase in network size would only increase the average path length by approximately 2.48 nodes;
* Optimization Potential: The consistent behavior across scales suggests that optimization strategies targeting average-case performance will remain effective as the network grows.  
The remarkable accuracy of our model across such a wide range of scales provides a solid foundation for future Ethereum scalability planning and optimization efforts.