学习证明（Proof-of-Learning）：定义与实践

1. 01这篇论文试图解决什么问题？

   模型训练者无法证明自己完成了训练计算，论文提出 proof-of-learning 概念与机制来解决。

   核心问题：训练出的模型参数发布后，训练者没有任何机制证明这些参数确实是自己执行优化过程得到的。

   • 应用场景：作者指出两类场景需要这种证明。其一，模型被公开发布或被盗后，所有者在模型窃取（model stealing）纠纷中主张所有权；其二，模型所有者把训练分发给不可信 worker 时，需要确认 worker 返回的更新计算正确，以抵御 Byzantine worker 发起的拒绝服务攻击。
   • 现有方法不足：作者称，针对模型窃取的两类现有防御各有代价：限制查询返回的信息会损害模型效用；水印需要修改训练过程，且部署后可能被移除或失效。可验证计算（verified computations）领域的已有工作针对推理而非训练设计，且需要为密码学原语修改算法。
   • 核心观察：作者观察到 SGD 的随机性（批划分、初始化、硬件与底层库噪声）使训练过程积累秘密信息，且梯度下降难以逆向；正向训练比重放或逆向构造一条训练序列更高效，这构成 PoL 的自然基础。
   • 论文贡献：作者形式化了 PoL 的定义、性质与协议（§IV），给出基于梯度下降的具体机制（§V），在 §VI 证明其正确性并做复现实验，在 §VII 分析熵增与多种伪造策略的安全性。
   • 威胁模型（§IV-A）：
     • 目标：对抗者 A 以低于证明者训练代价的计算量伪造能通过验证的 PoL（dishonest spoofing），分 retraining-based、stochastic、structurally correct、distillation-based 四类。
     • 知识：A 完全知晓模型架构与权重、损失函数、优化器和其他超参数。
     • 能力：A 可完整访问并修改训练数据集，但目的不是推断数据隐私而是伪造 PoL。
     • 限制：A 无法获得 T 的各随机性来源，包括批划分、参数初始化、随机种子及硬件加速器等内在随机性。

   收起这一问

2. 02有哪些相关研究？

   相关工作分三组：密码学 proof-of-work、模型窃取与其防御、Byzantine 容错分布式学习。

   Proof-of-Work（PoW）密码学

   • Dwork and Naor [12] 提出 PoW 概念，最初用于防御针对邮件与网络服务的 DoS 攻击；Jakobsson and Juels [13] 引入 PoW 一词，其关键性质是依赖单向函数在计算方与验证方之间建立不对称性。
   • 后续 PoW 函数包括 partial hash inversion [13]、memory-bound 函数 [23]、guided tour puzzle [24]、Merkle-tree-based [26]、Cuckoo cycle [28] 等；Bitcoin 与 HashCash [29], [30] 等加密货币也采用 PoW。作者指出本文目标与 PoW 不同：不是让计算变昂贵以抑制 DoS。

   模型窃取与所有权防御

   • 模型抽取攻击：Tramèr 等 [5] 及后续工作 [6]–[9] 通过查询受害模型、用替代数据集重训练功能相近的代理模型；也有利用侧信道信息的攻击 [38]。
   • 已有防御分两类：限制每次查询返回的信息 [5], [39]，以及判断可疑模型是否为被盗副本——水印触发器 [40]–[42] 或 dataset inference [43]。论文指出前者以效用为代价，水印则需在效用与鲁棒性间权衡、修改训练过程且可能被移除 [51]–[53]；作者称本文不影响训练、不限制推理时释放的信息，且 PoL 不可变。

   Byzantine 容错分布式 ML

   • 分布式训练 [10], [54] 中 worker 可能是 Byzantine [55] 的，任意行事并返回损坏的更新 [11]；已有工作研究对此鲁棒的训练算法。作者将可验证 PoL 定位为该场景下防御 DoS、确认 worker 计算正确性的手段。

   可验证计算

   • 验证外包计算结果的工作 [16]–[20] 及推理阶段的完整性机制（如 SafetyNets [14]、zkSNARK 类训练验证 [63]–[65]）被提及；论文指出这些工作不是为训练算法设计、需要修改算法以适配密码学原语，而本文只需额外日志记录。

   定位：作者称本文与上述工作的区别在于：不改训练过程、不影响模型效用，利用梯度下降难以逆向这一性质，为训练阶段本身提供可验证的完整性证明。

   收起这一问

