关于后端:横向联邦学习梯度安全聚合

最近总结本人的公众号的时候，发现一个问题：对于联邦学习的文章，根本都是在讲述纵向联邦学习，对于横向联邦学习的技术波及较少，所以灵机一动之下，决定写几篇文章来压压箱子底。

横向联邦：古代挪动设施能够拜访大量适宜学习模型的数据，这些数据反过来能够大大提高设施上的用户体验。例如，语言模型能够进步语音辨认和文本输出，图像模型能够主动抉择好的照片。然而，这些丰盛的数据通常是隐衷敏感的、数量很大的，或者两者兼有，这可能会阻止记录到数据中心并应用惯例办法在那里进行剖析训练。

所以针对于此研发人员设计了一种新的模式，即让训练数据分布在挪动设施上，并通过汇集本地计算的更新来学习共享模型。咱们将这种模式称为联邦学习。

横向联邦学习面临较多的挑战，大抵总结如下：

设施的异构性，不稳固；
通信网络的异构性、不稳固、不牢靠；
数据的异构性，Non IID 问题（云端数据与机器非公有附属关系，能够通过 Global Shuffle 解决）；
框架的算法效率，通信的频率等；
训练过程中的隐衷性；

本篇文章作为介绍横向联邦学习的首作，次要解说下横向联邦学习的模式、难点、参数的更新形式，后续文章会陆续从以下方面进行介绍；

高效的共享模型构建构建更新模式；
构建更新共享模型中的隐衷平安危险以及应答伎俩；
横向联邦学习的前沿技术；

在上一篇文章中，咱们介绍了横向联邦学习的两种模型更新的形式：

FedSGD
FedAVG

下面介绍的两个算法，所有的梯度、参数等都是通过明文的模式传递的，所以存在泄露问题，上面咱们就介绍下梯度泄露；

梯度会泄露用户的个人信息，在 NeurIPS 2019 中，《Deep Leakage from Gradients》一文指出，从梯度能够推断出原始的训练数据，包含图像和文本数据。

其中报道了一个用 20 行基于 PyTorch 外围代码的样例，使用 GAN 的思维，让分布式训练中的一个攻打方能够从整个模型更新梯度的过程中，通过缩小梯度差别的形式，一直生成与其余参加各方雷同的数据，从而实现『偷取』数据。

Deep Leakage by Gradient Matching

其外围算法是匹配虚构数据和实在数据之间的梯度。在 PyTorch 中，不到 20 行就能够实现它!

def deep_leakage_from_gradients(model, origin_grad): 
  dummy_data = torch.randn(origin_data.size())
  dummy_label =  torch.randn(dummy_label.size())
  optimizer = torch.optim.LBFGS([dummy_data, dummy_label] )

  for iters in range(300):
    def closure():
      optimizer.zero_grad()
      dummy_pred = model(dummy_data) 
      dummy_loss = criterion(dummy_pred, dummy_label) 
      dummy_grad = grad(dummy_loss, model.parameters(), create_graph=True)

      grad_diff = sum(((dummy_grad - origin_grad) ** 2).sum() \
        for dummy_g, origin_g in zip(dummy_grad, origin_grad))
      
      grad_diff.backward()
      return grad_diff
    
    optimizer.step(closure)
    
  return  dummy_data, dummy_label

在视觉图片上的试验成果

在语言模型上的试验成果

然而其实早在 2017 年，谷歌的 Bonawitz 等发表了《Practical Secure Aggregation for Privacy-Preserving Machine Learning》这篇文章，具体论述了针对梯度泄露攻打设计的 Secure Aggregation 协定，咱们简称为 SMPC.

前置常识

机密分享：能够参考我专栏外面的文章，隐衷计算根底组件系列 - 机密分享

DH 密钥替换：能够参考我专栏外面的文章，隐衷计算加密技术根底系列 -Diffie–Hellman key exchange

上面咱们再简略分享下机密分享和 DH 秘钥替换，这里只做简略的介绍，如果有须要具体理解这两个知识点内容的同学，请移步到下面的链接。

上面简略介绍下机密分享，有想全面理解的，请移步隐衷计算根底组件系列 - 机密分享

次要是介绍阈值机密分享，阈值机密分享的基本思路是，基于机密分享的便携性与安全性的考量，如果有个 n 个机密分片，咱们只须要凑齐 k（1 < K <n）集体，他们手中的信息拼凑起来，就能够获取机密。

那么如何能力做到这点呢？有以下几个问题须要思考；

随机性：筛选的 k 集体，须要是随机筛选的 k 集体，不能是一个固定的选取。
偶然性：随机选出的这 k 集体，必须能须要的数字进行解密。

那么，是什么样的技术能够实现呢？

