Proof-of-Learning: Definitions and Practice

I. INTRODUCTION

• Without a way to prove training, model owners cannot substantiate ownership claims, and distributed workers’ computations lack the desired integrity guarantees.The motivating settings include publicly released or stolen models and untrusted workers that might return incorrect updates.Source: §I · p. 1
• PoL records training-derived information so a prover can demonstrate both expended optimization work and correct computation, unlike proof-of-work schemes aimed at making computation costly.The verifier can re-execute selected gradient-descent steps from the recorded intermediate states, batch indices, and training information.Source: §I · pp. 1–2

A. Proof-of-Work in Cryptography

• Conventional proof systems often verify outsourced computation by duplicated execution, while PoL uses gradient-descent operations already performed during training to help generate the proof.The verifier may check only a subset of steps, trading verification cost against confidence.Source: §I · pp. 1–2

I. INTRODUCTION

• Inverting gradient descent to manufacture a proof takes at least as much work as training, making this spoofing strategy computationally unattractive.The paper’s analysis attributes the asymmetry to the many possible training sequences arising from stochasticity.Source: §I · p. 2

B. Security in ML Systems

• Existing model-extraction defenses can trade model utility or watermark robustness for protection, whereas the paper says PoL does not alter training or restrict information released at inference.The paper relates its use cases to model stealing and Byzantine-tolerant distributed learning.Source: B. Security in ML Systems · pp. 2–3

C. Byzantine-tolerant distributed ML

• Distributed-learning workers may return arbitrarily corrupted updates, and verifiable PoL is presented as a defense against denial-of-service and a way to check their computations.Workers receive batches, perform gradient-descent steps, and synchronize parameters with the model owner.Source: C. Byzantine-tolerant distributed ML · p. 3

III. BACKGROUND ON MACHINE LEARNING

• The paper treats deep-learning training as iterative stochastic gradient descent over batches, producing successive model weights across training steps.A full pass through the training data is an epoch, and total steps equal epochs times steps per epoch.Source: §III · p. 3

IV. FORMALIZING POL

• PoL is intended to verify training integrity for ownership claims and outsourced computation, without changing the model architecture or training algorithm beyond additional logging.A verifier reconstructs the proof to determine whether the prover performed the computation required to obtain the final model.Source: §IV · pp. 3–4

A. Threat Model

• The adversary may know the model, parameters, optimizer, hyperparameters, and training data, but is assumed not to know the trainer’s batching, initialization, seeds, or hardware randomness.Spoofing includes recreating the same proof, producing another valid one, making an invalid proof pass verification, or using a modified model.Source: A. Threat Model · p. 4

B. Protocol Overview

• A prover trains from random or previously proven initial weights, accumulates secret information, and returns requested portions so a verifier can assess the proof’s validity.The protocol seeks to make reconstructing the secret information or another valid proof at lower cost than proof generation infeasible.Source: B. Protocol Overview · p. 4

C. Defining PoL

• A PoL comprises ordered training-step records of model-specific information, data-point indices, data signatures, and auxiliary information needed to recreate and verify training states.The stated desiderata include correctness, security, efficient verification, model agnosticism, limited overhead, and concise proofs.Source: C. Defining PoL · pp. 4–5

V. A POL MECHANISM BASED ON GRADIENT DESCENT

• The mechanism relies on gradient descent being difficult to invert and reveals intermediate weights or updates together with the training-data indices used to compute them.The proof is encrypted for the verifier, who can authenticate, decrypt, and re-execute selected updates using the associated information.Source: §V · p. 5, A. Mechanism Overview · p. 5

A. Mechanism Overview

• Selective verification lets the verifier recompute chosen training steps rather than every step, trading verification cost against confidence in the proof.When data release is delayed, the proof includes training-data signatures to guard against later synthesis of data that would validate an invalid proof.Source: A. Mechanism Overview · p. 5

B. PoL Creation

• Every kth training step, proof creation stores the model weights; it also records batch indices and signatures so the stored states can be checked against the training data.Increasing the checkpointing interval reduces storage, but can reduce verification accuracy.Source: B. PoL Creation · pp. 5–6

C. PoL Verification

