拜占庭容错（Byzantine Fault Tolerance）

拜占庭容错（Byzantine Fault Tolerance）

Tendermint是一个分布式系统状态复制引擎，用于在多台机器安全一致地复制一个应用。所谓安全性，指的是即使有多达1/3的机器出现任意故障的情况下， Tendermint仍然能够正常工作。所谓一致性，指的是每一个正常工作的机器都会有着同样的交易日志，计算相同的状态。安全一致的复制是分布式系统中一个基本原则问题，它在各种应用程序（从货币到选举，到基础设施规划等）中的广泛应用的容错能力方面承担了极其重要的作用。

Tendermint被设计成易于使用、易于理解，且性能优异，适用于广泛的分布式应用。

正文

分布式共识系统成为现代互联网基础设施中的一个关键组件，正助力于每一个主要的互联网应用。本章节内容介绍了必要的背景材料来理解和探讨这些系统。

复制状态机（Replicated State Machine）

最常见的用来研究和实施分布式共识（distributed consensus）的范例的是复制状态机的范例，其中，一个确定的状态机在数个进程（processes）之间被复制，这样不管部分进程是否失败，这些进程看上去像单个状态机。状态机有一些列输入驱动，这些输入被称作交易（transactions），每一个交易根据其是否有效，可能引起一个状态迁移并返回一个结果。更正式的，交易为数据库上的原子操作（atomic operation），意味着其要么完成要么根本就没有发生，不能返回一个中间状态（ intermediate state）。状态交易逻辑（state transition logic）由状态机的状态转移函数决定，这个函数映射了一个交易和目前的状态到一个新的状态和一个返回值。状态转移函数有时也被称为应用逻辑（application logic）。

订购交易（order the transactions）并且将相应的交易日志（ transaction log ）复制到每一个进程是共识协议的责任。使用一个确定的（deterministic）状态转移函数意味着在给定同样的交易日志的情况下，每一个进程将计算出相同的结果。

复制状态机架构如图所示。

如图：一个复制状态机在多个机器之间复制了一个交易日志和结果状态。交易从客户端接受，运行了共识协议，在交易日志中订购（ordered），最后执行得到最新状态。在图中，每一个菱形代表了单个机器，其中，虚线代表机器间的通讯用来承载进行订购交易（ ordering transactions）的共识协议。

Tendermint的目标是创建一个通用目的，高性能，安全和健壮的复制状态机。

不同时性（Asynchrony）

容错复制状态机（fault-tolerant replicated state machine）的目的是在对上层提供服务的时候，协调网络中的计算机的同步，不管是否存在故障节点。

保持同步意味着成功复制交易日志；提供一个有用的服务意味着在处理新交易的时候保持状态机的可用性。传统上系统的这些方面被各自成为安全性（safety）和可用性（liveness）。通俗地，安全性意味着没有任何坏的事情发生；可用性意味着好的事情最终发生。安全违规（ violation of safety）意味着存在两个或者更多的有效的，竞争的交易日志。可用性违规（violating liveness ）意味着一个无法响应的网络。

通过接受所有的交易可以很容易来满足可用性。通过不接受任何交易可以很容易来满足安全性。因此，状态机复制算法可以被看作在两者之间的一个平衡。一般地，进程在提交一个新的交易在之前，需要对来自于其他进程的信息设立一个阈值。在同步的环境中，我们对网络消息的最大延迟或者处理器时钟的最大速度作出假设，通过轮流坐庄来提议新的交易，进行大多数投票表决，如果提议者在同步假设的区间内并没有产生任何提议，则跳过（skip）提议者的这一回合。

在一个异步的环境中，没有关于网络延迟或者处理器速度的保证的假设，权衡将变得更为困难。事实上，所谓的FLP不可能性结果（FLP impossibility result）证明了在确定的异步进程（单个进程可能会崩溃）之间的分布式共识的不可能性。该证明意味着，因为进程可能失败，存在协议的有效执行，但进程恰好在某一时间崩溃这样就阻止了共识。因此，我们对共识没有任何保证。

