摘要

基于资源的共识是无许可分布式账本系统的支柱。这种协议的安全性从根本上取决于系统中积极参与的资源水平。各种不同的资源（以及相关的证明协议，有时在文献中被称为 PoX）提出了一个根本问题，即是否有可能同时使用其中的许多资源并建立多资源共识协议。组合不同资源的挑战是实现它们之间的可替代性，从某种意义上说，只要所有资源中累积的对抗力量是有限的，安全就会保持不变。

在这项工作中，我们提出了 Minotaur，一种结合了工作证明（PoW）和权益证明（PoS）的多资源区块链共识协议，并证明了它是最优可替代的。在我们设计的核心中，Minotaur 以轮次为单位进行操作，同时不断对主动计算能力进行采样，以提供工作和权益这两种资源之间的公平交换。此外，与比特币区块链相比，我们展示了 Minotaur 处理更高程度工作波动的能力；我们还将 Minotaur 推广到任何数量的资源。

我们通过在 Rust 中实现一个全栈客户端（已开源）来证明 Minotaur 的简单性。我们使用客户端来测试 Minotaur 对可变采矿能力和联合工作/权益攻击的鲁棒性，并证明 Minotaur 适合作为真实世界区块链的共识层的具体经验证据。

CCS CONCEPTS

安全和隐私 —— 分布式系统安全

关键词

工作证明，权益证明，基于资源的区块链，安全分析

ACM 引用格式

Matthias Fitzi, Xuechao Wang, Sreeram Kannan, Aggelos Kiayias, Nikos Leonardos, Pramod Viswanath, and Gerui Wang. 2022. Minotaur: MultiResource Blockchain Consensus. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS ’22), November 7–11, 2022, Los Angeles, CA, USA. ACM, New York, NY, USA, 14 pages. https://doi.org/10.1145/3548606.3559356

1 介绍

基于资源的共识。 无许可区块链的去中心化计算范式的基本特征是，通过证明对某一资源的占有来实现对共识协议的参与。比特币开创了基于工作证明（PoW）的这一理念，其隐含的能源浪费激发了基于替代资源的新设计，如权益证明（PoS）、空间证明（PoSp）和消逝时间证明（PoD）。这些不同的资源涵盖了参与者带来的各种多维形式的“资本”。每个 X 证明机制在适当的设置（在 PoW 中的计算，PoSp 的存储和存储以及 PoD 中的时间/延迟，PoS 中的标记/资本的时间/延迟）都很有趣。此外，即使在同一资源格式中，这些机制也会引发不同的激励措施；以 PoW 为例，我们看到比特币中实现的 SHA256 函数实例化的哈希现金算法已经被其他算法取代，包括 scrypt 和 ethash。这些不同的 X 证明机制都导致了不同的、孤立的区块链生态系统。

结合不同的资源。 跨多种资源进行结合是一个自然的问题。结合多种资源的关键挑战在于确定汇率，即不同资源在多大程度上转化为系统的权力，并以最佳方式从这些资源中提取安全。使汇率动态地适应每一种资源类型的参与水平，形成一个真正可替代的资源概念，是一个基本的和根本的目标。所谓真正的可替代性，我们的意思是，只要诚实的参与者控制了系统中每种资源类型的大部分组合资源，多资源共识协议的安全性就能得到保证 —— 具体来说就是，∑i=1Mβi<M/2\sum_{i=1}^M \beta_i < M/2，其中 MM 是资源的数量，βi\beta_i 是第 ii 个资源中的对抗力量（此属性在定义 2 中适当地推广到任何线性组合）。我们注意到，实现这种类型的可替代性有利于底层区块链系统的安全，因为对手将无法通过指挥其中一个底层资源中的 51% 来发动成功的攻击。接下来，我们给出了一些非可替代的混合 PoW/PoS 协议设计的例子。

一阶混合 PoW/PoS 协议。 考虑到在单一区块链设计中包含多种资源的基本重要性，在文献中有多种混合 PoW/PoS 协议的设计。然而，这些协议要么是启发式的（缺乏正式的安全分析），要么是做了打破可替代性的假设（例如，诚实的多数股权和/或静态采矿能力）。事实上，有了足够的假设，混合协议的问题就很容易得到解决。例如，如果我们假设有一个诚实的多数股权（在任何时候），我们可以使用一个从利益相关者池中随机选择的委员会，通过定期发布检查点来协助 PoW 分类账。然而，这个方案的安全性完全由利益相关者保证，而且信任完全由 PoS 支持（不是来自 PoW）。

