Zhuang's Diary

言之有物，持之以恒

Posted on Edited on

摘自
https://twitter.com/dominic_w/status/932047902905634816

Dominic Williams 18 Nov 2017 DFINITY

I spent much of 2014 repurposing BFT (Byzantine Fault Tolerant) consensus protocols from traditional distributed computing for the decentralized setting. My aim was to make faster blockchains.

2014年，Dominic Williams 花了很多时间将传统分布式计算的BFT（拜占庭容错）共识协议重新用于分布式环境。目标是制作更快的区块链。

Such consensus protocols proceed through rounds of message passing and “decide” on an output value, providing instant consistency rather than converging on a value like a traditional blockchain

这种共识协议通过消息传递和”决定”产生输出值，提供即时的一致性，而不是像传统区块链一样收敛。

The protocols come in three main flavors: Synchronous, Partially Synchronous and Asynchronous consensus. The first two flavors make assumptions about how fast participants in the protocol can exchange messages over the network.

（共识）协议有三种主要形式：同步，部分同步和异步共识。前两种形式假设协议的参与者可以通过网络交换消息的速度非常快。

When network asynchrony is sufficiently high - e.g. when a DDoS attack slows down message passing - Synchronous protocols become unsafe and fail to output a value, and Partially Synchronous protocols remain safe but also fail to output a value.

当网络异步性足够高的时候 - 例如当DDoS攻击减缓了消息的传递时 - 同步协议变得不安全且无法输出值，此时，部分同步协议仍然是安全的，但也无法输出值。

Currently both Cosmos and Algorand involve Partially Synchronous consensus protocols and thus are vulnerable to “DDoS Flatline” attacks that could cause them to output null blocks.

目前，Cosmos和Algorand都涉及部分同步共识协议，因此容易受到”DDoS”攻击，可能导致它们输出空块。

During 2014 I worked exclusively on repurposing leader-free Asynchronous consensus protocols that don’t make timing assumptions and thus aren’t vulnerable to DDoS Flatline attacks. These are slower but provide a better fit for the decentralized setting.

2014年，我专门致力于重新调整无领导人的异步共识协议，这些协议不做时序假设，因此不易受到DDos攻击。这会使速度变慢，但更适合分布式环境。

Asynchronous consensus protocols are necessarily probabilistic in nature. To drive participants to a decision on an output, they must produce random numbers and use them to direct message passing.

异步共识协议本质上是概率性的。为了促使参与者对输出做出决定，他们必须产生随机数并使用它们指导消息传递。

The first Asynchronous consensus protocol that generated random numbers using cryptography in a practical way was described in 2000 by Cachin, Klaus & Shoup http://gridsec.org/docs/abba.pdf

