版权声明:可以转载,但请备注原文链接:https://shuwoom.com/?p=798

引言

共识机制是区块链的灵魂,它解决了区块链去中心化网络中两个关键的问题:谁来记账(创建区块)以及如何维护全网数据的一致性。它的目标就是让网络中的各个节点形成一致的区块链结构,也就是说需要满足以下属性:

  • 一致性:所有诚实节点保存的区块链的前缀部分完全相同
  • 有效性:由某个诚实节点发布的信息终将被其他所有节点记录在自己的区块链中

接下来的内容,我们通过介绍CAP理论、分布式系统的一致性问题、拜占庭将军问题以及常见的共识机制(POW、POS等)来介绍区块链共识机制的原理和发展。

一、CAP理论


1、CAP理论基本概念

区块链其实也是一个分布式系统,因此它也符合分布式计算领域公认的定理:CAP理论。

CAP理论是加州大学伯克利分校的Eric Brewer教授在ACM  PODC会议上提出来的猜想,2年后被麻省理工的两位教授从理论上证明成立。

CAP定理指出,一个分布式计算系统,不可能同时满足以下三点:

  • 一致性(Consistency):相当于所有节点访问同一份数据副本
  • 可用性(Availability):服务一直可用,每次请求都正常响应,但是不能保证获取到的数据时最新的
  • 分区容错性(Partition tolerance):就是分布式系统即使在部分节点故障或者分区故障的情况下,依然能够对外提供服务(进行容错处理)。

2、CA without P(弱化分区容错性)

如果要保证C(强一致性)和A(可用性),则无法保证分区容错性。但是分布式系统是无法避免分区的,两阶段的提交算法(如ZooKeeper等)主要考虑了这种设计。

3、CP without A(弱化可用性)

弱化A(可用性),那么每个请求都需要在server之间保持强一致性,而分区的出现会导致节点之间数据同步时间延长,但是CP是可以保证的。例如对一致性比较敏感的应用,例如ATM机、电子支付等,当系统出现故障时,直接拒绝服务。

4、AP without C(弱化一致性)

要求高可用性并允许分区容错,则需要弱化一致性。因为一旦一个节点或分区发生故障失去联系,为了保证高可用性,每个节点只能使用本地数据库提供服务,但这样会导致各个节点的数据不一致。这种情况一般是对一致性不敏感的应用,可以允许在新版本上线后过一段时间才最终更新完成,期间不保证一致。例如NoSQL、DNS、web缓存都属于此类。

比特币采用的POW共识机制就是牺牲了强一致性,获得高可用性和分区容错性,从而达到最终一致性。

 

二、一致性问题


一致性问题是分布式领域最为基础也是最重要的问题。它的一个基本目标就是在部分错误的情况下,保证系统的可靠性,这就要求系统中各个计算机在协作过程中对传递的信息达成一致。

分布式系统在建立之初首先要解决的问题就是一致性问题,它主要考虑以下情况:

  • 节点之间的网络通信不可靠,包括延迟终端、内容故障等
  • 节点的处理可能是错误的,甚至节点自身随时可能宕机
  • 同步调用会使得系统变得不具备可扩展性(Partition tolerance)
  • 可能存在恶意节点故意要破坏系统

分布式系统对一致性问题的常用解决方案是:state machine replication,这个我会在ratf算法讲解的时候单独写文章介绍。

一致性模型

一致性根据强弱,可以分为两类,分别是弱一致性和强一致性。

  • 弱一致性:

其达到的效果是最终一致性,典型的有比特币,比特币的交易账本会随着时间的推移最终达到一致性。其它的还有DNS应用(增加一条新的解析记录,需要过一段时间后才能访问到最新记录)。

  • 强一致性

大家可以理解为同步的概念,常见的有:Paxos、Raft和ZAB算法。

 

三、共识算法


共识和一致性,很多时候大家很容易搞混淆,实际上这两个是不同的概念。一致性往往是指分布式系统中多个副本对外呈现的数据的状态,而共识则描述了分布式系统中多个节点之间,彼此对某个状态达成一致结果的过程。所以说,一致性更注重的是结果状态,共识更多是一种手段、过程。

一般情况下,失败、出现故障(非响应)情况被称为非拜占庭错误,伪造信息恶意响应的情况被称为拜占庭错误,对应的节点也称为拜占庭节点。

所以拜占庭错误问题讨论的范围更广,它是讨论在允许少数恶意节点的情况下达成一致的问题。