3. 03论文如何解决这个问题？

   证明者发布训练中周期性 checkpoint 与批次索引作为 PoL，验证者重放每 epoch 最大 Q 段更新并比对。

   整体思路：proof-of-learning（PoL） 利用梯度下降难以逆向的性质——证明者 T 记录训练中的中间权重与所用数据批次，验证者 V 通过重新执行部分梯度步来确认计算确实发生。

   形式化与性质

   • PoL 定义为 P(T, f_WT) = (W, I, H, A)：W 为训练中获得的模型状态（按 checkpoint 间隔记录），I 为各步所用数据点索引，H 为训练数据点的签名，A 为辅助信息（论文只保留超参数 M）。
   • 两条代价性质：验证期望代价不高于训练（E[CV] ≤ E[CT]）；任何伪造策略的期望代价不低于训练（E[CT] ≤ E[CA]）。
   • 六项设计目标 G1–G6：正确性、安全性、验证效率（含跨硬件验证）、模型无关、低开销、证明简洁。

   PoL 创建（Algorithm 1）

   • T 训练 E 个 epoch、每 epoch S 步，每第 k 步把权重 Wt 追加进 W（k 为 checkpointing interval），其余位置记空；同时记录每步批次索引 It、数据签名 h(D[It]) 与元数据 Mt。
   • 证明用 V 的公钥加密、T 私钥签名后可加时间戳或上公共账本，以防重放攻击；存储开销为 ES/k · |W|，延迟验证时还需保存数据集。

   PoL 验证（Algorithm 2）

   • V 先验证签名与初始权重来源：冷启动时用 KS 检验核对各层是否来自声称的初始化分布；热启动时要求初始权重自带 PoL，形成 chain of trust，链上 VSR 按乘法规则衰减。
   • 之后按 d1 距离计算相邻 checkpoint 的更新幅度，每 epoch 取幅度最大的 Q 段，从 Wt 重放 k 步得到 W't+k，若 d₂(W′_t+k, W_t+k) > δ 则判 FAIL；δ 为需校准的松弛参数，Q 为验证预算。
   • 只验最大更新的理由（作者说法）：合法更新幅度通常较小，伪造者的估计误差在大更新处更易暴露。验证时间复杂度 O(E·Q·k·C|W|)，验证成功率 VSR 定义为验证者接受 PoL 的概率。

   正确性与安全性论证

   • 作者证明带硬件/库噪声 zt 的 SGD 是平稳马尔可夫过程，训练熵随步数线性增长（Theorem 1），因此精确复现整条训练序列不可能，必须逐步验证。
   • 逆向梯度过程同为马尔可夫过程且熵不低于正向（Theorem 2）；作者据此提出 Conjecture 1：用数值求根逆向训练序列的计算代价至少与训练相同。
   • 针对定向重训练，论文分析两种策略：拼接两段合法 PoL 会在拼接处产生远大于合法更新的断点，被 top-Q 验证捕获；用正则项直接向 WT 最小化权重距离则因正则项需要事先知道 WT 而无法通过验证（附录 B 论证其对数据无梯度）。

   收起这一问

