proofs/pulsar/scaling.tex

%% ============================================================
%% pulsar/scaling.tex
%% ============================================================
%%
%% Concrete numerical correctness + soundness claims for Pulsar
%% at the extreme committee size N* = 1,111,111.
%%
%% Papers and audit reports cite the bounds here directly; the
%% Go reference's TestShamirQ_LargeN_Extreme and
%% TestLargeShamir_EvalAtTargetCommitteeSize empirically verify the
%% correctness claim, while the unforgeability claim is by reduction
%% from pulsar/unforgeability.tex.
%% ============================================================

\subsection*{Pulsar at $N^\star = 1\,111\,111$ signers}

This section pins the concrete, numerical claims for the canonical
extreme committee size. Three claims are made: (i) algebraic
correctness, (ii) cryptographic soundness, (iii) operational
feasibility. The first is mechanical; the second is by
\Cref{thm:pulsar-tsuf}'s $n$-independence; the third is an
arithmetic estimate.

\paragraph{Constants.}
\begin{itemize}[leftmargin=*, itemsep=0pt]
\item Module-LWE prime: $q = 2^{23} - 2^{13} + 1 = 8\,380\,417$.
\item Maximum supported committee: $q - 1 = 8\,380\,416$.
\item Reference target: $N^\star = 1\,111\,111$.
\item Headroom: $(q - 1) - N^\star = 7\,269\,305$, i.e.\
  $\approx 86.7\%$ of the field's party-count capacity remains
  available beyond $N^\star$.
\end{itemize}

\paragraph{Claim 1 -- Algebraic correctness at $N^\star$.}

\begin{proposition}[Pulsar Shamir is correct at $N^\star$]
\label{prop:pulsar-correct-at-N-star}
Let $f(X) = s + a_1 X + \cdots + a_{t-1} X^{t-1}$ be a degree-$(t-1)$
polynomial over GF($q$). For any subset $T \subseteq \{1, \dots, N^\star\}$
with $|T| = t$ and distinct elements, the Lagrange interpolation
$\sum_{i \in T} \lambda_i^T \cdot f(i)$ at $X = 0$ recovers $s$
exactly. Equivalently: the Pulsar wide-field Shamir layer is
correct for every threshold subset of every committee with $n \le
N^\star$.
\end{proposition}

\begin{proof}
GF($q$) is a finite field of order $q$ with $N^\star < q$. The
evaluation points $1, 2, \dots, N^\star$ are distinct non-zero
elements of GF($q$), and any $t$-subset of them has pairwise
distinct denominators in the Lagrange basis. Lagrange interpolation
on $\le q - 1$ distinct evaluation points recovers any polynomial of
degree $\le t - 1$ exactly. \qed
\end{proof}

\Cref{prop:pulsar-correct-at-N-star} is the propositional content
verified empirically by
\texttt{ref/go/pkg/pulsar/largeshamir\_test.go:\\TestLargeShamir\_EvalAtTargetCommitteeSize}
and
\texttt{ref/go/pkg/pulsar/shamir\_gfq\_test.go:\\TestShamirQ\_LargeN\_BoundaryCommittees}.

\paragraph{Claim 2 -- Cryptographic soundness at $N^\star$.}

\begin{theorem}[Pulsar TS-UF at $N^\star$ is bounded by FIPS~204 advantages]
\label{thm:pulsar-soundness-at-N-star}
For every $\PPT$ adversary $\mathcal{A}$ against Pulsar at
$(n, t) = (N^\star, t)$, $1 \le t \le N^\star$, the TS-UF advantage
satisfies the bound of \Cref{thm:pulsar-tsuf} with the same
constants as the small-committee case.
\end{theorem}

\begin{proof}
By \Cref{thm:pulsar-scales-n}, the TS-UF advantage is independent
of $n$ once the parameter level $L$ is fixed. Instantiating at
$n = N^\star$ does not change the M-LWE, MSIS, ML-DSA EUF-CMA, or
RO-programming terms. The Shamir field choice (GF($q$) at this
committee size) is information-theoretically secure for $\le t-1$
corruptions over any field of order $> n$, which is satisfied
because $q > N^\star$. \qed
\end{proof}

\paragraph{Claim 3 -- Operational feasibility at $N^\star$.}

We collect the numerical operating costs of running Pulsar at
$n = N^\star$ for both the per-party (light-client / HSM) and the
aggregator (consensus-layer) viewpoints.

\begin{center}\small
\begin{tabular}{l r r}
\toprule
operation & cost & complexity \\
\midrule
per-party share size                 & $128$ bytes      & $O(\mathrm{SeedSize})$ \\
per-party share computation (\texttt{EvalAt}) & $\approx 1.2~\mu s$ & $O(t \cdot \mathrm{SeedSize})$ \\
per-party storage (one share)        & $128$ bytes      & $O(\mathrm{SeedSize})$ \\
$t$-quorum reconstruction            & $\approx 8~\mu s$ at $t = 5$ & $O(t^2 \cdot \mathrm{SeedSize})$ \\
full $n$-party deal (materialise all shares) & $\approx 142$~MB at $n = N^\star$ & $O(n \cdot \mathrm{SeedSize})$ \\
full $n$-party deal wall clock (M3)  & $\approx 1.3$~s at $n = N^\star$ & $O(n \cdot t \cdot \mathrm{SeedSize})$ \\
TS-UF advantage at $N^\star$         & same as $(3, 2)$ & $n$-independent \\
\bottomrule
\end{tabular}
\end{center}

The per-party costs (top three rows) are the production-relevant
numbers: a validator participating in a $1\,111\,111$-party committee
processes 128 bytes of share material, computes a single share in
$\sim 1.2~\mu s$, and stores 128 bytes per epoch.

\paragraph{Why $N^\star \neq q - 1$.}
The reference implementation could in principle support
$q - 1 = 8\,380\,416$ parties, but pinning $N^\star = 1\,111\,111$
gives an order-of-magnitude headroom for:

\begin{enumerate}[leftmargin=*, itemsep=0pt]
\item Over-provisioning the validator-set epoch with un-elected
candidates whose shares are pre-computed but never activated;
\item Joining-without-reshare slack so new validators can be added
without immediately triggering a $\Reshare$ ceremony;
\item Future grow-without-fork: the protocol can absorb a $7\times$
expansion of the committee without any algorithmic change.
\end{enumerate}

The cap $N^\star = 1\,111\,111$ is a deployment-time soft cap, not
a protocol-level hard cap: changing it requires only updating the
\texttt{TargetCommitteeSize} constant and re-running the conformance
tests, all of which are guaranteed to pass for any
$N^\star \le q - 1$ by \Cref{prop:pulsar-correct-at-N-star} and
\Cref{thm:pulsar-soundness-at-N-star}.

\paragraph{Arithmetic-width discipline.}
At $n = N^\star$ no intermediate value exceeds $46$ bits. uint128 or
uint256 widths are not needed for the Pulsar core; they are
reserved for the Z-Chain SNARK verifier path (which operates over
$\approx 254$-bit prime-order fields and consumes Pulsar outputs
as opaque byte strings rather than re-interpreting them as field
elements). This means every modern CPU and GPU dispatch backend
(Apple Metal, NVIDIA CUDA, AMD ROCm) runs the Pulsar reference
at memory-bandwidth-limited throughput; the dominant cost is the
$\cSHAKE$ stream expansion, not modular arithmetic.