使用加密技术，以工程方式生成随机数的第一个异步共识协议是在2000年由Cachin，Klaus＆Shoup发布的。 [http://gridsec.org/docs/abba.pdf](http://gridsec.org /docs/abba.pdf）

Unfortunately, the RSA threshold signature scheme they used to generate random numbers doesn’t have a companion distributed key generation (DKG) protocol and, depending on a trusted dealer, is unsuitable for decentralized networks.

不幸的是，他们用来生成随机数的RSA门限签名方案没有配套的分布式密钥生成（DKG）协议，并且必须依赖可信的分发人，所以不适合分布式网络。

In early 2014 I found a “unique deterministic” threshold signature scheme with a DKG https://hal.inria.fr/hal-00983149/document & was constructing new protocols derived from https://hal.archives-ouvertes.fr/hal-01176110/document

2014年初，我发现了一个DKG的”唯一确定性”的门限签名方案https://hal.inria.fr/hal-00983149/document，努力构建从https://hal.archives-ouvertes.fr/hal-01176110/document派生的新协议。

As 2014 closed however, I concluded that eventually-consistent blockchain-like protocols driven by random numbers created using cryptography could be constructed that were far superior in the decentralized setting.

然而，截至2014年，我的结论是，在分布式环境中，可以构建出最终一致的区块链式协议，这种协议由使用密码技术创建的随机数驱动。

Readers may have observed Proof-of-Work drives eventual agreement using random number production (random “puzzle solutions”/hashes are used for leader selection). Clearly by moving the expense of Sybil resistance elsewhere, random numbers can be generated more efficiently.

读者可能已经观察到使用随机数生产（随机”谜题解决方案”/ 散列用于领导者选择）的工作证明驱动器最终协议。很显然，通过将Sybil阻力转移到别处，可以更有效地生成随机数。

Unique deterministic signature schemes can only produce a single signature (which is a big number) given some input message and key pair (= unmanipulability and verifiability) and signatures are random numbers or they would be predictable and the schemes thus insecure.

独特的确定性签名方案只能产生一个签名（一个很大的数字），给定一些输入消息和密钥对（= 不可处理性和可验证性），签名是随机数，或者它们是可预测的，因此此方案不安全。

Trivially, if everyone in the network has an unforgeable key pair (e.g. created by PoS) they could create a random “priority” number by signing the round/block height. If nodes only forward the block containing the highest priority number seen, voila, you have a blockchain.

如果网络中的每个人都有一个不可伪造的密钥对（例如由PoS创建的），他们可以通过签署轮数/块高度来创建一个具有”优先级”的随机数。如果节点只转发包含所看到的最高优先级数的块，瞧，你成功创建了一个区块链。

This is too simple for various reasons (it would be a selfish miner’s dream!!), but I developed many different schemes that generate or apply cryptographic randomness in the decentralized setting. Generally, I only talk about schemes DFINITY will use in the nearest future.

由于各种原因，这太简单了（这将是一个自私的矿工的梦想!!），但我开发了许多不同的方案，在分布式环境中产生或应用密码随机性。通常我只谈论DFINITY将在不久的将来使用的方案。

By early 2015 DFINITY research was using “Threshold Relay” to generate randomness. On the advice of Dan Boneh, I started using BLS as the unique deterministic threshold signature scheme, and Benn Lynn (the “L” in BLS) works full time on DFINITY

到2015年初，DFINITY的研究使用”阈值继电器”来产生随机性。根据Dan Boneh的建议，我开始使用BLS作为唯一的确定性门限签名方案，而Benn Lynn（BLS中的”L”）全职工作于DFINITY。

Between then and now, DFINITY team members Timo Hanke (AsicBoost) and Mahnush Movahedi (Yale postdoc) have worked on this and derivative protocols, including “Probabilistic Slot Consensus”. The security properties and performance are stunning

至此之后，DFINITY团队成员Timo Hanke（AsicBoost）和Mahnush Movahedi（耶鲁博士后）一直致力于这一衍生协议，包括”概率性时隙共识”。安全属性和性能令人惊叹。

It turned out we could design blockchain protocols that are 1. far faster than those using traditional consensus, 2. scale to any number of participants as they should and 3. continue to make progress during asynchrony.

事实证明，我们设计区块链协议，1.比使用传统共识的区块链协议速度快得多; 2.参与者数量可以任意规模扩展; 3.在不同步时继续取得进展。

In its pursuit of unbounded capacity, DFINITY protocols rely upon the unmanipulable, unpredictable and highly fault tolerant production of random numbers by Threshold Relay. Powered by perfect randomness, DFINITY plans to change IT.

为了追求无限容量，DFINITY协议依靠阈值中继产生随机数，这些随机数是难以执行的，不可预测的和高度容错的。凭借完美的随机性，DFINITY计划使用它。

Back to the Q of whether Algorand’s “cryptographic sortition” is a big invention. Sounds fishy to me! What about Satoshi’s Proof-of-Work? Doesn’t he use cryptographically calculated random puzzle solutions to decide which new blocks are valid and what their priorities are?

回到Algorand的”密码分类”是否是一个重大发明的问题。听起来很腥！那么工作证明呢？他不使用密码计算的随机谜题解决方案来决定哪些新块是有效的，他们的优先级是什么？

But anyway, since Algorand is both much slower and less secure than Threshold Relay and PSC I don’t worry myself too much about it, notwithstanding Miscali’s MIT patent attorneys will have tried to be as broad as possible.

但无论如何，因为Algorand比Threshold Relay和PSC慢得多而且不太安全，所以我不用担心自己太多了，尽管Miscali的MIT专利律师会尽可能广泛地尝试。

Aside: given the Algorand patent situation, their claim to be the first truly “democratic ledger” is as ridiculous as Tezos claiming a “A new digital commonwealth” then redirecting investor funds back to themselves.

除此之外：鉴于Algorand的专利情况，他们声称自己是第一个真正的”民主分类账”，这是荒谬的，因为Tezos宣称”一个新的数字联邦”将投资者资金重新导回自己。

To wrap up, all theoretical work starts with important inputs. I think I was the first to apply cryptography in the ways described, but I drew inspiration from traditional asynchronous consensus algorithms and Nakamoto/PoW

总而言之，所有的理论工作都从重要的投入开始。我认为我是第一个以所描述的方式应用密码学的人，但我是从传统的异步共识算法和Nakamoto / PoW中取得的灵感。

Finally, I will make the claim that unless something better emerges, decentralization is going to be driven by random numbers generated by applied cryptography. Currently Threshold Relay and PSC are state of the art

最后，本人声称，除非有更好的选择出现，分布式将由应用密码学产生的随机数驱动。目前阈值继电器和PSC是最先进的。

Our foundational Threshold Relay protocol has probabilistic fault tolerance e.g.

  • Network 10,000 nodes. 7,000 are correct. 3,000 are faulty
  • Group size 400, threshold 201
  • In this network, probability some group contains >=200 faulty nodes, such that system stalls, is 10e-17

我们的基础门限中继协议具有概率容错能力，例如

  • 网络10,000个节点。 7,000是正确的。 3,000是错误的；
  • 集群规模400，门槛201；
  • 在这个网络中，某个集群包含 > = 200 个故障节点的概率（如系统失速）为10e-17

Posted on Edited on

here is algorand网址链接

PoW的安全性

基于PoW的区块链假定矿工拥有生成下一个区块所需的大部分计算能力。但是，工作证明已将权力集中在少数采矿池中。在比特币中，实际上只有三个这样的矿池控制区块链。对于任何实体而言，这种权力集中对于渴望分权的系统是不可接受的，并且很可能是非常危险的。

Bonded PoS的安全性

在基于Bonded PoS的区块链中，每个用户都可能将自己的部分资金置于危险境地。那些这样做的人有权根据他们的赌注选择一个新的区块。原则上，如果他们发现行为不端，他们可能会失去他们的赌注，如果他们主张通过行为失误赚更多的钱，这可能不是很有威慑力。但是，一个普通用户只能负担得起的一小部分资金。因此，这个系统可能会成为富有的不诚实的人的牺牲品，这些个人通过大量的资金来控制区块链。

DPoS的安全性

在基于DPoS的区块链中，生成区块的权力在很长的时间间隔内被提供给一小部分公认的用户群。这种方法可能比工作量证明的成本更低，但无可否认的是相当集中！在这里，安全依赖于这个小组中大多数人的诚实，但任何一小部分用户都是攻击者的明显目标。

安全在Algorand

如果系统中的大部分资金由诚实用户所有，Algorand将保证安全工作。请注意，我们并不是谈论一些特殊用户拥有的大部分资金，而是所有用户拥有的资金。此外，Algorand的用户不需要将任何一小部分资金投入赌注。用户的钱始终留在她的手中，随时准备用尽自己的希望。

高效且可扩展

Algorand因为它在两个阶段产生一个新的块，每一个都完美地缩放。
阶段1：随机选择一个用户并提出一个新的区块。
阶段2：随机选择一小部分用户来验证并同意该区块。

Algorand不能被审查

两阶段中，用户按照他们在系统中的金额成比例地选择。它可能不包含在由不诚实用户提出的区块中，但只要其提议者是诚实的，它就会进入新的区块。因此，进入Algorand区块链所需的交易费用也非常低。这允许在平等条件下处理宏观和微观支付。

灵活性是成功的关键。

Algorand通过其标志性的建议和约定机制产生一个新的区块。在很高的层次上，Algorand秘密并即时召集一小群用户，他们的加密和安全选择能够公平地代表所有用户的社区（由他们在系统中的持股量加权）。这个代表性的委员会就新的区块达成协议，但事实上，它可以用来就其他问题达成一致。例如，改变议定书或修改货币政策。

我们应该认识到，在任何复杂的系统中改变都是必要的。传统的加密货币是静态的，任何“改变方向”都需要一个硬分叉，从而导致社区分裂。从长远来看，分散会削弱社区和任何货币的效用。

传统的加密货币没有内置的安全机制来达成协议。因此，关于变革的辩论是非常结构化的，无论达成任何形式的协议，都必须在链条外达成。因此，人们总是怀疑任何结论的正确性。

相比之下，Algorand使社区和协议得以发展。Algorand以其有效和安全的拜占庭协议为中心。经过辩论后，在区块链上发布了一项拟议更改，并使用Algorand的共识协议，社群投票接受或拒绝该提案。如果获得批准，建议的更改将立即生效。

在Algorand，这种协议并不是通过智能合同来实施的。相反，它直接内置于协议的核心。

相关文章链接：

可验证随机函数VRF之Algorand共识算法

Posted on Edited on

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

论文发表In Proceedings of the 26th ACM Symposium on Operating Systems Principles (SOSP), Shanghai, China, October 2017.：

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

1. Algorand的目标是：

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

2. Algorand算法假设

  1. 网络中诚实节点的数目始终占优。
  2. 节点可以自由地随时加入网络，而不需要申请。网络中每个节点通过一个公钥地址(同时也是钱包地址)表示，对于新加入的节点地址，只有被网络中其他节点转账成功(即钱包余额大于0)后，才可以参与到网络中的区块共识。
  3. 攻击者也是动态变化的(诚实节点随时可能变为攻击者)。

3. 用户和交易特征

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

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

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

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

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

4. 网络通讯

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

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

5. 密码抽签（cryptographic sortition）

密码抽签是Algorand的关键创新，也是其得名的由来，其要点如下：

首先，Algorand创建并不断更新一个独立参数，称为“种子”。“种子”参数不仅不可能被“敌对者”预测，也不能被其操纵。

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

接着，每个用户使用自己的私钥运行系统公布的随机算法，得到自己的凭证(credential)。凭证值满足一定条件的用户就是这一轮的verifiers。verifiers组装一个新区块并连同自己的凭证一起对外发出。其中，在第一个子步骤中凭证值最小的那个verifier的地位比较特殊，称为leader。

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

6. 共识机制

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

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

7. 可能的攻击：

  1. 尽管可以通过对上一个区块的哈希计算来确定构建下一个区块的leader节点和verifier节点，但是由于哈希函数自身的性质，攻击节点只需要在区块中添加一些微小的改动就可以很大影响下一个区块的leader节点的选择，从而破坏leader／verifier的随机性。为保证完全随机，在区块中引入block quantity，Qr(r为第r个块)，一个区块的Qr值只有在当前区块的leader在整个网络中被揭晓时才能最终确认，从而使攻击者无法事先攻击。

  2. 即使leader／verifier的选择是完全随机的，攻击者也有可能在leader／verifier被揭晓的同时，马上攻击这些节点，从而控制leader/verifier。为解决这个问题，采用的方案是设计多个潜在的leader，并且每个潜在leader都独立完成区块的构建，然后每个潜在leader都将自己的认证信息，构建的区块一起发送到网络中，通过共识算法选定真正的leader。由于在真正leader的身份在被揭晓之前，网络已经完成了区块数据的广播，即使攻击者攻陷了真正的leader也无法改变区块的数据。

  3. 算法中，区块生成都需要经过若干步骤，如果在算法执行过程中verifier节点被攻击，比如网络被断开，可能造成算法无法持续执行下去，从而造成整个区块无法确认，整个网络被停滞。而且，也无法要求每个节点都7x24在线，始终为整个网络进行服务。因此设计算法支持player-replaceable，从而使任何节点都可以随时被其他节点接管。

8. 具体算法

8.1. 选出verifier和leader

  1. 系统创建并不断更新一个独立参数，称为“种子”,记为Q ^{r-1} 。第r轮的种子的参数是256位长度的字符串，入参是第r-k轮结束后活跃用户的公钥集合，记为PK^{r-k}。k被称为回溯参数或安全参数，比如=1，表示上一轮结束后的用户集合。上面2个参数属于公共知识。
  2. 基于当前 “种子”构建并公布一个随机算法，称为可验证的随机函数(verifiable random functions)。该随机算法中的一个关键参数是用户的私钥，这个私钥只有用户本人才知道。
  3. 每个用户使用自己的私钥对“种子”进行签名，用函数SIGi来表示，用它作为参数，运行系统公布的随机算法，用函数H()来表示，得到自己的凭证(credential)= H(SIGi(r,1,Q^{r-1}))(函数SIGi有多个输入参数时，表示将这些参数简单串联后再进行电子签名)。
    3.1. 凭证是一个近乎随机的、由0和1组成的长度为256的字符串，并且不同用户的凭证几乎不可能相同；
    3.2. 由凭证构建的2进制小数0.H(SIGi(r,1,Q^{r-1}))，也就是将凭证字符串写到小数点后在0和1之间均匀分布。
  4. 凭证值满足一定条件的用户就是这一轮的验证者verifiers。
    4.1. 条件是：对0和1之间的一个数，0.H(SIGi(r,1,Q^{r-1}))≤p发生的概率为p，称所有满足此条件的用户为verifiers。
    4.2. 有1-10^{-18}的概率保证在所有verifiers中，至少有一个是诚实的。
  5. verifiers组装一个新区块并连同自己的凭证一起对外发出。第r轮第s步(s>1)的verifier的产生程序与上文类似。其中，在第一个子步骤中凭证值最小(按字典方面排序)的那个verifier的地位比较特殊，称为leader。
  6. 所有verifiers基于leader组装的新区块运行拜占庭协议BA。
  7. 在BA的每次循环中的每一个子步骤中，被选中的“验证者”都是不同的。这样能有效防止验证权力集中在某些用户手中，避免“敌对者”通过腐化这些用户来攻击区块链。

8.2. 种子seed的更新

用Br表示第轮结束后，拜占庭协议BA输出的区块。

“种子”的更新过程是：
Q^r =H(SIGlr(Q^{r-1}，r)), 如果B^r不是空区块。
Q^r =H(Q^{r-1}，r）, 如果B^r是空区块。

如果Algorand在第r轮受到了“敌对者”攻击，B^r可能是空的。

8.3. Algorand的BFT实现，即BA

拜占庭协议BA相当于一个两阶段的投票机制。

  • 第一阶段，verifiers对其收到的候选区块(为控制通讯成本，实际上用的是候选区块的哈希摘要)运行分级共识协议(graded consensus), 选出verifiers共识最多的候选区块。
  • 第二阶段，verifiers对第一阶段选出的候选区块，运行二元拜占庭协议(binary Byzantine Agreement)，即要么接受它，要么接受空区块。需要强调的，在每一阶段中的每一个子步骤，Algorand可能使用完全不同的verifiers。

以下为叙述方便，假设：

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

3.1. 第一阶段：分级共识协议

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

vir不一定等于“领导者”lr构建的候选区块：

  • “验证者” i辨认 “领导者” 的方法是从他收到的所有“验证者”凭证中找出按字典排序最小者。但因为网络通讯原因，“领导者”lr发出的信息可能没有到达“验证者”i处。
  • “领导者”lr正好被“敌对者”腐化，对不同“验证者”发出不同的候选区块。
  • “验证者”i本身可能是恶意的。
  1. “验证者”i将收到的vi广播给其他用户。广播正确的vi代表他告诉其他验证者他同意该vi。
  2. 当且仅当“验证者”i在步骤2中收到消息x的次数超过了2t+1次（即 2i(x)≥2t+1），他将消息x发给其他用户。“验证者”i按以下规则输出(vi,gi)：
1
2
3
4
如果存在x使得#3i(x)≥2t+1，则, 
vi=x, gi=2；//2轮都投票成功 如果x存在使得#3i(x)≥t+1，则, 
vi=x, gi=1；//只有1轮投票成功 否则, 
vi=Ø, gi=1，其中Ø代表空区块。
含义是：
  • 如果存在诚实“验证者”i，使得,gi=2，那么对任意其他“验证者”j，必有gj≥1,vj=vi。此时所有诚实“验证者”输出的候选区块是一样的。当然，如果一开始的“验证者”收到的候选区块都是v，那么最后一批“验证者”输出的也将都是v。
  • 对所有的诚实“验证者”i，gi≤1，并且他们输出的候选区块不一定相同。

3.2. 第二阶段：二元拜占庭协议

基于分级共识协议的输出{(vi,gi):i=1,2,K……n}对每个诚实“验证者”赋值：

1
2
如果gi=2，那么bi=0；
其他情况，bi=1。
这些bi就是二元拜占庭协议的输入。
  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. 第二步“验证者”i发出bi。
    • 如果#2i(1)≥2t+1，那么“验证者”i设定bi=1，输出outi=1，并停止执行协议（也可以认为他以后将一直发出bi=1）；
    • 如果#2i(0)≥2t+1，那么“验证者”i设定bi=0；否则，“验证者”i设定bi=1。
  3. 第三步“验证者”i发出bi和SIGi(Qr-1,rj)。
    • 如果#3i(0)≥2t+1，那么“验证者”i设定bi=0；
    • 如果#3i(1)≥2t+1，那么“验证者”i设定bi=1；
    • 否则，用Si表示所有给“验证者”i发送消息的其他“验证者”集合。

结论

  • algorand已经成功实施了1000个虚机节点，模拟了500,000用户数量。
  • algorand的TPS性能是比特币的125倍，按照论文中给出的数据，每小时可以共识的交易是750M字节每小时，计算一下(按照每笔交易长度100字节计算)：750 1024 1024/60/60/100=2184.5 TPS，考虑到实际环境的运行，估计可以达到1000TPS左右。