POS、PBFT共识算法的介绍

王茂南

2827
文章

75
评论

2018年9月7日17:22:022 2077字阅读6分55秒

摘要关于两个共识算法的一些介绍；也是最近有接触到，就查了一些资料，这一篇文章就对我看的进行一下总结（网上能查到的资料太多了，需要进行一个总结归纳）。

文章目录(Table of Contents)

PBFT（实用拜占庭容错算法）

基于拜占庭将军问题，PBFT算法一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

我们首先解释一下上面各个符号表达的意思：

C表示客户端；
0，1，2，3表示4个节点；
0在这里为主节点，1，2，3为从节点；（注意，这里其他节点也可以作为主节点，若0发生错误只能由服务器监测。如果服务器在一段时间内不能完成客户端的请求，则会触发视图更换协议，将其他节点换为主节点）
3为故障节点；

下面我们结合上图，详细说一下PBFT的步骤：

Request：请求端C发送请求到主节点，这里是0节点；
Pre-Prepare：节点0收到C的请求后进行广播，扩散至123；
Prepare：123节点收到后记录并再次广播，1->023，2->013，3因为宕机无法广播；（这一步是为了防止主节点给不同从节点发送不同的请求）
Commit：0123节点在Prepare阶段，若收到超过一定数量（2F，实际使用中，F为可以容忍的拜占庭节点个数）的相同请求，则进入Commit阶段，广播Commit请求；
Reply：0123节点在Commit阶段，若其中有一个收到超过一定数量（2F+1）的相同请求，则对C进行反馈；

根据上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N为总计算机数，F为有问题的计算机总数。

一个例子

下面我们来举一个PBFT（实用拜占庭容错算法）的例子来进行说明。

我们假设N=4，F=1，即有四个节点，其中有一个节点是坏的，我们还使用上面的图，即节点3为故障节点。

请求端C发送请求到0节点，假设这里请求内容为“1”；
节点0收到C的请求后进行广播，将请求内容“1”扩散至节点123；
节点1、2、3收到后内容“1”后，再次广播，节点1->023，节点2->013，节点3因为宕机无法广播；
节点0，1，2会在上一阶段分别收到三个请求内容“1”，均超过了2个，于是节点0、1、2会分别广播请求内容“1”；
此时如果一个节点（0，1，2中任意一个）收到3即（2+1）条commit消息，即对C进行反馈。

一个问题说明 — 为什么至少需要N=3F+1个节点

我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里讨论一下原因。

我们可以考虑：由于有F个节点为故障或被攻击的节点，故我们只能从N-F个节点中进行判断。但是由于异步传输，故当收到N-F个消息后，并不能确定后面是否有新的消息。（有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们考虑最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量N-2F大于被攻击节点的数量F，于是有N-2F>F，即N>3F，所以N的最小整数为N=3F+1。

PoS（股权证明）

PoS算法类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。
简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度。在股权证明PoS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个PoS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

然而，一旦币的权益被用于签名一个区块，则币龄将清为零，这样必须等待至少30日才能签署另一区块。同时，为防止非常老或非常大的权益控制区块链，寻找下一区块的最大概率在90天后达到最大值，这一过程保护了网络，并随着时间逐渐生成新的币而无需消耗大量的计算能力。

权益证明必须采用某种方法定义任意区块链中的下一合法区块，依据账户结余来选择将导致中心化，例如单个首富成员可能会拥有长久的优势。为此，人们还设计了其他不同的方法来选择下一合法区块。

PoS机制虽然考虑到了PoW的不足，但依据权益结余来选择，会导致首富账户的权力更大，有可能支配记账权。股份授权证明机制（Delegated Proof of Stake，DPoS）的出现正是基于解决PoW机制和PoS机制的这类不足。