主页 > TP钱包苹果版 > >tp钱包官方网址|Cardano(ADA)的共识算法Ouroboros简介

tp钱包官方网址|Cardano(ADA)的共识算法Ouroboros简介

时间:2022-09-06浏览次数:

Cardano(ADA)的共识算法Ouroboros一、前言

2018年的公链将会毫不意外的统一转向pos共识方向,pow将会被扫入历史中。

在我认为,pos代表的就是不再需要从现实中将价值输入至区块链体系(pow消耗现实中的算力达成区块链的价值体系),而是根据已有的“历史”来不断衍生出新的价值来维护区块链的价值体系。也就是说,所谓权益证明(pos)就是能根据历史所产生的“权益”,使用一套算法能利用好历史中的“权益”来达成共识从而不断衍生出的新的价值,使得区块链本身就能成为一个闭环(而不像pow一样从外界,也就是算力来输入),不断运行下去。

在 区块链算法原理之:Casper 和Tendermint共识算法的比较 这篇文章中提到:

有很多不同的方式来实现权益证明的算法,但是权益证明设计的两个主要原理是基于链的PoS和基于拜占庭容错(BFT)的PoS。

Ada的共识算法 Ouroboros(乌洛波洛斯,也就是衔尾蛇)由于其严谨的学术性和在顶级密码学刊物上发表的论文而闻名,并且是 “Ouroboros是第一个被工业界采用的学术界提出来的可证明是安全和健壮的POS算法。(引用自maxdeath菊苣的回答)” (虽然我不确定和dfinity的那边相比谁才是第一)

本文即将根据 Ouroboros 的论文 “Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol”及IOHK在youtube上的视频解说:Bernardo David, IOHK Research, Proof-of-Stake Protocol 对Ouroboros的运作流程进行自己浅薄的解释。

若有错误,欢迎大家指出。

本文首发于我自己的知乎专栏 金狗喵喵喵的区块链研习

如需转载,需取得同意并标明出处!


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

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

我并没有看过 Cardano 的实现,所以主要是根据论文并结合Cardano来讲Ouroboros是怎么设计的

maxdeath菊苣在很多回答中都指出了:下文引用

本质上,POW和POS都是一种随机选择下一个区块上传者的方式。

所以Ouroboros的根本目的就是为了根据权益多少,随机的选出一个记账者,并且随机选择的这个过程是不可预知的。

二、Ouroboros 总体运行流程

开头先简单描述一下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 大致执行的流程。

三、详细解析

根据上一章所描述的Ouroboros的模型及结合目的“产生一个不可预测的随机数”,我们来探讨一下其中的关键问题:如何随机的选出记账者

我们可以发现,在Ouroboros中,由于epoch的模型,这个问题被拆分成两个部分:

产生一个随机种子ρ根据随机种子ρ在当前epoch中以权益的比例为概率,随机选出slotleader

以每一个epoch为分析单位,那么只要每一个epoch的执行流程是成立的,那么不断重复epoch生成的链就是成立的。(就像该算法的命名Ouroboros,衔尾蛇一样)

那么我们就来分别解释着两个问题

1. 产生一个随机种子ρ

产生这个随机种子的方法在密码学中应该属于交互式协议

首先需要介绍一些东西:

coin tossing (投硬币)

coin tossing 是为了在多方通信中,通过伪随机数和互相交互,最终得到一个统一的,被所有人认可的真随机数的交互式协议。如下图的左边所示:

左图是一个2方进行coin tossing 的过程:

A首先产生一个随机串s和一个nonce,然后用A和B都认可的加密方式进行加密此时加密的结果称为一个承诺(Commitments),A把这个承诺发送给B,此时相当于B知道A已经产生了一个东西,虽然不知那是什么,但是它已经存在了B保存这个承诺,然后自己生成一个自己的随机字串s',并发送给A此时A同时具有了A自己的字串s和B的随机字串s',那么A就发送一个揭露(或者打开Open)给B,包含自己一开始的s和nonceB收到open后使用open的数据加密,把结果和之前的承诺做对比,发现一致,那么B就可以肯定A发送的open就是在发送B自己的随机串之前就确实生成好并存在的。此时A和B都分别拿到了对方的随机串,并能肯定对方生成自己的串的时候是不知道自己的随机串的信息的,所以即便两方都是使用伪随机生成的字符串,那么对这两个字符串做一些统一的操作(比如异或xor)之后的结果一定是一个真随机字串S,并且被双方所认可。

当把这个两方的coin tossing 扩展为多方的时候,就是一个多方coin tossing的交互式随机数生成协议了。

但是呢,我们可以看到,这种交互至少需要3步(左图描述的过程),我们可以发现,要达成这样的交互式协议是不能比3步更少的(可以更多,比如一般google到的coin tossing会是4步,例如B并没有直接给s',而是给了一个Com(s',n'),然后需要第4步B发送给A一个Open)。如果少于了3步,就会出现右图的情况,协议出现了Abort!

在右图的执行流程中:

A首先产生一个随机串s和一个nonce,然后用A和B都认可的加密方式进行加密B给了A自己的s',此时A和B完成基本的信息交互但是此时A自己跑了(不管是作恶还是自己挂了,还是网络断开没法发送了),那么此时A没有把自己的Open发送给了B,此时会导致整个协议无法执行下去,因为现在A具有了所有的信息,但是B没法具有所有的信息,所以没法达成被双方都认可的随机字串

虽然最终这样并不是作恶成为A可以控制最终字符串的产生,但是A这样的行为却可能导致最终的协议无法执行下去,进而被中断(Abort)。而且即便是多步也会有Abort的行为发生使得协议无法执行下去,而太多的通信则会造成整个网络的拥堵(特别是多方的情况下,有k次通信就是O(n^k)的通信复杂度)。

所以如果能在尽可能少的通信下(如三步)又希望保证整个协议不会因为Abort而无法运作下去,这样的目的就被称为guarantee output delivery(G.O.D)

那么为了保证G.O.D这个目标成立,就需要引入一些新的机制,如下文所述。

verifiable secret sharing (VSS)

verifiable secret sharing (VSS) :可验证的密钥分享。在Cardano中使用的是PVSS,见链接 乌洛波罗斯协议论文与实现的区别。

这里先介绍VSS:

把一个秘密S 通过 share(s) 可以拆分成 m 份,分发给m个人,每个人拿到其中的一片并不知道整个S 是什么
但是只要收集到另外t(t

因为我并不是学密码学的,所以就不班门弄斧了,下文只能简单介绍一下VSS能起到的作用。

在视频里面举的例子如下:

S               share(S) -> S1, S2, ...  // 比如我原本有一个秘密S,通过 share(S) 把密码拆成了4份
share(S) = Sa, Sb, Sc, Sd
Sa Sb Sc Sd // 把这4份秘密分别给4个人
A B C D
// 比如按照如下的方式赋值分解出的各个秘密,xor是异或,
// 可以看出A,B,C,D分别拿到的秘密 Sa, Sb, Sc, Sd 都是不可能知道原来的S是什么的
Sa = S xor Ra R is random str
Sb = S xor Rb
Sc = S xor Rc
Sd = Ra xor Rb xor Rc
// 但是只要其中有人能收集到别人的秘密,比如A自己向B,C,D收集到了另外3个秘密
// 那么 A 就可以把这些秘密全部执行 xor, 由于xor 的性质,就能恢复出原本的 S
reconstract(Sa, Sb, Sc, Sd) = Sa xor Sb xor Sc xor Sd=S

标签: