1. 项目概述与核心挑战

在当前的机器学习即服务（MLaaS）范式下，用户将数据发送给服务提供商进行模型推理，已成为一种普遍模式。然而，这种模式引入了一个根本性的信任问题：用户如何确信返回的推理结果是服务商承诺的、未经篡改的模型，在数据上正确执行后产生的？传统的解决方案，如要求服务商公开模型或依赖可信硬件（TEE），往往在隐私保护、通用性或性能上存在局限。

零知识证明（ZKP）技术为这一困境提供了优雅的出路。它允许证明者（服务商）向验证者（用户）证明一个陈述（例如：“我使用某个私有模型M，对您的数据D进行了正确计算，得到了结果Y”）是真实的，而无需透露模型M的任何信息。这完美契合了ML推理场景下，既要保护服务商的知识产权（模型隐私），又要让用户能验证计算完整性的双重需求。

但是，将ZKP直接应用于复杂的机器学习管道（MLIP）面临巨大挑战。一个典型的MLIP，例如用于信号或图像分类的流程，可能包含离散小波变换（DWT）去噪、主成分分析（PCA）降维和支持向量机（SVM）分类等多个步骤。如果使用通用的算术电路（如R1CS）来表述整个计算过程，其约束数量会随着数据维度、模型复杂度（如SVM支持向量数量）呈爆炸式增长，导致证明生成时间漫长、证明体积庞大，完全不具备实用性。

因此， ezDPS 项目的核心目标，就是打破这一性能瓶颈。它不是简单地用ZKP“硬套”ML计算，而是深入ML算法的数学本质，设计一套量身定制的、高效的零知识证明方案。其核心思路是： 针对DWT、PCA、SVM中的特定计算模式（如卷积、线性变换、最大值比较、指数运算），设计专用的“小工具”（Gadgets）和优化策略，在算术电路中用远少于通用方法的约束数量来表达相同的计算逻辑，从而将证明开销降低数个数量级 。

简单来说，ezDPS想回答的问题是： 我们能否在不泄露模型细节的前提下，向用户高效地证明“您的数据确实经过了我们承诺的DWT+PCA+SVM流程处理，并且这个结果是正确的”？ 我们的答案是肯定的，并且通过一系列精巧的密码学与系统优化，让这个证明过程从理论可行走向了实际可用。

2. 方案核心设计思路拆解

ezDPS的整体协议遵循经典的“承诺-证明-验证”三段式结构，但其精髓在于对内部ML计算过程的深度优化。理解其设计思路，需要把握以下几个关键层面。

2.1 整体协议流程与角色分工

ezDPS协议涉及两方： 证明者（Prover，即服务商/服务器） 和 验证者（Verifier，即用户/客户端） 。整个交互流程是非交互式的，适合异步网络环境。

1. 系统初始化（Setup） ：输入安全参数λ，生成公共参数pp。这部分通常依赖于底层的ZKP后端（如Spartan），一次性生成后可重复使用。
2. 模型承诺（Commit） ：服务商拥有一个私有MLIP模型参数 w 。它选择一个随机数r，计算承诺 cm = Commit(w, r, pp) ，并将承诺cm公开。这个承诺如同一个“数字指纹”，将模型锁定。此后，服务商在后续推理中必须使用与这个承诺对应的模型，否则无法通过验证。
3. 推理与证明生成（Prove） ：
   • 用户提交查询数据 x 。
   • 服务商使用私有模型 w 对 x 执行完整的MLIP推理（即Algorithm 1，包含DWT、PCA、SVM），得到结果y。
   • 为了生成证明，服务商不仅需要执行计算，还需要在计算过程中记录下所有的“见证（Witness）”。这包括了模型参数 w 、中间计算结果（aux，如DWT各层系数、PCA投影后的特征等）。
   • 服务商调用底层的ZKP证明算法，生成一个证明π。这个证明π在数学上证明了如下陈述：“存在一组见证（w, aux），使得：1）这组见证与公开的承诺cm对应；2）使用这组见证和公开输入x，运行指定的MLIP算法（Algorithm 1），得到的结果恰好是y。”