一般地，协议中的同步是通过管理某些交易时用到的超时（timeouts）来进行的。在异步环境中，消息能够被任意延迟，依赖同步来确保安全性的话可能导致交易日志的分叉。依赖同步来保证系统的可用性能够引起共识的宕机，并且服务无法响应。前者通常被看作更为严重，因为调解冲突日志可能是一个令人生畏或者不可能的任务。

实际上，仅当消息延迟能够被良好的定义和控制的时候，同步解决方案才会被使用，例如在一架飞机上的控制器之间，或者利用同步的原子时钟的数据中心之间。因此，尽管存在很多高效的同步解决方案，计算机网络的一般化的不可靠性（general unreliability）太大以至于不能实际投入使用而不显著增加额外的成本。

根本上有两种途径来克服FLP不可能性结果。第一个是采用更强的同步假设-甚至相当弱的假设也是足够的，例如，那个唯一的最终崩溃的进程被怀疑崩溃了，正确的进程不受影响。一般地，这个方法利用leaders，其扮演了一个特别的协作的角色，并且在超时并被认为发生故障了以后可以被跳过。实际上，这样的领导选取机制成功运转起来很难。

第二种克服FLP的方法是使用非确定性的-包含随机化元素，这样达成共识的可能性接近为1。尽管第二种方法更智能并且某些高级加密技术近些年来取得了速度上的提高，依赖随机化的方法通常更慢。

广播和共识

为了让一个进程复制状态到其它进程上，它必须有基本通讯原语的权限来允许其传播或者传递信息。一个最有用的原语是可靠广播（reliable broadcast）。可靠广播（RBC）是一个广播原语满足如下特性，对消息m，有：

有效性（validity） - 如果一个正确的进程广播m，它最终成功传达了m
一致性（agreement） - 如果一个正确的进程成功传达了m，所有最终所有的进程成功传达m
完整性（integrity） - m只传递一次，并且是以广播的形式被发送者发送出去

本质上，可靠广播使得消息最终到达所有的进程一次。

另外，更有用的原语是原子广播（ atomic broadcast（ABC）），其满足可靠广播（RBC）和另外的一个属性：

总的顺序（total order） - 如果正确的进程p和q分别传递出m和m'，p传达m在m'之前，那么q传达m在m'之前
原子广播是一个可靠的广播，其中值(values)以相同的顺序被发送到每个机器上。注意到这实际上复制交易日志的问题。通俗地讲，该问题可以被称作共识，共识原语的标准定义满足以下条件：

终止性 - 每个正确的进程最终能做出决定
完整性 - 每个正确的进程最多只做出决定一次
一致性 - 如果一个进程做出了v1的决定，并且另外一个进程做出了v2的决定，那么v1=v2
有效性 - 如果一个正确的进程做出了v的决定，至少一个进程提议了v

直观地，共识和原子广播看上去十分类似，主要的差异在于，原子广播本身作为一个协议是连续的，然而共识期望终止。这就是说，每一个可以精简为另一个。共识可以被精简为原子广播通过决定第一个原子广播的值。原子广播可以精简为共识，通过依次运行许多共识协议的实例，然而存在一些微妙的考量，特别是在处理拜占庭故障方面。

一个完整的参数空间的关于原子广播精简为共识的描述仍然是一个开放的研究话题。

历史上，尽管大多数用例实际上需要原子广播，采用的最为广泛的算法是称作Paxos的共识算法，在90年代介绍并且证明该算法正确性的是Leslie Lamport。Paxos同时赋予和困惑了共识科学，一方面提供了第一个真实世界的，实用的，容错的共识算法，另一方面又难于理解和解释。算法的具体实现使用了其专门的技术来从Paxos建立原子广播，使得这个生态难于操纵，理解和利用。不幸的是，几乎没有任何工作使得提高该框架更容易理解，尽管有尝试来描绘解决方案中的各种困难。

