papers/zoo-gym-compute-proof/zoo-gym-compute-proof.tex

\documentclass[11pt,letterpaper]{article}
\usepackage{shared/zoocover}

% Packages
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{booktabs}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows,positioning,calc}
\usepackage{listings}
\usepackage{caption}
\usepackage{subcaption}
% geometry loaded by zoocover

\input{shared/lstlang}

% Listings style
\lstset{
  basicstyle=\ttfamily\small,
  breaklines=true,
  frame=single,
  numbers=left,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue!70!black}\bfseries,
  commentstyle=\color{green!50!black}\itshape,
  stringstyle=\color{red!60!black},
  showstringspaces=false,
  tabsize=2,
  captionpos=b
}

% Theorem environments
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]

% Custom commands
\newcommand{\Zoo}{\textsc{Zoo}}
\newcommand{\GYM}{\textsc{Gym}}
\newcommand{\LLM}{\textsc{llm}}
\newcommand{\PoC}{\textsc{PoC}}

% Hyperref setup
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    citecolor=blue,
    urlcolor=blue
}

% Title and authors
\title{\textbf{Proof-of-Compute for Federated Language Model Training:\\A Cryptographic Framework}}

\author{
Antje Worring, Zoo Labs Foundation Research\thanks{[email protected]}\\
\textit{Hanzo Industries \quad Zoo Labs Foundation}\\
\texttt{[email protected]}
}

\date{January 2025}

\begin{document}

\zoocoverpage

\begin{abstract}
We present a \textbf{Proof-of-Compute} (\PoC{}) framework for verifying that a participant in decentralized language model training actually performed the claimed computation.  \PoC{} combines three mechanisms: (1) \textbf{Ed25519 delta signatures}---each training delta is signed by the worker's key, binding the worker identity to the computation output; (2) \textbf{gradient hashing}---intermediate gradient states are committed via SHA3-256 hash chains, creating a tamper-evident log of the training trajectory; (3) \textbf{spot-verify sampling}---the orchestrator probabilistically re-executes a subset of training steps and compares results within a tolerance bound.  We prove that a rational adversary cannot profitably fake compute under the \PoC{} framework when the spot-check probability exceeds $p > c_{\text{fake}} / (c_{\text{fake}} + s \cdot f_{\text{slash}})$, where $c_{\text{fake}}$ is the cost of faking, $s$ is the stake, and $f_{\text{slash}}$ is the slash fraction.  For Zoo Gym's parameters ($p = 0.1$, $s = 10{,}000$ GYM, $f_{\text{slash}} = 0.5$), faking is unprofitable unless the adversary can produce indistinguishable fake deltas at less than 2\% of real training cost.  We also describe slashing conditions, the hash-chain audit trail, and the path toward zero-knowledge proofs of training for full verification without re-execution.

\textbf{Keywords}: proof-of-compute, Ed25519, gradient hashing, spot-check verification, slashing, zero-knowledge proofs
\end{abstract}

%----------------------------------------------------------------------
\section{Introduction}

In centralized training, the training operator trusts that its own GPUs performed the computation.  In decentralized training (Zoo Gym), nodes are untrusted: a rational node may claim rewards for compute it never performed.  Attacks include:

\begin{enumerate}
    \item \textbf{Free-riding}: Submitting zero or random deltas to collect participation rewards.
    \item \textbf{Replay}: Resubmitting deltas from a previous epoch.
    \item \textbf{Proxy}: Outsourcing compute to a cheaper (but lower-quality) provider and pocketing the margin.
    \item \textbf{Gradient theft}: Stealing another node's delta and claiming it as one's own.
\end{enumerate}

We need a verification system that makes these attacks economically unprofitable without requiring every delta to be fully re-verified (which would negate the throughput benefit of decentralization).

\subsection{Contributions}

\begin{enumerate}
    \item \textbf{Three-layer \PoC{} framework}: Signatures bind identity, hash chains bind sequence, spot-checks bind correctness.
    \item \textbf{Economic security model}: Formal conditions under which faking is unprofitable, parameterized by spot-check rate and stake/slash ratio.
    \item \textbf{Gradient hash chain}: Incremental commitment scheme that allows efficient audit of the training trajectory.
    \item \textbf{Spot-verify protocol}: Randomized re-execution with deterministic seeding to ensure reproducibility.
    \item \textbf{Path to zkPoC}: Architecture for zero-knowledge proofs of training steps, providing full verification without re-execution.
\end{enumerate}

%----------------------------------------------------------------------
\section{Threat Model}
\label{sec:threat}