4. 验证（Verify） ：用户收到结果y和证明π。他利用公开的承诺cm、自己的输入x、结果y以及公共参数pp，运行验证算法。算法输出一个比特b（0或1），代表证明是否有效。如果有效，用户就可以确信y是正确执行的结果。

这个流程的关键在于，验证者从未接触到模型 w 或中间过程aux，但通过密码学承诺和零知识证明，获得了与亲自计算同等的信心。

2.2 面向ML算法的专用算术电路优化

通用电路将每个基础运算（加、乘、比较）都转化为一个或多个约束，对于ML算法来说极其低效。ezDPS的核心贡献在于识别了MLIP中的计算瓶颈，并为之设计了专用电路。

1. DWT（离散小波变换）的优化：分解与重组 DWT包含分解、阈值处理、重构三个阶段。通用电路需要为每个输入点与滤波器系数的乘加操作生成约束，复杂度为O(mc)，其中m是数据长度，c是滤波器长度（如DB4小波的c=4）。

• 优化思路 ：利用DWT的多分辨率分析和滤波器组的周期性。我们不是为每一层的每一个操作单独生成约束，而是将整个DWT过程视为一个线性变换，并利用随机线性组合（Random Linear Combination）技术。通过引入验证者提供的随机向量，证明者可以计算原始数据与滤波器系数卷积结果的一个随机线性组合值，并对此单个值进行承诺和证明。这能将约束数量从O(mc)降低到O(m + c^2)，由于c很小，这带来了显著提升。
• 阈值处理的处理 ：软阈值函数涉及绝对值和非线性操作，在电路中成本较高。我们采用了一种“选择器”思路，通过辅助变量来表明每个系数是否超过阈值η，并据此选择输出是（系数-η）还是0，避免了昂贵的绝对值电路。

2. PCA（主成分分析）的优化：随机线性组合的妙用 PCA本质上是将数据投影到主成分空间，即 x' = (x - mean) * V ，其中V是由前k个特征向量组成的投影矩阵。直接证明这个矩阵乘法需要O(m*k)个约束。

• 优化思路 ：同样运用随机线性组合。验证者发送一个随机向量α。证明者计算 t = (x - mean) * α 和 s = x' * α （其中x‘是投影后的特征）。然后证明者需要证明的是 s = t * V 在随机α下的线性关系成立。通过Schwartz-Zippel引理，如果对于随机α该等式成立，那么原始矩阵乘法等式极大概率也成立。这成功地将约束复杂度从O(m*k)降到了O(m)。

3. SVM（支持向量机）的优化：攻克非线性与最大值难题 SVM，尤其是带RBF核的多类SVM，是证明的主要开销来源。它包含两个难点：RBF核的指数运算，以及多类决策中的最大值选取。

• Max Gadget（最大值小工具） ：通用电路比较s个值的大小需要O(s^2)次两两比较。我们设计了一个基于“排列”的Max Gadget。核心思想是，证明者可以私下对s个分类器输出值进行排序，将最大值排到第一位，然后向验证者证明：1）排序后的序列是原序列的一个排列；2）排序后的第一个值大于等于后面的所有值。证明一个排列关系可以通过随机线性组合来完成（即“置换测试”），其复杂度仅为O(s)。这实现了从平方级到线性级的跨越。
• Exp Gadget（指数小工具） ：用于计算RBF核 exp(-γ * ||xi - xj||^2) 。在有限域上直接计算指数函数非常昂贵。我们采用了预计算和二进制分解的策略。将底数 a = exp(-γ) 预先计算其2的幂次方 a^1, a^2, a^4, ... 。对于指数 e = ||xi - xj||^2 ，将其表示为二进制形式。那么 a^e 就可以表示为一系列预计算值的乘积，其中哪些值被选中相乘由e的二进制位决定。这将对任意指数的求值，转化为一系列预计算值的条件乘法，大幅减少了约束数量。