自然解决方案。 事实上，如果我们假设一个静态设置（总的采矿能力和总的“活跃”股权都是固定的，并且为协议设计者所知），一个简单的解决方案是：PoW 和 PoS 挖矿是平行进行的；无论哪个 PoW 或 PoS 先成功，都会继续下去并扩展最长的链。然而，似乎没有任何直接的方法将这个简单的想法扩展到非静态设置，因为当总的采矿能力是变化和未知的时候，我们不能再将系统中的股权和工作归一化（第 4 节）。即使是来自两个不同哈希函数的可替代工作组合（即诚实工作总量超过拜占庭工作总量）也没有得到解决。

Minotaur 协议。 在本文中，我们提出了 Minotaur，一个具有可互换工作和股权证明的区块链协议。在其核心，Minotaur 是一个最长的链式协议，它的区块提议者时间表基于我们的虚拟股权概念，融合了活跃的实际股权和工作股权。工作权益分配是通过衡量参与者在前一个时期的哈希算力贡献来确定的。工作贡献是通过对 PoW 区块（类似于“背书输入”或“果实”）的并发 PoW 挖掘来实现的，最终被主链区块所引用。然后，工作份额分配被按比例分配给参与者在该时代从主链上引用的认可者区块份额；该分配确实真正代表了参与者之间的 PoW 资源分配。图 1(a) 阐述了这个协议。

Minotaur 的安全是最佳的。我们通过证明当 ω\omega 乘以对抗者哈希算力的比例（βw\beta_w）和 1−ω1-\omega 乘以对抗者股权的比例（βs\beta_s）之和小于 1/21/2 时，对于任何 ω∈[0,1]\omega \in [0,1]（即 PoW/PoS 的权衡参数，见图 1(b)），Minotaur 在工作和股权之间是真正可替换的。图 1(b) 还比较了 Minotaur 和文献中的几个不可替换的 PoW/PoS 协议（检查点账本、2 跳区块链和一些最终性小工具）的安全保证。在第 6 节我们给出了一个正式的安全分析。一个直接的后果是，Minotaur 可以容忍 51% 的采矿对手，只要有一个超级多数的诚实股权（反之亦然，一个 51% 的股权对手）。我们证明了我们的安全保证是最优的，见第 3 节。我们还表明，Minotaur 能够比比特币更有效地容忍工作的波动，参见第 6.4 节。

实现。我们在大约 6000 行 Rust 代码中实现了 Minotaur 客户端的原型，并提供了实验结果来评估 Minotaur 在不同场景下的性能。我们还实施了比特币/水果链/Ouroboros 客户端作为基准。我们用这个客户端来实验验证 Minotaur 可以在网络哈希力更剧烈的变化中存活下来，而 Bitcoin/FruitChain 在同样的情况下已经不复存在。

动机。结合多种资源有助于防止对手可能获得对一种单一资源的大部分控制，但不能控制所有相关资源的组合的情况。例如，为了违反 ω=0.5\omega=0.5 的 PoW/PoS 情况下的安全性，控制一半哈希功率的对手现在还需要控制一半的股权。

作为一个具体的例子，考虑推出一个新的区块链。一个 PoS 链可以很容易地用现有的技术启动，如烧毁证明、初始硬币发行和空投。相比之下，PoW 链的引导是具有挑战性的，因为新系统开始时的总计算能力可能相对较小，因此容易受到“51% 攻击”。为了防御这种情况，Minotaur 允许在纯 PoS 模式下启动一个（预测的）PoW 区块链（设置参数 ω=0\omega=0），然后通过逐渐改变权重参数 ω\omega 到一个较高的值来过渡到一个纯 PoW 区块链，从而允许安全地提高应用的散列功率，直到达到一个安全的参与水平。

图表 1：(a) Minotaur 共识协议的结构。(b) 不同混合 PoW/PoS 协议的安全区域对比

图表 1：(a) Minotaur 共识协议的结构。(b) 不同混合 PoW/PoS 协议的安全区域对比

相关工作。混合 PoW/PoS 块生产的想法首次在文献中提到，并在“活动证明”的标签下给出了第一个具体的构造，但没有给出严格的安全分析。他们的区块生产机制本质上扩展了标准的比特币挖矿，让挖出的区块隐含地选出一组利益相关者，这些利益相关者需要在区块上签名以验证它。

另一个类似的结构被提出，并被证明在大多数对手的散列能力下是安全的 —— 然而，他们的安全证明仍然意味着一个诚实的大多数股权。特别是，该协议没有被证明在任何少数组合资源被对手控制的条件下是安全的。后续工作也探索了动态参与、散列能力和股权的适应，以及将 PoW 与多种资源（而不仅仅是 PoS）相结合，但这部分工作缺乏严格的安全分析。

此外，还存在另一类混合 PoW/PoS 协议，它使用 BFT 协议（PoS）在中本聪式最长链协议（PoW）的基础上建立一个最终性小工具/层，以实现问责和最终性等重要特性。然而，这些协议需要在矿工和利益相关者的集合上获得诚实的多数（甚至是超级多数），因此它们是不可替换的。

