tendermint 拜占庭共识算法
状态机概述
在每一个区块高度上, 基于多轮协议来决定下一个区块。每一轮有三个步骤(提案(Propose), 预投票(Provote), 预提交(Precommit)), 以及两个特殊的步骤Commit和NewHeight 所以在tendermint的区块打包始终是按着下面的顺序进行的:
NewHeight->(Propose -> Prevote -> Precommit)[一次区块确认可能需要多轮] -> Commit ->NewHeight
(Propose -> Prevote -> Precommit)被称为一轮。 所以说在tendermint中如果想要确认一个新的区块， 必须经历至少一轮这样的顺序。 一些情况下可能需要多轮才能决定出一个区块:
- 指定的提议者(指轮到其进行提案的验证者)不在线
- 被提议者提议的区块时无效的
- 被提议者提议的区块没有按时广播
- 提议的区块时有效的， 但是没有在规定时间内收到大于2/3个节点进行的预投票。
- 提议的区块时有效的， 但是没有在规定时间内收到大于2/3个节点进行的预提交。
PoLC
超过2/3的预投票为一个提议的区块或者nill, 将会进行锁定， proof-of-lock-change 。 也就是说当一个验证者在正常提议正常投票之后， 当它收到了超过2/3的投票他就会进入PoLC的锁定。
框图
(Wait til `CommmitTime+timeoutCommit`)
+-------------------------------------+
v |
+-----------+ +-----+-----+
+----------> | Propose +--------------+ | NewHeight |
| +-----------+ | +-----------+
| | ^
|(Else, after timeoutPrecommit) v |
+-----+-----+ +-----------+ |
| Precommit | <------------------------+ Prevote | |
+-----+-----+ +-----------+ |
|(When +2/3 Precommits for block found) |
v |
+--------------------------------------------------------------------+
| Commit |
| |
| * Set CommitTime = now; |
| * Wait for block, then stage/save/commit block; |
+--------------------------------------------------------------------+
背景知识
验证节点
tendermint中并不是所有节点都是验证节点(如果均是验证节点也不可能达到那么高的TPS), 只有那些参与上述区块打包过程的节点才会成为验证节点。 但是这并不表示其他节点没有作用。 其他非验证节点可以对相关的区块数据， 提议， 投票进行广播。 保证了网络的健壮性。
共识广播的策略
节点会广播一个提议者在当前轮提交的区块。 但是它只会广播区块数据的Parset部分(tendermint的区块数据结构在之前文档有提到过) 节点会广播预投票和预提交阶段的投票。 如果一个节点处于PoLC(proof-of-lock-change: 指当前验证者已经锁定了自己的改变, 表示在下一轮投票时， 它依然会坚持目前的投票)阶段。 他会在预投票阶段继续投票之前锁定的提议的区块。 节点会向那些之后的节点广播已经提交的区块 节点会找机会广播HasVote指令用于获取对方已经拥有的投票 节点会广播当前它的状态。
何为tendermint提案
提案是有特定的提议者在每一轮进行的将要打包的提议, 对其进行签名和广播。 提案者是确定性的。 一个在(H,R)(H高度R轮)的提案是由一个区块和可选的PoLC组成。 如果有PoLC说明之前此提案已经有超过2/3的节点进行了投票通过。
状态机步骤说明
通用的退出情况
- 超过2/3节点预提交投票在(H, R) 跳到Commit(H, R) --- 表示在本轮已经收到了2/3的节点预投票 那么直接可以进行Commit了
- 超过2/3节点进行了预投票在(H, R+X) 跳到Prevote(H, R+x) --- 表示有更新的轮进入到了预投票阶段了
- 超过2/3的预提交投票在(H, R+X) 跳到PreCommit(H, R+x) -- 表示更新的一轮已经进入到预提交阶段
Propose Step(H, R)
提议者提出一个区块。 根据下面几种情况进入下个步骤:
- 提案超时 直接跳到PreVote(H, R)
- 已经接收到提议的区块， 并且此提案已经锁定(PoLC) 跳到PreVote(H, R)
- 通用的退出情况
Prevote Step (H, R)
每一个验证者进入PreVote阶段时, 会广播自己的预投票。 如果验证者目前处于锁定阶段， 而且现在有一个新的锁定出现， 并且新的锁定比之前的锁定轮数大并且小于当前轮， 那么此验证者解锁 如果验证者处于锁定， 但是不满足上面的情况， 则会直接投票当前锁定的区块 如果验证者不处于锁定阶段，并且当前提案的区块是有效的 则投票给此处收到的提议区块。 如果验证者不处于锁定阶段，并且当前提案的区块是有效的 则投票给nill。
预投票阶段根据下面几种情况进入下一个步骤:
- 超过2/3的预投票为此提案区块或者nill 则进入PreCommit(H,R)阶段
- 预投票超时 进入PreCommit(H,R)阶段 ---也就是说在规定时间没有收到超过2/3的预投票
- 通用退出情况
Precommit Step (height:H,round:R)
在PreCommit阶段， 验证者广播预提交的选票: if 验证者在此轮锁定了区块, 那么它就会进行预提交投票此区块。并且设置LastLockRound=R else if 验证者在此轮锁定了nill, 那么它会解锁并且预提交投票给nill else 保持之前锁定不变, 投票nill
根据情况进入下一个步骤:
- 超过2/3的节点预提交为nill 进入ProPose(H, R+1)
- 规定时间没有收到足够多的预提交 进入ProPose(H, R+1)
- 通用退出情况
Commit Step (height:H)
设置CommitTime = now() 等待这个区块内容接收到， 进入NewHeight(H+1)