本文节选自：Tendermint: Byzantine Fault Tolerance in the Age of Blockchains

原文作者：Ethan Buchman

本章阐述 Tendermint 共识算法和用于原子广播（ atomic broadcast）的相关区块链。拜占庭容错共识问题将被详细讨论，并且 Tendermint 共识的一个正式说明将以π-calculus 的形式给出。Tendermint 区块链已经被非正式地证明为满足原子广播。将来我们将以进程演进的方式来描述完整的区块链协议，并证明相关特性。

Tendermint 综述

Tendermint 是区块链范式中的一个安全的状态机复制算法。其算法形态为 BFT-ABC，并且附加责任制，便于验证拜占庭节点的不诚实行为。

Tendermint 算法给每个区块赋予一个增量索引或者高度（height），在某一高度中只存在一个有效的区块，区块链从高度为 0 的创世纪块开始，由一个验证者集合投票产生下一个区块，其中每一个验证者由各自的公钥标识。每一个验证者需要维护一份完整的复制状态的拷贝。在投票产生某一高度的区块的过程中，在正式提交（commit）某一高度的区块之前，至少需要经过一轮（round）投票（vote）来达成共识。每一轮都会通过 round
robin 的方法产生一个提议者（proposer），该提议者在当轮以广播的形式提出一个提议（proposal），提议经过验证者的集体投票，来决定是否最终提交该区块或者进入下一轮。在提议的区块真正被提交（commit）之前，验证者们需要进行两轮投票
（pre-vote & pre-commit）,
通过一个简单的锁机制用来阻止少于总数 1/3 的拜占庭节点攻击。由于 Tendermint 网络的不同时性（asynchrony），当拜占庭节点超过总数的 1/3，网络存在瘫痪的可能性。

注意到，tendermint 的多轮投票机制的核心是共识算法。每一个区块包含一些元数据（metadata），称作区块头（header）。区块头里包含本区块的高度，提议时间，本区块所有交易的梅克尔根哈希值。

共识

共识算法可以大致分为以下几部分：

提议（Proposals）：
在每一轮（round）中，新区块的提议者必须是有效的，并且告诉（gossiped）其他验证者。如果在一定时间内没有收到当轮提议（proposal），当前提议者将被后面的提议者接替。

投票（Votes）：两阶段的投票基于优化的拜占庭容错。它们分别被称作预投票（pre-vote）和预提交（pre-commit）。对于同一个区块同一轮如果存在超过 2/3 的预提交（pre-commit）则对应产生一个提交 (commit)。

锁 (Locks)：
在拜占庭节点数少于节点总数的 1/3 的情况下，Tendermint 中的锁机制可以确保没有两个验证者在同一高度提交（commit）了两个不同的区块。锁机制确保了在当前高度验证者的下一轮预投票或者预提交依赖于这一轮的预投票或者预提交。

为了应对单个拜占庭故障节点，Tendermint 网络至少需要包括 4 个验证者。每个验证者拥有一对非对称密钥，其中私钥用来进行数字签名，公钥用来标识自己的身份 ID。验证者们从公共的初始状态开始，初始状态包含了一份验证者列表。所有的提议和投票都需要各自的私钥签名，便于其他验证者进行公钥验证。

验证人在发起提议（proposal）步骤之后，当且仅当收到其它验证人超过三分之二（+2/3）的投票后才会进一步推进流程。虚线箭头表示进入下一个区块高度共识流程的原子广播。

共识开始于第 0 轮，第一个提议者（proposer）是区块链头里验证者列表里的第一个验证者。每一轮最终要么完成了一个提交（commit），要么直接进入当前高度的下一轮，每一轮都会产生一个新的提议者。

与其他选举（leader election
）算法不同，Tendermint 每一轮都会产生一个新的提议者 (proposer)，验证者投票决定是否进入下一轮，这与接受提议的流程类似。

每轮的开始对同步有弱的依赖性。每一轮开始期间，存在一个用来计时的本地同步时钟，如果验证者在 TimeoutPropose 时间内没有收到提议，验证者将参与投票来决定是否跳过当前提交者。TimeoutPropose 会随着轮数的增加而增加。

