mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
4a753bb639
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.
80 lines
2.8 KiB
TeX
80 lines
2.8 KiB
TeX
\section{Zero-Knowledge Proof System}
|
|
\label{sec:zk}
|
|
|
|
\subsection{Circuit Description}
|
|
|
|
The withdrawal proof circuit $\mathcal{C}$ enforces four properties:
|
|
|
|
\begin{definition}[Privacy Pool ZK Circuit]
|
|
Public inputs: $(R, R_{\mathcal{A}}, \mathsf{nf}, \mathsf{recipient}, v)$\\
|
|
Private inputs: $(\mathsf{sk}, r, \mathsf{leafIndex}, \mathsf{merklePath}, \mathsf{assocPath})$
|
|
|
|
The circuit verifies:
|
|
\begin{enumerate}
|
|
\item \textbf{Deposit existence}: $\mathsf{leaf} = H(\mathsf{Commit}(v, r), \mathsf{pk})$ is in the Merkle tree with root $R$ at path $\mathsf{merklePath}$.
|
|
\item \textbf{Key ownership}: $\mathsf{pk} = \mathsf{sk} \cdot G$ (the prover knows the secret key).
|
|
\item \textbf{Nullifier correctness}: $\mathsf{nf} = H_{\text{null}}(\mathsf{sk}, \mathsf{leafIndex})$.
|
|
\item \textbf{Association set membership}: $\mathsf{leaf}$ is in the association set Merkle tree with root $R_{\mathcal{A}}$ at path $\mathsf{assocPath}$.
|
|
\end{enumerate}
|
|
\end{definition}
|
|
|
|
\subsection{Groth16 Proof System}
|
|
|
|
We use Groth16 \cite{groth2016size} over BLS12-381 for succinct proofs:
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{Groth16 proof parameters for the privacy pool circuit.}
|
|
\label{tab:groth16}
|
|
\begin{tabular}{lr}
|
|
\toprule
|
|
\textbf{Parameter} & \textbf{Value} \\
|
|
\midrule
|
|
Constraint count & $\sim$65,000 \\
|
|
Proof size & 192 bytes (3 $\mathbb{G}_1$ + 1 $\mathbb{G}_2$ elements) \\
|
|
Verification key size & $\sim$1.5 KB \\
|
|
Proving time (consumer HW) & 2.8 seconds \\
|
|
Verification time (on-chain) & 1.7 ms (precompile) \\
|
|
Verification gas & 326,000 \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
\subsection{Circuit Constraints Breakdown}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{Constraint breakdown by circuit component.}
|
|
\label{tab:constraints}
|
|
\begin{tabular}{lrr}
|
|
\toprule
|
|
\textbf{Component} & \textbf{Constraints} & \textbf{Share} \\
|
|
\midrule
|
|
Pedersen commitment & 2,500 & 3.8\% \\
|
|
Public key derivation & 5,000 & 7.7\% \\
|
|
Nullifier hash (Poseidon) & 1,200 & 1.8\% \\
|
|
Merkle path (depth 20) & 24,000 & 36.9\% \\
|
|
Association set path (depth 20) & 24,000 & 36.9\% \\
|
|
Range checks and padding & 8,300 & 12.8\% \\
|
|
\midrule
|
|
\textbf{Total} & \textbf{65,000} & \textbf{100\%} \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
\subsection{Hash Function Selection}
|
|
|
|
We use Poseidon \cite{grassi2021poseidon} as the in-circuit hash function, optimized for arithmetic circuits:
|
|
|
|
\begin{definition}[Poseidon Hash]
|
|
Poseidon is an algebraic hash function over $\mathbb{F}_p$ (the BLS12-381 scalar field) with:
|
|
\begin{itemize}
|
|
\item Width: $t = 3$ (2 inputs + 1 capacity)
|
|
\item Full rounds: $R_f = 8$
|
|
\item Partial rounds: $R_p = 57$
|
|
\item Security: 128-bit against algebraic and statistical attacks
|
|
\end{itemize}
|
|
Poseidon requires $\sim$300 R1CS constraints per hash, versus $\sim$25,000 for SHA-256 in a circuit.
|
|
\end{definition}
|
|
|