深入浅出话共识
发布时间:2019-09-09 作者:超哥
本文详细解析了PoW、PoS、PBFT…等主流共识机制各自特点及优劣;也从单一共识向可插拔共识、从链式共识向图式共识、从确定性共识向随机性共识,归纳总结出了共识机制的发展趋势。此外,还有更多的知识点和独家观点等你来发现哦~
概述
1.1 区块链技术
2008年11月1日,中本聪发表了《比特币:一种点对点的电子现金系统》[1]一文,阐述了基于P2P网络技术、加密技术、时间戳技术、区块链技术等的电子现金系统的构架理念,标志着比特币的诞生。2009年初,中本聪搭建了以其论文为原型的网络——比特币。区块链技术是比特币网络背后的技术基础,是一种基础设施。区块链作为一种解决不可信分布式环境下能够以较低成本建立信任的计算模式和协作模式,正在悄然改变这个世界。
1.2 共识机制
由于区块链系统多数采用去中心化的分布式设计,节点是分散在各处,所以必须设计一套完善的制度,以维护系统的运作顺序与公平性,统一区块链的版本,并奖励提供资源维护区块链的使用者,以及惩罚恶意的危害者。这样的制度,必须依赖某种方式来证明,是由谁取得了一个区块链的打包权(或称记帐权),并且可以获取打包这一个区块的奖励;又或者是谁意图进行危害,就会获得一定的惩罚,这就是区块链系统的共识机制[2]。
区块链是一个去中心化的分布式系统,在该系统中,所有的节点都是一个全副本,维护着全部的账本数据。这样,当某一个或多个节点故障时,用户可以从其他的节点读取数据。由于系统中有多个副本,如何保证副本之间的一致性是整个分布式系统的理论核心,下面会详细地向大家介绍传统分布式系统和区块链系统副本一致性问题。
传统分布式系统一致性问题
2.1 分布式一致性问题
从传统的集中式单节点结构,演变到分布式多节点结构,碰到的首个问题就是一致性的保障。如何保障副本之间的一致性是整个分布式系统的理论核心。
一致性是指分布式系统中的多个服务节点,给定一系列的操作,在约定协议的保障下,使它们对外界呈现的状态是一致的。换句话说,也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案(Proposal)达成一致。
一致性的要求,在分布式系统中,系统可以达成一致性需要满足以下三个要求:
-
有限性:达成一致的结果在有限的时间内完成。
-
约同性:不同节点最终完成决策的结果是相同的。
-
合法性:决策的结果必须是系统中某个节点提出来的。
一般地,非学术角度,分布式系统一致性主要包括以下三类:
-
强一致性(Strong):数据a一旦写入成功,在任意副本任意时刻都能读到a的最新值。
-
弱一致性(Weak):写入一个数据a成功后,在数据副本上可能读出来,也可能读不出来。系统不能保证多长时间之后每个副本的数据一定达成一致。
-
最终一致性(Eventually):最终一致性是弱一致性的一种特例。写入一个数据a成功后,在其他副本有可能暂时读不到a的最新值,但在某个不一致的时间窗口之后保证最终能读到。不一致性窗口的大小依赖于以下几个因素:交互延迟、系统负载、复制协议的副本数。
-
一致性(Consistency):所有节点访问同一份最新的数据副本,读操作总是能读取到之前完成的写操作结果,满足这个条件的系统就符合我们前面对强一致性系统的定义。
-
可用性(Availability):每次请求都能获取到非错的响应,但是不保证获取的数据为最新数据,读写操作在单台机器发生故障的情况下仍然能够正常执行,不需要等到故障的节点将数据迁移到新的节点。
-
分区容错性(Partition tolerance):以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。
2.2 可信环境分布式一致性问题
2.2.1 两阶段提交协议(2PC)
-
提交请求阶段:
-
提交执行阶段:
图一:二阶段(2PC)提交协议
2.2.2 Paxos协议
-
提议者(Proposer): Proposer 负责提出提案,包括提案标号和提案内容。
-
决策者(Acceptor):参与提案的决策,Acceptor收到提案后会根据情况决策是否要接受提案,若足够多的Acceptor接受提案,则该提案3通过。
-
决策学习者(Learner):不参与提案的提出或者决策过程,Proposer收到足够多的Acceptor同意后,会将通过的决议发送给所有的Learner。
图二:Paxos算法
-
决议提出与达成:
准备阶段(Prepare):Proposer选择一个提案标号Proposer ID并将prepare消息发送给Acceptors中的一个多数;Acceptor收到Prepare的消息后,如果提案标号大于它接受的所有历史提案的标号,就回复接受,并承诺不再接受提案标号小于该标号的提案。
批准阶段(Accept):当一个proposer收到了多数acceptors对prepare的回复后,就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求,Acceptor在不违背其他提案的前提下对收到的Propose请求进���Accept处理。Proposer在收到多数节点的accept消息后,提案就已经达成。
-
决议的发布(Publish):当提案已经达成后,Proposer会将该提案发送给所有的Learner。
2.2.3 Raft协议
-
领导者状态(Leader):Leader负责处理客户端的请求并将事务同步给Follwer。
-
跟从者(Follower):接受Leader的更新事务请求,并写入本地的日志文件。
-
候选状态(Candidate): 当Follower一段时间内没有接收到Leader的心跳,会认为Leader不可用,此时副本会进入Candidate状态,并开始新一轮选主,直到新的主被选择出来。
图三:Raft选主
2.3 不可信环境分布式一致性问题
2.3.1 拜占庭将军问题及算法
-
仲裁(Quorum):只作出一次决策至少需要的得到的同意的票数。
-
活跃度(Liveness):是指在共识决策的过程中保持活跃的节点,不能出现卡死或者无响应的状态。
-
安全性(Safty): 是指执行过共识算法后,节点能够达成一致。
证明过程如下,假设系统中共有N个节点,f个拜占庭节点,仲裁组节点为Q。
-
那么要满足Liveness,则Q<=N-f,如果Q>N-f,那么f个拜占庭节点都作恶时,算法无法继续运行。
-
为了满足Safety,则需要满足2Q-N>f,即任意两个仲裁组的交集一定要有非拜占庭节点;
-
则 N+f<2Q<=2N-2f 且N>3f;
-
当N=3f+1时,Q>=2f + 1;
2.3.2 PBFT
图四:PBFT算法
-
请求(request):客户端c向服务器0发起一个请求;
-
预准备阶段(pre-prepare):该阶段,服务器0分配一个整数n给收到的请求,并将消息广播给所有的副本节点,同时将消息添加到日志的结尾,消息格式为,其中v表示发送消息的视图、m表示客户端发送的消息,d表示消息的摘要。副本收到消息后会进行消息的签名验证、消息摘要验证、视图验证和水平线验证,验证通过的消息予以接收。
-
准备阶段(prepare):当副本接受了消息时,就会进入prepare阶段,这个阶段,副本会广播消息,同时将预准备消息和准备消息写入日志。当所有正常节点对统一视图v的请求序号n达成一致时,会进入确认阶段。
-
确认(commit):该阶段,副本会广播。其他副本会进行消息验证和确认,当确认后,会将消息写入日志。
-
返回(Reply):对客户端C进行反馈。
2.3.3 SBFT
-
降低通信:通过使用收集器,副本将消息发送给收集器,收集器将消息广播给所有节点,同时通过使用阈值前面,将收集器消息大小从线性减少到常量;
-
添加快速路径:在所有副本都非故障且同步的时候,SBFT使用一种乐观的快速路径;
-
将客户端通信从f+1 减到1:SBFT通过添加一个使用收集器聚合执行阈值签名的阶段,并给每个客户端发送一个带签名的消息,从而将每个客户端的线性成本降低为一条消息;
-
通过冗余服务器进行快速路径;
图五:原理图消息流
-
客户端向主服务器发送操作请求;
-
主服务器收集客户端请求,创建决策块,并将此块作为预准备消息转发给副本;
-
副本使用σ(3f+c+1)-阈值签名对决策块进行签名,并将签名共享消息发送给C-收集器;
-
每个C-收集器收集共享签名,并为决策块创建一个简洁的完全提交证明,并将其发送回副本,这种单消息提交证明具有固定的大小开销,包含单个签名,并且足以副本提交;
-
一旦副本接受到提交证明,它会提交决策区块,并启动执行协议;
当副本在提交决策区块前,他需要完成序列块的执行,并对新的状态进行阈值签名,然后将其发送给E-收集器;
每个E-收集器收集签名,并创建决策块的完整证明,然后,它向副本发送一个证书,表明状态是持久的,向客户机发送一个证书,表明其操作已被执行完毕。
2.3.4全球部署不可信环境
区块链共识机制及其应用
共识机制是区块链系统各节点达成一致的协议,对交易的进行合法性和一致性确认。早期的区块链系统采用PoW(Proof of work),后续随着区块链的发展、出现了PoS(Proof of Stake)、DAG等一系列的算法。下面这个图直观地向大家展示了各个共识协议的使用应用。后续各小节会详细进行介绍各个协议,并对其优缺点进行简要介绍。
图六:共识协议应用项目
3.1PoW(Proof of work)
图七:区块链式结构示意图
3.2 PoS(Proof of stake)
3.2.1基于币龄的 PoS
图八:PoS CoinStake的结构
3.2.2 基于币数的PoS
-
hash计算: 执行PoS最安全的方式是让尽可能多的节点在线。参与的节点越多,发生51%攻击的可能性越低,实际网络中通过这些节点确认事务的时间越快。因此,黑币取消了hash计算公式中币龄参数,新系统计算谜题的公式变成如下:
-
改变权益修正因子:为了减少预计算攻击的可能性,权重修正因子在每一次修正因子间歇时都会改变,以便对将要用来下一个权益累积证明的时间戳的计算结果进行更好的模糊处理。
-
区块时间戳规则:通过修改区块的时间戳以更好地使用PoS。预期的出块时间从最初的60s增加到粒度匹配的时间。假设节点有一个外部时间,假设节点时间与系统共识时间偏离太多,这个节点将被孤立。区块时间戳的修改规则如下:
图九:区块时间修正规则
- hash函数:黑币采用SHA256d算法,SHA256d是将SHA256算2遍,这种算法如下所示,
通过上述的优化,黑币将可能的攻击降到最小,并能够显著提升节点的在线率。使得PoS在进一步扩大节点范围的同时能够有效地降低系统风险,提高系统的安全性。
3.2.3 DPoS
3.3DAG(Directed Acyclic Graphs)
-
交易速度快:DAG 的并行化结构和blockless的设计会提高系统的效率,交易速度大大提升。
-
无需挖矿:由于不需要区块打包,故无需挖矿;
-
无手续费:由于blockless的项目中没有矿工进行区块打包,所以不需要付手续费给矿工。
3.4VRF(Verifiable Random Function)
2016年, 图灵奖得主、MIT 教授Sivio Micali提出了一种称为 Algorand的快速拜占庭容错共识算法[20][21]。该算法是基于VRF,利用密码抽签技术选择共识过程的验证者和领导者, 并通过其设计的BA* 拜占庭容错协议对新区块达成共识. Algorand只需要极小的计算量且不易分叉, 被认为是实现区块链去中心化、可延展性和安全性不可能三角的区块链项目。
VRF是可验证随机数,所谓的可验证的随机数可以看做一个随机预言机,可以通过任意一个输入获得一个随机数输出,主要有两点:
-
对于不同的Input,Output的值是随机的,但是均匀地分布在值域范围内。
-
对于相同的Input,他的Output是一定是相同的。
VRF的过程主要包括四个步骤:
-
VRFgen:随机生成密钥,生成一对非对称加密密钥(一对公私钥);
-
VRFval:生成随机数输出;
-
VRFproof:随机数输出的零知识证明;
-
VRFver:其他节点收到输入和零知识证明后,结合生成随机数的节点的公私钥,对随机数进行验证。
图十:加密排序算法
图十一:验证加密排序
Alogrand通过VRF实现了矿工选择的不可预测性,实现了区块链的去中心化;并且每个区块随机产生,不需要竞争出块,提升了系统的扩展性;PoW、PoS当恶意节点积攒到一定数量时就可以控制网络,一般地是通过博弈的方式来实现网络稳定性和安全性保障,Alogrand随机产生区块生产者,所以即使是恶意节点,也无法随意控制网络。
区块链共识机制发展趋势
自从2018年中本聪发布比特币以来,区块链系统已经经历了10年的发展。共识算法的发展也进入了百花齐放的时期。纵观区块链共识协议的发展过程,主要体现以下几大趋势。
4.1 从单一共识到可插拔共识
早期的区块链系统,一般采取单一的共识机制,比如BTC的PoW、Peercoin的PoS等、EOS的DPoS等。
在当前的技术背景下,没有哪一种共识机制是完美无缺的,每一种共识机制都有其优点和缺点,不同的应用场景可能需要不同共识机制。在区块链解决方案中,应该实现兼容多种共识算法,在实际业务落地中有选择性的使用一种最合适的共识机制,甚至整个网络具备让开发者自定义共识机制的能力。未来可插拔的共识机制可能是未来发展的主要方向。
百度超级链XuperChain实现了可插拔共识机制,目前已经支持Pow,DPoS,Pool和Raft等共识,同时还允许用户通过该可插拔共识框架定义符合其业务特征的共识机制。
Hyperledger的 Fabric也实现了可插拔的共识机制,目前支持的共识Solo、Kafka、SBFT。