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.
57 lines
1.8 KiB
TeX
57 lines
1.8 KiB
TeX
\section{Implementation Details}
|
|
\label{sec:implementation}
|
|
|
|
\subsection{Trusted Setup}
|
|
|
|
The Groth16 proof system requires a structured reference string (SRS) generated via a trusted setup ceremony:
|
|
|
|
\begin{itemize}
|
|
\item Powers-of-tau ceremony with $\geq 100$ participants.
|
|
\item Circuit-specific phase-2 ceremony.
|
|
\item Security: honest-majority assumption---if at least one participant destroys their toxic waste, the SRS is sound.
|
|
\end{itemize}
|
|
|
|
\subsection{Client-Side Proof Generation}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{Proof generation benchmarks across hardware.}
|
|
\label{tab:proving}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Hardware} & \textbf{Proving Time} & \textbf{Memory} & \textbf{Proof Size} \\
|
|
\midrule
|
|
Laptop (M1 MacBook) & 2.8 s & 1.2 GB & 192 B \\
|
|
Desktop (Ryzen 9) & 1.5 s & 1.2 GB & 192 B \\
|
|
Mobile (iPhone 15) & 8.2 s & 1.2 GB & 192 B \\
|
|
Browser (WASM) & 12.5 s & 1.5 GB & 192 B \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
\subsection{Merkle Tree Management}
|
|
|
|
The incremental Merkle tree uses Poseidon hashes and supports efficient updates:
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Incremental Merkle Tree Insert}
|
|
\label{alg:merkle}
|
|
\begin{algorithmic}[1]
|
|
\Require New leaf $\ell$, current tree with $n$ leaves
|
|
\State $\mathsf{filled}[0] \gets \ell$
|
|
\State $\mathsf{index} \gets n$
|
|
\For{$i = 0$ to $d - 1$}
|
|
\If{$\mathsf{index} \mod 2 = 0$}
|
|
\State $\mathsf{filled}[i+1] \gets H(\mathsf{filled}[i], \mathsf{zeros}[i])$
|
|
\Else
|
|
\State $\mathsf{filled}[i+1] \gets H(\mathsf{filledSubtrees}[i], \mathsf{filled}[i])$
|
|
\EndIf
|
|
\State $\mathsf{index} \gets \lfloor \mathsf{index} / 2 \rfloor$
|
|
\EndFor
|
|
\State Update root $R \gets \mathsf{filled}[d]$
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
Gas cost: $d \times 4{,}000 = 80{,}000$ gas for $d = 20$ Poseidon hashes.
|
|
|