图灵奖得主Sivio Micali的Algorand区块链协议简介

本文作者：温晓桦

2018-02-19 17:31

导语：本月，图灵奖得主、MIT教授Sivio Micali筹资开发Algorand区块链协议。Algorand代表了区块链底层技术发展的一个方向。

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

2018年2月，图灵奖得主、MIT教授Sivio Micali募集400万美元开发Algorand区块链协议一事受到了国内外媒体的普遍关注。2017年春天，笔者有幸在MIT选修了Micali教授和MIT媒体实验室数字货币计划负责人Neha Narula合开的《共享公共账本》（Shared Public Ledger）课程。这门课主要就是讲解Algorand。Algorand的目标是建立一个低能耗、高速度、民主化、可拓展性好而且几乎不会出现分叉的分布式账本。Algorand没有引入激励机制或发行数字加密货币。

Algorand代表了区块链底层技术发展的一个重要方向。本文对Algorand做一个简单介绍，分享给国内读者。Algorand涉及非常复杂的数学，笔者力图用最少的数学介绍Algorand最核心的想法（涉及数学的主要是本文第三、四节，略过不读不会影响对文章大意的理解）。对Algorand感兴趣的读者可以阅读关于Algorand的工作论文（不是白皮书，最新版工作论文于2017年5月发布，下载地址是https://arxiv.org/abs/1607.01341）。本文不构成对Algorand的商业评论。当然，笔者衷心祝愿Micali教授能取得成功。

一、Algorand的发展背景

Algorand是MIT机械工程与计算机科学系Silvio Micali教授与合作者（主要是纽约大学石溪分校陈静副教授）于2016年提出的一个区块链协议。Micali教授为意大利裔美国人，1982年获加州大学伯克利分校计算机科学博士，1983年起在MIT任教。他的研究领域包括密码学、零知识（zero knowledge）、伪随机数生成、安全协议（secure protocol）和机制设计。

Micali教授1993年获哥德尔奖（由欧洲理论计算机学会EATCS与美国计算机学会基础理论专业组织ACM SIGACT于1993年共同设立，颁发给理论计算机领域最杰出的学术论文），2004年获密码学领域的RSA奖（RSA是三位发明公钥-私钥密码系统的科学家Rivest、Shamir和Adleman的姓氏缩写），2012年获图灵奖（由计算机协会ACM于1966年设立，奖励给对计算机事业作出重要贡献的个人，有“计算机界诺贝尔奖”之称）。

Algorand由algorithm（算法）和random（随机）两个词合成，顾名思义，就是基于随机算法的公共账本协议（public ledger）。Algorand针对比特币区块链系统的几个核心缺陷进行了改进。

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

第二，比特币区块链系统要长期存续，要求50%以上的计算资源掌握在诚实用户的手中。否则，恶意用户在力量占优时可能篡改区块链。但随着市场演变（中本聪应该没有预见到这种情况），比特币区块链系统中的计算资源集中在少数几个“矿池”中。这就构成了一个潜在的不稳定因素。“矿池”的存在也使比特币区块链系统偏离了其早期宣称的民主特征，形成了“矿工”和普通使用者这样不同阶层的使用者。从比特币历史上关于扩容的讨论以及多次分叉不难看出，比特币区块链系统已经形成了中心化程度很高的社区结构。

第三，比特币区块链系统容易出现分叉。根据中本聪的白皮书[ Nakomoto, Satoshi, 2009, “Bitcoin: A Peer-to-Peer Electronic Cash System”. ]，当一笔交易被记入一个区块并接入区块链后，需要再等6个区块才能比较肯定这笔交易进入比特币的公共账本，而非在某一个分叉上。因为比特币区块链系统平均每10分钟才能产生一个区块，一笔交易从被记入区块到被确认需要1个小时左右时间。

