专访 | 那篇“怼”Algorand的论文说了啥？来听作者解释

编者按：本文来自36氪战略合作区块链媒体“Odaily星球日报”（公众号ID：o-daily，APP下载）

Odaily星球日报出品

作者 | 王也

6月24日，知名比特币投资人李笑来在微博上发文“我是真不知道Algorand是什么，也看不懂他们都在说什么...谁给我讲讲？”

李笑来还配了几张微信聊天截图，截图的内容大概就是刚刚进行过荷兰拍卖的，由图灵奖得主创办的明星公链Algorand被一位来自美国大学的教授质疑Algorand存在严重的、基础性错误。

人红是非多。6月18日，Algorand刚刚进行完第一轮荷兰拍卖，但是上线二级市场后币价暴跌，还被很多人diss为“图灵奖级别资金盘”。市场上Algorand争议太多，就连笑来老师都出来送瓜了。

质疑Algorand的论文作者是来自美国北卡罗来纳大学夏洛特分校（UNC Charlotte）计算机与信息学院王永革教授，同时也是公链项目SperaX的联合创始人兼首席科学家，王永⾰教授提出的RLCE后量⼦算法成为美国标准技术研究院NIST的候选标准。

近日，Odaily星球日报就其发布的论文独家采访了王永革，王永革向我们详细分析了论文中提到的对Algorand的质疑之处。

王永革表示，早在今年5月份，他就已经发布了这篇题目为“Another Look at ALGORAND”的论文，王永革对Odaily星球日报称，从没想到过自己的论文会被拿出来做恶意解读，这完全曲解了自己对Algorand的正面观点和改进意见。

6月26日，王永革通过媒体对外声明，“最近网络上以各种方式传播的所谓“由王永革教授撰写的一篇论文提出了Algorand项目严重的、基础性错误”的说法，是对他该篇论文的误读和炒作。”

王永革称，他在2019年5月正式公布了题目为“Another Look at ALGORAND”的论文，从学术角度对Algorand项目提出了几点商榷意见，包括理论上存在分叉可能，以及Algorand中的拜占庭协议过于复杂，有优化空间等，不过，“该论文内容被广泛误读”。

王永革向Odaily星球日报重申自己并非对Algorand这个项目有意见，恰恰相反，他对Algorand十分欣赏，并认为Algorand是当前最优秀的公链项目之一。之所以发表文章，也是因为当初对Algorand提出的抵抗分叉机制感到好奇，并认为有进一步优化的可能性，所以纯粹出于学术讨论的立场发表的该文章。

王永革解释称，其论文中提出的Algorand在理论上存在分叉可能，实际是PoS共识普遍存在的无代价模拟攻击（costless simulation attack）问题。任何采用PoS共识的公链在理论上均存在这样的风险；至于Algorand中的拜占庭协议过于复杂的问题，已经注意到Algorand团队从最初设计到最终实现的过程中，进行了很多改进，作出了优化。王永革教授表示，称该论文“提出了Algorand项目严重的、基础性错误”的说法，“显然是对该论文的误读和炒作”，并对这样的行为感到很气愤。

王永革称自己在推特上公开发布这个论文之前就已经给Algorand创立者，也是图灵奖得主Silvio Micali教授以及Algorand首席科学家陈婧女士发送过这份论文，遵守了学术界的规矩，但是后来却没有得到对方的回应。

后来在接受我们的采访中，王永革声明，他从未说过Algorand系统是完全错误的，而他的论文也是针对Algorand 2017年发布在arXiv的文章做出探讨。

王永革这篇论文对Algorand质疑的地方主要分为三点：

一、Algorand理论上存在分叉的可能性

首先，王永革认为Algorand提出的零分叉是不可能的。王永革表示，所有的PoS共识都存在无代价模拟攻击（“costless simulation attack” or “nothing at stake attack”）的问题。Andrew Poelstra在他2014年的文章“A Treatise on Altcoins”中已经注意到了这个问题。王永革说，Algorand和别的采用PoS共识的公链一样，在理论上存在分叉的风险。

