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.
54 lines
2.1 KiB
TeX
54 lines
2.1 KiB
TeX
\section{Finality Gadget}
|
|
\label{sec:finality}
|
|
|
|
\subsection{Lux Finality Certificate}
|
|
|
|
External chains need to verify Lux finality without understanding the full consensus protocol. We define a finality certificate:
|
|
|
|
\begin{definition}[Finality Certificate]
|
|
A finality certificate for block $B$ is:
|
|
\begin{equation}
|
|
\mathsf{FC}(B) = (\mathsf{header}(B), \sigma_{\text{agg}}, \mathsf{bitmap}, \mathsf{epoch})
|
|
\end{equation}
|
|
where $\sigma_{\text{agg}}$ is a BLS aggregate signature over $H(B)$ from validators with $\geq 2/3$ stake weight in epoch $\mathsf{epoch}$.
|
|
\end{definition}
|
|
|
|
\begin{theorem}[Finality Certificate Security]
|
|
A valid finality certificate implies that block $B$ is finalized (will never be reverted) with probability $1 - \mathsf{negl}(\lambda)$, assuming $< 1/3$ Byzantine stake.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
If $\geq 2/3$ of stake signed $B$, then by the Lux consensus safety property, no conflicting block at the same height can gather $\geq 2/3$ signatures. Under co-CDH, the aggregate signature is unforgeable. Therefore, $B$ is uniquely finalized.
|
|
\end{proof}
|
|
|
|
\subsection{Compact Finality Proofs}
|
|
|
|
For chains without BLS12-381 support (e.g., Bitcoin), we provide SNARK-compressed finality proofs:
|
|
|
|
\begin{definition}[SNARK Finality Proof]
|
|
A SNARK proof $\pi$ attests that:
|
|
\begin{enumerate}
|
|
\item There exists a valid BLS aggregate signature $\sigma_{\text{agg}}$ over block hash $H(B)$.
|
|
\item The signers have combined stake $\geq 2W/3$.
|
|
\item The signers' public keys are in the committed validator set.
|
|
\end{enumerate}
|
|
The proof $\pi$ is $\sim$256 bytes and verifiable in $\sim$200,000 gas (Groth16) or 350,000 gas (PLONK).
|
|
\end{definition}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{Finality proof formats and verification costs.}
|
|
\label{tab:finality}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Proof Type} & \textbf{Size} & \textbf{Verification Gas} & \textbf{Target Chain} \\
|
|
\midrule
|
|
Raw BLS aggregate & 173 B & 250,000 & Chains with BLS support \\
|
|
SNARK (Groth16) & 256 B & 200,000 & EVM chains \\
|
|
SNARK (PLONK) & 512 B & 350,000 & Any SNARK verifier \\
|
|
SPV (header chain) & $\sim$5 KB & 500,000 & Bitcoin-like \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|