Giskard：面向大规模去中心化学习的拜占庭鲁棒且隐私保护的聚合协议

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

   如何在大规模去中心化学习中同时实现拜占庭鲁棒聚合和差分隐私，且每方通信量随 n 次线性增长。

   核心问题：在去中心化学习中同时抵御模型投毒（拜占庭行为）和隐私攻击，且协议能扩展到百万级参与方。

   • 问题场景：去中心化学习中参与方点对点交换模型更新，缺少中心服务器把关，投毒攻击更难检测；同时直接访问他人更新会放大成员推断、梯度反演等隐私攻击面（作者称可能比 FL 中更强）。
   • 现有方法的不足：客户端本地 DP 会增大诚实更新的方差，削弱鲁棒聚合，且存在隐私-鲁棒-效用的不可能性结果 [24]；分布式 DP 需要密码学保护，而已有基于 MPC 的鲁棒聚合方案要么全互联通信、要么把全部计算压在一个小委员会上，每方开销随 n 增长，作者称这构成根本的可扩展性瓶颈。
   • 核心观察：坐标中位数（一种已知的鲁棒聚合规则）可以改写为一串安全计数查询——本地比较是明文免费操作，聚合只是求和这一可结合操作，从而把昂贵的非线性运算移出安全域，适合分层委员会 MPC。
   • 论文提出：Giskard，把 n 方组织成 O(log n) 大小委员会的 k 叉树，在委员会内用 MPC 评估带 DP 噪声的坐标近似中位数；作者称其在 f < n/4 下可证明安全，每方通信量为 polylog(n)，而最接近的竞争者为 O(n log² n)。
   • 威胁模型：
     • 攻击者目标：破坏聚合过程的机密性、隐私性和正确性；在学习层面提交对抗性更新以偏置全局模型。
     • 知识：静态敌手，协议执行前选定腐化集合，执行中不可更改；计算能力受限（多项式时间）。
     • 能力：被腐化方可任意偏离协议：发送畸形份额、合谋重构共享秘密、试图中止协议。
     • 受害系统与界限：n 方去中心化学习系统，要求 f < n/4；假设同步网络、PKI 认证点对点信道和 TLS。

   收起这一问

