papers/lp-137-gpu-crypto-stack/sections/04-determinism-harness.tex

\section{Determinism Harness}
\label{sec:determinism-harness}

Byte-equality is enforced by a uniform per-algorithm test harness:

\begin{lstlisting}[language=C++,caption={Per-algorithm Metal determinism test (canonical shape)}]
TEST(<alg>, MetalByteEqualToCPU) {
  std::mt19937 rng(0xCAFEBABE);
  for (int i = 0; i < 1000; ++i) {
    auto in = sample_random_input(rng);
    Output cpu_out = <alg>::cpu_canonical(in);
    Output gpu_out = <alg>::metal_kernel(in);
    EXPECT_EQ(cpu_out, gpu_out)
      << "byte-equality violated on input " << i;
  }
}
\end{lstlisting}

\subsection{Three-tier KAT methodology}

\begin{enumerate}
\item \textbf{Standard test vectors.} NIST CAVS \cite{fips180,fips202}, RFC test vectors (RFC 8032 \cite{rfc8032} for Ed25519, RFC 7693 \cite{rfc7693} for BLAKE2, RFC 9380 \cite{rfc9380} for hash-to-curve, RFC 9591 \cite{rfc9591} for FROST), EIP execution-spec-tests \cite{eip196,eip197}, Wycheproof \cite{wycheproof} are imported verbatim into \texttt{<alg>/test/kat\_*.json} and run against the Go canonical, C++ CPU body, and every shipping GPU kernel.
\item \textbf{Cross-oracle vectors.} For algorithms with multiple high-quality reference implementations (BN254 has \texttt{gnark-crypto} \cite{gnarkcrypto} and \texttt{arkworks-rs} \cite{arkworks}; Banderwagon has \texttt{go-ipa} and \texttt{arkworks}), KAT vectors are generated by oracle A and verified by oracle B. A discrepancy fails the test.
\item \textbf{Random-input determinism.} On every commit, $N=1000$ random inputs (via deterministic PRNG seed) are sampled and run through CPU canonical and each GPU kernel; bytes must match exactly.
\end{enumerate}

\subsection{What ``byte-equal'' means here}

For deterministic algorithms (hashes, AEAD, ECDSA verify, ECDSA recover, EdDSA verify, BLS verify, all KEM decap, all NTT/INTT, all FHE arithmetic, all threshold-share validation), byte-equal means literal bit-equality of the output buffer.

For randomized algorithms (signing operations that consume entropy: ECDSA sign, EdDSA sign, BLS sign, KEM encap, threshold sign), the harness fixes the entropy source to a deterministic stream derived from the test seed, so the operation becomes deterministic for the test and bit-equality applies.

For algorithms whose output specifically embeds high-entropy state (e.g.\ Paillier ciphertext in CGGMP21 presigning), byte-equality is enforced over the verifiable output (the produced share) by fixing the underlying ring randomness, not over the raw nonce.

\subsection{GPU-residency invariant check}

A separate static check runs on every Metal/CUDA/WGSL build:

\begin{itemize}
\item Disassemble every kernel (\texttt{metallib-disassemble}, \texttt{cuobjdump --dump-sass}, \texttt{naga validate}).
\item Verify that no kernel imports a host symbol that would force a GPU$\rightarrow$CPU copy of secret-state during the hot path.
\item Verify that all secret-state buffers are declared in private/threadgroup memory (not constant), so they cannot be bound from host without an explicit copy that the harness can detect.
\end{itemize}

This is operational, not aspirational: the check fires on every PR.

\subsection{Test oracle isolation, verified}

After each \texttt{cmake --build} of a per-algorithm test target, the harness runs:

\begin{lstlisting}[language=bash]
nm --defined-only lib<alg>.a | grep -Ev '^(<alg>_|crypto_|<alg>::)' \
  | (! read line)  # zero unprefixed symbols allowed
\end{lstlisting}

The production library exposes only its own algorithm-namespaced symbols. The test oracle (e.g.\ \texttt{libblst.a}) is linked into the test binary, not into the shipped library; \texttt{ldd} on \texttt{lib<alg>.so} (when built dynamic) must contain none of \texttt{libblst}, \texttt{libcrypto}, \texttt{libgmp} (off the modexp non-test path), or any other vendor.