\subsection{Adversary Capabilities}

The adversary controls up to $f < N/3$ nodes and can:

\begin{enumerate}
    \item Produce arbitrary delta payloads.
    \item Observe all public communications (delta hashes, ring messages).
    \item Collude across controlled nodes.
    \item Invest up to budget $B$ in computational resources.
\end{enumerate}

The adversary \textit{cannot}:

\begin{enumerate}
    \item Forge Ed25519 signatures (computational hardness of DLP on Curve25519).
    \item Predict the spot-check selection (random oracle model).
    \item Corrupt the blockchain state (honest majority assumption on Hanzo chain).
\end{enumerate}

\subsection{Security Goals}

\begin{definition}[Compute Authenticity]
A delta $\delta$ is \textit{authentic} if it was produced by executing the specified training step on the specified data with the specified model weights.
\end{definition}

\begin{definition}[Non-Repudiation]
A node that submits delta $\delta$ with signature $\sigma$ cannot later deny having produced $\delta$.
\end{definition}

\begin{definition}[Freshness]
A delta $\delta$ for epoch $e$, step $t$ cannot be a replay of a delta from any other $(e', t') \neq (e, t)$.
\end{definition}

%----------------------------------------------------------------------
\section{Ed25519 Delta Signatures}
\label{sec:signatures}

\subsection{Key Registration}

Each node generates an Ed25519 keypair $(sk, pk)$ at registration.  The public key $pk$ is recorded on-chain in the orchestrator registry contract.

\begin{lstlisting}[language=Rust,caption=Key generation and registration]
use ed25519_dalek::{SigningKey, VerifyingKey};
use rand::rngs::OsRng;

pub fn register_node() -> (SigningKey, VerifyingKey) {
    let sk = SigningKey::generate(&mut OsRng);
    let pk = sk.verifying_key();
    // Record pk on-chain
    chain.register_key(node_id, pk.as_bytes());
    (sk, pk)
}
\end{lstlisting}

\subsection{Delta Signing}

Every delta includes a signature over the tuple $(e, t, H(\delta))$:

\begin{equation}
    \sigma = \textsc{Ed25519.Sign}\!\left(sk, \; e \| t \| \text{SHA3-256}(\delta)\right)
    \label{eq:delta-sig}
\end{equation}

where $e$ is the epoch, $t$ is the step, and $\delta$ is the serialized delta payload (header + tensors, per the Delta binary format).

\begin{theorem}[Unforgeability]
Under the hardness of the Discrete Logarithm Problem on Curve25519, no PPT adversary can produce a valid $(\delta', \sigma')$ for a node it does not control, with probability greater than $2^{-128}$.
\end{theorem}

This follows directly from the EUF-CMA security of Ed25519~\cite{bernstein2012ed25519}.

\subsection{Freshness}

Including $(e, t)$ in the signed message prevents replay: a signature valid for $(e_1, t_1)$ is invalid for $(e_2, t_2)$.

\begin{proposition}[Anti-Replay]
A delta signed for $(e, t)$ cannot be replayed at $(e', t')$ without forging a new signature.
\end{proposition}

\subsection{Non-Repudiation}

The on-chain binding of $pk$ to $\text{node\_id}$ means that a valid signature constitutes proof of authorship.  The node cannot deny having produced the delta.

%----------------------------------------------------------------------
\section{Gradient Hash Chain}
\label{sec:hashchain}

\subsection{Construction}

At each training step $t$, the node commits the intermediate gradient state to a hash chain:

\begin{equation}
    h_t = \text{SHA3-256}\!\left(h_{t-1} \| t \| \text{SHA3-256}(\nabla_t)\right)
    \label{eq:hashchain}
\end{equation}

with $h_0 = \text{SHA3-256}(\text{``GENESIS''} \| e \| \text{node\_id})$.

\begin{lstlisting}[language=python,caption=Gradient hash chain (Python)]
import hashlib

class GradientHashChain:
    def __init__(self, epoch: int, node_id: str):
        genesis = f"GENESIS|{epoch}|{node_id}".encode()
        self.current = hashlib.sha3_256(genesis).digest()
        self.chain = [self.current]

    def commit(self, step: int, gradient_bytes: bytes):
        grad_hash = hashlib.sha3_256(gradient_bytes).digest()
        payload = (
            self.current
            + step.to_bytes(8, "little")
            + grad_hash
        )
        self.current = hashlib.sha3_256(payload).digest()
        self.chain.append(self.current)
        return self.current

    def verify(self, step: int, gradient_bytes: bytes,
               expected_hash: bytes) -> bool:
        grad_hash = hashlib.sha3_256(gradient_bytes).digest()
        prev = self.chain[step]
        payload = (
            prev
            + step.to_bytes(8, "little")
            + grad_hash
        )
        computed = hashlib.sha3_256(payload).digest()
        return computed == expected_hash
