DxChain中文博客

共识算法(一):初探共识


引言

在全球化的今天,不同组织之间的信息交流和资产流转仍然通过中心化的服务进行,而在中心化的服务中面临着信任问题以及因信任而导致的实效问题。如何解决在非信环境中可靠的信息交流和资产流转是全球化今天面临的重要问题之一,如:跨行转账、数据交易等。区块链技术的出现为非信环境中可信操作提供可能,区块链技术源于2008年中本聪在《BitCoin: A Peer-to-Peer Electronic Cash System》[1]提出的,其具有去中心化、防窜改、可追溯以及公开透明等特点。在区块链系统中,共识算法是区块链核心,其用来保证在去中心化环境中各个节点数据的一致性。透过共识算法研究可以探索数据在区块链系统中的流转、验证和存档过程以实现数据在不同节点的一致性。本系列文章将带你共同领略共识算法在区块链系统中的魅力。

一、 何为共识算法?

在传统中心化网络中,数据的一致性和安全性由中心化的服务器保证,数据管理员通过对中心化服务器的操作进行数据修改。如:银行业务系统,用户的转账、提现操作都是通过银行客户端(ATM机器、柜台或手机银行)对中心化服务器中的账户数据进行修改,从而实现转账或提现业务,在此过程中不会存在双花等风险。在区块链网络系统中,数据存储在分布式网络中的各个节点中,区块链系统通过共识算法来维护各个节点数据的一致性和安全性,从而保证区块链系统的常态化运行。

二、共识算法分类

在区块链领域,共识算法可以根据实现方式不同划分为难度计算型和投票表决型;根据共识算法个数不同分为单一共识和混合共识;根据共识算法确定性分为概率型共识和确定型共识。本篇文章主要从共识算法确定性角度分析现有主流共识算法。

2.1 概率型共识

从整个区块链系统来看,所谓概率型共识为记账节点(挖矿节点)通过挖矿产生最新区块,而在最新区块中的交易需要在未来​N个块后才能实现不可篡改,例如:BTC的交易确认需要在未来6个块后。为了更加有效的了解和熟悉概率型共识,本节将从PoW探讨概率型共识的相关内容。

2.1.1 PoW共识算法

PoW(Proof -of -Work)又称工作量证明算法,区块链系统中各个节点通过计算数学难题争夺记账权,从而实现交易打包上链。其中,计算数学难题的节点被称为矿工,争夺记账权的过程被称为挖矿PoW应用的经典项目比特币项目。

其解数学难题的过程如下:

sha256(sha256(blockheader + nonce)) <= target

在比特币系统的挖矿过程中,算力越大挖矿概率越大,即算力越大解出数学难题的概率也就越大。在交易完成打包后,需要经过6个块的确认达到最终的确认,即在BitCoin中的交易在达到6个块确认后被攻击的概率为小概率事件[2][3],可认为该处交易数据为安全的。

2.1.2 PoS共识算法

PoW共识算法中,采用了工作量证明作为挖矿依据,通过拼算力实现记账权的争夺,此方式挖矿浪费了大量的计算资源和电力资源。为解决PoW中资源过度浪费问题,为了弥补此不足,Sunny King在PPCoin [4]引入了权益证明(Proof-of-Stake, PoS)共识机制,区块链系统中各个节点通过持有币时间来争夺记账权,从而实现交易打包上链。其中,持有币时间称为币时币时 = 持有币量 * 持有币时间

其PoS共识算法实现过程如下:

hash(block_header) ≤ target × coinagehash(block_header)

在PoS的挖矿过程中,节点的挖矿概率与该节点持有币量和持有币时间正相关,节点持有币量越大,持有币时间越长则挖出块的概率越大。

2.1.3 DPoS共识算法

在PoW和PoS共识算法分别采用了“算力为主”和“权益为主”的竞争方式,拥有大算力和大权益是实现快速争夺记账权的依据,而委托权益共识算法(DPoS, Delegated Proof-of-Stake)则依据“选票为主”的竞争方式实现记账权的争夺。2013年8月, 比特股 (Bitshares) [5]提出DPoS共识算法,采用区块链中各个节点对候选节点投票,区块链系统根据的候选节点的票数来争夺记账权。

2.2 确定型共识

对比概率型共识来看,确定型共识对应于记账节点(挖矿节点)通过挖矿产生最新区块,而在最新区块中的交易(事务)即为确定不可更改的。为讨论确定型共识,我们将以BFT为基础,通过改进共识过程以及共识节点选择而衍生出一系列共识机制。

2.2.1 PBFT共识算法

