Biscotti: A Blockchain System for Private and Secure Federated Learning"译为“Biscotti：一个用于隐私和安全联邦学习的区块链系统”

这是IEEE Transactions on Parallel and Distributed Systems 21（简称TPDS）上的一篇联邦学习和区块链相结合的文章。众所周知，TPDS是CCF A类期刊，上面论文的质量都不错，因此选读了这篇论文。以下内容，是自己阅读完后的一些小笔记，有不懂和疑问的地方，记录的都是个人认为重点的地方。

• 原文链接：Biscotti: A Blockchain System for Private and Secure Federated Learning

需要注意的是，本文中提到的见附录，但是我在下载的文献pdf中并没有看到附录。因此，还需要结合该作者18年发表在arXiv上的一篇论文来理解。以下是原文链接：

Biscotti: A Ledger for Private and Secure Peer-to-Peer Machine Learning

一、背景及挑战

1.1 相关背景

联邦学习（FL）中的客户端需要完全相信中央服务器进行协调，且恶意客户端可能通过投毒攻击来损害模型性能。当前，FL主要受到投毒攻击和信息泄露攻击两种类型的攻击。

• 1）投毒攻击：一般是指恶意客户端污染数据或模型，从而使得全局模型难以收敛或降低准确度。
• 2）信息泄露攻击：文中也可以叫推理攻击，指通过某一上传的参数信息，从而推理出客户端个人隐私信息。

而以往的方案都是通过集中的异常检测、差分隐私和安全聚合进行防御。但是，目前还不存在同时解决这两种威胁的隐私和去中心化的解决方案。况且，传统方法不适用于缺乏可信中心权威的训练过程。

综上，本文提出了一种完全去中心化的Peer多方机器学习方法，它使用区块链和加密原语来协调peer客户端之间的隐私包含ML过程，称为Biscotti。

Biscotti使用了基于PoF（Proof of Federation）的一致性哈希和可验证随机函数（VRF）结合，为peer节点选择关键的角色，这些角色将帮助协调模型更新的隐私和安全性。为防止peer通过Multi-Krum防御毒害模型，通过差异化的私有噪声提供隐私，使用shamir秘密共享进行安全聚合。

首先理解相关的小知识。

• 1）PoF：简称联邦共识协议，大概理解为客户端对每轮训练的模型状态达成一致性协议。（详细内容需要找相关文献，我还没深入调研）
• 2）VRF：简称可验证随机函数，大概理解是一种输入某个值，输出一个随机值（包含生成者的私钥签名）和可验证的值（无需私钥即可验证该随机值是它产生的）。VRF具有三大特性：可验证性、唯一性和随机性。（可验证随机函数详细介绍）
• 3）Multi-Krum：这是一种聚合算法，由krum聚合算法演变而来。krum聚合算法指在若干个局部模型种选择一个与其他模型都相似的模型作为全局模型。这里将欧氏距离作为相似性的评判标准。而Multi-Krum就是执行多次krum算法，具体而言，首先执行一次krum算法，将得到的梯度从总的里面删除，然后再次迭代执行krum算法，到最后将每轮迭代选出的梯度进行krum算法，选择最终的全局模型。
• 4）Shamir秘密共享：也称为门限秘密共享，是指一份秘密值分为$n$份，至少拥有$t,(1<t<n)$份时，就可以恢复出秘密值。（详细内容，我会在“密码学相关小知识"栏进行更新）

1.2 关键挑战

• 1）Sybil Attack：使用VRF和PoF来解决。
• 2）中毒攻击：使用Multi-Krum聚合算法更新验证。
• 3）信息泄露攻击：VRF验证者peer、使用预先承诺的噪声进行差分隐私更新。
• 4）差分隐私的效用损失：安全更新聚合和加密承诺。

二、主要内容

设计目标：

• 1）聚合生成最优全局模型。
• 2）通过验证peer模型更新预防中毒。
• 3）保持peer训练数据隐私以预防信息泄露攻击。
• 4）获得影响而无需获得充足的stake预防共谋peers。

分布式账本中的每个区块就代表了每次SGD的迭代，账本包含每次迭代全局模型中的state。

主要有八个步骤：

