Algofans | Algorand爱好者

深度解析Algorand共识协议(上)

云上春野云上春野 2019-08-21 34 次 收藏0

 

概述

 

1.1 引言

 

Algorand 称其突破了”公链不可能三角“,项目创始人是图灵奖得主、MIT CSAIL 实验室的 Silvio Micali 教授。Algorand 提出的共识协议是项目的一大亮点,本文主要分析 Algorand 共识协议的工作原理,并分析其优缺点。

 

1.2 Algorand 设计的初衷

 

Algorand 想解决的核心问题是:去中心化网络中低延时(Latency)和高置信度(Confidence)之间的矛盾[1]。

 

其中,延时指从发起交易到确认交易所需要的时间;置信度指的是发出的交易不会再被更改的概率。

 

在比特币网络中,为了提高交易的置信度,用户必须等待 6 个区块确认(约 1 个小时)的确认延时;而如果选择低延时,比如少于 6 个确认,甚至是 0 确认,则必然导致低置信度,增加“双花”攻击的可能。双花问题是绝大多数加密数字货币的核心问题。比特币中采用 PoW 共识来解决,但链本身仍然有分叉的可能,并且需要较长的共识达成过程和确认时间。

 

同时 Algorand 还想解决比特币中 PoW 挖矿耗费巨大资源、交易确认时间长、易分叉、网络呈中心化趋势,可扩展性差等问题。

 

1.3 Algorand 是什么?

 

根据官方描述,Algorand 是一个采用 permissionless 的纯 PoS 共识的公链项目,结合改进的拜占庭共识协议,可实现快速的交易确认,几乎不会分叉,并且用户数可无限扩展,不会影响交易确认速度。同时兼顾“可扩展、安全性、去中心化”这个“公链不可能三角”[2]。

 

(注:”公链不可能三角“的正确性和具体定义存在较多争议[7]。在 Algorand 中:可扩展性指在较大用户规模下仍可实现较高的吞吐量[8],安全性指的是可以对抗恶意攻击[9],去中心化指的是网络完全开放,成为节点没有任何门槛[10]。)

 

  • 可扩展性:Algorand 通过可验证随机函数(VRF)随机选择区块的生产者和验证者,一旦得知被选中,生产者或验证者只需广播一个简短的消息即可证明自己的身份。每产生一个新区块在网络中需要交换的消息不会随着用户数的增大而改变,,因此即使用户规模增大,系统仍可保持较高的 TPS(每秒处理的交易数)。Algorand 的 TPS 是比特币的 125 倍。
  • 安全性:由于采用了上述的 VRF 随机选取生产者和验证者,并且选取的过程完全由节点独立完成,因此Algorand 网络中的攻击者无法预先得知下一个区块生产者和验证者,从而也就无法完成攻击。具体来说,生产者和验证者的身份只有在他们确定自己被选中并广播对应的证明信息时才会被披露,这时攻击者即使立刻采取各种攻击手段,也无法阻止关于新区块的正确消息在网络中的传播。
  • 去中心化:Algorand 中每一轮的区块生产者和验证者都是随机选取的,并且加入网络没有任何门槛,因此是完全去中心化的。

 

下面详细介绍 Algorand 的共识协议。

 

Algorand 协议详述

 

几乎所有公链项目的区块产生和共识的过程都可以抽象为两个步骤:

 

  1. 选择出区块生产者,生成新区块
  2. 其他节点对新区块达成共识

 

以上步骤周而复始,最终形成一条“不可篡改”的区块链。

 

整个共识过程虽然简单,但在实际实现中,必须解决几个关键问题:

 

  • 如何选择区块生产者,且保证公平和不可被预测?
  • 如何对新区块达成共识?
  • 如何避免分叉?
  • 如何提高安全性?
  • 如何扩展到更大规模的用户?

 

比特币采用哈希函数的随机性来确保公平,采用工作量证明(PoW)达成共识,同时能够在一定程度上抵抗算力攻击。然而比特币仍然面临上述消耗计算资源、确认时间长、易分叉以及扩展性差等问题。以 Qtum 为代表的采用纯权益证明(PoS)共识机制的项目,同样采用了哈希函数,并且不需要消耗大量的计算资源,然而仍然面临易分叉、安全性及扩展性的问题。

 

Algorand 提出了一种新的共识机制解决上述 5 个问题。

 

2.1 基础知识

 

正式介绍 Algorand 共识协议之前,本文假设读者基本了解以下名词的含义:

 

  • 哈希函数(Hash)
  • 公钥/私钥
  • 数字签名
  • 交易
  • 区块
  • 账本
  • 共识
  • 拜占庭协议(Byzantine Agreement,BA)
  • 诚实节点
  • 攻击节点
  • P2P 通信

 

如果读者对上述概念不理解,请先搜索相关关键词进一步了解,再阅读以下内容。

 

2.2 Algorand 的基本过程

 

