可验证随机函数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左右。