• 1）每个peers本地计算SGD更新。
• 2）因为SGD更新必须保持隐私，每个peer首先用差分隐私噪声masks（掩盖）更新。
• 3）这个噪声从每个客户端唯一的一组噪声peer中收集，并由VRF选择。
• 4）掩盖更新被验证委员会进行验证以防止投毒攻击，该验证委员会是由VRF算法选举出来的，若peer的掩盖更新可以通过multi-krum算法的验证，那么验证委员会的每个成员会为该peer的unmasked更新签署一个承诺。（不是很理解这句话）
• 5）若大多数委员会的成员都签署了更新。
• 6）这个更新就会通过shamir秘密共享协议分成多份。
• 7）然后多份更新就会发送到聚合委员会中进行聚合，聚合委员会执行一个安全协议去聚合unmasked的更新。完成聚合后，所有对梯度有贡献的peer以及担任了验证和聚合委员会的peer都将在系统中获得额外的stake（权益）。
• 8）聚合后的更新添加到全局模型中，并存储在一个区块内，同时将更新后的模型广播给所有的节点，并产生的区块会被添加到账本中。

2.1 训练初始化

每个peer使用genesis（原始）区块中的信息初始化训练过程。每个peer从生成区块中获取以下信息：

• 1）模型的初始状态 w 0 w_0 w0​，期望的迭代次数$T$。
• 2）创建SGD更新承诺的公钥$PK$。
• 3）公钥系统中所有其他peer的 P K i PK_i PKi​，用于验证过程中创建和验证签名。
• 4）每个peer对$T$次SGD迭代的差分隐私噪声 ζ 1.. T zeta_{1..T} ζ1..T​的预承诺。
• 5）在peer之间的初始stake分配。
• 6）当添加新区块时执行的stake更新函数。

2.2 区块链设计

每个区块包含前一个区块的哈希指针，还有多个peer的SGD更新的聚合$\Delta w$和在迭代$t$次时的全局模型 w t w_t wt​。新添加到账本中的区块存储了多个peer的聚合更新 ∑ Δ w i sumDelta w_i ∑Δwi​。为了验证聚合是真实计算的，需要将单个更新包含在区块中。然而，单独存储会泄露个人私有训练数据，本文使用多项式承诺来解决这个问题。

通过在区块中包含每个peer $i$的承诺列表 C O M M ( Δ w i ) COMM(Delta w_i) COMM(Δwi​)，可以提供聚合的隐私性和可验证性。若提交的更新列表等于聚合总和，即以下等式成立
C O M M ( ∑ Δ w i ) = ∏ i C O M M ( Δ w i ) COMM(sumDelta w_i) = prod_i COMM(Delta w_i) COMM(∑Δwi​)=i∏​COMM(Δwi​)

2.3 使用权益进行角色选举

每次迭代中，一个由peer的stake权重的一致性哈希进行选举出噪声者、验证者和聚合者。PoF确保peer的影响受其stake的限制。Peer可以在给定迭代中被分配多个角色。验证和聚合委员会对所有peers是相同的，但噪声委员会对每个peers是唯一的。

最后一个区块的初始SHA256被重复的进行哈希，每个新哈希被映射到一个哈希环，在这个哈希环中，根据他们的权益比例分配给peers，直至选出正确数量的验证者和聚合者委员会。

攻击者无法预测未来区块的状态，则不可能猜测出一致性哈希的输出，并制定策略进行攻击。

2.4 噪声协议

为防止信息泄露攻击，peer在验证过程中使用差分隐私，通过添加正态分布采样的噪声来隐藏自己的更新。

攻击者可能恶意使用噪声协议进行投毒或信息泄露攻击。若没有提前承诺噪声，那恶意参与方在完成本地梯度更新后，再生成自己的噪声，很容易进行伪造。

