Setup-and-Goals.md

设置和⽬标

本⽂的主要⽬标是描述和证明具有某些安全性和活性声明的权益证明区块链的属性。在本节中，我们将介绍共识协议和区块链的⼀些⼀般背景。由于⽂献使⽤的词汇多种多样，本节的主要⽬的是为本⽂的其余部分选出⼀组特定的词汇。

2.1 共识协议、验证者、区块链

我们的⽬标是创建⼀个共识协议($consensus\ protocol$，或简称为协议），这是⼀套经过商定的算法，供⼀组实体（节点、⼈员等）遵循，以获得其状态的共识历史，即使⽹络不可靠和/或许多验证者是恶意的。

我们将参与协议验证的实体（⼈员、程序等）称为集合 $V$。他们之所以被称为“验证者”，是因为他们承担着以太坊 2.0 信标链中的数据验证⻆⾊，尽管该⻆⾊的具体内容不属于我们的抽象协议。其他著作对同⼀概念使⽤了许多不同的词语：例如经典 PBFT ⽂献中的“副本”（"replicas"）、DPoS 和 EOS 中的“区块⽣产者”（"block producers"）、Peercoin 和 Nxt 上的“对等者”（"peers"）或 Tezos 上的“⾯包师”（"bakers"）。验证者在（点对点）⽹络上相互连接，这意味着它们可以相互⼴播消息（基本上是数据包）。在我们感兴趣的协议类型中，主要的消息类型是区块，它们收集消息的捆绑包。第⼀个区块称为创世区块，充当初始“⽩板”状态。其他块是状态转换描述，带有指向⽗块的指针。区块链只是这种共识协议的实例（即具有特定的⽹络条件、验证者等），在其中，我们使用区块来构建整体状态。

我们不希望⽹络上看到的所有区块都被接受为共同历史，因为区块可能会相互冲突。这些冲突可能是出于诚实的原因（例如⽹络延迟），也可能出于恶意的原因（例如拜占庭验证者想要双重⽀付）。拜占庭（Byzantine） 是指分布式系统中的⼀个经典问题，即拜占庭将军问题（the Byzantine Generals Problem），在这种情况下⽤于描述不遵守协议的验证者，因为他们是恶意的或遇到⽹络延迟。从图论上讲，⼈们可以将历史的选择视为从创世块到特定块的“链”的选择。因此，共识历史是就接受哪条区块链为正确的共识。这就是我们将协议的这种实例称为“区块链”的原因。

例 2.1。 假设协议的⽬标是记录每个验证者的账⼾余额。那么他们的集体状态就是账本，每个区块捕获状态转换，例如从⼀个验证者到另⼀个验证者的货币交易（例如，“Yunice 将 ID 为 538 的硬币发送给 Bureau-gard”）。我们可能想要避免的⼀种冲突是将上述交易和另⼀笔内容为“Yunice 将 ID 为 538 的硬币发送给 Carol”的交易都接受到共识历史中，这种⾏为通常称为双重⽀付（double-spending）。当前的共识状态可以通过从“创世状态”开始，然后从创世区块开始依次处理共识历史中的每条消息（希望所有诚实的验证者都会同意）来确定。

2.2 消息和视图（views）

在我们的模型中，验证者 $V$ 通过⼴播消息（某种语⾔的字符串）与⽹络交互。当诚实的验证者 $V$ ⼴播消息 $M$ 时，我们假设 $M$ 被发送给⽹络上的所有验证者。

主要类型的消息是向⽹络提议⼀个区块，即⼀段数据。其他消息可以是记账通知，例如投票区块（“attestation”）、将新验证者放⼊区块链（“activation”）、证明其他验证者的不良⾏为（“slashing”）等，具体取决于特定协议。我们假设每条消息都由单个验证者进⾏数字签名，这意味着我们可以准确追踪每条消息的作者，并且冒充诚实验证者等攻击是不可能的。

由于⽹络延迟和不诚实的验证者（延迟消息或传递不正确的信息），验证者对发送给⽹络的整套消息可能具有不同的了 解状态；我们将其形式化为：验证者在任何给定时间要么看到要么没有看到（sees or does not see） 发送给⽹络的每条消息。

每条消息可能有⼀个或多个依赖项，其中每个依赖项都是另⼀条消息。在任何时候，我们接受⼀条消息当且仅当其所有依赖 项（可能没有）都被接受时，这一规则是递归定义的。我们现在定义验证者 $V$ 在给定时间 $T$ 的视图，表⽰为 view $(V, T)$，作为验证者迄今为⽌看到的所有已接受消息的集合。我们还有⼀个“上帝视⻆”，称之为⽹络视图，定义为一个假想的验证者已接受的消息集，该验证者已经看到（⽆延迟）任何验证者在任何时间⼴播的所有消息（这包括恶意验证者仅发送到⽹络⼦集的消息）。我们将⽹络视为“虚拟验证者”，因此我们使⽤ view $(NW, T)$ 来表⽰时间 $T$ 的⽹络视图。对于任何验证者 $V$ 和任何给定时间 $T$，view $(NW, T)$ 包括 view $(V, T)$ 中的所有消息，尽管时间戳可能不匹配。最后，由于通常我们谈论的是特定的时间点，我们通常会省略时间并使⽤诸如 view $(V)$ 之类的符号来谈论 view $(V, T)$，除⾮有必要谈论特定的时间。

例 2.2。 在时间 $T$，假设验证者 $V$ 看到内容为“Yunice 将硬币编号 5340 发送给 Bob”的消息 $M$，但尚未看到包含“Yunice 获得硬币编号 5340”的消息 $M'$（该消息在⽹络上，但尚未到达 $V$）。同时假设在我们的协议中， $M$ 依赖于 $M'$（⽽不是其他消息），这捕获了语义上的含义，即我们需要在花费硬币之前获得它，并且 $V$ 不能也不应该在没看到 $M'$ 的情况下对 $M$ 采取⾏动。在这种情况下，我们说 $V$ 已经看到但还没有接受 $M$，所以 $M ∉$ view $(V, T)$。然⽽，⽹络已经看到了两者；所以如果⽹络接受 $M'$，我们有 $M ∈$ view $(NW, T)$。

我们现在对视图的结构做出⼀些假设：

• 每个⼈（验证者和⽹络）都以⼀条消息（⽆签名）开始，该消息对应于⼀个商定的创世区块($genesis\ block$)，称为B_genesis，没有任何依赖（因此它⼀开始就⾃动被所有视图接受）。
• 除 B_genesis 之外的每个块都引⽤（并依赖）⽗块($parent\ block$)作为其数据的⼀部分。因此，我们可以将 view $(V)$ 视为⼀个以 B_genesis 为根的有向⽆环图（实际上是⼀棵有向树），如果 $B$ 是 $B'$ 的⽗级，则有⼀条边 $B\ {\leftarrow}\ B'$，在这种情况下，我们说 $B'$ 是 $B$ 的⼦级。我们将这些边称为⽗⼦边($parent-child$ edges)，以区别于其他类型的边。
• 如果⼀个块没有⼦块，我们称它为叶块($leaf$)。
• 此类协议中的链将是成对的父子边序列 $B$_$1$$\ {\leftarrow}\ B$_$2$$\ {\leftarrow}\ · · ·$ 如果有一条从 $B$ 到 $B'$ 的链，我们说 $B'$ 是 $B$ 的后代($descendant$)。当且仅当 $B'$ 是 $B$ 的后代时，我们才说 $B$ 是 $B'$ 的祖先($ancestor$)。如果两个块 $B$ 和 $B'$ 不相等，并且都不是对方的后代，我们说它们冲突($conflict$)。
• 上述设置意味着每个块 $B$ 唯⼀地定义⼀条从 B_genesis 到 $B$ 的（向后）链，并且这条链在任何包含 $B$ 的视图中都必须是相同的链（因此我们不需要将视图作为其定义的⼀部分）。我们称之为 $B$ 链($the\ chain\ of\ B$)或 chain($B$)。

图 1：我们关⼼的协议类型中出现的视图的图形可视化（仅可视化块⽽不可视化其他消息）

⽰例 2.3。 参⻅图 1 中仅限于区块的视图⽰例。箭头表⽰⽗⼦边。视图中的区块形成⼀棵树，以单个创世区块 B_genesis 为根。此处区块 $C$ 和 $D$ 发⽣冲突（以及 $E$ 和 $D$）。 $E$ 拥有最⻓的链，即 chain $(E)$ = $($ B_genesis$, A, B, C, E)$。

本节中的措辞有⼀些技术性细节，这些细节促使我们定义视图($views$)，但对本⽂的核⼼来说并不重要。为了不分散读者的注意⼒，我们将这些细节推迟到附录 A。

2.3 权益证明

区块链协议的第⼀个也是最具影响⼒的⽅法是⽐特币，它使⽤⼯作量证明模型。这种⽅法使⽤简单直观的分叉选择规则，“链最重的区块是链的头部”，这使得提议区块在计算上变得困难。矿⼯（类似于验证者）只是提议在最重的链（计算⼯作量最多的链）上构建区块，这在数学上并不能保证任何⾮创世区块是“正确的”，但提供了概率保证，因为⼀旦其他矿⼯在其上构建，它与区块冲突的可能性就会越来越⼩。然后共识历史就是⼯作量最⼤的链，理想情况下会不断增⻓。工作量证明的优雅是通过提出区块的昂贵的计算工作/电力等成本来支付的。

在本⽂中，我们希望创建⼀个权益证明（proof-of-stake） 区块链，其中验证者的投票权与他们在系统中的抵押权益（或资⾦）成正⽐。提议区块本质上是免费的，而不是使用计算能力来提议区块。作为交换，我们需要一个额外的数学理论层来防止当我们让提议区块变得“容易”时出现不正当的激励。现在，我们将论文的重点转移到一系列考虑到权益证明的区块链设计上。

⾸先，我们假设我们有⼀组 $N\ 个验证者\ V = \{$V₁, . . . , V_N$\}$，并且每个验证者 V ∈ $V$ 都有⼀定数量的质押 w(V)，这是一个描述抵押品数量的正实数。我们进一步假设每个验证者的平均质押量为 1 个单位，因此总质押总和为 N。我们所有涉及质押的操作都将是线性的，因此这种扩展不会改变情况并使记账更容易。我们假设验证者集和质押规模是固定的，以便专注于协议的理论要点。我们将在后面的章节中解决在实际使用中放宽这些条件时出现的问题，特别是第 8 节。

我们需要的主要原料有：

• 分叉选择规则（fork-choice rule）：⼀个函数 fork()，当给定⼀个视图 G 时，它会识别单个叶块 B。此选择会⽣成⼀条从 B_genesis 到 B 的唯⼀链 fork(G) = chain(B)，称为规范链（canonical chain）。区块 B 称为视图 G 中的链头。直观地说，分叉选择规则为验证者提供了⼀条“规则”，以决定“正确”的区块应该是什么。例如，最⻓链规则（longest chain rule） 就是⼀条分叉选择规则，它返回距离创世区块最远的叶块。此规则与⽐特币使⽤的“最重链规则”（heaviest chain rule）类似。
• 最终性（finality） 的概念：正式来说，⼀个确定性函数 F，当给定⼀个视图 G 时，它会返回⼀组 最终（finalized） 区块 F(G)。直观地说，最终区块是“每个⼈最终都会认为是共识历史⼀部分的区块”或“区块链确定的内容”。
• 削减条件（Slashing conditions） ：诚实验证者绝不会违反这些条件，违规验证者可以被抓获，违规者的权益将被削减或销毁。削减条件激励验证者遵守协议（例如，协议可以奖励诚实的验证者来捕获违反条件的不诚实的验证者）。

我们⽤来定义这些成分的关键概念是证明（attestations），即投票（嵌⼊在消息中），投票决定哪些区块“应该”成为链的头部。为了防⽌验证者进⾏双重投票或以违反协议的⽅式投票，我们强制实施削减条件，这些条件可⽤于销毁验证者的权益，从⽽激励验证者遵守协议。

图 2：包含区块和证明的理想视图。

我们可以在 图 2 中看到我们将要展⽰的协议的理想版本；在每个时间段内，都会创建⼀个新块，其⽗块是链的最后⼀个头部（理想情况下是最后⼀个创建的块），并且相应委员会中的验证者都完美地证明新块。在不太理想的情况下，区块可能会分叉，我们可能会缺少证明等。证明将通过帮助验证者决定正确的链头来发挥作⽤。在第 4 节中，我们将定义所有细节。

2.4 拜占庭验证者（PBFT）

在一个协议中，如果验证者遵守协议，则称其为诚实的，否则为拜占庭式的。我们通常假设严格少于 p = 1/3 的验证者是拜占庭式的。这个常数可以追溯到实用拜占庭容错（Practical Byzantine Fault Tolerance (PBFT) ）[8]，这是拜占庭容错⽂献中的经典共识协议；PBFT 确保只要少于 1/3 的副本（与我们的验证者同义）是拜占庭的，系统就能正常运⾏，如 [3] 中证明的那样。这个常数 1/3 容错率经常出现在许多基于 PBFT 的作品中（主要思想是鸽巢原理论证需要 1/3 才能起作⽤，例如我们在第 5 节中的证明），其中 Casper FFG [7] 与我们的⼯作最直接相关，我们将在第 3.1 节中对其进⾏回顾。

具体来说，如果具有总计 pN 权益的验证者可以被具有⽹络视图的验证者可证明的削减，我们将运⾏该协议的区块链定义为 p-slashable，并且我们的⼤多数结果将采⽤以下形式：“在任何时候，我们的区块链要么具有（良好的）属性 X，要么是 (1/3)-slashable ”，因为当我们有许多拜占庭参与者时，我们真的⽆法保证具有任何良好的属性，所以这是我们可以得到的最强类型的声明。还请注意，具有 (1/3)-slashable 是⼀个⽐仅仅具有 (1/3) 属于拜占庭验证者的权益更强⼤且更理想的结果，因为如果我们只有后者的保证，我们仍然可以激励原本诚实的验证者以不被抓住的⽅式作弊。

PBFT 最重要的⼀个⽅⾯是它在异步条件下⼯作，这意味着我们对接收消息所需的时间没有限制。因此，它能够满足区块链和加密货币的需求，而在这些领域，我们经常会担心对抗性环境。我们将在第 2.6 节进⼀步讨论同步假设。

2.5 安全性和活性

诚实验证者的最终⽬标是发展⼀条最终链，其中所有区块彼此形成“逻辑上⼀致”的状态转换（尽管验证者可能会离线、遭遇延迟问题或恶意提出冲突的状态更改）。正式⽽⾔，这转化为两个期望属性：

定义 2.4。 我们说共识协议具有：

• 安全性（safety），如果任何视图 G 的最终区块集合 F(G) 永远不会包含两个冲突区块。安全性的结果是，任何验证者视图 G 的最终区块 F(G) 都可以“完成”为 F(view(NW)) 的唯⼀⼦链，该⼦链始于创世区块，⽌于最后⼀个最终区块，我们称之为最终链。

• 活性（liveness），如果最终确定的区块集能够增⻓。定义活跃度的⽅法有很多种。对于我们的论⽂，我们认为该协议具有：

  • 可信活性（plausible liveness），如果⽆论之前发⽣什么事件（攻击、延迟等），新区块总是有可能被最终确定（或者说，不可能陷⼊“僵局”）。这是为了防⽌诚实验证者⽆法继续，除⾮有⼈放弃⾃⼰的权益。
  • 概率活性（probabilistic liveness），如果⽆论之前发⽣什么事件，新区块都有可能被最终确定（⼀旦我们对⽹络延迟、攻击者的能⼒等做出⼀些概率假设）。

  乍⼀看，后者意味着前者，但情况更微妙；前者是关于协议逻辑的纯粹⾮概率属性；后者需要（可能⾮常强的）关于实现上下⽂的假设来保证协议“通常按预期⼯作”。我们将在第 7.3 节中进⼀步讨论这种对⽐。

本文的主要目标是在第 4 节中证明我们的主要协议的这些重要属性。

备注（语法与语义）。链与状态转换逻辑一致性之间的关系不应立即显而易见，这需要协议设计者做更多的工作来确保。例如，可以制定一个协议，允许用户花费代币 S 的区块禁止祖先区块在其他交易中使用 S。在这种情况下，如果 Xander 从区块 B_x 获得代币 S ，并写⼊两个区块 B_y 和 B_z，其中 B_y 的数据包括 Xander 向 Yeezus ⽀付 S，⽽ B_z 的数据包括 Xander 向 Zachariah ⽀付 S，那么这些⾏为不⼀致的逻辑思想对应于图论性质，即 B_y 和 B_z 作为区块发⽣冲突。链和冲突区块的语⾔⾜以满⾜任何此类逻辑，因此我们在论⽂中假设，哪些区块可以成为其他区块的⼦区块的语法已被设计为嵌⼊逻辑⼀致性的语义，这使我们能够忽略逻辑，只从链和冲突区块的⻆度进⾏思考。

2.6 时间、时期和同步

在我们的模型中，我们⽤插槽（slots） 来测量时间，插槽定义为某个常数秒数（ [11] 中暂定为 12 秒）。然后，我们将⼀个时期（epoch） 定义为某个常数 C（ [11] 中暂定为 64 个插槽）的插槽。插槽 i 的时期 j（epoch j of slot i） 为 ep($i$) = $j$ = $\frac{i}{C}$ 。换句话说，属于时期 $j$ 的区块的插槽号为 $jC$ + $k$，因为 $k$ 遍历 {0, 1,... , C − 1}。创世区块 B_genesis 的插槽号为 0，是时期 0 的第⼀个区块。

时期的主要⽬的是将时间划分为多个部分，各个部分之间的边界可以被视为“检查点”（“checkpoints”）。这允许使⽤ Casper FFG 中的概念，我们将在第 3.1 节中看到。

我们不应该假设⽹络保证验证者在任何给定时间看到相同的消息，甚⾄不同的验证者具有相同的时间视图。共识协议的研究通过设置不同的同步条件（synchrony conditions） 来解决这个问题，例如：

• 同步系统对于在两个系统之间发送消息所需的时间有明确的上限节点；
• 异步系统没有任何保证；回想⼀下，PBFT [8]在异步下⼯作。
• 部分同步（partially synchronous ） 系统可能意味着以下两种情况之⼀，具体取决于上下⽂：（i）存在明确的延迟上限，但事先不知道；（ii）在某个未知时间 T 之后，已知存在明确的上限。⼯作[10]在不同故障和同步模型中建⽴了容错界限，重点关注部分同步。

对于我们来说，在研究安全性和可信活性时，我们不做任何同步假设。在研究概率活性（即试图在“现实”条件下量化活性）时，我们将使⽤上述部分同步的概念 (ii)。如果在时间 (T − t) 或之前的所有带有时间戳的消息在时间 T 及之后都在所有验证者的视图中，我们称⽹络在时间 T 是 t-同步（t-synchronous） 的（其中 T 和 t 都以插槽为单位）；例如，如果每个插槽为 12 秒，则 (1/2) 同步意味着所有消息都在最多 6 秒后收到。

备注。 例如，可以接收“来⾃未来”的消息。假设 Alexis 发送了⼀条时间戳为 00:01:30 PT 的消息，Bob 在 1 秒后收到该消息，⽽他的时钟⽐ Alexis 慢 3 秒。Bob 在⾃⼰的时钟上看到这条 00:01:30 PT 消息，时间戳为 00:01:28 PT，因为他总共落后了 2 秒。为了便于分析，我们可以假设所有（诚实的）验证者总是延迟接收消息（即将其添加到他们的视图中），直到他们⾃⼰的时间戳达到消息的时间戳。这使我们能够假设没有消息在⽐它们应该的更早的时间被读取（再次，由诚实的验证者读取）。