2.3 零知识准确率证明（zkPoA）的创新

除了单次推理，ezDPS还扩展出了一个重要功能：零知识准确率证明。服务商可以承诺其模型的准确率（例如，在某个公开测试集上达到95%），并生成一个证明，而无需透露具体哪些样本分对、哪些分错，也无需透露模型本身。

• 核心问题 ：直接证明准确率等于某个精确值（如95.3%）非常复杂，因为需要同时证明“哪些样本对了”和“哪些样本错了”。
• 优化思路 ：我们转而证明一个更宽松但足够有用的陈述： 模型的准确率至少为ψ （例如，不低于95%）。这等价于证明在M个测试样本中，至少有 ψ * M 个被正确分类。
• 技术手段 ：
  1. 排列与隐藏 ：证明者私下对预测结果序列Y和真实标签序列T分别进行重排，将正确分类的样本集中到前 ψ * M 个位置。生成两个排列后的序列Y‘和T’。
  2. 证明内容 ：证明者需要向验证者证明：a) Y‘和T’的前 ψ * M 项完全相等；b) Y‘是Y的一个排列；c) T‘是T的一个排列；d) 对Y和T使用的排列是相同的。条件d)确保了是同一组样本被移动到了前面，从而保证了“至少ψ*M个样本正确”的断言。
  3. 置换测试 ：同样利用随机挑战和线性组合来高效证明排列关系，避免了暴露具体哪个样本对应哪个位置。

这个zkPoA方案使得服务商能够以一种可验证的方式“广告”其模型质量，增强了其服务的可信度，同时保护了模型细节和测试样本的预测结果隐私。

3. 关键技术细节与实操要点解析

理解了高层设计，我们深入到实现层面，看看这些优化是如何落地为具体约束和代码的。这里我会结合论文中的算法和公式，解释关键步骤的意图和实操中的注意事项。

3.1 DWT电路的具体构造与约束计数

以DB4小波（滤波器长度c=4）的一层分解为例。对于长度为 m 的信号，经过一层分解后会产生 m/2 个近似系数和 m/2 个细节系数。

• 通用电路的笨办法 ：需要为每个输出系数（共m个）编写约束。每个系数是输入信号中4个点的线性组合。这需要约 4*m 个乘法约束。对于多级分解，约束数约为 8m - 4c （论文表2中Baseline的DWT行）。
• ezDPS的优化方法 ：
  1. 分解与重构的线性组合 ：我们引入一个随机挑战向量β（由验证者在证明阶段提供）。证明者计算原始信号z与β的点积 S1 ，再计算DWT分解后的两组系数分别与β的特定子集的点积 S2 和 S3 。约束在于证明 S1 、 S2 、 S3 之间满足DWT滤波器定义的线性关系。由于β是随机的，只要这个线性关系对随机β成立，原始变换的正确性就以极高概率成立。这仅需 O(log m) 级别的约束来处理下采样带来的索引映射，主要开销在于处理滤波器系数，总计约 16 * log2(2m/c) 个约束。
  2. 软阈值化的电路实现 ：对于细节系数 d[i] ，软阈值操作是 sign(d[i]) * max(|d[i]| - η, 0) 。在电路中，我们引入一个辅助二进制变量 b[i] 来表示 |d[i]| > η 是否成立。
     • 约束1： (d[i] - η) * b[i] = output_positive_part 。如果 b[i]=1 ，则输出正部为 d[i]-η ；如果 b[i]=0 ，则该乘积被强制为0。
     • 约束2：需要处理 d[i] 可能为负的情况。我们引入另一个变量来表示 sign(d[i]) ，并通过约束将其与 b[i] 和 d[i] 关联。
     • 最终输出 d'[i] = sign(d[i]) * output_positive_part 。这部分每个系数需要常数个约束，总计 (3n+9)(m-c)/2 ，其中n是数值的比特宽度。

