深入理解比特币系列(11): 共识机制

去中心化一文中我们提到——比特币系统交易信息的确认是基于共识机制的。共识机制并非比特币系统独创,事实上,分布式网络中共识机制的研究已经在计算机科学领域持续了几十年。本文我们将更细致的了解什么是共识机制?比特币系统采用的共识机制是什么?数字货币/区块链领域还有哪些其它常见的共识机制?

什么是共识机制?

Wikipedia上对共识机制(也有叫协议、算法的)问题的描述是需要满足如下的条件:

Termination
Every correct process decides some value.
Validity
If all processes propose the same value , then all correct processes decide .
Integrity
Every correct process decides at most one value, and if it decides some value , then  must have been proposed by some process.
Agreement
Every correct process must agree on the same value.

简言之:所有正确的节点最终对某一value达成共识;这一value值是由正确的节点产出的。

这里面提到一个“correct process”,也就是说还有“incorrect process”。一个支持共识机制的系统需要具备一定的容错能力。

共识机制的容错场景

容错场景包含两种情况。

一种情况是假如系统中有一部分节点出现故障、网络不通等问题,整个系统依然可以正常工作。

第二种情况是假如系统中有一部分节点会“作恶”,只要“好的”节点数量在网络中占大多数,系统依然可以正常运行。

比特币系统采用PoW(Proof of Work)共识机制

比特币系统之前的共识机制是纯靠计算机科学的算法来解决问题的。而比特币系统所采用的共识机制是计算机科学算法与利益驱动的绝妙结合。它通过利益的驱动来解决一些计算机传统算法中难以实现的问题。

比特币系统共识算法的逻辑可以理解为其交易确认的过程:

1)新的交易向全网进行广播;
2)每一个节点都将收到的交易信息纳入一个区块中;
3)每个节点都尝试在自己的区块中找到一个具有足够难度的工作量证明;
4)当一个节点找到了一个工作量证明,它就向全网进行广播;
5)当且仅当包含在该区块中的所有交易都是有效的且之前未存在过的,其他节点才认同该区块的有效性;
6)其他节点表示他们接受该区块,而表示接受的方法,则是工作在以该区块为末尾的链条上,通过引用该区块的哈希值来制造新的区块。

这其中第3步的工作量证明即是PoW。其原理是通过不断的计算给定输入的哈希值来找到一个随机数nonce,使得计算的哈希值小于系统设定的一个难度目标。

由于PoW计算哈希值不可逆,只能通过枚举的方式,所以保证了在一定的时间内,Pa系统中只可能出现极少数的合法value(区块)。这些区块会在网络中进行广播,收到的用户节点验证后会基于它认为的最长链继续PoW的计算。因此,系统中可能出现分叉,但最终会有一条链成为最长的链。

对恶意破坏系统的行为,比特币从利益驱动的角度来解决。参与PoW计算的节点,亦即挖矿,需要付出不小的经济成本(硬件、电力、维护等)。因此,从经济博弈的角度,节点最终会回归到最长链上来继续PoW的工作。

其它常见共识机制

除了比特币系统采用的PoW外,还有PoS、DPoS、PBFT、Paxos、Raft等共识算法,这里简要介绍一下,以后有时间我再深入讲解。

PoS(Proof of Stake):权益证明。PoW是基于节点算力的,而PoS是基于节点“财富”的,即某一节点拥有记账权的概率为其所拥有的“财富”占整个系统“财富”的百分比。采用这一算法的如Peercoin、Nxt。以太坊也在计划采用PoS协议来替代现在的PoW机制。

DPoS(Delegated Proof of Stake):代理权益证明。不同于PoS的所有节点都可参与,DPoS是由节点们选出一定数量的节点来代表整个网络的决定。这有点像现实中股东投票选举董事会,董事会代表股东的权益来做决定。采用这一算法的如Bitshares、Lisk。

PBFT(Practical Byzantine Fault Tolerance):分布式计算系统中的一个经典问题就是拜占庭将军问题,其描述如下:

拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。

PBFT算法解决了拜占庭将军问题,其对故障节点数量有一定的要求,即故障节点数在小于总体节点数1/3的情况下,系统可以达成一致。IBM所主导的Hyperledger Fabric项目采用的就是PBFT算法。

Paxos:该算法是由Lesilie Lamport以古希腊Paxon岛上的一个故事提出的。

希腊岛屿Paxon岛上的多个立法者在议会大厅中对议案进行表决,他们之间通过服务人员传递纸条的方式来交流信息,每个立法者都会将通过的议案记录在自己的账单(ledger)上。立法者可能因各种事情随时离开或进入大厅,服务人员可能偷懒去睡觉。使用何种方式能够使得这个表决过程正常进行,且通过的议案不发生矛盾。

上述故事中,可以做这样的类比:议会大厅是分布式系统;立法者是进程或者节点;议案是value;立法者的离开意味着网络节点出现故障;服务人员睡觉意味着网络不通。Paxos算法采用了一种基于消息传递的模型解决了节点通信(立法者交流)的问题。Paxos算法要求系统中有超过50%的节点正常工作便可以达成共识。

Raft:该算法是另一种实现Paxon问题的一致性共识算法。相比较Paxos更容易理解,在开源项目中,已经有了Java、C++、Scala的实现版本。