共识算法解决什么问题(如何理解共识算法)

谈起区块链里的热门词,一定离不开伟大的共识算法,它是构筑区块链信任特性的基础。到底有哪些共识算法?今天来了解一下:

共识算法解决什么问题(如何理解共识算法)

共识算法是什么?

共识机制就是用来解决分布式系统的一致性问题,其核心为在某个协议(共识算法)保障下,在有限的时间内,使得指定操作在分布式网络中是一致的、被承认的、不可篡改的。在区块链系统中,特定的共识算法用于解决去中心化多方互信的问题。

其实简单理解就是达成一致。现实生活中很多场景是需要达成一致的。区块链系统中,每个节点必须让自己的账本和其他节点的账本保持一致。而中心化世界里,这几乎不可能,因为有一个中心服务器存在。

共识算法有几类?

在区块链系统中,共识算法则通过经济利益的博弈,来鼓励对系统的贡献及提高不可信节点的作恶成本。常用算法如PoW、PoS、DPoS等,不同的算法,其实就是不同的游戏玩法。

基于挖矿方式分类:

PoW(Proof of Work,工作量证明)—主要代表:比特币所谓的比特币挖矿就是通过计算符合某一个比特币区块头的哈希散列值争夺记账权。这个过程需要通过大量的计算实现,简单理解就是你进行的计算量大(工作量大),你就有大概率获得记账权。包括:Bitcoin,Ethereum,Litecoin,Zcash。优点:随机性、公平性好;缺点:耗能。

PoS(Proof of Stake,权益证明)—主要代表:点点币简单理解就是根据资产的多寡分配获取记账权的概率,类似股份公司中的股东。包括:Ethereum-PoS,Tendermint,Algorand,EOS DPoS,DFINITY,VBFT。优点:攻击更昂贵,性能效率高;缺点:权利集中。

DPoS(Delegate Proof of Stake,委托权益证明)—主要代表:EOSPoS的改进,通过社区选举产生记账者,类似股份公司中的董事会。如:Steemit, EOS, bitshare优点:廉价的交易,可伸缩的;缺点:目前部分集中。

为适应不同的应用场景,区块链共识机制的研究集中于优化系统的可扩展性、运行效率、容错性等方面。在新兴的区块链方案中,会将各种共识机制结合使用,例如在分层/分片方案中,最上层的主链使用PoW机制以确保全局共识的有效性并用来对抗女巫攻击,而在相对小范围的分片中,使用PoS或者BFT算法来实现更高效率的共识。典型的案例包括未来引入基于校验器管理和约分片方案的以太坊以及Zilliqa等。尽管这些方案尚未落地验证,但他们代表了未来区块链设计的趋势。

实际上,共识算法还有很多种,如用于解决可信节点间的网络通信故障问题,常用算法包括Paxos、Raft、ZAB等,常见于大数据分布式系统,这些算法不具备对不可信节点的容错性。这类算法也包括用于解决拜占庭将军问题的拜占庭容错算法(BFT)等,该算法允许有一定比例的不可信节点。

共识算法发展历程:

从历史上看,共识算法起源于多处理器计算的研究;它们解决的是处理器可能出现故障(即变得无响应)时的全局状态问题。在这些情况下通信是同步的,即受一些已知的时间上限。

后来,随着电信和计算机网络的发展,出现了另外两个问题:未知的通信延迟和对手的存在。前者导致了部分新的研究同步和异步共识算法和创建算法可以容忍任意代理行为(拜占庭行为)——即所谓的拜占庭容错算法(或BFT共识)。

随着互联网的广泛应用,对手的问题变得更加严重。如果在多处理器环境或电信基础设施中可以识别每个代理,那么在Internet的许多情况下就不能这样做。因此,出现了一种新的公共(或无许可)共识,共识算法必须成为一种协议,其中嵌入了识别和排除拜占庭式代理的规则和程序——就像一些附带机制降低了此类代理进一步参与协议的经济能力一样。这种制度以POW 和POS的名义引起了公众的注意。我们将以经济激励(BFT- ei)命名这些协议。在许多情况下,异步性和无许可性要求牺牲其他共识品质,比如决定论或适用于领导人选举场景的能力。

共识算法应用:

通常,共识算法用于解决以下问题:

· 领袖选举(在所有共识参与者中选择代理人,有权更新系统的全球状态)

· 原子交换(不能根据事件的内部属性确定其顺序事件的确切顺序)

· 状态复制(维护所有或大多数代理共享的全局状态)