4. 04论文做了哪些实验？

   在 ResNet/LeNet5 上测复现误差、初始化检验与伪造策略，验证机制在噪声下可行且伪造代价高。

   实验设置

   • 被测模型与数据集：ResNet-20 于 CIFAR-10、ResNet-50 于 CIFAR-100（各 50,000 训练图像、10,000 测试图像，训练 200 epoch、batch size 128，E=200、S=390）；LeNet5 于 MNIST；22 神经元 logistic 回归于 Iris（附录 D）。
   • 主要指标：归一化复现误差 ||εrepr|| = max_t(εrepr)/dref，其中 εrepr 是验证者重放权重与声称权重的距离，dref 是两个独立训练同架构模型的参考距离（Table V）；另用 KS 检验 p 值（显著性水平 α=0.01）、验证准确率、函数调用次数。
   • 重复次数：逆梯度实验重复 35 次以估计方差（§VII-B3a）；其余实验重复次数论文未统一说明。
   • 评审方式：不涉及 LLM 或人工评审；验证判定依据 Algorithm 2 的距离阈值 δ 与 KS 检验。

   主结果

   复现误差（Table I，相同初始化、批划分与训练策略下重放）：

   设置	CIFAR-10 (ResNet-20) l1	CIFAR-100 (ResNet-50) l1
   k = E·S	0.974(±0.004)	0.903(±0.002)
   k = 1	0.001(±0.001)	0.002(±0.001)
   确定性操作	0.582(±0.004)	0.903(±0.001)

   • 作者称结果印证 Theorem 1：逐步重放（k=1）误差可忽略，整段重放误差接近 dref，因此 k 必须足够小。
   • 确定性操作在 ResNet-20 上把误差降到约一半，但训练变慢且准确率下降超过 1 个百分点；ResNet-50 上未观察到下降，作者认为其主要噪声来源未被 pytorch 的确定性设置覆盖。
   • Figure 1、2 显示 k≈S（每 epoch 一个 checkpoint，存储开销 1×）时 ||εrepr|| 仍明显低于 1，作者称无需额外存储即可满足验证要求。

   初始化验证

   • 测了什么：对冷启动声称，用 KS 检验核对早期训练步的各层权重是否仍符合初始化分布（Figure 4、Table II）。
   • 结果：CIFAR-10 上平均 7.00(±3.87) 步、CIFAR-100 上 1(±0) 步后 p 值跌破 0.01，此时验证准确率仅 10.526(±0.953)% 与 1.124(±0.348)%，接近随机猜测。
   • 作者解读：训练极少步后权重分布即偏离初始化分布，KS 检验可识别以他人最终权重冒充随机初始化的行为。

   伪造策略评估

   • 逆梯度方法：从训练 5 epoch 后的状态逆向 50 步（k=1）。ResNet 上 ||εrepr|| 大于 Table I 中 k=1 的情形（Table III：CIFAR-10 l1 为 0.023±0.001）；LeNet5/MNIST 上学习率超过 1e-4 后误差迅速增大（Figure 13），函数调用次数比训练基线高一个数量级以上（Figure 12、14）。逆向 50 步后的状态无法通过 KS 检验：CIFAR-10 平均 p 值 0.044(±0.102)、最小 1.077(±1.864)×10⁻²⁸；CIFAR-100 平均 0.583(±7.765)×10⁻¹²、最小 0(±0)。作者称逆向代价不低于训练且找不到合法初始化。
   • PoL 拼接：把 WT 微调 1 epoch 的 PoL 与另一从头训练 s 步的 PoL 拼接。断点 ||WT − W's||2 远大于所有合法更新且幅度接近 dref（Figure 5），作者称 Q=1 即可检出，验证代价为 E 步；若验证者改为随机抽查，发现断点的概率只有 1/390。
   • 例外：作者指出若 A 知道 Q 或 Q 很小，可用任意大学习率制造 Q 个合法大更新绕过 Algorithm 2，缓解办法是增大 Q、额外随机抽查或周期性检查模型性能。

   其他消融与分析

   • 学习率影响（Figure 3，k=12）：η 比 10⁰ 小一个量级时对 εrepr 影响不大；η=1 时 ||εrepr|| 上升。
   • 存储开销（Figure 6）：CIFAR-100 的 MB 级开销高于 CIFAR-10，作者归因于模型更深；float16 存储可再省一半。
   • 求根器选择（附录 D）：在 Iris/logistic 回归上比较 Gradient Descent、Newton-Krylov、Broyden1，Newton-Krylov 收敛最快，被选为求根器。
   • 验证时间（Figure 7）：给出验证耗时占训练时间比例随 k、Q 变化的解析关系，适用于 50,000 样本的数据集。

   收起这一问

