Algofans | Algorand爱好者

Algorand 论文解读 (上)

AlgofansAlgofans 2019-05-06 126 次 收藏0

Algorand是图灵奖获得者Silvio Micali主导研发的一种加密货币方案。该方案通过密码学抽签算法实现了拜占庭共识算法的大规模扩展,从而适用于公链数字货币体系。同传统加密货币共识算法PoW、PoS等相比拥有更安全、几乎不分叉、更高效(每轮共识达成时间在1分钟以内)等特性。

关键概念

  1. Weighted users: 在Algorand中会对每个用户(用户特指Alogrand运行实例或者说节点)分配一个权重,该权重大小由相应用户所占有的资金数量决定(这点和PoS类似)。因此Alogrand算法需要系统中占有2/3(该比例由BFT算法特性决定) 资金以上的为诚信节点方可避免分叉双花
  2. Consensus by committee: 和传统BFT算法不同的是Algorand会随机选举一个小的节点子集运行BA算法从而实现BA扩展性。 选举会依据节点占有的资金量分配相应的选中概率。
  3. Cryptographic sortion: 为了防止针对committee的恶意攻击,Algorand在选举committee的时候采用了一种私密且非交互的方式。每个节点通过运行VRFs 以及自身私钥和来自区块链的公共信息(主要是随机种子)计算自己本轮是否是committee的成员。当节点发现自己是committee的成员之后会将VRFs返回的证明信息广播给其他用户,其他用户可依据该证明验证其身份。这样攻击者是无法提前知晓被选举的committee成员的。
  4. Participant replacement: 同传统BFT算法不同的是BA* 在共识的每个阶段都会选举新的committee, 每个阶段之间节点之间没有私有状态会参与到共识中去。也就是每个阶段被选举的BA* committee成员将本次的决策信息发送到网络中去之后就与接下来的共识过程无直接关系。

算法假设

  • 诚实节点运行的是bug-free的软件;
  • 诚实节点所占有的金钱数量超过总数量的2/3;
  • 大多数诚实节点(e.g,95%)发出的消息能够被大多数诚实节点(e.g,95%)在一定时间限制内接受到 -- 强同步, 如果该条件不能满足则系统依然安全但是性能会受很大影响;
  • 假设所有诚实节点的时钟是接近同步的(例如采用NTP)

执行流程概述

Algorand目前仅支持数字货币交易,每个交易包含了转出方的签名、转入方信息以及转账金额。一系列的交易组成一个区块,Algorand维护出块的顺序以及整个区块链状态。

Algorand按照轮次(rounds)的概念产生区块,每个round产生一个区块,Algorand通过BA* 算法保障整个网络在每个round产生的区块一致。

如下图所示交易以及其他信息在Algorand网络中通过gossip协议进行传播。

fig1

如下图所示,Alogrand算法通过加密抽签算法选举节点子集运行BA* 算法决定哪些pending transactions组成新的区块append到区块链上。BA*算法的每个step都会按照下图的方式进行,收钱进行抽签然后进行决策投票,最后通过gossip方式将本轮的决策广播出去。

fig2

Block提议

Block提议是BA*算法运行的前置阶段,Block提议是指每个被选中为区块提议成员的用户将一段时间内的pending transactions打包并发布出去的过程。具体流程如下:

  1. 所有用户运行cryptographic sortition算法判断自身是否为本次的出块成员。cryptographic sortition算法能够生成一个证明自己为共识节点的proof以及本节点的priority。其中优先级用于在众多共识节点中定本次该提议的block(即优先级高者优先)
  2. 被选中的出块节点向Algorand网络中广播 < proof,priority, block>;
  3. 其他节点在一定时间内等待接收来自出块节点的block,并丢弃低优先级的节点发送过来的区块;

BA* 共识

BA* 共识的目标是选择提议阶段产生的区块中最具优先级且被一直认可的区块确定下来添加到区块链上。

  1. 每个用户在round中初始化BA* 算法,并将其收到的具有最高优先级的区块作为参数输入到BA*;
  2. BA* 包含多次重复步骤,每次步骤如图2所示;
    • 2.1 每个节点运行密码学抽签算法检查自己是否为本step中的共识成员;
    • 2.2 共识成员向网络中广播证明 \"\\pi\" 以及决议信息;
    • 2.1 ~ 2.2 的步骤一直重复至足够数量的共识成员达成了共识;

以上便是整个区块的产生到添加到区块链的过程。

核心算法

Algorand的核心算法包括两个:1.密码学抽签算法,该算法用于保障每次参与共识的共识委员会成员接近完全随机;2. BA* 算法,该算法由共识委员会成员运行用于产出本次应该打包的区块。

密码学抽签算法

密码学抽签算法保障每个用户(\"pk_{i},)被选中为共识委员会成员的概率同其拥有的货币的金额成比例。即:假设每个用户的权重记为\"w_{i}\"(货币数量), 那么总的权重为 \"W(总货币量), 那么用户i被选为共识委员会成员的概率就同其权重占比相匹配 \"w_{i}/W\",

算法流程

如下图Algorithm 1所示为抽签算法的流程伪代码,抽签函数的输入为:sk: 用户私钥,seed: 伪随机种子,t: 期望被选为该role的用户的数量,role: 角色,w: 用户权重,W: 总权重

algo1
  1. 算法首先使用VRFs函数进行计算 \"<hash, 该函数返回一个哈希值和一个证明,其中哈希值由私钥和输入参数功能决定,他人不可伪造;证明\"\\pi\" 可以让任何知晓该用户公钥的用户验证hash值确实由该输入推导出来,该hash值的随机范围在[0, \"2^{hashlen}]。
  2. 为了能够使用户被选中的概率和其所拥有的货币相对应,Algorand将用户User按照其拥有多少单位的货币分割成sub-users,也即:假设用户i拥有\"w_i\"的货币, 那么该用户就拥有\"w_i\"个sub-users.(i, j)其中 \"j 代表了i拥有的\"{j^{th}}\" 个货币,每一个单位货币被选中的概率p = \"\\frac
  3. 用户的w个sub-users中被选中k个的概率遵循二项分布: \"B(k;w, 其中 \"\\sum_{k=0}^wB(k;w,p) ;
  4. 为了确定用户w个sub-users中多少个sub-user被选中,抽签算法将[0,1) 区间分割成连续的区间:\"I^j 其中\"j
  5. 如果\"hash/2^{hashlen}\" 落在区间\"I^j\" 上,那么该用户共有j个sub-users被选中,该数字j能够通过 \"\\pi\" 被其他用户验证, j >0 就证明本节点在本轮次中被选中为共识委员会成员。

如Algorithm 2算法所示为其他用户验证的逻辑,该逻辑类似抽签算法,通过用户公钥以及hash, \"\\pi\",seed等可进行正确性验证。

algo2

作者:bitking
链接:https://www.jianshu.com/p/1c17ab53380a

本文系作者个人观点,转载请注明出处!
喜欢 0
支付宝扫码打赏
微信打赏

相关文章

更多