这是共识算法的三个主要用例是高度相关的。例如,状态复制可以通过状态更改的适当顺序(即原子广播)来解决,而适当的领导人选举过程本身可能允许有序的原子广播(但是,在没有领导人选举过程的情况下,有达成相同结果的共识)。

总体来说,主流共识算法逐渐由PoW转向PoS共识算法,出现POW和POS混合的趋势,POW的公平性和POS的效率得到融合补充。但即便是每种加密货币背后都有一种伟大的共识算法,没有一种共识算法是完美的,各有优缺点。随着区块链项目越来越多,而共识算法也会不断改进。

共识算法解决什么问题

分布式一致性

在一个分布式系统中,如何保证集群中所有节点中的数据完全相同并且能够对某个提案(Proposal)达成一致是分布式系统正常工作的核心问题,而共识算法就是用来保证分布式系统一致性的方法。

然而由于分布式系统存在多个节点,所以系统中会出现各种故障,如:节点失效、网络延时或者宕机。最为常用的两种故障模型是 故障-停止(Fail-stop) 和 随机故障(Byzantine) ,在故障-停止模型中当进程发生故障后只是简单的停止运行。相对的,随机故障又称为拜占庭故障,意指发生故障的进程会像不忠的拜占庭将军一样,产生无法预料的响应结果。故障-停止是随机故障的一种特殊形式,因此,能够容忍随机故障的算法也能够容忍故障-停止。

CAP

在 1998 年,加州伯克利大学的教授 Eric Brewer 提出了分布式系统的 CAP 理论,该理论可总结如下:

  • 在异步的网络模型中,所有的节点由于没有__同一时钟__,仅仅能根据接收到的消息作出判断,这时完全不能同时保证一致性、可用性和分区容错性,每一个系统只能同时保证这三种特性中的两种。

这里讨论的一致性其实都是__强一致性__,也就是所有节点接收到同样的操作时会按照完全相同的顺序执行,被一个节点提交的更新操作会立刻反映在其他通过异步或部分同步网络连接的节点上,如果想要同时满足一致性和分区容错性以及可用性。在异步的网络中,我们只能__中心化存储所有数据__,通过其他节点将请求路由给中心节点达到这两个目的。

在现实世界中其实并不存在绝对异步的网络环境,如果我们允许每一个节点拥有自己的时钟,这些时钟虽然有着完全不同的时间,但是它们的__更新频率是完全相同的__,所以我们可以通过时钟得知接收到节点消息的间隔时间。时钟的出现能够让我们知道__当前消息有多久没有得到回应,通过超时时间就能在一定程度上解决信息丢失的问题__。

由于网络一定会存在延时,所以没有办法在分布式系统中做到强一致性的同时保证可用性,不过我们可以通过降低对一致性的要求,在一致性和可用性之间做出权衡,所以在目前主流的分布式系统中都选择最终一致性。

最终一致性允许多个节点的状态不一致,但是所有能够沟通的节点都能够在有限的时间同步状态,从不一致的状态恢复到一致,这里列出的两个条件比较重要,一是__节点直接可以正常通信__,二是__状态能够在有限时间内完成同步__,只有在这两个条件成立时才能达到最终一致性。

拜占庭将军问题

拜占庭将军问题是 Leslie Lamport 在 The Byzantine Generals Problem 论文中提出的分布式领域的容错问题,它是__分布式领域中最复杂、最严格的容错模型__。

在该模型下,系统不会对集群中的节点做任何的限制,它们可以向其他节点发送随机数据、错误数据,也可以选择不响应其他节点的请求,这些无法预测的行为使得容错这一问题变得更加复杂。拜占庭将军问题是对分布式系统容错的最高要求。

FLP

FLP 不可能定理是分布式系统领域最重要的定理之一,它给出了一个非常重要的结论:在网络可靠并且存在节点失效的异步模型系统中,不存在一个可以解决一致性问题的确定性算法。

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once.

这个定理其实也就是告诉我们不要浪费时间去为异步分布式系统设计在任意场景上都能够实现共识的算法,异步系统完全没有办法保证能在有限时间内达成一致。

分布式系统模型