实操心得 ：DWT优化中， 随机线性组合的挑战值必须在证明生成阶段由验证者提供 ，这要求协议是交互式的，或者通过Fiat-Shamir变换在非交互式协议中由哈希函数模拟。在实现时，务必确保挑战值的生成严格遵循协议，任何偏差都会导致安全漏洞。

3.2 PCA投影的随机线性组合实现

假设中心化后的数据向量为 x_centered ，投影矩阵为 V （k个主成分，每个m维），投影后特征为 x_feature = x_centered * V 。

1. 验证者发送随机向量 α ∈ F^k （域F上的k维向量）。
2. 证明者计算两个标量：
   • t = <x_centered, α * V^T> 。注意， α * V^T 是一个m维向量，它是主成分的随机线性组合。
   • s = <x_feature, α> 。
3. 证明者需要证明的约束是： s == t 。
4. 为什么这就够了？如果 x_feature 确实等于 x_centered * V ，那么对于任何α，都有 s = <x_centered * V, α> = x_centered * (V * α^T) = <x_centered, α * V^T> = t 。反之，如果两者不相等，则对于随机α， s == t 成立的概率可忽略不计。

这个技巧将证明一个 m x k 的矩阵乘法，转化为证明一个标量等式，约束数从 O(mk) 骤降至 O(m) （用于计算t和s的线性组合）。

3.3 SVM中Max Gadget的排列证明详解

这是ezDPS中最精妙的设计之一。假设有s个分类器输出值 [y1, y2, ..., ys] ，需要证明最终分类 c = argmax(y_i) 。

1. 证明者的预处理 ：证明者私下找到一个排列σ，使得 y'_1 = y_{σ(1)} 是最大值，并且 y'_1 >= y'_i 对于所有 i>1 成立。他将排列后的序列 Y' = [y'_1, ..., y'_s] 作为辅助见证提交。
2. 需要证明的陈述 ：
   • Y‘ 是 Y 的一个排列。
   • y'_1 >= y'_2 , y'_1 >= y'_3 , ..., y'_1 >= y'_s 。
3. 如何证明排列关系？ 使用置换测试。验证者发送一个随机挑战ξ。
   • 证明者计算两个多项式： P(ξ) = Σ_{i=1}^s (y_i + ξ * i) 和 P'(ξ) = Σ_{i=1}^s (y'_i + ξ * σ(i)) 。
   • 约束是 P(ξ) == P'(ξ) 。如果 Y‘ 确实是 Y 的一个排列，那么对于任何ξ，两个求和都相等，因为加数只是顺序不同。如果 Y‘ 不是 Y 的排列，则对于随机ξ，等式成立的概率极低。
4. 证明最大值关系 ：这只需要 s-1 个简单的比较约束（ y'_1 - y'_i >= 0 ）。

这样，总约束数从通用电路的 O(s^2) 次两两比较，降低到了 O(s) （主要是置换测试的线性组合和 s-1 次比较）。

注意事项 ：Max Gadget依赖于证明者诚实地将最大值排到第一位。如果证明者恶意地将一个非最大值排到第一位，虽然排列关系仍能通过，但后续的大小比较约束将无法满足。因此， “最大值在第一” 这个事实是由证明者声明的，并由比较约束来验证其正确性。这是一个“Proof of Knowledge”而非“Proof of Computation”的典型例子——证明者知道一个满足所有约束的排列，而这个排列恰好将最大值放在了首位。

3.4 工程实现中的关键决策

