深度解析共识算法系列之二 | Hacker Speaker 回顾 #09

共识算法（Consensus Algorithm)是保证区块链可信度和安全性的重要技术。目前，有多种主流的共识算法，如工作量证明（Proof of Work, PoW）、权益证明（Proof of Stake, PoS）等等，各有其优、缺点与适用对象。在区块链技术领域，不可小觑共识算法的重要地位。

我们与Algorand合作，共同为大家带来的硬核分享“深度解析共识算法”系列活动目前已进行到第二讲。在本期分享中，Algorand基金会首席科学家陈婧博士，为诸位Hacker讲解Algorand共识算法。

在本篇回顾中，你将读到关于本次分享的全部核心内容和在线答疑部分。预计阅读时间30分钟。脑洞猫建议各位将这份干货十足的硬核分享回顾添加收藏，以便温故知新哦！

1. 什么是Algorand算法

Algorand一方面指的是共识算法，另一方面指基于该共识算法开发出的网络体系。我们经常说，Algorand是一个不一样的公链，因为它是从底向上，基于严格的数学分析设计的。在讲Algorand之前，我们先简单地回顾什么是区块链，即通常所说的分布式公共账本。

所谓公共账本的结构非常简单，每个数据块中打包了一些交易。所有的数据块会以唯一的顺序链接起来，即区块链。对于区块链或分布式账本的要求，首先需要对所有人可读、可写。这里的所有人，并不单指同一个公司或组织内部，而指互联网上的所有人。同时，我们也要求区块链数据对所有人不可更改。如果我们只要求以上这些性质，那么即使一个集中式的数据库也可以做到。比如一个中心化数据库中的管理员，其通过client model从外部接受用户需求，然后通过响应需求对数据库进行读写。如果该数据库有足够高的安全性能，那也是不可被更改的。但是，中心化的数据库常会成为网络空间的巨大目标，同时也很容易变成系统性能方面的瓶颈。因为管理员需要响应所有的需求，所有的congestion都会在这里发生。所以，区分分布式账本的另一特点即去中心化。所有的用户都可以用这种方式对系统进行读写。

比如，可以在区块链上进行公证的存证，现在也有一些法律上的案例。这也是区块链中一个比较新的应用。另外，区块链可以把混乱的数据做成有序的数据结构，可以使金融交易和支付简便化。同时，还可以在系统中建立起虚拟、可信的第三方。即，不通过任何一个第三方实体，即可以在两点之间完成交易

。

这些多样的应用都非常有前景，让人感到乐观。但在实现方面必须回到区块链的具体技术，我们必须面对所谓区块链中公开的秘密。我们对于区块链的期待和现实技术还有一段距离。无论是可扩展性，还是分布式管理，或是安全性方面，我们对区块链的商业化要求与实际技术还有差距，尤其是在大规模商业应用面前。

当然，之前也有很多如何设计和实现区块链技术的分享，比如时常提到的工作量证明（PoW），或者基于代理的权益证明（DPoS），还有基于托管的权益证明（BPoS），这些都是已被讨论很多的技术了，我们这里不做展开。但也不难发现，有很多系统不得不产生比较集中的super node，或money pool这样的集中实体。比如Bonded PoS要求参与系统的用户，把tokens和stake在系统中锁定很长的时间，如果用户在系统中作恶，那这些stake就会被没收。这样的系统对于有很多stake的用户会产生偏向，因为更多的stake可以被锁定，而小用户没有办法提供被长时间锁定的stake。

Algorand基于的共识协议是不同的，即纯粹的权益证明。特性如下：

1. 系统不需要惩罚或没收用户的stake来防止作恶。因为通过严格的数学证明，即使用户想要作恶，他成功的概率也是非常小的，也不会对系统造成伤害，降低了作恶动机。

2. 系统不要求用户锁定token，拥有的所有stake都可以立即花出去。每个用户都可以随时注册、参与。

3. 安全性假设使诚实的用户掌握token和stake，因此系统就会是安全的。即基于工作量证明，整个系统中的算力掌握在诚实的用户手中。

4. 所有的token都有同样的voting power，所有的用户都可以选择参与共识协议。

2. 核心技术点与创新之处

