{"content":{"title":"Fast HotStuff 理解和思考","body":"原文：https://xufeisofly.github.io/blog/fast-hotstuff\r\n\r\n# 原生 HotStuff 的局限\r\n\r\n相比其他 BFT 类共识算法，HotStuff（下文简称 HS） 通过增加一个投票阶段的方式实现了正常和异常情况下 O(n) 的通讯复杂度，并且没有牺牲响应性（Responsiveness）。具体请参考文章[HotStuff 工程设计与实现](https://xufeisofly.github.io/blog/shardora-hotstuff)。\r\n\r\n然而，HS 有以下两个局限：\r\n\r\n- **交易确认延迟高**\r\n\r\n为了在超时视图切换时达到线性时间复杂度，同时避免像 Tendermint 之类共识一样牺牲系统响应性，HS 在 Lock 之前增加了一个 Key 阶段（即 Prepare 阶段），成为了一个三阶段投票的共识算法。多数工程实现都采用 Chained HotStuff，因此多一个阶段对吞吐量并没有太大影响。然而交易打包到最终提交期间的延迟却增大了一个视图的时间。\r\n\r\n- **分叉攻击影响吞吐量**\r\n\r\nHS 对于新交易的验证逻辑保证了共识协议的安全性（Safety）和活性（Liveness）。在 Chained HotStuff 中，每个提案通过 QC 指针与前一个提案相连，当一个 Leader 节点打包新的提案时，并没有要求这个提案必须从最新块之后打包，只需要在最新的 Locked 提案之后即可。这就使得恶意节点可以进行分叉攻击。如下图。\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/rGO80Ev1669e35a0e20e2.png)\r\n\r\n新提案 View4 本应该从 View3 之后出块，但恶意节点可以选择从 View1 （最新 Locked 视图）之后出块而且能顺利通过验证。这种攻击行为不会对系统安全性造成影响，却令吞吐量大幅下降，极端情况如下图。\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/MtsBfnJq669e35ad89b08.png)\r\n\r\nFast HotStuff 论文中给出了在持续的分叉攻击下，随着拜占庭节点数量 f 增加，系统吞吐量的改变情况。可以看到 f 增加时，系统吞吐量快速下降（Average Case & Worst Case）。\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/vrd89Obq669e35bbcdd55.png)\r\n\r\n# Fast HotStuff 逻辑\r\n\r\nFast HotStuff(下文简称 FHS) 的核心逻辑，就是**确保新提案永远从最长的链后继续出块**，**即 Leader 确保提案中的 QC 是最新的 QC（即 HighQC），并为之提供证明**。为此 FHS 分别讨论了正常路径（Happy path） 和超时路径（Unhappy path）两种情况，如下图：\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/SsB1tJH5669e35cb8b4b1.png)\r\n\r\n- Happy path: 由于提案的 View 是 HighQC 决定的，因此在 Happy path 下，Replica 只需要要求新提案的 View 必须大于自己的 CurView 即可保证 QC 为 HighQC。\r\n- Unhappy path: 超时触发视图切换后，Leader 收集 2/3+1 节点各自的 HighQC 及其签名，生成聚合签名 AggQC，作为 HighQC 的证明。新提案必须根据此 HighQC 生成。\r\n\r\nFHS 论文中证明了，只要满足「新提案永远打包 HighQC」这个事实，即可保证**提案在收到两个 QC 后就可以安全提交**，且不需要像 Tendermint, Casper 和 两阶段 HotStuff 那样等待一个网络延迟。\r\n\r\n> Indeed, the presence of the proof for the *highQC* guarantees that a replica can safely commit a block after two-chain without waiting for the maximum network delay as done in two-chain HotStuff [7], Tendermint [5], and Casper. — 《Fast HotStuff》\r\n> \r\n\r\n然而，由于 Unhappy path 视图切换时需要收集 2/3+1 节点对各自 HighQC 的签名，FHS 需要使用能够对不同消息进行签名的聚合签名来替换原生 HS 的阈值签名，这使得 Unhappy path 视图切换的通讯复杂度升级为 O(n^2)。\r\n\r\n> Unfortunately, we are not able to avoid the transfer of quadratic view change messages over the wire during view change due to primary failure (also called unhappy path). — 《Fast HotStuff》\r\n> \r\n\r\n好在 FHS 优化了验证逻辑，只需要验证两个 QC，在节点数量可控的情况下，实测计算耗时没有太大影响。下文对聚合签名进行介绍。\r\n\r\n## FHS 使用聚合签名\r\n\r\n论文中，FHS 和原生 HS 有个很大的区别，就是使用聚合签名而非阈值签名，其实不仅仅是 FHS，如 LibraBFT 等工程实现中，也都将阈值签名换成了聚合签名，这是因为聚合签名相比阈值签名有很多工程优势。\r\n\r\n- **阈值签名（Threshold Signature）**\r\n    \r\n    基于沙米尔秘密分享原理（多项式），每个节点初始时仅拥有部分私钥和联合公钥。利用部分私钥对同一个消息体进行签名，当 Leader 收到任意 m 个部分签名后可以从中恢复出完成的签名并使用联合公钥进行验证。\r\n    \r\n    阈值签名最大的问题是一开始需要进行 DKG（分布式密钥生成）来分发部分私钥并生成联合公钥，并且分发的过程需要进行复杂的验证。然而一旦 DKG 完成，在签名和验签阶段效率较高。\r\n    \r\n- **聚合签名（Aggregation Signature**）\r\n    \r\n    能够将 m 个签名「压缩」成一个聚合后的签名，仅对该聚合后的签名进行验证就能证明这 m 个签名的合法性，不需要单独一个个验证，但验证时仍然需要使用 m 个签名对应的公钥，因此聚合签名中是包含「谁签了名」这个信息的。\r\n    \r\n    聚合签名最大的特点是节省了存储 m 个签名所用的空间，但计算过程时间复杂度比阈值签名要高，其验证过程看似一步完成，本质上仍然需要一个 m 次循环逐一进行配对计算。\r\n    \r\n    此外聚合签名有一个重要特点，就是允许对不同的消息体做签名，这和阈值签名是很不一样的。阈值签名要求所有的部分签名都是针对同一个消息的，否则无法恢复出完成签名。这也是 FHS 使用聚合签名的主要原因。\r\n    \r\n\r\n下面代码是 bls12 的聚合签名验证逻辑，可见验证过程拥有线性时间复杂度：\r\n\r\n```go\r\nfunc (bls *bls12Base) coreAggregateVerify(publicKeys []*PublicKey, messages [][]byte, signature *bls12.PointG2) bool {\r\n\tn := len(publicKeys)\r\n\t// ...\r\n\tengine := bls12.NewEngine()\r\n\r\n\t// O(n) 复杂度\r\n\tfor i := 0; i < n; i++ {\r\n\t\tq, err := engine.G2.HashToCurve(messages[i], domain)\r\n\t\tif err != nil {\r\n\t\t\treturn false\r\n\t\t}\r\n\t\tengine.AddPair(publicKeys[i].p, q)\r\n\t}\r\n\r\n\tengine.AddPairInv(&bls12.G1One, signature)\r\n\treturn engine.Result().IsOne()\r\n}\r\n```\r\n\r\n无论是阈值签名和聚合签名都可以实现 HS 所需要的 m-n 签名。\r\n\r\n对比阈值签名，聚合签名最大优点是节省了复杂的 DKG 过程，并且可以记录签名者信息，这在 HS 实现时可以避免恶意不投票行为。然而，聚合签名的验证过程时间复杂度高，如果有 N 个签名进行了聚合，那么多这个聚合签名验证时仍需要 N 次配对计算，随着节点数量的增多，聚合签名的验证时间会线性增高，同时由于 AggQC 中携带了 `2/3+1` 节点的 HighQC，Unhappy path 下新提案的带宽也会增加。\r\n\r\n下表为阈值签名和聚合签名特性对比。\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/wRw1EHlQ669e35e01066a.png)\r\n\r\nFHS 在 Unhappy path 时对 HighQC 进行聚合签名生成 AggQC，打包了 AggQC 的提案相当于告诉所有的 Replicas 自己是从最长链之后出块的，因此可以避免分叉攻击，Replica 需要对 AggQC 进行两个方面的验证：\r\n\r\n- **验证 AggQC 是否合法**。如果合法，说明该 AggQC 确实饱含了 `2/3+1` 个节点对于自己 HighQC 的签名。\r\n- **验证 AggQC 中最高 HighQC 是否合法并且是否是最新的**。如果仅验证 AggQC 合法性，恶意 Leader 完全可以使用一个旧的 AggQC 作为证明，因此 Replica 还要对 AggQC 其中的 HighQC 进行验证，确保确实比本地的 HighQC 高。\r\n\r\n一旦 Replica 发现 AggQC 不满足上述两个条件，就会做出惩罚，这就增加了恶意 Leader 进行分叉攻击的成本。\r\n\r\n### 对于工程实现的一个疑问\r\n\r\n和 TC 方案不同，TC 方案中所有的节点是对 CurView 做阈值签名的，这就要求 `2/3+1` 节点的 CurView 是一致的，而 FHS 并不需要保证这一点，那么当 Leader 收到 `2/3+1` 个超时消息时，是如何能保证这 m 个消息是针对统一视图产生，里面没有旧的消息呢？\r\n\r\n即，在异步情况下，新 Leader 是如何得知这 2/3+1 对 HighQC 的签名是针对统一视图的？🤔\r\n\r\n## 不同签名对 HotStuff 激励机制的影响\r\n\r\n阈值签名和聚合签名还有一个区别，即阈值签名无法得知具体参与签名的节点是哪些，而聚合签名可以。因此阈值签名方案便存在一个问题：**无法甄别恶意 Replica 的故意不投票行为**。\r\n\r\n对于一个恶意的 Replica，在收到诚实 Leader 的提案后可以不进行投票，而在收到与之串谋的恶意 Leader 提案时再投票，由于使用了阈值签名，我们无法知道参与了投票的节点有哪些，导致这种行为并不会收到任何惩罚。而当一个恶意行为零成本时，就会导致恶意节点越来越多，最终打破拜占庭假设，造成共识系统彻底崩溃。\r\n\r\n而使用了聚合签名便可解决该问题，如 LibraBFT。聚合签名可以得知具体参与投票的节点身份，因此可以：\r\n\r\n- 给参与投票的节点一定激励\r\n- 提升参与投票的节点下次称为 Leader 的概率\r\n\r\n不过需要说明的是，聚合签名由于是 Leader 生成的，该 Leader 完全可以对该投票节点的列表进行恶意操作，比如去掉自己不喜欢的节点，而放入串谋节点的签名。因此我们虽然可以保证聚合签名的正确性，但却无法完全保证聚合签名的真实性，这个问题需要额外进行解决。下图中示意了恶意 Leader 在收集投票签名时，故意不使用 Sig3 而使用 Sig4 的过程。\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/07/2dw0ONuq669e35f0110f1.png)\r\n\r\n\r\n## 总结\r\n\r\nFHS 解决了 HS 工程实现中的重大问题，即分叉攻击导致吞吐量降低，并且减少了一个阶段使得交易确认延迟降低。\r\n\r\n为此，其使用聚合签名代替阈值签名，除了可以保证 Unhappy Path 下的依然从最长链之后出块以外，还带来了诸多工程上的便利。如消除 DKG，解决避免恶意不投票行为等。\r\n\r\n但对于超大量节点的共识场景（粗估超过 2000 节点），由于聚合签名验证过程提升了复杂度，FHS 的可行性需要额外验证。同时，超时的工程实现中可能仍然需要生成 TC 已保证视图的一致性。\r\n\r\n## 参考资料\r\n\r\n- [HotStuff: BFT Consensus in the Lens of Blockchain](https://arxiv.org/abs/1803.05069)\r\n- [Fast-HotStuff: A Fast and Robust BFT Protocol for Blockchains](https://arxiv.org/pdf/2010.11454)\r\n- [State Machine Replication in the Libra Blockchain](https://diem-developers-components.netlify.app/papers/diem-consensus-state-machine-replication-in-the-diem-blockchain/2019-06-28.pdf)\r\n- [https://github.com/relab/hotstuff](https://github.com/relab/hotstuff)"},"author":{"user":"https://learnblockchain.cn/people/18365","address":null},"history":"bafkreihlo4oims7sfryulw322mmblf5wcflnpy7e6bjkxgoh25xuipojbm","timestamp":1722302484,"version":1}