图灵奖获得者 Sivio Micali 介绍 Algorand 区块链协议

雷锋网AI财经评论出版社：本文作者为邹传伟，博士。经济学博士，哈佛梅森学者，南湖金融服务合伙人，南湖互联网金融研究院常务副院长。荣获首届（2014）孙冶方金融创新奖。

2018 年 2 月，图灵奖获得者、麻省理工学院教授 Sivio Micali 筹集 400 万美元用于开发 Algorand 区块链协议，受到国内外媒体的广泛关注。 2017 年春天，作者有幸参加了由 Micali 教授和麻省理工学院媒体实验室数字货币项目负责人 Neha Narula 共同开设的共享公共账本课程。本课程主要是讲解 Algorand。 Algorand 的目标是构建一个低能耗、高速、民主化、可扩展且很少分叉的分布式账本。 Algorand 不引入激励措施或发行数字加密货币。

Algorand 代表了区块链底层技术发展的一个重要方向。本文对Algorand进行了简单的介绍，并与国内读者分享。 Algorand 涉及非常复杂的数学。作者尽量用最少的数学来介绍Algorand的核心思想（本文第四节主要涉及数学，跳过或不看都不影响对文章大意的理解）。对 Algorand 感兴趣的读者可以阅读 Algorand 上的工作论文（不是白皮书，最新版本的工作论文于 2017 年 5 月发布，在此处下载）。本文不构成对 Algorand 的商业评论。当然，作者祝 Micali 教授一切顺利。

一、Algorand 的开发背景

Algorand 是麻省理工学院机械工程与计算机科学系的 Silvio Micali 教授和合作者（主要是纽约大学石溪分校的陈静副教授） 2016 年提出的区块链协议。博士1982 年获得加州大学伯克利分校计算机科学博士学位，自 1983 年以来一直在麻省理工学院任教。他的研究领域包括密码学、零知识、伪随机数生成、安全协议和机制设计。

Micali 教授于 1993 年获得哥德尔奖（1993 年由欧洲理论计算学会 EATCS 和美国计算机学会基础理论专业组织 ACM SIGACT 于 1993 年共同创立，颁发给世界上最杰出的学术论文）理论计算领域），2004年获得密码学领域RSA奖（RSA是发明公私钥密码系统的三位科学家Rivest、Shamir和Adleman的姓氏缩写）比特币每十分钟产生一个区块，并获得图灵奖2012年（美国计算机协会ACM于1966年成立，颁发给对计算机行业做出重要贡献的个人，被誉为“计算机行业的诺贝尔奖”）。

Algorand 由算法（algorithm）和随机（random）两个词组成。顾名思义，它是一种基于随机算法的公共账本协议。 Algorand 解决了比特币区块链系统的几个核心缺陷。

首先，比特币区块链系统的工作量证明共识机制需要消耗大量的计算资源和能源。根据 Digiconomist 网站数据，截至 2018 年 1 月，每个比特币区块需要运行 1.18*1022 的哈希运算。考虑到哈希函数作为随机预言机的性质，比特币出块的过程相当于掷了一个 1.18*1022 面的骰子，直到掷出特定的面。比特币区块链系统一年的用电量相当于秘鲁全国的用电量，而且还在快速增长。这些巨大的计算量和功耗，除了比特币区块的产生，对人类社会几乎没有什么价值。

其次，比特币区块链系统的长期存在要求50%以上的计算资源掌握在诚实用户手中。否则，当他们的权力占上风时，恶意用户可能会篡改区块链。但随着市场的发展（中本聪不应该预见到），比特币区块链系统中的计算资源集中在几个“矿池”中。这构成了潜在的不稳定因素。 “矿池”的存在也使得比特币区块链系统偏离了其早期宣称的民主特征，形成了“矿工”和普通用户等不同类别的用户。从比特币历史上关于扩容和多次分叉的讨论不难看出，比特币区块链系统已经形成了高度中心化的社区结构。

第三，比特币区块链系统容易分叉。根据 Satoshi Nakamoto 的白皮书 [ Nakomoto, Satoshi, 2009，“比特币：点对点电子现金系统”。 ]，在一笔交易被记录在一个区块中并连接到区块链之后，需要等待6个区块才能更加确定该交易进入了比特币的公共账本，而不是在一个分叉上。由于比特币区块链系统平均每 10 分钟产生一个区块，因此一笔交易被记录在区块中并被确认大约需要一个小时。

