Algorand: Scaling byzantine agreements for cryptocurrencies

文章链接：https://doi.org/10.1145/3132747.3132757

作者：Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich

发表：SOSP ‘17: Proceedings of the 26th Symposium on Operating Systems Principles

截止当前（2021.03.08）被引次数：738

Zotero链接: 从我的文库打开

标签1 标签2 标签3 标签4
PoS VRFs Consensus

[toc]

CS1951L-Algorand

Lack of finality（终结性） is a major issue with PoW!

PoW的主要问题是缺乏终结性。尤其是在跨链（cross-chain）或者链下（off-chain）应用中。

Byzantine Fault-Tolerance 问题

  • 无法扩展到大量选民（voters）的情景中
  • 扩展Scalability：Elect a Committee （只需要委员会选择committee selection不是腐败的） ==»通过委员会方法进行扩展并不是一个新方法
  • 对于女巫攻击而言是脆弱的（vulnerable）
    • Anti-Sybil：PoS（Proof-of-Stake）

Algorand

Customized BFT protocol，Randomly select committee，Weighted by stake，Reselect on each round

  • With high probability, all agree on sequence of transactions 极有可能所有人都同意交易顺序

  • Safety: if one honest use accepts A, all eventually do 安全性：如果一个诚实的使用接受A，则所有最终都接受

  • Liveness: under network assumptions 活动性：在网络假设下

Algorand Adversary

  • 我可以参加并持有金钱， 但是我承受不起 h <1/3
  • 我可以破坏目标用户， 但是我不能破坏 > 2/3的用户

富有的投票更多

  • 有k枚硬币的用户，每一枚硬币被分为k个子用户， 被独立选择， 没有人必须知道……， 多少次Alice被选择

Conclusions

  • 委员会的途径达成共识
  • Proof-of-Stake
  • Sortition
  • VRFs
  • Choosing seeds
  • Choosing secret keys

0.Abstract

Algorand：一种新的加密货币，在扩展到许多用户时可以确认时延为一分钟（几乎不分叉）的交易。 即使有一些恶意用户并且网络被临时分区也能确保用户不会对已确认的交易有不同的view。

使用一种新的Byzantine Agreement（BA）protocol； 使用基于VRFs的新机制来将共识扩展到许多用户

在Algorand的BA协议中，除了用户的私钥外，用户不保存他们的任何私有状态，这使得用户发送完消息后立即更换参与者==»缓解了参与者身份暴露后的针对性攻击

1.Introduction

当前的协议遭遇到交易中时延和信任的权衡。 Bitcoin达成交易实现高度信任需要花费 1小时，另外要求低时延的应用不能肯定交易得到确认并且必须相信payer不会双花。 双花攻击=>使用区块链记账， 但是达成共识困难（任何人能够参与，敌手可以创造任意数量的假币【女巫攻击】使得需要一小部分诚实用户的传统共识协议不可行了） ==» Bitcoin及其他加密货币使用 PoW， 但是PoW允许分叉攻击的可能性 。

减缓分叉需要两个牺牲：

  • 将链增长一个区块的时间必须相当高(例如，比特币10分钟)，
  • 应用程序必须等待几个块，以确保它们的事务保持在权威链上(比特币[7]推荐6个区块)

==»其结果是，用比特币确认一笔交易大约需要一个小时。

Byzantine agreement（BA，应用于大规模用户中，低时延且没有分叉的可能性）协议是Algorand的核心。BA的关键性技术是VRFs（以私密和非交互的方式随机选择用户）。 【38，16】是本文的前期技术报告

Three Challenges(Algorand)

  • 女巫攻击
  • BA必须扩展到数百万用户，远高于当前最先进的拜占庭协议的操作规模
  • 必须能抵抗拒绝服务攻击（denial-of-service attacks），并且即使在敌手断开一些用户的连接也要继续操作【30，52】