5. 05有什么可以进一步探索的点？

   作者列出数据隐私、存储开销、链长衰减等局限；实验只覆盖四个模型与四个数据集。

   作者指出的局限与后续方向

   • 训练数据需共享（§VIII）：验证方案要求把训练数据交给验证者，数据私有时不理想；作者提出可用多方安全计算的私有推理协议保护机密性，代价是额外计算开销。
   • 存储开销（§VIII）：checkpoint 存储需求大；作者用 float16 降一半，并指出 Merkle tree 哈希可进一步压缩但会因权重误差无法比对，设计适用的 fuzzy extractor 或 LSH 是 future work。
   • 噪声来源缺乏 ground-truth（§VIII）：counter-based 伪随机数生成器可能消除大部分训练噪声，但目前没有覆盖硬件、底层库全部噪声源的 ground-truth。
   • 链式验证成功率乘法衰减（§VIII）：VSR 随 PoL 链长度乘法下降，限制长链（如多次迁移学习）使用；因无其他 PoL 方案可参照，作者留作 future work。
   • 逆向代价仅为猜想（§VII-B3a）：Conjecture 1（数值求根逆向至少与训练同代价）未获形式化证明；Theorem 2 等号条件的严格验证也留作 future work。
   • 适用场景（§IX）：作者期望后续工作提出适用于模型窃取与分布式训练之外场景的机制。

   实验覆盖范围

   • 被测模型为 ResNet-20、ResNet-50、LeNet5 与一个 22 神经元 logistic 回归，共 4 个；数据集为 CIFAR-10、CIFAR-100、MNIST、Iris。
   • 主实验训练配置为 200 epoch、batch size 128、S=390；逆梯度实验重复 35 次，其余实验的重复次数论文未统一报告。
   • 伪造策略评测覆盖逆梯度（含学习率与求根器扫描）、PoL 拼接；fine-pruning 与 sparsification 仅论证其无法通过 KS 检验，未给出实验数字。
   • 分布式训练场景未做端到端实验，PoL 在该场景的应用为机制设计层面的论证。
   • 论文未报告验证阈值 δ 在具体数据集上的校准取值，只给出设定启发式（取若干梯度更新的平均值）。

   收起这一问

6. 06总结一下论文的主要内容

   PoL 用训练轨迹作所有权与完整性证明，验证者重放最大更新；作者称伪造代价不低于训练。

   一篇关于训练完整性的防御论文：训练者如何向验证者证明模型权重确实由自己执行梯度下降得到。

   • 问题：模型被盗后所有者难以主张所有权；分布式训练中无法确认不可信 worker 的更新是否正确。现有水印与查询限制类防御以效用为代价或需改动训练。
   • 方法：PoL 由周期性 checkpoint 权重、批次索引、数据签名与超参数组成，加密签名后发布；验证者用 KS 检验核对初始化来源，重放每 epoch 幅度最大的 Q 段更新并以阈值 δ 比对。机制不改训练流程，只增加日志。
   • 理论：作者证明带噪声的 SGD 是平稳马尔可夫过程、训练熵随步数线性增长（Theorem 1），逆向过程熵不低于正向（Theorem 2），据此提出逆向代价不低于训练的猜想。
   • 关键结果：k=1 时复现误差 0.001–0.002，整段重放误差 0.974/0.903（Table I）；每 epoch 一个 checkpoint 即可满足验证且几乎无额外存储；训练 7 步（CIFAR-10）或 1 步（CIFAR-100）后 KS 检验即可识别非随机初始化（Table II）；拼接伪造的断点幅度接近 dref，top-Q 验证可检出（Figure 5）。
   • 作者结论：梯度下降的随机性天然积累秘密信息，熵增在攻防间形成有利于防御方的不对称；作者同时承认数据共享、存储开销与链长衰减等局限，期望后续工作改进机制并扩展到更多场景。

   收起这一问

相关论文