拜占庭容错(2)

拜占庭容错(2)

区块链通过结点连接的散状网络分层结构，能够在整个网络中实现信息的全面传递，并能够检验信息的准确程度。这种特性一定程度上提高了物联网交易的便利性和智能化。区块链+大数据的解决方案就利用了大数据的自动筛选过滤模式，在区块链中建立信用资源，可双重提高交易的安全性，并提高物联网交易便利程度。为智能物流模式应用节约时间成本。区块链结点具有十分自由的进出能力，可独立的参与或离开区块链体系，不对整个区块链体系有任何干扰。区块链 +大数据解决方案就利用了大数据的整合能力，促使物联网基础用户拓展更具有方向性，便于在智能物流的分散用户之间实现用户拓展

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

最后，为了证明当拜占庭节点少于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的提议者产生方法，用同样的机制跳过一个提议者。多轮投票之间的安全性通过锁机制得到了保障。