Proof-of-learning (PoL) proposes a model owner use machine learning training
checkpoints to establish a proof of having expended the necessary compute for
training. The authors of PoL forego cryptographic approaches and trade rigorous
security guarantees for scalability to deep learning by being applicable to
stochastic gradient descent and adaptive variants. This lack of formal analysis
leaves the possibility that an attacker may be able to spoof a proof for a
model they did not train.
We contribute a formal analysis of why the PoL protocol cannot be formally
(dis)proven to be robust against spoofing adversaries. To do so, we disentangle
the two roles of proof verification in PoL: (a) efficiently determining if a
proof is a valid gradient descent trajectory, and (b) establishing precedence
by making it more expensive to craft a proof after training completes (i.e.,
spoofing). We show that efficient verification results in a tradeoff between
accepting legitimate proofs and rejecting invalid proofs because deep learning
necessarily involves noise. Without a precise analytical model for how this
noise affects training, we cannot formally guarantee if a PoL verification
algorithm is robust. Then, we demonstrate that establishing precedence robustly
also reduces to an open problem in learning theory: spoofing a PoL post hoc
training is akin to finding different trajectories with the same endpoint in
non-convex learning. Yet, we do not rigorously know if priori knowledge of the
final model weights helps discover such trajectories.
We conclude that, until the aforementioned open problems are addressed,
relying more heavily on cryptography is likely needed to formulate a new class
of PoL protocols with formal robustness guarantees. In particular, this will
help with establishing precedence. As a by-product of insights from our
analysis, we also demonstrate two novel attacks against PoL.

本文对 Proof-of-learning（一种基于机器学习的训练检查点建立验证机制）进行了形式化分析，发现其存在容易被攻击者欺骗的漏洞，并提出在保护 Proof-of-learning 的真实性方面需要更多地借助密码学的方法。

关于正式（非）证明学习证明中鲁棒性的根本限制

On the Fundamental Limits of Formally (Dis)Proving Robustness in Proof-of-Learning

Training machine learning (ML) models typically involves expensive iterative
optimization. Once the model's final parameters are released, there is
currently no mechanism for the entity which trained the model to prove that
these parameters were indeed the result of this optimization procedure. Such a
mechanism would support security of ML applications in several ways. For
instance, it would simplify ownership resolution when multiple parties contest
ownership of a specific model. It would also facilitate the distributed
training across untrusted workers where Byzantine workers might otherwise mount
a denial-of-service by returning incorrect model updates.
In this paper, we remediate this problem by introducing the concept of
proof-of-learning in ML. Inspired by research on both proof-of-work and
verified computations, we observe how a seminal training algorithm, stochastic
gradient descent, accumulates secret information due to its stochasticity. This
produces a natural construction for a proof-of-learning which demonstrates that
a party has expended the compute require to obtain a set of model parameters
correctly. In particular, our analyses and experiments show that an adversary
seeking to illegitimately manufacture a proof-of-learning needs to perform *at
least* as much work than is needed for gradient descent itself.
We also instantiate a concrete proof-of-learning mechanism in both of the
scenarios described above. In model ownership resolution, it protects the
intellectual property of models released publicly. In distributed training, it
preserves availability of the training procedure. Our empirical evaluation
validates that our proof-of-learning mechanism is robust to variance induced by
the hardware (ML accelerators) and software stacks.

此研究的目的是实现机器学习中证明训练过程的机制 ——proof-of-learning。作者观察到随机梯度下降算法具有积累秘密信息的性质，并构建了一种自然的证明机制来证明一个实体已经正确地完成了模型参数优化过程，进而保护模型的知识产权。同时，该证明机制也保持了训练过程的可用性，可以在多方争议模型所有权的情况下使用。实验证明，该机制在硬件和软件环境的变化下仍能保持鲁棒性。