根据解决的是否拜占庭错误,共识算法可以分为以下两类:

这里需要说明下,确定性算法,一旦对某个结果达成共识,就不可逆转。而概率算法,如比特币使用的工作量证明机制,共识结果是临时的,随时间推移,共识结果可能会发生改变,但最终会达成一致共识。

 

四、FLP不可能原理


FLP不可能原理是Fischer、Lynch和Patterson三位科学家在1985年发表的论文。它的定义如下:

在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。

说白了,这个原理就是告诉我们不要浪费时间,去为异步分布式系统设计一个在任意情况下都能达成一致共识的共识算法。

 

五、拜占庭将军问题


在1982年Leslie Lamport等人通过提出拜占庭将军问题(Byzantine Generals Problem)来描述分布式系统容错与一致性问题。

Leslie Lamport在其论文中这样描述拜占庭将军问题:

一组拜占庭将军分别率领一支军队共同围攻一座城市。现在这些军队有两种行动策略:进攻或撤离。因为各个军队如果不能同时行动(即一部分军队进攻,一部分军队撤离)的话可能会造成灾难性后果,所以各个将军需要通过投票来达成一致的策略。也就是要么所有军队一起进攻,要么所有军队一起撤离。但是现在这几个将军分布处在城市的不同方向,只能通过信使进行联系。在投票的时候,每个将军会将自己的策略(进攻或撤离)信息通过信使分别通知给其他军队的将军,然后每个将军就可以通过自己的投票和其他所有将军送来的信息从而决定是进攻还是撤离。

但是这里有两个问题:

(1)将军中可能存在叛徒,他们可能选择糟糕的行动策略来破环军队的整体行动。例如有9个将军,其中有一个时叛徒。8名忠诚的将军中出现4人投进攻,4人投撤离的情况。这个时候,叛徒就可能故意给4名投进攻的将军送信表示投票进攻,而给另外4个投撤离的将军送信表示投票撤离。那么在4名投进攻的将军来看,投票结果是5人投进攻,从而发起进攻;而在4名投撤离的将军来看,投票结果是5人投撤离,从而选择撤离。最终就导致军队的行动不一致从而遭到灾难性后果。

(2)由于将军之间是通过信使进行通信的,即使能保证在所有将军都是忠诚的情况下,也不能排除信使可能被中途截杀或者被敌人替换。因此很难通过保证人员可靠性和通信可靠性来解决问题。

把上面的问题映射到分布式系统中,将军就对应计算机,信使对应通信系统。

拜占庭问题就是在上述情况下,如何让忠诚的将军对行动达成一致。对应到区块链,就是如何在不可信的环境下,如何让所有节点形成一致的区块链结构(分布式账本)。

下面,我们就来介绍各种拜占庭问题(一致性问题、共识问题)的解决方案,包括比特币使用的POW工作量证明机制。

 

六、POW(工作量证明)


比特币的一大重要成就就是采用了POW工作量证明机制解决了拜占庭问题。

在比特币网络中,时刻都在产生新的交易,而节点需要将合法交易放入区块中写入区块链里。那么这里就有两个问题:谁拥有记账的权利以及如何达成一致性。

POW,工作量证明机制,通过一个竞争机制(计算猜测一个nonce随机值,得以解决规定的哈希问题),让计算工作完成最出色的节点获得记账的权利。这样可以保证一段时间内,只会出现少数几个同一高度的合法区块。而POW通过这种算力消耗的经济惩罚限制了恶意节点的参与,因为它需要付出大量的经济成本。而这个计算过程就是挖矿。

1、工作量证明机制的基本原理

工作量证明机制的主要特征就是让节点解决一个数学问题从而获得该区块的打包权(记账权),这个数学问题就是不断的修改随机值(nonce),并对区块头进行哈希运算,使得计算的哈希值小于某个目标值。这个计算过程需要耗费大量的计算资源和电力成本,从而限制了区块链网络中提案的数量(拥有记账权的节点数量),而验证却很容易,只需对目标区块头进行哈希校验并对比目标值大小即可。

例如,给定一个字符串“Hello World!”,我们给出的工作量证明是,可以在字符串末尾添加一个随机值(nonce)整数,使得变更后的字符串进行SHA256哈希运算后,得到的哈希结果是以“0000”四个零开头,只有这样才通过验证。那么,为了达到这个工作量证明,我们就需要找到nonce值使得字符串SHA256哈希运算后得到四个0开头,但是由于哈希函数的特性(任何微小的改动都会导致哈希值完全不一样),我们只能通过暴力破解的手段,也就是一直对nonce进行递增来破解。那么最多需要运算10^4=10000次才能找到目标nonce值。

