TT共识系列之PaLa

下文是对TT链白皮书中PaLa协议描述的改编，在白皮书基础上进行了扩展，并增添了许多细节、图表和解释。

PaLa是一种基于部分同步网络假设的区块链共识协议，对作恶行为的容忍度可达到1/3。下面，我们将描述一个名为基础版Pala（Basic Pala）的协议简化版本，来说明PaLa的简单性和有效性。基础版Pala是理解完整版协议的基础，稍后我们会对完整版进行概述。PaLa协议的全部细节目前可以从PaLa研究论文中获取。

设置

假设有一个固定的选民委员会，稍后会描述如何选择节点，每个节点维护一个局部历元计数器e和区块链的一个局部视图。每个区块包含一个历元号、一张交易列表以及其父块的哈希。链的历元数定义为链中最后一个区块的历元数。每个历元都有唯一的一个提案者，这个提案者对网络中所有节点来说都是已知的。在该简化版本中，每一位选民同时也是某些历元的提案者。

共识一次只能处理一个区块。若有资格，提案者会在当前历元提出一个区块。如果满足了一组条件，选民就可以在区块上投票。2/3的委员会对某一区块的投票的集合构成对该区块的公证。若某一区块有公证，则意味着该区块被证实。每个区块都有一个对应的历元，历元数单调递增。如果某历元e区块有一个历元e-1父块，那么这个区块就定义为一个普通块，否则为一个超时块。如果一个区块是经过公证的普通块的父块，则该区块已得到最终确认。已确认的区块成为区块链不可更改的历史记录的一部分，且表明在该块上的共识已经达成。

协议

每个节点始终对其本地当前区块链进行更新。每当各节点看到一个比当前链更新的、即历元数大于当前链的、且有效的区块链时，它们会切换到这个新链。一个有效的区块链应该满足以下条件：

1. 各区块的历元数应严格递增

2. 区块链中的每个区块都经过了公证

此外，每个节点将执行以下操作：

满足下列条件时，将本地历元计数器增加至e：

●?各节点当前的本地历元数比e小，且

●?（各节点已经看到历元e-1存在一条被公证的链，或者

●?各节点看到至少2/3的委员会成员已有效签署clock(e)时钟消息）

若各节点在历元e-1停留超过一段固定时长，则

●?广播clock(e)时钟消息。

若各节点为历元e的提案者

●?如果他们当前的链以历元e-1的区块结束，则即刻为历元e提出一个新的区块来扩展他们当前已被公证的链

●?如果他们当前区块链的历元号是e（因超时而导致的结果），则等待一段固定的时长（希望接收到一个更新的已被公证的链），并为历元 e提出一个新的区块来扩展他们自己当前的链。

●?请注意，如果经过公证的区块在固定的延迟之后到达，则它可能成为孤立的块。

在收到来自历元e提案者对于历元 e的区块提案时，在提案上签名，如果下列条件成立，则多播签名：

●?各节点已经看到对提案的父块的公证。

●?在历元e开始的时候，这个区块至少和各节点的当前链一样新。

●?各节点尚未对历元e签署任何其他区块。

●?如果某区块是一个经过公证的区块的父块，那么节点会报告其为一个已被最终确认的区块。

通过这些简单的规则，PaLa共识协议实现了活跃性和一致性。PaLa协议虽简单，但已经过严格证明。PaLa是基于部分同步网络假设设计的。它天生具有分区容忍性且响应迅速。当遇到网络分区时，只会出现短暂的活跃性中断。一旦分区被融合，在状态上没有冲突时，便会恢复进度。

委员会重置

在现实世界的权益证明区块链中，随着权益在系统中易手，我们希望能定期地更换委员会成员。PaLa共识算法支持快速、无缝的委员会切换。基本的思路是，上一个委员会必须在下一个委员会上任之前确认一个特定的重置区块，以确保一致连续性。

以下是对PaLa共识协议的更深入的解读。

到目前为止，我们描述的PaLa只能在固定委员会下保证区块链历史的一致性。有可能就在临重置前，前一个委员会完成对重置区块扩展的最终确认。请记住，连续出现2个公证过的区块，这两个区块中的第一个区块即被最终确认。因此，当满足两个公证过的普通块这一条件时，超时设定允许一次性对连续的多个区块进行公证和确认。如果从重置区块中扩展出下一轮，那么从重置区块延伸出的、确认过的链会丢失。这样一来，我们会失去一致性。我们无法保证新委员会能看到这个延伸出的、经过确认的链，而且我们无法要求新委员会必须从重置区块中延伸出下一轮。

TT链的做法始终是从重置区块进行扩展，并且要求重置区块之后的所有区块必须为空。这样做是因为扩展部分只是为了确认重置区块，内容无关紧要。

另一个解决方案是让重置区块后的区块被下一个委员会确认。

?

?

双流水式PaLa

PaLa研究论文中所述的完整版PaLa协议被称为双流水式PaLa，支持流水线式提案功能。该版本允许共识每次处理k个区块，k是一个协议设置参数。流水式提案允许在对旧块仍在进行投票时缓冲新块。基于经验测试，我们发现当网络延迟高于区块时间时，较高的k值可以提高吞吐量。

由于单个提案者可以按顺序提案多个区块，因此需要更细致的区块编号方案。目前的区块都有一个历元和序列号。和以前一样，提案者是根据历元来选择的，且来自同一序列的每个新提案都会在每个历元伊始从0开始递增序列号。如果某区块在同一历元的第k个子块通过公证，则该区块被最终确认。

协议的其余部分与PaLa非常相似。一致性和活性的证明也如出一辙。我们将在未来的博文中比较PaLa和Hotstuff，深入探讨相关细节。

性能

从性能的角度来看，PaLa是对之前的经典共识协议的重大改进，经典协议要求每个区块进行两轮投票和O(n?)消息复杂度。PaLa利用了流水式BFT的思想，第二轮投票附带在下一个区块的第一轮投票上。活跃的提案者使用BLS多重签名来收集选票和分发公证。结合多中心辐射型网络拓扑结构，PaLa可以实现仅用O(n)消息复杂度即达成共识。

总结

在新兴加密范式下，长达数十年的分布式共识研究才铸就出PaLa这一巅峰之作。PaLa将许多协议中的想法大胆而又巧妙地结合在一起，形成一个简练而又有效的协议。从上面对算法的简短描述中可以明显看出这一点。PaLa研究论文基于现实的网络假设，为其安全性能提供了简练而严谨的证据。

较新的BFT共识算法，如Tendermint、FBFT、Casper FFG、Hotstuff等，使用了许多与PaLa相同的创新。然而，这些算法都不如PaLa简练、巧妙和优化。

我们期待有朝一日人们一谈起BFT共识就能想到PaLa，就像大家现在一提起分布式哈希表（DHT）就会想到Kademlia那样。

PaLa共识协议的参考实现（https://github.com/thundercore/pala）已经发布，并有详尽的文档，敬请查阅。

—-

编译者/作者：币懂区块链

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。