Ouroboros

背景

PoW消耗现实中的算力达成区块链的共识体系，就好像需要从外界提供能量来获得一个稳定系统一样，而PoS能根据历史所产生的“权益”，使用一套算法能利用好历史中的“权益”来达成共识从而不断衍生出新的价值，使得区块链本身就能成为一个闭环，不断运行下去。

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

“基于链的PoS”：Ouroboros

论文中的Ouroboros是一个理论：按照什么样的一个流程可以设计出一个健壮的PoS算法并给出数学上充分的证明。而Cardano中的Ouroboros是对论文的实现，工程实现上跟论文中的描述有所不同。

本质上，PoW和PoS都是一种随机选择下一个区块生产者的方式。

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

Ouroboros运行流程

首先要对一些术语进行解释：

• 在Cardano的运行中，时间被分为slot
• 每个slot只能生产一个块，若这个块有问题，或者生产这个块的“矿工”（stakeholder的候选人）不在线，或者产出的块没有广播给大多数人，那么这个slot是当作废弃的，也就是会调过这个slot的块。
• 多个slot为一个epoch，权益的计算是以每个epoch开始前的历史来计算，也就是说在这个epoch中所产生的权益变化不影响当前这个epoch中的slot的出块者的选择和其他和历史相关的东西。当前epoch中所产生的这些历史只能在以后的epoch中生效。
• 每个epoch的开头有个genesis block，其不会上链，而是当前这个节点（矿工）自己在内存中生成，这个genesis block会记录好当前这个epoch中的可能参与出块的stakeholder的候选人，及一个随机种子ρ。
• stakeholder是权益持有者，也就是潜在矿工，在Cardano的实现中权益stake并不是直接指有多少ADA（Cardano的代币），而是和有多少ADA相关联，同时要成为一个stakeholder需要有2%的ADA才行。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选择出块者的概率。

[图片上传失败...(image-1c939-1523805330515)]

论文中的函数表示按照权益占比为概率从stakeholder候选人集合中选出该slot的出块者U。

• secure multiparty computation（MPC）MPC协议，参与者使用一种能达成MPC的密码学协议来参与生成下一轮epoch的随机种子ρ，这个MPC协议必须保证guarantee output delivery（GOD），这个随机种子ρ是用于Slot Leader Selection中的。

image

如图所示，执行流程如下：

• 1.从链的真正创世块开始，硬编码进入一些公钥和这些公钥对应的权益s及初始的种子ρ，之后，这个epoch会采用这些基础信息继续运行。
• 2.每个节点自己独立运行代码，根据当前epoch的种子ρ，执行F(follow-the-satoshi)，把genesis block中的权益，ρ和slot的index作为输入，根据概率获得当前这个slot应该由谁出块。
  • 1.若发现自己出块，则执行打包交易等操作，和bitcoin没有太大区别，除了基础工作之外，还要生成一个随机数，但这个随机数不放在链（块）中，而是放一个承诺（后面大家打开承诺一看，验证自己没有说谎）。
  • 若不是自己出块，则等待出块者出块并广播。收到这个块的时候就性和bitcoin类似的检查，要是长时间未收到（超出这个slot的时间）则会认为这个slot的块废弃。
• 3.在当前epoch中不断重复2的流程直到这个epoch中的所有slot结束。
• 在整个epoch的过程中会产生出一个在这个epoch参与出块者们（slot leaders）都共同认同的随机种子ρ。
• 在自己的内存里记录好这个ρ及下一个epoch参与的stakeholders，开启下一个epoch周期，进入2的流程。

深入解释

Ouroboros的模型及结合目的“产生一个不可预测的随机数”，我们来探讨一下其中的关键问题：如何随机的选出记账者

这个问题在Ouroboros的模型下，可以拆分成两个部分：

• 1.产生一个随机种子ρ
• 2.根据随机种子ρ在当前epoch中以权益的比例为概率，随机选出slot leader

以每一个epoch为分析单位，只要一个epoch的执行流程是成立的，那么不断重复epoch生成的链就是成立的。（就像衔尾蛇一样）

产生一个随机种子ρ

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

coin tossing（投硬币）

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

image

左图是一个两方进行coin tossing的过程：

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

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

这种交互至少需要3步，要达成这样的交互式协议是不能比3步更少的，如果能在尽量少的通信下（如三步）又希望保证整个协议不会因为Abort而无法运行下去，这样的目的就被称为guarantee output delivery（GOD），为了保证GOD这个目标成立，就需要引入一些新的机制。

verifiable secret sharing（VSS）

VSS:可验证的密钥分享。在Cardano中使用的是PVSS。

先讲解VSS：

把一个秘密S通过share(s)可以拆分成m份，分别给m个人，每个人拿到其中的一片并不知道整个S是什么

但是只要收集到另外t(t<m)个人的秘密（总共有t+1份），就可以重新恢复reconstracct(s1,...,st+1) = S出这个秘密。

VSS的特定就是，每个人拿到的那个秘密是不可能知道原来的秘密是什么的，必须得到其他人的帮助才能恢复出原来的密码是什么。

每个人并不是要拿到所有的秘密，而是要拿到一定多的秘密，就可以重新恢复出原来的那个秘密S。

这个特性就可以达成这样一个功能：例如A向大家宣告我有一个东西，然后A就可以用VSS把这个东西分发给所有人，但是所有人又不知道这个东西是什么，此时，即时A挂了或者跑路了，大家也可以互相通信恢复出A一开始的东西。

VSS就是用来解决coin tossing协议中断执行的问题。