在2013年，Ongaro和 Ousterhout发表了Raft，一个状态机复制算法，其主要的设计动机是可理解性。与其从一个共识算法开始，并且尝试建立原子广播，Raft的设计首先考虑的是交易日志，寻求正交组件，其组合在一起来提供最终的原子广播，尽管其不是被这样描述的。

Paxos是工业领域的主要共识算法，在工业领域像亚马逊，谷歌和其他扩建了高可用性全球互联网服务的公司。

Paxos 共识位于应用程序栈的底部，提供了资源管理和分配的一致接口，操作在一个更慢的时标相比于其他面对用户的高可用性应用程序。

Raft登场以来得到了广泛的采用，特别是在开源社区，其具有多个主流语言的实现，并且在多数项目中作为其主干。
Raft与Paxos在设计方面主要的不同是先聚焦于交易日志，而不是单个值，特别是允许一个leader持续提交交易直到其卸任，这时领导选举开始生效。在某种程度上，这类似于在区块链中采用的方法，尽管其主要优势是能够容忍不同种类故障。

拜占庭容错（Byzantine Fault Tolerance）

区块链通过在共享数据库上责任的去中心化，减少了对手方风险，因此被称为“信任机器”。比特币由其具有的抵抗任何攻击和恶意行为的能力而著称。传统地，容忍恶意行为的共识协议被称为拜占庭容错共识协议（Byzantine Fault Tolerant ）。术语“拜占庭”被使用，源于拜占庭将军们面对的类似问题，这些将军们尝试相互协调来攻击罗马，使用唯一的信使，其中一个将军可能是叛徒。

在一个崩溃故障中，一个进程可能宕机。在一个拜占庭故障中，故障节点能做任何事情。崩溃的故障更容易处理，因为没有进程会对其他进程说谎。只存在崩溃故障的系统可以通过简单的多数决定规则（ majority rule）来操作，因此通常能够同时容忍近一半的系统故障。如果系统能够容忍失败的数量是f，这样系统必须至少有2f+1个进程。

拜占庭故障复杂一些。在一个具有2f+1进程的系统中，如果f是拜占庭，这些拜占庭节点可以协作来说任何事情对另外f+1的进程。例如，我们尝试取得单比特共识，并且f=1,所以我们有N=3个进程，A，B，C，其中C是拜占庭，如图2.2所示。C可以告诉A这个值是0，告诉B这个值是1。如果A同意它是0，B同意它是1，那么他们都将认为他们获得了大多数，提交，这样就违反了安全条件。因此，拜占庭系统能够容忍的故障上限小于非拜占庭系统。

如上图一个拜占庭进程C，告诉A一件事，告诉B另外一件，致使他们得出关于网络的不同的结论。这里。简单的大多数投票导致了安全违规，源于单个拜占庭进程。

事实上，可以证明拜占庭故障的上限为f

在1999年，Castro 和 Liskov 发表了实用拜占庭容错（Practical Byzantine Fault Tolerance），提供了第一个优化的适用于实际的拜占庭容错算法。其为工业系统中拜占庭容错的实用性设定了一个新的先例，每秒可以处理成千上万比交易。除此之外，拜占庭容错仍然是被人认为是昂贵的，大部分时间是不必要的，并且最流行的实现很难建立在其上面。因此，尽管学术对其兴趣日增，包括大量提高了的变种，但在实施和配置方面并没有太多进展。进一步，如果网络中超过1/3的节点是拜占庭，PBFT将不能提供任何保证。

密码学，信任和经济学

根本上说，容错这个问题起源于缺乏信任 - 不知道一些进程将如何表现（behave）。正式地，信任需要从理论上被定义成一种信息，其作为一种减少世界模型熵的手段-信任某个人就是乐观地减少这个人对于这个世界的不确定性，使得可以把注意力放在更高阶的组织层面上。

密码学原语从根本上与信任问题相关，主要被定义为允许熵大量减少的机制-成功认证一个密码学函数把一个可能结果的分布坍缩成一个点，或者在一些例子中一些少量的结果。

