微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

从拜占庭将军问题看:区块链「 共识算法 」

2018-08-09 15:16 奎哥

来自:不止思考(微信号:bzsikao)


假如你是古代某个国家的将军,你们国家除了你以外,还有另外9个将军,每个将军带领着一支军队,总共10支军队,这10支军队在地域上分散驻扎。你们国家想要进攻一个强大的敌国,这个敌国也有一定的实力,足以抵御你们5支军队的同时袭击。因此你们10支军队必须要成一致意见,起码要大部分军队达成一致,才可顺利的消灭掉这个敌国。

而由于地域上特殊原因,你们这10支军队不能集合在一起单点进攻,必须在分开的状态下同时包围攻击敌国。如果是单支军队单独进攻的话是毫无胜算的,除非有至少有6支军队同时调遣一起袭击才能攻下敌国。你们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向和进攻时间。

此时困扰着你们10个将军的问题是,你们没有一个中心领导,10名将军都是平等的,且你们当中可能会有叛徒,叛徒可能擅自变更进攻意向或者进攻时间,甚至是传递假的进攻消息,在这种状态下,你们10名将军们能否找到一种分布式的协作方式,来让你们能够远程、准确无误的协商,从而赢取战斗呢?

这就是著名的「拜占庭将军问题」。

拜占庭将军问题就是要解决去中心化的共识机制问题,而这个共识问题也是比特币中区块链网络所需要解决的。

因为拜占庭将军们是分散的,没有一个中心的领导机构,因此他们在进攻敌方的时候必须事先对进攻地点和时间进行协商,达成共识。那么在有限的时间内,要解决提案(进攻方案)的一致性且获取大部分将军的认可,才能解决拜占庭将军问题。

在区块链网络中也是类似情况。

区块链的分布式网络中可能会有多个人提出打包区块的请求,并且其中还有可能是有伪造的区块,那么只能靠分布式共识算法来解决这个问题了。

我们知道区块链的核心价值之一就是共识,这也是大家一直所追捧区块链的特性之一。那今天我们就来重点来聊一聊区块链是怎样通过「共识机制」来解决上述问题的。

其实共识机制的概念并非是由区块链兴起才有的,它早在数学领域就是长期以来在研究和攻克的方向,尤其是在计算机领域针对分布式共识机制也已经有了一些知名的解决方案,取得了非常卓越的成就。

区块链算是一个将「共识机制」充分应用的一个场景。

一、什么是共识算法?

共识算法 顾名思义,就是通过算法手段让各参与方对某个确定的结果达成一致的方案。
在区块链里,就是指在不可靠的网络环境里,在不可信的各参与方中,寻找一个传递和验证信息的可靠策略。

不过,这里的可靠也是相对而言的,非法节点必须控制在一定的比例之内才能保证可靠性。
共识算法有很多种,目前比特币所采用的是:工作量证明的共识机制。

二、区块链为什么需要共识算法?

拿比特币举例,在比特币的区块链网络中,因为是去中心化的,每个节点都是平等的,每个节点都会有一个账本、都可以记账,那最终就会产生很多个不同的账本。

但事实上我们是需要所有人都掌握同样一个账本,才能保证系统数据的一致性,系统才能有效运行。

那如何保证在一段时间内只有允许一个节点去生成合法账本、保证大家的账本是一致的(起码大部分人的账本是一致的),如何验证合法的账本、鉴别非法账本呢?

这些问题是在去中心化的区块链网络中必须要解决的,不然谁都可以随意篡改账本内容,然后说自己的账本才是合法的,这样的话,比特币系统就乱套了。

比特币是怎么解决这个问题的呢,它采用的是PoW(Proof of Work)的共识算法。这个算法不仅可以保证在一段时间内网络中出现的提案(提出记账请求)的个数是有限的,同时也放弃了强一致性的要求,改为最终一致性要求(即允许链中同一时刻有多个合法区块,出现链路分叉,但最后会以工作量最大的那个链路,也就是最长的那条链为最终的合法链)

除了比特币,其它一些代币的区块链网络都是使用什么样的共识算法呢?

三、共识算法有哪些?

共识算法比较多,有 PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)、PoW(Proof of Work,工作量证明)、PoS(Proof of Stake,权益证明)、DPoS(Delegate Proof of Stake,委托权益证明)、Ripple(瑞波),还有 分布式一致性算法(Pasox、Raft) 等等,每种算法的玩法都不一样。

这里重点来介绍一下区块链中常用的几种:

  1. PoW (Proof of Work,工作量证明)


