点评Cardano的共识算法Ouroboros(1)

2018年的公链将会毫不意外的统一转向pos共识方向,pow将会被扫入历史中。大牛哥认为,pos代表的就是不再需要从现实中将价值输入至区块链体系(pow消耗现实中的算力达成区块链的价值体系),而是根据已有的“历史”来不断衍生出新的价值来维护区块链的价值体系。也就是说,所谓权益证明(pos)就是能根据历史所产生的“权益”,使用一套算法能利用好历史中的“权益”来达成共识从而不断衍生出的新的价值,使得区块链本身就能成为一个闭环(而不像pow一样从外界,也就是算力来输入),不断运行下去。然后,现在,Cardano(ADA)的共识算法Ouroboros是第一个被工业界采用的学术界提出来的可证明是安全和健壮的POS算法。

权益证明设计的两个主要原理是基于链的PoS和基于拜占庭容错(BFT)的PoS。Ada的共识算法 Ouroboros(乌洛波洛斯,也就是衔尾蛇)由于其严谨的学术性和在顶级密码学刊物上发表的论文而闻名,并且是 “Ouroboros是第一个被工业界采用的学术界提出来的可证明是安全和健壮的POS算法。(引用自maxdeath的回答)”

毫无疑问,Ouroboros是 “基于链的PoS”。

首先先要声明:论文中的Ouroboros是一个理论,说的是按照什么样的一个流程可以设计出一个健壮的pos算法并给出充分的证明,而Cardano中的Ouroboros是对论文的实现,在实现上和论文中的描述有所不同。

下面简单阐述一下Ouroboros的共识机制。Cardano的系统会内部设立一个时间段(slot),每隔一定的时间段,随机选出一个该时间段的记账者(slot leader),所有人获得记账权的概率与其持有的ada数量成正比(例如如果A持有占总量1%的ada币,那么其就有1%的概率会获得记账权)。记账者完成打包出块的工作后即可获得对应的手续费。该模式既有POS的各种优势,例如不耗费电力及大量算力,同时因为是由系统进行随机筛选,不容易产生恶性分叉。

ADA的共识机制

开头先简单描述一下Ouroboros运行的流程:

首先是一些术语及作用的解释:

在Cardano的运行中,时间被分为 slot

每个slot只能产生一个块,若这个块有问题,或者应该产出这个块的“矿工”(也就是stakeholder的候选人)不在线,或者产出的块没有广播给大多数人,那么这个slot是当作废弃的,也就是会跳过这个slot的块。

多个slot为一个 epoch,权益的计算是以每个epoch开始前的历史来计算,也就是说在这个epoch中所产生的权益变化不影响当前的这个epoch中的slot的出块者的选择和其他和历史相关的东西。当前epoch中所产生的这些历史只能在以后的epoch中生效。

每个epoch的开头有个 genesis block(注意是每一个epoch,不是整个链),这个genesis block 不会上链(整个链初始的那个genesis会,当然这一点可以根据实现自己决定),而是当前这个节点(矿工)自己在内存中生成,这个genesis block会记录好当前这个epoch中的可能参与出块的 stakeholder的候选人,及一个随机种子ρ。

stakeholder是权益持有者,也就是潜在矿工,在Cardano的实现中权益stake并不是直接指代有多少Ada,而是和有多少Ada相关联(更详细的我不是很清楚),同时要成为一个stakeholder需要有2%的Ada才行。当然论文中不关注这些,直接定义了stakeholder。而stakeholder并不一定要参与出块,只有记录在每个epoch的genesis block中的stakeholder才能参与当前epoch中slot的出块,所以记录在每个epoch中的genesis block中的stakeholder叫做 “stakeholder候选人”

由这些epoch衔接而成的链就是由Ouroboros共识产生的链,这个链的基本属性和Bitcoin相同(如每个块包含上一个块的hash等等)。

Slot Leader Selection 是指根据权益占比选择按概率选择出当前slot的出块者。指代的是在当前的epoch中,按genesis block 中记录的stakeholder候选人的权益分别占用的比例为这个epoch中的每一个slot选择出块者的概率(注意这个概率是独立事件,也就是有可能在同一个epoch中重复选出相同的人)。在论文中用函数

来表示按照权益占比为概率从stakeholder候选人选出该slot的出块者U。注意在论文中只是定义了这个函数具有这样的作用,在Cardano中使用了 “follow-the-satoshi(fts)” 算法(fts具有论文中定义的这个函数的性质)来选出这个slot leader也就是出块者。

secure multiparty computation (MPC) MPC协议,参与者使用一种能达成MPC的密码学协议来参与生成下一轮epoch的随机种子ρ,这个MPC协议必须是保证guarantee output delivery(G.O.D,下文会解释)。这个随机种子ρ是用于Slot Leader Selection中的。

在已有这些基础术语及作用的基础上,现在来简单介绍一下的工作流程:

如图所示,执行流程如下:(注:我并不保证这个流程是完全符合Cardano源码的实现(毕竟我没看过),但是是符合论文的描述的)

从链的真正创世块开始,硬编码进入了一些公钥和这些公钥vk对应的权益s及初始的种子ρ,之后,这个epoch会采用这些基础信息继续运行。

每个节点自己独立运行代码,根据当前epoch的种子ρ,执行F(比如 follow-the-satoshi),把genesisblock中的权益,ρ和slot的index作为输入,根据概率获得当前这个slot应该由谁出块。

若发现是自己出块,则执行打包交易等等操作,和bitcoin没有太大区别,但是除了基础工作之外,还会生成一个随机数,但是这个随机数不放到链(块)中,而是放一个承诺(后文解释)。

若不是自己出块,则等待出块者出块并广播。收到这个块的时候就进行和bitcoin类似的检查,要是长时间未收到(超出这个slot的时间)则会认为这个slot的块废弃。

在当前epoch中不断重复2的流程直到这个epoch中的所有slot结束。

在整个epoch的过程中会产出一个在这个epoch参与出块者们(slot leaders)都共同认同的随机种子ρ。

在自己的内存里记录好这个ρ及下一个epoch参与的stakeholders,开启下一个epoch周期,进入2的流程。

以上就是 Ouroboros 大致执行的流程。此外,Cardano及其共识机制还有更多亮点。(后续持续分析,请保持关注)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180720G0O9HU00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券