PBFT(Practical Byzantine Fault Tolerance)[6]是一种基于状态机复制的算法,状态机在分布式系统的不同节点进行副本复制。每个状态机都保存了服务状态的副本,同时也实现了服务的操作。PBFT能够容忍拜占庭错误,在算法上具有安全性。(安全性证明:假设系统中存在f个故障节点(可以给出错误响应或者不响应)和k个诚实节点,当f个节点均不响应时,则k个诚实节点均可取得大多数结果;当f个节点错误响应,且k个节点中有f个节点离线时,此时系统仍需正常运行需要k - f个节点收到大多数正确的响应,即kf > f => k > 2f,综上系统中的全部节点R = k + f => R > 2f + f => R > 3f 即系统中最少节点数为R = 3f+1在现有的区块链系统中Hyperledger Fabric v0.6版本即采用此共识机制。

PBFT在实现过程中将节点分为排序节点和备份节点,排序节点用于接收客户端请求。PBFT的排序节点接收到客户端请求后,通过三阶段协议完成各个节点数据的一致性,其三阶段协议简要概括如下:

  • pre-prepare阶段:排序节点广播pre-prepare信息给所有节点,若节点接收pre-prepare信息,则进入prepare阶段,否则什么都不做。
  • prepare阶段:节点将自己的prepare消息广播给排序节点和其余备份节点,该节点在收到其余备份节点的prepare后,对请求n进行验证,当收到2f+1个验证后进入prepare阶段,并发送commit消息。
  • commit阶段:当该节点收到其他副本节点2f+1个commit时,则说明提案通过,并向客户端响应。

2.2.2 DBFT共识算法

DBFT(Delegated Byzantine Fault Tolerance)[7]是一种改进的拜占庭容错算法,通过投票机制选举出共识委员会,旨在提高出块速度,降低交易确认周期。现有区块链项目中NEO即采用此共识机制。

DBFT将全网节点分为共识节点和普通节点,共识节点提议新区块并对区块进行一致性验证,普通节点验证和接收新区块,以此提高系统性能。

DBFT在每一轮共识中会选出一个共识节点作为议长(通过地址Hash顺序选择),其他共识节点作为议员。每次出块时时,先由议长发起区块提案,一旦有超过2/3的节点确认这个提案,那么这个区块提案就成为了新的区块,且此区块是不可逆的。其共识过程简要概括如下(假设共识委员会委员数量为n):

  • Prepare Request阶段:满足出块条件的议长发起共识,广播Prepare Request
  • Prepare Response阶段:议员接收到请求后进行验证,验证签名并广播Prepare Response
  • Commit阶段:接收到超过(2*n)/3的Prepare Response消息后,共识节点广播Commit消息。
  • Create Block阶段:接收到超过(2*n)/3的Commit之后,产生新的区块并广播。

2.2.3 Tendermint共识算法

Tendermint[8]是一种弱同步的BFT算法,在共识过程中参与协议共识的节点被称为验证节点,验证节点轮流提议交易区块并对其进行投票。在每一个高度上只允许一个块被确认,所以Tendermint不会进行分叉。为了保证区块的安全性,Tendermint除了需要三分之二的拜占庭假设之外,还使用一种锁定规则,一旦验证节点参与提交了一个块,那么这个验证节点会被锁定在这个区块上,验证节点必须对这个区块进行预投票,或者当其锁定区块为无效块时,验证节点必须预提交下一个块才能解锁。现有的区块链系统中cosmos即采用此共识,其共识过程简要概括如下:

  • Propose阶段:新的验证节点提议一个该高度的区块。
  • Prevote阶段:验证节点验证块是否有效,并广播prevote消息。
  • Precommit阶段:验证节点接收prevote,当有2/3的节点投票通过时,节点广播commit消息。
  • Commit阶段:节点等待至少2/3个precommit并出块。若是少于2/3个commit,则重新开始新的一轮验证工作。

三、总结

本篇文章通过共识算法确定性角度分析现有主流共识算法,大致熟悉现有主流共识算法的原理和操作步骤,对于每类共识算法的详细实现过程和安全性剖析详见后续文章。

附录

[1] https://bitcoin.org/bitcoin.pdf

[2] https://www.jianshu.com/p/5effdcf79114

[3] https://happypeter.github.io/binfo/calculations

[4] https://www.peercoin.net/whitepapers/peercoin-paper-cn.pdf

[5] https://how.bitshares.works/en/master/

[6] http://pmg.csail.mit.edu/papers/osdi99.pdf

[7] https://docs.neo.org/docs/zh-cn/basic/technology/dbft.html

[8] https://docs.tendermint.com/master/introduction/what-is-tendermint.html

Author image

About Kang Gao

Blockchain Developer & Researcher