\end{lstlisting}

\subsection{Properties}

\begin{theorem}[Tamper Evidence]
If an adversary modifies any gradient $\nabla_t$ after committing $h_t$, all subsequent hashes $h_{t+1}, h_{t+2}, \ldots$ become invalid.  Specifically, for the chain to remain consistent, the adversary must find a preimage collision in SHA3-256, which has complexity $O(2^{128})$.
\end{theorem}

\begin{proof}
The hash chain is a Merkle list.  Modifying $\nabla_t$ produces $\nabla'_t$ with $\text{SHA3-256}(\nabla'_t) \neq \text{SHA3-256}(\nabla_t)$ (collision resistance).  This yields $h'_t \neq h_t$, which propagates to $h'_{t+1} \neq h_{t+1}$, etc.  The final hash $h_T$ no longer matches the committed value.
\end{proof}

\begin{proposition}[Efficient Audit]
Given the full chain $\{h_0, \ldots, h_T\}$ and any single gradient $\nabla_t$, verification of step $t$ requires $O(1)$ hash computations.
\end{proposition}

\subsection{Submission}

At epoch end, the node submits:
\begin{itemize}
    \item The final hash $h_T$ (32 bytes).
    \item The delta $\delta$ (compressed tensors).
    \item The Ed25519 signature $\sigma$ over $(e, T, h_T, \text{SHA3-256}(\delta))$.
\end{itemize}

The orchestrator stores $h_T$ for potential spot-check verification.

%----------------------------------------------------------------------
\section{Spot-Verify Sampling}
\label{sec:spotcheck}

\subsection{Protocol}

\begin{algorithm}[t]
\caption{Spot-Verify Protocol}
\label{alg:spotcheck}
\begin{algorithmic}[1]
\REQUIRE Delta $\delta$, hash chain tip $h_T$, spot-check probability $p$
\STATE Draw $u \sim \text{Uniform}(0, 1)$
\IF{$u < p$}
    \STATE // Select random step to verify
    \STATE $t^* \leftarrow \text{Uniform}(\{1, \ldots, T\})$
    \STATE Request gradient $\nabla_{t^*}$ and chain prefix $\{h_0, \ldots, h_{t^*}\}$ from node
    \STATE // Re-execute step $t^*$
    \STATE Load model state at step $t^* - 1$ from checkpoint
    \STATE Load batch $B_{t^*}$ (deterministic from step number + dataset seed)
    \STATE $\nabla'_{t^*} \leftarrow \textsc{Forward+Backward}(\theta_{t^*-1}, B_{t^*})$
    \STATE // Verify
    \IF{$\|\nabla'_{t^*} - \nabla_{t^*}\|_2 / \|\nabla'_{t^*}\|_2 > \epsilon$}
        \STATE Flag node for slashing
    \ENDIF
    \STATE // Verify hash chain consistency
    \STATE Recompute $h_{t^*}$ from $h_{t^*-1}$, $t^*$, $\nabla_{t^*}$
    \IF{$h_{t^*}$ does not match submitted chain}
        \STATE Flag node for slashing
    \ENDIF
\ENDIF
\end{algorithmic}
\end{algorithm}

\subsection{Deterministic Seeding}

For spot-checks to be reproducible, the training step must be deterministic given:
\begin{enumerate}
    \item Model weights $\theta_{t-1}$ (from checkpoint).
    \item Batch $B_t$ (determined by $\text{seed} = \text{SHA3-256}(e \| t \| \text{dataset\_cid})$).
    \item Random number generator state (seeded by step number).
\end{enumerate}

\begin{lstlisting}[language=python,caption=Deterministic batch selection]
import hashlib, torch

def get_batch_indices(epoch: int, step: int,
                     dataset_cid: str,
                     dataset_size: int,
                     batch_size: int) -> list[int]:
    seed_bytes = hashlib.sha3_256(
        f"{epoch}|{step}|{dataset_cid}".encode()
    ).digest()
    seed = int.from_bytes(seed_bytes[:8], "little")
    rng = torch.Generator().manual_seed(seed)
    indices = torch.randperm(
        dataset_size, generator=rng
    )[:batch_size]
    return indices.tolist()