第四，比特币区块链系统的可拓展性比较差。比如，一个比特币区块的大小为1M，大约能容纳2000笔左右交易，因为平均每10分钟产生一个区块，比特币最高支持每秒钟6笔交易；相比而言，Paypal平均每秒钟能支持193笔交易，Visa平均每秒钟能支持1667笔交易[ http://www.altcointoday.com/bitcoin-ethereum-vs-visa-paypal-transactions-per-second/ ]。从这个意义上讲，比特币是人类历史上投入产出比最低的社会和技术试验之一。对可拓展性问题，比特币闪电网络是目前很受关注的一个解决方案。

鉴于比特币区块链系统的上述缺陷，Algorand的目标是：

1.能耗低，不管系统中有多用户，大约每1500名用户中只有1名会被系统挑中执行长达几秒钟的计算。
2.民主化，不会出现类似比特币区块链系统的“矿工”群体。
3.出现分叉的概率低于一兆分之一（即10-18）。假设Algorand中平均每分钟产生一个区块（后文会给出有关测试数据），这个概率意味着平均每190万年出现一次分叉。
4.可拓展性好。

二、Algorand的基本设置

（一）用户和交易特征

Algorand是一个公有链系统。用户（或者节点）加入Algorand不需要事先申请，可以随时加入。Algorand对用户数量也没有任何限制。每个用户持有多个公钥。每个公钥均是一个电子签名机制的一部分，也就是有一个与之对应的私钥。每个公钥对应着一定数量的货币。每笔交易实际上是一个电子签名，该电子签名将一定数量的货币从某一个公钥转移给另一个公钥，并用前一个公钥对应的私钥进行加密。不难看出，Algorand的这些设计，与比特币是一样的。

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

对恶意用户，Algorand假设他们由一个“敌对者”（adversary）控制。“敌对者”能发起强大攻击，包括：

“敌对者”可以在任何时候瞬间地腐化任何他选中的用户，使其成为恶意用户（哪怕该用户之前是诚实用户）。
“敌对者”完全控制并且完美协调所有恶意用户。可以理解为，恶意用户的行为（包括发送和接收消息）完全由“敌对者”代理。
“敌对者”控制所有信息发送，但必须满足一点：诚实用户发出的消息能在一定时间内（该时间只与信息的存储大小有关）抵达95%的诚实用户。然而，“敌对者”几乎不可能伪造诚实用户的电子签名或者干涉诚实用户之间的通讯。

（二）区块链结构

在Algorand中，与交易有关的信息均存储在一系列区块中。每个区块主要包括：1.从上一个区块以来的交易信息；2.一个哈希指针，相当于对所有前序区块所含信息的一个摘要或浓缩；3.当期“领导者”电子签名后的“种子”参数（细节见后文）。这样，这一系列区块通过这些哈希指针连接在一起，构成了区块链。如果某一区块的信息被“敌对者”篡改，其与后序区块中保存的哈希指针就会出现不匹配。这就使得区块链难以被篡改。

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

（三）网络通讯

与比特币区块链系统一样，Algorand假设用户之间的通讯采取“点对点传言”模式（peer-to-peer gossip）：当某一用户传播一条消息后，第一次收到这条消息的用户随机并且独立地选择他的一些“邻居”，并将消息传给“邻居”们。当没有用户是第一次收到这条消息时，这条消息的传播就终止了。

Algorand对网络通讯的要求是：对任意大于95%的可及性参数（reachability）ρ和消息的存储大小参数μ，总存在一个时间参数λ（λ只与ρ和μ有关），使得一个诚实用户发出的存储大小为μ的消息，在经过λ长时间后，至少被超过ρ的诚实用户接收。

（四）共识机制

Algorand中，用户（不是全部用户，仅指被系统随机挑中作为“验证者”的用户，详见下文）通过一个拜占庭协议（由Micali教授开发，称为BA★）对新区块达成共识。BA★执行起来非常快。大致言之，BA★每次循环有3个子步骤，在每次循环后均有1/3以上的概率能达成共识。一旦“验证者”对某一个新区块达成共识，超过一半的“验证者”再用自己的私钥对该区块进行电子签名（相当于认证），该区块就开始在Algorand网络中传播。

BA★的一个重要特征是：在点对点网络通讯下，BA★的参与者可更换（player-replaceable）。也就是，BA★每次循环的每一个子步骤均可由全新的、独立随机选择的参与者来执行。在这种情况下，BA★仍能正确、有效地达成共识。假设有上百万的用户，BA★每次循环的每一个子步骤的参与者可以完全不一样，而且每一批参与者都无法确定下一批参与者是谁，从而无法串谋。

（五）密码抽签（cryptographic sortition）

密码抽签是Algorand的关键创新，也是其得名的由来，其要点如下。首先，Algorand创建并不断更新一个独立参数，称为“种子”。“种子”参数不仅不可能被“敌对者”预测，也不能被其操纵。

其次，在BA★每次循环中，Algorand基于当前 “种子”参数构建并公布一个随机算法（也被称为“可验证的随机函数”或verifiable random functions，见下文）。该随机算法中的一个关键参数是用户的私钥，这个私钥只有用户本人才知道。

接着，每个用户使用自己的私钥运行系统公布的随机算法，得到自己的凭证（credential）。凭证值满足一定条件的用户就是这一轮的“验证者”（verifiers）。“验证者”组装一个新区块并连同自己的凭证一起对外发出。其中，在第一个子步骤中凭证值最小（按字典方面排序，见下）的那个“验证者”的地位比较特殊，称为“领导者”。

最后，所有“验证者”基于“领导者”组装的新区块运行拜占庭协议BA★。在BA★的每次循环中的每一个子步骤中，被选中的“验证者”都是不同的。这样能有效防止验证权力集中在某些用户手中，避免“敌对者”通过腐化这些用户来攻击区块链。

从上述过程可以看出，

第一，“验证者”在秘密情况下获知自己被选中，但他们只有公布凭证才能证明自己的“验证者”资格。尽管“敌对者”可以瞬间腐化身份公开的“验证者”，但已不能篡改或撤回他们已经对外发出的消息。
第二，所有“验证者”公布自己的凭证并进行比较后，才能确定谁是“领导者”，也就是“领导者”可以视为由公共选举产生。
第三，随机算法的性质决定了，事先很难判断谁将被选为“验证者”。因此，“验证者”的选择过程很难被操纵或预测。
第四，尽管“敌对者”有可能事先安插一些交易来影响当前公共账本，但因为“种子”参数的存在，他仍然不可能通过影响“验证者”（特别是其中的“领导者”）的选择来攻击Algorand。接下来，对密码抽签和拜占庭协议BA★做一个相对技术化的介绍。

三、Algorand的密码抽签

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

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

假设在第r轮（可以理解为产生第r个区块的时间段）开始时，“种子”参数为Q^r-1（表现为一个由0和1组成的长度为256的字符串），PK^r-k是第r-k轮结束后系统中活跃的用户/公钥（活跃的标志是至少参与过一笔交易）的集合，其中k被称为回溯参数或安全参数。Q^r-1和PK^r-k属于公共知识（common knowledge）。

凭证的定义。对每一个PK^r-k中的用户i，他使用自己的私钥对“种子”参数Q^r-1进行电子签名后（用函数SIGi来表示）并输入哈希函数（用函数H_:来表示），得到自己的凭证H(SIG_i(r,1,Q^r-1))(函数SIG_i有多个输入参数时，表示将这些参数简单串联后再进行电子签名，下同）。哈希函数的性质决定了：

凭证是一个近乎随机的、由0和1组成的长度为256的字符串，并且不同用户的凭证几乎不可能相同；

由凭证构建的2进制小数0.H(SIG_i(r,1,Q^r-1))（也就是将凭证字符串写到小数点后）在0和1之间均匀分布。

“潜在领导者”的选择。对0和1之间的一个数，0.H(SIG_i(r,1,Q^r-1))≤p发生的概率为p，称所有满足此条件的用户为“潜在领导者”（也是这一步的“验证者”）。p使得以1-10^-18的概率，在所有“潜在领导者”中，至少有一个是诚实的。
“领导者”的选择。在所有“潜在领导者”中，存在一个用户l^r，其凭证按字典排序最小。也就是，对所有0.H(SIG_i(r,1,Q^r-1))≤p的用户i，均有H(SIG_l^r(r,1,Q^r-1))≤H(SIG_i(r,1,Q^r-1))。用户l^r就是第r轮的“领导者”。
“验证者”的选择。第r轮第s步（s>1）的“验证者”的产生程序与上文类似。在这一步中，每一个PK^r-k中的用户i使用自己的私钥对“种子”参数Q^r-1进行电子签名后并输入哈希函数，得到自己的凭证H(SIG_i(r,1,Q^r-1))。对0和1之间的一个数p^r，满足0.H(SIG_i(r,1,Q^r-1))≤p^r的用户就构成这一步的“验证者”。

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

用B^r表示第轮结束后，拜占庭协议BA★输出的区块。如果Algorand在第轮受到了“敌对者”攻击，B^r可能是空的，也就是不含有任何真实交易记录（用符号来表示）。比如，“敌对者”可能腐化了这一轮的“领导者”，使其将两个不同的候选区块发给诚实的“验证者”。考虑到这个情况，“种子”参数的更新过程是：

Q^r=H(SIG_lr(Q^r-1，r)),如果B^r不是空区块
=H(Q^r-1，r）,如果B^r是空区块

哈希函数的性质决定了，Q^r和Q^r-1之间的关系近乎随机的。回溯参数或安全参数k则保证了，“敌对者”在第r^-k-1轮几乎不可能预测到Q^r-1；否则，他将在第r-k轮引入恶意用户（也就是进入PK^r-k），从而能影响第r轮“领导者”和“验证者”的选择。

四、Algorand的拜占庭协议BA★

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

以下为叙述方便，假设：

1.系统处在第r轮；
2.每一个子步骤都选出n名“验证者”，其中恶意“验证者”不超过t，并且n≥3t+1（也就是诚实“验证者”占比在2/3以上）。另外，引入计数函数#^s_i(v)表示在第s步，“验证者”i收到的消息v的次数（来自同一发送人的只能算1次）。

（一）分级共识协议

步骤1.1：运行密码抽签程序，选出“领导者”l^r和这一步的“验证者”。用vi表示“验证者”i收到的并且他认识是来自“领导者”l^r的候选区块。

有3个原因使得v_i^r不一定等于“领导者”l^r构建的候选区块：

第一，“验证者”i辨认“领导者”的方法是从他收到的所有“验证者”凭证中找出按字典排序最小者。但因为网络通讯原因，“领导者”l^r发出的信息可能没有到达“验证者”i处。
第二，“领导者”l^r可能被“敌对者”腐化，对不同“验证者”发出不同的候选区块。
第三，“验证者”i本身可能是恶意的。

步骤1.2：“验证者”i将v_i发给其他用户（这对其他“验证者”都适用，下同）。

步骤1.3：当且仅当“验证者”i在步骤1.2中收到的某一个的x次数超过了2t+1次（即#²_i(x)≥2t+1），他将x发给其他用户。

输出：“验证者”i按以下规则输出(v_I,g_i)：

如果存在x使得#³_i(x)≥2t+1，则v_i=x,g_i=2；
如果x存在使得#³_i(x)≥t+1，则v_i=x,g_i=1；
否则v_i=Ø，g_i=1，其中Ø代表空区块。

Micali教授证明了，分级共识协议的输出{(v_i,g_i):i=1,2,L……n}满足下列性质：

对任意诚实“验证者”i和j，|g_i-g_j|≤1；
对任意诚实“验证者”i和j，如果gi,gj>0，那么必有v_i=v_j；
如果存在v使得有v'₁=v'₂=K……=v'_n=v，那么对所有的诚实“验证者”i，均有v_i=v,g_i=2。

因此，分级共识协议的输出{(v_i,g_i):i=1,2,L……n}存在两种可能的情形。

情形一：如果存在诚实“验证者”i，使得,g_i=2，那么对任意其他“验证者”j，必有g_j≥1,v_j=v_i。此时所有诚实“验证者”输出的候选区块是一样的。当然，如果一开始的“验证者”收到的候选区块都是v，那么最后一批“验证者”输出的也将都是v。
情形二：对所有的诚实“验证者”i，g_i≤1，并且他们输出的候选区块不一定相同。

（二）二元拜占庭协议

首先，基于分级共识协议的输出{(v_i,g_i):i=1,2,K……n}对每个诚实“验证者”赋值：如果g_i=2，那么b_i=0；否则b_i=1，。这些b_i就是二元拜占庭协议的输入。对应着前面的讨论，此处也存在两种情形：

情形一：存在诚实“验证者”i，使得b_i=0。
情形二：对所有诚实“验证者”i，均有b_i=1。

二元拜占庭协议可能经过多次循环，用计数器r_i表示“验证者”i经历的循环的次数。开始时，r_i赋值为0。

步骤2.1：“验证者”i发出b_i。

如果#¹_i(0)≥2t+1，那么“验证者”i设定b_i=0，输出out_i=0，并停止执行协议（也可以认为他以后将一直发出b_i=0）；

如果#¹_i(1)≥2t+1，那么“验证者”i设定b_i=1；

否则，“验证者”i设定b_i=0。

步骤2.2：“验证者”i发出b_i。

如果#²_i(1)≥2t+1，那么“验证者”i设定b_i=1，输出out_i=1，并停止执行协议（也可以认为他以后将一直发出b_i=1）；

如果#²_i(0)≥2t+1，那么“验证者”i设定b_i=0；

否则，“验证者”i设定b_i=1。

步骤2.3：“验证者”i发出b_i和SIG_i(Q^r-1,r_j)。

如果#³_i(0)≥2t+1，那么“验证者”i设定b_i=0；

如果#³_i(1)≥2t+1，那么“验证者”i设定b_i=1；

否则，用S_i表示所有给“验证者”i发送消息的其他“验证者”集合，定义图灵奖得主Sivio Micali的Algorand区块链协议简介（lsb表示一个数的二进制表述中的最右边位置上的数字），“验证者”i设定b_i=c，并且ri的计数往上调1位。鉴于哈希函数的性质，这实际上是将bi随机地、不被操纵地赋值为0或1。

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

（共识性）存在out_i∈{0,1}，使得对任意诚实“验证者”i，均有out_i=out；
（一致性）如果存在b∈{0,1}，使得对任意诚实“验证者”i，均有b_i=b，那么out=b。

（三）拜占庭协议BA★的输出

BA★的输出：对诚实“验证者”i，如果二元拜占庭协议的输出out_i=0，则输出v_i（即分级共识协议的输出）；否则，输出空区块Ø。

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

1. （共识性）最后一批诚实“验证者”输出的区块是相同的；
2. （一致性）如果一开始的“验证者”收到的候选区块都是v，那么BA★的最终输出也是v。

五、Algorand的测试情况

MIT计算机科学和人工智能实验室对Algorand进行了模拟测试[Gilad, Yossi, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich, 2017, “Algorand: Scaling Byzantine Agreements for Cryptocurrencies”. 本节引用的图均来自这篇文章。]。他们的测试在亚马逊云上进行，使用了1000台EC2虚拟机，发现：

第一，Algorand能在1分钟内确认交易，而且确认交易的时间随着用户数量的增加，变化不大。

图灵奖得主Sivio Micali的Algorand区块链协议简介