区块链系统采用去中心化的设计,网络节点分散且相互独立,所以由不同节点组成的系统之间必须依赖一个制度来维护系统的数据一致性,并奖励提供区块链服务的节点,以及惩罚恶意节点。
这个制度的建立需要依赖一套方法和规则,即由谁取得一个区块的打包权(或称记账权),并获取该区块的奖励或者怎样界定谁是作恶者,让他受到怎样的惩罚,这套方法和规则便是共识机制。
现在有多种共识算法在区块链中使用,较为常用的有:工作量证明(Proof of Work,PoW)算法、权益证明(Proof of Stake,PoS)算法、股份授权证明(Delegated Proof of Stake,DPoS)算法、实用拜占庭容错(Practical Byzantine Fault Tolerance,PBFT)算法。
PoW算法是一种防止分布式服务资源被滥用、拒绝服务攻击的机制。
PoW算法要求节点进行适量消耗时间和资源的复杂运算,并且其运算结果能被其他节点快速验算,以耗用时间、能源做担保,以确保服务与资源被真正的需求所使用。比特币首次利用PoW算法来验证交易并向网络广播区块,现在很多区块链也采用PoW算法。PoW算法已经成为广泛使用的共识算法。
矿工进行哈希运算,此过程消耗算力,算出“正确的结果”,并向全网广播,其他矿工或者普通节点同步区块并校验是否正确。
节点“挖矿”的过程
PoW算法中最基本的技术原理是使用哈希算法。假设求哈希值Hash(r),若原始数据为r(raw),则运算结果为R(Result)。
R = Hash(r)
哈希函数Hash()的特性是,对于任意输入值r,得出结果R,并且无法从R反推回r。当输入的原始数据r变动1比特时,其结果R值完全改变。在比特币的PoW算法中,引入算法难度d和随机值n,得到以下公式:
Rd = Hash(r+n)
该公式要求在填入随机值n的情况下,计算结果Rd的前d字节必须为0。由于哈希函数结果的未知性,每个矿工都要做大量运算之后,才能得出正确结果,而算出结果广播给全网之后,其他节点只需要进行一次哈希运算即可校验。PoW算法就是采用这种方式让计算消耗资源,而校验仅需一次。
PoS算法要求节点验证者必须质押一定的资金才有挖矿打包资格,并且区域链系统在选定打包节点时使用随机的方式,当节点质押的资金越多时,其被选定打包区块的概率越大。
例如,某个节点拥有整个区块链系统5%的股份,则这个节点在下一个出块周期里,将有5%的概率打包出块。
节点通过PoS算法出块的过程
节点通过PoS算法出块的过程如下:普通的节点要成为出块节点,首先要进行资产的质押,当轮到自己出块时,打包区块,然后向全网广播,其他验证节点将会校验区块的合法性。
DPoS算法和PoS算法相似,也采用股份和权益质押。
但不同的是,DPoS算法采用委托质押的方式,类似于用全民选举代表的方式选出N个超级节点记账出块。
选民把自己的选票投给某个节点,如果某个节点当选记账节点,那么该记账节点往往在获取出块奖励后,可以采用任意方式来回报自己的选民。
这N个记账节点将轮流出块,并且节点之间相互监督,如果其作恶,那么会被扣除质押金。
PBFT算法解决了拜占庭将军问题。
拜占庭是古代东罗马帝国的首都,为了防御在每块封地都驻扎一支由单个将军带领的军队,将军之间只能靠信差传递消息。在战争时,所有将军必须达成共识,决定是否共同开战。
但是,在军队内可能有叛徒,这些人将影响将军们达成共识。拜占庭将军问题是指在已知有将军是叛徒的情况下,剩余的将军如何达成一致决策的问题。
1982年,莱利斯·兰波特(Leslie Lamport)等在论文The Byzantine Generals Problem中证明当将军总数大于3f,背叛者数为f或者更少时,忠诚的将军可以达成命令上的一致,即 3f+1≤n,算法复杂度为O(nf +1)。
米格尔·卡斯特罗(Miguel Castro)和芭芭拉·利斯科夫(Barbara Liskov)在1999年发表论文Practical Byzantine Fault Tolerance提出PBFT算法。该算法的容错数量也满足3f+1≤n,算法复杂度为O(n2)。
该算法能提供高性能的运算,使系统可以每秒处理上千次请求,这比旧系统快了一些。
PBFT算法的共识过程
PBFT算法的共识过程如下:客户端(Client)发起消息请求(request),并广播转发至每一个副本节点(Replica),由其中一个主节点(Leader)发起提案消息pre-prepare,并广播。其他节点获取原始消息,在校验完成后发送prepare消息。每个节点收到2f+1个prepare消息,即认为已经准备完毕,并发送commit消息。当节点收到2f+1个commit消息时,我们就认为该消息已经被确认完成(reply)。