mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
41 lines
1.5 KiB
TeX
41 lines
1.5 KiB
TeX
\section{Merkle Tree Limitations}
|
|
|
|
|
|
\subsection{Proof Size Complexity}
|
|
|
|
Merkle trees authenticate data through recursive hashing, requiring $O(\log n)$ hash values for proof construction. For a tree of depth $d$ with hash output size $h$ bytes, proof size equals:
|
|
|
|
\begin{equation}
|
|
P_{merkle} = d \cdot h = \log_2(n) \cdot h
|
|
\end{equation}
|
|
|
|
With SHA-256 ($h = 32$ bytes) and $n = 2^{32}$ accounts:
|
|
\begin{equation}
|
|
P_{merkle} = 32 \cdot 32 = 1024 \text{ bytes}
|
|
\end{equation}
|
|
|
|
\subsection{Deep Tree Structures}
|
|
|
|
Binary Merkle trees exhibit depth linear in $\log n$, creating cascading performance penalties:
|
|
|
|
\begin{itemize}
|
|
\item \textbf{Verification time}: $O(d)$ hash computations
|
|
\item \textbf{Update complexity}: $O(d)$ nodes modified per update
|
|
\item \textbf{Cache inefficiency}: Poor locality for deep paths
|
|
\item \textbf{Network overhead}: Linear bandwidth in tree depth
|
|
\end{itemize}
|
|
|
|
\subsection{Bandwidth Amplification}
|
|
|
|
For batch operations touching $k$ keys, Merkle proof sizes grow as:
|
|
\begin{equation}
|
|
P_{batch} = O(k \cdot \log n)
|
|
\end{equation}
|
|
|
|
This creates prohibitive overhead for common patterns like multi-asset transfers or contract calls touching multiple storage slots.
|
|
|
|
\subsection{State Witness Size}
|
|
|
|
Ethereum's current state witness for a typical block exceeds 500 KB using Merkle proofs, making real-time propagation challenging on bandwidth-constrained networks. This fundamentally limits the viability of stateless clients under the Merkle tree paradigm.
|
|
|