比特币和以太坊都是基于这种算法来实现的。简单来说,PoW 就是一份确认工作端做过一定量工作的证明。PoW 系统的主要特征是计算的不对称性,工作端需要做一定难度的工作才能得出一个结果,而验证方却很容易通过结果来检查工作端是不是做了相应的工作,哈哈,这就是俗话说的 完成工作很辛苦,检查工作很容易。

在比特币系统中,大约每10分钟就开始一轮算力的竞争工作,大家将特定的字符串+随机nonce数进行SHA256运算,期望得到一个符合系统预期的值,如果算出来的结果不满足预期,则不断的调整nonce值,重新计算,一直到满足预期值为止,所以要找到预期值还是比较难的,而且没有捷径可走,必须要不停的尝试nonce值,会消耗巨大的计算量,这也就是所谓的挖矿(这里为方便理解对工作原理介绍的比较粗略,更为具体的我会在另外一篇讲区块链哈希算法的文章中介绍)。

如果某一个节点运气好,计算的结果恰好满足预期值,那么这个节点就需要告诉全网的其它节点,让其它节点来验证它的工作是否正确,别人验证起来运算量是非常简单的,所以说PoW是一种计算力不对称性的算法。如果其它节点经过快速验证没有问题,那么这个运气好的节点就拥有了记账权,可以将自己刚才打包的区块放到区块链里。

PoW的特点是:

  • 完全去中心化,节点自由进出

  • 只要网络中非法节点的算力不超过50%,那么这种验证方法就是可靠的

  • 造成大量的计算资源的浪费(因为这种寻找随机数的挖矿行为消耗GPU等算力但不产生价值)

所以PoW的优点和缺点都挺明显的,尤其是算力空耗的问题在比特币上经常被人诟病,因此以太坊的规划目标是变更为PoS算法。

  1. PoS  (Proof of Stake,权益证明)

PoS算法解决了PoW的算力空耗的问题。POS叫权益证明,也可以称为股权证明,它其实是一种要求各节点提供拥有一定数量虚拟币证明的方式来竞争区块链记账权的共识机制。

在PoS模式下,记账权不再像PoW那样由谁的算力大谁就有更高的概率来记账,而是由谁的代币多,谁就越有可能获得记账权。可以想象一下, PoW类似于多劳多得,PoS类似于有钱人多得。

单纯靠代币多少来分配记账权,很有可能会导致记账权的中心化,所以有些代币系统在记账权的竞争中,除了计算谁的代币多以外,还会计算持有代币的时间长短,例如点点币。

虽然PoS很明显的解决了算力空耗的问题,且缩短了共识的达成时间。但PoS算法也可能会导致一些新的问题,比如,由于马太效应,系统的决策权和收益会越来越集中到少数人手中,失去公正。另外,在PoS系统上容易受到「分叉攻击」导致「双重支付」等问题。

因此POS算法也有了各种变化和升级,比如DPos算法。

  1. DPoS (Delegate Proof of Stake,委托权益证明)

DPos算法称为 委托权益证明或股权委托证明。它相比较于PoW与PoS,更进一步的提高了区块链的效率。

DPoS机制不需要网络中的所有节点都参与区块的创建和校验,它会不定期的选出一小群节点,让这小群节点去做区块链的创建和校验,这样对整个网络的资源消耗进一步减少了,也提高了区块链的工作效率,例如EOS。

但这一小群节点是怎么定出来的呢?其实是由大家投票选出来的,在DPoS系统下,每个token都是一个选票,充分利用了持股人的投票,以公平的方式达成共识,大家选出N个见证人(也就是N个矿池),这N个见证人权力平等,只有见证人才可以生成和管理区块。另外,持股人可以随时通过投票来更换这些见证人。

还有一些其它共识算法就不在这里一一展开了。在区块链中,由于每个项目的场景不同,所以设计的架构和采用的共识算法都不尽相同。主要还是从 去中心化、安全、性能 三要素中根据不同的应用场景,进行不同的组合。


●编号716,输入编号直达本文

●输入m获取文章目录

 
算法与数据结构 更多文章 这样去面试算法工程师,难怪会凉! 关于递归的有趣漫画 机器学习模型,能分清川菜和湘菜吗? 转行人工智能,哈佛博士后有话说 2018全球计算机与工程学科排名:清华第7,中国9个学科世界第一!
猜您喜欢 你应该知道的计算机网络知识 这些年你读过的书 \/*皮*\/ 腾讯云+未来峰会北京站开发者专场——参会倒计时! [DM] 都是套路: 从上帝视角看透时间序列和数据挖掘 php读取apk包信息,提取应用图标