papers/lux-fpc-consensus/sections/08-security-analysis.tex

\section{Security Analysis}

\label{sec:security}

\subsection{Byzantine Fault Tolerance}

\begin{theorem}[Byzantine Tolerance]
FPC tolerates up to $f < n/3$ Byzantine nodes with overwhelming probability.
\end{theorem}

\begin{proof}
With $f < n/3$ Byzantine nodes, any random sample of size $k$ has expected honest majority $h > 2k/3$. By Chernoff bound:

\begin{equation}
P(\text{honest in sample} < k/2) < e^{-2k(1/6)^2} < 2^{-k/18}
\end{equation}

For $k = 20$:
\begin{align}
P(\text{Byzantine takeover per round}) &< 2^{-1.1} \approx 0.47 \\
P(\text{Byzantine success after } \beta = 3) &< 0.47^3 < 0.1
\end{align}
\end{proof}

\subsection{Attack Vectors and Mitigations}

\subsubsection{Sybil Attack}
\textbf{Vector}: Create many identities to influence sampling\\
\textbf{Mitigation}: Require stake or proof-of-work for participation

\subsubsection{Eclipse Attack}
\textbf{Vector}: Isolate nodes to control their sample\\
\textbf{Mitigation}: Diverse peer connections, gossip protocol redundancy

\subsubsection{Timing Attack}
\textbf{Vector}: Delay responses to influence outcome\\
\textbf{Mitigation}: Strict timeouts with exponential backoff

\subsubsection{Adaptive Adversary}
\textbf{Vector}: Change strategy based on observations\\
\textbf{Mitigation}: Commit-reveal schemes, threshold encryption

\subsection{Probability of Safety Violation}

The probability of safety violation decreases exponentially with committee size:

\begin{equation}
P(\text{safety violation}) \leq e^{-\Omega(k)}
\label{eq:safety}
\end{equation}

For practical parameters:
\begin{itemize}
\item $k = 20$: $P(\text{violation}) < 10^{-6}$
\item $k = 25$: $P(\text{violation}) < 10^{-8}$
\item $k = 30$: $P(\text{violation}) < 10^{-10}$
\end{itemize}