2 预设

2.1 安全模型

时间，时段和同步。我们考虑的环境是，时间被划分为不连续的单位，称为时段（slot）。玩家配备了大致同步的时钟。时段以整数为索引，并进一步分组为固定大小为 RR 的轮次（epoch），即轮次 ee 由时段 {(e−1)R+1,(e−1)R+2,…,eR}\{(e-1)R+1, (e-1)R+2, \ldots, eR\} 组成。而我们假设与每个时段对应的实时窗口具有两个特性：（1）当前时段由一个公开的、单调增长的当前时间函数决定；（2）每个玩家都能获得当前的时间，与一个时段的时间相比，各方的当地时间的任何差异都是微不足道的。我们在现在标准的 Δ\Delta-同步网络模型中描述我们的协议，其中对手可能对任何信息的传递造成的延迟（以时隙数衡量）有一个（未知）的上限 Δ\Delta。协议的执行在时段中进行，输入由环境程序提供，用 Z(1κ)Z(1^\kappa) 表示，给执行协议 Π\Pi 的各方，其中 κ\kappa 是一个安全参数。该网络允许消息排序被对手 AA 控制，即 AA 可以注入消息进行选择性传递，但不能改变诚实方的消息内容，也不能阻止它们在 Δ\Delta 时段的延迟内被传递。

协议玩家。该协议由两类玩家执行，即 PoW 矿工（简称矿工）和 PoS 持有者（简称利益相关者），他们产生不同类型的区块，即 PoW 区块和 PoS 区块。

随机预言。对于 PoW 挖掘，我们将哈希函数抽象为一个随机预言功能。它接受的查询形式为 (compute,x)(compute, x) 和 (verify,x,y)(verify, x, y)。对于第一种类型的查询，从 {0,1}κ\{0,1\}^\kappa 中抽出一个值 yy，并将其输入到一个表 THT_H。对于第二种类型的查询，要对表进行查找操作。诚实的矿工被允许在每个时段提出一个 computecompute 类型的查询和无限的 verifyverify 类型的查询。

对资源的对抗性控制。我们假设有一个拜占庭式的对手，他可以自适应地破坏矿工。在一个时段 rr 中，协议中活跃的诚实矿工的数量用 hrh_r 表示，rr 时段中所有活跃矿工的数量用 nrn_r 表示。为了在足够长的窗口中获得有意义的 PoW 区块数量的集中界限，我们对诚实采矿能力的部分设定了一个下限 α0\alpha_0，即对于所有 rr，hr≥α0nrh_r \ge \alpha_0 n_r。我们需要以某种有限的方式限制诚实/对抗性查询数量的波动。

定义 1（波动限制）。对于 γ∈[1,∞)\gamma \in [1,\infty)，我们称一个序列 (xr),r∈[LR](x_r), r \in [LR] 是 (γ,s)(\gamma,s)-尊重的，如果对于任意的集合 S⊆[0,LR]S \subseteq [0,LR]，在大多数的连续时段中有：

max⁡r∈Sxr≤γmin⁡r∈Sxr \max_{r \in S} x_r \le \gamma \min_{r \in S} x_r

我们就说 ZZ 是 (γ,s)(\gamma,s)-尊重的，如果对于所有的 AA 和整个执行过程中的所有槽，序列 (hr)(h_r) 和 (nr)(n_r) 也是 (γ,s)(\gamma,s)-尊重的。

最后，Minotaur 通过可互换工作和股权的证明来实现共识。以下是可替换性的正式定义和我们对对抗性权力的主要假设。

定义 2（资源的可替代性）。对于一个时间窗口 WW，让 βsW\beta_s^W 是 WW 中对抗性股权的最大比例；让 βwW\beta_w^W 是 WW 中所有时段的对抗性采矿能力的最大比例（即 βwW=1−min⁡r∈Whr/nr\beta_w^W = 1 - \min_{r \in W} h_r/n_r）。对于 θ∈[0,1]\theta \in [0, 1]，如果对于任何有最多 mm 个时段的时间窗口 WW，我们有 ωβwW+(1−ω)βsW≤θ\omega \beta_w^W + (1 - \omega) \beta_s^W \le \theta，我们就说对手 AA 是 (θ,m,ω)(\theta,m,\omega)-有界的。我们说，如果一个区块链协议对这样的对手是安全的，它就实现了工作和股权的可替代性。

为了简化分析，Minotaur 协议将依赖于下面的初始化假设：

