使用容量时间证明和类Casper确定性装置
带来快速确定和抗长程攻击

原著：Alex Skidanov 推特：/AlexSkidanov 邮箱： [email protected] 2019年10月

---

原文链接：PoST.pdf

翻译：Marco     校对：Sissi     编辑：Buster

---

摘要

我们提出一个包括分叉选择规则，抗女巫攻击机制和确定性装置的设计。这一设计可以提供快速确定性、抗长程攻击，以及阻止池化。该设计同时基于权益证明和容量时间证明，使用了一个类似Casper FFG的确定性装置。一旦某个块获得确定，短期内就不可逆，除非有超过 $\left \lceil \frac{n}{3}-1 \right \rceil$⌈3n​−1⌉的总权益被罚没。一旦质押的代币被释放，该块就不可逆，除非作恶者控制了系统中接近 $50\%$50%的容量。

---

1 导言

在本文中，我们介绍了一个分叉选择规则和一个抗女巫攻击机制，该设计预期使用在NEAR Protocol（注1）上。我们将其与其它三种抗女巫攻击和分叉选择规则比较：工作量证明的最重链规则，它最初在比特币论文[1]中提出;（委托）权益证明的最长链规则，例如乌洛波罗斯协议[2]；以及（委托）权益证明的BFT共识，例如ByzCoin[3]。

我们将从多个维度审视现存的分叉选择规则和抗女巫攻击机制。

1.1 理想特性

1.1.1 抗长程攻击

工作量证明的最重链分叉选择规则有个非常理想的特性，就是无论作恶者做什么，除非他控制了超过$50\%$50%的哈希算力，否则就无法逆转一个经过充分长时间确认的块。

权益证明系统没有这种特性。特别是，在过去创建区块的出块人取回其质押权益后，用来出块的秘钥对其就不再具有价值。一个破坏者可以尝试用明显低于对应质押权益的价格买到这样秘钥。而且，不像工作量证明，权益证明没有强制出块间隔的机制。所以破坏者可以在分分钟内创建一条长于正统链的分叉链，骗过（最长链）分叉选择规则。

应对该问题主要有两种方式：

弱主观性。要求网络中的所有节点周期性地检查最新产出的块，不允许早于该块的重组。只要节点检查链的频率快于取回质押代币的时间间隔，那些破坏者通过获取过去质押代币对应的秘钥所构建的更长的链，就不会被选为正统链。

弱主观性的问题是，尽管现存节点不会被攻击者迷惑，但所有首次上线的新节点没有信息能判断哪条链是最先创建的，只能选择攻击者创建的最长链。为了避免该问题，他们需要从链下获取正统链的相关信息，而这实质上是强迫他们标识某个网络中的节点为可信节点。

前向安全秘钥。另一个方式是让出块人在出块后立即或稍等一小段时间就销毁刚刚用来出块的秘钥。实现方式包括在每次出块时创建新的秘钥对，或使用一种称为前向安全秘钥的机制，它可以在公钥保持不变的前提下，改变对应的私钥。

这个方式依赖于节点自身的诚实性及其对协议的严格遵守。对他们来说，销毁秘钥没有任何激励，相反，因为知道未来某人也许会试图购买，所以这些秘钥甚至还有价值。虽然大部分出块人更改执行文件，移除销毁秘钥逻辑的情况不太可能出现，但一个依赖于诚实的协议，在安全性等级上，是不能与一个依赖理性的协议相比的。只要过半参与者保持理性，工作量证明就一直有效，而且无需参与者之间协同。因此，让权益证明网络在分叉选择规则和抗女巫攻击机制也具有这种特性是更理想的。

1.1.2 环境友好

比特币和以太坊的矿工每年要消耗数兆瓦时的电力进行工作量证明的计算，严重影响了环境。

权益证明在这方面有了显著改进，基本上对环境无任何影响。但因为参与者不使用稀缺资源来确保链的安全，它也有其他弊端，接下来几节将围绕这个问题进行阐述。

容量时间证明的抗女巫攻击机制相比工作量证明明显更加环境友好，而且它利用了稀缺资源的优势，也就是容量；同时并不消耗多少电力，因为硬盘不是靠电力存储信息的。

1.1.3 确定性用时

工作量证明系统，例如比特币和以太坊，以及非BFT的权益证明系统都需要用户等待一段时间，才能充分确认那个包含他们所关心交易的块已确定。在比特币中，通常要等6个块，这大约要一个小时左右。

