Istanbul BFT解读(上)

Istanbul BFT共识算法详细文档

Istanbul BFT 作为BFT类算法的一种已经有过在以太坊上的实践。虽然Istanbul目前还存在一些，但其算法思想和实现还是值得学习和借鉴的。

源代码： https://github.com/jpmorganchase/quorum/tree/master/consensus/istanbul

术语

• Validator: 区块验证者。
• Proposer: 出块者。
• Round: 共识的轮数。一轮从出块者提出一个区块proposal开始，结束于区块提交或者轮数改变（轮数改变可能由于出错或者区块更新）。
• Proposal: 提出的一个在处理中的新的区块。
• Sequence: proposal的高度。块高和sequence相对应。
• Blocklog: 将来的信息记录在backlog里面。 core.backlogs
• Round state: Round 和 Sequence 绑定在一起组成 view ，
• Consensus proof: 提交的区块签名。每个 validator 对区块验证后会对其进行签名。
• Snapshot: validator的投票状态。

共识算法描述

Istanbul BFT修改自PBFT算法，包括三个阶段： PRE-PREPARE 、 PREPARE 以及 COMMIT 。在 N 个节点的网络中，这个算法可以最多容忍 F 个出错节点，其中 N=3F+1 。在每一轮开始前， validator 会选择其中一个作为 proposer ，默认以轮询的方式（除此之外还有sticky的方式，搜索 stickyProposer 方法去看细节）。然后proposer会提出一个区块的proposal，并且广播 PRE-PREPARE 信息。一旦一个validator收到 PRE-PREPARE 信息，会把状态标记为 PRE-PREPARED ，然后广播 PREPARE 信息。这一步是为了确保所有的validator在同一个seqnence和round（代码中为view）上进行共识验证。一旦收到 2F+ 1 个 PREPARE 信息，validator进入 PREPARED 状态然后广播 COMMIT 信息。这一步是为了通知节点的peer已经接收到了提出的区块，并且即将插入区块到链中。最后，validator等待 2F + 1 个 COMMIT 信息，然后进入 COMMITTED 状态然后插入区块到链中。 Istanbul BFT算法中的区块是确定的，意味着链没有分叉并且合法的区块一定是在链中。为了防止一个恶意节点生成不同的链，在把区块插入进链 之前 ，每一个validator必须把 2F + 1 个 COMMIT 签名放进区块头的 extraData 字段。因此，区块时可以自我验证的（因为有签名）并且轻客户端也支持。然而动态的 extraData 也会造成区块的hash计算问题。因为一个区块可以被不同的validator验证，所以会有不同的签名，所以同一个区块会有不同的hash。解决的方案是，计算区块hash的时候把 COMMIT 签名排除在外。因此我们任然可以在保证block hash一致性的同时进行共识验证。

共识状态

• New Round : 一个proposer发送新的区块proposal。validator等待 PRE-PREPARE 信息。
• PRE-PREPARED : 一个validator已经收到 PRE-PREPARE 信息，并且广播 PREPARE 信息。然后等待 2F + 1 个 PREPARE 或者 COMMIT 信息。
• PREPARED : 一个validator已经收到 2F + 1 个 PREPARE 信息，此时把自身状态标记为 PREPARED ，并且广播 COMMIT 信息。然后等待 2F + 1 个 COMMIT 信息
• COMMITTED : 一个validator已经收到 2F + 1 个 COMMIT 信息，此时把自身状态标记为 COMMITTED ，并且开始把提出的block插入链中。
• FINAL COMMITTED : 一个validator已经成功把区块成功插入了链中，此时把自身状态标记为 FINAL COMMITTED ，并且等待下一轮。
• ROUND CHANGE : 一个validator等待关于同一个round下的 2F + 1 个 ROUND CHANGE 信息。

状态转换

• NEW ROUND -> PRE-PREPARED:
  • Proposer在txpool中收集交易。
  • Proposer提出一个区块proposal并且广播给validator。然后进入 PRE-PREPARED 状态。
  • 每一个validator进入到 PRE-PREPARED 状态，一旦收到 PRE-PREPARED 信息并且伴随着以下情况:
    • 区块proposal是来自于有效的proposer。
    • 区块头有效。
    • 区块proposal的sequence和round和validator的状态匹配。
  • Validator广播 PREPARE 信息给其他validators。
• PRE-PREPARED -> PREPARED:
  • Validator收到 2F + 1 个有效的 PREPARE 信息，因此而进入 PREPARED 状态。有效信息需要满足以下条件：
    • sequence和round匹配。
    • 交易hash匹配。
    • 信息是来自已知的validators。
  • 一旦进入 PREPARED 状态，Validator广播COMMIT信息。
• PREPARED -> COMMITTED:
  • Validator收到 2F + 1 个·有效的 COMMIT 信息，以此进入 COMMITTED 状态。有效的信息需要满足以下条件：
    • sequence和round匹配。
    • block hash匹配
    • 信息是来自已知的validators。
• COMMITTED -> FINAL COMMITTED:
  • Validator把 2F + 1 个commitment签名放进区块头的 extraData 并且尝试插入区块进区块链。
  • 当插入区块成功，Validator进入 FINAL COMMITTED 状态。
• FINAL COMMITTED -> NEW ROUND: Validators选一个新的proposer开始新的一轮。

潜在问题

• Fail-Stop failures
• 这篇文章详细分析了IBFT
• 没有激励机制