第四，比特币区块链系统的扩展性比较差。例如，一个比特币区块的大小为 1M，大约可以容纳 2000 笔交易，因为平均每 10 分钟产生一个区块，而比特币每秒最多支持 6 笔交易； Clock 可以支持 193 笔交易，Visa 平均每秒可以支持 1667 笔交易[]。从这个意义上说，比特币是人类历史上投入产出最低的社会和技术实验之一。比特币闪电网络是目前备受关注的可扩展性问题的解决方案。

鉴于上述比特币区块链系统的不足，Algorand 旨在：

二、Algorand 的基本设置（一）用户和交易特征

Algorand 是一个公链系统。用户（或节点）加入 Algorand 无需提前申请，随时可以加入。 Algorand 对用户数量也没有限制。每个用户拥有多个公钥。每个公钥都是电子签名机制的一部分，即有一个对应的私钥。每个公钥对应一定数量的货币。每笔交易实际上是一个电子签名，将一定数量的货币从一个公钥转移到另一个，并用与前一个公钥对应的私钥进行加密。不难看出，Algorand 的这些设计与比特币的设计是一样的。

Algorand 要求系统中 2/3 的货币由诚实用户持有。诚实用户的含义是：他们的行为遵循相关的准则（主要是指拜占庭共识协议，见下文），并且可以完美地发送和接收消息。除了诚实用户是恶意用户外，恶意用户可以任意偏离相关准则。

对于恶意用户，Algorand 假设他们由可以发动强大攻击的“对手”控制，包括：