• The verifier checks initial-weight provenance, ranks checkpoint-to-checkpoint updates by magnitude, and re-executes selected largest updates against the claimed weights.For lazy data release, the proof’s data signatures help ensure queried samples match those used during training.Source: C. PoL Verification · p. 6
• Verification accepts an update when the recomputed and claimed weights are within a calibrated slack, with a larger query budget or shorter checkpoint interval making verification more stringent.The slack accounts for hardware, model, dataset, checkpointing, and learning-hyperparameter variation; verification costs O(E·Q·k·C|W|).Source: C. PoL Verification · pp. 6–7

• The section discusses practical considerations for implementing the mechanism.Source: D. Practical Considerations · p. 7

1) Private Datasets & Lazy Verification:

• For private datasets, the trainer publishes signatures of sampled datapoints rather than the dataset, then reveals the data for signature checks when verification is needed.This permits verification to be delayed until necessary.Source: 1) Private Datasets & Lazy Verification · p. 7

2) Amount of Data Needed:

• Expected data transfer under lazy verification is modeled as a function of S, E, k, and Q, assuming equal sampling likelihood and a fixed Q across epochs.The supplied text does not give a complete expression for the expectation.Source: 2) Amount of Data Needed · p. 7

3) Initial State Provenance and Chain of Trust:

• Because a warm-started model could be fine-tuned from stolen weights and presented as starting from a lucky initialization, the authors propose chaining its PoL to a previously published proof for its initial state.The verifier can reuse a recorded initial proof or verify it if it has not been recorded.Source: 3) Initial State Provenance and Chain… · p. 7
• Without a prior proof for a warm start, the trainer should provide the claimed initialization distribution and strategy, which the verifier checks statistically against the initial parameters.Source: 3) Initial State Provenance and Chain… · p. 8

4) Verifying Initialization:

• A single-trial Kolmogorov–Smirnov test checks each layer’s weights against the claimed initialization distribution; the procedure assumes layer independence and a publicly chosen initialization strategy.A layer fails if its p-value is below the chosen significance level; otherwise multiple-testing correction is needed when layers are not independent.Source: 4) Verifying Initialization · p. 8

VI. CORRECTNESS ANALYSIS OF THE GRADIENT DESCENT MECHANISM FOR PROOF-OF-LEARNING

• The verifier checks PoL updates step-wise rather than validating only the end-to-end sequence, so it can assess the validity of each recorded step.Source: §VI · p. 8

A. Stationary Markov Process

• With fixed architectural randomness, gradient-based stochastic optimization is a stationary Markov process, so its next-step progression depends on the current state rather than the full history.Source: A. Stationary Markov Process · p. 8

B. Entropy Growth

• Training-process entropy grows linearly with the number of steps, implying an exponential growth in possible sequences and making exact reproduction difficult.The stated result assumes some i.i.d. noise from hardware and low-level libraries; the authors say it renders retraining-based spoofing impossible even with identical initialization and batching.Source: B. Entropy Growth · pp. 8–9

1) Experimental Setup:

• The experiments evaluate ResNet-20 and ResNet-50 on CIFAR-10 and CIFAR-100, training each model for 200 epochs with batch size 128.The datasets contain 50,000 training and 10,000 test images each; CIFAR-100 has 100 classes versus CIFAR-10’s 10.Source: 1) Experimental Setup · p. 9

2) Metrics For Evaluation:

• Reproduction error must remain small relative to dref, the distance between independently trained models, and full-sequence noise accumulation makes sufficiently short checkpoint intervals necessary.Source: 2) Metrics For Evaluation · p. 9
• With k = 1, step-by-step reproduction yields negligible εrepr(t), while reproducing the entire sequence produces large error as entropy accumulates.Source: Table I · p. 9, 2) Metrics For Evaluation · p. 9
• For ResNet-20, deterministic operations halve ||εrepr|| versus nondeterministic operations, but incur substantial training cost and over a one-percentage-point accuracy drop; ResNet-50 shows no such error reduction.The authors suggest the randomness reduction available in PyTorch may not capture ResNet-50’s main randomness source.Source: 3) Deterministic Operations · p. 9

4) Checkpointing Interval and Storage Cost:

• At 1× storage overhead, reproduction error remains significantly below 1; roughly epoch-spaced checkpoints also preserve training speed and model accuracy.The authors report that using k ≈ S outperforms deterministic operations for CIFAR-10 without affecting training speed or accuracy.Source: 4) Checkpointing Interval and Storage… · pp. 9–10, Figure 2 · p. 10