\end{lstlisting}

\subsection{Tolerance Bound}

Due to floating-point non-determinism across hardware, we allow a relative tolerance:

\begin{equation}
    \epsilon = \frac{\|\nabla' - \nabla\|_2}{\|\nabla'\|_2} \leq 0.05
    \label{eq:tolerance}
\end{equation}

This accommodates differences in GPU precision (FP16 rounding, fused multiply-add order) while detecting gross discrepancies (random gradients, zero gradients, stale replays).

\begin{lemma}[Tolerance Soundness]
For honest computation, the relative error between two executions of the same step on different hardware satisfies $\epsilon_{\text{honest}} < 0.01$ with probability $>0.999$.  The threshold $\epsilon = 0.05$ provides a $5\times$ margin.
\end{lemma}

This was measured empirically across A100, RTX 4090, and RTX 4080 hardware.

%----------------------------------------------------------------------
\section{Economic Security}
\label{sec:economics}

\subsection{Adversary's Decision}

A rational adversary chooses between:
\begin{enumerate}
    \item \textbf{Honest}: Pay cost $c_{\text{real}}$ per step, earn reward $r$.
    \item \textbf{Fake}: Pay cost $c_{\text{fake}} < c_{\text{real}}$ per step (e.g., submitting random data), earn reward $r$ if undetected, lose stake $s \cdot f_{\text{slash}}$ if detected.
\end{enumerate}

\subsection{Expected Payoff}

\begin{equation}
    \mathbb{E}[\pi_{\text{honest}}] = r - c_{\text{real}}
\end{equation}

\begin{equation}
    \mathbb{E}[\pi_{\text{fake}}] = (1 - p_d) \cdot r - c_{\text{fake}} - p_d \cdot s \cdot f_{\text{slash}}
    \label{eq:fake-payoff}
\end{equation}

where $p_d$ is the detection probability.  From the quality scoring, a fake delta gets $q_i \approx 0$ (zero convergence contribution), so in practice $r_{\text{fake}} \approx 0$ even if undetected.  This strengthens the bound, but we analyze the worst case where $r_{\text{fake}} = r$.

\subsection{Incentive Compatibility Condition}

Honest computation dominates when:

\begin{equation}
    \mathbb{E}[\pi_{\text{honest}}] > \mathbb{E}[\pi_{\text{fake}}]
\end{equation}

Substituting and simplifying:

\begin{equation}
    p_d \cdot (r + s \cdot f_{\text{slash}}) > c_{\text{real}} - c_{\text{fake}}
    \label{eq:ic-condition}
\end{equation}

\begin{theorem}[Minimum Spot-Check Rate]
Faking is unprofitable when the spot-check probability satisfies:
\begin{equation}
    p > \frac{c_{\text{real}} - c_{\text{fake}}}{r + s \cdot f_{\text{slash}}}
    \label{eq:min-p}
\end{equation}
\end{theorem}

\subsection{Zoo Gym Parameters}

\begin{table}[t]
\centering
\begin{tabular}{lr}
\toprule
\textbf{Parameter} & \textbf{Value} \\
\midrule
Spot-check probability $p$ & 0.10 \\
Minimum stake $s$ & 10{,}000 GYM \\
Slash fraction $f_{\text{slash}}$ & 0.50 \\
Reward per epoch $r$ & 8.4 GYM \\
Real compute cost $c_{\text{real}}$ & \$2.50 (GPU-hour) \\
\bottomrule
\end{tabular}
\caption{Zoo Gym economic parameters.}
\label{tab:params}
\end{table}

For faking to be profitable:

\begin{equation}
    c_{\text{fake}} < c_{\text{real}} - p \cdot (r + s \cdot f_{\text{slash}})
\end{equation}

\begin{equation}
    c_{\text{fake}} < 2.50 - 0.10 \cdot (8.4 + 5{,}000) = 2.50 - 500.84 < 0
\end{equation}

Since $c_{\text{fake}} \geq 0$, the condition is \textit{never satisfiable}: faking is always unprofitable under Zoo Gym's parameters.  The massive stake-to-reward ratio ($5{,}000:8.4 \approx 595:1$) provides overwhelming security margin.

\begin{corollary}
Even with spot-check probability $p = 0.001$ (0.1\%), faking remains unprofitable as long as $s \cdot f_{\text{slash}} > (c_{\text{real}} - c_{\text{fake}}) / p$.  For $c_{\text{real}} = \$2.50$ and $c_{\text{fake}} = \$0$: $s \cdot f_{\text{slash}} > \$2{,}500$, which holds for a 10{,}000 GYM stake valued at $>\$5$ per GYM.
\end{corollary}

%----------------------------------------------------------------------
\section{Slashing Conditions}
\label{sec:slashing}

\subsection{Offense Categories}

\begin{table}[t]
\centering
\begin{tabular}{llrl}
\toprule
\textbf{Category} & \textbf{Detection} & \textbf{Slash} & \textbf{Evidence} \\
\midrule
Invalid signature & Signature check & 5\% & $(\delta, \sigma, pk)$ \\
Hash chain break & Chain verification & 10\% & $(h_t, h_{t+1}, \nabla_t)$ \\
Spot-check failure & Re-execution & 25\% & $(\nabla, \nabla', \epsilon)$ \\
Gradient poisoning & Statistical outlier & 50\% & Norm/direction analysis \\
Collusion & Cross-node correlation & 50\% & Correlated deltas \\
\bottomrule
\end{tabular}
\caption{Slashing categories, detection methods, and penalties.}
\label{tab:slashing}
\end{table}

\subsection{Evidence Format}

Slashing requires on-chain evidence submission:

\begin{lstlisting}[language=Solidity,caption=Slashing evidence contract]
contract SlashingJury {
    struct Evidence {
        address accused;
        uint8 category; // 0-4 per table
        bytes32 deltaHash;
        bytes proof;
        uint256 timestamp;
    }

    function submitEvidence(Evidence calldata ev)
        external onlyOrchestrator {
        require(verifyProof(ev), "Invalid proof");
        uint256 slashPct = slashRates[ev.category];
        gymToken.slash(
            ev.accused, slashPct, msg.sender
        );
        emit NodeSlashed(
            ev.accused, ev.category, slashPct
        );
    }

    function verifyProof(Evidence calldata ev)
        internal view returns (bool) {
        if (ev.category == 0) {
            // Invalid signature: verify that sig
            // does NOT match registered key
            return !ed25519Verify(
                ev.deltaHash,
                ev.proof,
                registeredKeys[ev.accused]
            );
        } else if (ev.category == 1) {
            // Hash chain break: verify
            // recomputed hash differs
            return verifyHashChainBreak(ev.proof);
        }
        // ... other categories
        return false;
    }
}
\end{lstlisting}

\subsection{Progressive Penalties}

First offense: base rate (per Table~\ref{tab:slashing}).  Repeat offenses within 30 days: $2\times$ base rate.  Three offenses in 30 days: full stake slash and permanent ban.

\subsection{Appeal Process}

Slashed nodes may appeal within 7 days by submitting counter-evidence.  A governance vote (simple majority of GYM stakers) can reverse the slashing if the evidence is found insufficient.

%----------------------------------------------------------------------
\section{Toward Zero-Knowledge Proofs of Training}
\label{sec:zkpoc}

The spot-check approach requires the orchestrator to re-execute training steps, which is computationally expensive.  Zero-knowledge proofs of training (zkPoC) would allow full verification without re-execution.

\subsection{Architecture}

A zkPoC system proves the statement:

\begin{quote}
``I executed forward pass $f$ and backward pass $b$ on batch $B$ with weights $\theta$, producing gradient $\nabla$, such that $\|\nabla - \nabla_{\text{claimed}}\|_2 / \|\nabla\|_2 < \epsilon$.''
\end{quote}

\subsection{Challenges}

\begin{enumerate}
    \item \textbf{Circuit size}: A single forward pass of a 7B parameter model involves $\sim10^{12}$ floating-point operations.  Current zkSNARK circuits cannot handle this directly.
    \item \textbf{Floating-point arithmetic}: ZK circuits operate on finite fields, not IEEE 754 floats.  Fixed-point approximation introduces errors.
    \item \textbf{Proving time}: Even with recursive SNARKs, proving a single training step may take hours.
\end{enumerate}

\subsection{Tractable Approach: Partial Verification}

Instead of proving the entire training step, prove a subset:

\begin{enumerate}
    \item \textbf{Commitment}: Prove that $H(\nabla) = h_{\text{claimed}}$ (the gradient hash matches the chain entry).  This is already done by the hash chain.
    \item \textbf{Structural validity}: Prove that $\nabla$ has the correct shape and dtype for the model architecture.  This is a simple constraint circuit.
    \item \textbf{Statistical properties}: Prove that $\|\nabla\|_2 \in [0.5\bar{n}, 2\bar{n}]$ (gradient norm within expected range).  This requires $O(|\theta|)$ multiplications.
    \item \textbf{Random projection}: Prove that $\langle \nabla, r \rangle = v$ for a random vector $r$ chosen by the verifier.  By the Johnson-Lindenstrauss lemma, this preserves distance with high probability.
\end{enumerate}

\begin{proposition}[Random Projection Verification]
If a prover claims gradient $\nabla$ and the verifier checks $k$ random projections $\langle \nabla, r_j \rangle = v_j$, a fake gradient $\nabla'$ that differs from $\nabla$ by $\geq\delta$ in any coordinate is detected with probability $\geq 1 - (1 - \delta^2 / \|\nabla\|^2)^k$.  For $k = 128$ and $\delta / \|\nabla\| = 0.01$, detection probability exceeds $1 - 10^{-5}$.
\end{proposition}

\begin{lstlisting}[language=Rust,caption=Random projection proof generation]
pub fn generate_projection_proof(
    gradient: &Tensor,
    verifier_seed: &[u8; 32],
    num_projections: usize,
) -> Vec<(Vec<u8>, f64)> {
    let mut proofs = Vec::new();
    for j in 0..num_projections {
        let r = deterministic_random_vector(
            verifier_seed, j, gradient.len()
        );
        let projection = gradient.dot(&r);
        let r_hash = sha3_256(&r.to_bytes());
        proofs.push((r_hash.to_vec(), projection));
    }
    proofs
}

pub fn verify_projection_proof(
    claimed_gradient: &Tensor,
    proofs: &[(Vec<u8>, f64)],
    verifier_seed: &[u8; 32],
    tolerance: f64,
) -> bool {
    for (j, (r_hash, claimed_proj)) in
        proofs.iter().enumerate() {
        let r = deterministic_random_vector(
            verifier_seed, j, claimed_gradient.len()
        );
        assert_eq!(&sha3_256(&r.to_bytes())[..], &r_hash[..]);
        let actual_proj = claimed_gradient.dot(&r);
        if (actual_proj - claimed_proj).abs()
            / actual_proj.abs() > tolerance {
            return false;
        }
    }
    true
}
\end{lstlisting}

\subsection{zkML Research Directions}

Full zkPoC for training steps requires advances in:
\begin{enumerate}
    \item \textbf{zkML frameworks}: EZKL~\cite{ezkl2023}, zkLLM~\cite{sun2024zkllm}, and Modulus Labs' ZKML work toward proving inference.  Training proofs are harder (backward pass + optimizer state).
    \item \textbf{Recursive SNARKs}: Nova~\cite{kothapalli2022nova} and Supernova enable incremental verification, amortizing proof cost across steps.
    \item \textbf{Hardware acceleration}: FPGA-based provers~\cite{zhang2023pipezk} can parallelize MSM computations required for large circuits.
\end{enumerate}

%----------------------------------------------------------------------
\section{Evaluation}
\label{sec:evaluation}

\subsection{Setup}

32-node ring training Qwen3-2507 (QLoRA, 50 epochs, 100K samples).  Injected attacks: 3 nodes submitting random gradients, 2 nodes replaying stale deltas, 1 node submitting poisoned gradients (biased toward a specific output).

\subsection{Detection Results}

\begin{table}[t]
\centering
\begin{tabular}{lccc}
\toprule
\textbf{Attack} & \textbf{Nodes} & \textbf{Detected} & \textbf{Epochs to Detect} \\
\midrule
Random gradients & 3 & 3/3 & 1 (quality score = 0) \\
Replay (stale delta) & 2 & 2/2 & 1 (signature check) \\
Gradient poisoning & 1 & 1/1 & 4 (spot-check) \\
\bottomrule
\end{tabular}
\caption{Attack detection results.}
\label{tab:detection}
\end{table}

Random gradients are detected immediately by the quality scoring system ($q_i = 0$ due to zero convergence contribution).  Replay attacks are detected by the epoch/step binding in Ed25519 signatures.  Gradient poisoning (subtle bias) requires spot-check re-execution and is detected within 4 epochs.

\subsection{Spot-Check Overhead}

\begin{table}[t]
\centering
\begin{tabular}{lcc}
\toprule
\textbf{Spot-Check Rate} & \textbf{Overhead} & \textbf{Detection Rate (poison)} \\
\midrule
5\% & 2.1\% wall-clock & 41\% after 10 epochs \\
10\% & 4.3\% wall-clock & 65\% after 10 epochs \\
20\% & 8.7\% wall-clock & 88\% after 10 epochs \\
\bottomrule
\end{tabular}
\caption{Spot-check overhead and detection effectiveness.}
\label{tab:overhead}
\end{table}

At 10\% spot-check rate, the wall-clock overhead is 4.3\%---the orchestrator must re-execute 10\% of steps, but this is parallelized with ongoing training.

\subsection{Hash Chain Verification}

\begin{table}[t]
\centering
\begin{tabular}{lc}
\toprule
\textbf{Metric} & \textbf{Value} \\
\midrule
Hash chain entries per epoch & 2{,}000 \\
Chain verification time (single step) & 0.4 ms \\
Full chain verification (per epoch) & 0.8 s \\
Storage per node per epoch & 64 KB \\
\bottomrule
\end{tabular}
\caption{Hash chain performance metrics.}
\label{tab:hashchain}
\end{table}

\subsection{Random Projection Proofs}

\begin{table}[t]
\centering
\begin{tabular}{lccc}
\toprule
\textbf{Projections ($k$)} & \textbf{Proof Size} & \textbf{Gen.\ Time} & \textbf{Verify Time} \\
\midrule
32 & 1.2 KB & 12 ms & 8 ms \\
64 & 2.4 KB & 24 ms & 16 ms \\
128 & 4.8 KB & 48 ms & 31 ms \\
\bottomrule
\end{tabular}
\caption{Random projection proof performance (LoRA delta, 16M parameters).}
\label{tab:projection}
\end{table}

Random projection proofs are fast enough for per-step verification.  128 projections detect any gradient deviation $>$1\% of norm with probability $>0.99999$.

%----------------------------------------------------------------------
\section{Related Work}

\textbf{Proof-of-useful-work.}  Primecoin~\cite{king2013primecoin} proves prime finding; Gridcoin~\cite{gridcoin2014} credits BOINC compute.  Neither provides verifiable ML training proofs.

\textbf{Verifiable computation.}  Pinocchio~\cite{parno2013pinocchio} and Groth16~\cite{groth2016size} prove arbitrary circuits but are infeasible for large ML models.

\textbf{zkML.}  EZKL~\cite{ezkl2023} proves neural network inference in ZK circuits.  zkLLM~\cite{sun2024zkllm} extends this to transformer attention.  Neither addresses training verification.

\textbf{Trusted execution.}  Intel SGX~\cite{costan2016intel} and ARM TrustZone provide hardware attestation but require specific hardware and have been subject to side-channel attacks~\cite{vanBulck2018foreshadow}.

\textbf{Optimistic verification.}  Gensyn~\cite{gensyn2023} uses probabilistic spot-checking similar to our approach but lacks the economic security formalization and gradient hash chain.

\textbf{Federated learning verification.}  Bonawitz et al.~\cite{bonawitz2019towards} study secure aggregation in federated learning.  Our work focuses on verifying individual contributions rather than aggregate privacy.

%----------------------------------------------------------------------
\section{Conclusion}

The Proof-of-Compute framework provides layered security for decentralized training: Ed25519 signatures for identity binding, SHA3-256 hash chains for trajectory integrity, and spot-verify sampling for correctness.  Under Zoo Gym's parameters, faking compute is always unprofitable---the stake-to-reward ratio provides a $595:1$ security margin.  Random projection proofs offer a practical stepping stone toward full zkPoC, enabling per-step verification at 48ms per proof.  The path to zero-knowledge proofs of training is open but requires advances in zkML circuit design and recursive SNARK efficiency.

\section*{Acknowledgments}

This work was supported by Zoo Labs Foundation.

\bibliographystyle{plain}
\begin{thebibliography}{30}

\bibitem{bernstein2012ed25519}
D.~J.~Bernstein, N.~Duif, T.~Lange, P.~Schwabe, and B.~Yang, ``High-Speed High-Security Signatures,'' \textit{J. Cryptographic Engineering}, 2(2):77--89, 2012.

\bibitem{shao2024deepseekmath}
Z.~Shao et al., ``DeepSeekMath: Pushing the Limits of Mathematical Reasoning,'' \textit{arXiv:2402.03300}, 2024.

\bibitem{schulman2017proximal}
J.~Schulman et al., ``Proximal Policy Optimization Algorithms,'' \textit{arXiv:1707.06347}, 2017.

\bibitem{king2013primecoin}
S.~King, ``Primecoin: Cryptocurrency with Prime Number Proof-of-Work,'' 2013.

\bibitem{gridcoin2014}
Gridcoin, ``Rewarding BOINC Contributions with Blockchain,'' Whitepaper, 2014.

\bibitem{parno2013pinocchio}
B.~Parno, J.~Howell, C.~Gentry, and M.~Raykova, ``Pinocchio: Nearly Practical Verifiable Computation,'' \textit{IEEE S\&P}, 2013.

\bibitem{groth2016size}
J.~Groth, ``On the Size of Pairing-Based Non-Interactive Arguments,'' \textit{EUROCRYPT}, 2016.

\bibitem{ezkl2023}
EZKL, ``EZKL: Easy Zero-Knowledge Inference,'' \url{https://github.com/zkonduit/ezkl}, 2023.

\bibitem{sun2024zkllm}
H.~Sun, J.~Hulse, and T.~Ristenpart, ``zkLLM: Zero Knowledge Proofs for Large Language Models,'' \textit{arXiv:2404.16109}, 2024.

\bibitem{kothapalli2022nova}
A.~Kothapalli, S.~Setty, and I.~Tzialla, ``Nova: Recursive Zero-Knowledge Arguments from Folding Schemes,'' \textit{CRYPTO}, 2022.

\bibitem{zhang2023pipezk}
Y.~Zhang et al., ``PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture,'' \textit{ISCA}, 2021.

\bibitem{costan2016intel}
V.~Costan and S.~Devadas, ``Intel SGX Explained,'' \textit{Cryptology ePrint Archive}, 2016.

\bibitem{vanBulck2018foreshadow}
J.~Van~Bulck et al., ``Foreshadow: Extracting the Keys to the Intel SGX Kingdom,'' \textit{USENIX Security}, 2018.

\bibitem{gensyn2023}
Gensyn, ``Gensyn Protocol: Trustless Training of Deep Neural Networks,'' Whitepaper, 2023.

\bibitem{bonawitz2019towards}
K.~Bonawitz et al., ``Towards Federated Learning at Scale: A System Design,'' \textit{SysML}, 2019.

\bibitem{yin2018byzantine}
D.~Yin et al., ``Byzantine-Robust Distributed Learning,'' \textit{ICML}, 2018.

\bibitem{mcmahan2017communication}
H.~B.~McMahan et al., ``Communication-Efficient Learning of Deep Networks,'' \textit{AISTATS}, 2017.

\bibitem{blanchard2017machine}
P.~Blanchard et al., ``Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent,'' \textit{NeurIPS}, 2017.

\bibitem{shazeer2017outrageously}
N.~Shazeer et al., ``Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer,'' \textit{ICLR}, 2017.

\bibitem{bittensor2023}
Opentensor Foundation, ``Bittensor: A Peer-to-Peer Intelligence Market,'' Whitepaper, 2023.

\bibitem{hu2021lora}
E.~J.~Hu et al., ``LoRA: Low-Rank Adaptation of Large Language Models,'' \textit{ICLR}, 2022.

\bibitem{dettmers2023qlora}
T.~Dettmers et al., ``QLoRA: Efficient Finetuning of Quantized Language Models,'' \textit{NeurIPS}, 2023.

\bibitem{touvron2023llama}
H.~Touvron et al., ``LLaMA 2: Open Foundation and Fine-Tuned Chat Models,'' \textit{arXiv:2307.09288}, 2023.

\bibitem{ipfs2014}
J.~Benet, ``IPFS -- Content Addressed, Versioned, P2P File System,'' \textit{arXiv:1407.3561}, 2014.

\bibitem{ethereum2014}
V.~Buterin, ``Ethereum Whitepaper,'' 2014.

\bibitem{sergeev2018horovod}
A.~Sergeev and M.~Del~Balso, ``Horovod: Fast and Easy Distributed Deep Learning,'' \textit{arXiv:1802.05799}, 2018.

\bibitem{vonwerra2022trl}
L.~von~Werra et al., ``TRL: Transformer Reinforcement Learning,'' \url{https://github.com/huggingface/trl}, 2022.

\bibitem{patarasuk2009bandwidth}
P.~Patarasuk and X.~Yuan, ``Bandwidth Optimal All-Reduce Algorithms,'' \textit{J. Parallel Distrib. Comput.}, 2009.

\bibitem{filecoin2017}
Protocol Labs, ``Filecoin: A Decentralized Storage Network,'' Whitepaper, 2017.

\bibitem{nist2024pqc}
NIST, ``Post-Quantum Cryptography Standards: ML-KEM, ML-DSA, SLH-DSA,'' FIPS 203/204/205, 2024.

\end{thebibliography}

\end{document}