papers/lux-warp-messaging/sections/02-preliminaries.tex

\section{Preliminaries}
\label{sec:prelim}

\subsection{Bilinear Pairings and BLS12-381}

Let $\mathbb{G}_1, \mathbb{G}_2$ be additive groups and $\mathbb{G}_T$ a multiplicative group, all of prime order $p$. A bilinear pairing is a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ satisfying:
\begin{enumerate}
    \item \textbf{Bilinearity}: $e(aP, bQ) = e(P, Q)^{ab}$ for all $P \in \mathbb{G}_1, Q \in \mathbb{G}_2, a, b \in \mathbb{Z}_p$.
    \item \textbf{Non-degeneracy}: $e(g_1, g_2) \neq 1_{\mathbb{G}_T}$ for generators $g_1, g_2$.
    \item \textbf{Efficiency}: $e$ is computable in polynomial time.
\end{enumerate}

BLS12-381 \cite{bowe2017bls12381} is a pairing-friendly curve providing approximately 128 bits of security with:
\begin{itemize}
    \item $\mathbb{G}_1$ elements: 48 bytes (compressed)
    \item $\mathbb{G}_2$ elements: 96 bytes (compressed)
    \item Scalar field order: $p \approx 2^{255}$
\end{itemize}

\subsection{BLS Signature Scheme}

\begin{definition}[BLS Signatures \cite{boneh2001bls}]
Let $H : \{0,1\}^* \to \mathbb{G}_1$ be a hash-to-curve function modeled as a random oracle.
\begin{itemize}
    \item $\mathsf{KeyGen}(1^\lambda)$: Sample $\mathsf{sk} \xleftarrow{\$} \mathbb{Z}_p$; output $(\mathsf{sk}, \mathsf{pk} = \mathsf{sk} \cdot g_2)$.
    \item $\mathsf{Sign}(\mathsf{sk}, m)$: Output $\sigma = \mathsf{sk} \cdot H(m) \in \mathbb{G}_1$.
    \item $\mathsf{Verify}(\mathsf{pk}, m, \sigma)$: Accept iff $e(\sigma, g_2) = e(H(m), \mathsf{pk})$.
\end{itemize}
\end{definition}

\begin{definition}[Same-Message Aggregate Signature]
Given $n$ signatures $\sigma_1, \ldots, \sigma_n$ on the same message $m$ from public keys $\mathsf{pk}_1, \ldots, \mathsf{pk}_n$:
\begin{align}
    \sigma_{\text{agg}} &= \sum_{i=1}^{n} \sigma_i \in \mathbb{G}_1 \\
    \mathsf{apk} &= \sum_{i=1}^{n} \mathsf{pk}_i \in \mathbb{G}_2
\end{align}
Verification: accept iff $e(\sigma_{\text{agg}}, g_2) = e(H(m), \mathsf{apk})$.
\end{definition}

The aggregate signature is a single $\mathbb{G}_1$ element (48 bytes), regardless of $n$.

\subsection{Co-CDH Assumption}

\begin{definition}[Computational co-Diffie--Hellman]
Given $(g_1, g_2, a \cdot g_1, a \cdot g_2, b \cdot g_1)$ for random $a, b \in \mathbb{Z}_p$, it is computationally hard to compute $ab \cdot g_1$.
\end{definition}

\begin{theorem}[\cite{boneh2018compact}]
BLS aggregate signatures are existentially unforgeable under chosen-message attack in the random oracle model, assuming co-CDH holds on BLS12-381 and all signers prove possession of their secret keys.
\end{theorem}

\subsection{Lux Appchain Model}

\begin{definition}[Appchain]
A Lux appchain $\mathcal{S} = (\mathcal{V}, \mathsf{VM}, \mathsf{State}, \mathsf{ChainID})$ consists of:
\begin{itemize}
    \item A weighted validator set $\mathcal{V} = \{(v_i, w_i, \mathsf{pk}_i)\}_{i=1}^{n}$ with total weight $W = \sum_i w_i$.
    \item A virtual machine $\mathsf{VM}$ defining state transition rules.
    \item A state $\mathsf{State}$ maintained by consensus.
    \item A unique 32-byte chain identifier $\mathsf{ChainID}$.
\end{itemize}
Consensus requires agreement from validators with combined weight $\geq 2W/3$.
\end{definition}