本文档补充介绍Tendermint 共识协议中validator选取规则以及算法的相关证明。关于Tendermint共识协议的详细解析，请看https://my.oschina.net/u/3620978/blog/3233106

1. validator选取

与其他的一些PoS共识算法不同的是，Tendermint中，各validator节点都需要联网，并且validator集合由外部的特定程序进行指定和管理。

对Tendermint共识来说，PoS不是必需的，但可以基于它实现PoS共识，也就是说，此时节点需要在链上或链下支付保证金，或者也可能不需要支付任何保证金。

每个validator节点拥有一对密钥对，以及相应数量的投票权，而且投票权不需要都相同。

选取validator节点有两种方式：

可以在创世状态（genesis state）对应的创世配置文件genesis.json中进行预先设置；

每次 commit 新区块后，Application logic通过ABCI（Application Blockchain Interface）接口发送的针对EndBlock消息的回复中，会包含有validator集合的更新。

2. 算法相关证明

本部分介绍算法的Safety，Liveness和Fork Accountability的证明。

2.1. Safety证明

Safety指的是，假设系统中拜占庭的validator投票权占比为 -1/3（小于1/3），就可以保证链不会产生分叉，也就是同一高度不会commit两个不同的区块。证明如下：

假设一个validator在round R中commit了一个区块B，这就意味着该节点接收到了+2/3（大于2/3） 的precommit投票。由于拜占庭节点投票数最多为-1/3，因此有1/3+（大于1/3）的诚实节点在round R中仍然lock在区块B上。

这些诚实节点要解除lock状态的话，需要接收到来自round R'>R的PoLC，即需要有+2/3的针对另一个区块B'的prevote投票。但这是不可能的，因为按照算法规则，这些占比为1/3+的诚实节点只会prevote区块B，从而导致针对区块B'的prevote投票无法达到+2/3。这就说明，除了commit的区块B之外，同一高度上不会再commit其它区块，保证了safety。

2.2. Liveness证明

如果有1/3+的诚实节点在不同的round中lock在不同的区块上，由于最终会有proposer将更靠后的round上对应的PoLC广播出来，这样就会导致在更靠前的round上lock的节点被unlock。这就能保证足够多的节点可以进行后续的共识投票，从而保证系统的Liveness。

此外，各节点等待接收完整的proposal即block以及可能的PoLC信息的超时时间timeoutProposalR可以随着round的推进而增加，这样在proposal的大小相对比较固定的情况下，整个网络可以保证proposal被各节点接收到。

综合以上两点，系统可以保持Liveness。

2.3. 分叉问责证明

分叉问责（Fork Accountability）需要收集相应的投票信息，以便在分叉时，能够判断是那些节点进行了双重签名，即同一个节点在同一高度，对两个不同的区块进行签名。

对于一个validator v1来说，所有对应高度为H，由它签名的precommit投票，加上与这些投票对应的、证明合法性所有PoLC（即所有对应lock change的prevote投票）组成的集合，记为JSet（justification-vote-set）。

比如，如果v1对以下precommit投票签过名：
Precommit(B1 @ round 0)
Precommit(nil @ round 1)
Precommit(B2 @ round 4)

则 Precommit(B1 @ round 0)投票需要round 0 有一个PoLC来证明，同时Precommit(B2 @ round 4)投票需要round 4 有一个PoLC来证明。Precommit(nil @ round 1)根据算法规则，不需要有对应的PoLC，同理，这里没有round 2和3的precommit 投票信息，也不需要对应的prevote投票信息。因此JSet只需包含round 0和4的PoLC投票。

进一步地，对于一个区块链高度H，以及validator集合VSet，可以定义JSet为所有VSet中的validator对应的JSet的并集。对于所有在round R commit过区块B的诚实的validator来说，可以构建一个JSet来证明这个commit。

在指定高度H，和round R,如果有一个commit，并且所有commit区块的validator（committer）对应的JSet能够为每一个validator提供证明，则称JSet能够证明该commit。

现在我们来证明，如果检测到分叉，即同一高度上存在两个不同的commit，则这两个commit对应的JSet的并集中，存在1/3+的validator有双重签名。

证明：
假设commit的两个区块分别为B和B'，则它们分别对应着两个precommit投票集合P和P'。P和P'中都包含+2/3的precommit投票。

P中每一个precommit投票对应一个validator,记所有validator的集合为V。同理，P'对应validator集合为V'。则V和V'的交集即为进行过双重签名的节点集合。假设其节点数量占比为-1/3，则V中去掉这部分节点占比为+1/3，加上V'的节点，则占比超过 1/3 + 2/3 = 1，这是不可能的，说明假设不成立，也就是有1/3+的节点有双重签名。

这同时也说明，当检测到分叉时，就说明拜占庭节点占比为1/3+，不符合为保证Safety所需的条件。

此时，可以通过外部介入的方式，来判定相应的责任。根据前面的推理，最后可以找到至少1/3或更多的节点，对于其中每个节点来说，要么其至少一个投票无法证明合法性，要么其有双重签名。

3. References

[1] https://tendermint.readthedocs.io/en/master/

重点章节：

Tendermint 201/Specification/Byzantine Consensus Algorithm，Genesis， Validators