Techniques

  • Weighted users
    • 为抵抗女巫攻击，Algorand给每个用户一个权重。BA旨在保证用户的一致意见，只要有加权的部分(大于2/3的常数)用户是诚实的。在Algorand，我们根据用户账户里的钱来衡量用户。 ==»只要诚实用户拥有超过2/3，则Algorand能够避免分叉和双花攻击。
  • Consensus by committee
    • BA通过选择一个委员会执行协议的每一步（从所有用户中随机选择的一小部分代表）实现扩展性。BA基于用户的权重在用户中随机选择委员会成员==» 允许Algorand确保委员会成员中有相当一部分是诚实的。 但是，对委员会的依赖增加了对选定的委员会成员进行有针对性攻击的可能性
  • Cryptographic sortition（加密抽签）
    • 为了解决利用委员会达成共识产生的针对性攻击问题，BA以一种私人的、非交互式的方式选拔委员会成员。 系统中的用户通过计算自身私钥的VRF以及来自区块链的公共信息来 独立决定他们是否能够被选择为委员。 若函数显示用户被选择了，会返回一个向其他用户证明委员会成员身份的短字符串（包含在他的网络信息中）。由于委员选择是非交互式的，因此直到该用户开始参与BA，对手都不知道目标用户。
  • Participant replacement
    • 一旦某个委员会成员在BA中发送了一条信息，敌手就可能盯上该委员会成员。==» BA要求委员成员只发送（发言）一次来减缓这种攻击。 因此，一旦委员会成员发送了他的信息(向对手暴露他的身份)，对于BA委员会成员就变得无关紧要了。
    • BA通过避免任何私有状态**(用户的私钥除外)**来实现此属性，这使得所有用户都**能够平等地参与**，并且通过为Byzantine agreement协议的每一步选举新的委员会成员来实现。

2.Related Work

  • Proof-of-Work
  • Proof-of-Stake
    • Algorand使用货币价值作为权重， 许多权益证明的加密货币 两者之间有重要的不同：Algorand中只要攻击者控制的货币价值少于1/3，就能够保证分叉的可能性是可忽略的（不存在的）；在其他许多权益证明加密货币中，恶意leader创造新块导致网络分叉，leader将会失去他的钱
    • PoS避免了PoW的计算开销 ==» 允许减少交易确认时间。 PoS在实践中实现【Outdoors【31】第一个实现】是具有挑战的。一些权益证明加密货币要求主密钥来周期性对正确账本签名来避免 信任危机；而Algorand在即使leader证明是恶意的情况下也能避免分叉解决这个问题
  • Trees and DAGs instead of chains

3.Goals AND Assumptions

  • Safety: if one honest use accepts A, all eventually do 安全性：如果一个诚实的用户使用接受A，则所有最终都接受

  • Liveness: under network assumptions 活动性：在网络假设下

  • Assumption

    • Algorand Adversary：我可以参加并持有金钱， 但是我承受不起 h <1/3我可以破坏目标用户， 但是我不能破坏 > 2/3的用户

    • Strong synchrony：Algorand用于实现Liveness，在一个已知的有限时间内大部分诚实用户（eg.95%）能发送消息被大部分其他诚实用户（eg.95%）接收；敌手最多只能能够控制网络的小部分诚实用户

    • Weak synchrony：Algorand用于实现Safety。在每个时长b的周期中，必须要有一个时长为s<b的strong synchrony时间

      in every period of length b (think of b as a day or aweek), there must be a strongly synchronous period of length s < b (an s of a few hours suffices).

4.Overview

Algorand要求每个用户拥有一个公钥，类似Bitcoin在区块链中添加区块。用户使用gossip protocol通信来提交新交易。Algorand使用BA就未确定（排队中）的区块达成共识。BA**按步骤（step）**执行，在相同的gossip protocol上通信，并产生一个新的一致同意的块。

BA能达成两类共识：

  • final consensus；达成最终共识说明在一个区块上达成共识，进一步地交易得到确认

  • tentative consensus。达成暂时性共识说明可能在不同的区块（只要没有达成final consensus）上达成了共识

    • 两类情况
    • 1）若网络是强同步的，敌手 只有小概率可能性 使BA在一个区块上达成tentative consensus。BA既不能在不同区块上达成共识，也不能简单确认网络是强同步的。Algorand最终（in a few rounds）以压倒性（绝对）概率在后续区块上达成共识，因此确认这些更早一些的交易。
    • 2）若网络是弱同步的（例如，它完全由对手控制，并有一个上限，即对手可以控制多久）。此时BA能在不同区块上达成tentative consensus，形成多个分叉。这反过来又会阻止BA再次达成共识，因为用户被分成不同的组，而这些组对之前的块有disagree。 为了恢复liveness，Algorand周期性的invoke BA决定哪个分叉进一步增长。 一旦网络重新回到强同步，这将允许Algorand选择其中一个分叉，然后在该分叉的后续区块上达成final consensus。