大家还记得学习《线性代数》的时候吧，在线性代数的课上，k 个参与者，相当于 k 个变量，那么须要 k 个方程就才能够解进去。

计算逻辑

机密数字：D；

参与方：n 个参与者，$D_1, D_2, …，D_n$

一个大的素数：p，束缚这个素数要大于 D 和 n

首先，结构出 n 个方程式，结构公式 $D_i = q(i) = \sum_{j=0}^{j=k-1}a_j * i^j$，这个公式是从文章 How to Share a Secret 外面剖析的，说白了就是多项式，列举如下：
- 公式开展：$$D_i = q(i) = D + a_1 * i + … + a_{k-1} * i^{k-1}$$，其中 $a_0 = D$；
- 公式举例（假如 k 为 3，n 为 10）
  
  $D_1 = q(1) = D + a_1 + a_2$$，其中 $a_0 = D$；
  
  $D_2 = q(2) = D + 2a_1 + 4a_2$$，其中 $a_0 = D$；
  
  ……
  
  $D_{10} = q(10) = D + 10a_1 + 100a_2$$，其中 $a_0 = D$；
而后，目前的方程组外面，还有 $a_1 — a_{k-1}$ 的（k-1）个变量，那么这几个变量如何获取呢? 依据 Adi Shamir 在 ACM 公布的《How to Share a Secret》的形容，The coefficients $a_1 ….. a_{k-1} $in q(x) are randomly chosen from a uniform distribution over the integers in [0, p), 也就是说在 [0,p) 的范畴内均匀分布中进行获取。
而后，原始文章中也对 $D_1, D_2, …，D_n$ 进行了束缚是大素数的取模，不过这了解这个大素数的 p 的作用更多是管制咱们抉择 $a_1 — a_{k-1}$ 的大小的，避免数据的过于收缩；（惟一解的问题，在结构的时候根本能够躲避，大家能够自行证实，提醒一下：系数行列式不等于零）；
最初，将这个 n 个方程划分给 n 个参与者。须要计算的时候，只须要将 k 个方程获取进行联结计算就能够计算出 a 也就是机密 D。

案例介绍

上面通过一个案例，介绍下基于多项式的阈值机密分享。

输出
- 机密数字：D = 88
- 参与方：10 个，$D_1, D_2, …，D_10$
- 大素数：991
- 解密阈值：3
加密逻辑
- 首先，生成方程组
  
  $D_1 = q(1) = 88 + a_1 + a_2$，其中 $a_0 = D$；
  
  $D_2 = q(2) = 88 + 2a_1 + 4a_2$，其中 $a_0 = D$；
  
  ……
  
  $D_{10} = q(10) = 88 + 10a_1 + 100a_2$，其中 $a_0 = D$；
- 而后，基于素数生成 $a_1 — a_{k-1}$ 的值，设定 $a_1 = 1, a_2 = 2$，则方程组如下，并且
  
  $D_1 = q(1) = D + a_1 + a_2 = 91$，其中 $a_0 = D$；
  
  $D_2 = q(2) = D + 2a_1 + 4a_2 = 98$，其中 $a_0 = D$$；
  
  ……
  
  $D_{10} = q(10) = D + 10a_1 + 100a_2 = 298$，其中 $a_0 = D$；
- 而后，可见 $D_1，D_2, …, D_10$ 都小于咱们设置的素数 991，合乎预设，所以将这 10 个方程散布散发到 10 个参与者分片 Server。
解密逻辑
- 首先，假如抽取参与者 1，2，10 的方程组成方程组进行解密，则方程组如下：
  
  $$D_1 = q(1) = D + a_1 + a_2 = 91$$
  
  $$D_2 = q(2) = D + 2a_1 + 4a_2 = 98$$
  
  $$D_{10} = q(10) = D + 10a_1 + 100a_2 = 298$$
- 最初，求解这个方程组，则 $D=88, a_1 = 1, a_2 = 2$，则解出机密 D。

上面先简略介绍下 DH 秘钥替换，有想全面理解的，请移步隐衷计算加密技术根底系列 -Diffie–Hellman key exchange

最简略，最早提出的这个协定应用一个质数 p 的整数模 n 乘法群以及其原根 g。上面展现这个算法，绿色示意非机密信息， 红色粗体 示意机密信息：

由下面的流程能够看到，Alice 和 Bob 最终都失去了同样的值，因为在模 p 的状况下 $g^{ab}和 g^{ba}$ 相等。留神 $a、b 和 g^{ab}=g^{ba} mod p$ 是机密的。

然而其实早在 2017 年，谷歌的 Bonawitz 等发表了《Practical Secure Aggregation for Privacy-Preserving Machine Learning》这篇文章，具体论述了针对梯度泄露攻打设计的 Secure Aggregation 协定。

