2018年明星级项目Algorand简介
2018年明星级项目Algorand简介
6 人赞了文章
这个项目的白皮书及其生涩难懂，而且它还有两个白皮书，一个2017年的，一个2018年的。两个白皮书有一些地方意思相同但是表达方法又完全不同，理解起来简直是让人抓耳挠腮。我来来回回看了俩遍，因为不是学这个出身的，仅能靠著上下句理解把白皮书大概翻译一下。有错误的地方请大牛出来指证，谢谢。
什么是Algorand
Algorand是一款新型的付款协议，换句话说，就是和比特币一样的分散式记账本。在我们继续介绍之前，先介绍一下什么是拜占庭将军问题：
拜占庭将军问题是Leslie Lamport（2013年的图灵讲得主）用来为描述分散式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。这个例子大意是这样的：
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？
拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，已经假定了信道是没有问题的.
单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：
先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。
再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻， 通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。
叛徒发送前后不一致的进攻提议，被称为「拜占庭错误」，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。
中本聪在比特币中创造性的引入了「工作量证明（POW: Proof of Work）」来解决这个问题，有兴趣可进一步阅读工作量证明。通过工作量证明就增加了发送信息的成本，降低节点发送消息速率，这样就以保证在一个时间只有一个节点(或是很少)在进行广播，同时在广播时会附上自己的签名。
这个过程就像一位将军A在向其他的将军（B、C、D…）发起一个进攻提议一样，将军B、C、D…看到将军A签过名的进攻提议书，如果是诚实的将军就会立刻同意进攻提议，而不会发起自己新的进攻提议。
以上就是比特币网路中是单个区块（账本）达成共识的方法（取得一致性）。理解了单个区块取得一致性的方法，那么整个区块链（总账本）如果达成一致也好理解。我们稍微把将军问题改一下：假设攻下一个城堡需要多次的进攻，每次进攻的提议必须基于之前最多次数的胜利进攻下提出的（只有这样敌方已有损失最大，我方进攻胜利的可能性就更大），这样约定之后，将军A在收到进攻提议时，就会检查一下这个提议是不是基于最多的胜利提出的，如果不是（基于最多的胜利）将军A就不会同意这样的提议，如果是的，将军A就会把这次提议记下来。这就是比特币网路最长链选择。
Algorand不使用POW机制，而是选择了新的方向 – RPOS（Random Proof of Stake）。使用这种方式的前提是必须二分之三的网路用户是不作恶的。如果超过的这个范围，则拜占庭将军问题本身将无解。这一点其实也是这个项目被有些人诟病，但是通过巧妙的设计，Algorand将可以在网路被严重恶意控制下仍旧自主无错运行。我会把2017年的白皮书和2018年的白皮书结合分析。
Algorand项目优点
产生区块时间短
区块产生时间在大家都是良性用户时，只需要两步。如果有任何恶性用户企图篡改信息，则需走完五步。即使是这样，产生一个区块的时间是固定的（几分钟）。在这里，所有用户不需要同步他们的时间，他们只需要在自己规定的时间内完成工作并保证每个用户的时间流逝的速度是一致的即可（在纽约的一秒钟和在日本的一秒钟长度一样）。
反分叉
协议制定没有两个良性用户可以同意两个不同的消息。因此只能有一个消息为真实消息，如果有人试图双花攻击（详见下）。则理论上他可以开一个新的区块里面包含错误的信息并把上一个区块的广播时间延到无限长，但是受制于第一条的限制，每个区块产生时间为固定并通过之后会介绍的五步方法，任何的恶意分叉都会被干掉。
双花攻击：
双花攻击（double spend attack），在介绍51%攻击的时候出现过这个词语。光看中文名可能会因为汉语的多重含义而理解错，但英文名就很明显的表达出意思了。双花攻击就是一笔钱花了两次，也可以称之为双重支付攻击。
快速从分叉中恢复
如果强行出现分叉，新的分叉将会被五步方法干掉，然后全网把分叉浪费掉的时间归零，从新开始。
Algorand如何做到这些特点的
随机预言机与电子签名
黑盒随机预言机来进行256位的公/私钥生成。每个公/私钥对应一个可防选择性秘文攻击的电子签名。这是如何做到的呢？根据我的翻译（误）应该是这样的：每个公/私匙钥对应其禅达的消息（m），其电子签名只有一堆位元组中的一串位元组。即使有个恶意的产生出新的公/私钥，他也无法通过选择性秘文攻击猜到真正的电子签名的位元组是什么。
设立临时简单假设
这个假设包括总用户的数量为3x恶性用户数量+1。换句话说，就是良性用户无论在什么状况都比恶性用户对于维护拜占庭将军协议稳定性上多一个人。（N=3t+1，t为恶性用户）如果超过了维护拜占庭将军协议稳定性的话，我们定其为「临界值」。
每一个用户i会对协议在一开始的时候有一个输入为vi。一堆用户的vi组成了「大V」（误）。所有用户的职责为同一大V中的一个数字。
如果有人恶意攻击并生生新的公/私钥，则这个恶意的公/私钥生成的「vi」将不在大V里。（⊥ ∈/ V）。我们给他它起个名字叫「恶意值」。
协议中会有一个一直保持自动（无互动）和随机的函数字元串R。作为选择随机用户的指标。
从有许可权系统到无许可权系统的过度
有许可权即所谓的超级节点，工作证明等方式给验证者施以门槛。无许可权即进入协议的用户不需要被验证。他们可好可坏。即使当恶意用户可以在任何时间立即协调控制任何他想控制的用户（前提是2/3的用户是善意的）；恶意用户可以完美的协调大量被控制的用户。在这种条件下，恶意用户也不能进行恶意分叉（双花）。这种过度意味著会使大量用户聚集到Algorand的协议下，因为相对容易并没有入门门槛。
协议交流
这个部分稍微生涩一些。我们如何解决协议的不可能三角（Impossible Trinity）：安全性，可拓展性与分布性呢，Algorand的五步法如下：
第一步：价值提案
情况1：在一个固定时间段内，用户i收到的协议上反馈数量超过临界值数量的恶意值时，系统自判用户i提议vi（坏）。
情况2：反之，用户i提议v（好）。
第二步：过滤
在情况1的前提下，用户i指认其领导者L，系统自判用户i软提议v，我们可以看到，对于情况1，这是一个恶意用户，但是系统会鉴别其恶意值并在恶意值爆表的前提下，为这个恶意用户对领导者L投赞成票（在这里我们认定领导者的决策是善意的），我们在这里可以把vi看成是恶意票，v为善意票。
情况2：反之，用户i提议v（好）。
第三步：认证
如果用户i发现整个协议中投善意票的用户超过了临界值，则用户i对其软投票进行认证，认证后，我们可以认为这个投票即为有效票。如果善意用户并没超过临界值，则软投票报废，系统继续提取随机用户进行再投票（即用户的可替代性，这个替代可以是在这五步内的任何一个环节）。
第四步：完成环节1
在用户i认证本轮投票后，他的下一轮的投票即为v，这等于协议判定这个用户在下一轮的投票中自带良性身份（v）。反之，则自带恶人身份。
第五步：完成环节2
如果用户i在本轮投票后未被下一轮选中，则他的身份变成待定良性身份（va）。反之，则自带待定恶人身份。
其他
区块的形成和广播同步。这样用户i可以在看不到区块的前提下进行软投票。因为软投票的速度比区块生成要快，因此，在生成真正的区块前，超出临界值数量的良性用户应该早已完成了验证，保证了区块形成的速度。