假设 1（初始化）。在协议的初始化阶段，我们假设：

  • 1.1 初始股权分布具有诚实多数，即 βs0≤1/2−σ\beta_s^0 \le 1/2-\sigma，其中 βs0\beta_s^0 是由对手控制的初始股权的比例。我们对初始诚实采矿能力 h1h_1 有一个很好的估计。特别是，让 h~1\tilde{h}_1 是 h1h_1 的估计值，我们有 h1/(1+δ)γ2≤h~1≤γ2h1/(1−δ)α0h_1/(1+\delta)\gamma^2 \le \tilde{h}_1 \le \gamma^2 h_1 / (1-\delta)\alpha_0。
  • 1.2 初始化后，我们将上述内容放宽到下面描述的可替换资源假设。

假设 2（执行阶段）。在协议的执行阶段，我们假设：

  • 2.1 股权-工作约束：对手 AA 是 (1/2−2σ,2R,ω)(1/2-2\sigma, 2R, \omega)-有界的。
  • 2.2 工作波动约束：环境 ZZ 是 (γ,2R)(\gamma, 2R)-尊重的。
  • 2.3 工作参与约束：对于任意的时段 r∈[LR]r \in [LR]，hr≥α0nrh_r \ge \alpha_0 n_r。

参与模式。Minotaur 可以基于不同的 PoS 最长链协议来构建。各种版本的 Minotaur 将采取以下参与模型的不同假设子集：

  • (P1) 诚实的利益相关者总是在线。
  • (P2) 在轮次 ee 中开采了 PoW 区块的诚实矿工将在轮次 e+2e+2 中保持在线。
  • (P3) 如果一个诚实的一方在协议开始后加入，其由环境提供的初始化链 CC 应该与在前一个时段活跃的诚实一方的链相匹配。

2.2 区块链安全属性

注释 1。我们用 C⌈lC^{\lceil l} 表示“修剪”时间戳在最后一个时段内的 ll 个块所产生的链。如果 C1C_1 是 C2C_2 的前缀，我们写 C1≺C2C_1 \prec C_2。链中最新的区块 CC 被称为链的头部，用 head(C)head(C) 表示。我们用 C1∩C2C_1 \cap C_2 表示链 C1C_1 和 C2C_2 的共同前缀。给定一个链 CC 和一个区间 SS（或 [r1,r2][r_1,r_2]），让 C(S)C(S) 是 CC 的一段，包含时间戳在 SS 的区块。如果一个链 CC 是其视图中的最佳链之一，我们就说它是由一个诚实节点持有或属于该节点。

定义 3（共同前缀（CPCP））。参数为 lcp∈Nl_{cp} \in \mathbb{N} 的共同前缀属性指出，对于任何两个在时段 r1,r2r_1, r_2 持有链 C1,C2C_1, C_2，且 r1≤r2r_1 \le r_2 的诚实节点，持有 C1⌈lcp≺C2C_1^{\lceil l_{cp}} \prec C_2。

定义 4（存在性链质量（∃CQ∃CQ））。参数为 lcq∈Nl_{cq} \in \mathbb{N} 的存在链质量属性指出，对于任何诚实的一方在时段 rr 持有的任何链 CC，以及至少有 lcql_{cq} 个连续时隙的任何区间 S⊆[0,r]S \subseteq [0,r]，C(S)C(S) 中至少有一个诚实生成的块。

我们的目标是生成一个健壮的交易账本，满足以下持久性和活跃性。

定义 5（健壮交易账本）。如果一个协议 Π\Pi 将账本组织成交易的区块链，并且满足以下两个属性，那么它就能维护一个健壮的公共交易账本：

  • 持久性：考虑任何节点 p1p_1 上的确认账本 L1L_1 在任何时段 r1r_1，以及任何节点 p2p_2 上的确认账本 L2L_2 在任何时段 r2r_2。如果 r1+Δ<r2r_1+\Delta < r_2，那么 L1L_1 是 L2L_2 的前缀。
  • 活跃性：以 u∈Ru \in \mathbb{R} 为参数，如果一个交易 txtx 被所有诚实节点收到超过 uu 个时段，那么所有诚实节点将在确认的分类帐中的同一位置包含 txtx。

3 不可能的结果

考虑由矿工和利益相关者这两类人执行的任何协议 Π\Pi，让 DΠ∗D_\Pi^* 成为 (βw,βs)(\beta_w, \beta_s) 的安全区域，在对手控制 βw\beta_w 比例的采矿能力和 βs\beta_s 比例的股权的情况下，Π\Pi 可以生成一个稳健的公共交易账本。

定理 3.1。任何两个点 X1=(p1,q1)X_1=(p_1,q_1) 和 X2=(p2,q2)X_2=(p_2,q_2)，满足 p1+p2≥1p_1+p_2 \ge 1 和 q1+q2≥1q_1+q_2 \ge 1，在 DΠ∗D_\Pi^* 中不能共存。

