什么是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，所有的用户都可以选择参与共识协议。

核心技术点与创新之处

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

该共识系统的特性如下：

1. 支持 permissionless 系统。每个用户都可以自行注册，不需要许可即可加入。设计成 permissionless 的协议，想要做成 permission 的系统也很容易，只需要加入一些相应节点即可，而反之则不可。（最近推出的 Co-Chain 即为 permission 版本的 Algorand）
2. 针对动态攻击者也是安全的。所谓动态攻击者在密码学中被严格定义的（下文有详细描述），如果只对静态攻击者安全的话，则说明安全性较低。
3. 拥有一个随机选择，不断变化的委员会。
4. 在系统时钟同步方面，不要求所有人拥有一个完全同步的时钟。系统的安全性可以在完全异步的环境下得到保障。
5. 可终止性，当所有的 message 延迟的上限已知，系统就可以保持应有的可终止性。在共识协议中，这也是最常用的可终止性 model。

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

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

拜占庭协议

拜占庭协议在计算机科学领域，特别是分布式计算中是一个非常经典的概念。自八、九十年代开始，便有许多经典的研究。无需使用生涩数学定义即可说明。拜占庭协议是一种通信协议，规定用户发布信息的内容和时间。当大多数用户是诚实的时候，不同的拜占庭协议对“大多数”的要求有所不同。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设成千分之一即可达到。此时攻击者可以针对其来攻击，使第二、三步用户的组成完全变成恶意。

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

共识协议的结构

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

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

总结

Algorand 共识协议提供了以下特性：

1. 系统的计算量很小，采用了纯粹的基于权益的证明机制
2. 不会产生分叉，保证了交易的即时确认的特性
3. 对于动态攻击者来说，系统也是安全的，拥有非常强大的安全假设模型