想弄明白分布式共识问题,首先要了解分布式系统中的基础模型,我们在设计和思考分布式算法时,首先需要思考的一点就是__算法运行的环境是什么,算法运行中需要处理什么样的问题__,一般来说从以下三个方面来考虑:

  • 分布式系统中节点会发生什么样的故障?最为常用的两种故障模型是 故障-停止(Fail-stop) 和 随机故障(Byzantine),在故障-停止模型中当进程发生故障后只是简单的停止运行。相对的,随机故障又称为拜占庭故障,意指发生故障的进程会像不忠的拜占庭将军一样,产生无法预料的响应结果。故障-停止是随机故障的一种特殊形式,因此,能够容忍随机故障的算法也能够容忍故障-停止。
  • 分布式系统的网络传输时延特性是什么样的? 在分布式系统中,节点间通过传递消息进行通信,按照消息在网络中传递时间是否有上限,可以将分布式系统分为同步模型(Synchronous model)和异步模型(Asynchronous model), 在同步分布式系统中消息传递时间的上限是已知的,而在异步分布式系统中消息可能在任何时间送达.因此在同步分布式系统中,由于消息传递时间的上限已知,则可以根据超时来检测进程故障(非拜占庭故障),大大简化了分布式算法的设计,但遗憾的是,大部分实际的分布式系统往往是异步的,比如互联网就是异步分布式系统,如果为异步分布式系统中设计分布式算法,必须意识到消息可能延迟任意长的时间到达。
  • 分布式系统消息传递的可靠性如何?在分布式系统中传递的消息有可能出现丢失、乱序甚至重复送达的情况,算法是否需要容忍这些情况.网络分区就是一种常见的需要加以考虑的现象.

在整个设计和思考分布式算法的过程中,都要基于同样的系统模型来进行,并对分布式算法的正确性进行证明。通常来讲,一个正确的分布式算法需要满足两条性质:

  • Safety:具备Safety性质的算法保证坏的事情绝对不会发生,例如对于满足Safety性质的分布式选主(Leader election)算法,绝对不会出现一个以上进程被选为Leader的情况。
  • Liveness:具备Liveness性质的算法保证好的事情终将发生,即算法在有限的时间内可以结束。

综上,一个正确的分布式算法可以在指定的分布式系统模型中保证Safety和Liveness属性。

分布式共识(Consensus)

分布式共识问题,简单说,就是在一个或多个节点提议了一个值应当是什么后,使系统中所有节点对这个值达成一致意见。这样的协定问题在分布式系统中很常用,比如说选主(Leader election)问题中所有节点对Leader达成一致;原子组播(Atomic broadcast)中节点对消息传递(delivery)顺序达成一致。对于这些问题有一些特定的算法,但是,分布式共识问题试图探讨这些问题的一个更一般的形式,如果能够解决分布式共识问题,则以上的问题都可以得以解决。

为了达到共识,每个节点都提出自己的提议(propose),最终通过共识算法,所有正确运行的节点决定(decide)相同的值。

共识算法的正确性要求是在运行中满足以下条件:

  • 终止性(Liveness):所有正确节点最后都能完成决定。
  • 协定性(Safety):所有正确节点决定相同的值。
  • 完整性(Integrity):如果正确的节点都提议同一个值,那么所有正确节点最终决定该值。

如果在一个不出现故障的系统中,很容易可以构造出一个符合要求的共识算法:每个节点都将自己的提议通过可靠组播(Reliable broadcast)发送给其他节点,当节点收到所有成员的提议后,取所有提议中出现最多的值作为最终决定即可。

而如果是在存在故障的异步系统中,共识问题是否有可用的解法呢?

著名的FLP不可能性证明告诉我们:** 没有任何算法可以在存在任何故障的异步系统中确保达到共识 ,正如之前说的,大部分实际的分布式系统都是异步的,FLP不可能性证明阻止了无数分布式系统设计者把时间浪费在寻找一个完美的异步系统共识算法上,而更应该去使用一个不那么完美却有实际意义的解法。

正如FLP不可能性证明所述,不存在算法可以“确保”达到共识,但我们可以设计出有较大概率可以达到共识的算法。绕过不可能性结论的办法是考虑部分同步系统,利用故障屏蔽、故障检测器或随机化手段避开异步系统模型,构造出可接受的共识算法。

共识与多副本状态机(Replicated state machines)

分布式系统中对共识问题的直接应用常常是在多副本状态机的场景中出现的。多副本状态机是指多台机器具有完全相同的状态,并且运行有完全相同的确定性状态机。通过使用这样的状态机,可以解决很多分布式系统中的容错问题,因为多副本状态机通常可以容忍⌊N/2⌋进程故障,且所有正常运行的副本都完全一致,所以,可以使用多副本状态机来实现需要避免单点故障的组件。虽然有很多不同的多副本状态机实现,但其基本实现模式是类似的:状态机的每个副本上都保存有完全相同的操作日志,保证所有副本状态机按照相同的顺序执行操作,这样由于状态机是确定性的,则一定会得到相同的状态。

