papers/lux-state-sync/sections/04-merkle-range-proofs.tex

\section{Merkle Range Proofs}
\label{sec:rangeproofs}

\subsection{Range Proof Definition}

\begin{definition}[Merkle Range Proof]
A range proof $\pi_{[a,b]}$ for key range $[a, b]$ in a trie with root $R$ consists of:
\begin{itemize}
    \item All leaf nodes with keys $k \in [a, b]$.
    \item All internal trie nodes on paths from the root to the boundary keys $a$ and $b$.
    \item Hashes of all sibling nodes adjacent to these paths.
\end{itemize}
The proof demonstrates that the provided leaves are exactly the entries in $[a, b]$---no more, no less.
\end{definition}

\begin{theorem}[Range Proof Correctness]
Given root $R$ and range proof $\pi_{[a,b]}$, a verifier can confirm:
\begin{enumerate}
    \item Every leaf in $\pi$ has a key in $[a, b]$ (inclusion).
    \item No leaf with key in $[a, b]$ is missing (completeness).
    \item The proof is consistent with root $R$ (authenticity).
\end{enumerate}
\end{theorem}

\begin{proof}
Inclusion follows from direct key comparison. For completeness, the verifier reconstructs the trie from root to the boundary paths. Any ``gap'' in the key range would require a branch node pointing to a missing subtree; the verifier detects this because the branch hash would not match the provided sibling hashes. Authenticity follows from recomputing the root hash from the provided nodes and comparing with $R$.
\end{proof}

\subsection{Proof Size}

\begin{proposition}[Range Proof Size]
For a trie of depth $d$ containing $n$ leaves, a range proof covering $k$ consecutive leaves has size:
\begin{equation}
    |\pi_{[a,b]}| = k \cdot L + 2d \cdot N + O(d)
\end{equation}
where $L$ is the average leaf size (bytes) and $N$ is the average internal node size.
\end{proposition}

\begin{proof}
The $k$ leaves contribute $kL$ bytes. The two boundary paths contribute at most $2d$ internal nodes. Sibling hashes along the paths contribute $O(d)$ additional 32-byte hashes. The total is $kL + 2dN + O(d \cdot 32)$.
\end{proof}

For a chunk of 10,000 leaves with $L = 100$ bytes, $d = 8$, $N = 550$ bytes: $|\pi| \approx 1{,}000{,}000 + 8{,}800 + 512 \approx 1{,}009$ KB. The proof overhead is $< 1\%$ of the data payload.

\subsection{Range Proof Verification}

\begin{algorithm}[H]
\caption{Merkle Range Proof Verification}
\label{alg:verify_range}
\begin{algorithmic}[1]
\Require Range $[a, b]$, leaves $\{(k_i, v_i)\}$, proof nodes $\mathcal{P}$, root $R$
\State Verify all $k_i \in [a, b]$ and $k_i$ are sorted
\State Verify no gaps: for consecutive $k_i, k_{i+1}$, the trie has no leaf $k$ with $k_i < k < k_{i+1}$
\State Reconstruct partial trie from leaves and proof nodes
\State Compute root hash $R' \gets H(\text{reconstructed root})$
\If{$R' = R$}
    \State \Return \textsc{Valid}
\Else
    \State \Return \textsc{Invalid}
\EndIf
\end{algorithmic}
\end{algorithm}

The gap verification (line 2) is the key step for completeness. It leverages the trie structure: if a branch node has a child pointer that should lead to a key in $[a,b]$ but no corresponding leaf was provided, the reconstructed hash will differ from $R$.