Istanbul BFT解读(上)
Istanbul BFT作为BFT类算法的一种已经有过在以太坊上的实践。
## Istanbul BFT共识算法详细文档 [Istanbul BFT](https://github.com/ethereum/EIPs/issues/650)作为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`信息。 ## 状态转换 ![Istanbul_rc.jpg](https://img.learnblockchain.cn/attachments/2020/05/gxPIBlCH5ec4ca0006b12.jpg) * 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](https://github.com/jpmorganchase/quorum/issues/305) * [这篇文章详细分析了IBFT](https://arxiv.org/pdf/1901.07160.pdf) * 没有激励机制
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信息。
- Validator收到
- PREPARED -> COMMITTED:
- Validator收到
2F + 1
个·有效的COMMIT
信息,以此进入COMMITTED
状态。有效的信息需要满足以下条件:- sequence和round匹配。
- block hash匹配
- 信息是来自已知的validators。
- Validator收到
- COMMITTED -> FINAL COMMITTED:
- Validator把
2F + 1
个commitment签名放进区块头的extraData
并且尝试插入区块进区块链。 - 当插入区块成功,Validator进入
FINAL COMMITTED
状态。
- Validator把
- FINAL COMMITTED -> NEW ROUND: Validators选一个新的proposer开始新的一轮。
潜在问题
- Fail-Stop failures
- 这篇文章详细分析了IBFT
- 没有激励机制
区块链技术网。
- 发表于 2020-05-19 17:08
- 阅读 ( 1952 )
- 学分 ( 88 )
- 分类:共识
评论