Algorand 协议可以按照时间顺序划分为不同轮次,每一轮都会达成共识并生成新区块。其典型的通用过程如下:

 

  1. 每一轮共识开始时,随机选出潜在的 leaders,各自生成新区块,对新区块进行签名和广播
  2. 随机选出验证组,对 leaders 广播的新区块进行验证,达成共识后广播确认新区块,进入下一轮

 

接下来具体讨论 Algorand 共识协议细节,本节主要参考[4]。

 

2.3 保证 Algorand 的随机性:可验证随机函数

 

Algorand 利用 VRF 来选择区块生产者和验证者,保证所有共识参与者都是随机地、公平地被选出的。可验证随机函数(VRF,Verifiable Random Function)是由 Micali 教授等提出的一种伪随机函数,和普通的随机函数一样,对于不同输入,其输出也具有随机性(严格来说是“伪随机”)。其独特之处在于调用者可以提供一个证明,表明这个随机输出确实由该调用者产生。

 

VRF 可以有多种实现方式,Micali 等人在其原始论文中提供了一种较复杂的实现方式[3]。

Algorand 利用哈希函数和数字签名的特性,提供了一种较为简单的 VRF 实现。具体实现方式是调用者 i 将输入 m 通过数字签名和哈希函数映射为固定长度的输出 H[SIGi(m)],即 m -> H[SIGi(m)]。

 

对于任何输入 m,不同的调用者 i 生成的数字签名 SIGi(m) 都是唯一的;而对于不同输入,哈希函数 H 的输出具有随机性,因此上述映射符合 VRF 的”随机性“要求。同时,由于 i 的数字签名 SIGi(m) 可通过其公钥对其身份进行验证,因此其也符合 VRF ”可验证“ 的特性,SIGi(m) 就是 VRF 中提到的”证明“。

 

这个函数特别适合在所有节点中随机选择出共识的参与者,下面具体讨论。

 

2.3.1 随机选出每一轮的区块生产者(Leader)

 

每一轮共识开始时,每个节点都可以通过以下 VRF 独立地验证自己是否是潜在的 leader:

 

.H[SIG(r, 1, Q(r-1))] <= 1 / SIZE(PK(r-k))

 

其中,H 是哈希运算;SIG 是签名运算;r 是目前的轮次;Q(r-1) 为与 r-1 轮的种子(将在后续 2.6 节中解释);SIZE(PK(r-k)) 是在 r-k 轮所有符合要求的公钥的数量(为什么是 r-k ?k 为回溯系数,也将在 2.6 节中阐述);公式开始的 . 表示将哈希结果转化为小数位,从而保证结果为[0,1)的某个值。

 

节点通过自己的私钥计算上面签名的哈希值是否符合要求,从而知道自己是否属于候选的 leader,在此过程中无需和其他节点交换信息。由于哈希函数输出的随机性,可以认为符合要求的候选节点都是随机选出的。候选节点随后可以生成新区块,并向全网提供签名证实自己的身份。如果有多个候选 leader,最终上述哈希值最小的 leader 将在后续的共识中成为本轮最终的 leader。Leader 产生的区块 Br 包含了本轮的所有交易和上述的证明信息,由验证组成员进行共识验证。

 

2.3.2 随机选出每一轮每一阶段的验证组

 

验证组成员的选择与上述过程类似,在每一轮和每一阶段(step),所有节点都可以独立验证自己是否属于验证组成员:

 

.H[SIG(r, s, Q(r-1))] <= n / SIZE(PK(r-k))

 

其中 s 为本轮所处的不同阶段,Algorand 在每一轮的各个阶段都有不同的验证组,从而进一步保证安全性;n 为预期的验证组成员数量,可以人为设定;其他参数含义不再重复。

 

与候选 leader 一样,每一阶段的验证组成员均随机选出,验证节点在证实自己身份后,可以开始参与共识验证过程,揭露自己的签名即可证明其身份。

 

2.3.3 引入权益证明(Proof-of-Stake,PoS)机制

 

上述的随机选择过程没有考虑 Token 持有者的权重,恶意节点可能通过大量生成有效私钥从而有极大概率成为区块的生产者和验证者。Algorand 在其公布的实现建议中引入了名为 Honest Majority of Money (HMM)的条件假设,其基本思想来源于 PoS 共识机制,即在上述随机选择过程中引入代币持有量(Stake)作为权重,持有量多的节点被选中的概率较高,而代币持有者往往更倾向于保护网络的安全性。具体可以表示为如下公式:

 

.H[SIG(r, 1, Q(r-1))] <= (a(i,r) / M) * (1 / SIZE(PK(r-k)))

 

其中,a(i,r) / M 为节点所持有的币的数量占代币总数 M 的权重。其余过程与前面描述一直。

 

Algofans是由Algorand技术爱好者自发建立的技术和生态交流社群,Algofans立足于建立最好的Algorand中文技术社区,持续推广和普及Algorand技术与知识,帮助Algorand释放技术潜力。如果您和我们一样,相信Algorand技术实力、Algo以及无边界经济的潜在价值,请扫码加入Algofans社区!

 

 

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

相关文章

更多