区块链中的共识算法

在对等网络结构的区块链系统中,每个运行的节点都各自保存自己的数据副本,如何保证彼此之间的数据统一,使网络中产生的数据让大家都能认可,以及确保分布式系统的一致性,这时就需要共识算法来实现。
共识算法解决的是对某个提案(proposal),大家达成一致意见的过程。
常见算法 针对非拜占庭错误的情况,一般包括Paxos、Raft及其变种。
对于要能容忍拜占庭错误的情况,一般包括PBFT系列、PoW系列算法等。
Paxos和Raft
Paxos 问题是指分布式的系统中存在故障(fault),但不存在恶意(corrupt)节点场景(即可能消息丢失或重复,但无错误消息)下的共识达成(Consensus)问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。
拜占庭问题与算法

【区块链中的共识算法】
拜占庭问题更为广泛,讨论的是允许存在少数节点作恶(消息可能被伪造)场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。
中国将军问题 拜占庭将军问题之前,就已经存在中国将军问题:两个将军要通过信使来达成进攻还是撤退的约定,但信使可能迷路或被敌军阻拦(消息丢失或伪造),如何达成一致。根据 FLP 不可能原理,这个问题无解。

FLP 不可能原理:在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。
拜占庭问题 又叫拜占庭将军(Byzantine Generals Problem)问题,是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致的决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将努力向不同的将军发送不同的消息,试图会干扰一致性的达成。
拜占庭问题即为在此情况下,如何让忠诚的将军们能达成行动的一致。
“拜占庭将军问题”模型中,对于将军们(节点)有两个默认的假设:
所有忠诚的将军收到相同的命令后,执行这条命令得到的结果一定是相同的;
如果命令是正确的,那么所有忠诚的将军必须执行这条命令。
假设1的含义是:所有节点对命令的解析和执行是一样的,这个命令必须是一个确定性的命令,不能存在随机性,也不能依赖节点自身的状态。(这个命令不能是心情好就攻击敌人,心情不好就原地休息。)
假设2的含义是:忠诚的将军需要判断接收到的命令是不是正确的。这个判断命令的方法是整个拜占庭容错技术的核心。
对于将军们的通信过程,在“拜占庭将军问题”中也是有默认假设的:点对点通信是没问题的。也就是说,在这里,我们假设A将军要给B将军一条命令X,那么派出去的传令兵一定会准确的把命令X传递给B将军。
我们考虑4个将军的情况,同时假设4个将军中最多只有1个背叛者。当4个将军A、B、C、D把敌人包围了之后,必须协商一个统一的时间去发起进攻。这时,A将军派出了3个传令兵,分别告诉B、C、D将军,下午1点准时发起进攻。到了下午1点,A、C、D三个将军发起了进攻,歼灭了敌人,同时他们三个发现B是背叛的。虽然B背叛了,但是对最终任务没有影响。
但如果A是背叛的,会发生什么情况?A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。于是,到了下午1点,B将军去攻击敌人,由于寡不敌众,全军覆没;2点,C将军全军覆没;3点,D将军全军覆没。
因为对于忠诚的将军来说,他不知道谁是背叛者,所以,他不能完全相信接收到的命令,他必须对命令做出判断。
Byzantine Fault Tolerant 算法 面向拜占庭问题的容错算法,解决的是网络通信可靠,但节点可能故障情况下的一致性达成。
最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant(PBFT)是第一个得到广泛应用的 BFT 算法。只要系统中有 区块链中的共识算法
文章图片
的节点是正常工作的,则可以保证一致性。
算法的核心思想是:对于每一个收到命令的将军,都要去询问其他人,他们收到的命令是什么。
回到刚才的第二种情况(A是背叛者),A派出3个传令兵,分别告诉B、C、D将军在下午1点、2点、3点发起进攻。B将军派出传令兵去告诉C和D两位将军,B收到的命令是下午1点进攻。C也同样派出了传令兵分别告诉B和D两位将军,C收到的命令是下午2点进攻。D也同样告诉B和C两位将军,D收到的命令是下午3点进攻。于是,B得到了3条指令:A命令B下午1点进攻,A命令C下午2点进攻,A命令D下午3点进攻。B很容易判断出来,A是背叛者(因为B知道最多只有一个背叛者)。C和D也能做出同样的判断。因此这次进攻时间的协商是无效的。
采用了这种办法以后,另一种情况又会怎样?当B是背叛者,A将军派出了3个传令兵,分别告诉B、C、D将军,下午1点准时发起进攻。B告诉C说B收到的命令是下午2点,B告诉D说收到的命令是下午2点,C和D分别告诉另外2个将军,A告诉他们的命令是下午1点。
于是,C、D收到的消息都是两个1点,一个2点。对于C、D而言,不需要判断是A和B谁是背叛者——他们只需要执行收到多的那个命令就可以了。
如果A是忠诚的,那么B是背叛的,这种情况下对于A来说,他知道自己是忠诚的,他发出的命令,至少有2个将军会执行,所以下午1点,A、C、D三个将军一起去进攻,有3个将军一起发起攻击,敌人被歼灭了。如果B是忠诚的,那么B会收到两个1点一个2点,B也会执行收到多的命令,于是B、C、D三个将军一起去进攻,有3个将军一起发起攻击,敌人被歼灭了。不管怎样,按照这种方式执行,结果是没问题的。
采用PBFT方法,本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息,通信代价是非常高的。通常采用PBFT算法,节点间的通信复杂度是节点数的平方级的。
注意,上面所讨论的所有情况里,还有一个假设:所有传递的消息都是口头消息。口头协议满足三个条件:
A1:每个被发送的消息都能够被正确的投递
A2:信息接收者知道是谁发送的消息
A3:能够知道缺少的消息
意思就是,A告诉B下午1点进攻,B可能告诉C说“A命令我下午2点进攻”。如果采用了书面消息,那么情况是不一样的。除了A1,A2和A3以外,我们在口头协议之上添加一个条件A4,使之成为书面协议
A4:(a)签名不可伪造,一旦被篡改即可发现,而叛徒的签名可被其他叛徒伪造;(b)任何人都可以验证签名的可靠性。
A派传令兵给B一张纸,A将军用自己独特的笔迹写的“下午1点进攻”,然后要求B把这张纸传给C,B在纸上用自己独特的笔迹签名表示同意,然后B传给C,C也签名表示同意,然后D也同意,最后签过所有名的纸再给每个人看一眼,就可以让所有节点一致了。这种采用书面签名消息的情况,对算法要求简单得多。但是,采用书面消息的前提是:每个将军都知道其他将军的笔迹是什么样的,并且无法模仿其他将军的笔迹。
在PBFT的基础上,又出现了很多变种算法,这些算法往往都带有一些额外的假设。例如:认为发起请求的客户端一定是忠诚的,由客户端去验证节点是否忠诚;认为绝大部分时候将军都是忠诚的,所以降低两两交互核验消息的次数;通过对节点进行分工,来提高整个系统的处理速度;等。这些变种算法由于增加了额外的假设,导致了整个系统的去中心化程度的降低(关于区块链系统去中心化程度的理解,可以参见本系列的第6篇文章)。
PBFT 算法包括三个阶段来达成共识:Pre-Prepare、Prepare 和 Commit。
超级账本中的共识算法 目前fabric嵌入的共识算法是pbft。
参考网址:
拜占庭问题与算法
区块链研习 | 看懂“拜占庭容错”,也就看懂了区块链的核心技术
拜占庭将军问题深入探讨
超级账本PBFT(拜占庭容错)算法详解(太复杂了没细看)

    推荐阅读