另一方面，使用BFT共识去确定每个块的权益证明系统，拥有非常快速的确定性。只要一个块被创建出来，并由BFT共识达成一致，该块就不可逆，除非大部分的质押权益被罚没。

1.1.4 颠覆确定块的代价

要颠覆一个近期被确定的块，在使用BFT共识的权益证明系统中，其代价明显高于工作量证明或非BFT的权益证明系统。特别的，在一个特定的周期中（周期的模糊定义是一个时间段，期间验证者集合是稳定的），要颠覆一个块，需要三分之一的质押权益被罚没。这从某种意义上，等同于10%到20%的流通代币都被销毁。而在工作量证明系统中，代价只是近期的奖励，一般来说其对应价值显然相对更小。

然而，正如前面讨论的，颠覆一个早就被确定的块，在权益证明系统中的代价可能很小。而在工作量证明系统中，代价随着时间而增加。

在我们的设计中，当一个块确定后，实施一次短重组的开销是三分之一的总质押权益被罚没，类似与使用BFT共识的权益证明系统。另一方面，实施一次长重组将消耗掉所有容量时间证明中累积的奖励。后者的代价，小于短重组，在确定块的质押权益解质押时达到低谷，但之后代价随时间增加。

1.1.5 可用性

使用某种最重链分叉选择规则的工作量证明和权益证明系统，即使在大比例的出块人同时掉线的情况下，仍然能保持可用。要在使用BFT共识的系统中获得相同的特性是非常困难的。

区块链领域的BFT共识协议和BFT确定性装置主要设计于这样的环境，存在单一的n个验证人组成的授信集合，不随时间变化，且在任意时刻都有至少 $\left \lfloor \frac{2n}{3}+1 \right \rfloor$⌊32n​+1⌋个验证人在线。验证人集合发生改变，以及超过 $\left \lceil \frac{n}{3}-1 \right \rceil$⌈3n​−1⌉ 的验证人同时掉线，这些对区块链协议的安全和可用性造成的影响，我们会在1.2.1节详细讨论。

1.1.6 池化的激励

目前的工作量证明的实现，为矿工组池挖矿提供了高度的激励。每个块的创建都是一个乐透**，而单位时间可以出块的人数是相当低的，对大多数矿工来说，赢得一次乐透之前的预期等待时间会非常漫长。矿工会非常乐意支付预期收益的一小部分换得这种不确定性的降低。所以，他们选择加入一个池，而不是自己独立挖矿。

通过矿池挖矿的矿工经常在矿池提供的哈希上挖矿，而不是自己观察网络上的哈希，自己选择在他们看来最重的链。因此，一个累计超过一半哈希算力的矿池集合，可以给所属矿工发送一个不对应最重链的哈希，以实施一个短程重组。

目前，对以太坊和比特币，需要贿赂以达成攻击的矿池数目都不超过5个，导致了对集中化的严重关切。

与工作量证明不同的是，容量时间证明很难设计成一个乐透过程。我们提出的特定设计中没有乐透，使得容量时间证明的池化实际上不可能出现。

1.1.7 无需许可

尽管是个争议性的问题，可以争辩说权益证明系统没有工作量证明系统里那种意义上的无需许可特性。因为对于想成为出块人的参与者，他们一般都需要提交一个权益质押交易，而该交易需要被接受。这实际上等于出块人要获得区块链当前用户的许可才能开始出块。

在NEAR协议中，交易不是直接收录在块中，而是打包在组成块的段中，细节参见[5]。创建无效的段必然是个被惩罚行为。而出段的过程是依赖于权益证明的，因此不具有工作量证明上的那种无需许可特性。综上，无需许可特性不是其设计目标。

可以这样更改其设计，改由容量时间证明标识参与者而不是权益证明。这样，至少部分引入了工作量证明的那种无需许可特性。但这超出了本文的范围。

