papers/lux-fraud-proofs/sections/20-mathematical-foundations.tex

\section{Mathematical Foundations}


We present the formal mathematical framework underlying the fraud proof system.

\subsection{State Transition Function}

\begin{definition}[State Transition Function]
The state transition function $\text{STF}: \mathcal{S} \times \mathcal{T} \rightarrow \mathcal{S}$ maps a state $S \in \mathcal{S}$ and transaction $t \in \mathcal{T}$ to a new state:
\begin{equation}
\text{STF}(S, t) = S'
\end{equation}
where $\mathcal{S}$ is the state space and $\mathcal{T}$ is the transaction space.
\end{definition}

\subsection{Assertion Validity}

\begin{definition}[Valid Assertion]
An assertion $A = (S_{\text{old}}, S_{\text{new}}, \mathcal{T}, \sigma)$ is valid if:
\begin{equation}
S_{\text{new}} = \text{STF}^*(\text{S}_{\text{old}}, \mathcal{T})
\end{equation}
where $\text{STF}^*$ denotes the iterative application of STF over transaction sequence $\mathcal{T}$.
\end{definition}

\subsection{Bisection Round Complexity}

\begin{theorem}[Bisection Rounds]
For $n$ computational steps, the number of bisection rounds required is:
\begin{equation}
R = \lceil\log_2(n)\rceil
\end{equation}
\end{theorem}

\subsection{Fraud Proof Validity}

\begin{definition}[Valid Fraud Proof]
A fraud proof $\mathcal{F}$ is valid if there exists step $i$ such that:
\begin{equation}
\text{STF}(S_i, t_i) \neq S_{i+1}
\end{equation}
where $S_i$ is the intermediate state claimed in the assertion.
\end{definition}

\subsection{Economic Security Model}

\begin{theorem}[Economic Security Bound]
The system maintains economic security if:
\begin{equation}
B > C_{\text{attack}} + O_{\text{capital}}
\end{equation}
where $B$ is the required bond, $C_{\text{attack}}$ is the cost of attacking, and $O_{\text{capital}}$ is the opportunity cost.
\end{theorem}

\subsection{Safety Condition}

\begin{theorem}[Safety]
The system is safe if:
\begin{itemize}
    \item $\exists$ at least one honest party capable of detecting fraud
    \item Challenge period $\tau > \tau_{\text{network}} + \tau_{\text{proof}}$
    \item Honest party has sufficient stake to challenge
\end{itemize}
\end{theorem}

\subsection{Liveness Condition}

\begin{theorem}[Liveness]
The system maintains liveness if:
\begin{itemize}
    \item $\exists$ at least one honest proposer
    \item Proposer can post assertions within timeout
    \item Network partition duration $< \tau_{\text{challenge}}$
\end{itemize}
\end{theorem}