首页 > Zilliqa > 正文

如何通俗解释拜占庭容错算法?

ZILLIQA中文技术社区 2018-07-18 13:36

  前言 拜占庭容错算法(BFT,这里指的是 PBFT、DBFT这一类算法)是一种共识机制,IBM 的超级账本 Fabric、小蚁 NEO 等区块链项目使用了该共识算法。拜占庭容错算法通常用于联盟链或私有链(这点会在后文解释),比特币这样的公共链通常使用 PoW 或 PoS 共识算法。和其他算法相比,拜占庭容错算法相对更难理解,因为它的工作流程不太直观。

  本文将带你一步步走进拜占庭容错算法,为了便于理解本文将对问题和算法进行简化。

  首先,我们要解决什么问题? 拜占庭容错算法是一种共识机制,而共识机制用于使一个群体对某一事物达成一致的认识(例如,所有人都可以记账,那以谁记的为准呢,这就需要共识机制。更通俗易懂的解释,可以参看我上一篇文章)。

  我们的目的就是要达成共识,拜占庭容错算法就是一种方案,除此之外,还有我们相对比较熟悉的工作量证明机制 PoW、股权证明机制 PoS 和委托股权证明 DPos 等等。

  拜占庭容错算法的想法 为了理解这个机制的基本想法,我们需要一个场景。

  这个场景是这样的:

  你们宿舍一共 4 个人(A、B、C、D)

  因为放寒假各回了各家,现在大家要约定哪天一起返校,因为一个宿舍只有在超过一半人返校时,宿管阿姨才给你们宿舍钥匙

  4 个人不能聚在一起商量,每个人都只能通过手机与其他人取得联系

  4 个人中有人会捣乱放其他人鸽子,但无法知道具体是谁,彼此之间都是不信任的请问,在这种情况下,你们如何才能商定出一个时间返校,顺利进入宿舍?

  试想一下:如果你是 A,你发短信(“1”)给 B、C、D 表示 1 号去学校,同时你收到 B、C、D 的消息分别为(“2”,“1”,“1”),那么你“1”号应该动身去学校吗?

  我们假设 4 个人中,只有一个人捣乱,有两种情况:

  如果 B 在捣乱,那么恭喜你,你 1 号去学校能进宿舍。

  如果 C 在捣乱呢?那么最终 1 号去学校的只有两个人(A 和 D),你们是进不了宿舍的!

  情况和 2 一样。

  所以,单凭你收到 BCD 的消息,你是无法做出判断的。

  呼,说了这么多,终于到拜占庭容错算法登场了。

  拜占庭容错算法的基本想法可以用一句话来描述:系统中任何人都是不可靠的,一个人收到其他人发过来的消息后,并不立即做出判断,而是把自己收到的消息再传递给其他人,因为系统中诚实的人是多数,所以最终每个人可以根据总信息作出判断。

  听起来有点绕,其中的关键点是:收到消息后不立即判断,而是再传递给其它人,通过信息交换作出一致决定。

  还是用之前的例子,你(A)收到 B 发过来的短信“ 2 ”,你需要把短信转发给 C、D,告诉他们“B 发给我的是 2”。

  我们把整个过程用下面的表格来表示:

  编号 A B C D A 1 1 1 1 B 2 2 2 2 C 1 1 1 1 D 1 1 1 1 其中,表格里的每一行表示一人发给其他人的信息,例如第二行表示 B 发给 A、C、D 的信息分别为(2,2,2)。表格里的每一列表示一人收到其他人的信息,例如第一列表示 A 收到 B、C、D 的消息分别为 (1,2,1,1)。

  在不进行拜占庭容错算法的情况下,每个人只能看见自己的列,例如 A 只知道第一列的数字。在进行该算法后,因为信息的再传递,每个人能看到表格里的所有内容。

  如果系统中只有 1 个人捣乱,那么诚实的人现在能做出判断了:1 号去学校就可以了。

  需要说明的是,根据这个表格是无法判断谁在捣乱的,这个人可能是 ABCD 中的任何一个,但是这已经不重要了,因为系统中诚实的人只需要按照多数的那个结果去做就能达成共识了。

  如果你坚持到了这里,那么恭喜你,你已经基本理解了拜占庭容错算法 BFT 了。

  拜占庭容错到底能容多少错? 这里先给出结论:如果系统中有 F 个不诚实节点,系统的总节点数目至少要为:N = 3F 1 才能正常工作。 也就是说,容错节点数为:(N - 1)/3,容错率约为 1/3 。

  这里参考知乎上的一回答给出一个简单的证明:

  假设系统中一共有 N 个节点,其中 Fault 节点数为 F 个 ==> 那么系统至少能接收到 (N - F) 个应答消息, (因为 Fault 节点可能出故障而不发送应答消息)。系统至少需要从(N - F)个应答消息中就能做出判断。 又因为:收到的(N - F)个应答中最多可能有 F 个是假的(Fault 节点发出的) ==> 那么真实应答数为 N-F-F, 又因为:要求真实的应答大于假的应答, 即 N-F-F > F ==> 因此:N > 3F ==> 所以:N_min = 3F 1 拜占庭容错算法有什么优势 在说 BFT 算法的优势之前,我们先来回顾下这个算法的精髓:收到消息后再传递给其他人,以使系统能做出最终判断。 一个节点收到消息后,需要再传递给其他人,这个过程的效率消耗随着节点数目的增多,呈平方级上涨。100 个节点需要传递 100^2 = 10000 次消息(算法复杂度为o(N^2))。因此,使用 BFT 共识算法的网络记账节点必然不能过多。去中心化网络的记账节点少,又必然会损失安全性。此外,系统仅能容错约 1/3 ,这要求系统需要相对的高度可用。这就回答了我们在前言里面的那个说法,拜占庭容错一般用于似有链或联盟链。

  最后来说说 BFT 算法的优点:

  因为记账节点少,所以必然是专业的记账节点

  共识效率高、节约资源,节点之间不用拼算力

  严格的数学证明保证了系统的正确性

阅读更多

上一篇:落地应用才有真正价值,全新智能合约语言将为Zilliqa保驾护航

下一篇:Zilliqa进度更新第12期

您可能喜欢:

关于我们联系我们作者投稿
Copyright © 2013 比特巴手机版
币圈人都爱上的网站,新闻行情教程人物测评资讯大全