前序

共识算法的正确性可以分为以下两个性质：

  1. 安全性 (safety)，也叫一致性 (agreement)，表示 所有正确节点执行的请求（包括顺序）一致，即其最后达成的共识一致且信息正确
  2. 活性 (liveness)，也叫可终止性 (termination)，表示 共识总能在有限时间内达成。

    换句话说，如果没有安全性，不同节点就可能执行了不同请求，使系统失去了一致性，这是不可容忍的；如果没有活性，那么系统会永远“卡住”，无法处理请求。

背景现状

基于leader的hotstuff

每轮流程和原始pbft类似，只是都先把消息发给leader，再由leader广播给所有节点。

待优化问题

  1. 可以发现网络消息数从$O(N^N)$下降到$O(N)$，但因为每个prepareQC包含2f + 1 签名，所以通信量复杂度还是$O(N^N)$。

    Q：如何理解通信复杂度？

  2. 缺点是如果leader作恶，那么共识无法达成，需要切换leader。切换开销很大，因为相当于重新需要发送一遍信息。

    • 视图切换需要将新主节点的身份信息广播给其他节点，以便其他节点能够知道新主节点是谁，并与它建立新的通信连接。这些消息需要在网络中传递，因此视图切换消息的传递可能是一项非常昂贵的操作。另外，在 HotStuff 协议中，每次视图切换都需要广播至少 3 条消息
    • 视图切换过程中状态同步的开销：当视图切换完成后，新主节点需要将全局状态同步给其他节点，以便其他节点能够继续验证交易和生成新块。这可能需要耗费大量的带宽和计算资源，尤其是在区块链网络很大的情况下。此外，在状态同步的过程中，如果存在错误或冲突的信息，可能会需要回滚部分状态并重新同步所有数据。

通信复杂度问题

传统解决方案

包含2f + 1 签名信息的prepareQC，占用空间降至O(1)，整个通信量复杂度下降到O(N)。
【需要详细了解！】

门限算法

Leader问题

leader可能做什么恶

目的：破坏共识，不让他们达成一致；最终目的不是篡改消息，他篡改了也不能上链。

hotstuff的步骤

  • 篡改消息
    • 给每个结点发送篡改后的相同的消息，其他结点验证这是错误信息，造成无法达成共识，无法将正确信息上链。
    • 给每个结点发送不同的消息，造成无法达成共识

      分析：
      在prepare阶段，主节点向其他结点发送消息——

      1. 消息都有签名验证功能，所以即使篡改了消息，其他结点也能判断出这个leader是错误的，那么最终造成的结果是，正确的区块无法被共识上链，因为leader直接篡改了。所以情况一主要是正确的区块无法被共识上链的问题
      2. 当然，签名不一定要对整个消息进行签名，一些无关紧要的信息，如时间等无需进行签名（否则存储验证成本开销太多），这样的话结点可能就篡改信息了
        【举个例子】：将军说“向南门发动攻击，传令时间是14：00”，只有“向南门发动攻击”被加密了。其他结点可以根据加密签名信息来判断主节点传递的信息是否正确。如果间谍士兵传令“向北门发起攻击，传令时间是14：00”，那么其他士兵解密会发现消息无法完成验证。但是“14：00”，有可能没有被加密，间谍士兵可能给其他士兵分别传令“13：00”、“12：00”，这样也无法达成共识。
        在commit阶段，主节点leader收集他们的门限签名，主节点篡改的消息就无效了（因为门限签名的性质）。
  • 不发消息——宕机

传统解决方案

最原始的方案：

  • 设定超时时间，如果超过某个时间还没有对某个高度的提案达成共识，就认为 leader 为错误节点，触发视图切换。
  • leader发送了错误的消息，触发视图切换。

因此：主要消耗性能的地方在于触发视图切换，触发视图切换意味着要重新传送一遍消息

1. leader的选择问题

为了保证 HotStuff 协议中的 Leader 的有效性，以防止其成为恶意节点，可以采取以下几种措施：

  1. 随机选择：HotStuff 中的 Leader 应该通过随机选择而不是固定的方式确定。这样可以防止攻击者预测 Leader 的身份并构造攻击。【不好：因为随机的过于随机了】
  2. 轮流成为 Leader：在每个轮次（round）开始之前，可以按照事先约定的顺序轮流选择 Leader，确保每个参与节点都有机会成为 Leader。这样可以实现公平性，减少某个节点长期担任 Leader 的可能性。【不好：因为轮流仍然可以被预测】
  3. 多签名验证：Leader 生成的提议需要经过多个节点的验证才能被接受。例如，至少需要其他两个节点对 Leader 提议进行签名验证，以确保 Leader 没有恶意行为。【不好：因为随机的过于随机了】
  4. 选举机制：如果发现当前的 Leader 具有恶意行为，可以通过选举机制重新选择 Leader。这可以由其他节点共同参与，基于一定的规则和算法重新选出新的 Leader。

2. 什么时候停止计票（达成共识）

由于有 f 个恶意结点可能不投票，所以收集到 2f+1 个投票（含提案）就该停止，否则系统将失去活性。

通过选择 2f+1 个节点来达成共识，我们可以确保至少有 f+1 个诚实节点参与其中，从而保证了系统的安全性和正确性。

3. 加锁

正确节点只会对某个高度投一票，即当高度 H 已经给区块 A 投过票时，不会再对该高度的其他区块投票，我们称这个行为为“加锁”，并且说节点对于高度 H “锁定”在了区块 A。

保证了每个结点只对同一高度的同一区块投票

4. 为什么Leader无法篡改信息

因为在prepare阶段，主节点向其他结点发送待加入的区块，这个区块内其实是有签名的，各个节点可以验证签名来验证这个区块的有效性。如果有效，那么缓存。这里保证了其他结点拿到的信息都是正确的。
验证后进入commit阶段，此后leader的信息篡改就没用了——
此处引入一个概念——门限签名，即每个结点手握着一个钥匙的一部分，只有凑齐其中的2f+1片，才能合成最终的钥匙，最终的钥匙只需要简单的验证即可知道消息对不对，也就是说如果没有收集到2f+1 个节点的共识钥匙，其他结点是不会将区块上链的。
即恶意结点最坏情况下只能破坏共识，这将导致更换leader；而不是将篡改的信息上链。

改进灵感

1. 增加Leader

参考资料