摘要 | 大狗精读 PBFT 论文（一）

1 原文与翻译

This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantinefault-tolerant algorithms will be increasingly important in the future because malicious attacks and software errors are increasingly common and can cause faulty nodes to exhibit arbitrary behavior. Whereas previous algorithms assumed a synchronous system or were too slow to be used in practice, the algorithm described in this paper is practical: it works in asynchronous environments like the Internet and incorporates several important optimizations that improve the response time of previous algorithms by more than an order of magnitude. We implemented a Byzantine-fault-tolerant NFS service using our algorithm and measured its performance. The results show that ourservice is only 3% slower than a standard unreplicated NFS.

该论文主要阐述了一种新的复制算法，这种算法可以处理「拜占庭错误」。我们认为拜占庭算法将会变得越来越重要，因为恶意攻击和软件错误是如此的常见，可以导致故障节点产生任意行为。而早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作：这个新的系统可以在诸如互联网等异步环境中工作，并且结合了多项重要的优化措施，这些改进措施将先前算法的响应时间缩短了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系统（NFS），性能测试证明了该系统仅比无副本复制的标准 NFS 慢了 3% 。

2 概念解析

相较于「比特币白皮书」来说，这篇论文的理解难度要高，因此更适合作为区块链的进阶阅读。

2.1 拜占庭错误

拜占庭错误又称之为拜占庭将军问题。要说拜占庭将军问题，我们首先要讲分布式系统。

什么是分布式系统呢？我们可以通过一个比喻去理解 ——「在只有一个手表的情况下我们无法得知手表是否出现了时间不对的故障；有两个手表的时候我们依然无法得知；但如果我们有了三个手表，我们可以以两个一致的表的时间为准，因为两个表同时出故障的概率要更小」。

所以，分布式系统即是通过多重备份来保障数据 / 计算可靠性的系统。 所以，分布式系统相关的算法会被称之为复制算法（replication algorithm）。

传统分布式系统，例如 Paxos 和 Raft 系统，能容纳「节点宕机」的错误，即一个节点发给另一个节点信息，另一个节点没有回复。

这在节点都由一个机构所控制的情况下当然没有问题，例如同一个公司的多台服务器构成的分布式系统。

但是，如果节点来自于多个机构（联盟链）或者直接允许自由进出（比特币），问题就来了。

节点不仅可能出现宕机故障，还可能发送不正确的信息。例如，一个节点问另一个节点：「查查数据库，看下小明有多少钱？」在那个节点的数据库里面，实际上小明只有 1 块钱，但是因为节点是恶意的或者有了故障，所以回答 2 块钱。——这就是拜占庭错误。

因此，新的共识算法，例如比特币使用的 PoW 算法，又比如本文所说的 PBFT 算法就出现了，用以解决「拜占庭错误」。

2.2 「同步系统」与「异步系统」

一个公司在同一个办公地点进行办公，这个是同步系统 —— 某人对同事传递信息，其它的人立刻就收到了。

如果一个公司的员工分散在全球各地，这个是异步系统 —— 某人在中国做出了一个指令，在美国的同事会在几个小时后查看。

为什么比特币 10 分钟出个块，每个块的大小 1 MB？

* Why The Design 是计算机学习中的关键问题，多问 WTD，能加深对所学知识的理解

原因在于比特币是一个「异步系统」，信息在节点间的传递受到网速的限制。

作者：maxdeath 链接：https://www.zhihu.com/question/22108601/answer/181996826 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

比特币有很多神奇的数字，这些数字到最后都被证明是很有效的，其中就包括这10分钟。

10 分钟并不是一个什么必须要遵从的公理，我猜你把它改成8分钟或者15分钟也不会有太大问题。

然而如果你把它改成1分钟，问题就来了——

我们假设任何一个新的区块传遍网络需要 2 分钟。

那么，如果 10 分钟产生一个区块，那么新区块在传播过程中没收到它的节点又生成了一个新区块的几率还不算大，因为毕竟只是全网平均产生区块时间的 1/5 。

然而，如果 1 分钟产生一个区块的话，问题就大了——假设区块传输速度平均，那么几乎可以确定，在新产生的区块传输到一半的时候，还没收到这个区块的网络有很大可能性也生成了一个新的了。

于是，一个分叉就产生了。

而这种情况是很可能会出现的，也就是说，这个网络里会长期存在至少一个分叉。

这样的网络显然是不安全的，因为比特币的假设是「如果想要作弊，你得算赢所有的竞争者，也就是全网51%的算力」。

但是，如果网络里常年有两个以上的分叉，说明全网的算力被分摊了，于是，想要作弊的话，只需要算赢一半的网络就够了，也就是 25% 算力。

很显然，这样比特币的可靠性就降低了。

这也是比特币为何不能通过减少区块产生时间来扩容了，增加区块大小也同理。

我记得有一篇论文里曾经讨论过，比特币现在的结果，通过修改区块大小和间隔时间来提高输出的话，现行的比特币系统最多支持 27 tx/s。

早期提出的 BFT 算法无法打破同步网络的假设，或者性能太低，所以无法进行实际运用，只是学界的一种模型 / 算法。直到 PBFT 这篇论文的面试。所以，这篇论文是区块链领域中的一篇里程碑式的论文。