授权拜占庭容错算法

文章正文
发布时间:2024-08-16 09:25

授权拜占庭容错算法

授权拜占庭容错算法,是基于持有权益比例来选出专门的记账人(记账节点),然后记账人之间通过拜占庭容错算法(即少数服从多数的投票机制)来达成共识,决定动态参与节点。dBFT可以容忍任何类型的错误,且专门的多个记账人使得每一个区块都有最终性、不会分叉。

相关简介

拜占庭将军问题(Byzantine Generals Problem/BGP)

拜占庭将军问题是指“在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的”。因此在系统中存在除了消息延迟或不可送达的故障以外的错误,包括消息被篡改、节点不按照协议进行处理等,将会潜在地会对系统造成针对性的破坏。1

改进型实用拜占庭容错(Practical Byzantine Fault Tolerance/PBFT)

PBET共识机制是少数服从多数,根据信息在分布式网络中节点间互相交换后各节点列出所有得到的信息,一个节点代表一票,选择大多数的结果作为解决办法。PBET将容错量控制在全部节点数的1/3,即如只要有超过2/3的正常节点,整个系统便可正常运作。

联邦拜占庭协议(Federated Byzantine Agreement/FBA)

联邦拜占庭协议的主要特性是去中心化和任意行为容错,通过分布式的方法,达到法定人数或者节点足够的群体能达成共识,每一个节点不需要依赖相同的参与者就能决定信任的对象来完成共识。

工作过程

拜占庭将军问题

最为熟知的两种共识机制分别是PoS(工作证明机制)与PoW(权益证明机制)。NEO在其基础上进行改进,拟定了一种新的共识机制,称为dBFT。

在对投票的正确结果进行判定时,拜占庭将军问题总会出现。假设拜占庭帝国的9位将军带领军队包围了古罗马,为了成功占领古罗马城,将军们面临两个选择,一是全体进攻,一是全体撤退,如有任何将军违背了共识决定,就会导致全军覆没。

每天进行一次投票决定是进攻还是撤退,若某一决定的赞成率超过50%,便达成共识。因为每位将军所处的地理位置不同,因此他们会让信使将各自的投票通报给其他将军。

这个体系存在固有缺陷。

首先,任意数量的拜占庭将军都可能受罗马人的贿赂成为拜占庭军队的叛徒,这些将军就称为叛变的将军。

其次,任何将军都可能做出不合适的决定,这些将军就称为判断不当的将军。

再者,通报将军指令的信使也可能受罗马人的贿赂叛变篡改投票结果,而且信使也可能无法通报信息或通报错误的信息。

拜占庭将军的情形可用来类比分布式计算系统所面临的问题:系统存在可能会造成生态瘫痪的不可信及不能正常工作的节点时怎样达成共识?

dBFT算法:有很多协议想要解决拜占庭将军的问题。如Hyperledger的工作证明机制就使用了PBFT算法。而NEO则使用dBFT算法来解决拜占庭将军的问题。NEO创始人之所以选择这个协议是因为与其他现有方案相比,它的可扩容性与性能更强。

可扩容性对于任何区块链来说都是一个主要问题。随着交易数量的增加以及网络规模的扩大,区块链必须相应地扩容。如果区块链不能根据需求扩容,就会导致交易延迟或交易无法处理。

类比一下:假设有个国家叫NEO,这个国家的每位公民都有权选举领袖,也称为代表。代表负责制定国家法律。如果公民不同意代表对某部法律的投票决定,可以下次票选另一位代表。公民会告诉所有代表怎样做能让他们最为满意。每位代表必须追踪了解所有公民的需求并在账本上做好记录。满足公民的所有需求后才能通过法律,目的在于让公民满意。

需要通过法律时,就会从代表中随机选出一名发言人,这位发言人将根据公民的需求拟定法律。拟定法律时他会计算这部法律对国家的幸福指数(衡量幸福程度的指标)有何影响。接着,发言人将拟好的法律交给每位代表,每位代表先判断发言人的计算结果与它们的是否一致,再与其它代表商讨验证幸福指数的计算结果是否正确。如果66%的代表一致表示发言人计算的幸福指数是正确的,那么法律就此通过,大功告成。

全体节点都是诚实的,达成100%共识,将对法律A(区块)进行验证。

如果只有不到66%的代表达成共识,将随机选出一名新的发言人,再重复上述流程。这个体系旨在保护系统不受叛徒/坏人及无法行使职能的领袖(即没有恶意只是无法正确计算幸福指数的领袖)影响。

以此类推,对于NEO区块链而言,公民就是NEO持有者,大多数NEO持有者都是普通节点,他们只能转移或交易资产。

就像NEO国的公民一样,他们不能参与区块验证。公民选出的代表就是NEO智能经济的记账节点。记账节点负责验证区块链上写入的每个区块。

公民的需求就是NEO持有者进行的交易,法律代表区块链当前生成的区块,而幸福指数代表当前区块的哈希值。下面我们来了解下系统是如何实施保护的。

不诚实的发言人

鉴于发言人是随机选出的一名代表,因此他可能会不诚实或出现故障。在下文的案例中,发言人就给3名代表中的2名发送了恶意信息(法律B),同时给1名代表发送了正确信息(法律A)。

不诚实的发言人向左边的节点发送了正确信息(A),但向中间和右边的节点发送了恶意信息(B)

在这种情况下该法律议案无法通过。中间与右边的代表计算的幸福指数与发言人发送的不一致,因此就不能验证发言人拟定的法律,导致2人拒绝通过法律。左边的代表因接收了准确的法律,因此能确认幸福指数,继而成功完成1次验证。但本提议仍无法通过,因为不足66%的达成共识(还需要2票)。接着将随机选出一名新发言人,重新开始共识流程。

不诚实的代表

在此情况下,发言人是诚实的,但其中一名代表出现了异常。

右边的代表向其他代表发送了不正确的信息(B)

这样,发言人拟定的法律A就可以获得验证,因为(左边与中间)诚实的代表都可以验证由诚实的发言人拟定的法律A,达成66%的共识。代表也可以判断到底是发言人向右边的节点说谎还是右边的节点不诚信。这点现在还不清楚,但公民可以根据相关数据审核各节点是否诚信/正常运作。这些信息有助于投票人判断哪个代表最信得过,继而选择把票投给哪个代表。

本词条内容贡献者为:

肖志勇 - 副教授 - 江南大学