全面介绍区块链共识机制。

640_wx_fmt_png

前言

640_wx_fmt_png 1

区块链技术是目前金融领域的研究热点,共识机制是其技术框架中非常重要的一种技术。正是因为共识机制的存在,区块链才可以在分布式网络中达到一致性状态。本文中首先介绍了共识的基本概念,接着介绍了共识算法需要面对的问题,然后介绍了目前主流的共识算法,最后对共识算法进行了整体分析与比较。

640_wx_fmt_png

基本概念

640_wx_fmt_png 1

区块链是一种分布式记账系统。在分布式系统中,最为关键的问题就是一致性问题。一致性问题指的是对于给定一组服务器节点指定一系列操作,在某个协议保障下,使得各服务器节点对处理结果达成一致,其中用到的协议也被称作为共识算法。

共识算法在分布式系统中应用十分广泛,如领导选择问题中所有进程对领导达成一致、互斥问题中对于哪个进程进入临界区达成一致、区块链中记账问题的所有节点对账目达成一致都可以看作是共识算法需要解决的问题。

640_wx_fmt_png

共识算法与容错

640_wx_fmt_png 1

在实际的分布式系统应用环境中,通过共识算法达到一致性,往往需要面对服务器节点保障及服务器节点之间的网络通信故障等问题。上述问题可以分为两类情况,一类情况是仅发生服务器宕机、通讯协议不可靠、消息延迟或丢失等情况。另外一种情况则更加严重,网络中不仅可能存在上述问题,还可能存在某些恶意节点,他们向其他节点发送虚假或者错误消息。针对此类情况,相关研究人员专门提出了拜占庭将军问题用于描述此类问题。

拜占庭将军问题是由Leslie Lamport在1982年提出的,具体描述如下:拜占庭帝国派出了m支军队去围攻一个敌人。由于拜占庭的军队在不同的地点,所以必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有多于n支军队同时袭击才能攻下敌国,而军队之间只能依靠通信兵相互通信来协商进攻意向及进攻时间。但是在拜占庭将军之间可能存在叛徒,这些叛徒的目的是通过故意传出虚假消息或者不传出任何消息等行为,来阻挠其他忠诚的将军达成一致的作战计划。

拜占庭将军问题是现实的分布式系统的模型化,其中的军队对应于分布式网络中的节点,是否能达成行动协议并消灭敌人对应于分布式网络中是否能达成一致性,而将军中的叛徒行为则对应于当计算机出现故障节点表现出前后不一致的情况,如信道不稳定、导致节点发送给其他节点的消息发生了错误,或者消息损坏等,上述分布式系统故障也被称为拜占庭错误。当分布式系统中仅出现消息丢失或者重复,但是不会出现内容损坏的情况则被称为非拜占庭错误。容错性指的处理这些异常或故障的协议。能够处理拜占庭错误的算法称为拜占庭容错,而能够处理非拜占庭错误的则被称为非拜占庭容错。

640_wx_fmt_png

共识算法

640_wx_fmt_png 1

不同的分布式系统,由于其故障类型不同,因此采用的共识算法也不同。根据处理的异常情况不同,同样可以分为两种类型,一种是针对非拜占庭错误的,这类算法性能较高,但容错性较差,如Paxos、Raft等,另一种是针对拜占庭错误的,这类算法往往容错性较高,但是性能相对较差,包括工作量证明(POW)、权益证明(POS)、股份授权证明(DPOS)、实用拜占庭容错算法(PBFT)等。处理拜占庭错误的算法有两种思路,一种是通过提高作恶节点的成本以降低作恶节点出现的概率,如工作量证明、权益证明等,其中工作量证明是通过算力,而权益证明则是通过持有权益。另外一种是在允许一定的作恶节点出现的前提下,依然使得各节点之间达成一致性,如实用拜占庭容错算法等。下面对目前存在的主流共识算法做一简单介绍:

01

工作量证明(Proof of Work,POW)

工作量证明最初提出是为了防止垃圾邮件,后来由中本聪在比特币区块链设计共识机制中引入。工作量证明是通过解决是一个不容易解答但是容易验证的问题来争取记账权以达到共识目的。例如,在比特币区块链中,是通过枚举法对得到的新字符串进行SHA256哈希运算,找出满足给定数量前导为0的哈希过程。前导0的个数越多,代表问题的难度越大。一旦某个节点找到符合要求的随机数,该节点就获得当前区块的记账权,并获得一定的奖励。该算法实现简单,节点间无需交换额外的信息,但是能源消费比较高且共识达成的周期较长。

02

权益证明(Proof of Stake,POS)

权益证明是让网络中拥有越多权益的节点有机会做更多的决定,这种机制的假设前提是权益持有人更倾向于维护网络利益且担心作恶后遭受惩罚。权益证明的实现方式很多,比较典型的是引入“币龄”概念的方式,即用币龄来计算权益。每个代币持有一天记为一个币天,完成一次记账后清空一定的币天。例如,在交易中,某人收到10个币,持有10天,则拥有100币天,如果花去5个币,则消耗掉50币天。权益证明算法不需要消耗大量资源,并在一定程度上缩短了确认时间,不过仍然需要挖矿。

03

股份授权证明(Delegated Proof of Stake,DPOS)

股份授权证明是基于权益证明发展而来的。股份授权证明能够让每个节点首先通过权益选举出n个记账节点,类似于公司中的董事会制度,后续提案由这些被选中的节点轮流处理。股份授权证明理论上不要求选出的代表个体本身是权益所有人,看起来更民主、更开放。如果选出的代表不作为(轮到自己记账时不记账),或者作恶,可以把他们踢掉,如有必要则进行惩罚(选民们也有可能被惩罚)。股份授权证明机制大大提高了效率,但是减少了记账节点的规模,属于弱中心化。