2. 02有哪些相关研究？

   相关工作分三类：鲁棒聚合规则、DP 与鲁棒性的结合、以及用密码学实现鲁棒聚合，作者称前人均未同时满足形式鲁棒、DP 与可扩展。

   鲁棒聚合规则（防御投毒）

   • Yin et al. [16] 提出坐标中位数、截尾均值等坐标估计器；Blanchard et al. [17] 提出 Krum；Pillutla et al. [42] 提出几何中位数（RFA）。这些规则在 (f, κ)-鲁棒性框架 [19] 下有可证明保证。
   • Karimireddy et al. [18]、Allouah et al. [19] 通过预聚合机制增强异构环境下的鲁棒性；Erbani et al. [20] 通过重构损失函数应对投毒。

   DP 与鲁棒聚合的结合

   • Allouah et al. [24] 证明在 (f, κ)-鲁棒聚合上加本地 DP 会大幅损害模型效用（隐私-鲁棒-效用三难）。
   • CafCor [55] 用跨参与方的相关噪声机制替代本地 DP，并提出基于协方差界无关过滤的新鲁棒聚合器；论文指出它运行在经典 FL 设置、假设诚实但好奇的聚合服务器。

   用密码学实现鲁棒聚合

   • Sable [25] 用半同态加密计算截尾均值，论文指出其依赖单个强大且诚实但好奇的服务器。AlphaFL [26]、EIFFeL [65] 在多方或客户端-服务器设置下做启发式输入校验而非形式鲁棒规则；DP-BREM+ [66] 结合零知识输入校验与 MPC 分布式噪声生成，论文指出其限于 FL cross-silo 拓扑且每客户端通信随模型维度、系统规模和敌手上界线性增长。
   • SecureDL [30] 用恶意安全 MPC 实现余弦相似度过滤，论文指出其全互联拓扑扩展性差且余弦过滤无形式鲁棒保证；Franzese et al. [29] 在 all-to-committee MPC 下形式化无服务器鲁棒协同学习，论文指出其单层拓扑把计算集中在小委员会上，且没有 DP，全局模型仍易受隐私攻击。

   基线与基准：通信与延迟对比的基线是 A2A（全互联 [30]）和 A2C（all-to-committee [26], [29]）两种拓扑；明文鲁棒性对比的基线聚合器是 trimmed mean（TM）和 CAF，攻击为 FoE [38] 与 ALIE [39]，数据集为 MNIST、Fashion-MNIST、CIFAR-10；DP 对比在 EMNIST 上对 Local DP+Median 与 Local DP+CAF。

   定位：作者称 Giskard 是把这些缺口一起补上的方案——用分层 MPC 委员会评估形式鲁棒的聚合器并加入分布式 DP，使每方通信开销次线性，把鲁棒去中心化学习扩展到大规模网络。

   收起这一问

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

   Giskard 把坐标中位数改写为带 DP 噪声的安全计数查询序列，在 O(log n) 大小委员会的 k 叉树上用 BGW 类 MPC 分层求值。

   整体思路：把鲁棒聚合规则与它的 MPC 实现协同设计。Giskard 的关键改写是把坐标中位数表示为一串私有的安全计数查询，使所有昂贵操作（比较、排序）移出安全域，安全域内只剩可加性求和，从而可以分摊到小规模委员会组成的分层树上。

   问题形式化与计数查询改写

   • n 方各持有本地数据集，共同最小化全局损失；采用用户级 DP（保护单个参与方整个本地数据集的增删），鲁棒性采用 (f, κ)-Byzantine robustness 定义（Def. 3）。
   • 给定公开枢轴 p，计数查询 count(p) = ∑_j=1ⁿ 1[x_j ≤ p] 返回不超过 p 的输入个数；每次迭代揭示带噪计数 count̂ = count(p) + Z_t，Z_t ∼ 𝒩(0, N_iter/2ρ)，每次查询敏感度为 1，预算 ρ/Niter，经组合得整体 ρ-zCDP。
   • 二分搜索（Algorithm 1）：值域 (−u, u]，精度 q，迭代次数 Niter = ⌈log₂(2u/q)⌉；带噪计数 ≥ ⌊n/2⌋+1 时右界左移，否则左界右移；模型各坐标并行处理。

   分层委员会架构

   • 一次性 B UILD T REE：通过可扩展拜占庭协议做种子协商（Lemma 1，容忍至多 (1/4−ϵ)n 腐化，每方通信 polylog(n)），由公共伪随机函数确定 k 叉树拓扑，树在所有轮次复用，摊销建立成本。
   • 叶子（Level 0）是全部 n 方：本地把向量与当前枢轴逐坐标比较，把比特向量秘密共享给所属基础委员会；基础委员会（Level 1）验证份额的比特域和格式、求和后向上重共享；中间委员会逐级转换再聚合；根委员会（Level L）做最终检查与聚合、联合生成高斯噪声、明文重构带噪计数、选出下一个枢轴并沿树广播。
   • 委员会大小 m = O(log n)（Theorem 5：m = O(ϵ⁻² ln n)，失败概率 1−n^(−c)），阈值 τ < m/4，分支因子 k 为常数。

   关键子协议

   • I NPUT S HARE：叶子用 VSS-S HARE 共享比特；委员会用二度域证明（M ULTIPLY([b],[1−b]) 后重构，结果为 0 才接受）验证每个共享值确为比特，非法贡献替换为零的规范共享，从而把每个拜占庭方每轮对计数的影响限制在 1 以内（count_B ∈ [0, f]）。
   • R ESHARE：用 VSS-S UB S HARE 把子委员会的 (τ, m) 份额转换为父委员会的新份额，父方用 Lagrange 系数本地重组，能检测并纠正畸形或不一致的子份额。
   • N OISE G EN：根委员会成员各自采样截断到 [−B, B−1] 的离散高斯噪声、比特分解后共享，用与 I NPUT S HARE 类似的比特验证，畸形贡献替换为零；聚合噪声至少含 m−τ 个诚实样本。
   • B ROADCAST D OWN：父委员会向子委员会下发公开值，子方按超过 m/4 的重数做多数表决。

   安全、鲁棒与隐私结论（理论）

   • Theorem 2：在 f < n/4 的静态恶意敌手下，Giskard 在 UC 框架下安全实现近似坐标中位数功能（证明在附录 C-F）。
   • Theorem 3：输出与诚实均值偏差 ≤ √κ0·σH + q/2，κ0 = (n−f)/(⌈n/2⌉−f)；作者称乘性因子与 CWMed、GM、Krum 同属 Θ(1) 区间，且对任意 f < n/2 的拜占庭输入满足 Def. 3（至多附加离散化项 Dq²/2）。
   • Theorem 4：理想机制为 (ρ+ξDG)-zCDP；截断机制为 (ε0, δ0+(1+e^ε0)βtr)-DP；有效拜占庭容忍 fDP = f − ηDP − τB。
   • Theorem 6：乐观执行下最坏每方通信 O(d·Niter·log³ n)、总量 O(d·Niter·n·log³ n)；非乐观执行（含投诉广播）为 O(d·Niter·log⁵ n) 与 O(d·Niter·n·log⁵ n)。

   可推广性

   • 作者给出 Giskard 兼容聚合规则的三条要求（G1 紧凑可分解、G2 可高效认证的鲁棒性、G3 低安全算术复杂度），并在 Table I 中对 ℓ1-RSA/DP-RSA、signSGD-MV、BRACE、几何中位数/RFA、Krum、坐标中位数、截尾均值、SMEA、CAF/CafCor 做了兼容性分类；作者称 Krum、坐标中位数、截尾均值的直接实现需要昂贵的选择、比较或排序，CAF 的反复谱估计与非线性权重更新违反 G3。

   收起这一问

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

   实验回答四个问题：每方通信量、端到端延迟、明文下抗投毒鲁棒性、DP 对鲁棒性的影响；作者称 Giskard 每方通信量比 A2C 最多低 722 倍。

   实验设置

   • 实现与平台：Giskard 用 Rust 基于 arkworks 实现；明文基线用修改过的 ByzFL Python 框架；单机 Ubuntu 24.04、Intel Core i9-13950HX、NVIDIA RTX 5000。
   • 通信成本模型（RQ1）：同一中位数电路、同一成本模型下比较 A2A、A2C、Giskard 三种拓扑；按发送/接收的域元素计数（不含网络头）；δ = 2⁻⁴⁰，Niter = 10，穷举搜索 2 ≤ k ≤ 32 与可行 L 使 Giskard 每方成本最小。
   • 延迟模型（RQ2）：f/n = 0.10，假设每方 1 Gbps 带宽、1 s 往返延迟，计算与传输在一轮内重叠、同层委员会并发、I NPUT S HARE 单线程顺序执行，取最小端到端墙钟时间。
   • 投毒实验（RQ3）：n = 100 方、f = 25 拜占庭；聚合器为 Giskard 的二分搜索中位数（BSM）、trimmed mean（TM）、CAF；攻击为 FoE 与 ALIE，授予对聚合规则和全部诚实更新的白盒访问并优化超参（作者称这比 Giskard 中拜占庭方的真实视野更强，视为保守压力测试）；数据集 MNIST、Fashion-MNIST、CIFAR-10，Dirichlet 参数 α 控制异构度（α=100 接近 i.i.d.）。
   • DP 实验（RQ4）：EMNIST，n = 11850，f = 24%，α = 1.0；Giskard 的分布式 DP 对 Local DP+Median 与 Local DP+CAF；四种攻击（Sign Flipping、Label Flipping、ALIE、FoE）× 三个隐私预算（ε = 10、25、100），δ = 10⁻⁵；两种机制都在明文下模拟、保留各自隐私记账（Giskard 用 zCDP 组合，Local DP 用 Opacus 与 RDP）。
   • 指标：每方/总通信量（字节）、估计端到端运行时间、峰值测试准确率。

   主结果

   通信成本（Figure 4，标量中位数、Niter = 10；Table II 给出渐近对比：A2A 每方 O(dn²)、A2C 每方 O(dn log² n)、Giskard 每方 O(d log³ n)）：

   表格较宽，可左右滑动

   拓扑	n=10⁶, f/n=0.10 每方成本	n=10⁶ 每方成本范围（f/n∈{0.05,0.10,0.20}）	出处
   Giskard	1.99 TB	146 GB – 3.09 PB	Figure 4(b)(c)
   A2C	未报告单一值	45.3 TB – 44.4 PB	Figure 4(b)(c)
   A2A	约 4.57·10²² bytes（与拜占庭比例无关）	同左	正文 §VI-A

   • f/n = 0.10 时 Giskard 每方成本从 n=10³ 的 392 GB 增至 n=10⁶ 的 1.99 TB（5.1 倍），而 A2C 约增 572 倍、A2A 约增 1.00·10⁹ 倍；f/n = 0.01、n=10⁶ 时 Giskard 比 A2C 低 722 倍（Figure 4(c) 还标注 311×、135×、14× 等比值，对应不同 f/n 与 n）。
   • 作者解释：A2C 把 I NPUT S HARE 集中在一个委员会（n=10⁶、f/n=0.10 时占其每方成本 99.7%），Giskard 把验证分摊到多个委员会，根委员会 N OISE G EN 占其每方成本 89.5%；代价是总通信量略高于 A2C（N OISE G EN 总量 1.78 TB 对 0.78 TB）。
   • 延迟（Figure 5）：f/n = 0.10 下，作者的成本模型把 Giskard 的墙钟时间置于分钟到小时级；A2C 从 n=10⁵ 起为多小时到多天；A2A 在 n=10⁴ 已超出实际可用范围；n=10² 时三者相差在一个小的常数因子内。

   明文抗投毒（RQ3，Table III）

   • 测了什么：BSM、TM、CAF 在 FoE/ALIE 下、多个 Dirichlet 异构度（α ∈ {0.10, 0.50, 0.75, 1.00, 100}）的峰值测试准确率。
   • 结果：MNIST 上 α ≥ 0.5 时 BSM 与 TM 的 FoE 准确率相差至多 0.9%（如 α=100：BSM 0.97、TM 0.97、CAF 0.99），ALIE 下 BSM 高于 TM（α=0.10：0.84 对 0.76）；Fashion-MNIST 上 FoE 差距从 α=0.75 的 3.4% 扩大到 α=0.1 的 18.9%（0.15 对 0.33），但 ALIE 下 BSM 全程更高；CIFAR-10 上差距从 α=1.0 开始出现，α ≥ 100 时 BSM 在两种攻击下都保持（α=100：FoE 0.57、ALIE 0.48）。
   • 作者解读与例外：FoE 专门针对中位数和 TM；CAF 在低 α 明文下仍最鲁棒（CIFAR-10、ALIE、α=0.10 时 CAF 0.63*，BSM 0.19；*表示 ALIE 导致 CAF 训练停滞而提前终止），但作者称 CAF 的谱估计与非线性权重更新对 MPC 过于昂贵，与 Giskard 不可互换。

   DP 对鲁棒性的影响（RQ4，Figure 6）

   • 测了什么：EMNIST（n=11850、f=24%、α=1.0）上 Giskard DP 对 Local DP+Median、Local DP+CAF，4 种攻击 × 3 个隐私预算共 12 个设置。
   • 结果：作者报告 Giskard 在 12 个设置中的 11 个取得最高准确率；Sign Flipping 下各预算均接近 91%，ε=10 时约高出两个本地 DP 基线 56%、ε=100 时约 3%；FoE、ε=100 时 Giskard 63.1%，Local DP+CAF 16.0%，Local DP+Median 10%。
   • 作者解读：本地 DP 在聚合前扰动诚实更新、增大其离散度；Giskard 在 MPC 内聚合后加噪，无需可信协调者即获得接近中心 DP 的效用，因此即使基线用更鲁棒的 CAF 也能反超。

   其他消融与分析

   • 委员会大小（Figure 3）：Pr[failure]=2⁻⁴⁰ 目标下，所需 m 随全局腐化比例与 1/4 要求之间差距拉大而减小；f/n ∈ [0, 1/5] 时 m 随网络规模增长保持稳定（作者称 Theorem 5 的界偏松，图为更紧的数值评估）。
   • 成本构成（§VI-A）：n=10⁶、f/n=0.10 时 A2C 每方成本的 99.7% 来自 I NPUT S HARE，Giskard 每方成本的 89.5% 来自根委员会 N OISE G EN。
   • 异构度压力设置（§VI-C）：MNIST、α=0.10 时 49% 的参与方至少 75% 样本来自单一类别，α=1 时为零；作者说明这些极端设置用于定位中位数类聚合失效的边界，不代表典型部署假设。

   收起这一问

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

   作者仅在结论中提出一项后续方向：研究非交互式证明以进一步降低通信成本。

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

   • 结论（Section VIII）：作者计划研究非交互式证明技术（non-interactive proof techniques）以进一步降低通信成本。
   • 论文未设置专门的 Limitations 小节；除此之外没有以“局限/未来工作”措辞写出的其他条目。

   实验覆盖范围

   • 通信与延迟实验（RQ1/RQ2）为解析成本模型与实现校准的推算：按域元素计数、不含网络头，延迟假设 1 Gbps 带宽与 1 s 往返延迟；论文未报告真实多机部署的实测。
   • 投毒鲁棒性实验（RQ3）在明文下进行，规模为 n = 100 方、f = 25，聚合器为 BSM、TM、CAF 三种，攻击为 FoE 与 ALIE 两种，数据集为 MNIST、Fashion-MNIST、CIFAR-10。
   • DP 对比实验（RQ4）在单一数据集 EMNIST、单一异构度 α = 1.0、n = 11850、f = 24% 下进行，隐私预算为 ε ∈ {10, 25, 100}，δ = 10⁻⁵；两种机制均在明文下模拟、仅保留隐私记账。
   • 攻击设置为白盒压力测试：FoE/ALIE 被授予对聚合规则和全部诚实更新的访问，强于 Giskard 中拜占庭方的真实视野；论文未报告针对 Giskard 自适应攻击（利用协议结构）的实验。
   • 论文未报告各实验的重复次数与方差，也未报告训练轮数 T 等超参数的具体取值（Theorem 4 的隐私分析以 T 轮计，实验部分未写明）。

   收起这一问

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

   Giskard 用“中位数=安全计数查询序列”的改写和分层委员会 MPC，在去中心化学习中同时获得形式鲁棒性、分布式 DP 和次线性每方通信。

   一篇面向大规模去中心化学习的系统安全论文，提出聚合协议 Giskard，目标是同时解决拜占庭投毒与隐私泄露，并把每方通信量压到随 n 次线性增长。

   • 问题：去中心化学习缺少中心把关，投毒更难防；本地 DP 与鲁棒聚合存在效用冲突，已有 MPC 鲁棒聚合方案全互联或单委员会，扩展性差。
   • 方法：把坐标中位数改写为二分搜索下的一串带噪安全计数查询——本地明文比较、委员会内 MPC 只做比特验证与求和；n 方组织成 m = O(log n) 委员会的 k 叉树，根委员会用 N OISE G EN 分布式生成离散高斯噪声，实现无可信协调者的分布式 DP。
   • 理论结果：作者证明在 f < n/4 静态恶意敌手下 UC 安全（Theorem 2）；输出满足 (f, κ)-鲁棒、乘性因子与 CWMed/GM/Krum 同阶（Theorem 3）；机制为 (ρ+ξDG)-zCDP（Theorem 4）；乐观执行下每方通信 O(d·Niter·log³ n)（Theorem 6）。
   • 通信与延迟：n=10⁶、f/n=0.01 时每方通信量比 A2C 低 722 倍；f/n=0.10 时从 n=10³ 的 392 GB 增至 n=10⁶ 的 1.99 TB（5.1 倍，A2C 约 572 倍）；成本模型下延迟为分钟到小时级，A2C 从 n=10⁵ 起为多小时到多天。
   • 鲁棒性与 DP 效用：明文下 BSM 在 MNIST/Fashion-MNIST 中等异构度与 TM 相当、ALIE 下更高，极端异构下明文 CAF 更鲁棒但作者称其不兼容 MPC；EMNIST（n=11850、f=24%）上 Giskard DP 在 12 个设置中 11 个准确率最高，FoE、ε=100 时 63.1% 对 Local DP+CAF 的 16.0%。
   • 作者结论：Giskard 把形式鲁棒聚合、分布式 DP 与次线性每方通信结合在恶意威胁模型下，使鲁棒去中心化学习可扩展到百万级参与方；后续将研究非交互式证明以进一步降通信。

   收起这一问

相关论文