图1：工作量证明下的大矿工排斥小矿工 (原作者解释该图:

Bob按照协议规则挖矿，而Alice拒绝在Bob的块上挖矿。此时，左边展示了Bob的情况，对其最坏的是他创建了一个块，但后两个块都是Alice创建的，这有4%的概率。右边展示了Alice的情况，对其最坏的是，和Bob同时出块，但其他矿工在Bob的块上继续挖矿，这有0.8%的概率。）

我们注意到，工作量证明的无需许可特性也是有些言过其实的。考虑图1的情况。掌控了大比例哈希算力的恶意矿工或矿池，比如说20%算力，可以选择排斥一个小出块人，比如说只有1%算力的。排斥小矿工产出的块，恶意矿工的损失约占奖励的1%左右，而小矿工的损失约占奖励的4%（可能更多）。假设挖矿与电力成本的边际收益是低于4%的，那小矿工就亏本了，并最终被迫停止挖矿。这实际上为其他所有矿工，包括攻击者，提升了1%的未来奖励。因此，大矿工可以并且有动机去排斥小玩家，导致了这样的争议：工作量证明系统中也并不真的具有无需许可特性。

1.2 BFT确定性，验证人轮转和可用性

当设计基于BFT共识的权益证明区块链时，一般都希望当一个块被共识确定后就不可逆，除非很大比例的质押权益被罚没了。

很多BFT协议提供这样的保证：只要验证人集合保持不变，并且任意时刻至少 $\left \lfloor \frac{2n}{3}+1 \right \rfloor$⌊32n​+1⌋ 的验证人在线（，确定的块就不可逆）。

1.2.1 BFT确定性与验证人轮转

通常，验证人轮转带来的问题是，如果两个相邻的验证人集合没有大范围的重叠，后面的验证人集合可以假装没有看到前一个验证人集合所确定的块，且没有被惩罚的风险。这个问题至少有两种解决方案。一个是禁止相邻验证人集合的大比例变动，比如仅仅允许最高某个百分比的验证人变化。另一个是强制两个验证人集合都确定在交接过程中产生的某个块。

1.2.2 BFT确定性与可用性

一个更大更基础的问题是，下述情况如何处理：因某种原因，超过 $\left \lceil \frac{n}{3}-1 \right \rceil$⌈3n​−1⌉ 的验证人同时掉线。例如，在一个存在多种客户端的区块链中，如果某种主要客户端触发了一个bug，就会导致大比例的验证人同时掉线。

这里，我们审视一下分别被Cosmos，Polkadot和以太坊宁静所采用的三种方案。Cosmos使用BFT共识作为主分叉选择规则，正统链是由确定块组成的最长的链。Polkadot和以太坊宁静使用非BFT分叉选择规则（分别是BABE和LMD GHOST），外加一个BFT确定性装置（分别是GRANDPA 和 Casper FFG）。

• Cosmos方案。Cosmos重点侧重一致性。因此，若超过$\left \lceil \frac{n}{3}-1 \right \rceil$⌈3n​−1⌉ 的验证人同时掉线，链就停了。如果验证人遭遇不可恢复的崩溃，唯一恢复链的方法只能是一个硬分叉。
• Polkadot方案。Polkadot中，即使大比例的验证人掉线，底层的非BFT共识BABE也会继续运行，但BFT确定性装置GRANDPA就停了，直到最后验证人集合中有足够确定块的验证人恢复上线。类似的，若验证人遭遇了不可恢复的崩溃，当前的确定性装置只能通过硬分叉恢复，但是链本身还是会继续通过BABE出块。由于Polkadot中许多组件都依赖于确定的块，所以该方案也是侧重一致性的。
• 以太坊宁静方案。宁静侧重于可用性。即使大比例的验证人掉线，其底层非BFT共识 LMG GHOST 会继续出块。若超过$\left \lceil \frac{n}{3}-1 \right \rceil$⌈3n​−1⌉ 的验证人掉线，其BFT确定性装置 Casper FFG 会停住。然而掉线的验证人会慢慢失去质押权益，达到某个临界点就会被踢出（验证人集合），使系统恢复到至少 $\left \lfloor \frac{2n}{3}+1 \right \rfloor$⌊32n​+1⌋ 的验证人在线的状态。此时Casper FFG就能恢复继续确定块。要注意的是，这种情况下，前后两个验证人集合会有很大的不同。之前确定的块现在有可能变成孤儿块，且无人会因此受罚，如图2所示。
  

图2：侧重可用性的确定性装置可能出现确定块被颠覆而无人受罚的情况
一般来说，我们认为侧重可用性比侧重一致性更好，因为想要一致性的客户端总是可以选择采用本地的方式处理一条可用链的一致性。以以太坊宁静为例，当前委员会如果与之前的差异过大，一个客户端可以选择不认可它确定的块（并导致在本地停止该链）。在这种情况下，如果有足够数目的客户端质疑委员会的差异，认为有确定过的块在此过程中被颠覆，他们可以达成一个社群共识，以执行一次硬分叉。

本文提出的方案侧重一致性，侧重可用性所需要做的变化留给将来探索，参见4.1节。

2 设计

本节提出我们的设计，它的长期安全性基于容量时间证明，短期安全性基于类Casper的确定性装置。

2.1 出块

我们的方案中，按周期出块。每个周期有一个固定参与者集合负责出块，我们称其为出块人。出块人质押一定数量的权益，在我们的方案中，所有出块人的质押权益是相等的。尽管实践中出块人集合在周期间是大部分重叠的，但我们并不作此假设。

特定周期内的出块人按照一个固定安排出块。一种安排可能是把周期分成10秒的间隔，给每个间隔安排一个出块人。

当出块人创建一个新块时，他需要其他所有出块人对前一个块（新块基于其上创建）提供一个许可。然后他将这些许可包含在这个新块里。夜影[5]，NEAR协议里的分片设计，要求至少一半当前周期的出块人提供许可，但是本文的设计并不依赖于此。

2.2 容量时间证明

除了出块人外（权益证明中抗女巫攻击机制需要他们），还有一种参与者叫矿工（miner）。矿工在系统中没有权益抵押，负责进行容量时间证明的计算。与工作量证明中在每个块上进行乐透不同，我们设计中的容量时间证明不是个乐透过程。若系统预估的容量时间证明复杂度是正确的，所有生成的证明都会被采用。

特别的，矿工在基于周期首块形成的种子上计算容量时间证明，如图3所示，代表着整个周期而不是某个块。每个出块人生成的块里都有 s, s > 1 个槽位，留给代表前一个周期的容量时间证明。块里包含的一份容量时间证明都对应有奖励，出块人受此激励，会包括尽可能多的证明（上限是所允许的槽位数 s）。

周期末尾，若每个块的平均证明数超过1，则容量时间证明的目标复杂度略微提升，反之若小于1，则稍事下调。所以，只要用于容量时间证明的可用容量没有突然成倍上升，复杂度设置为一个合理的值，则一个特定周期的所有证明都会被包括在下个周期额块中。要注意的是，可用容量不满足容量时间复杂度的参与者是无法从池化中受益的，所以，对矿工来说，没有池化的动机。

图3：容量时间证明的计算与收集的时间线

2.3 许可

我们设计中的许可与Casper FFG[6]中的投票有相同的作用。来自出块人 v 的一个许可表示为一个有序元组
$<v, p, r>$<v,p,r>
这里 p 是被许可的块， r 被称为参照块。

参照块必须是p的祖辈（我们称b是另一个块a的祖辈，只要满足：b等于a，或b是a的前一个块，或b是a前一个块的祖辈）。

我们在2.5节会给出块的score s(b) 和weight ω(b)的定义。对任意两个出块人发出的两个许可
$<v, p_{1}, r_{1}>$<v,p1​,r1​>
和
$<v, p_{2}, r_{2}>$<v,p2​,r2​>
一定有

这里 A(b) 代表b的所有祖辈块。

换句话说，若两个许可的参照块相同，则被许可的块必然在同一个链上。若他们的参照块不同，则(r, p)的socres和weights的范围必然不重叠，且scores高的许可，其weights也必然更高。创建违反这些规则的两个许可是要被惩罚的。

出块人v创建块b，需要收集其前一个块p的许可。另一个出块人 v’ 应提供该许可，只要p是由分叉选择规则（参见2.5节）确定的正统链的链尖（最新块）。若其签发的最新许可块是p的祖辈，则应在许可中使用相同的参照块；否则，参照块一定p的祖辈中，比其签发的最新许可块的score和weight高的块集合中score最低的那个块。按这个方式构建，就不会触发惩罚条件。参见图4。

图4：延续正统链的块许可与导致重组的块许可

2.4 确定性装置

本节我们讨论一个类Casper的确定性装置，我们称其为Casper NFG（注2）。

给定许可 a = <v, p, r> 和 块 b，我们称 a 为 b 的一个 pre-vote，只要

1. b 是 p 的祖辈；
2. r 是 b 的祖辈。

我们称块 $b(p)$b(p) 有一个块 b 的 quorum pre-vote， 只要b是$b(p)$b(p)的祖辈，且有 $\left \lfloor \frac{2n}{3}+1 \right \rfloor$⌊32n​+1⌋ 的出块人在 $b(p)$b(p)的祖辈块中收集有许可
$a = <v, p, r>$a=<v,p,r>
使 p 是 b§ 的祖辈且 a 是 b 的 pre-vote。

给定许可 a = <v, p, r> 和 块 b， 我们称 a 为 b 的一个 pre-commit， 只要

1. b 是 p 的祖辈；
2. r 是 b 的祖辈；
3. p 的祖辈中有一个块 b§，其有一个 b 的 quorum pre-vote。

我们称块 $b(p)$b(p) 有一个块 b 的 quorum pre-commit，只要 b是$b(p)$b(p)的祖辈，且有$\left \lfloor \frac{2n}{3}+1 \right \rfloor$⌊32n​+1⌋ 的出块人在 $b(p)$b(p)的祖辈块中收集有许可
$a = <v, p, r>$a=<v,p,r>
使p 是 $b(p)$b(p) 的祖辈且 a 是 b 的 pre-commit。

正如3.1节将展示的，互不为祖辈的两个块，不可能在同一个出块人集合下同时获得一个quorum pre-commit，除非至少 $\left \lceil \frac{n}{3} \right \rceil$⌈3n​⌉的出块人被罚掉。也就说，拥有一个quorum pre-commit的块实际上可以被视为确定了。2.7节中将分析在轮转出块人的情况下，这个确定性装置的工作情况。

2.5 分叉选择规则

我们首先定义块的 weight 和 score 的概念，之后定义分叉选择规则。

块 b 的 weight（记做 $ω(b)$ω(b)）， 定义为b的所有祖辈块里包含的容量时间证明的复杂度之和。

记 $HQV(b)$HQV(b) 是存在对b的quorum pre-vote的祖辈块中最重（按照weight的意义）的那个块。

块的 score（记为 $s(b)$s(b)）则是：
$s(b) = ω(HQV(b))$s(b)=ω(HQV(b))
为了在一些分叉链中选出一条正统链，首先计算每个链尖的score，然后拥有最高链尖score的就是正统链。

如果两个链score相同，其确切的分叉选择规则（我们称这样的分叉选择规则为低级分叉选择规则）对于本设计的其余部分来说并不重要。下一节我们调查了可能的低级分叉选择规则。

2.6 低级分叉选择规则调查

2.6.1 LMD GHOST

LMD GHOST（Latest Message Driven Greedy Heaviest Observed Subtree）处理一颗块树，树根源自确定性装置所确定的最新块。LMD GHOST先对每个出块人标识出来自其签发的weight最高的许可块。然后从最后确定的块开始每次构建一个块到正统链。每一步中，对最新加入块的每个子块，都计算满足条件的出块人的数目，条件是其签发的最重的许可块位于该子块开始的子树中。接下来，选择出块人数目最多的那个子块，加入正统链，并继续这个步骤，直到最新块已没有子块。

LMD GHOST 有一个特性，称为“粘性”。换句话说，对一个特定块 b，若大比例的出块人的最重许可块都在其子树中，则只要大部分出块人是诚实的，并在LMD GHOST选定的正统链上出块，b 就将保持在正统链上。

在目前的设计中，使用LMG GHOST的缺点是，若确定性装置停止确定块，系统再次对长程攻击敏感。我们注意到，确定性装置停止确定块不太会持续超过数个周期，所以实践中这不是个大问题。特别的，如果大比例的出块人掉线，他们会在数个周期内被移出出块人集合，剩余的出块人足以再次开始确定块。

2.6.2 最重链

LMD GHOST的替代方案是，当两条链的score相等时，就看链尖的weight。

我们提出的容量时间证明模型与经典的工作量证明有个主要的区别。证明是基于过去两个周期的哈希进行计算的。因此，当前和前一个周期中的分叉链都会包括这个证明。这样的话，一个只有很小可用容量的恶意破坏者，可以创建一个短分叉，包括诚实参与者的所有容量时间证明，加上很少一点自己计算的证明，就能成为最重链。

一种解决方案是，让矿工在提交容量时间证明时，不仅包括用来计算证明的上周期哈希，还包括他认为的当前正统链的最新块。这样，提交的证明就只能用于继承该块的链。同时证明的奖励稍微延迟发放，如果相同的证明被用于多个之前的块，就可以通过密码学证明这个事实，以罚没奖励。

该设计可抵抗长程攻击。我们没有深入分析其安全性，但要注意到，它不抗适应性贿赂：一个破坏者可以试图支付一小笔费用购买矿工以算出的证明，并创建一条比正统链更重的链，导致一次短重组。

2.7 出块人轮转

我们按周期出块，而周期的长度是块数目的一个常数。实践中，我们调整一个周期中的块数使周期长度约为一天。

在周期$k$k中，参与者可以权益抵押代币以表明做出块人的愿望，或发起一笔交易表明退出出块人的意愿。在周期$k$k的结尾，来自周期$k-1$k−1的交易被执行，任何在$k-1$k−1周期质押了代币的新参与者都被加入到出块的参与人池中。同时，在周期$k-1$k−1中表达了退出愿望的出块人被移出池。然后，周期$k+1$k+1的出块人就从这个池中按某个算法选出。具体的细节对本设计并不重要。我们在NEAR中使用的算法，叫做权益证明门限，选择出最大的门限值$t$t，使得

这里$n$n是出块人席位数，$V$V是可以出块的参与者池。$s(v)$s(v)是参与者$v$v抵押的权益。然后，为每个参与者分配个 $\lfloor(s(v)/t\rfloor$⌊(s(v)/t⌋ 出块人席位。

因为每个周期的出块人基本上在上个周期的开始就确定了，我们可以在下个周期的出块人确定后，就让他们也提供块的许可。然后，让客户端将那些由且仅由当前周期出块人与下个周期出块人都独立确定的块，视为真正的确定。

如果特定周期内，一个出块人提供许可的比例低于某个预设百分比（比如 pk = 80%），将视其为提交了退出出块人集合的交易，而且要么罚没他一个小比例的抵押权益，要么禁止它在接下来的某些周期内重新成为出块人。

因此，在超过$\lceil(n/3-1)\rceil$⌈(n/3−1)⌉的出块人掉线的场景中，在两个周期内，掉线的出块人会被移出出块人集合，确定性装置会再次开始确定块。然而，我们注意到，如果一个特定的出块人集合在某个周期内一个块都没有确定，那将来就有可能出现两个或以上的确定块互相冲突，而没有任何参与者被惩罚。

一个客户端可以选择看中链的可用性或是一致性。一个侧重可用性的客户端会认可确定性装置确定的所有块。而一个侧重一致性的客户端将仅仅认可这样的块：在该块产生的周期及其之前周期中，每个周期都至少有一个块是被其当时出块人集合和下一个周期出块人集合同时确定的。3.3节中，我们会讨论具体的确定性保证，以及作恶者需要什么样的资源才能进行一次短程或长程分叉。

3 分析

3.1 确定性装置的安全性

这一节，我们证明两个互不为祖辈的块，不可能被同一出块人集合确定（好比说，有一个quorum pre-commit），除非一个不是他们公共祖辈的块被某个其他出块人集合确定。3.3节中，我们讨论这种可能性带来的影响，就是另一个出块人集合确定了一个冲突块。

给定一个链尖 t，以及其中一个确定块 b，我们定义 $QV(t, b)$QV(t,b) 为 t 的祖辈中有 b 的 quorum pre-vote 的块中，score最低的那个块。

引理 1. 若块 b1 是链尖 t1 所在链中的一个确定块， 则在某个链尖 t2 所在的链中， 不存在这样的块 b2 ，当 ω(b2) > ω(b1) ，且 b1 b2 互不为祖辈时， 有同一出块人集合对其的 quorum pre-vote。 除非超过 ceil(n/3-1) 的出块人做出了要被惩罚的举动，或一个不是 b1 祖辈的块，其weight超过ω(b1) ，且被其他出块人集合确定。

图5：若块 b1 在一个链中被确定，就没有更重的块可以在其他链上获得quorum pre-vote

证明.
假设引理不对，存在一个那样的块 b2。考虑b2为其中高度最低的块（这里高度定义为其祖辈块的个数）。
由确定块的定义，有 floor(2n/3+1) 的出块人有形如<v, p1, r1> 的许可，使得 QV(t1, b1) 是p1的祖辈。注意到，既然 QV(t1, b1) 有 b1 的 quorum pre-vote, 则 p1的 score 至少为 ω(b1)。

既然 t2 所在链里有关于 b2 的 quorum pre-vote，有 floor(2n/3+1) 的出块人有形如 <v, p2, r2> 的许可，使得 b2 是 p2 的祖辈，r2 是 b2 的祖辈。至少 ceil(n/3) 的出块人有上述两种形式的许可。

考虑这些出块人。记得有ω(b1) ≤ ω(b2)。既然 b2 是 p2的 祖辈, 以及 r1 是 b1 的祖辈，则有 ω(r1) ≤ ω(b1) ≤ ω(b2) ≤ ω(p2)。 因为 p2 和 p1 在不同的链上， 除非出块人做出了要被惩罚的行为，否则 (ω(r1), ω(p1)) 和 (ω(r2), ω(p2)) 的范围就不相交。而因为 ω(r1) ≤ ω(p2)，所以一定有 ω(p1) < ω(r2)。记得对这两个许可来说，要使得 ω(p1) < ω(r2)，则必须 s(p1) < s(r2)， 如图5所示。

因为 p1 的score至少为ω(b1)， r2 的score严格大于 ω(b1)。但那意味着有一个块 b2’ ，其weight 高于 ω(b1)，且有一个b2所在链中的quorum pre-vote。

因此，若weight高于ω(b1)的块 b2 存在于与 b1 不同的链上，就必然存在另一个块 b2’ 为其祖辈。而这违背了 b2 是最早块的假设。

定理 1 (安全保证)。若块 b1 在链尖 t1 所在的链中被确定，任何看到 t1 的参与者都会将 b1 视为正统链中的块，除非超过 ceil(n/3-1) 的出块人做出了被惩罚的行为，或一个weight超过 ω(b1) 且不是其祖辈的块被其他出块人集合确定。

证明。
假设定理不对，另一个链被选为正统链。因为t1 所在的链有一个b1的 quorum pre-vote，该链的score至少为 ω(b1)。因此，不包含 b1 的正统链的score也至少为 ω(b1)， 否则不会被选为正统链。根据score的定义，这意味着有一个与b1不同的块，其weight 大于等于 ω(b1) 且有一个quorum pre-vote。这违反了引理 1。

3.2 确定性装置的可信活性

我们说一个协议具有可信活性，是指如果在任何状态下，都有一个协议参与者的行动序列，能让之前没确定的块被确定。这与通常意义下的活性不同，后者一般是指这样的特性，如果诚实参与者遵守协议，就能保证有进展。

只要系统持续出块，Casper NFG就能保有可信活性。考虑指定时刻的所有块，以及由分叉选择规则在这些块中选出的一条正统链。出块人可以一起持续在那条链上确定块。这就足以让块继续在这条链上生成，除非有个weight比曾经许可过的块更重的块被出块人创建出来。此时，所有出块人可以提供对该块的许可，并在接下来的两个块时间内确定它。

要注意的是，尽管Casper NFG有可信活性，却没有一般意义上的活性。特别的，能轻易的构建这样的场景：一条链上的某个块获得一个quorum pre-vote，然后在它获得quorum pre-commit之前，其他链上一个更重的块又获得了一个quorum pre-vote，接下来在这个块获得quorum pre-commit之前，前一条链上又出现了一个更重的块，获得了一个quorum pre-vote，这样周而复始地重复下去。

实践中，我们假设是个同步网络，意思是网络上传播块的速度要快于出块间隔。在这个同步网络假设下，我们假定若有一个高度为$h$h的块$b_{h}$bh​，有一个对$b_{0}$b0​块的quorum pre-vote，则$b_{h}$bh​会在高度为$h+1$h+1的块$b_{h+1}$bh+1​生成前，被所有的出块人观察到。这样，出块人就有时间积累$b_{h}$bh​的许可，使得$b_{0}$b0​被确定。

3.3 确定性保证与长程攻击

本节中，我们分析一个破坏者需要什么才能控制或颠覆一个确定的块，前提是在任意时刻，至少有 $\lfloor(2n/3+1)\rfloor$⌊(2n/3+1)⌋的出块人在线，且在创建块，许可他们观察到的块，所有的客户端都是侧重一致性的，不会轻易认可一个确定块，除非过去的每个周期都有至少一个块被确定。在没有这些假设下保证确定性，留给未来工作，参见4.1节。

考虑图6的情况。一个客户端观察到块A和B，它们在各自的链上都是最后一个确定块。它们互不为祖辈，且它们之前的每个周期里，都有至少一个块被确定。设（客户端不知道此信息）A在诚实出块人的正统链上，B是由破坏者创建的。考虑他们在周期i中的公共祖辈C，因为周期 $i+1$i+1的出块人集合在周期$i-1$i−1的最后一个块时就揭晓了，所以A和B的祖辈周期$i+1$i+1的出块人集合是相同的。基于假设，每个周期都至少有一个块是确定额，设A’ 是周期 $i+1$i+1 中 A 的祖辈确定块， B’ 是周期 $i+1$i+1 中 B 的祖辈确定块。自然，这两个块也互不为祖辈。也就是说，他们被相同的出块人集合确定。

图6：每个周期都有至少一个块确定时的区块链分叉

假设在最后签名块所在周期之后 $z$z 个周期才返回用户抵押的权益。

设 A 在周期 $i+k+1$i+k+1 中。分析 $k$k 的取值。 若 $k ≤ z$k≤z，则那些周期 $i+1$i+1 时出块人的权益还在质押中，会被罚没。（译者注：短程攻击场景）。

若 $k > z$k>z 。则质押权益已释放，无法对周期 $i+1$i+1 的出块人的双签A’ 和 B’ 的行为进行惩罚。既然A是确定块，其所在链的socre至少为 $ω(A)$ω(A)。A 的weight包括了诚实矿工在过去 $k$k 个周期里的所有容量时间证明，不包括已经算好的，但要被当前周期包括的证明。因此，A的weight至少是分叉以来，诚实参与者计算出的容量时间证明的$(k-1)/k$(k−1)/k 。为了让 B 所在的链有高于 A 的 score， 至少链中要有一个块的weight大于 A 的weight，这样，破坏者需要在同样的时间片中计算出相当于诚实参与者 $(k-1)/k$(k−1)/k 的容量时间证明。

综上所述，假定破坏者无法在过去的时间中计算证明比诚实参与者明显得快，则为了让客户端选择B所在的链，破坏者要么让至少$1/3$1/3的总质押权益被罚没，要么控制超过$(k-1)/(2k-1)$(k−1)/(2k−1) 的系统中用来计算容量时间证明的空间。

4 未来工作

4.1 侧重可用性

参考图6， 假设我们允许确定这样的块，在其过去的周期中至少有一个周期内没有确定块。那对于破坏者来说，确定块B就不需要再周期i+1中有确定的块。他们可以用小于 $\lceil(n/3)\rceil$⌈(n/3)⌉ 的出块人子集，在B所在的链上创建和许可区块。在所有的诚实参与者因为不活动而掉出该链之前，不能确定块，但破坏者所控制的出块人也不会被罚。若破坏者在周期i内分叉的足够早，从B所在的链看来，诚实出块人在周期i中就无法创建和许可足够数量块，会在周期i+2开始时被踢出。这时，破坏者就可以开始确定块了。

我们的早期分析表明，有可能对score方法做一些小改动，就确保破坏者，即使在放开历史周期内必须有确定块这个限制的情况下，也无法颠覆一个确定块，除非他们控制了大比例的用于挖矿的容量。形式化的对score方法的明确修改以及相应的证明留给本文的未来版本。

4.2 确保活性

我们的早期分析表明，对确定性装置进行一些改动（具体的，小心的放置一个超时，随着未确定的块高度而增加时间），就可能再部分同步网络的条件下，拥有可证明的活性。明确的修改和对应的证明留给本位的未来版本。

总结

本文提出的设计，提供了基于BFT共识的权益证明区块链的快速确定性，以及基于工作量证明协议的抗长程攻击能力。同时作为一个附加优势，本设计不激励池化。

使用容量时间证明替代工作量证明，显著降低了对环境的负面影响。

References

[1] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. http: //bitcoin.org/bitcoin.pdf.
[2] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In CRYPTO, pages 357–388. Springer, 2017.
[3] Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th USENIX Security Symposium (USENIX Security 16), pages 279–296, Austin, TX, August 2016. USENIX Association.
[4] Tal Moran and Ilan Orlov. Simple proofs of space-time and rational proofs of storage. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692 of Lecture Notes in Computer Science, pages 381–409. Springer, 2019.
[5] Alex Skidanov and Illia Polosukhin. Nightshade: Near protocol sharding design. http://near.ai/nightshade.
[6] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. CoRR, abs/1710.09437, 2017.

---

Note：
1 This is an ongoing research. NEAR will initially launch without Proof-of-Space-Time.
2 Nightshade Finality Gadget. Also a play of words Naughty Finality Gadget to contrast with Friendly Finality Gadget. Coincidentally, NFG is also a reference to the biggest problem in the space today, namely the current adoption of blockchain protocols in the wider community, with N and G standing for “no” and “given” correspondingly.