证明。我们表明，如果存在一个协议 Π\Pi 在 X1X_1 和 X2X_2 两点下都是安全的，那么我们可以用 Π\Pi 来实现一个有两个玩家的稳健交易账本，其中一个是拜占庭的，这是不可能的。

让 Alice 和 Bob 是两个玩家，其中一个可能是恶意的。让 Alice 控制 p1p_1 比例的采矿能力和 1−q21-q_2 比例的股权。让 Bob 控制 1−p11-p_1 比例的采矿能力和 q2q_2 比例的股权。在 Alice 是恶意的情况下，p1p_1 比例的采矿能力和 1−q2≤q11-q_2 \le q_1 比例的股权是恶意的，这由 X1X_1 点支配。在 Bob 是恶意的情况下，1−p1≤p21-p_1 \le p_2 比例的采矿能力和 q2q_2 比例的股权是恶意的，这由 X2X_2 点支配。假设 Π\Pi 实现了一个稳健的公共交易账本，意味着当其中一个人是恶意的时候，两个玩家之间的协议也是如此。然而，这与容忍 1 个恶意玩家至少需要 3 个玩家的经典共识下界相矛盾。

图表 2 给出了一些满足定理 3.1 约束条件的可能的最大安全区域的例子。

图表 2：满足定理 3.1 约束条件的安全区域

图表 2：满足定理 3.1 约束条件的安全区域

推论 1。没有任何协议 Π\Pi 能在 (1/2,m,⋅)(1/2, m, \cdot)-有界的对手下产生一个稳健的公共交易账本。 因此，推论 1 意味着假设 2.1 不仅是充分的，也是必要的。

4 基线方法

在这一节中，我们提供了几个自然设计的混合 PoW/PoS 协议，它们未能实现 Minotaur 的全部目标。

想法 1：通过检查点保证 PoW 链的安全。 检查点分类帐采用了一组从利益相关者池中随机选择的委员会来协助 PoW 分类账，在区块创建后不久就完成了区块。最终的区块被称为检查点，最终的账本由检查点链形成。这种机制也可以保证 PoW 账本在存在对抗性采矿多数的情况下的安全，但安全性完全由外部集合或利益相关者保证。

想法 2：在 PoW 和 PoS 区块之间进行平滑插值。在静态环境下（总的采矿能力和总的活跃股权都是固定的，协议设计者都知道），有一个简单的协议也可以实现图 1(b) 中红线所定义的区域。在这个协议中，PoW 和 PoS 挖矿是平行进行的，遵循最长链规则。在初始化阶段，我们调整采矿目标，使 PoW 区块的采矿率为 ωf\omega f，PoS 区块的采矿率为 (1−ω)f(1-\omega)f。

然而，很难将这个简单的想法扩展到非静态环境中，尤其是可变采矿能力。为了保证非静态设置的安全性，我们需要确保每个轮次中 PoW 区块和 PoS 区块的总开采率的比率是一个常数 ω/(1−ω)\omega/(1-\omega)。然而，这在可变采矿能力设置中是不可能实现的，因为对手总是可以决定隐藏或释放其 PoW 区块，这样就没有办法准确估计总采矿能力。

5 完整协议

在这一节中，我们将对我们的协议 Minotaur 进行详细描述。该协议建立在基于纪元的 PoS 最长链协议上（例如 Ouroboros Classic, Praos, 或 Genesis）。

与原始的 Ouroboros 协议相比，区块提议者时间表通过虚拟股权来说明这两种资源，虚拟股权是实际股权（代表原始协议中的股权）和工作股权的组合，代表归属于 PoW 资源的区块生产权份额。

此外，PoW 矿工通过开采代言人区块（类似于“背书输入”或“果实”）参与。每个纪元都会被分配一定数量的工作股份，分配给各矿工的工作股份与他们在一个纪元内从主链引用的 PoW 区块的贡献成正比。