它是做所周知的有着更好制度信任的文明，例如法治具有更高的生产率和更充满生气的经济。结果产生了一个直观的感觉，能够更多的信任相互作用，减少可能结果的空间，其需要被主动建模，使其更容易协调。不幸的是，评价现代机构的信誉越来越困难，因为他们的复杂度在近些年增加了很多，增加了可能性，其声称的确定性是幻觉。

幸运的是，密码学形成了社会中心的信任体系的基础，奇迹大地提高了人类在全球范围内协作的能力，由于减少了欺骗和无责任行动的风险。比较有趣的是密码学原语在BFT算法中的重要性，为了认证和散播不确定性。

最有趣的是，经济机制也能当作减少熵的一种方式，迄今为止经济代理可以被激励-更有可能被用来执行一个特定的行为。比特币深入的洞察是密码原语可以与经济激励结合起来有效减少公共共识网络的熵来取得状态安全复制。

更正式的信任的信息理论根基，密码学，共识和经济学和他们之间的关系的调查将会在以后的工作中展开。

区块链

区块链的核心是一个关于拜占庭容错原子广播的聚焦完整性的方法。例如，比特币区块链结合了经济学和密码学随机化来提供一个强的概率保证，保证安全违规不会发生，给定了一个弱同步假设，即区块间的通讯比产生哈希碰撞更迅速。实际上，然而，众所周知，比特币的安全保证容易受到各种狡猾（subtle）的攻击。

区块链从两个关键的优化中得到它的名字，其利用这两个优化解决了原子化广播的问题。第一个是交易以块为单位进行分组来分摊高提交延迟（在10min量级）。第二个优化是通过加密哈希把区块链接起来成为一个不可篡改的链，这样就很容易验证历史记录。两个优化都相对于原始的BFT-ABC的有所提高，前者提高了性能，后者提高了容错。

经过这几年的发展，使用哈希链接交易块并以原子广播发送出去已经成为公共的区块链共识算法。据作者所知，Tendermint是第一个这样的提议，升级了知名的80年代的BFT算法，成为了自成体系的共识算法。Tendermint被IBM跟进，IBM升级PBFT到区块链，JP摩根升级了一个Raft的BFT版本。

过程演算

各个部分同时执行的分布式系统，因难以设计、构建和调试而饱受诟病。它们更难以正式验证，因为大多数技术的形式验证，以及实际上非常基础的计算机科学，都是通过推算得到的，因此很难正式验证。

过程演算是一种为并发计算提供了有条理的基础原理的模型系列。最通常的演算方法，Communicating Sequential Processes（CSP）构成了许多现代编程语言的理论基础。比如Go语言，在设计中包含了并发原语。

我们可以使用一个正式的逻辑来表达一个过程可能满足的属性。举例来说，模态Hennessy–Milner逻辑可以表示，在某些或所有形式的动作发生后，一个进程将满足其他一些逻辑表达式。通过将更复杂的运算方法添加到逻辑中，可以建立正式的系统，可以很容易地描述分布式系统的重要属性，比如安全性、可用性和本地化等。通过π-calculus编写的系统可以被正式验证，以满足使用模型检查软件的相关属性。

当我们使用π-calculus来详细说明Tendermint算法时，我们会使用相关的正式逻辑，以及相应的属性验证，以备将来的工作。

Tendermint的需求

比特币及其衍生物的成功，特别是以太坊和他们的关于安全，自治，分布式，对任意代码的容错执行的前景引起了事实上每一个主要的金融机构的兴趣。特别地，出现了对两种种区块链技术：一方面是公链，被亲切地称为Big Dad公链（Big Bad Public Blockchains），其协议被内建经济激励通过原生货币（native currency）的方式所支配。

另一方面是所谓的私有链，更准确的被称为“联盟链”（ consortia blockchains），通过哈希树的使用，数字签名，p2p网络和加强的问责制，其对传统共识和拜占庭算法有一定的提高。

就像现代社会的基础设施持续的去中心化或者正如商业的跨组织本质，对透明，问责和高性能的拜占庭系统的需求越来越多，这个系统支持的应用程序从财政到域名注册到电子投票和与治理的高级机制协作和未来的演进。