• 1）例如：一个peer可以发送一个有毒的更新 Δ w p o i s o n Delta w_{poison} Δwpoison​和添加噪声 ζ p zeta_p ζp​，使其更新类似于一个诚实更新$\Delta w$，正如 Δ w p o s i o n + ζ p = Δ w Delta w_{posion} + zeta_p = Delta w Δwposion​+ζp​=Δw。在最终梯度聚合时，噪声会被去掉，那么就会把投毒的更新加到了最终的模型中，从而敌手完成了攻击。
• 解决办法：关键在于更新$\Delta w$的承诺时间点，若协议规定对更新承诺是在参与方获取噪声前，就没有办法作假了。此噪声并未来自参与方自己，而是通过VRF选举出来的噪声委员会，即这个参与方无法提前预知这个噪声，参与方也无法预知更新值，即无法根据噪声值和更新来求出投毒更新值。因此，一定要先产生更新，再添加噪声，若规定必须先对更新值做出承诺，那么该参与方不知道噪声的前提下，就无法构造投毒更新，即使构造了，在后面的验证过程也会被发现。
• 2）例如：有噪声的peer A和验证者B共谋攻击受害者peer C时，也可能发送信息泄露攻击。噪声peer A可以提交0噪声，完全不隐藏原始梯度值。B是验证者，当peer C添加了来自A的噪声，并将噪声梯度发送给验证者B时，B进行验证就知道是A提供的噪声0，就可以看到C传递的更新是unmasked更新，就可以对客户端C的梯度进行重构出训练数据。
• 解决办法：参与方C的噪声提供者与其私钥相关（签名噪声委员会选举时，参与方的私钥被作为参数传递给VRF函数的），只要C的私钥不泄露，谁也无法提前知道C的噪声委员会是由哪个参与方构成。就算有共谋，这个恶意的噪声提供者不一定会被C采纳，且噪声提供者的数量不止一个，里面也不可能全为恶意的噪声提供者，就算其中一个提供了0噪声，那么也无法获取真的更新值。

每个参与方对训练的每次迭代产生一个噪声和该噪声的承诺。

• 1）每次包含某个参与方i在T轮迭代中所有的噪声；
• 2）每列表示在第t次迭代中可能被使用的噪声；
• 3）当参与方准备在某次迭代中贡献自己的更新时，他会通过噪声VRF选举一个噪声委员会，并从中获取噪声提供者的噪声。
• 4）他们提供的噪声都是提前做过承诺的噪声；
• 5）这个参与方使用验证VRF去选举验证者集合；
• 5）该参与者把如下信息发送给验证者集合，如添加噪声的更新、噪声的承诺、未添加噪声更新的承诺和噪声委员会的选举证明。

2.5 验证协议

验证者peer对接收的更新集合运行Multi-krum算法，通过接收每轮接收到的大部分更新来过滤恶意的更新。每个验证者受到每个参与方$i$的如下信息：

• 1）添加噪声后（mask SGD）的更新： ( Δ w i + ∑ k ζ k ) (Delta w_i + sum_k zeta_k) (Δwi​+∑k​ζk​)。
• 2）对SGD更新的承诺： C O M M ( Δ w i ) COMM(Delta w_i) COMM(Δwi​)。
• 3）一组$k$个噪声承诺： { C O M M ( ζ 1 ) , C O M M ( ζ 2 ) , . . . , C O M M ( ζ k ) } {COMM(zeta_1),COMM(zeta_2),...,COMM(zeta_k)} {COMM(ζ1​),COMM(ζ2​),...,COMM(ζk​)}。
• 4）一份关于$k$个噪声提供者的身份VRF证明。

当验证者收到上述信息后，会按照如下公式进行验证：
C O M M ( Δ w i + ∑ k ζ k ) = C O M M ( Δ w i ) ∗ ∏ k C O M M ( Δ ζ k ) COMM(Delta w_i + sum_k zeta_k) = COMM(Delta w_i) *prod_k COMM(Delta zeta_k) COMM(Δwi​+k∑​ζk​)=COMM(Δwi​)∗k∏​COMM(Δζk​)
只要验证者收到了足够多的更新$R$，他会使用multi-krum算法去挑选最好的更新。

• 1）对每个peer $i$，验证者计算分数$s(i)$，即$i$更新到最接近$R-f-2$欧式距离的和，即
  s ( i ) = ∑ i → j ∣ ∣ ( Δ w i + ∑ i , k ζ i , k ) − ( Δ w j + ∑ j , k ζ j , k ) ∣ ∣ 2 s(i) = sum_{ito j}||(Delta w_i + sum_{i,k} zeta_{i,k}) - (Delta w_j + sum_{j,k} zeta_{j,k})||^2 s(i)=i→j∑​∣∣(Δwi​+i,k∑​ζi,k​)−(Δwj​+j,k∑​ζj,k​)∣∣2
  其中$i\to$