而在验证的时候,只需要拿到目标的nonce值跟“Hello World!”字符串拼接后进行一次SHA256哈希就可以进行快速验证。

对于比特币,其区块结构如下。某个节点想要获得区块的打包权,就需要不停地变换nonce值,并对区块头进行SHA256哈希运算直到找到小于某个目标值为止。

2、工作量证明机制的过程

我们可以将比特币的工作量证明机制的步骤大致分为以下过程:

  • 生成Coinbase交易(用于奖励矿工),并将所有的交易打包,通过Merkle Tree算法生成Merkle根的哈希值
  • 把Merkle根哈希值跟区块头中的其他字段组合在一起,将区块头的80字节数据作为工作量证明的输入
  • 遍历区块头中的nonce随机值,并对更变后的区块头进行双重SHA256哈希运算,将运算后的哈希值跟目标哈希值进行对比,如果小于目标值,则解题成功,工作量证明完成

3、工作量证明机制的优点

  • 算法简单,容易实现
  • 攻击成本高(要获得网络中多数节点的认同,攻击者需要投入全网50%以上的算力(51%攻击,才能保证篡改成功,这使得攻击者篡改成本极高,难以实现)

4、工作量证明机制的缺点

  • 非常浪费能源(计算力和电力)
  • 区块确认时间比较长(共识时间长),比特币目前确认一个区块需要10min钟
  • POW算力集中化,风险和收益的博弈,最终必然导致联合挖矿,而算力大的矿池逐渐对系统的去中心化构成威胁(如下图,各大矿池的算力)

5、总结

  • 干的越多,获得越多
  • 通俗的说,POW就是社会主义,安劳分配,多劳多得

 

七、POS(权益证明)


POS可以作为POW算法的一种替换。POW是保证比特币、当前以太坊和许多其它区块链安全的一种机制,但是POW算法在挖矿过程中因破坏环境和浪费电力而受到指责。POS试图通过以一种不同的机制取代挖矿的概念,从而解决这些问题。

POS是POW共识机制的升级,根据每个节点所占货币的比例和时间,从而等比例来降低挖矿的难度,加快寻找随机数的速度。

1、权益证明机制的原理

POS机制是署名为“Quantum Mechanic”的数字货币爱好者提出的(如下图),经过社群讨论后并得到认可。如果POW竞争的是计算力,那么POS竞争的就是资产。节点持有的资产越多,挖掘块的概率就越大。POS机制用验证者来取代POW机制中的矿工。

网址:https://bitcointalk.org/index.php?topic=27787.0

举例来说,在POW中,一个用户用1000美元购买一个计算机进行挖矿,从而获得产生新块的奖励。在POS中,一个用户拿1000美元购买等值的代币,并把这些代币作为押金放入POS机制中,从而获得产生新块的奖励。但是,在POW中,用户如果用2000美元购买计算机,那么就得到2倍的算力,那么挖到区块的概率就是以前的两倍。同样,在POS中,如果用户用2000美元购买等值的代币作为押金投入到POS机制中,那么它挖到区块获得奖励的概率也是以前的两倍。

2、权益证明机制的过程

  • 验证者把自己的一些货币作为押金投入到POS机制中
  • 接下来,验证者就会开始验证区块(相对于POW的挖矿过程)。当他们发现一个区块可以添加到区块链时,他们会把自己的持有的货币作为投注进去作为押金来验证它
  • 如果区块被添加到区块链中,那么验证者就会获得跟他们投注的押金成比例的奖励

3、权益证明机制的优点

  • 资源消耗少,不需要消耗大量的电力和计算力
  • 缩短了共识达成的时间

4、权益证明机制的缺点

  • 单纯采用POS机制的区块链产品,需要通过IPO的方式来发行,这会导致少数人获得大量成本极低的货币。因此,一般采用POW+POS的双重混合机制,前期通过POW机制挖矿来发行货币,后期发行完货币后通过POS机制来维护网络稳定
  • 实现较为复杂
  • 中间步骤较多,容易产生安全漏洞
  • 需要时间验证

5、总结

  • 持有越多,获得越多
  • 通俗的说,POS就是资本主义,按钱分配,钱生钱

 

关注我的微信公众号(shuwoom的博客),每周定期推送文章:

打赏

发表评论

电子邮件地址不会被公开。