现在我们详细介绍该协议。该协议在固定时间的轮次中运行，每个轮次有 RR 个时段。

  • PoW 挖矿：在一个轮次 ee 中的时段 slsl，一个矿工挖了一个 PoW 区块，如果： H(pk,sl,h,mr,monce)<Te H(pk, sl, h, mr, monce) < T_e 其中 pkpk 是矿工的公钥，hh 是最后确认的 PoS 区块的哈希值，mrmr 是有效载荷的 Merkle 根，TeT_e 是轮次 ee 中的挖矿目标。如果一个 PoW 区块指的是不早于 slnow−slresl_{now}-sl_{re} 时段开采的确认的 PoS 区块，那么它在当前时段被称为最近的区块。
  • PoS 挖矿：在轮次 ee 的 slsl 时段中，一个或多个利益相关者被选中。被选中的概率与它的相对“虚拟”股权（实际股权与工作股权之总和）成正比。在每个轮次开始时，我们将总的工作权益设定为系统中实际权益的 ω/(1−ω)\omega / (1-\omega) 倍。而在轮次 ee 中使用的工作权益分布被设定为轮次 e−2e-2 中 PoS 区块所指的 PoW 区块难度分布。
  • 调整 PoW 挖矿目标：对于轮次 ee，TeT_e 根据 De−1totalD_{e-1}^{total} 调整，即： Te=f(w)R/De−1total T_e = f^{(w)} R / D_{e-1}^{total} 其中 f(w)f^{(w)} 是一个协议参数，代表每槽区块数量的预期 PoW 开采率。（对于 e=2e = 2，T2=f(w)(R−k)/D1totalT_2 = f^{(w)}(R - k)/D_1^{total}。）
  • 链式选择规则：我们使用以下链式选择规则之一：
    • maxvalid-mc（需要一个可信的第三方来引导，即假设(P3)）：它更喜欢较长的链，除非新链相对于当前持有的链分叉超过 kk 块（在这种情况下，新链将被丢弃）。
    • maxvalid-bg（支持从创世开始引导）：如果新的链 C′C' 相对于当前持有的链 CC 来说分叉少于 kk 个块，则倾向于长链。若分叉超过 kk 块，如果 C′C' 在最后一个共同区块之后的 ss 个槽位中增长得更快，则 C′C' 仍将是首选。

6 安全分析

6.1 主要理论

定理 6.1。在假设 1、假设 2 和假设 (P1)-(P3) 下，当在锁步同步模型中执行时，用 Ouroboros 构建的 Minotaur 生成的交易账本以压倒性的概率满足持久性和灵活性。

定理 6.2。在假设 1、假设 2 和假设 (P1)-(P3) 下，当在 Δ\Delta-同步模型中执行时，用 Ouroboros Praos 构建的 Minotaur 产生了一个交易账本，以压倒性的概率满足持久性和有效性。

定理 6.3。在假设 1、假设 2 和假设 (P1)-(P2) 下，当在 Δ\Delta-同步模型中执行时，用 Ouroboros Genesis 构建 of Minotaur 产生了一个交易账本，以压倒性的概率满足了持久性和有效性。

6.2 使用 Ouroboros 的安全性

6.2.1 单轮次安全

定理 6.4。设 κ,R,Δ∈N,σ∈(0,1)\kappa, R, \Delta \in \mathbb{N}, \sigma \in (0,1)。让 βv\beta_v 是满足以下条件的对抗性虚拟桩的比例：

βv≤1/2−σ \beta_v \le 1/2-\sigma

那么对手在 RR 个时段内违反参数 lcp=κl_{cp} = \kappa 的 CP 和参数 lcq=κl_{cq} = \kappa 的 ∃CQ\exists CQ 的概率不超过 Re−Ω(κ)R e^{-\Omega(\kappa)}，其中 Ω(⋅)\Omega(\cdot) 隐藏的常数取决于 σ\sigma。

6.2.2 FruitChain 参数

对于一组时段 SS，我们定义 h(S)=∑r∈Shrh(S)=\sum_{r \in S} h_r 和 n(S)=∑r∈Snrn(S)=\sum_{r \in S} n_r。为了在足够长的窗口中获得有意义的 PoW 区块数量的集中界限，我们对诚实采矿能力的部分设定了一个下限 α0\alpha_0，即对于所有 rr，hr≥α0nrh_r \ge \alpha_0 n_r。

根据共同前缀属性，前缀 C⌈κC^{\lceil \kappa} 是稳定的。我们设置最近参数 slre=3κ+Δsl_{re} = 3\kappa + \Delta。

定理 6.5（水果新鲜度）。如果 slre=3κ+Δsl_{re} = 3\kappa + \Delta，在 rr 时段开采的诚实 PoW 区块将在 r+rwaitr + r_{wait} 之前被纳入稳定的链中，其中 rwait=2κ+Δr_{wait} = 2\kappa + \Delta。

证明。假设一个诚实的 PoW 区块 BwB_w 在 r0r_0 时段被开采，而 PoS 链 C0C_0 被采用，那么 BwB_w 将引用 C0⌈κC_0^{\lceil \kappa} 的顶端作为最后确认的 PoS 区块。此外，根据 ∃CQ\exists CQ 属性，C0⌈κC_0^{\lceil \kappa} 的顶端有时间戳 r1≥r0−2κr_1 \ge r_0 - 2\kappa。通过时段 r0+Δr_0 + \Delta，所有诚实的节点将收到 BwB_w。让 r2=r0+2κ+Δr_2 = r_0 + 2\kappa + \Delta，CC 是由诚实节点在时段 r2r_2 持有的任何链，那么同样根据 ∃CQ\exists CQ，CC 上存在一个诚实块 BsB_s，其时间戳 r3r_3 在区间 [r2−2κ,r2−κ][r_2 - 2\kappa, r_2 - \kappa] 内。我们检查 BwB_w 在 r3r_3 槽位上仍然是最近的，因为：