5) Varying Learning Rate:

• When η is set to 1, reproduction error increases significantly; values an order of magnitude smaller than 100 have no significant impact.The authors suggest that an overly large learning rate may destabilize training, so tiny differences can lead to distinct parameters after a few steps.Source: Figure 3 · p. 10, 5) Varying Learning Rate · p. 10

D. Initialization Verification

• 7 ResNet-20 updates and 1 ResNet-50 update on average bring KS-test p-values below 0.01, while validation accuracy remains only slightly above random guessing.The minimum p-value across network layers drops rapidly, indicating at least one layer differs statistically from its claimed initialization distribution.Source: Table II · p. 10, D. Initialization Verification · p. 10

VII. SECURITY ANALYSIS OF THE GRADIENT DESCENT MECHANISM FOR PROOF-OF-WORK

• Controlling the number of possible gradient-descent sequences through checkpoint intervals supports verification and disadvantages adversaries attempting structurally correct spoofs.The analysis considers two spoofing strategy classes.Source: §VII · p. 10

A. Defining a Spoof

• An honest spoof may retrain to comparable performance at expected cost at least as high as the trainer’s; a dishonest spoof passes verification at lower expected cost.Attacks leveraging final weights are framed as directed retraining or inverse-gradient methods.Source: A. Defining a Spoof · p. 11

B. Inverse Gradient Methods

• Inverse gradient methods iteratively solve backward from final weights to a justified initialization; the proposed top-Q verification strategy is stated to prevent this spoof.The approach is analogous to the Euler Backward method for iteratively maximizing loss.Source: B. Inverse Gradient Methods · p. 11

1) Entropy for the Inverse Gradient Process:

• The reverse training process has entropy at least equal to the forward process, with equality only when the conditional inverse gradient is deterministic.When inverse steps have multiple possible solutions, inverse entropy is higher and greater variance in inverse paths is expected.Source: 1) Entropy for the Inverse Gradient… · p. 11

2) Retraining-based Spoofing:

• For sufficiently long training sequences, the probability of exactly reconstructing a specific path is negligible, and reported reproducibility results support this for DNN training lengths.The analysis relates the growing entropy to an exponential increase in paths reaching the final weights.Source: 2) Retraining-based Spoofing · pp. 11–12

3) Stochastic Spoofing:

• Inverting a training step is at least as computationally expensive as a training step, and the paper conjectures this holds for numerical root finding over a sequence.The conjecture is stated for the same model and is not presented as formally proved.Source: 3) Stochastic Spoofing · p. 12
• Above learning rates of 10^-4, reconstruction error quickly rises after a few inverse steps, and ResNet inversions also have greater average error than training with k = 1.The experiments also report that inverse-gradient methods are unlikely to find an initialization that passes the verifier's KS test.Source: 3) Stochastic Spoofing · p. 12

C. Directed Retraining

• In concatenated proofs, the discontinuity is much larger than valid updates, so checking the largest update can detect the spoof; random sampling may miss it.In the reported setup, Q = 1 suffices, while randomly sampling E steps gives probability 1/S of finding the discontinuity, with S = 390.Source: 1) Approach 1: PoL Concatenation · p. 13, Figure 5 · p. 13
• If the adversary knows Q or Q is small, arbitrarily large learning rates may enable Q legitimate updates per epoch and bypass Algorithm 2.Suggested responses include increasing Q, randomly checking additional updates, or periodically checking model performance.Source: 1) Approach 1: PoL Concatenation · p. 13
• Directed weight minimization fails verification because its custom regularizer requires final weights before they have been achieved, and its gradient cannot be distilled into synthetic data.Optimizing the learning rate to converge toward the final weights also fails verification.Source: 2) Approach 2: Directed Weight… · p. 13

VIII. DISCUSSIONS & LIMITATIONS

