【Cardano】一文读懂 Ouroboros 算法

中文
1

卡尔达诺社群刘大佬翻译对卡尔达诺Ouroboros运算方式的介绍：

知乎原文：https://zhuanlan.zhihu.com/p/49573481

这是卡尔达诺社区成员 Llfourn 的文章，他是一位资深的开发工程师，早在年初就开始研究 Cardano 的算法，在这过程中不断改进，并且与论文作者沟通，最终写下此文。

文中比较了 Ouroboros 与 Praos 两个版本的权益证明机制，通过浅显易懂的方式介绍了区块链生成与领导者选举的方式。

希望你能够有所启发。

本文翻译自：https://medium.com/unraveling-the-ouroboros/introduction-to-ouroboros-1c2324912193

作者： LLFOURN

译者：刘祯

发文时间：2018 年 2 月 16 日

翻译时间：2018 年 11 月 13 日

Ouroboros 是 Cardano 权益证明共识算法的名称。迄今为止，它有两种形式，Ouroboros 和Ouroboros Praos。这篇文章给出了我对于两者如何运作的深度解析。若是你想要粗略了解，请查阅这两篇论文。Peter Gaži 博士的讲解是这篇文章的绝佳补充（幸运的是，当我正在撰写这篇文章时，视频就发出来了）。

https://youtu.be/PoNaw-Mtxgo

正如 Gaži 博士所指出的，对于任何类型的分布式账本，你都需要两个属性：持久性和活跃性。其中 𝐤 是安全参数，它们被定义为：

持久性： 一旦交易超过 𝐤 个区块到一个诚实玩家的区块链中，那么它将以极大的概率被包含在每个诚实玩家的区块链中。或者更简单地说，一旦你的交易在区块链中，它就会留在那里。
活跃性： 来自诚实账户持有人的所有交易最终都会在诚实玩家的区块链中超过 𝐤 个区块，因此对手无法对诚实账户持有人进行选择性的拒绝服务攻击。或者更简单地说，如果你进行有效的交易，它将最终进入区块链。

根据 GKL15 论文（我从中获取了两个定义），比特币的工作证明（PoW）协议可证明地实现了上述两种方法。想要让权益证明（PoS）协议以实现同样的目标是一项挑战。工作量证明通过区块链之外的计算密集型竞争来选择区块创建者。使用权益证明，区块创建者选择过程的输入是区块链本身 - 区块链选择谁将扩展区块链。这给持久性和活跃性带来了一些问题：

操纵： 攻击者可以通过设计区块链的状态来偏向阻止创建者选择过程。如果可以，他们可以反复重新选举自己作为区块创建者。如果他们主宰区块创建，他们可以审查交易，违反活跃性。
零权益攻击： 因为创建一个区块你没有任何成本，你也可以在任何地方创建区块。如果攻击者可以有效地使用这种权力，他们可能会通过在竞争链上创建阻止或贿赂/鼓励其他人这样做来违反持久性。如果区块链变得足够长，它将超过主链，从而重写历史。

两个 Ouroboros 协议都产生无偏的随机数来解决操纵问题。这种随机性允许一个无偏见的「时隙领导者」（区块创建者）选择过程，选择具有与其权益成比例概率的领导者。在「纪元」（划分为许多时隙的时间段）期间，参与者将随机数写入区块链，最终选择下一个时期的时隙领导者。两者在这方面的主要区别是：

Ouroboros：每个人都提前了解时隙领导者，每个时隙总有一个时隙领导者。
Praos：每个权益持有者都提前了解他们领导时隙的位置。其他人只有在发布一个区块时才发现。时隙可以有多个时隙领导者，或者根本没有。

这些论文通过证明即使攻击者能够轻松创建分支的能力来证明持久性和活跃性也能解决无关紧要的问题（视频演示了证据的方法）。在论文中还有一个尚未实施的「输入背书」的想法，可以创造出诚实行事的规则。

最初构想 Ouroboros 是为了证明权益证明协议可以是安全的。它也可以在实践中使用，现在正在Cardano 主网上使用。但是，目前只有少数获得授权的权益持有者才符合资格。所有权益基本上都分配给他们。在 2018 年的某些时候，这些引导阶段将会结束，权益委托将能够重新分配他们的股份。最终，Cardano 将过渡到 Praos，这是与其中一位作者 Aggelos Kiayas 教授的「与Ouroboros相比实质性的跨越式发展」。

本文的其余部分详细介绍了两种协议的领导者选举流程。

Ouroboros