r3−r1<(r2−κ)−(r0−2κ)=3κ+Δ=slre r_3 - r_1 < (r_2 - \kappa) - (r_0 - 2\kappa) = 3\kappa + \Delta = sl_{re}

由于 BsB_s 是在 r0+Δr_0 + \Delta 之后开采的诚实区块，BsB_s 或 BsB_s 的祖先必须包括 BwB_w。由于 BsB_s 在 CC 中是在 r2r_2 时段上稳定的，我们有 rwait=r2−r0=2κ+Δr_{wait} = r_2 - r_0 = 2\kappa + \Delta。

图表 3：证明简图

图表 3：证明简图

命题 1。在一个 (γ,s)(\gamma,s)-尊重的环境中，让 UU 是一个最多有 ss 个连续时段的集合，S⊆US \subseteq U。然后对于任意的 h∈{hr:r∈U}h \in \{h_r : r \in U\} 和任意的 n∈{nr:r∈U}n \in \{n_r : r \in U\}，我们有：

h/γ≤h(S)/∣S∣≤γh,n/γ≤n(S)/∣S∣≤γn h/\gamma \le h(S)/|S| \le \gamma h, \quad n/\gamma \le n(S)/|S| \le \gamma n

以及：

h(U)≤(1+γ∣U\S∣/∣S∣)h(S),n(U)≤(1+γ∣U\S∣/∣S∣)n(S) h(U) \le (1+\gamma|U \backslash S|/|S|)h(S), \quad n(U) \le (1+\gamma|U \backslash S|/|S|)n(S)

定义 6（好的轮次）。如果满足以下条件，则称时段 ee 是好的：

(1−δ)α0f/γ≤ph(e)Te≤(1+δ)γf (1-\delta)\alpha_0 f / \gamma \le p h^{(e)} T_e \le (1+\delta)\gamma f

其中 p=1/2κp = 1/2^\kappa，h(e)=h(e−1)R+1h^{(e)} = h_{(e-1)R+1}，为轮次 ee 的第一个时段中诚实查询的数量。

命题 2。在一个 (γ,2R)(\gamma,2R) 尊重的环境下，如果时段 rr 在轮次 ee 中是一个好的时段，那么：

(1−δ)α0fγ2≤phrTe≤(1+δ)γ2f \frac{(1-\delta)\alpha_0 f}{\gamma^2} \le p h_r T_e \le (1+\delta)\gamma^2 f

定义 8（公平性）。我们说协议具有（近似的）(W0,σ)(W_0,\sigma)-公平性，如果对于任何 ϕ\phi（α0≤ϕ<1\alpha_0 \le \phi < 1），任何 ϕ\phi-分数的诚实子集 HH，以及任何诚实矿工在 rr 时段持有链 CC 和任何间隔 S0⊆[0,r]S_0 \subseteq [0,r]（至少有 W0W_0 个连续的时段），HH 所开采的 C(S0)C(S_0) 中包含的 PoW 区块的总难度至少为 (1−σ)ϕd(1-\sigma)\phi d，其中 dd 是 C(S0)C(S_0) 中包含的所有 PoW 区块的总难度。

定义 9（典型执行）。如果以下条件成立，一个执行 EE 就是典型的：

  1. 对于任何一个至少有 ll 个连续好时段的集合 SS，满足 D(S)<(1+ϵ)ph(S)D(S) < (1+\epsilon)p h(S)。
  2. 对于任何由至少 ll 个连续好时段组成的集合 SS，让 JJ 是 SS 中对抗性查询的集合。如果满足目标 TT 的合理范围，则： D(S)+A(J)<(1+ϵ)p(h(S)+∣J∣) D(S) + A(J) < (1+\epsilon)p (h(S) + |J|)
  3. 对于任意的集合 SS（至少有 l/ϕl/\phi 个连续的好时段），满足 DH(S)>(1−ϵ)pnH(S)D^H(S) > (1-\epsilon)p n^H(S)。

为了获得有意义的集中度，我们考虑窗口大小至少为：

l≜2(1+ϵ/3)ϵ2γ3(1−δ)α0fλ l \triangleq \frac{2(1+\epsilon/3)}{\epsilon^2 \gamma^3 (1-\delta)\alpha_0 f} \lambda

其中 λ\lambda 为系统的典型性参数。

我们要求协议参数满足：

R−3κ−Δ≥l/α0≥γϵ(4κ+Δ)(C1) R-3\kappa-\Delta \ge l / \alpha_0 \ge \frac{\gamma}{\epsilon} (4\kappa + \Delta) \tag{C1}

并且：