• A PoL supports ownership claims for the exact trained model, but does not connect it to a surrogate or prevent model extraction.With a chain of trust, the guarantee extends to using that model as an initial state for surrogate training; a timestamped signature provides a legal record against false ownership claims.Source: §VIII · p. 13
• Verification requires sharing training data with the verifier; private inference using multi-party computation can protect confidentiality but adds scheme-dependent overhead.The additional overhead depends on the chosen private inference scheme.Source: §VIII · p. 13
• The proof-of-work has considerable storage requirements, and float16 saves a factor of 2 over float32 with minimal verification error.Merkle-tree hashing is not used because reconstruction error can make verifier and worker hashes differ; fuzzy extractors or locality-sensitive hashing require finding a suitable bound across choices of E, Q, and k.Source: §VIII · p. 13
• Counter-based pseudorandom number generators could remove most, if not all, training noise, but ground truth for all randomness sources is currently unavailable.Such ground truths would make training more reproducible and facilitate the approach.Source: §VIII · pp. 13–14
• Verification success probability degrades multiplicatively with each use, limiting extremely long chains of PoLs; the paper leaves this issue for future work.The stated example is successive transfer learning between many models where any given success probability is significantly below 1.Source: §VIII · p. 14

IX. CONCLUSIONS

• Gradient descent’s stochasticity naturally produces secret information that can serve as PoL, while entropy growth creates an asymmetry favoring the defender.The approach requires no changes to existing training and adds little prover overhead.Source: §IX · p. 14

APPENDIX A MARKOV PROCESSES AND ENTROPY

• A Markov process has a future independent of its past conditioned on its current state; entropy is presented as information needed to describe a random variable.The appendix also gives formal definitions for discrete entropy, cross-entropy, and entropy rates of stationary stochastic and stationary Markov processes.Source: Appendix A · p. 16
• The appendix defines discrete entropy, cross-entropy, and entropy rates for stationary stochastic and stationary Markov processes.The entropy-rate limit is stated to exist.Source: Appendix A · p. 16

APPENDIX B INFEASIBILITY OF DIRECTED RETRAINING

• An adversary can add a regularizer that minimizes the distance between its weights and the prover’s final weights, but this requires the final weights as an additional state without a valid PoL.The state also does not pass the KT test.Source: Appendix B · pp. 16–17
• Gradient-based optimization cannot distill the targeted information into input x because the relevant gradient does not exist; gradient-free optimization requires far more function calls than training.The paper attributes the gradient-free cost to the highly nonlinear relation between x and ∇f(x)(L).Source: Appendix B · p. 17

APPENDIX C TABLE OF NOTATIONS

• Table IV is a reference for the paper’s notations.The supplied table passage gives its title but no individual notation entries.Source: Table IV · p. 17

APPENDIX E ADDITIONAL FIGURES AND TABLES

• CIFAR-100 has significantly higher memory cost than CIFAR-10 because the experiment uses a much deeper model; the table defines dref as average parameter distance between independently trained models of the same architecture and dataset.Figure 6 expresses memory cost in megabytes.Source: Figure 6 · p. 17, Table V · p. 17

APPENDIX D NOTES FROM SPOOFING SECTIONS

• Figure 7 relates verification time, as a proportion of training time, to checkpoint interval k and Q, and applies to datasets with 50,000 training samples.The caption says verification then depends on k, Q, and training-dataset size.Source: Figure 7 · p. 17
• Newton Krylov converged fastest among gradient descent on the l2-norm, Newton Krylov, and Broyden1; inversion complexity is measured by function calls per step and can be converted to FLOPs.The appendix reports Newton Krylov converging to zero, gradient descent converging linearly, and Broyden’s method converging below 1e −7 in l∞ norm.Source: Appendix D · p. 17, Figure 9 · p. 18, Figure 8 · p. 18

APPENDIX E ADDITIONAL FIGURES AND TABLES

• For LeNet5, inversion’s l∞ error is several orders of magnitude higher as learning rate increases from 0.1 to 0.01; the cosine measure relative to the trained sequence steadily decreases across tested rates.For larger learning rates, numerical methods cannot converge to a sufficiently small error.Source: Figure 11 · p. 18, Figure 15 · p. 18, Figure 13 · p. 18

APPENDIX D NOTES FROM SPOOFING SECTIONS

• In the tested setup, inversion function calls are a magnitude or more above the training baseline across learning rates.The training baseline is y = x; the appendix describes the current setup as magnitudes more expensive and leaves improvement for future work.Source: Appendix D · p. 17, Figure 14 · p. 18, Figure 12 · p. 18