每轮收到提议以后，进入完全异步模式。之后验证者的每一个网络决定需要得到 2/3 验证者以上的同意。这样降低了对同步时钟的依赖或者网络的延迟。但是这也意味着如果得不到 1/3 以上验证者的响应，整个网络将瘫痪。

简言之，每轮，开始提议弱同步，之后投票完全异步。

为了增强 Tendermint 共识网络的安全性，引入了少量的锁定规则（locking
rules）来迫使验证者自证其投票的合法性。尽管我们不需要实时广播他们的合法证明，但是我们确实期望验证者们保存相关数据。这样当网络被拜占庭故障节点瘫痪时，其可以存留为相关证据。这个问责机制确保在网络故障（例如 PBFT）的时候 Tendermint 具有一个更健壮的担保（guarantees）。

验证者使用一组不同的消息（messages）来管理区块链，应用程序状态，p2p 网络和共识。其中，核心的共识算法包含两类消息：

ProposalMsg:对应某一高度及某一轮数的区块的提议（proposal），该提议已经由提议者签名

VoteMsg:对某一提议的签名投票

一

提议

每轮开始于一个提议（proposal），提议者从内存池（Mempool）选取一批交易进而构成了一个区块，该区块随后被嵌套在 ProposalMsg 中，最后提议者广播（broadcast） ProposalMsg。如果这个提议者是拜占庭节点，他可能向不同的验证者广播不同的 ProposalMsg。

提议者通过一个简单并且相对固定的的 roubd
robin 轮流坐庄，所以每一轮只有一个有效且被所有验证者公认的提议者。如果验证者收到了之前更低轮次的提议或者提议来自于非法的提议者，该提议将被拒绝。

提议者的轮流坐庄对于拜占庭容错是必要的。比如，对于 raft 算法，如果选举出来的 leader 是拜占庭，并且 leader 与其他节点网络连接状态良好，该 leader 可以完全控制整个网络，网络节点的安全和正常运转将无从得到保障。Tendermint 通过投票和锁的机制（voting
and locking mechanisms
）确保了系统的安全性。如果一个提议者在限定时间内没有处理任何交易，排在其后的提议者将会接替他。更有趣的是验证者能通过治理模块投票来移出或者替换拜占庭验证者。

二

投票

一旦验证者从网络中收到了一份完整的提议（proposal ），他对该提议进行预投票（pre-vote）签名，并且广播到网络中。如果验证者在 ProposalTimeout 时间内没有接收到一个有效的提议，其对该提议的预投票为空（nil）。

在存在拜占庭节点的异步环境中，单阶投票，即每个验证者对每个提议只投一次，不能足以确保整个系统的安全。本质上，因为验证者可能做出一些不诚实的行为，并且消息的到达时间没有任何保障，一个不诚实的验证者可以与其他验证者进行协作来提交（commit）一个区块，然而其他没有看到这个提交区块的验证者进入了新的一轮，并提交（commit）了一个不同的区块。

一个单阶的投票允许验证者互相沟通他们知道的关于该提议的信息。但是为了容忍拜占庭故障，他们也需要互相告诉对方他们自己了解到的其他验证者声称了解到的关于该提交的信息。换句话说，二阶段提交确保了足够的验证者见证了第一阶段的结果。

对于某个区块的非空预投票是为网络提交（commit）区块已做好准备的投票。空预投票是为网络直接进入下一轮的投票。在理想的一轮中，超过 2/3 的验证者为该提议进行了预投票。在任意一轮中，区块具有的超过 2/3 的预投票被称作一个波尔卡（polka）。超过 2/3 的空预投票成为空波尔卡
（nil-polka）。

当一个验证者收到了一个波尔卡（polka），他接受到了一个信号，即网络准备提交该区块，作为一个验证者签名并且广播预提交（pre-commit）的背书。有时，由于网络的不同时性，验证者可能没有收到对应的波尔卡或者波尔卡根本就不存在。在这种情况下，验证者没有对应的波尔卡为这个预提交背书，此时预提交为空。也就是说，在没有收到波尔卡背书的情况下，签名一个预提交被看作是一个恶意行为。