当且仅当后续块达成最终共识时，用户才会确认一个暂时块的交易。

Algorand的Gossip Protocol 实现类似Bitcoin

Block proposal（section 6）

Agreement using BA（section 7）

每个用户都用他们收到的最高优先级区块初始化BA。

上图中，每一步从sortition开始，所有用户检查他们自己是否被选为委员会成员。是委员会成员就广播一条包含他们的选择证明的消息（上图中部区域的蓝红绿三个箭头）。在经过BA的多次这样重复执行的步骤后，委员会的足够用户达成共识。

(Steps are not synchronized across users; each user checks for selection as soon as he observes the previous step had ended.) 用户之间步骤不是同步的

委员会成员会在每一步结束后可以替换，每个用户只要观察到每一步结束后则检查选择。

正如前面所讨论的，BA的一个重要特征是委员会成员除了私有密钥之外不保存私有状态，因此（委员会成员）可以在每一步之后被替换，以减少针对他们的有针对性的攻击

Efficiency

当网络是强同步的，BA保证所有诚实的用户从相同的初始区块开始（例如，the highest priority block proposer was hon est）

5.Cryptographic Sortition

使用VRFs实现Sortition。

Selection procedure

Sortition Interface（CS1951L）

Sortition Algorithm

其中W表示 Algorand中货币单元总数，t表示用户预计被选择的次数，p是被选择成为委员的概率。j是被选中的次数。

伪随机数（PRN，pseudo-random number）hash 决定了 被选择的sub-users数量。

PS：上面两张PPT后面没被选中应该是 (1-p)^(w-k) 这样，大概教授笔误了吧？ 看下图原论文

w(用户权重)个子用户中正好有k个子用户被选中的概率遵循二项分布，子用户的选择遵循二项分布。

由于上图的性质，则将[0,1) 区间划分称如下连续的区间（consecutive intervals）

选择的子用户的数量是可以使用proof π(来自VRF输出)公开验证的。

Two important properties

  • Users selected at random based on weights

  • Adversary（that does not know sk_i） can’t guess how many times a user was chosen 或者 更准确地说，对手的猜测不可能比基于权重随机猜测更好

Verifying Sortition

Choosing the seed

  • PRG requires a seed …
  • Chosen at random
  • Publicly known
  • Algorand: new one every round
  • Cannot be controlled by Adversary

每一轮，发布一个新的seed，Round r determined with VRFs of r-1（在Algorand中基于第r-1轮的seed使用VRFs来决定第r轮的seed）

Each committee member computes …

Round Seeds

seed0 由Algorand最初的参与者（在他们的公钥公开后）使用distributed random number generation[14]随机选择

Limiting the Adversary

Choosing sk_u well in advance of the seed

如果网络不是强同步的，attacker对链有完全的控制，因此可以drop block proposal，并强迫用户同意空区块，这样就可以计算未来的选择种子 ==» 为缓和这种攻击，Algorand依赖于weak synchrony assuption。

强同步时期的时长s内应该允许足够多的区块被创造以保证绝对的（压倒性的）概率至少有一个区块是诚实的。这可以确保，只要s足够大，选择私钥sk_u的敌手u就无法预测r回合的种子

this look-back period b 体现了如下权衡：

较大的 b 降低了attacker能够打破弱同步假设的风险，但是 增加了用户将他们的货币转移给其他人的机会 因此如果系统的安全性破坏，也不会有什么损失（俗称 “无利害关系”问题）。 一个可能避免这种权衡的方法是：将用户当前余额的最小值和look-back block中的用户余额作为用户的权重。【本文作者指出，但并未在Algorand中使用】

上图WHP表示 with overwhelming probability

6.Block Proposal

  • Minimizing unnecessary block transmissions
    • 为了降低通信成本，用sorting hash对block proposal进行优先级排序：对于用户i的每个被选择的sub-user 1,…,j，区块proposal的优先级通过对连接子用户索引的VRF(可验证的随机)hash输出进行哈希得到。
  • Waiting for block proposals
  • Malicious proposers

Evaluation

References

  • Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies[C]//Proceedings of the 26th Symposium on Operating Systems Principles. 2017: 51-68.

  • Micali S, Rabin M, Vadhan S. Verifiable random functions[C]//40th annual symposium on foundations of computer science (cat. No. 99CB37039). IEEE, 1999: 120-130.

  • CS1951L-Algorand

  • Algorand Releases First Open-Source Code: Verifiable Random Function