大体来说，Algorand基于不断变化的委员会生成新的区块链。每个委员会都是随机形成，每一个被选中的用户的工作要求也很简单，只要发出简短的message即可。所以每个用户的参与成本很低。

该共识系统的特性如下：

1. 支持permissionless系统。每个用户都可以自行注册，不需要许可即可加入。设计成permissionless的协议，想要做成permission的系统也很容易，只需要加入一些相应节点即可，而反之则不可。

2. 针对动态攻击者也是安全的。所谓动态攻击者在密码中被严格定义。如果只对静态攻击者安全的话，说明安全性较低。

3. 随机选择、不断变化的委员会上面已经提到。

4. 在同步方面，不要求所有人拥有同一个时钟。

5. 系统的安全性在完全异步的环境下得到保障。

6. 进展性，当所有的message延迟的上限已知，系统即有新的进展。在共识协议中，这也是最常用的进展性model。

Algorand具体的数据结构是一个接一个的生成，是真正的链状结构。很多区块链系统在数据结构上并不是链状，而是树状。比如Bitcoin，很多矿工会自己挖矿，产生各自独立的区块。只有通过时间的区分，比较短的才不会进一步增长，大家才会得知哪一条分支会成为主链。而在Algorand中不存在这样的分支。

这种结构的好处在于：没有所谓的软分叉，也没有挖矿工作量证明。在所有交易上链的那一刻，即被最终确认，无需等待。马上可以基于交易进行下一步，对于金融来说非常有利。在没有工作证明的时候，任何一个小用户即可交易，不需要加入矿池或购买硬件，使用家庭电脑就可以参与系统。

3. 拜占庭协议

拜占庭协议在计算机科学领域，特别是分布式计算中是一个非常经典的概念。自八、九十年代开始，便有许多经典的研究。无需使用生涩数学定义即可说明。拜占庭协议是一种通信协议，规定用户发布信息的内容和时间。当大多数用户是诚实的时候，不同的拜占庭协议对“大多数”的要求有所不同。Algorand要求这个比例是三分之二，这也是大多数异步协议所要求的。

拜占庭协议的特点：

1. 共识性，即起初每个人看到这个系统的状态不同，认为下一个区块的样子即v1、2、3。在通过这个通讯之后，所有的诚实用户都会输入同一个值，即对下一个区块内容达成一致。

2. 一致性，该特点时常被忽略但是非常重要。该性质排除了边角情况，要求系统状态在被诚实节点看到时是一致的，按拜占庭协议要求，不会要求节点改变观点，输出的仍是起始的值。结果是，拜占庭协议不会浪费系统资源，强迫用户已达成的共识，另外系统要不断有新的进展。所谓的边角协议，即所有人什么都不做，只输出空的区块，这样的情况不满足拜占庭协议，因为不满足一致性。

拜占庭协议乍听之下听起来对生成区块链已足够，那为何不直接选择一个共识协议要求所有用户运行呢。所以这里我就想和大家讨论一下，为何单纯的拜占庭协议是不够的。

因为经典的拜占庭协议在区块链的应用中，面临了几个较大的挑战：

1. 计算和通讯效率。在理论方面，被设计出的拜占庭协议在理论计算方面是指多项式时间或多项式等级的通信。这种等级的通讯在理论方面被认为是高效的，但在实践中并不足。比如一个拜占庭协议在计算效率是N的立方，在几百万用户的系统中是完全无法被应用的。

2. 除此之外，该协议不能被直接应用在区块链系统中。因为传统的协议环境是固定和封闭的，通常假设用户是确定的，身份也是已知的。这样两个假设在互联网公链的环境中是不能成立的。即，用户数量随时在改变，并且因为网络攻击，一个物理上的用户可以控制多个公钥和虚拟身份，以此加入系统，传统的拜占庭协议无法处理。

Algorand做出改进：

效率：我们的共识协议非常高效，通讯量和计算量都非常低。用户在每一步发送简短信息即可，即便面对恶意用户，系统也可以完成共识协议执行。但即便是速度很快、通讯容量很低的协议，我们仍然认为在有10亿用户的大体量系统中应用这样的协议时，仍然很慢。在通讯方面，网络很难支撑。