在 Ouroboros 中，随机生成过程中使用的主要加密方案是可公开验证的秘密共享（PVSS）。在秘密共享方案中，「共享者」将秘密分成多个「共享」。如果一方可以访问某些比例的权益（这里将超过 50％），则只能重建原始机密。在可公开验证的秘密共享计划中，共享者公开发布权益有效的证据。

使用 PVSS，利益相关者在区块链上玩硬币翻转游戏。游戏的随机结果为下一个纪元产生了时隙领导者。为了玩游戏，每个参与者向区块链发布秘密随机数。在这个纪元，这些随机数被揭示出来。最后，他们结合起来确定性地产生一个最终的公共随机数，所有参与者都用它来确定下一个纪元的时隙领导者。

协议运行机制如下，一个纪元被定义为 10𝒌 个时隙长度：

  • 委员会的形成：这个纪元的独特时隙领导者组成了一个名义委员会，它将扮演硬币翻转游戏。每个委员会成员私下生成一个随机数 𝒖（他们翻转硬币）。
  • 提交阶段：在一个纪元的前 2 个时隙，委员会成员根据协议使用的特定 PVSS 方案将他们的 PVSS 数据发布到区块链。各方发布：

1）对 𝒖 的承诺。

2）用其公钥加密的每个其他委员会成员的“份额”。此份额不会向他们提供有关 𝒖 的信息，但如果你拥有超过一半的份额，则可以重建它。

3）承诺的密码证明和共享的密码证明是相同的。

  • 显示阶段：在接下来的 2 个时隙，委员会成员在区块链上显示他们的 𝒖 。
  • 恢复阶段：在最后 1 个时隙，委员会成员检查谁没有透露他们的 𝒖。对于没有透露的人来说，每个成员都将该参与者的份额发布到区块链。一旦超过一半的股票被公布，所有各方都可以重建该方的 𝒖。
  • 新时代：各方的 𝒖 价值已公开。它们被合并在一起得到 ρ，它被用作种子，为下一个纪元的每个时隙挑选一个随机的聪（最小的货币单位）。那个聪的拥有者是时隙领导者。现在开始下一个时代的委员会组建。

注意事项

  • Ouroboros 论文中提到的 PVSS 方案是 Sch99。为 Cardano 开发的是 SCRAPE。我还没有经历过 SCRAPE，所以在阅读下面的猜想时请记住这一点。两者的 Haskell 实现由 IOHK 开发人员编写：https：//http://github.com/input-output-hk/pvss-haskell。
  • 在提交阶段，很多东西被写入区块链。PVSS 相关消息的数量与 𝒎² 成正比，其中 𝒎 是委员会的规模。大型委员会规模导致大量通信和计算开销。这需要成为委员会成员的最低权益限制，以限制委员会的规模。
  • 最低权益限制并不高。他们的意思是你需要一个代表团计划，以便参加的人数少于限制。强制授权基本上是一种社会制度，如投票。如果恶意方通过社交操纵说服了足够多的人投票给他们，那么他们可能会获得超过 50％ 的股份，从而违反了安全模型中的假设。
  • Ouroboros 完全不受操纵影响。即使各方以对抗方式产生随机数（𝒖），它们也无法影响领导者选择种子 ρ。即使他们从未透露过他们的 𝒖，它也会被重建，ρ 将保持不变。Ouroboros 使用同步网络模型来证明其安全性，这意味着所有方的消息不会延迟比时隙延迟。对抗方不能随意拖延某些方面。在 Praos 论文中，如果没有实现这一条件，则会描述对 Ouroboros 的攻击。
  • 攻击者可以提前确定哪些方面最好是提前破坏或入侵，因为当前纪元的时隙领导计划是公开的。该模型假设攻击者在看到 ρ 之后不能立即破坏其他方，这意味着它不能抵御「完全适应性腐败」。
  • 你可以做最好的三个小时的研究来了解如何在 Ouroboros 中使用 PVSS：https：//youtu.be/hMgxZOsTlQc，其中 Bernardo David（Ouroboros、Praos 和 SCRAPE 的合作者）清楚地解释了加密原语。我可能会在以后的帖子中引用它。

Ouroboros Praos

Praos 使用可验证的随机函数（VRF）作为其核心随机生成方案。给定私钥和输入，VRF 方案输出伪随机数和证明。拥有你的公钥和证明的任何人都可以验证该号码是使用给定的输入生成的，但在此之前无法生成该号码。