1. 数值表示 ：ZKP通常在有限域上进行，而ML计算涉及浮点数。ezDPS采用了 定点数（Fixed-Point Arithmetic, FPA） 表示。论文中选用64位，其中1位符号位，31位整数部分，32位小数部分。这需要在训练ML模型时就使用定点数或进行充分的量化微调，以保持精度。
2. ZKP后端选择 ：ezDPS选用 Spartan 作为证明系统后端。Spartan是一种无需可信设置的透明zkSNARK，其验证时间和证明大小是亚线性的（相对于约束数量），这非常适合约束数量庞大的ML电路。实现时利用libspartan库将算术约束转化为R1CS关系。
3. 指数运算的预计算 ：对于Exp Gadget，预计算 a^(2^i) 表是关键。论文中提到，由于RBF核参数γ通常很小（如10^-3），指数 e = -γ * ||x_i - x_j||^2 的绝对值也很小。他们发现用20位来存储指数的小数部分足以覆盖大多数情况。对于极少数溢出情况，采用了截断处理，这引入了微小的精度损失（实验显示约1-2%），但在可接受范围内。
4. 代码结构 ：项目用Python和Rust实现，约2500行代码。Python端负责ML流程（使用sklearn训练，但推理部分需自实现以获取所有中间见证），Rust端负责密码学操作（约束生成、证明生成与验证）。这种混合架构兼顾了开发效率和执行性能。

4. 性能评估与结果分析

理论上的优化需要实验数据的支撑。ezDPS在三个公开数据集上进行了全面测试：UCR-ECG（心电图，750维）、Cifar-100（图像，3072维）和LFW（人脸，~5655维）。对比基线是将整个DWT+PCA+SVM流程硬编码到通用算术电路中。

4.1 整体性能对比：数量级的提升

实验结果令人印象深刻。ezDPS在 证明时间、验证时间和证明大小 三个核心指标上，全面领先基线方法一到三个数量级。

• 证明时间（Prover Time） ：这是服务商的开销，通常最大。在LFW数据集上，当类别数（s）为8时，ezDPS耗时1702秒，基线耗时11491秒，加速约6.75倍。当类别数增加到2048时，ezDPS耗时6977秒，而基线预估耗时超过280万秒（约32.5天），加速比超过1842倍。这直观地体现了从O(s^2)到O(s)优化带来的巨大收益。
• 验证时间（Verifier Time） ：这是用户的开销，必须足够小。ezDPS的验证时间基本在10秒以内，甚至对于大规模问题（LFW-2048）也仅需9秒，而基线方法需要123.6秒。这得益于Spartan的亚线性验证特性。
• 证明大小（Proof Size） ：影响通信带宽。ezDPS的证明大小控制在MB级别（例如LFW-2048为4.4MB），而基线方法达到56.8MB，ezDPS减少了约14倍。

这些数据强有力地证明了专用电路优化对于zkML实用化的决定性作用。

4.2 各阶段开销分解

为了更细致地理解开销来源，论文将ezDPS的总开销按DWT、PCA、SVM三个阶段进行了分解。

• DWT阶段 ：开销相对稳定，主要取决于输入数据维度m。它在总开销中占相当一部分，但不像SVM那样随类别数增长。例如在Cifar-100上，证明时间约656秒。
• PCA阶段 ：开销最小且稳定。由于其优化将约束降至O(m)，即使m很大（如5655），其证明时间也几乎可以忽略（UCR-ECG上约17秒），在总开销中占比最低。
• SVM阶段 ： 这是主导性因素 ，尤其当类别数s很大时。其开销随s和总支持向量数t线性增长。在LFW-2048任务中，SVM阶段贡献了超过73%的总证明时间。这说明了为什么Max Gadget的优化如此关键——它直接攻击了开销增长最快的部分。

4.3 精度损失评估

由于采用了定点数运算，需要评估其对ML模型精度的影响。实验对比了浮点数（FP）和定点数（FPA）下DWT+PCA+SVM流程的准确率。