为了解决这个问题，目前已有很多提议。一个简单的想法：我们从所有的用户中，公开、随机选择一组用户即可，公开选择无需额外通信。比如，我们可以用HASH函数来进行选择。比如我们可以把每个用户的高度作为输入，那么HASH函数就会随机输出某个字符串。然后我们按从小到大的顺序排列该字符串，就可以在系统中随机选出一定数量的用户。这时让这些用户参与共识协议，通讯量就会小很多。

而问题在于，作为公开的选择，不仅诚实的用户可以得知结果，攻击者也能知道。这些攻击者就可以提前攻击被选择的用户，使这些用户无法参与发送消息，击溃系统。为了处理掉这样的攻击模式，这样的技术需要额外的假设，比如攻击者需要很长的时间才能破坏一个用户。但这样的假设基于弱攻击者的前提，这样的系统能够抗衡的攻击就相应较弱。这不是我们想要的情况，与其假设，我们需要去处理攻击者。

动态攻击者即攻击者可以随时攻击任何一个用户，而不是在系统开始之前。这些用户的攻击也不需要耗费时间。另外攻击者可以完全控制、协调被攻击的用户。完全控制即用户发送的信息可以被攻击者控制。攻击者不光可以攻击共识协议，也可以攻击底层的通信网络，例如破坏数据中心，把某个用户的网络进行分割。这是一种非常强的攻击模型。对其的唯一限制在于，不可以伪造用户的数字签名，他们无法破解现代密码学中的签名、证书等。现代密码学是现代电子商务等领域基于的基础，是保证线上交易安全的底线。

另外，对于用户的时钟没有要求（除了要求速度必须一致以外）。

为了保证安全，除了拜占庭协议之外的另一个新技术，即基于密码的自选择。相对于我们提到的公开选择，这里的关键词是自选择，即每个用户单独、秘密地选中自己参与共识协议。做法是通过自己的彩票系统，在该系统中无法作弊，如果未被选中，是无法说服别人相信自己被选择，而被选择时可以提供简单的、被接受的证明。在现实世界中的彩票系统的运作，需要某个机构印刷好彩票，确定中奖比例，用户购买彩票后，如果中奖即可兑奖，没有中奖也无法伪造。为什么无法我们无法让用户在家中生成、打印彩票呢？因为恶意用户可以自行生成多张彩票，直到中奖。而这是不被允许的，系统中的诚实的大多数用户即不存在。而基于现代密码学的设计，在区块链世界中，我们可以让用户有效地自行生成彩票系统，也使得用户无法作弊。

好处在于，用户在选择时无需通讯。这样可以减低系统通讯量，也可以保证系统的安全性。因为用户无需发送消息告知选中结果，因此攻击者也无法看到消息。所以对攻击者来说，无法定点攻击，唯一可以做的是在系统中随机选择用户。在这种情况下，概率论可以保证攻击者在攻击时，攻击到被选择用户的概率会很小。

具体来说，对于自选择的实现需要唯一性签名，另一点是可以被验证的随机函数。这两点关系紧密，对于随机性签名的实现（VRF+HASH函数）使得通常认为这两点是同一方面。

数字签名大家并不陌生，简单来说，每个用户生产一个公钥和私钥对，用户使用私钥生成签名，而所有人可以用公钥来验证其有效性。而唯一性签名在此基础上有一个很好的性质，对于同一个消息，该用户本身没有随机性，只能生成唯一签名。

HASH函数的建模基于随机数据库，即任意长度的数字串会被映射成256或512位的字符串。要求是HASH函数的输出是很难找到真正被隐藏的输入，同时也很难找到两个不同的字串有同样的HASH值。

简单来说，系统中用户生成彩票的过程，就是对于系统中某一个特定的量，首先使用特定的签名，然后用HASH函数来hash。然后将这个hash，即字符串，可以被解释为0-1之间的小数，该小数与预先设定的概率进行比较，如果小于，则用户被选中，签名会被当做自己的系统中的彩票证明。签名会和拜占庭协议中的投票信息一起发送。

这个选择的概率是我们想要的。首先签名是确定的，用户不可以作弊，签名是唯一确定的东西。而HASH函数把唯一确定的签名映射到随机的字符串。当我们把随机的字符串前面加上小数点，可以解释其为0-1之间的随机数。对于一个均匀分布的随机数，小于某一个值的概率，就是这个值的本身。

