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.
70 lines
2.6 KiB
TeX
70 lines
2.6 KiB
TeX
\section{The Flare Protocol}
|
|
|
|
\label{sec:protocol}
|
|
|
|
\subsection{Core Protocol}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Flare Protocol --- Conviction-Based Certification}
|
|
\label{alg:flare-core}
|
|
\begin{algorithmic}[1]
|
|
\Require Validator $v$, transaction $t$ with conflict set $\mathcal{C}(t) \neq \emptyset$
|
|
\Require Parameters: $k$ (sample size), $\alpha$ (quorum), $\beta_2$ (conviction threshold)
|
|
\State $cnt \gets 0$
|
|
\State $\text{col} \gets$ color of first-seen transaction
|
|
\While{$\lnot \text{certified}(v, t)$}
|
|
\State $S \gets \text{RandomSample}(V \setminus \{v\}, k)$
|
|
\State Query each $u \in S$ for $\text{col}(u, t)$
|
|
\State $n_{\text{col}} \gets |\{u \in S : \text{col}(u, t) = \text{col}\}|$
|
|
\If{$n_{\text{col}} \geq \alpha k$}
|
|
\State $cnt \gets cnt + 1$ \Comment{conviction strengthened}
|
|
\If{$cnt = \beta_2$}
|
|
\State Issue $\text{cert}(v, t, \text{col})$
|
|
\State $\text{certified}(v, t) \gets \text{true}$
|
|
\EndIf
|
|
\Else
|
|
\State $c^* \gets \arg\max_c |\{u \in S : \text{col}(u, t) = c\}|$
|
|
\If{$c^* \neq \text{col}$ \textbf{and} $|\{u \in S : \text{col}(u, t) = c^*\}| \geq \alpha k$}
|
|
\State $\text{col} \gets c^*$ \Comment{preference switch}
|
|
\State $cnt \gets 1$ \Comment{skip: reset with credit for this round}
|
|
\Else
|
|
\State $cnt \gets 0$ \Comment{no supermajority: full reset}
|
|
\EndIf
|
|
\EndIf
|
|
\EndWhile
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Certificate Propagation}
|
|
|
|
Once a certificate is produced, it is broadcast to all validators. Validators that
|
|
receive a valid certificate for transaction $t$ with color $c$ can immediately finalize
|
|
$t$ without running their own conviction counter to completion.
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Flare Certificate Verification and Adoption}
|
|
\label{alg:flare-cert}
|
|
\begin{algorithmic}[1]
|
|
\Function{OnReceiveCertificate}{$\text{cert}(u, t, c)$}
|
|
\If{$\text{VerifySignature}(\text{cert}, u)$}
|
|
\State $\text{col}(v, t) \gets c$
|
|
\State $\text{certified}(v, t) \gets \text{true}$
|
|
\State \textbf{broadcast} $\text{cert}(u, t, c)$ to peers
|
|
\EndIf
|
|
\EndFunction
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{DAG Integration}
|
|
|
|
Flare operates on individual conflict sets within the DAG. A transaction $t$ is finalized
|
|
when:
|
|
\begin{enumerate}[nosep]
|
|
\item A certificate exists for $t$ (or $t$ has no conflict), and
|
|
\item All ancestors $t' \in \mathcal{A}(t)$ are also certified (or conflict-free).
|
|
\end{enumerate}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 4. CERTIFICATE SKIP EXCLUSIVITY
|
|
%% -----------------------------------------------------------------------
|