• 结果 ：在所有数据集上，定点数运算导致的准确率下降约为1%到2%。例如，在LFW数据集8分类任务上，浮点精度为73% ± 7%，定点精度为72% ± 7%。
• 分析 ：1-2%的精度损失对于许多实际应用场景是可以接受的，尤其是考虑到它换来了可验证的完整性和模型隐私。这种损失主要来源于指数运算中小数部分的截断，以及整个计算链中的累积量化误差。

4.4 zkPoA（零知识准确率证明）性能

zkPoA的性能与单次推理证明线性相关。在包含64个样本的LFW测试集上，ezDPS的zkPoA方案相比基线，证明时间快6-9倍，验证时间快3倍，证明大小小3倍。这证明了该扩展方案的可行性，使得服务商能够高效地、隐私地证明其模型整体性能。

5. 总结、局限与未来展望

ezDPS项目成功地展示了一条通向实用化zkML的清晰路径： 通过深入理解特定领域算法（Domain-Specific Algorithms）的计算特性，设计与之匹配的专用零知识证明原语（Custom ZK Gadgets），可以达成数个数量级的性能提升 。它将一个原本需要数十天才能生成证明的任务，缩短到数小时之内，同时将验证开销控制在用户可接受的秒级。

从工程实践角度，我总结出以下几点关键经验：

1. 算法洞察优先 ：在动手设计电路之前，必须吃透目标ML算法的数学本质。寻找其中的线性结构（如PCA）、可聚合操作（如DWT的线性变换）和非线性瓶颈（如SVM的max和exp），这是所有优化的源头。
2. 权衡精度与效率 ：在密码学领域使用定点数几乎是必然选择。需要在模型训练阶段就考虑量化，或进行充分的量化感知训练（QAT），以最小化精度损失。1-2%的损失是一个很好的参考基准。
3. 利用现代ZKP后端特性 ：选择像Spartan这样具有亚线性验证和证明大小的证明系统至关重要。这确保了无论电路多复杂，用户端的验证负担都是轻量的。
4. 模块化设计 ：将DWT、PCA、SVM的证明电路设计为独立的Gadgets，有利于代码复用和未来扩展到其他ML管道（如替换SVM为神经网络）。

当然，ezDPS也有其局限性和未来的改进空间：

1. 模型类型限制 ：目前专注于DWT+PCA+SVM这一特定管道。虽然其Gadget设计思想（如Max、Exp、随机线性组合）可迁移，但要将ezDPS扩展到更复杂的深度学习模型（如CNN、Transformer），需要设计新的、更复杂的Gadgets。
2. 证明时间依然较长 ：即使优化后，对于大规模问题（如Cifar-100全量100类），证明时间估计仍需数万秒（十多个小时）。这要求服务商拥有较强的计算资源。未来的方向包括：探索更高效的证明系统（如折叠方案）、GPU加速证明生成、以及模型本身的压缩（如减少SVM支持向量）。
3. zkPoA的扩展 ：目前的zkPoA仅针对一个固定的测试集证明准确率。一个更有趣的方向是能否构造支持交叉验证（Cross-Validation）的zkPoA，同时不因多次测试而泄露模型信息，这仍是一个开放问题。
4. 硬件加速 ：论文中的实验基于单线程CPU。实际部署中，证明生成过程的许多部分（如大规模矩阵运算、多重标量乘法）可以高度并行化，利用多核CPU或GPU能带来显著的进一步加速。

总而言之，ezDPS不仅仅是一个高效的zkML方案，它更提供了一套方法论： 针对复杂计算设计专用零知识证明电路 。随着ZKP硬件加速和算法本身的不断进步，以及更多针对不同ML操作符的Gadgets被设计出来，我们正稳步走向一个未来：在那里，隐私保护、可验证的机器学习服务将成为可靠且高效的标配，而ezDPS正是这个未来的一块重要基石。对于任何想要在业务中引入可验证计算的研究者或工程师而言，深入理解这种“领域专用优化”的思想，远比单纯调用一个ZKP库更为重要。