Algorand 声称自己解决了区块链中的分叉问题，使其成为一个可以持续「进化」的公链。由于区块链的去中心化设计，每个节点都必须保持一致，这使得单纯的系统升级在区块链上很难做到，每当改变规则，很容易导致系统分叉。但 Algorand 却是几乎不会出现分叉的分布式账本，因为其分叉的概率低至1/10^18 ，这相当于如果每一秒出一个块，那么从宇宙大爆炸到现在 Algorand 只会分叉一次。交易能在几秒钟内得到确认，通过 Algorand 的转账资金立即可用。

对于网络不在强同步的情况下（即两个区域因网络延迟问题提议了两个区块），Algorand 网络将会出现分叉。白皮书中提到这不影响 Algorand 的安全性，但会影响 Algorand 网络内的活跃度。在给定的 S 时间内，因为不同分叉区块上的委员会成员将拥有不同的区块信息，也就意味着他们不会计算彼此对区块公证时的投票数，因此没有足够的票数将达到人数阀值，BA*将无法在更多的分叉区块上达到共识。而此时 Algorand 将会提出一个所有用户都统一的分支，并且运用 BA*共识来使用户确认是否应该切换到此分支。在全网弱同步的情况下，若时间超过 S，Algorand 网络就完成不可逆的分叉，不能恢复。这里的 S 只是一个系数，具体参数并未提及。

Algorand的共识机制在许可环境（permissioned environments）下和无需许可环境（permissionless environments）下都可以正常运行，在许可环境下只需要保证全网 2/3 的节点是诚实节点，在无需许可环境下需要保证全网2/3的资产（token）掌握在诚实节点手中，在这两种情况下，Algorand网络产生分叉的概率将被降低到小于 1/10^9（Algorand 2017年的文章中写到的是1/10^12 - 1/10^18 ）。

在论文中，王永革认为，Algorand的这两种假设没法保证这种小概率的分叉特性。Algorand的文章认为，只要恶意节点控制的节点数不超过总结点数的1/3，恶意节点就没法恶意分叉。但是王永革举出了一个反例：恶意节点可以通过控制某些特定的不超过1/3的节点而轻易的分叉。

“Algorand的2017文章有一个定理：如果任何时候恶意节点总数（或恶意财产总值）小于总节点数（或总财产）的1/3，那么恶意节点是没法对Algorand发起分叉攻击的。这个定理是不对的。”王永革说道。

王永革进一步解释，假如在区块链高度100的时候，Algorand链上所有的财产集中在两百个用户手中。这些用户可以表示为P1, P2, …, P200。在链增长的过程中，新的用户会加入，同时这两百个用户可能会把他们的Algorand财产全部出售。

此外假定在区块高度300的时候，链上已经有700个用户了。在这个时候，用户P1, P2, …, P200的数目已经小于总用户数的1/3了（他们所持有的财产总值也远远小于Algorand总财产的1/10）。根据Algorand的2017文章的数学模型和定理，如果这些用户P1, P2, …, P200在区块高度300的时候变为恶意的，他们是没法对Algorand的主链发起分叉攻击的。但事实是：如果这些用户在区块高度300之前，已经几乎售完了他们手上的Algorand财产，他们对Algorand的主链已经没兴趣了。

所以他们可以从区块高度100开始，生成一条新链。因为这些用户组成了区块高度100 的所有用户。所以他们可以非常快速的生成一条假链。他们的这条假链可以很快的生成并很快超过主链的长度。到这个时候，新加入的用户，是没法辨别那个链是主链的。换句话说，在区块高度300的时候，不超过总节点数1/3的恶意节点（或者总财产值不超过1/3的恶意财产）P1, P2, …, P20可以分叉Algorand主链。这与Algorand的2017文章的定理是矛盾的。