04

瑞波协议共识算法(Ripple Protocol Consensus Algorithm,RPCA)

瑞波协议共识算法使得一组节点能够基于由特殊信任节点达成共识。在瑞波网络中,每个服务节点都会维护一个信任节点列表且认为信任列表中的节点不会联合起来作弊。在共识过程中,各个需要共识的交易需要接受只接受来自信任节点列表中节点的投票,只有超过一定阈值后才能达成共识。瑞波协议共识算法比较高效,但是同样属于弱中心化且防攻击能力比较弱。

05

实用拜占庭容错算法(Practical Byzantine Fault Tolerance,PBFT)

实用拜占庭容错算法是一种基于消息传递的一致性算法。该算法经过预准备(Pre-prepare)、准备(Prepare)和确认(Commit)三个阶段达成一致性。这些阶段可能因为失败而重复进行。实用拜占庭容错算法信息在节点之间互相交换后,各节点列出所有得到的信息最后以大多数的结果作为解决方法。该算法通过投票达成共识可以很好得解决包括分叉的问题同时提升网络效率,在保证灵活性和安全性的前提下最大允许(n-1)/3故障节点的容错性,但是可扩展性相对较差。

06

Paxos

Paxos算法的基本思想是就是让分布式系统节点按照少数服从多数的方式,最终达成一致意见。Paxos算法的节点角色分为提议者(Proposer)与决策者(Acceptor),提议者提出提案,提案信息包括提案编号和提议的值,决策者收到提案后可以接受提案,若提案获得多数决策者的接受,则称该提案被批准。提议者先从大多数决策者那里学习提案的最新内容,然后根据学习到的编号最大的提案内容组成新的提案提交,如果提案获得大多数决策者的投票通过就意味着提案被通过。Paxos算法的性能较高,但是不允许恶意节点存在,所以容错性较差。

07

Raft

Raft算法是对Paxos算法的一种简单实现,包括三个角色:领袖(Leader)、群众(Follower)、候选人(Candidate)。Raft机制可以理解成从全网选出一个记账者,如果它稳定运行没有挂掉,就由这个节点记账,全网无条件接受他的记账结果,相信他是诚实的,假如这个节点挂掉了,那么其他节点是可以通过超时或网络探测感知,然后快速启动一轮投票,来选出一个新的记账节点,然后继续无条件的等它记账,这样就达成了容错性。这在信任度较高的分布式系统中应用是比实用拜占庭容错算法更加高效的一种做法,因为不需要多步的反复确认,受网络影响的可能性也小很多。Raft算法强调可用性和最终一致性,效率非常高,但是防欺诈性通常只能事后检查。

640_wx_fmt_png

区块链与共识方法

640_wx_fmt_png 1

由于共识算法是区块链中的必备因素,所以现有的区块链都采用了相应的共识算法。不同区块链在选择共识算法时,主要需要考虑以下因素:1)可扩展性。网络节点扩展能力的支持程度;2)性能效率。交易达成共识被确认的效率;3)资源消耗。共识过程中耗费的CPU、网络输入输出、存储等计算机资源;4)容错性。防攻击、防欺诈的能力。

上述标准在现实区块链场景中,往往是无法同时达到最优的。只有根据区块链的现实情况中的节点数量、信任度分级、容错性、性能效率等指标,自由选择共识机制,才能达到共识算法最优化。如对于私有链,由于是企业内部部署的区块链应用,所有节点都是可以视为信任的且无需代币激励机制,所以通常选择容错性低、性能效率高、无需代币的算法,如Paxos、Raft等。联盟链通常是由不同的机构节点组成,网络节点规模可控,内部存在不对等信任的节点且无需激励机制,所以通常选择容算性与性能效率适中、无需代币的算法,如实用拜占庭容错算法等。公有链则是任意节点可以随便加入或者退出,各种故障通常都要考虑,希望所有节点尽量拥有平等的权力并且需要引入代币激励机制,所以通常选择容错性较高、时间效率较低且具有代币激励机制的算法,如工作量证明、权益证明与股份授权证明等。下图给出了主流的区块链及其采用的共识算法。

区块链项目

共识算法

Bitcoin

POW

Ethereum

POW+POS

Ripple

RPCA

Litecoin

POW

EOS

DPOS

 BitShares

DPOS

NXT

POS

Asch

DPOS

Zilliqa

PBFT

另外,针对各共识机制的优缺点,目前很多区块链也在尝试将不同的共识算法进行整合,形成新的共识机制,如在2-hop区块链中尝试将工作量证明和权益证明的结合。在该种方式中,以轮为单位,每轮包含工作量证明阶段与权益证明两个阶段。在工作量证明阶段,节点尝试完成工作量证明提出新区块。随后进入权益证明阶段,由完成权益证明的节点对新区块进行验证和确认。通过交替进行工作量证明和权益证明,削弱初始状态下计算资源占优势的节点对区块链的影响,以进一步提高系统的安全性和公平性。

640_wx_fmt_png

总结

640_wx_fmt_png 1

共识机制解决了区块链如何在分布式场景下达成一致性的问题。在保证安全性和一致性的基础上,对于共识机制的研究一直围绕在如何平衡系统的性能效率、扩展性和资源消耗等因素上。尽管目前区块链上的共识机制有很多种,但是没有一种共识算法是适用于所有应用场景的。随着区块链应用场景的不断扩展,未来必然不断会有新的区块链共识算法涌现。