papers/lux-prism-protocol/sections/02-spectral-decomposition.tex

\section{Spectral Decomposition}

\label{sec:partition}

\subsection{Band Assignment}

\begin{definition}[Spectrum Band]
Given $B$ spectrum bands $\{b_0, b_1, \ldots, b_{B-1}\}$, a transaction $t$ with
conflict set identifier $\text{csid}(t)$ is assigned to band:
\[
\text{band}(t) = H(\text{csid}(t)) \mod B
\]
where $H$ is a cryptographic hash function (SHA-256).
\end{definition}

\begin{definition}[Conflict Set Identifier]
The conflict set identifier $\text{csid}(t)$ is determined by the consumed UTXO(s)
of transaction $t$. All transactions consuming the same UTXO share the same $\text{csid}$.
Non-conflicting transactions have distinct $\text{csid}$ values.
\end{definition}

\begin{theorem}[Conflict Locality]
\label{thm:locality}
If $t_1 \in \mathcal{C}(t_2)$ (the transactions conflict), then $\text{band}(t_1) = \text{band}(t_2)$.
Conflicting transactions are always processed in the same spectrum band.
\end{theorem}

\begin{proof}
By definition, $t_1 \in \mathcal{C}(t_2)$ implies $\text{csid}(t_1) = \text{csid}(t_2)$
(they consume the same UTXO). Therefore:
\[
\text{band}(t_1) = H(\text{csid}(t_1)) \mod B = H(\text{csid}(t_2)) \mod B = \text{band}(t_2)
\]
\end{proof}

\subsection{Load Balance}

\begin{theorem}[Load Balance]
\label{thm:balance}
For $T$ transactions with uniformly distributed $\text{csid}$ values and $B$ bands,
the load on band $b$ satisfies:
\[
\Pr\left[|L_b - T/B| > \sqrt{\frac{2T \ln B}{B}}\right] < \frac{2}{B}
\]
where $L_b$ is the number of transactions assigned to band $b$.
\end{theorem}

\begin{proof}
Each transaction is independently assigned to band $b$ with probability $1/B$ (by
the uniformity of $H$). The load $L_b \sim \text{Binomial}(T, 1/B)$ with mean $T/B$
and variance $T(B-1)/B^2$.

By the Chernoff bound:
\[
\Pr[|L_b - T/B| > \delta] \leq 2\exp\left(-\frac{\delta^2 B}{2T}\right)
\]
Setting $\delta = \sqrt{2T \ln B / B}$ gives $\Pr[|L_b - T/B| > \delta] < 2/B^2$.
A union bound over $B$ bands:
\[
\Pr[\exists b : |L_b - T/B| > \delta] < B \cdot 2/B^2 = 2/B
\]
For $B = 16$: the maximum deviation from mean load is at most $\sqrt{2T \ln 16 / 16} \approx 0.66\sqrt{T}$
with probability $> 87.5\%$.
\end{proof}

%% -----------------------------------------------------------------------
%%  3. THE PRISM PROTOCOL
%% -----------------------------------------------------------------------