下载掌阅APP，畅读海量书库
立即打开
Algorand是麻省理工学院教授希尔维奥·米卡利（Silvio Micali）于2016年提出的一个区块链协议，主要是为了解决比特币区块链采用的PoW共识协议存在的算力浪费、扩展性弱、易分叉、确认时间长等不足，并且宣称能够解决区块链项目存在的“不可能三角”问题。Algorand由algorithm和random两个词合成，顾名思义是基于随机算法的公共账本协议。它整合了PoS、可验证随机函数（VRF）、拜占庭协议，实现高TPS的同时保持去中心化与隐私性。
Algorand的主要性质有以下几个方面。
（1）所需计算量很少，无论系统中有多少用户，每1500个用户只有一个人需要执行几秒钟的计算。
（2）新区块在10分钟内产生，并且事实上不会因分叉而回滚。产生区块的时间小于Λ+12.4λ。Λ是以点对点散播（peer-to-peer gossip）方式传播一个区块的必要时间，λ是传播1500个200B长度的消息所需要的时间。在分布式系统中Λ是固有的延时，网络速度是区块产生的限制因素。
（3）区块链分叉概率低于十亿分之一，新区块中的交易可以马上被接受。
（4）所有权力属于用户，没有外部实体（如比特币中的矿工）来决定哪些交易会被接受。
Algorand有以下几个技术特点。
（1）新的快速拜占庭共识算法。Algorand通过一种新的、基于消息传输的二进制拜占庭共识协议（Byzantine Agreement，BA）来产生新的区块，这种算法称为BA*。
（2）密码学抽签（Cryptographic Sortition）。Algorand在所有用户中选取一个子集参与到算法BA*。为了避免中心化，每一个新的区块都会由另一群验证者（Selected Verififiers，SV）来执行BA*并达成共识。其中领导者（相当于特殊的验证者）负责提议新区块，其余验证者对领导者的提议达成共识。Algorand用密码学保证验证者是随机的。
（3）种子。 Q r Algorand根据上个区块B r- 1 来选取B r 的验证者。攻击方就可以在之前的区块通过选择某些交易，来操纵下一个区块领导者的选择。这样即使攻击方只掌握少数的代币/代表，也可以控制系统。为此，就需要引入随机种子，通过某种方式构造并更新种子Q r ，且能保证这个种子不可预测，并且不会被攻击方影响，Algorand将基于这个种子进行秘密密码学选举，选择参与下一个区块生成的验证者。
（4）秘密密码学选举（Secret Cryptographic Sortition）和秘密资格证书（Secret Credentials）。假如选举是公开的，那么攻击方可以根据B r-1 和Q r-1 来计算出验证者。假设Algorand的攻击方能够在任何时刻攻击任何用户，所以攻击方就会在它们生成B r 前攻击所有验证者，完全控制新区块的生成。为此，验证者需要秘密地知道它们被选上了，并且能够生成证书对外证明自己的身份。当一个用户秘密地得知自己被选为领导者，它会秘密地组装它提议的新区块，然后附上身份证明并传播它。尽管此时攻击方知道谁是领导者，但是新区块的消息已经散播出去，再攻击它也无济于事。
（5）用户可替换（Player Replaceability）。当领导者发布新区块后，即使它被攻击也无所谓，因为它的任务已经完成。但是对于其他验证者，执行BA*需要若干步，在这若干步中，它们可能会被攻击，并且验证者事实上只占全用户的一小部分，所以可以假设，攻击者是可能将它们全部攻陷的。幸运的是，BA*是用户可替换的，这意味着即使协议的每一步都由全新的验证者SV集合执行，依然能够达成共识。因此，在用户数很大的情况下，可能每一步的SV集合间没有交集，以保证协议的共识安全。
Algorand的选举过程如下。
Algorand的第r个区块可以表示为B r =( r,PAY r ,Q r ,H ( B r- 1 ) )，其中PAY r 表示第r个区块内的交易集合。假如用户i能够满足H ( SIG i ( r,1,Q r- 1 ) )≤ p，那么它是一个潜在的领导者。由于种子Q能够保证随机且不被操纵，所以哈希结果是完全随机的256bit值。H前面的小数点使它变为一个0到1的值，所以对于一个用户而言，它是潜在领导者的概率是p。p的选取要使概率意义上基本至少有一个潜在领导者是诚实的。由于只有i自己掌握自己的私钥，故别人无从得知它是不是一个潜在领导者。但是它可以通过发送自己的签名SIG i ( r,1,Q r- 1 )来证明自己是第r轮的潜在领导者。验证者SV的选举也是类似的，用户i成为BA*的第s步验证者SV需要满足H ( SIG i ( r,s,Q r- 1 ) )≤ p'。同样地，只有它自己知道自己被选举上，并且可以出示证明——SIG i ( r ， s ， Q r- 1 )。证明通常与消息m r ， s i 一起发送，让下一轮的认证人能够确认这个消息是合法的。p'的选取需要满足：①BA*的每一步都有2/3以上的诚实节点。②每一轮只有一个区块有阈值个数以上的签名。③BA*的最后一步有阈值以上个数的诚实节点签署新区块。
随机选举认证人的第一个难题是如何保证结果是随机的。Algorand利用哈希输出是随机的特点，让某些用户签名的哈希满足条件，成为潜在认证人。第二个难题是防范认证人被攻击。由于只有用户掌握自己的私钥，在它发布签名，宣布自己身份前，他人无从得知。而当它宣布后，由于它提议的区块或提议的消息已经发出，即使被攻击，也不会影响系统的安全。