papers/ntt-transform/sections/05-gas-optimization-journey.tex

\section{Gas Optimization Journey}


\subsection{Baseline Implementation}

Our journey began with a direct port of the reference Python implementation to Solidity:

\begin{itemize}
\item \textbf{Recursive NTT}: 6.9M gas
\item \textbf{Recursive INTT}: 7.8M gas
\item \textbf{Full FALCON-512 verification}: 24M gas
\end{itemize}

This baseline consumed nearly 80\% of Ethereum's block gas limit, making it impractical for production use.

\subsection{Iterative Algorithm}

Replacing recursion with iteration eliminated stack overhead:

\begin{itemize}
\item \textbf{Iterative NTT}: 4.0M gas (42\% reduction)
\item \textbf{Iterative INTT}: 4.2M gas (46\% reduction)
\item \textbf{Full FALCON-512 verification}: 8.5M gas (65\% reduction)
\end{itemize}

\subsection{Yul Optimization}

The breakthrough came from aggressive Yul optimization:

\begin{itemize}
\item \textbf{Yul NTT}: 1.9M gas (72\% reduction from baseline)
\item \textbf{Yul INTT}: 2.0M gas (74\% reduction)
\item \textbf{Full FALCON-512 verification}: 3.6M gas (85\% reduction)
\end{itemize}

\subsection{Optimization Techniques Applied}

\begin{table}[h]
\centering
\caption{Gas Savings by Optimization Technique}
\begin{tabular}{lrr}
\toprule
Technique & Gas Saved & \% Impact \\
\midrule
Iterative algorithm & 2.9M & 42\% \\
Memory pre-allocation & 0.8M & 12\% \\
Loop unrolling (4x) & 1.2M & 17\% \\
Yul inline assembly & 1.5M & 22\% \\
CODECOPY for constants & 0.5M & 7\% \\
\bottomrule
\end{tabular}
\end{table}