\texttt{Range-Arithmetic}: Verifiable Deep Learning Inference on an Untrusted Party

技术摘要：范围算术（Range-Arithmetic）——针对不可信方的可验证深度学习推理

问题陈述
去中心化机器学习（ML）系统日益依赖于将资源密集型任务（如深度神经网络 DNN 推理）卸载给不可信的外部方（证明者），以克服区块链的局限性。这一范式中的一个关键挑战是，如何在不要求验证者重新执行整个过程的情况下，确保这些外包计算的完整性，因为重新执行的过程通常极其昂贵。

现有的可验证计算（VC）技术在应用于机器学习时面临显著障碍。大多数 VC 方案运行在有限域之上，并受限于算术运算（加法和乘法）。然而，标准的机器学习计算涉及非算术运算，具体包括：

1. 定点舍入（Fixed-point rounding）： 在矩阵乘法之后进行，用于管理精度并防止溢出。
2. 非线性激活函数： 例如 ReLU（修正线性单元）。

在传统的 VC 框架中表示这些操作通常需要复杂的布尔电路编码、高次多项式或大型预计算查找表。这些方法会引入显著的证明者开销、验证者成本和通信带宽压力，或者无法同时支持 ReLU 和舍入等基本操作。

方法论：范围算术框架
作者提出了 Range-Arithmetic，这是一个旨在高效验证 DNN 推理，同时保持与基于有限域的证明系统兼容性的新颖框架。其核心创新在于将非算术操作转化为可通过 sum-check 协议和级联范围证明（concatenated range proofs）进行验证的算术步骤，从而避免了布尔编码和大型查找表。

该框架通过以下机制运行：

1. 矩阵乘法验证：
   矩阵乘法（$C = AB$）的验证被重新表述为一个 sum-check 问题。通过将矩阵元素表示为有限域上的多项式扩展（MLEs），乘积的正确性被简化为验证一个多项式恒等式。作者利用 Schwartz-Zippel 引理在随机点上检查该恒等式，并利用 sum-check 协议将通信复杂度降低至 $O(\log n)$。

2. 舍入验证：
   为了验证乘法后应用的舍入操作 $R(x)$，作者将该过程分解为算术约束。他们定义了舍入部分的丢弃部分（$E$）和舍入分数的分子（$D$）。通过**聚合范围证明（aggregated range proofs）**确保正确性，需证明两个条件：

   • 丢弃的位位于特定的微小区间内（$-2^{s-1} \leq e_i < 2^{s-1}$）。
   • 剩余值是 $2^s$ 的整数倍且没有回绕（wrap-around）。
     这种方法允许使用标准的范围证明来验证舍入，而无需使用大型有限域来防止溢出。

3. ReLU 验证：
   ReLU 函数定义为 $\text{ReLU}(x) = \max(0, x) = (x + |x|)/2$，其验证过程如下：

   • 使用范围证明证明绝对值 $Y = |A|$ 是非负的。
   • 使用基于多项式 $f(x) = \tilde{I}(s, x)(\tilde{a}^2(x) - \tilde{y}^2(x))$ 的 sum-check 协议，证明对于所有元素均满足 $a_i^2 = y_i^2$。
   • 验证最终的线性组合 $B = (A + Y)/2$。

4. 组合：
   该框架将神经网络推理视为一系列层。每一层（带舍入的矩阵乘法或 ReLU 激活）都进行独立验证。前一层输出的承诺（commitment）作为下一层的输入，从而实现了验证算法的模块化组合，而无需重新传输大型中间矩阵。

核心贡献
论文声称其具体贡献如下：

• 统一框架： Range-Arithmetic 是首个在支持定点舍入和 ReLU 的同时，实现 $O(n^3)$ 证明者复杂度、$O(n^2)$ 验证者复杂度和 $O(\log n)$ 通信复杂度的方案。
• 消除开销： 该方法避免了对布尔电路编码、用于防止溢出的超大有限域以及大型预计算查找表的需求，这些是先前工作的常见做法。
• 无需预处理： 与基于 R1CS 或算术电路的方法不同，该方法不需要预处理或编码开销。
• 实用性： 由于不需要通过扩大有限域来避免溢出，该方案在密码学规模的素数下仍保持实用。

实验结果
作者在一个线性神经网络以及一个涉及 MNIST 数据集（使用 6 位整数和 8 位小数位）的四层全连接网络的案例研究中评估了所提算法。

• 性能比较： 与缺乏 ReLU 支持且需要扩大字段的现有最先进方法 [20] 相比，随着网络层数的增加，Range-Arithmetic 展示了更优越的性能。
• 指标： 所提方法降低了证明者和验证者的计算成本，并降低了通信开销。
• 具体数值： 在 MNIST 案例研究中，证明者运行时间约为 230 毫秒，验证者运行时间约为 154 毫秒。
• 可扩展性： 随着矩阵规模的增大，通信成本呈对数增长，而证明者和验证者的运行时间呈多项式级增长。

意义与主张
论文将 Range-Arithmetic 定位为在针对不可信方的可验证 DNN 推理中，在证明者工作量、验证者成本、通信量和功能完整性之间提供了“最平衡的权衡”。作者强调，虽然基于查找表的方法在纯 ReLU 验证方面可能更快，但其对大型辅助表的需求使其在资源受限的验证者面前并不实用。Range-Arithmetic 用轻量级的范围证明取代了这些表格，为特定于去中心化机器学习系统的约束提供了一个更通用且高效的解决方案。这项工作旨在通过实现对复杂、非算术类机器学习操作的高效验证，促进开放、动态环境下的可信且自主的 AI 应用。