4ϵ≤δ≤1(C2) 4\epsilon \le \delta \le 1 \tag{C2}

定理 6.8（公平性）。对于在一个 (γ,2R)(\gamma, 2R)-尊重的环境中的典型执行，具有最近参数 slre=3κ+Δsl_{re} = 3\kappa + \Delta 的协议满足 (W0,σ)(W_0,\sigma)-公平性，其中 W0=l/α0+3κ+ΔW_0 = l/\alpha_0 + 3\kappa + \Delta 并且 σ=4ϵ\sigma = 4\epsilon。

证明。让 S0={u:r1≤u≤r2}S_0 = \{u : r_1 \le u \le r_2\} 是一个至少有 W0W_0 个连续时段的窗口。让 C(S0)C(S_0) 是 CC 中包含时间戳在 S0S_0 中的 PoS 块的部分，让 dd 是其包含的所有 PoW 块的总难度。

让 S1={u:r1−(4κ+Δ)≤u≤r2+κ}S_1 = \{u : r_1-(4\kappa+\Delta) \le u \le r_2+\kappa\}，S2={u:r1≤u≤r2−(3κ+Δ)}S_2 = \{u : r_1 \le u \le r_2-(3\kappa+\Delta)\}，JJ 是 S1S_1 中与该区块相关的对抗者查询的集合。要证明 σ\sigma-公平性，只需证明：

DH(S2)≥(1−σ)ϕ(D(S1)+A(J)) D^H(S_2) \ge (1-\sigma)\phi(D(S_1) + A(J))

在一个典型执行中，根据定义有：

DH(S2)>(1−ϵ)pnH(S2)≥(1−ϵ)ϕpn(S2) D^H(S_2) > (1-\epsilon)p n^H(S_2) \ge (1-\epsilon)\phi p n(S_2)

且：

D(S1)+A(J)<(1+ϵ)p(h(S1)+∣J∣)=(1+ϵ)pn(S1) D(S_1) + A(J) < (1+\epsilon)p (h(S_1) + |J|) = (1+\epsilon)p n(S_1)

根据（C1），我们有：

n(S1)≤(1+γ∣S1\S2∣∣S2∣)n(S2)≤(1+γ8κ+2Δl/α0)n(S2)≤(1+2ϵ)n(S2) n(S_1) \le \left(1+\gamma\frac{|S_1 \backslash S_2|}{|S_2|}\right)n(S_2) \le \left(1+\gamma\frac{8\kappa+2\Delta}{l/\alpha_0}\right)n(S_2) \le (1+2\epsilon)n(S_2)

最后，通过设定 σ=4ϵ\sigma=4\epsilon，我们结束了证明。

6.3.3 从单轮次到多轮次的提升论证

定理 6.9（定理 6.1 的重述）。在假设 1、假设 2 和假设 (P1)-(P3) 下，当在锁步同步模型中执行时，用 Ouroboros 构建的 Minotaur 产生了一个交易账本，在 LL 个轮次期间满足持久性和有效性，概率为 1−RL(e−Ω(κ)+e−λ)1-RL(e^{-\Omega(\kappa)}+e^{-\lambda})。

其在论文的完整版本中给出。它表明对 δ2κ\delta^2 \kappa 的依赖性无法进一步提高。

6.4 与比特币的比较

在这一段中，我们观察到 Minotaur（当在纯 PoW 情况下执行时，ω=1\omega=1）比比特币对 PoW 参与度的波动更稳健。

考虑比特币的情况，即最初有 nn 个诚实方，目标为 TT。每个时段的成功概率为 f=1−(1−pT)n≈pTnf = 1 - (1 - pT)^n \approx pTn。我们将表明，对于 s=⌊m/pTn⌋s = \lfloor m / pTn \rfloor，在一个 (2,s)(2,s)-尊重的环境中有效性可能失败。在该环境中，对手被允许每隔 s≈m/fs \approx m/f 时段将各方的数量减半。

攻击以 ss 个时段为单位进行，在此期间，对手不挖矿，也不延迟信息。对手在每个阶段开始时将各方的数量减半。让 NiN_i 表示第 ii 阶段的诚实方数量，N0=nN_0=n，Ni=n/2iN_i = n/2^i。在阶段 ii 中期望的成功的时段的数目为：

s⋅[1−(1−pT)Ni]<spTNi=spTn/2i≤m/2i s \cdot [1-(1-pT)^{N_i}] < s pT N_i = s pT n / 2^i \le m / 2^i

在前 jj 个阶段计算的预期块数为：

m/2+m/4+…+m/2j≈m m/2 + m/4 + \ldots + m/2^j \approx m

随着各方的数量每两周减半，比特币可能会因为难度无法及时调低而陷入“死锁”，而 Minotaur 则可以通过对主动计算能力的细粒度采样安全度过这一波动。