共识算法的作用就是在这样的场景中保证所有副本状态机上的操作日志具有完全相同的顺序,具体来讲: 如果状态机的任何一个副本在本地状态机上执行了一个操作,则绝对不会有别的副本在操作序列相同位置执行一个不同的操作。

而在区块链中,共识算法需要解决的问题是在多个可能会出现随机故障的节点间维护其账本数据的一致性.

最终一致性以及比特币

一致性、可用性,以及分区

  • 一致性
  • 一个系统中所有节点就系统的当前状态达成一致
  • 可用性
  • 系统时可用的且正在处理请求
  • 分区容忍性
  • 分区容忍性是指分布式系统具备一种能力:在存在网络分区时仍可以正确的工作
  • CAP定理
  • 一个分布式系统不可能同时实现一致性,可用性以及分区容忍性.它可以满足其中任意两个要求,但是不能同时满足三个.
  • 假设一个银行系统存在分区,欧文准备在上海的一个ATM取1w,此时如果ATM允许欧文取出1w,则在北京,欧文银行账户的数据库余额不会及时更新,即不满足一致性.如果想要满足欧文账户余额的一致性,则上海ATM不能提供欧文取款服务,即不可用.
  • 最终一致性
  • 所有节点最终会就共享状态达成一致,但是可能在一个短的时间段内,共享状态在各个节点所存的状态可能不一致.在分区期间,不同节点可能执行不同的更新,而这些更新可能在语义上彼此矛盾,因此还需要一个 冲突解决 机制来解决这些冲突,并使得这些节点最终在一个相同的状态上达成一致.

比特币

  • 比特币网络
  • 比特币网络是一个随机连接的覆盖网络,它包含成千上万个节点,被各种各样拥有者控制.所有节点运行相同的操作,即这是一个去中心化的同质网络.
  • 输出
  • 一个输出是一个元组, 包含一定数额的比特币以及一个使用条件.绝大多少情况下, 使用条件需要一个和特定地址对应私钥相关联的有效签名. 输出有两种状态:未使用(Unspent)和已使用(Spent).任何输出只能被使用一次, 一个地址的账户余额是所有与该地址关联的未使用输出的比特币数额总和.
  • 所有未使用的交易输出(UTXO)以及一些附加的全局参数就构成了比特币网络的共享状态.每个在比特币网络中的节点都拥有一个该状态的一个完整副本,这些本地副本之间可能暂时性地不一致,但最终将重新达成一致性.
  • 输入
  • 一个输入是一个元组,包含对前面已经创建的输出的引用,以及用于该输出中使用条件的一组参数(签名),这些参数将证明交易创建者有权使用所引用的输出.
  • 交易
  • 交易是一个数据结构,描述了比特币的转移(使用者到接收者)情况.一个交易包含很多输入和新创建的输出.这些输出将导致所引用的输出变为已使用,此外新创建的输出将被增加到UTXO中.

比特币节点处理接收到的交易

 1: 接收到交易t
 2:for each t中的输入(h,i) do
 3: if 输出(h,i)不在本地UTXO or 签名无效 then

共识算法

所谓区块链共识过程,是指如何将全网交易数据客观记录并且不可篡改的过程。目前, 比特币使用工作量证明PoW(Proof of Work),以太坊即将转换为权益证明PoS(Proof of Stake),柚子(EOS)使用授权权益证明DPoS(Delegated Proof of Stake). 以上这些算法可以称之为“经济学”的算法,所谓经济学的算法,是指让作弊成本可计算,且让作弊成本往往远大于作弊带来的收益,即作弊无利可图,通过这种思想构造一个用于节点之间博弈的算法,并使之趋向一个稳定的平衡。

计算机领域的分布式一致性算法,例如Paxos、Raft,也称之为传统分布式一致性算法。他们之间的最大区别是:系统在拜占庭将军(Byzantine Generals Problem)情景下的可靠性,即拜占庭容错(PBFT算法支持拜占庭容错)。然而无论是Paxos还是Raft算法,理论上都可能会进入无法表决通过的死循环(尽管这个概率其实是非常非常低的),但是他们都是满足safety的,只是放松了liveness的要求, PBFT也是这样。

共识算法解决什么问题(如何理解共识算法)

版权声明:本文(即:原文链接:https://www.qin1qin.com/catagory/32177/)内容由互联网用户自发投稿贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 630367839@qq.com 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022-11-16 10:02:00
下一篇 2022-11-16 10:20:00

软件定制开发公司

相关阅读

发表回复

登录后才能评论
通知:禁止投稿所有关于虚拟货币,币圈类相关文章,发现立即永久封锁账户ID!