作者：王永革教授，著名华裔密码学家，北卡罗来纳大学夏洛特分校 (UNC, Charlotte) 计算机系终身教授，德国海德堡大学获得博士学位。
在前一篇文章中我们分析了 PBFT 拜占庭协议的安全性问题。今天我们探讨另外一个被区块链系统广泛使用的 Tendermint BFT 拜占庭协议的安全性问题。Tendermint BFT 拜占庭协议可以认为是 PBFT 拜占庭协议的改进版。据最新的统计，Tendermint BFT 拜占庭协议被超过 40% 的 PoS 区块链所使用（参阅 Jae Kwon 最近的演讲：Tendermint powers 40%+ of all proof-of-stake blockchains ）。比如，公链 Cosmos（常被称为「Internet of Blockchain」）和联盟链 Hyperledger burrow 都使用了 Tendermint BFT 拜占庭协议。我们的分析是基于以下论文中的 Tendermint BFT 协议：
-E. Buchman, J. Kwon, and Z. Milosevic. The latest gossip on BFT consensus. Preprint arXiv:1807.04938, 2018. https://arxiv.org/pdf/1807.04938.pdf
Tendermint BFT 的作者称其协议是在异步网络里安全的。在前边文章中，我们提到过，常用的异步网络是用如下的模型来刻画的：
-存在一个 Global Stabilization Time (GST)，在 GST 之前，任何消息可能丢失（比如 DoS 攻击），或被重新排序。在 GST 之后，网络变为同步网络。GST 什么时候开始，没人知道。
但是我们所要注意的是，Tendermint BFT 虽然使用了以上异步网络模型，但是它也有一个额为的很强的假设：
-所有的节点之间都有一个安全可靠的点对点的通信渠道。也就是说，如果一个节点 A 向节点 B 发送一个消息。那么节点 B 一定会在 GST 之后的某个时间收到这个信息。
这是个很强的假设。比如说，在这个模型里，DoS 攻击一般是不被允许的。今天我们来分析 Tendermint BFT 协议。我们的分析结果是：即使在如上很强的网络假设下，Tendermint BFT 也不是安全的。在分析其安全性之前，我们先给出其协议的形式化描述。
在 Tendermint BFT 协议中，我们假定有 n=3t+1 个节点 P1, …, Pn。其中最多 t 个节点被攻击者所控制。在整个协议的运行过程中，每个节点有五个变量： step, lockedV, lockedR, validV, 和 ValidR。对每一个区块链的高度 h，该协议从 round 0 开始一直到共识达成（也就是说：一直到高度为 h 的区块生成）。然后协议进入区块链的下一个高度。协议的每一个 round 含有三步： propose, prevote, 和 precommit。对每一个区块链高度 h，每个节点首先初始化她的五个变量： step = propose, lockedV = nil, lockedR = ?1, validV = nil, 和 ValidR = ?1。然后所有节点从 round 0 开始执行协议一直到高度为 h 的区块生成。每个 round r 有一个大家公认的发起人。该发起人的身份是由一个公开函数 proposer(h, r) 决定的。高度为 h 的 round r 过程如下：
1.propose: 发起人 Pi = proposer(h, r) 区分一下两种情形：
◎r=0 或 validV=nil: Pi 选择她自己的提议 v 并置 vr=?1。
◎r>0 并且 validV?nil：Pi 置 v=validV 并置 vr=ValidR
然后 Pi 广播如下的消息给所有的节点
?PROPOSAL, h, r, v, vr?
所有节点 Pj 初始化其超时计数器函数 OnTimeoutPropose(h, r)。
2. prevote: 所有在 step = propose 的节点 Pj 区分以下三种情形：
◎Pj 从 Pi 收到的?PROPOSAL, h, r, v, vr?中 vr = ?1： 如果 lockedR = ?1 或 validV =v，那么 Pj 对所有节点广播如下消息 ?PREVOTE,h,r,H(v)?。否则 Pj 对所有节点广播如下消息 ?PREVOTE,h,r,nil?。Pj 置 step = prevote。
◎o Pj 从 Pi 收到的?PROPOSAL, h, r, v, vr?中 vr >?1 并且 Pj 已经收到了至少 2t + 1 个?PREVOTE, h, vr, H(v)?：Pj 区分以下两种情形
●lockedR ≤ vr 或 lockedV = v：Pj 对所有节点广播如下消息 ?PREVOTE, h, r, H(v)? ●否则 Pj 对所有节点广播如下消息 ?PREVOTE,h,r,nil?
Pj 置 step = prevote.
◎Pj 从 Pi 收到的?PROPOSAL, h, r, v, vr?中 vr >?1 但是 Pj 尚未收到 2t+1 个 ?PREVOTE,h,vr,H(v)?：Pj 什么都不做。
3. precommit:
◎每当处于 prevote 状态的节点 Pj 收到 2t + 1 个消息 ?PREVOTE, h, r, ??，Pj 初始化超时计数器函数 OnTimeoutPrevote(h, r)。
◎每当处于 prevote 状态的节点 Pj 收到 2t + 1 个消息 ?PREVOTE, h, r, nil?，Pj 向所有节点广播消息 ?PRECOMMIT, h, r, nil? 并置 step = precommit。
◎如果 Pj 在状态 prevote 或状态 precommit 并已经从 Pi 收到的?PROPOSAL, h, r, v, vr?和从所有节点收到至少 2t + 1 个消息 ?PREVOTE, h, r, H(v)?，那么 Pj 进行以下的步骤
●如果 step = prevote，那么 Pj 置 lockedV = v, lockedR = r, 向所有节点广播消息 ?PRECOMMIT, h, r, H(v)?, 并设置 step = precommit。 ●Pj 设置 validV = v 和 validR = r。
4. decision: 每当节点 Pj 收到 2t + 1 个消息 ?PRECOMMIT, h, r, ??，Pj 初始化超时计数器函数 OnTimeoutPrecommit(h, r)。如果 Pj 尚未对高度 h 的区块最初决定，并且从 Pi 收到的?PROPOSAL, h, r, v, vr?，从别的节点收到至少 2t + 1 个消息 ?PRECOMMIT, h, r, H(v)?，那么 Pj 决定 v 是高度为 h 的区块并初始化她的五个全局变量。然后进入高度为 h + 1 的 round 0。
5. 自动 round 更新: 在任何时候如果节点 Pj 收到 t + 1 个 round r′ > r 的消息，那么 Pj 自动进入到 round r′。
6. 超时计数器函数:
(a) OnTimeoutPropose(h, r): 广播 ?PREVOTE, h, r,nil? 并设置 step = prevote.
(b) OnTimeoutPrevote(h, r): 广播 ?PRECOMMIT, h, r,nil? 并设置 step = precommit
(c) OnTimeoutPrecommit(h, r): 进入高度为 h 的 round r + 1。
最近我们在如下文章中对 Tendermint BFT 的安全性进行了分析：
-Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks
该文章的分析结论是 Tendermint BFT 共识协议在异步网络里是不安全的。我们在本文，简单的介绍我们设计了在异步网络里对 Tendermint BFT 协议的攻击办法。为了简化我们的描述，我们假定系统有 n=3+1=4 个节点 P1,P2, P3, P4。其中节点 P1 被攻击者控制。另外我们假定 round 0 的发起人是 P1。我们的攻击在 round 0 展开：
1. 在高度 h 的 round 0，P1 选择一个最小可能的合法区块 v 作为其提议。P1 对节点 P1,P2, P3 广播消息?PROPOSAL, h, 0, v, ?1?。
2. 收到消息 ?PROPOSAL, h, 0, v, ?1?后，P1 对节点 P2, P3 广播消息 ?PREVOTE, h, 0, H(v)?，节点 P2 和 P3 对所有的节点广播消息?PREVOTE, h, 0, H(v)?。节点 P1,P2, P3 设置 step = prevote。
3. 节点 P2 和 P3 收到 2 + 1=3 个消息 ?PREVOTE, h, 0, H(v)?。所以节点 P2 和 P3 设置 lockedV = v, lockedR = 0, step = precommit, validV = v, validR = 0。然后节点 P2 和 P3 向所有节点广播消息 ?PRECOMMIT, h, 0, H(v)?。
4. 因为每个节点收到至多 1+1=2 个 pre-commit 消息，没有节点可以在 round 0 决定高度为 h 的区块。
5. 在 round 0 的超时计数器过期后（我们假定 GST 尚未到达），所有的节点进入高度为 h 的 round 1。
6. 从此之后，节点 P1 进入睡眠状态并且不在参与任何协议的执行。
7. 假如 round 1 的发起人是 P2（或 P3），P2 对所有的节点广播消息 ?PROPOSAL, h, 1, v, 0?。因为节点 P4 在 round 0 收到了至多 t + 1 个对 v 的 provote 消息，因此在超时计数器过期之前 P4 什么都不做。因此没有诚实的节点可以收到足够多的 prevote 消息让协议进入下一步。在 round 1 的超时计数器过期后（我们假定 GST 尚未到达），所有的节点进入高度为 h 的 round 2。
8. 假如 round 1 的发起人是 P4, P4 对所有的节点广播消息 ?PROPOSAL, h, 1, v′, ?1?。因为节点 P0 在 round 0 选取了最小的合法区块 v，在过去的一段时间，新的交易已经被提交，所有在很大概率状况下，v′和 v 是不一样的。因此节点 P2 与 P3 不会接受 v′，而是对所有的节点广播消息?PROVOTE, h, 1, nil?。在 round 1 的超时计数器过期后（我们假定 GST 尚未到达），所有的节点进入高度为 h 的 round 2。
9. 这样的过程将一直持续下去。所有高度为 h 的区块永远无法生成。系统进入死循环。
我们以上的攻击是在异步网络的 GST 之前是可以展开的。所以当网络进入同步后，由于各个节点所锁定的值不同，所以系统一直无法恢复运行。
查看王永革教授在区块律动 BlockBeats 发表的其他文章：
Sperax 首席科学家王永革：PoS 有中心化的嫌疑，PoTR 是现今最好的解决方式
PBFT 拜占庭协议安全性分析：不适合联盟链或公链-区块律动 BlockBeats
拜占庭共识已经无法满足今天公链和联盟链的安全需求-区块律动 BlockBeats
Sperax：U 盘 Staking？一种基于硬件随机源的 PoS 设计 | 新项目介绍-区块律动 BlockBeats
区块律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。
—-
编译者/作者：区块律动BlockBeat
玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。
|
