papers/lux-verkle-trees/sections/04-verkle-tree-structure.tex

\section{Verkle Tree Structure}


\subsection{Tree Parameters}

Verkle trees are characterized by:
\begin{itemize}
    \item \textbf{Width} $w$: Number of children per node (typically 256)
    \item \textbf{Depth} $d$: Tree levels, where $d = \lceil \log_w(n) \rceil$
    \item \textbf{Commitment size}: 48 bytes (compressed $\mathbb{G}_1$ point)
    \item \textbf{Key size}: 32 bytes (matching existing infrastructure)
\end{itemize}

\subsection{Node Structure}

Each Verkle node contains:

\begin{lstlisting}[language=C,caption=Verkle Node Structure]
struct VerkleNode {
    Commitment C;           // 48 bytes: KZG commitment
    Key prefix;            // Variable: key prefix
    Value* values[256];    // Optional values
    NodeID* children[256]; // Child commitments
    uint8_t depth;         // Tree depth
    bool is_leaf;          // Leaf indicator
}
\end{lstlisting}

\subsection{Commitment Construction}

For internal node with children $(C_0, \ldots, C_{w-1})$, the commitment is:
\begin{equation}
    C_{node} = \mathsf{Commit}(C_0 || C_1 || \ldots || C_{w-1})
\end{equation}

Using KZG, this becomes:
\begin{equation}
    C_{node} = \sum_{i=0}^{w-1} C_i \cdot [\tau^i]_1
\end{equation}

\subsection{Path Resolution}

Key lookup follows the path determined by key chunks:
\begin{algorithmic}[1]
\STATE \textbf{function} $\mathsf{Lookup}(root, key)$
\STATE $node \gets root$
\STATE $depth \gets 0$
\WHILE{$node$ is not $null$}
    \STATE $chunk \gets key[depth]$
    \IF{$node.is\_leaf$}
        \RETURN $node.values[chunk]$
    \ENDIF
    \STATE $node \gets node.children[chunk]$
    \STATE $depth \gets depth + 1$
\ENDWHILE
\RETURN $null$
\end{algorithmic}