所以通过比较随机字符串和选择的阈值大小，可以保证用户被选中到委员会的概率是我们想要的。比如从系统中一百万用户中选出1000个委员，只需要将p设成千分之一即可达到。此时攻击者可以针对其来攻击，使第二、三步用户的组成完全变成恶意。

我们将这个特性称为用户的可替代性。即共识协议中的各个步骤中都有被选出的委员会，但其之间的成员组成毫无关系。我们的共识协议好在无需参与者维护任何内部状态。第一步中是随机选中的委员会，第二步中是独立的。其用户数量等是不同的，也没有共享的数据变量。攻击者在攻击第一步委员会后，对之后束手无策，仍是随机攻击，可以保证后面的安全。

4. 共识协议的结构

1. 被选出的随机用户会随机选择区块。每一步选择和每一个用户的token数量是成正比的，即纯粹基于权益的证明。

2. 共识协议基于每个人的权益数来参与。

这就是共识协议的基本结构。接下来我们提一下网络攻击。大多数拜占庭协议不考虑这一点，但Algorand的共识协议在网络攻击的情况下，区块链也不会分叉。区块链在攻击下还是会产生区块。

总结：

系统的计算量很小，真正基于权益的纯粹证明。
从来不会分叉，保证交易的最终性。
对于动态攻击者来说，系统也是安全的，拥有较高的安全性。

我们在基于共识协议的网络之后，我们的新进展：我们的共识协议和系统在去年6月正式上线，运行顺畅。接下来，我们在此基础上，搭建了许多新的特性，去年11月做了第二版升级更新。我们加入了标准的资产发行，即任何用户都可以在上面发布自己的资产。另外，原子交易可以让用户将交易打包成组进行，即所有发行的资产可以一部完成，不需要托管、延时等，效率和安全性都得到保障。第三，我们在整个区块链的首层加入了简单的智能合约操作，即在第一层就可以进行金融交易，而不影响系统速度。这个合约是我们精心挑选的指令集，可以支持足够的应用，但不影响系统的总运行效率。所有的特性都可以享受整个共识性的效益。

下一步的路线图上，我们已经完成了许多新技术的设计，完成了原型验证，在接下来的更新中将会逐步加入。比如Token Bridge会增强Algorand和其它链的互联性。我们会支持Co-Chain，任何人在基于Algorand主链情况下，可以建立自己的区块链系统。可以在自己的私链和共生链上有权限控制，用主链增强安全性。Vault和Fast Catch-up也可以增强安全性。Vault系统可以使新用户再加入时，无需从头下载，在短时间内就可以享受到最新的系统状态。我们还会有自己的聚合签名系统。同时，Algorand还在推动BOS系统聚合签名的标准化。还有未公开、研发中的新技术，还请大家继续关注。

精选问答

Q: 老师能给agreement和consistency一个严格的定义吗？

A: 拜占庭协议的基本模型要求，用户有私人输入和输出值，在这个过程中，有诚实的和恶意的用户。agreement的定义要求，无论是何种用户，有着怎样的运作，对其都有很强的要求，所有用户的输入，在输出时都是一致的，是严格的数学定义。对于consistency来说，如果所有用户在输入时都是一致的，那么协议结束的时候用户的输出值等于输入值。这个相等关系是consistency要确保的，而agreement是没有的。

Q: 同样speed的时钟是作用在协议的什么位置呢？如果速率不同会造成什么影响呢？

A: 时钟的速度对于安全性没有影响。所以速度或延迟如何，都不会影响系统的安全性。时钟的速度会影响区块生成的速度，如果快慢不同，那么区块生成的速度和慢的用户持平，这个只会影响速度，不会影响安全性。

Q:老师能讲一下唯一性签名是怎么实现的吗？如何和token结合来做抽签呢？

A: 基于椭圆曲线。普通的数字签名过程随机，用户生成随机字符串，和需要签的消息和自己的私钥生成签名。而唯一性签名不会用到任何随机字符串，可以保证自己的唯一性。token的数量控制每个用户被选中的概率，唯一性签名和HASH函数配合生成唯一确定和不可预测的字符串，而这个字符串和用token控制的随机概率的比较，就可以确定用户是否被选中。像我们刚才提到的，用作自选择的标准和过程，这个公式左边是自选择本身的操作，右边的概率由token的数量来决定。