GOD coin tossing

coin tossing的问题是要是A没有发送open给B，那么协议就无法执行下去。那么VSS的性质，直接把open分发给所有人就可以，即使A跑路了，大家也可以相互通信恢复出A一开始给出的承诺是什么东西，使得coin tossing的协议能够正常执行下去，得到大家都认可的真随机串。

把VSS和coin tossing结合起来，就可以达成GOD的目标，称为“GOD coin tossing”。

论文提出的方案如下：

image

这里的Deal()对应上面的Share()并对share的结果使用对应接受者的公钥进行加密

Ouroboros采用的方法如下：

• 把整个epoch的slot分成10等份，这里的k是倍数，在Cardano中可以通过配置文件指定

• 整个epoch被分为三个阶段：Commitment Phase，Revel Phase，Recovery Phase，分别占比4：4：2

  • 1.在Commitment阶段的时候，所有的stakehols(i∈{0...n})必须把自己的随机串生成做处理后并把这个内容广播出去，被前4k的leader打包进入区块。（当然如果这个时间内没有把自己的随机串广播出去的话就相当于放弃了参与下一个epoch随机的权力了）而这个处理的内容是2部分：
    • 1. 这个随机串的承诺commitment
    • 2. 把Open的内容做成VSS后对应所有的leader，使用这些leader的公钥（在genesis block中有）进行加密，也就是Dea的过程，生成σ1, . . . , σn 被加密过的shared secret
  • 2.在Reveal阶段中，这些stakeholders(i∈{0...n})把自己的Open广播出去。这时候就出现有人跑路了，有人掉线，网络不好的情况，这个人的Open没有被打包到链中，此时若没有下一个阶段救场的话，就相当于coin tossing协议被Abort了。若所有的Open都在的话，就当然得到下一个epoch的ρ是什么了。
  • 3.在Recovery阶段的时候，这些诚实的slot leaders(i∈{0...R})就会检查出有哪些Open没有成功，那么他们就会把没有成功的Open对应的秘密自己解密后，广播出去上链条，那么这样每个人都可以收集到足够数量的共享秘密而恢复出没有被Open的随机串，GOD满足。此时所有人都获得了所有人的随机字符串，那么就可以得到一个统一的随机数ρ了。

至此，如果在一个epoch中生成一个不可控制的随机数ρ就深入解释完成了。可以看出通过GOD coin tossing是可以做到一个不会被Abort的交互式随机数生成过程。

前两个阶段指的是所有的stakeholders都参与，然后Recovery阶段只有被选中的stakeholders才参与。

根据Cardano结算层的文档来看，在实现上和论文有区别的。

Slot leaders are elected from the group of all stakeholders.Please note that not all stakeholders participate in this election, but only ones who have enough stake (for example, 2% of the total stake). This group of stakeholders are known as “electors”.

具有权益的确就是stakeholders，但是参与过程的并不是所有的stakeholders，而是只有2%以上的人才能参与，而这些2%以上的人就叫做“electors”。

而后续的操作都是基于elector的。

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

在论文中没有详细描述，只是直接定义出了这样一个函数，在Cardano中的实现使用的是“follow-the-satoshi”算法。

follow-the-satoshi算法最原始来自于论文:Proof of Activity:Extending Bitcoin's Proof of Work via Proof of Stake

论文大概是说，使用PoW产生一堆stakeholders，然后在这堆stakeholders中使用follow-the-satoshi找出出块者，当然Ouroboros对其的改进就是把pow做成了G.O.D coin tossing

image

如上图，把所有的stakeholders组成一个merkletree的形式，然后根据一个随机种子开始，通过伪随机数作出选择，最终会按照大家权益的比例选出对应的stakeholder。

这里的伪随机数，是为了当有一个相同的种子后，每个不同的个体分别执行这个伪随机后都能得到相同的序列。

根据随机数进行随机漫步，最后选中某个stakeholder的概率就是其权益占总体的比例。又因为是使用一个真随机数作为种子，执行伪随机进行漫步，那么只要所有人拿到的真随机数的种子是一致的时候，那么所有人得到的随机出的stakeholder的结果就是一致的。

这就可以解释GOD coin tossing中的问题，只要genesis block能够生成后得到ρ和权益集合S，那么就相当于可以计算出当前这个epoch中所有的slotleaders们都是谁了。

总结

整个Ouroboros的核心就是随机数，如何随机选择出块人，并且被全网认可，还不能被操控，也不能被预测。

Ouroboros是基于链的PoS方案，随机选举一个节点出块，其被选中的概率和它拥有的份额相关。关键是如何保证“随机”性？

传统的PoS方案都是从现有的链上数据入手，比如使用上一个区块的哈希值，上一个区块的时间戳作为随机数的来源，但这些会带来额外的安全风险，因为区块本身的信息就是节点写进去的，然后又根据里面的信息来选举后续的出块者，存在循环论证的嫌疑，安全性不会太好。

Coin-Tossing，如果大家都不跑路，就能得到一个一致的无法被操控的随机数。

VSS，就是预防跑路的，叛徒节点。结合Coin-Tossing和VSS就有一个完整的随机数生成协议了。

协议流程：

• 1.提交阶段，每个节点本地生成随机数和对应的承诺，把随机数拆n份匹配其他投票节点，相应投票节点的公钥加密，承诺和加密信息广播。
• 2.打开阶段，每个节点把自己的打开发到链上。
• 3.恢复阶段，恢复出随机数。
• 4.选下一轮出块者