王永革特别指出，他的以上攻击，是无代价模拟攻击对Algorand攻击的一个特例。所有的基于PoS共识的区块链是没法预防这种攻击的。要想防止无代价模拟攻击，我们必须引入别的机制。比如SperaX是用可信硬件来击败这种攻击的。

二、“大部分节点是诚实节点”，这种假设是不切实际的

在Algorand网络里，所有参与共识投票的用户都是秘密地得知他们的身份，投票后他们的身份被暴露，虽然敌手可以马上腐蚀（corrupt）他们，但是他们发送的消息已经无法被撤回，另外在消息生成后，用于签名的临时秘钥会立刻被销毁，使得敌手在该轮无法再次生成任何合法消息。

Algorand假设全网超过2/3的节点是诚实的，而且，他们假设所有的诚实节点在完成任务之后都会销毁这个临时密钥。

王永革认为这种假设是不可行的，他认为在一个分布式网络中，尤其是在一个无需许可环境下，去假设一个节点足够诚实是不现实的。如果一个节点被给予足够多的好处，他是可以被“贿赂”的。一个原本诚实的节点最终也可能“叛变”，这就是“贿赂攻击”（bribery attack）。

王永革分析道，虽然一个恶意攻击者没办法提前知道要去腐蚀（corrupt）哪个用户，但是它可以公开明码标价它收买一个区块提议者（block proposer）和区块验证者（ verifiers）的协议。他会鼓励那些区块提议者（block proposer）和区块验证者（ verifiers）在提出他们的区块建议之前或投票之前先和他这个恶意攻击者联系。通过这种方式，这些恶意节点就可以确认要去腐蚀的目标用户。这种情况下，区块提议人和区块验证者就会成为这些恶意节点的拥趸。

王永革认为Algorand这种假设大部分用户是诚实节点的设想在现实世界中是不切实际的。每一个在区块链网络中的节点都想把自己的利益最大化（几乎没有人会拒绝这一点），被选中的区块提议者和区块验证者在得到足够多的“贿赂”的前提下是可以“叛变”的。而且，对于参与共识投票的用户来说，系统并没有给他们足够的经济激励来确保他们去销毁临时密钥，与直接销毁这个临时密钥相比，他们更倾向于把这个临时密钥卖掉。

三、Algorand中的拜占庭协议存在优化空间

Algorand 通过「即时提议与确认（Immediate Propose and Agree）」来形成共识。这是一种「超快速拜占庭协议（Byzantine Agreement，BA*）」。拜占庭协议是普遍运用于区块链的通讯协议模式。Algorand 的共识机制分成两个步骤，分别是提议和达成共识。

实用拜占庭容错算法（Practical Byzantine Fault Tolerance，PBFT）是首个实用的在异步分布式网络中实现拜占庭容错的共识算法。算法应用于一个分布式文件拷贝系统。系统中共有 3f+1 个复制节点，其中最多 f 个拜占庭错误节点。系统中的每个复制节点都运行一个有限状态机的副本，并且支持若干种操作。

PBFT 算法包含一个三阶段的协议，分别是预准备、准备、确认。预准备和准备阶段是保证所有正常节点按照相同的顺序执行所有有效的用户请求，而 BA*可以完成即时提议与确认。

王永革认为Algorand中的拜占庭协议过于复杂，实现成本过高，存在优化地空间。

王永革认为可以通过简单的方法达到相应的效果，假设在相同的网络环境下，就可以通过“多数票决：（majority vote）来达到同样的效果。

王永革称Algorand团队似乎也已经认识到一点了，在项目后来实践的过程中，Algorand并没有按照他们2017年文章提出的拜占庭协议进行。王永革表示这一点与Algorand的安全性无关，只是他给Algorand的一个建议。

参考资料：

《一文读懂 Algorand 算法，彻底消除区块链「不可能三角」》

《Another Look at ALGORAND》