预提交（pre-commit）是关于提交 (commit) 一个块的投票。空预提交则投票进入到下一轮。如果验证者收到 2/3 以上验证者的预提交，则其在本地提交该块，计算结果状态，并移动到下一高度的第 0 轮。如果验证者接收到超过 2/3 的空预提交，则投票进入下一轮。

三

锁

多轮投票的安全问题是棘手的，必须避免同一高度不同轮数分别提交两个不同区块的情形。在 Tendermint 中，这个问题可以通过锁机制（locking
mechanism）得到解决。锁机制的大致定位在波尔卡附近。本质上，预提交必须有一个波尔卡为其背书，验证者被锁定在其最近预提交（pre-commit）的区块上。

锁定规则：

预投票锁（Prevote-the-Lock）：验证者只能预投票 (pre-vote) 他们被锁定的区块。这样就阻止验证者在上一轮中预提交 (pre-commit) 一个区块，之后又预投票了下一轮的另一个区块。

波尔卡解锁（Unlock-on-Polka ）：
验证者只有在看到更高一轮（相对于其当前被锁定区块的轮数）的波尔卡之后才能释放该锁。这样就允许验证者解锁，如果他们预提交了某个区块，但是这个区块网络的剩余节点不想提交，这样就保护了整个网络的运转，并且这样做并没有损害网络安全性。

简单来说，验证者可以被看作锁在任意高度-1 轮的 nil-block 上，所以波尔卡解锁意味着验证者不能预提交一个新高度的区块直到他们看见一个波尔卡。

这些规则可以以例子的形式被更直观的理解。考虑 4 个验证者，A,B,C,D, 假设有一个第 R 轮关于 blockX 的提议。现在假设 blockX 已经有一个波尔卡，但是 A 看不见它，预提交
（pre-commit）为空，然而其他人对 blockX 进行了预提交。进一步假设只有 D 看见了所有的预提交，然而其他人并没有看见 D 的预提交（他们只看见他们的预提交和 A 的空预提交）。D 现在将要提交（commit）这个区块，然而其他人进入到 R+1 轮。由于任何验证者都可能是新的提议者，如果他们提议并投票了一个新的区块 blockY，他们可能提交这个区块。可是 D 已经提交了 bockX，因此损害了系统的安全性。注意，这里并没有任何拜占庭行为，仅仅是不同时性。

为了便于读者理解，译者补充此表格，下同

锁定解决了这个问题通过强迫验证者粘附在他们预提交（pre-commit）的区块上，因为其他的验证者可能居于这个预提交进行了提交（如上例中的 D）。本质上，在任何一个节点一旦存在超过 2/3 预提交（pre-commit），整个网络被锁定在这个区块上，也就是说在下一轮中无法产生一个不同块的波尔卡。这是预投票锁的直接动机。