(二）区块链结构

在 Algorand 中，交易相关信息存储在一系列区块中。每个区块主要包括：1.上一个区块以来的交易信息；2.一个哈希指针，相当于所有之前区块中包含的信息的摘要或浓缩；3.当前“leader”电子签名 在“seed”参数之后（详见下文）。这样，这一系列区块通过这些哈希指针连接在一起，形成了区块链。如果一个区块的信息被“敌人”篡改，其将与后续区块中保存的哈希指针不匹配。这使得区块链难以被篡改。

Algorand 的上述设计与比特币区块链系统基本相同，但有一个关键区别。目前，Algorand 是一个纯粹的分布式账本协议，没有像比特币那样引入激励和发行数字加密货币。 Algorand 中用于交易的货币是外生的（可以是任何法定货币或数字加密货币），交易只影响不同用户之间的货币分配。在比特币区块链系统中，“矿工”构建的区块被公共账本接受后，他们将获得系统给予的一定数量。比特币作为奖励。

(三）网络通讯

与比特币区块链系统一样，Algorand 假设用户之间的通信采用“点对点谣言”模型（点对点八卦）：当用户传播消息时，接收消息的用户为第一次随机独立地选择他的一些“邻居”并将消息发送给“邻居”。当没有用户第一次收到消息时，消息的传播将终止。

Algorand 对网络通信的要求是：对于任何大于 95%（可达性）ρ 和消息存储大小参数 μ 的可达性参数，总是存在一个时间参数 λ（λ 只与 ρ 和 μ 有关），因此一个诚实用户发送的存储量为 μ 的消息，经过很长一段时间 λ 后，至少会被 ρ 个以上的诚实用户接收到。

(四）共识机制

在 Algorand 中，用户（不是所有用户，只有那些被系统随机选择为“验证者”的用户，详见下文）通过拜占庭协议（由 Micali 教授开发，称为 BA★）达成新区块的共识. BA★ 执行速度非常快。粗略地说，BA★每个循环有3个子步骤，每个循环后有1个/3或以上的概率可以达成共识。一旦“验证者”就一个新区块达成共识比特币每十分钟产生一个区块，超过一半的“验证者”将使用他们的私钥对该区块进行电子签名（相当于认证），该区块将开始在 Algorand 网络中传播。

BA★的一个重要特点是，在点对点网络通信下，BA★参与者是可替换的（player-replaceable）。也就是说，BA★ 每次循环的每个子步骤都可以由一个新的、独立随机选择的参与者执行。在这种情况下，BA★ 仍然可以正确高效地达成共识。假设有数百万用户，BA★每个周期的每个子步骤的参与者，可以完全不同，每批参与者无法确定下一批参与者是谁，因此不能串通。

(五）密码抽取（密码抽签）

加密彩票是 Algorand 的一项关键创新，也是其名称的由来。要点如下。首先，Algorand 创建并不断更新一个名为“种子”的独立参数。 “种子”的参数不仅不能被“对手”预测，也不能被操纵。

其次，在 BA★ 的每个周期中，Algorand 都会根据当前的“种子”参数（也称为“可验证随机函数”或可验证随机函数，见下文）构建并发布随机算法。该随机算法中的一个关键参数是用户的私钥，只有用户自己知道。

接下来，每个用户使用自己的私钥运行系统发布的随机算法，得到自己的凭证。凭证值满足一定条件的用户就是本轮的“验证者”。 “验证者”组装一个新区域 该块连同它自己的凭证一起发送出去。其中，在第一个子步骤中，凭证值最小的“验证者”（按字典排序，见下文）具有特殊地位，称为“领导者”。

最后，所有“验证者”根据“领导者”组装的新区块运行拜占庭协议BA★。在BA★的每个循环的每个子步骤中，选择的“验证者”都是不同的。这样可以有效防止验证权集中在某些用户手中，防止“敌对者”通过腐蚀这些用户来攻击区块链。

从上面的流程可以看出，

三、Algorand 的密码抽奖

密码抽签根据两条线索进行：一是选择“验证者”和“领导者”二是创建并不断完善“种子”参数。

(一）“验证者”和“领导者”的选择

假设在第r轮（可以理解为产生第r个块的时间段）一开始，“种子”参数为Qr-1（表示为一串长度为256的0和1） , PKr-k 是第 r-k 轮结束后系统中的活跃用户/公钥（活跃标志是一组至少一个交易），其中 k 称为回溯参数或安全参数。 Qr-1和PKr-k属于常识。

凭据的定义。对于PKr-k中的每个A用户i，在使用他的私钥对“种子”参数Qr-1（由函数SIGi表示）进行电子签名并输入哈希函数（由函数H:表示）后，得到自己的证书 H(SIGi(r,1,Qr-1)) （当函数 SIGi 有多个输入参数时，表示将这些参数简单串联后进行电子签名，下同）。哈希的性质函数确定现在：

凭证是长度为256的近乎随机的0和1字符串，不同用户几乎不可能拥有相同的凭证；

由凭证构造二进制小数0.H(SIGi(r,1,Qr-1))（即在小数点后写入凭证字符串）均匀分布在0和1之间。

(二）“种子”参数的更新

用Br表示拜占庭协议BA在回合结束后输出的区块。如果 Algorand 在本轮攻击中收到“敌人”，Br 可能为空，即不包含任何真实的交易记录（以符号表示）。例如，“敌对者”可能会破坏本轮的“领导者”，使其将两个不同的候选区块发送给诚实的“验证者”。考虑到这种情况，“种子”参数的更新过程是：

哈希函数的性质决定了Qr和Qr-1之间的关系几乎是随机的回溯参数或安全参数k保证了“对手”几乎不可能在r-k-1中预测Qr-1圆形的;否则会在r-k轮引入恶意用户（即进入PKr-k），影响第r轮“leader”和“validator”的选择。

四、Algorand 的拜占庭协议 BA★

拜占庭协议BA★相当于一个两阶段投票机制。在第一阶段，“验证者”对其接收到的候选块运行一个分级共识协议（控制通信成本，候选者的哈希摘要块实际使用），选择“验证者”共识最多的候选块。第二阶段，“验证者”对第一阶段选出的候选区块运行二元拜占庭协议（binary Byzantine agreement）。 ne 协议），即要么接受它，要么接受一个空块。需要强调的是，在每个阶段的每个子步骤中，Algorand 可能会使用完全不同的“验证器”。

为方便起见，假设如下：

(一）分级共识协议

步骤1.1：运行密码抽签程序，为这一步选举“leader”lr和“validator”。设 vi 为“验证者”i 收到的候选块，他知道该候选块来自“领导者”lr。

是的 3 个原因使 vir 不一定等于“领导者”lr 构造的候选块：

步骤1.2：“验证者”i将vi发送给其他用户（适用于“验证者”，下同）。

Step1.3：当且仅当“验证者”i在步骤1.2中收到某个x，如果次数超过2t+1（即#2i(x)≥2t+ 1），他将 x 发送给其他用户。

输出：“验证者”i根据以下规则输出（vI,gi）：

如果x存在使得#3i(x)≥2t+1，则vi=x,gi=2;

如果x存在使得#3i(x)≥t+1，则vi=x，gi=1；

否则vi=Ø，gi=1，其中Ø代表一个空块。

Micali教授证明分类共识协议{(vi,gi):i=1,2,L...n}的输出满足如下性质：

对于任何诚实的“验证者”i 和 j，|gi-gj|≤ 1;

对于任何诚实的“验证者”i和j，如果gi,gj>0，那么必然有vi=vj；

如果有 v 满足 v'1= v'2=K...=v'n=v，那么对于所有诚实的“验证者”i，vi=v，gi=2。

因此，分层共识协议的输出 { (vi,gi):i=1,2,L...n} 有两种可能的情况。

(二）二进制拜占庭协议

首先，根据分层共识协议 {(vi,gi):i=1,2,K...n} 的输出为每个诚实的“验证者”分配一个值：如果 gi=2，则 bi =0;否则，bi=1，。这些 bi 是二进制拜占庭协议的输入。对应前面的讨论，这里也有两种情况：

二进制拜占庭协议可能要经过很多个周期，计数器ri用来表示“验证者”i经过的周期数。开始时，ri 被赋值为 0。

步骤2.1：“验证者” i 发布 bi。

如果#1i(0)≥2t+1，那么“验证者”i设置bi=0，输出outi=0，停止执行协议（也可以认为他会一直发出bi= 0）;

如果#1i(1)@ >≥2t+1，那么“验证者”i设置bi=1；

否则，“验证者”i 设置 bi=0。

步骤2.2：“验证者” i 发布 bi。

如果#2i(1)≥2t+1，那么“验证者”i设置bi=1，输出outi=1，停止执行协议（也可以认为他永远是issue bi =1）;

如果#2i(0)≥2t+1，则“验证者”i设置bi=0；

else , "Verifier" i 设置 bi=1。

步骤2.3：“验证者”i发出bi和SIGi(Qr-1,rj)。

如果#3i(0)≥2t+1，那么“验证者”i设置bi=0；

如果#3i(1)≥2t+1，则"验证器"i"设置bi=1；

否则，使用 Si 表示向“验证者”i 发送消息的所有其他“验证者”的集合，定义

（lsb表示一个数字的二进制表示中最右边的数字），“验证者”i设置bi=c，ri加1。给定哈希函数，其实就是将bi赋值为0或1 随机且无需操作。

回到步骤2.1，Micali教授证明了在二元拜占庭协议中，每个诚实的“验证者”i可以以概率1停止并输出outi∈{0,1}，并且：

(三）拜占庭协议BA输出★

BA★的输出：对于诚实的“验证者”i，如果二进制拜占庭协议outi=0，则输出vi（即分层共识协议的输出）；否则，输出空块Ø。

Micali教授证明BA满足拜占庭协议的要求：

五、Algorand 的测试情况

进行了 MIT 计算机科学和人工智能实验室的 Algorand 模拟测试 [Gilad、Yossi、Rotem Hemo、Silvio Micali、Georgios Vlachos 和 Nickolai Zeldovich，2017 年，“Algorand：为加密货币扩展拜占庭协议”。本节引用的数据来自本文。]。他们在亚马逊云上使用 1000 个 EC2 虚拟机进行了测试，发现：

首先，Algorand 可以在 1 分钟内确认交易，并且交易的确认时间不会随着用户数的增加而发生太大变化。

其次，用户数固定为50000，测试没有相同块大小对吞吐量的影响（可以用生成块的平均时间来衡量）。可以看出，区块越大，构建区块的时间越长，但对拜占庭协议BA★的运行时间影响不大。

参考资料：

1.中本聪，Satoshi，2009 年，“比特币：点对点电子现金系统”

2.

3.

雷锋网版权文章，未经授权禁止转载。详情见转载说明。