平安地聚合用户数据向量的第一次尝试波及到每对用户 u,v，用户 u < v 批准一个机密的总程序，这个机密被记为 su,v。每个用户用他们与所有其余用户构建的机密蒙蔽了他们的输出值 xu。如果 u 将 su,v 加到 xu 上，v 从 xv 中减去它，那么当它们的向量相加时，掩码就会被勾销，但它们的理论输出不会显示进去。模式上，每个用户的盲值是

P 是一个公共的大的素数。

整体流程如下：

下面的计划是存在问题的，假如用户 2 在上传 $y_2$ 的时候掉线了，没有把 $y_2$ 发送给服务器，那么这一轮全局更新中，服务端的聚合值 $\sum_{i=0}^{i=3}y_i$ 是没有意义的。

下面的计划，在有用户掉线的时候，存在聚合时效的状况。所以思考复原计划，比方用户 2 掉线的时候，进行复原阶段的解决，对于用户 2 的增加的扰动值 $s_{1,2},s_{2,3}$ 来说，用户 1 和用户 3 是晓得的，所以服务器只有询问用户 1 和用户 3，获取相应的扰动值，就能够剔除影响，实现聚合。

问题
- 在回复机密之前，其余用户可能会在复原阶段退出，这将须要一个额定的复原阶段来报告新删除的用户的机密，所以这个计划的要求比拟严格，思考一个较为涣散的计划替换。
- 提早的通信可能会导致服务器认为某个用户被删除了，从而能够从所有其余用户那里复原他们的秘密。然而如果是网络提早，将导致服务器可能在收到用户的机密后解密他们的个人信息。

针对下面存在的问题，采纳双掩码机制，即应用两个随机数，并且退出机密分享的机制。

为用户 u 引入另外一个随机数 $b_u$。所有的 $b_u$ 和 $s_{**}$ 均应用机密分享的形式分享给其余用户，在复原阶段，至多 t 个用户能力复原一个机密。
在聚合阶段
- 如果用户 u 掉线，只聚合第一个分享的随机数 $s_{**}$;
- 如果用户 u 不掉线，则聚合两个随机数 $b_u$ 和 $s_{**}$；\

整体流程如下，因为这个整体流程较为简单，所以本问仅仅进行大体介绍，后续会另开一篇文章进行具体的介绍。

Deep Leakage from Gradients
Secure Analytics: Federated Learning and Secure Aggregation
Federated Learning of Deep Networks using Model Averaging
Practical Secure Aggregation for Privacy-Preserving Machine Learning

集体介绍：杜宝坤，隐衷计算行业从业者，从 0 到 1 率领团队构建了京东的联邦学习解决方案 9N-FL，同时主导了联邦学习框架与联邦开门红业务。
框架层面：实现了电商营销畛域反对超大规模的工业化联邦学习解决方案，反对超大规模样本 PSI 隐衷对齐、平安的树模型与神经网络模型等泛滥模型反对。
业务层面：实现了业务侧的开门红业务落地，创始了新的业务增长点，产生了显著的业务经济效益。
集体比拟喜爱学习新货色，乐于钻研技术。基于从全链路思考与决策技术布局的考量，钻研的畛域比拟多，从工程架构、大数据到机器学习算法与算法框架均有波及。欢送喜爱技术的同学和我交换，邮箱：baokun06@163.com

本人撰写博客曾经很长一段时间了，因为集体涉猎的技术畛域比拟多，所以对高并发与高性能、分布式、传统机器学习算法与框架、深度学习算法与框架、明码平安、隐衷计算、联邦学习、大数据等都有波及。主导过多个大我的项目包含批发的联邦学习，社区做过屡次分享，另外本人保持写原创博客，多篇文章有过万的浏览。公众号 秃顶的码农 大家能够依照话题进行间断浏览，外面的章节我都做过依照学习路线的排序，话题就是公众号外面上面的标红的这个，大家点击去就可以看本话题下的多篇文章了，比方下图（话题分为：一、隐衷计算二、联邦学习三、机器学习框架四、机器学习算法五、高性能计算六、广告算法七、程序人生），知乎号同理关注专利即可。

<font color=red> 所有有为法，如梦幻泡影，如露亦如电，应作如是观。</font>

本文由 mdnice 多平台公布

关于后端:横向联邦学习梯度安全聚合

一背景

二横向联邦学习的平安问题

三前置常识

1 简略介绍下机密分享

2 简略介绍下 DH 秘钥替换

三横向联邦学习的参数更新机制

2.2 平安聚合算法简介

3.2 First Attempt: Masking with One-Time Pads

3.3 Second Attempt: Masking with One-Time Pads with Recovery

3.4 Final Attempt: Double-Masking

四参考资料

五番外篇

六公众号导读

一 背景

二 横向联邦学习的平安问题

三 前置常识