在 Praos 中，每个纪元都有一个协定的 nonce，所有参与者都必须将其作为 VRF 的输入。对于每个时隙，每个参与者使用其 VRF 和随机数生成随机数。如果该数字小于与其权益成比例的阈值，则他们是该位置的领导者。由于这些随机数是每个参与者独立产生的，因此可以有多个领导者用于一个时段或根本没有。下一个纪元的随机数是从嵌入在前一个纪元的区块标题中的 VRF 值产生的。将一个纪元定义为 24𝒌 长，领导者选择过程运行如下：

  • 对于每个时隙 𝒊，作为权益持有者，你使用 η、𝒊 和任意字符串“TEST”作为输入运行 VRF，以生成随机数 𝘆ᵢ 和证明 πᵢ。如果 𝘆ᵢ<𝗧，你就是时隙领导者，其中 𝗧 与上一纪元开始时你的权益成正比。当你发布区块时，header 和 πᵢ 包含在区块头部中，以便其他人可以验证你是否有资格在时隙中生成块 𝒊。这里有一些伪代码可能会让它更清晰：

T = calculateMyThreshold(myAmountOfStake)

foreach 1..nSlots -&gt; i:

y, proof = VRF(myPrivateKey, concat(epochNonce, i, "TEST"))

if y &lt; T:

getReadyToGenerateBlockAt(i, y, proof)
  • 生成区块时，在同一输入上再次运行 VRF，除了“NONCE”而不是“TEST”以产生 ρᵢ，你也将其放入块头（及其相关证明）。
  • 在一个纪元的末尾，每个参与者在其前 16 个时隙中查看块以产生下一个纪元的 η。从这些块中，它们将所有 ρ 值与先前的 η 连接在一起。散列结果会产生即将到来的时代的 η。每个参与者还更新他们的 𝗧 值以反映刚刚完成时期开始时的权益分配。

注意事项

  • 没有理由拥有参与协议的最低权益限制。对于没有足够利益的人来说，授权可以是可选的，以使盈利有利可图。没有固定的最小值是对 Ouroboros 的重大改进。
  • 操纵攻击是可能但有限的。对手不能随意控制 η，因为它甚至不能随意控制自己块中的 ρᵢ 值（由于 VRF）。能做的就是尝试创造尽可能多的分叉，直到确定 η 的 16𝒌 时隙的末端。它计算出哪一个对自己最有利，并试图确保它最终成为最长的链条。根据该论文的分析，该优点不会改变协议的安全属性。
  • 操纵攻击也受到对手的散列能力的限制。为了比较 η 的不同值的可取性，你必须为每个要比较的 η 生成下一个纪元中每个时隙的所有（或一些大比例）𝘆ᵢ 值。计算每个 𝘆ᵢ 需要多个哈希值。增加协议中计算 𝘆ᵢ 所需的哈希数量不会太多地影响诚实参与者（我们可以简单计算他们的 𝘆ᵢ值），但会大大增加对手从操纵中获得任何好处所需的计算能力。在我看来，诚实与不诚实参与者的这种计算不对称是一个非常酷的特征。
  • 当两个或多个参与者在同一个时隙中当选时，即使他们都是诚实的，他们也会创建一个分支。他们应该是短暂的。对于操纵攻击者来说，在 nonce 确定时隙的末尾有更“诚实的分叉”越好。
  • 该论文表明，如果是分叉，诚实的参与者应该选择他们首先获得的链条（见第 24 页末尾）。这意味着能够更快地传递区块的时隙领导者有更好的机会进入最长的链条。
  • 任意值“TEST”和“NONCE”都是从 ρᵢ 中分离出来的，但是并不完全清楚为什么需要 ρᵢ。我认为这是因为使其成为块的 𝘆ᵢ 值偏向于低数（因为它们必须小于 𝗧），因此不能随机地用于生成 η。
  • Praos 的安全性证明是在半同步模型下完成的，攻击者可以将消息延迟超过一个时隙。根据该报告，间歇性的空位（没有人是时隙领导者）可以抵消这种能力，因为它可以让攻击者延迟一些时间赶上他们。
  • 由于时隙领导者没有提前公开，攻击者在他们发布一个区块之后才能看到谁是时隙领导者。攻击者无法知道具体攻击者是为了提前控制某个时隙。
  • Praos 使用「前向安全」数字签名方案，这意味着块创建者在每次创建块（并删除旧块）时使用不同的私钥，同时保留其公钥。因此，即使攻击者能够破坏一方，他们也无法在已发布的时隙中创建区块。这一点和上面的意思是，与最初的 Ouroboros 不同，Praos 可以抵御完全适应性腐败。
  • Praos 不是唯一使用 VRF 的区块链协议。 Algorand 在 Praos 之前发布并以类似的方式使用VRF，还有 Dfinity。