当然这里必须有相应的解锁方式。假设在某一轮中，A 和 B 预提交（pre-commit）了 blockX，与此同时 C 和 D 的预提交为空。因此所有的验证者进入到下一轮，预提议 (pre-vote） blockY。假设 A 是拜占庭，为 blockY 也进行了预投票（不考虑其被锁在 blockX 上），导致了一个波尔卡。假设 B 并没有看见这个波尔卡，预提交为空，此时 A 下线，C，D 预提交 bolckY。他们进入到下一轮，但是 B 仍然被锁定在 blockX 上，C 和 D 被锁定在 blockY 上。这时因为 A 下线了，他们将永远得不到一个波尔卡。因此即使在拜占庭节点少于 1/3 的情况下，这里网络的正常运转仍然受到了影响。

解锁的条件是 1 个波尔卡。一旦 B 看见了 blockY 的波尔卡（用来为 C 和 D 的关于 blockY 的预提交背书），他应当能够解锁并预提交（pre-commit） blockY。这是波尔卡解锁的动机，其允许验证者在看见更高轮数波尔卡的时候解锁并且提交对应的新区块。

区块链

Tendermint 对交易按批或块进行处理。区块之间通过加密哈哈希算法链成一个完整的区块链。区块链包括经过排序的交易日志和验证者提交的相关证据。

为什么是区块？

共识算法一次提交若干个交易（transactions）。正如在第二章提到的那样。从分批原子广播（batched atomic
broadcast）的角度来看待这个问题，对应两个主要的优化，其给了我们更多的吞吐量和容错能力：

带宽优化：因为每一次提交 (commit) 需要验证者之间的两轮通讯，以块为单位交易的批处理，平摊了提交的成本在该区块中的所有交易上。

完整性优化：区块的哈希链形成了一个不可篡改的数据结构，跟 git 仓库很像，具备历史任意点的子状态认证检查的能力。

区块也引起了另外一个效应，看上去更微妙，但是可能更重要。他们增加了单个交易的最小延迟到区块的最小延迟，对于 Tendermint 来说在数百毫秒到数秒量级。传统的序列化数据库系统提供了提交延迟在毫秒到数百毫秒量级。他们的低延迟是因为这些数据库不是拜占庭容错的，只需要一轮通讯而不是两轮和来自于 1/2 而不是 2/3 节点的响应。然而，与其他具有快速提交时间（commit
times）的选举算法不同，Tendermint 提供了一个更常规的脉冲（pulse ），在节点故障和网络不同时方面对整个网络的状态具有更好的响应度。

脉冲在通讯自治系统一致性方面的角色现在并不明朗，但是由此引发的延迟在金融市场中是具有前景的。

区块的结构

区块的目的是打包一批交易，并且链接到前面一个块。链接包含两种形式：前面一个区块的哈希和前面区块的预提交的集合，其也被称作 LastCommit。因此一个区块由三部分构成：区块头，交易列表和 Lastcommit。

安全性

这里我们简要地证明一下 Tendermint 满足原子广播。原子广播被定义为满足以下条件：

有效性（validity）- 如果一个正确的进程广播 m，它最终成功传达了 m

一致性（agreement）- 如果一个正确的进程成功传达了 m，所有最终所有的进程成功传达 m

完整性（integrity）- m 只传递一次，并且是以广播的形式被发送者发送出去

总的顺序（total order）- 如果正确的进程 p 和 q 分别传递出 m 和 m'，p 传达 m 在 m' 之前，那么 q 传达 m 在 m' 之前

注意到，
如果把 m 看作一个区块，Tendermint 并不满足有效性，因为并不能保证提议的区块最会会被提交，因为验证者可能进入到新的一轮，并提交一个不同的区块。

如果我们把 m 看作某一区块里的一批交易，那么我们能够满足有效性通过验证者重新提议同一批交易直至交易最终被提交。

为了满足完整性的第一部分，我们必须引入额外的规则来禁止一个合法的验证者提议或者预提交一个区块，其中这个区块包含的这批交易已经被提交过。幸运的是，交易可以被梅克尔根索引，在提议和预提交以前可以进行相关的查找来滤除已经提交的交易。

或者我们可以把 m 当成一个交易（transaction），通过引入内存池的持久属性，可以满足有效性，即，交易可以驻留在内存池中直到它被提交。然而为了满足完整性的第一部分，我们必须依赖应用程序状态（application
state）来制定一些针对交易的规则，这样一个给定的交易只能进行一次。例如，可以通过基于账户的序列号，正如在以太坊中的那样。或者保存一份未使用资源的列表，每一个资源只能被使用一次，正如在比特币中使用的那样。因为有多种方法，Tendermint 本身并不保证消息只传达一次，但是允许应用开发者来指定相关特性。完整性的第二部分显而易见，因为只有正确的提议者提议的区块中的交易才能被提交。

为了证明 Tendermint 满足“总的顺序”，我们引入了一个新的特性，状态机安全性（state machine
safety），并且可以证明满足状态机安全性的协议必定满足“一致性”和“总的顺序”。所谓的状态机安全是指如果一个正确的验证者在高度 H 提交了一个区块，没有其他的验证者在同一高度提交一个不同的区块。考虑到所有的消息最终被接收，这个立刻暗示了一致性，因为如果一个正确的验证者在高度 H 提交了一个区块 B，包含了交易 m，所有其他的正确的验证者不能提交其他的区块，因此最终提交了区块 B，传达了消息 m。

现在，我们需要证明状态机安全满足“总的顺序”，并且 Tendermint 满足状态机安全。为了证明前者，考虑两个消息 m 和 m' 分别由验证者 p 和 q 发出。状态机安全确保 p 发出消息 m 在高度 Hm 当且仅当 q 发出消息 m 在高度 Hm，并且 p 发出消息 m' 在高度 Hm' 当且仅当 q 发出消息 m' 在高度 Hm'。不失一般性，因为高度是严格递增的，假设 Hm<Hm'。那么我们有 p 发出消息 m 在 m' 之前当且仅当 q 发出消息 m 在 m' 之前，这恰恰就是“总的顺序 " 的定义。

最后，为了证明当拜占庭节点少于 1/3 的时候，Tendermint 满足状态机安全，我们采用反证法。假设 Tendermint 并不满足状态机安全，允许在某一高度提交多个区块。那么我们可以证明至少需要 1/3 的拜占庭节点，与假设矛盾。

考虑一个有效的验证者在高度 H 和轮数 R 提交了一个区块 B。提交一个区块意味着验证者在第 R 轮收到了关于区块 B 的超过 2/3 的预提交。假设另一个区块 C 在高度 H 提交。我们有两个选项：要么在第 R 轮提交要么在 S 轮提交（S>R）。

如果区块 C 在第 R 轮提交，那么超过 2/3 的验证者必须为该区块预提交，那么意味着至少 1/3 的验证者在第 R 轮同时对区块 B 和 C 进行了预提交，那么显然这些同时节点是拜占庭节点。假设区块 C 在 S 轮提交。因为超过 2/3 对 B 区块进行了预提交，他们在 S 轮也将被锁定在区块 B 上，因此他们必须对 B 进行预投票。为了对区块 C 进行预提交，他们必须接收到关于区块 C 的波尔卡，因此需要关于区块 C 的超过 2/3 的预投票。然而，超过 2/3 的验证者已经被锁定在区块 B 上。节点为了收到区块 C 的波尔卡至少需要网络中 1/3 的验证者违背锁机制，这部分节点显然是拜占庭节点。因此，为了违背状态机安全，至少需要 1/3 的拜占庭验证者。即若网络中的拜占庭节点少于总数的 1/3，Tendermint 满足状态机安全性。

综上，Tendermint 满足原子广播。

在未来的工作中，我们会提供关于 Tendermint 的安全性的更正式的证明。

责任制

一个具有问责制的拜占庭容错算法能够在存在安全隐患时标识所有的拜占庭验证者。传统的拜占庭容错算法并没与这个特性，对应地也没有任何相应的保证。当然，问责制仅能适用在拜占庭节点在 1/3 到 2/3 的情况。如果超过 2/3 的节点是拜占庭，他们能够完全占据协议，此时无法保证一个合法的验证者可以收到任何拜占庭节点违法的证据。

进一步，问责制是在异步网络环境下最终性的尽力而为，在这样的网络环境中着安全问题，关键消息（critical
messages）的延迟使得在探测到安全问题以后才可能发现拜占庭验证者。事实上，如果正确的进程（correct
processes）可以接受拜占庭行为的相关证据（evidence），但是在他们能够通讯之前不可逆地失败了（fail
irreversibly），可能使得问责制永久失效（ Permanently compromised），尽管实际上这种情形可以通过高级备份策略来克服。

通过枚举安全问题的各种隐患，拜占庭验证者是可以识别的，这样协议是具有问责制的。与其它竞选相关的协议相比，Tendermint 的简洁给予了其更简单的分析方法。

在 Tendermint 存在两类安全隐患，每一种都是可问责的。第一种，拜占庭提议者在单轮中产生两个冲突的提议，并且拜占庭验证者同时对这两个提议进行投票（vote）。第二种，一些验证者在单轮已经提交（commit）之后，拜占庭验证者违反锁机制（locking
rules），致使其他验证者在随后的轮数提交一个不同的区块。注意到，若拜占庭验证者少于 2/3，只通过违反解锁机制的方法是无法引发安全性问题的，同时超过 1/3 的节点必须违背波尔卡锁机制，因为每一个提交（commot）需要有一个波尔卡为其背书。

在存在提议或者投票冲突的情况下，同时接受冲突的提议或者投票，可以根据这些提议或投票的签名来辨别这些拜占庭节点。

在违反锁定机制 (locking
rules) 的情况下，伴随着相应的安全性问题，有效的验证者必须广播在当前高度看到的所有投票，这样证据可以被收集起来。少于 2/3 的正确验证者在所有导致两个区块被同时提交的投票中集体隐匿。此时在这些投票中，如果没有 1/3 或者更多的验证者签名冲突的投票，那么存在 1/3 或者更多的验证者违反了锁定机制。

如果预投票（ pre-vote ）或者预提交（ pre-commit）影响了一个提交，它一定会被一个合法的验证者看见。因此，通过搜集所有的投票，通过匹配每一个预投票和最近的预提交，可以探测到违反锁机制的行为（violations
of Prevotethe-Lock ）。

类似的，通过匹配预提交（pre-commit ）和为其背书的波卡尔卡（polka），可以探测到违反解锁机制的行为（violations of Unlock-on-Polka ）。注意到这就意味着如果拜占庭验证者可以在看见波尔卡之前预提交（pre-commit），并且如果相应的波尔卡最终发生的话，拜占庭验证者将逃脱责任制。然而，如果每一个预提交有波尔卡背书的话，这些安全隐患就不存在。

目前的设计提供了问责制，伴随着后危机广播协议（post-crisis broadcast
protocol），但是其能够用来提高实时的问责制。也就是说，一旦提交被改变，相应的预提交，为预提交背书的预投都会发生改变，这样一直回退到创世纪块。通过上面的方式，如果发生安全问题，没有背书的投票可以立即被探测到。

故障和可用性

作为一个拜占庭共识容错算法，Tendermint 可以容忍拜占庭故障节点到（但不包括）节点总数的 1/3。这就意味着节点可能会崩溃，发送不同和冲突的消息到不同的节点，拒绝中继消息或者表现异常，安全或者运转存在问题。

协议中有两个地方我们可以通过使用本地时钟的超时特性，为不同时性做一些优化：在接收到 2/3 或者更多预投票（pre-votes）之后（不针对单个区块或者 nil）和在收到 2/3 或更多预提交（pre-commit）以后（不针对单个区块或者 nil）。在每一中情形中，我们可以睡眠一段时间用来给延迟的投票一个被接受的机会，因此减少在新的一轮没有提交区块的可能性。时钟不需要在验证者之间同步，因为验证者在观测到 2/3 或更多的投票时会重置各自的时间。

如果 1/3 或者更多的验证者崩溃，网络瘫痪，因为任何共识进展需要 2/3 以上验证者的投票。网络仍然可以读取数据，但是没有新的区块的提交。只要验证者重新上线，他们能够从之前的投票状态开始。共识状态机应该配置一个预写式日志
（write-ahead log），这样重新上线的的验证者可以快速回退到之前机器崩溃时的位置，确保没有违反规则。

如果 1/3 或者更多的验证者是拜占庭，他们能够以多种方式损害系统的安全性。例如，在同一轮提交两个块，并且投票提交这两个区块或者通过通过违反锁定机制在同一高度不同轮提交两个不同的区块。在每一种情形中，有清晰的证据显示哪些验证者是拜占庭节点。在第一个例子中，他们在同一轮签名两个不同的提议，违反规则。在第二个例子中
，他们锁定在 r-1 轮在第 r 轮提交了一个不同的区块，违反了锁定机制。

当使用经济和治理组件来激励和管理共识，这些额外的责任制保证是具有决定性的。

结论

Tendermint 本身是弱同步，拜占庭容错，状态机复制协议，拥有优化的拜占庭容错和额外的责任制来保证当超过拜占庭容错假设上限时的情形。协议采用 round
robin 的提议者产生方法，用同样的机制跳过一个提议者。多轮投票之间的安全性通过锁机制得到了保障。

本章是关于协议的表述，存在许多有待进一步讨论的重要细节，例如块之间有效的通讯（efficient gossiping of
blocks），缓存交易，验证者集合的改变和应用逻辑的接口。这些重要的话题将在随后的章节得到进一步的解释。

来源链接：mp.weixin.qq.com