|
Bram Cohen & Krzysztof Pietrzak 2019年7月9日 摘要
本文概述了奇亚网络的共识层（区块链）的基本设计原则。它受到比特币区块链的启发，也与比特币区块链相似，当大部分专门用于保障区块链安全的计算能力由诚实的各方控制时，区块链就会实现共识。在奇亚网络中，资源不是计算能力，而是磁盘空间。 为了实现这一目标，比特币中使用的工作证明被替换为了空间证明。为了获得像比特币区块链中那样的挖矿动态，奇亚用可验证的延迟函数交替证明空间。 我们对奇亚骨干网进行了初步安全分析，表明只要至少大约61.5%的空间是由诚实方控制的，奇亚就满足基本的区块链安全属性。
术语： 在本文中，我们保留了如下术语： w ∈ Z+ ：一个安全参数，我们用它来做各种事情，比如下面H的输出或者挑战的大小：w=256就可以满足所有情况。 H : {0, 1}∗ → {0, 1}w ：一个加密的哈希函数，作为证明的随机模型。 T ∈ Z+: 奇亚难度参数（具有类似比特币中难度参数的功能）。 κ ∈ Z+:诚实的农民在k最好的道路上工作（在奇亚中，大概k=3的时候）。 θi ∈ [0, 1]:与κ=1相比，使用κ=i得到的加速因子（如图2所示）。 ιi = 1-1/(1+e·θi )∈ [0, 1]:如果诚实的农民使用κ=i，他们必须持有的空间分数（如图2所示）。 η ∈ R+: 计算可验证延迟函数(VDF)的一个步骤(未知阶数组的平方)所需的秒数。 ξ ∈ R+: 在连续的纪元中允许T的最大波动(在比特币中对应的参数是4，在Chia中这个参数将被调整)。
内容 0 大纲 1.简介 1.1比特币 1.2 攻击 1.3 用空间证明代替工作证明 1.4 挖掘攻击 1.4.1 分链 1.4.2 唯一基元 1.4.3 慎用难度重置 1.5双浸攻击 1.5.1惩罚不是解决办法 1.5.2消除研磨优势 1.5.3奇亚如何解决双浸问题 1.6奇亚的链品质 1.6.1链品质 1.6.2基础概率实验 1.7远程攻击 1.7.1 用旧钱对权益证明进行远程攻击 1.7.2 利用资源变化对空间证明进行远程攻击 1.7.3 利用VDFs解决远程攻击问题 2.构建区块：空间证明，可验证延迟函数和签名 2.1（唯一）数字签名 2.2（唯一）空间证明 2.2.1空间证明的算法 2.2.2空间证明的安全性 2.2.3唯一的空间证明 2.2.4[AAC+17]空间证明 2.3 可验证延迟函数 2.3.1 [Wes18, Pie18]可验证延迟函数 3. 区块链 3.1 躯干和枝叶 3.2 块格式 4. 农民和时间领主的算法 4.1 链管理 4.2 空间农民算法 4.3 时间领主算法 5. 难度调整 5.1比特币的难度调整 5.2 使用难度重置的研磨攻击 5.3奇亚的难度调整 5.4 关于4的重要性 5.4.1 ξ < e时的攻击 5.4.2 最佳攻击 6.链增长和k 6.1 我们的理想设置 6.2 随机变量C`κ,h模拟链式增长 6.3 C`κ,h的分析界限 6.4 ιi 和θi 6.5 奇亚骨干
0 概要 在§1中，我们讨论了在不依赖工作证明的情况下设计区块链时遇到的主要挑战，以及如何在Chia中解决这些问题。 在§2中，我们介绍了Chia的主要构建模块。除了像唯一签名和加密散列函数这样的标准基元外，还包括最近开发的新的证明系统，即空间证明（PoSpace）和可验证延迟函数（VDF）。 在§3中，我们指定了Chia的区块链格式，它在一些关键点上与比特币区块链有所不同。Chia不使用工作证明，而是用可验证的延迟函数交替使用空间证明。这导致链在很多方面与比特币相似，特别是，在比特币中不需要同步，我们可以证明严格的安全保证，假设有足够部分的资源（Chia中的空间，比特币中的计算）是由诚实的各方控制的。 为了防止研磨攻击（如§1中讨论的那样），Chia链被分成两条链，一条 "不可研磨 "的链称为主干，它只包含PoSpace和VDF输出，另一条链称为枝叶，它包含其他一切。 §4节包含了计算空间证明的农民和计算VDF输出的时间领主所使用的算法的（伪）代码。 在§5中，我们讨论了Chia的难度调整。 它不同于比特币中的难度调整工作方式，因为如果一个人会天真地适应它，那么微妙的研磨攻击是可能发生的。 我们还做了一个似乎不为人所知的观察，但中本聪（匿名的比特币设计者）可能已经意识到了，因为它解释了为什么难度的因素可以在连续不断地变化。epochs（一个epoch指的是使用相同难度参数的区块序列，在比特币中就是2016个区块）设置为4这个相当大的值，我们发现如果该因子小于e≈2.718，就有可能发生攻击。 在§6中，我们提供了对Chia的初步安全分析。我们在下面的§1.1中有更详细的介绍，但总的来说，对于我们提供的最基本的设计，只要诚实的农民至少控制73.1%的空间，就能证明安全。这一点可以改进，让老实的农户不只延长第一条，而是每深入一层就延长第一条κ>1的链条。使用哪个κ值是一个 "社会惯例"，而不是一个协议参数。通过使用κ=3，诚实的农民只需要控制≈61.5%的空间。
1.简介
1.1比特币
我们假设读者对比特币有一定的了解，只是提到与讨论Chia相关的方面和结果。我们回顾一下，在比特币区块链中，要扩展一个区块β，矿工必须提供挑战c=H(β，数据)的工作证明，通过对要扩展的区块β和要添加的区块的有效载荷数据(交易和时间戳)进行哈希得出。该证明是一个随机数v使得0.H(c, ν) < 1/D，其中D为难度参数，H为加密哈希函数（SHA256）。如果H被建模为一个随机函数，那么为了找到这样的证明，需要对H进行D次调用。 比特币规定，矿工应该始终致力于延长他们所知道的最长链。恶意矿工控制了一半以上的哈希力量，就可以完全控制这条链。他可以无视其他方贡献的区块，这样只有他的区块出现在链上，从而获得所有的奖励和审查交易。更糟糕的是，这样一个51%的对手可以两次消费。 中本聪假设，一个恶意矿工如果控制了不到一半的总哈希力，就不能通过偏离诚实的挖矿策略获得任何利益。由于微妙的自私挖矿攻击[ES14]，这种直觉被证明是错误的：控制α<1倍< span="">的诚实矿工的哈希能力的矿工（例如，不到总数的一半）可以将α部分的区块添加到链上（相比之下，他们通过遵循规则可以得到α /1+α部分）。从积极的一面来看，[GKL15]显示没有更好的攻击。他们将链的质量定义为一个对抗性矿工可以推入链中的区块的分数，并表明对于上述对抗性矿工来说，这个分数最多为α/1+α。
1.2攻击
研磨攻击（Grinding attacks）。不幸的是，[GKL15]对比特币主干的简单分析并不能扩展到使用工作证明以外的证明系统的区块链，比如权益证明（PoStake）或空间证明（PoSpace）。原因是，在基于PoW的区块链中，人们只能将挖矿资源（做计算所需的硬件和电力）用于扩展一个特定的区块，以应对一个特定的挑战。另一方面，像空间证明（或股权证明）这样的证明系统的计算成本非常低，所以恶意矿工有可能通过偏离诚实的挖矿规则，并计算出比协议规定的更多的证明，从而发起研磨攻击（在股权证明的背景下，这些攻击称为"事不关己"的问题）。我们区分两种类型的研磨攻击。 挖掘（digging）指的是对手试图以不同的方式扩展一个特殊的块的研磨攻击。 双浸式（double dipping）指的是对手试图扩展许多不同的块，而不仅仅是协议指定的块的研磨攻击。 我们将在1.4和1.5章节中详细讨论挖掘和双浸以及它们在Chia中的处理方式。 短程和远程攻击（Short & long-range attacks）。一旦我们用空间证明（或者权益证明）来代替像比特币一样的区块链中的工作证明，研磨问题将不再是唯一的安全问题。另一个问题便是远程攻击，指的是对手试图从老实的农民很久以前看到的链上产生分叉的攻击。我们将在§1.7中讨论远程攻击以及Chia如何使用可验证的延迟函数(在空间证明之上)来避免这些攻击。
1.3用空间证明代替工作证明
在本节中，我们将讨论在区块链中用PoSpace取代PoW的含义，这一点（即使忽略安全问题）并不明显，因为PoW和PoSpace在语法上是不同的。 在比特币中，矿工们竞相寻找PoW，找到PoW的矿工向网络广播一个新区块，区块被添加，矿工获得奖励，矿工们转而扩展这个新区块。使用PoSpace这样的证明系统，每个矿工都可以立即计算出一个PoSpace，所以我们需要以某种方式指定谁 "获胜"，以及何时继续下一个区块。基于PoSpace的Spacemint[PPK+15]区块链为每个PoSpace分配一个质量（这个质量只是证明的哈希值），协议规定宣布质量最好的PoSpace应被视为链的延伸。在Chia中，这一基本思想得到了进一步的发展。我们还为每个PoSpace分配一个质量，但要最终完成块，必须用一个可验证的延迟函数的输出来增强这个PoSpace。VDF的时间参数--它规定了计算输出需要多少个连续的计算步骤--与PoSpace的质量是线性的，这意味着质量最好的PoSpace（最好的意思是最低值）可以先被最终确定。像这样用VDF交替使用PoSpace，让奇亚区块链有了类似比特币中挖矿的耕种动态。不同的是，我们不需要任何像Spacemint或Ourborors这样基于PoStake的区块链的同步化。
1.4 挖掘攻击
如前所述，当比特币矿工想要扩展一个区块β时，他们准备好有效载荷数据，然后必须找到一个挑战c=H(β，数据)和难度D的PoW，即一个随机数ν，使0.H(c，ν)<1/D。当矿工选择数据时，他们实际上可以计算出许多不同的挑战c1，c2，......。(例如，通过取可用交易的各种子集或稍微改变时间戳)。原则上，一个比特币矿工现在可以选择同时为两个（或更多）挑战搜索一个PoW，但这需要在这些挑战中分割资源（硬件和电力），因此他们这样做无法获得任何优势。与此形成鲜明对比的是，如果我们在类似比特币的设计中使用类似PoSpace的证明系统，一个恶意矿工可以为许多不同的挑战c1、c2、......生成证明，然后挑出一个最有前途的证明（比如说，上面概述的最好的证明）。通过尝试X次挑战，矿工的获胜几率将增加X倍（与诚实采矿相比）。因此在某种意义上，我们又回到了基于PoW的方案，因为理性的矿工不会遵循诚实的挖矿规则，而是竞相计算尽可能多的PoSpace。 我们把这种研磨攻击--对手试图以许多不同的方式扩展一个块——称为挖掘。 在§1.4.1到§1.4.3中，我们概述了如何在Chia中防止挖矿攻击。 1.4.1分链 为了防止如上所述通过对数据的不同值进行研磨来挖掘，Chia采用了Spacemint的一个想法。如图1所示，链由两条链组成，一条链称为主干，只包含证明（PoSpace和VDF输出），另一条链称为枝叶，包含有效载荷数据（以及一些签名，将枝叶绑定到主干上）。所有的挑战（对于PoSpace和VDF）都来自于树干中的以前的值，因此不容易受到研磨攻击，在枝叶中尝试各种数据值（如果我们把难度重置考虑在内，那就不太正确，我们将在§1.4.3中讨论）。 图1：Chia区块链的说明，将在§3中解释。(不可磨)主干链中的块β = (σ, τ )包含一个空间σ的证明，然后是一个VDF输出τ 。枝叶中的一个块α包含了有效载荷（交易、时间戳）、枝叶中前一个块的签名（用来连锁这些块）、空间证明的签名（用来将枝叶与树干绑定）。这张图只是说明了一个链的三个最深的区块，第20页的图5说明了一个 "更丰富 "的视图，它包含了分叉和非最终的区块。 1.4.2 唯一基元 为了防止挖掘攻击，主干中使用的加密基元也必须是唯一的。特别是，Chia使用了一个唯一的签名方案，唯一性意味着对于每一个公钥/消息对，都会有正好存在一个有效的签名。我们使用的空间证明是唯一的，并且可验证的延迟函数也有唯一的定义。 1.4.3慎重对待难度重置问题 即使将有效载荷数据外包给枝叶，并确保主干中的所有基元都是唯一的，但事实证明，如果直接改编比特币的难度重置机制，还是有可能被挖矿攻击。我们在§5中讨论这个问题，但总之，攻击是可能的，因为难度参数取决于时间戳，而时间戳（作为数据的一部分）在枝叶中，因此可以被研磨。由于VDF输出取决于难度参数，所以VDF输出可以通过这个连接间接接地。 为了使这种攻击奏效，难度重置必须适用于紧随时间戳被用来重新计算难度参数的区块之后的区块（就像比特币中的情况一样）。通过指定难度重置只适用于足够多的区块之后，可以很容易地防止这种情况的发生。
1.5 双浸攻击
在上一节中，我们概述了Chia如何防止挖掘攻击。我们现在讨论另一种类型的研磨攻击，称为双浸。回想一下，挖矿指的是对手试图以许多不同的方式扩展一个特定块的攻击，而双浸指的是他们试图扩展不同的块的攻击，而不仅仅是协议指定的那个块。 1.5.1 惩罚不是办法 2014年，有人建议将处罚作为抑制双浸的一种手段。Spacemint[PPK+15]还规定了一种处罚形式。遗憾的是，处罚并不能真正解决这个问题。特别是，惩罚只能对潜在收益小于潜在惩罚的攻击起到威慑作用，所以它们可能会抑制自私采矿等事情，但不会抑制双花。惩罚也不能阻止远程攻击（在§1.7中讨论），在这种情况下，对手试图在私下产生一个长链，只是因为这样一来，周围就没有人触发惩罚。 1.5.2 消除研磨优势 在Spacemint中引入的对抗双浸和也挖攻击的一个想法（后来在Ourborors Praos中使用）是通过在几个连续的区块中使用相同的挑战来偏离类似区块链的设计。这使得磨合攻击的吸引力降低，原因是不可能连续挑战很多块且都是好的结果。回到挑选樱桃的比喻：你可以一个一个地去挑选最好的樱桃，但如果你一定要从很多桶樱桃中挑选出整整一桶，那么最好的一桶樱桃的质量只会比一般的樱桃稍好。 1.5.3奇亚如何解决双浸问题 Chia区块链的规范根本没有内置机制来防止双浸，相反，我们首先量化了一个人从双浸中获得的优势。然后，我们展示了如何通过改变耕作规则，让诚实的农民在每一个深度上延伸出更多的区块来减少这种优势。我们在下面的§1.6中更详细地解释了这一结果，但总之，我们表明，只要至少73.1%的空间是由诚实的农民控制的，那么基本设计就是安全的（在具有非零链质量的意义上）。由于工作证明不容易受到双浸攻击，所以比特币只需要诚实的矿工控制>50%的哈希算力就是安全的。为了缩小这种差距，我们还在一定程度上让诚实的农民双浸：一个参数κ∈Z+指定诚实的农民应该在每个深度计算第一个κ（而不仅仅是第一个）块的PoSpace。设置κ=3似乎是个不错的选择，这不会增加农民太多的工作，现在老实的农民只需要控制≈61.5%。图2显示了随着κ的增加，这个分数是如何下降的。 备注1（选择k的社会约定） 我们要强调的是，κ的值不是奇亚规则的一部分。相反，它是由诚实的农民搭建起来的社会约定，因此可以很容易地适应未来，特别是，这将不需要一个分叉。人们可能会选择降低κ来加快共识，或者增加κ来提高安全性（这不仅意味着提高双倍支出所需的空间分数，还比如让自私的采矿变得不那么有利可图）。
1.6奇亚网络的链品质
我们为Chia提供了一个理想化环境下的初步安全分析，这样我们就可以专注于核心问题。 具体来说，我们假设： I.我们没有网络延迟； II.对手计算VDF的速度不会比诚实的一方快（但他们可以并行计算无限量的VDF输出）； III.空间的证明是理想的（即绝对不允许有时间-内存的权衡），而且 IV.我们没有难度重置。 1.6.1 链品质 当链品质为κ=1时。在这个理想化的环境中，我们证明了最基本的κ=1的情况下——诚实的农民只为他们在每个深度看到的第一个区块计算一个PoSpace——如下： (Lemma 2的推论)一个控制着小于a *(1 /(1+e))≈0.269部分总 空间的对手不可能(在私下)比诚实的各方更快地增长一条链。 如图1所示，在Chia中，计算PoSpace σi的挑战来自于最后的VDF输出τi -1。这个挑战不是简单的τi -1的哈希，而是τi -1的一个签名的哈希。这意味着潜在的对手将无法预测农民的挑战，这又让我们可以证明以下观点： ("不减速"的非正式陈述 Lemma 4)一个无法破解签名方案安全性 的对手(但其他方面可以不受限制，尤其是拥有无限空间，甚至可 以在零时间内计算出VDF输出)无法减缓诚实农民的种植链速度。 作为Lemmas 2和4的必然推论，我们得到以下语句： 只要诚实的农民至少控制了总空间的1-1/(1+e) ≈ 0.731部分，区块链是 安全的，即链上的区块有非零的部分是由诚实的农民提供的(链质属性 )，一个在链上足够深的区块几乎肯定会永远存在(共同前缀属性)。 当链品质为κ>1时。我们在Chia中需要诚实地控制≈0.731分量（空间）和比特币中0.5分量（计算能力）之间的差距，原因是由于双浸攻击。如果我们规定老实的农民每看到一个区块就必须延长，那么我们也只需要0.5的分量，因为最极端的双浸攻击就会和老实的农民策略相吻合。当然那是完全不现实的。 我们将考虑介于两种极端情况之间的设置，其中一个参数κ∈Z+指定诚实的农民应该为他们在每个深度看到的第一个κ块计算一个PoSpace。同时，每个时主都应该努力在每个深度最终确定κ块（所以上述极端情况对应κ=1和κ=∞）。 设定κ值是一种权衡：κ值越高，安全保障越好，但增加了农民的工作量，因为他们必须为每个深度计算κ证明。要在Chia中设定κ的值，有助于了解当我们增加κ时，诚实的农民所需控制的空间分量接近0.5的速度，我们用ικ表示这些值。我们只能分析计算κ=1的这个分数，其中ι1=1∞(1/e)(1+1/e)≈0.731，由定义可知ι∞为0.5。为了确定其他的数值，我们进行了模拟（这将在§6.2中讨论）。正如人们所期望的那样，如图2所示，ιi很快就向0.5收敛。Chia将使用κ=3，对应于ι3≈0.615。 1.6.2 基础概率实验 Lemma 2的技术说明考虑以下简单的概率实验。对于正整数h，l，考虑一个深度为l的h-ary树。给树的每个枝叶分配一个在[0，1]中均匀采样的权重iid。然后，我们考虑以下随机变量(如图4所示)。 图2：红色的数值显示了（模拟值为）ι1 ... .... ι100，即诚实的农民必须持有的必要的空间分量，以超越拥有无限数量VDF服务器的恶意农民。它接近0.5（红色虚线），因为κ（在x轴上，注意步长从1增加到10的时候。κ=10）增加。蓝色的数值显示(模拟值为)θ1 ... ... θ100, 其中 θi = liml→∞,h→∞ E[Cl. κ,h]/E[Cl1,h]规定了通过在每个深度扩展κ（而不是只扩展一个）块可以实现的加速；它接近1/e。为κ → ∞。为了模拟θi，我们对Cl进行采样。κ,h(参见§1.6.2)，h=999，l=100000。和近似的θκ≈Cl。κ,h/E[Cl1,h]。ικ由θκ计算而来，为：ικ = 1 ∞ 1+e1-θκ . 图3：对κ=1（底部）到κ=4（顶部）的链式增长的可视化，用h=29，l=30模拟。x轴是时间，绿线连接同一水平的κ块（红点）。链条（或者对于κ>1棵树）是蓝色的。 图4：§1.6.2概述的概率实验的说明。全局最短路径的权重为0.54；我们通过贪婪地跟随每个节点的最佳边缘得到的路径权重为0.80。 l(贪婪路径)让Cl1,h是我们从根开始，沿着每个节点上权重最低的边缘，到枝叶结束，得到的路径的总边缘权重。 l(全局最短路径)设Cl∞,h为从根到叶子的所有hl路径的总边重的最小值。 Cl1,h基本上捕获了总空间为h的诚实矿工成长一条长度为`的路径所需要的时间，而Cl∞,h捕获了试图扩展所有可能路径的对手所需要的时间(即对手发起最极端的双浸攻击)。从简单的顺序统计（参见Lemma 1）可知， E[Cl1,h]=l / (1+h) 而Lemma 2表明 E[Cl1,h] ≤ E[Cl∞,h] · e . ——（1） 我们分析推导出了式(1)，模拟结果表明，随着h，l走向无穷大，它是紧密联系的。 我们还为任何κ∈Z+定义了随机变量Clκ,h，其中Clκ,h捕获了诚实的农民需要生长一条长度为l的路径所需的时间，假设他们试图扩展他们在每个深度看到的第一个κ块。 我们将θκ定义为通过延长κ链而不是仅仅延长一条链来加快链的生长速度的因素。 θκ = liml→∞,h→∞E[Clκ,h]/E[Cl1,h] = 1 + hl · liml→∞,h→∞E[Clκ,h] 虽然我们在大l和h的极限中定义了这个值，但这个值收敛得非常快，所以我们可以通过对相当小的有限l，h进行采样Clκ,h得到很好的近似值。我们将表明，上一节讨论的分数ικ可以从θκ计算为 ικ = 1 -1/(1 + e · θκ ). θκ和ικ如图2所示。
1.7 远程攻击
大多数对区块链的攻击大致可以分为短程攻击和远程攻击。短程攻击指的是只涉及最后几个区块的攻击，而远程攻击则是指对手试图生成一条在过去许多区块中分叉的链（从诚实方看到的链）的攻击。 针对比特币的短程攻击包括自私挖矿[ES14]--对手策略性地扣留区块，以获得不公平的区块奖励份额--或者双花--对手试图在私下生成一条足够长的链，以实现双花。由于比特币规定深度为6的区块可以被认为是确认的，所以即使是一个哈希能力明显低于50%的对手，也有很大的机会是成功地进行了这次攻击（这需要比诚实的矿工更快地增长一条长度为6的链）。 远距离攻击对于比特币来说不是问题，但对于基于空间证明或权益证明等高效证明系统的区块链来说是个大问题。 1.7.1 用旧钱对权益证明进行远程攻击 针对木桩证明区块链的一种特别烦人的长程攻击，使用了这样的观察，即只要持有一个大的质押(即允许花币的秘钥)，在过去的某个时刻是有效的(但鉴于当前的链可以是没有价值的)。这样的老钥匙可以在币有效的地方分叉链，然后我们可以引导一条在目前看来有效的链条。对手有可能获得以低成本购买这种股份，例如购买大量的代币，然后再立即出售它们。除非有人假设受信任的各方或要求各方足够频繁地联机，以便人们可以在足够短的时间间隔内获得检查点，否则似乎没有解决该攻击的方法。 1.7.2 利用资源变化对空间证明进行远程攻击 回顾一下，在比特币中，"最长的链 "其实并不是指拥有最多区块的链，而是指 "最重的链"，也就是需要最多散列能力才能生成的链（这可以通过将每个区块的难度参数相加来计算）。我们可以把这个规则改编成基于PoSpace的链，说 "最重的链 "是指PoSpace（区块的质量反映了用于生成区块的空间量）在所有区块上的质量之和最大的链。这一点很微妙，原因有很多，但最严重的是，现在可以用空间生成比诚实生成的链更重的链，而这个空间只是用于耕种诚实链的空间的平均值，它可以比目前专门用于采矿的空间低很多（例如，因为随着时间的推移，采矿变得更有利可图，或者磁盘空间变得更便宜）。Spacemint[PPK+15]在计算链的权重时，将更多的权重放在最近的区块上，以一种特别的方式解决了这个问题。 1.7.3利用VDFs解决远程攻击问题 上述两种远距离攻击关键利用了PoStake和PoSpace可以快速计算的特性，所以一旦有足够的（旧）质押或空间，就可以在很短的时间内引导出一条重链。对于像比特币这样基于PoW的区块链来说，这是不可能的：人们可以使用比创世以来专用的平均哈希算力略高的哈希算力来生成一条比当前比特币区块链更重的链，但这需要（2019年）十年的时间，到那时就没用了，因为诚实链也会进步十年。Chia实现了这一理想的特性（即不能快速引导链），而不像PoW那样依靠浪费大量计算能力。相反，Chia用VDFs交替使用PoSpace。这样一来，主要的资源是空间，而VDFs则保证了人们无法以比诚实地耕作更快的速度来引导一条链。
2.构建区块：空间证明，可验证延迟函数和签名
在本节中，我们将勾勒出Chia区块链中使用的主要构件：唯一的数字签名、空间证明[DFKP15]和可验证的延迟函数[BBBF18，Wes18，Pie18，BBF18]。这些定义并不是完全通用的，而是针对[AAC+17]的PoSpace和基于顺序平方的VDFs[Wes18，Pie18，BBF18]的特殊构造而定制的。
2.1（唯一）数字签名
一个数字签名方案由三种算法来指定，一种是（概率）密钥生成算法Sig.keygen，一种是签名算法μ ← Sig.sign(sk, m)，一种是验证算法Sig.verify。我们假设标准的安全概念（在选择的消息攻击下的不可伪造性）和完美的完备性，也就是说，一个正确生成的签名将永远验证： ∀m, Pr[Sig.verify(pk, m, µ) = accept] = 1 where (pk, sk) ← Sig.keygen ; µ ← Sig.sign(sk, m) . Chia在枝叶中使用签名（用来连锁枝叶的块，并将其绑定到主干上），也在主干中使用签名（所以只有农民可以计算挑战）。为了避免研磨攻击，主干中使用的签名必须是唯一的，即对于每一个pk（这包括恶意生成的公钥）和消息m，最多只能有一个接受的签名 ∀pk, m, (Sig.verify(pk, m, µ) = accept) ∧ (Sig.verify(pk, m, µ0) = accept) ⇒ (µ = µ0) .
2.2（唯一）空间证明
2.2.1空间证明的算法 空间的证明是由下面给出的四种算法指定的： PoSpace.init 输入一个空间参数N∈N(其中N⊂Z+是一组有效的参数)和一个唯一的标识符pk(我们用pk来表示标识符，因为在Chia中，它将是一个签名方案的公钥)，然后输出 S = ( S.Λ , S.N = N , S.pk = pk) ← PoSpace.init(N, pk) 这里的S.Λ是临界者需要存储的大小为|S.Λ| ≈N的大文件。 我们也把N，pk作为S的一部分，因为这样会很方便。 PoSpace.prove在输入S和一个挑战c∈{0, 1}w上输出一个证明 σ = ( σ.π , σ = σ.N = S.N , σ.pk = S.pk , σ.c = c ) ← PoSpace.prove(S, c) 这里的σ.π是实际的证明，σ中的其他条目只是方便保管。 PoSpace.verify 在输入一个证明σ时，输出接受或拒绝。 PoSpace.verify(σ) ∈ {reject, accept} . 我们假设完全完整 ∀N ∈ N , c ∈ {0, 1}w, Pr[PoSpace.verify(σ) = accept] = 1 where S ← PoSpace.init(N, pk) and σ ← PoSpace.prove(S, c)
2.2.2空间证明的安全性 我们在这里不给出PoSpace的正式安全定义，但非正式地给出了以下定义——它指出，一个对手如果存储一个大小明显小于N位的文件 应该不能为随机挑战提供有效证明，除非他投入了相当大的计算量（最好是接近它的成本，以运行完整的初始化PoSpace.init(N，pk))。此外，它必须是不可能的分摊空间，也就是说，对m>1的不同身分的初始化空间必须需要m倍的空间。 为了避免研磨攻击，我们需要我们的空间证明是唯一的，定义如下。 2.2.3唯一的空间证明 如果对于任何身份pk和任意挑战c，恰好有一个证明，即，一个PoSpace是唯一的。如： ∀N, pk, c, |{σ : (PoSpace.verify(σ) = accept) ∧ ((σ.N, σ.pk, σ.c) = (N, pk, c))}| = 1 如果一个空间证明的预期证明数量接近1，那么我们称其为弱唯一，如： ∀N, pk, c, Ec←{0,1}w [|{σ : (PoSpace.verify(σ) = accept}) ∧ ((σ.N, σ.pk, σ.c) = (N, pk, c))|] ≈ 1 对于弱唯一性的PoSpace，我们假设每当给定挑战有一个以上的证明通过验证时，PoSpace.prove(S,c)就会输出所有的证明。 Chia中使用的[AAC+17]PoSpace只有微弱的唯一性。为了能够专注于主要的挑战，我们在分析Chia时还是会假设一个独特的PoSpace，但我们的分析可以扩展到处理弱独特的PoSpace，而不会有大的困难，只是事情会变得更乱一些。 2.2.4[AAC+17]空间证明 我们从[AAC+17]给出了一个非常高层次的PoSpace的轮廓。空间参数由一个值l∈Z+隐式给出，实际需要的空间大约是N≈l-2-2l位（例如对于l=40即10TB）。让L :={0，1}l表示l位字符串的集合。下面我们用X|l表示一个字符串X的l位前缀。 身份id :=pk与散列函数H一起定义了两个函数f: L→L，g: L×L→L为 f(x) = H(id, x)|l and g(x, xl) = H(id, x, xl)|l. 请注意，如果我们将H建模为一个随机函数，那么f，g也是随机函数。在一个挑战y∈L上，证明者必须用一个元组id，(x，x’)来回答，其中x=x’，f(x)=f(x’)，g(x，x’)=y，如果它存在的话。 在这种构造中，对于大约a(1-1/e)≈0.632的一部分挑战y∈L，至少会有一个证明，而预期的证明数是1(所以它是一个弱唯一的PoSpace)。 证明者将生成并存储两张表，这样他们就可以有效地生成证明。他们首先计算并存储一个表，表中的值(x, f(x))按第2个条目排序。有了这个表，证明者现在可以高效地枚举所有的元组(x，x’)，其中x≠x’，f(x)=f(x’)，以生成一个包含所有三元组(x，x’，y=g(x，x’))的表；这种三元组的预期数量是|L|=2l 。然后这个表按第三值排序。现在给定一个挑战y，可以有效地在第二个表中查找证明，因为它是按y值排序的。存储第二张表需要≈3|L| log(|L|) = 2l+1l位，通过更巧妙的编码方式，可以将其降低到≈2|L| log(|L|) 位。 Chia是基于这个PoSpace的，但为了进一步减少时间/空间权衡的影响（恶意农民试图以做更多计算为代价来节省空间），我们使用了这个构造的嵌套版本。我们在本文中省略了细节。
2.3 可验证延迟函数
VDF由下面给出的两种算法来指定。 VDF.solve在输入一个挑战c∈{0，1}w和时间参数t∈Z+上输出一个证明τ = ( τ.y ，τ.π ，τ.c = c ，τ.t = t ) ← VDF.solve(c，t)，并以(不多于)t个顺序步骤运行(步骤是什么取决于特定的VDF)。这里τ.y是输出，τ.π是τ.y被正确计算的证明。为了方便起见，我们也将(c，t)作为τ的一部分。 VDF.verify输入时τ输出 接受或拒绝。 VDF.verify(τ ) ∈ {reject, accept} 验证必须以t步为单位，对于现有的VDF来说，验证只需要log(t)[Pie18]甚至是恒定的[Wes18]时间。 我们有完全完整性：∀t, c : VDF.verify(VDF.solve(c, t)) = accept 我们所要求的两个安全属性是： 独特性（uniqueness）：对于错误的输出，很难拿出任何语句和接受的证明。更准确地说，在计算上很难找到任何τ’，其中对于τ←VDF.solve(τ’.c，τ’.t)，我们有VDF.verify(τ’)= accept和τ.y=τ’.y 。请注意，我们只需要τ.y（但不需要τ.π）是唯一的，也就是说，证明τ.π表明τ.y是正确的值是可以变通的。这对于VDF的所有应用似乎已经足够了，但我们要提到的是在下面章节中讨论的[Pie18，Wes18]VDF，τ.π也是唯一的。 序列性（sequentialitiy）：非正式地来讲，顺序性指出，对于任何t，一个对手A如果进行少于t个顺序步骤，将不会在随机挑战中找到一个接受的证明。即对于一些微小的x ,Pr[VDF.verify(τ )=accept ∧τ.c = c ∧τ.t = t : c rand←{0，1}w，τ← A(c，t)]≤x。 我们要强调的是，A只受顺序步数的限制，但他们可以使用高并行性。因此，通过增加并行度，不能使VDF输出的计算速度超过可以用来加快VDF计算的单步。 2.3.1 [Wes18, Pie18]可验证延迟函数 在[Wes18, Pie18]中提出的VDFs（见[BBF18]的概述）都是基于未知阶数组中的平方，对具体的群是Z∗N，其中N=pq是两个大列表的乘积。在输入(c∈Z∗N , t)时，VDF.solve(c, t)的输出是(y, π)，其值为 y = c2t mod N.这个y可以通过将c连续平方t次计算出来c → c2 → c22 → - - - → c2t。据推测，如果不知道N的因式化的话，这种计算没有捷径可走。 [Wes18, Pie18]中的VDF在证明π的定义上有所不同，它证明了y = c2t mod N。[Wes18]中的证明更短(1vs.log(T)元素)，但证明的合理性需要一个额外的假设(取随机根很难)。 如果像上面那样使用RSA组，则需要一个可信的设置或多方计算来采样模数N，使任何人都无法得知其因式。[Wes18，BBF18]建议使用虚二次场的类群作为未知阶的底层群。这些类群可以被无视地采样——这意味着给定随机位，人们可以在不学习其阶数的情况下对一个类群进行采样——因此不需要一个可信的设置。
3. 区块链
3.1 躯干和枝叶 在本节中，我们使用我们在§2中介绍的构件来指定区块链格式。如前言所述，Chia使用两个独立的链，称为躯干和枝叶，以防止研磨攻击。躯干中的块β0，β1，......包含了证明（最终确定块所需的PoSpace和VDF输出）。躯干中每有一个区块βi，枝叶中就包含一个区块αi。这个区块包含区块链的有效载荷（交易和时间戳）和签名，用于将叶子与主干绑定，同时将叶子中的区块链起来。 图5：说明区块链的可能视图（如§4.1中存储在C中）。最长路径有i+2个块，其头部是最终确定的块γi+2。在块γi-1处有一个分叉；块γ’i+1为非最终化。生成PoSpace σi+1的农民（可能是恶意的）签下了两个不同的枝叶块αi+1和αi∗+1。σi+2的农户延长了枝叶块αi+1。
3.2 块格式
一个块γi = (βi，αi)包含一个来自主干βi = (i，σi，τi)的块，其中σi = (σi.π，σi.N，σi.pk，σi.c，σi.µ)是一个空间的证明，有一个额外的条目σi.µ(下面解释)，τi = (τi.y，τi.π，τ.c，τ.t)是一个VDF输出。此外，γi必须包含枝叶的一个区块αi=（φi，datai）。 我们把刚才描述的一个块γi称为最终化，如果缺少了VDF输出的τi，我们就说这个块是非最终化的。 如果满足以下条件，一个(已定型或非定型)区块γi=(βi，αi)扩展了前一个区块γi 1=(βi-1，αi-1)(如果区块是非定型的，则省略以下第2点)。 1.σi是一个有效的PoSpace PoSpace.verify(σi) = accept 其中，挑战是前一个VDF输出τi 1的唯一签名σi.µ的哈希σi.c=H(σi.µ)，所以我们也需要检查(也见下面的注释2) Sig.verify(σi.pk, σi.µ, τi 1) = accept and σi.c = H(σi.µ) . (2) 2.τi是一个有效的VDF输出 VDF.verify(τi) = accept 其中，挑战是前一个主干块的(散列)(也见下面的注释3)，时间参数是前一个PoSpace的散列乘以当前难度参数T。 τi.c = H(βi 1) and τi.t = 0.H(σi) · T (3) 3.φi是（当前PoSpace中使用的pk下）枝叶中前一个区块、树干中空间的证明和数据的签名（哈希）。 Sig.verify(σi.pk, H(αi 1, σi, datai), φi) = accept 4.datai是指块中包含的实际数据。在本文中，我们只是讨论Chia的共识层，对于这一点，具体如何规定并不相关。但是，像在Bitcoin中一样，它本质上是一个交易列表，必须与前面区块中的交易data0，...。, data i-1 保持一致。 注释2（为什么空间证明挑战是一个签名）。eq.(2)中的PoSpace挑战被定义为签名的哈希值，而不是简单的VDF输出的哈希值，即σi.c=H(τi 1)，原因是这样只有农夫(知道σi.pk的秘钥)才能计算挑战。这将是后面证明 "不减速 "Lemma 4的关键。 注释3（为什么VDF挑战来自前一个区块）。eq.(3)中的VDF挑战之所以定义为前一个主干块的哈希，而不是简单地用前一个PoSpace来推导挑战，即τi.c = H(σi)，是为了让一个已经完成τi-1计算的时间领主可以释放它，并立即开始计算τi。农民现在可以计算这个区块的PoSpace σi，如果时间领主在它做出τi.t=0.H(σi)-T序步之前收到一个σi，它就可以最终确定这个区块，并马上继续进行τi+1。这样诚实方就不会因为有网络延迟而被拖累。这一点很重要，因为对手如果把VDF服务器和存储设备放在物理上很近的地方，就不会有这个缺点。 在极少数情况下，如果最好的PoSpace拥有极好的质量（因此可以在短短几秒钟内敲定），时间领主有可能无法及时收到PoSpace。为了避免这种情况的发生，Chia中的时间参数将有一个加法项，以强制执行VDF运行时间的下限，因此网络延迟永远不应该减慢诚实方的速度。
4. 农民和时间领主的算法
在本节中，我们提供了农户的伪代码，农户为保障链的安全奉献了空间，而时间领主则计算VDF输出以最终确定区块。
4.1 链管理
空间农民和时间领主将他们在链上的本地视图存储在数据结构C中，图5说明了可能视图中的最高块。 Chain.init不需要任何输入，但是输出从网络接收到的链的当前视图C。 每当从网络中接收到新的区块或本地生成证明时，就会调用Chain.update（这个证明对于时间领主来说是一个VDF输出，对于农民来说是一个PoSpace）。 它期望输入一个已定型或未定型的块γ(也可以允许一个索引/VDF输出对(i, τ )作为输入，在这种情况下，它检查这个输入是否对某个已知的非最终化块进行了最终化，并像它的输入是这个最终化块一样继续)。 它更新本地视图C，有时还会进一步传播这些区块--例如使用比特币这样的八卦协议--以确保所有诚实的农民最终会得到它。 输出包含两个（可能都是空的）集合（Γf , Γn），其中Γf (Γn)包含了刚刚附加到C中的所有有效的、新鲜的和最终确定的（非最终确定的）块（如下文定义）。对于Γn中的每一个区块，我们也会在它之前添加主干区块的哈希值，因为在计算下一个VDF挑战时需要用到它。 我们不会完全指定Chain.update功能的伪代码，因为它不是Chia所特有的。我们可以方便地定义一个区块（作为Chain.update的输入）可以有以下三个谓词： 非最终化（(non-)finalized）：（如3.2章节中所定义的）一个块γ=(β=(i，σ，τ ))，α=(φ，data))称为最终化；如果VDF输出的τ缺失了，则称为非最终化。 有效的（valid）：一个（最终化或非最终化）区块如果扩展（如3.2章节中所定义的）了一个C中已有的区块，则是有效的。 新鲜（fresh）：块是新鲜的，如果它是有效的，而且还没有在C中（如果它已经最终化，我们也认为它是新鲜的，但只有它的非最终化版本已经在C中了）。 注释4（多重枝叶块）。诚实的农户会为他们找到的每一个PoSpace准确地签下一个枝叶块（参见下面算法3中的第13行），但恶意的农户可能会为同一个PoSpace签名并传播不止一个枝叶块。我们指定Chain.update通常会将它看到的任何给定PoSpace的第一个枝叶块视为有效的枝叶块，但是如果PoSpace得到了新块的最终确定和扩展，并且这个新块扩展的枝叶块与我们最先看到的枝叶块不同，就必须偏离这个规则。例如：在图5的视图中，即使我们先看到αi∗+1，我们也会认为αi+1是正确的枝叶块。
4.2 空间农民算法
为了简化论述，我们假设想要奉献空间的各方都奉献了相同数量的N位数，但这并不是必要的，我们将在备注8中详细讨论。想要充当空间农夫的一方首先要初始化自己的空间S（和其他一些变量）以运行下面的SpaceFarmer.init算法。 注释5（存储无限向量）向量pos count的第i个条目存储了深度i处产生了多少个证明。我们认为pos_count是无限的，但它永远只有一个微小的活跃窗口j，......。, j + δ，这样∀i < j，pos count[j] = κ，而∀i > j，pos count[j] = 0，所以它可以被有效地存储。在下面的伪代码中，时间领主使用的最终化和运行向量也同样成立。 初始化之后，空间农民运行无限循环脚本SpaceFarmer.loop。在这个循环中，对每一个从网络中接收到的有效的、新鲜的和最终确定的区块，SpaceFarmer.farm都会被调用，它决定是否计算一个空间证明来扩展这个区块。 SpaceFarmer.farm伪代码中只影响枝叶的部分用紫色显示。 注释6（考虑到难度重置）如果我们考虑到难度重置，下面的SpaceFarmer.farm算法3以及TimeLord.finalize算法6就会变得更加复杂。具体来说，如果这个新的区块是一个链的头部，而这个链的 "累积工作 "比我们迄今为止在这个深度看到的κ链要高，那么这些算法可能不得不在深度i处扩展/最终确定一个区块，即使它们已经在这个深度扩展/看到了κ区块。例如，如果我们有一个网络分割，农民落在网络控制空间较小的部分，随着分割的结束，我们希望他们切换回另一个分区产生的较重的链条，就可能发生这种情况。我们在本文中省略了一些细节。 注释7（保持较小的网络负荷）如果SpaceFarmer.farm生成了一个新鲜的（非最终确定的）区块，它将调用Chain.update更新C并传播这个新鲜的区块。传播空间农民创建的每一个区块都会产生大量的网络负荷。 为了避免这种情况，我们可以指定Chain.update，这样它就不会传播区块（无论是否最终确定，本地生成或从网络中接收），这些区块基本没有机会最终进入区块链。这样一来，网络负荷就从二次方程式(农户数量)降到了线性(每个农户的通讯也从线性降到了恒定)。 注释8（处理非等值空间）我们假设每个空间农民正好奉献了N位的空间，但实际上农民想要贡献的空间数量会有很大的不同。处理这个问题的一个简单的办法是，让N成为一些任意的空间单位（1位，或者100GB），现在一个拥有k-N，k>1位空间的农户可以模拟k个空间的农户，每个农户有N个空间。这种解决方案在养殖过程中会产生计算成本，在固定空间中是线性的。更好的解决方案是允许空间农民只初始化一个大小为N - k的空间证明（即把SpaceFarmer.init "S ← PoSpace.init(N) "中的第4行改为 "S ← PoSpace.init(N-k)"）。 如果空间农夫现在生成空间σ的证明，那么最终确定区块的时间不仅仅是由一个在[0，T]中统一的值t给出的（计算方式为t := 0.H(µ)。在下面算法6中的第8 行的T值，农民可以使用这些值中的最小值，而不是让其在t1 :=0.H(σ，1) .T，......。，tk := 0.H(σ，k) .T中抽取K个随机值。在农夫看来，有k个证明，并为每个证明得到一个随机值，和有一个证明给出k个随机值一样，但后者效率更高，因为只需要计算一个，而不是k个空间证明。 上述解法的成本在某种意义上仍然是以k为线性的，因为必须对H 进行k次评估才能找到最小的ti。在Spacemint[PPK+15]中，描述了一个解决方案，其渐近成本其实只是ploylogarithmic。简而言之，人们用H(σ)作为随机币，从一个分布中取样，这个分布对应于从[0，1]中均匀取样的k iid值的最小值。这样一来，即使空间的粒度N只有很小值，甚至值为0，农民的效率也可以很高。
4.3 时间领主算法
除了空间农民，维持区块链的发展，至少需要一个时空领主参与确定区块。回顾一下，要最终确定一个具有空间证明 σ的区块，需要计算一个关于挑战H(σ)的VDF，运行时间依次为0.H(σ)- T。要以时间领主的身份参与，当事人首先要运行下面的简单初始化，它从网络中检索当前的区块链，并初始化两个向量，用于跟踪每个深度已经计算了多少个VDF输出和当前正在计算的VDF输出。 初始化之后，时间领主运行无限循环的脚本TimeLord.loop。
在这个循环中，每当收到一个有效的、新鲜的、非最终化的块时，就会调用TimeLord.finalize。 然后，这个算法决定是否启动一个线程来计算一个VDF输出，以最终完成这个块。此外，对于每接收到一个有效的、新鲜的和最终确定的区块，都会调用TimeLord.restore，它将本地视图调整为考虑到这个区块。 时间主宰的状态包含两个向量，即finalize和running，其中在任何时间点，对于任意i∈Z： finalized∈{0, 1, ...... , κ}包含深度为i的最终确定的（由时主自己确定的，或者从网络中接收到的）块数（一旦这个计数器达到κ，就不再增加）。 running ∈{0, 1, ... ... , κ}包含当前正在运行的计算VDF的线程数，该线程将在深度i处最终确定一个块。总而言之，时间领主算法的目标是尽可能快地在每个深度i处生成κ确定区块。 由于我们只是想要κ块，所以对于任何深度i在任何时间点上，都认为0≤finalized+running≤κ，此外，对于每一个i，running的VDF线程是--给定时间领主的观点--是可以最早确定的线程。具体来说，这意味着在收到网络发来的最终确定的块后，时间领主可能会中止计划在最后完成的VDF线程，因为这个线程会在这个深度创建(κ+1)个块。在接收到一个非最终化的区块后，时主可能要开始对这个区块进行最终化，在这种情况下，可能还要中止预定最后完成的VDF线程。 注释9（时间领主平行论）如果K=1，那么一个时间领主永远不会有一个以上的VDF线程同时运行。如果κ>1，那么理论上线程数是没有上限的。如果κ=2，那么我们可以有很多线程，如果在很多连续的深度，第二好的空间证明比最好的证明差很多，如图6所示。这种具有pτ并行线程的兴奋丛是不太可能的（其概率以p为单位呈指数级下降），在实践中，能够并行运行，比如说，2κ的VDF在大多数时候就足够了。在极少数情况下，我们只需暂停计划在最后完成的VDF（这将减少该块在最终链中结束的机会，但在这个特定的配置中，该块追赶的机会极低，无论如何都不会成为孤块）。 注释10（空间和时间使用相同的k值）请注意，我们对每个深度的空间农民产生的空间证明数量和每个深度的时间领主产生的VDF输出数量使用相同的参数κ。这样我们就可以保证——如果至少有一个诚实的空间农民，一个时间领主总是具有足够的（即k）区块在每一个深度上进行最终化。而且如果至少有一个诚实的时间领主的话，每个空间农民总会得到足够的（即κ）最终确定的区块来扩展。但当然也有可能（由于网络延迟或对抗行为）在一定深度上看到超过κ的最终块。
5. 难度调整
在本节中，我们将讨论如何调整难度参数T，以确保区块以大致相同的间隔出现，即使专用于确保Chia的空间或VDF计算的速度随时间而变化。回想一下，在TimeLord.finalize算法6中使用了此参数，在该算法中，最终确定一个PoSpaceσ区块所需的VDF的时间参数计算为t：= 0.H（σ）·T。 图6：注释9中讨论的配置的说明，其中在时间t，多达7个VDF线程（红色显示）并行运行。
5.1比特币的难度调整
参数T的作用类似于比特币中的难度参数D。比特币中的D规定了解决扩展一个块所需的工作证明的难度：要附加一个块β，需要找到一个非ceν，使0.H(β，ν)<1/D。 假设H的行为像一个随机函数，则对H的预期D评估对于找到这样的证明是必要和充分的。为了使新块平均以大约600秒（= 10分钟）的速度保持在区块链上，尽管事实上，挖矿的哈希能力随时间变化很大，但参数D每隔2016个块进行调整（≈ 每两周）如下：比特币中的每个块都包含一个时间戳（一个整数，说明自1970年1月1日以来的秒数）。考虑一个长度为i的链，其中i是2016的倍数。让χj表示第j个区块中的时间戳，Dc表示当前的难度(i-2015至i个区块采用该难度)。 接下来2016个区块的难度Dn计算如下。 如果我们将新的难度设置为Dn := D0，这将使下一个区块的区块到达时间改变为10分钟（在预期中），假设哈希力与过去2016个区块的哈希算力相同（平均）。比特币的难度调整基本就是这样，只是多了一条规则，每次调整的难度变化不允许超过4倍，所以实际难度设置为 正如我们将在下面的§5.4章节中介绍的那样，将这个值设置为4似乎有一个不为人知的具体原因。 图7：说明在§5.2中讨论的难度参数的磨合攻击，在深度i的难度重置前，枝叶块αi1、αi2、αi3右的时间戳略有不同，导致深度i+2的块的PoSpace挑战c1、c2、c3不同。
5.2 使用难度重置的研磨攻击
正如我们在§1.4中所讨论的那样，通过将链分成树干和枝叶，并且只在树干中使用唯一的基元，我们可以防止任何形式的挖掘攻击（请回顾一下，这些攻击指的是研磨攻击，即对手试图以多种不同的方式扩展块），因为树干中的块不能以任何方式被研磨。这个简单的论证忽略了难度参数T，我们观察到，使用与比特币相同的难度重置机制，可以对Chia进行微妙的挖矿攻击。从高层次上看，原因是（不可磨）树干并不完全独立于（可磨）枝叶，因为VDF的时间参数取决于难度参数T，而难度参数T本身是由枝叶中的时间戳计算出来的。 利用这种连接可以发起挖矿攻击，如图7所示。 具体来说，当i是2016的倍数时，考虑一个深度为i-1的链（其头部区块γi-1=（βi-1，αi-1）），所以在第i个区块之后，我们会有一个难度重置。现在拥有空间S的恶意农民： 1.在深度i处生成一个主干块βi=（σi，τi），该主干块扩展γi 1。 2.生成许多枝叶块（比如说3个，如图7所示）αi1、αi2、αi3，这些枝叶块通过包含稍微不同的时间戳而有所不同。现在农户在深度i处有三条带头块γij = (βi，αij )，j∈{1，2，3}的链。 3.每条链都定义了一个有不同的难度参数T1, ... ..., T3用于深度为i + 1, ... ... .i + 2016的区块，因为每个Tj都是用不同的时间戳计算的。 4.用区块γij+1=（（σi+1，τij+1），αi+1）来扩展每个区块γij，j∈{1，2，3}。由于我们使用不同的时间参数tj = 0.H(σi+1)- Tj ，VDF输出τij+1将是不同的，那么深度i+2的PoSpace的挑战cj = H(τij+1)也将是不同的。 以上构成了一种磨合攻击，恶意农民可以对难度调整后的一个区块，获得任意多的挑战（数量只受他可以并行计算的VDF数量限制）。每2016个区块能够研磨一个区块，这似乎并不是一个严重的威胁，但一个拥有一小部分空间的恶意农民可以并行计算许多VDF，可以创造相当长的分叉，超过诚实的链条，从而使得双花得以发生。 在下一节中，我们概述了Chia的调整程序，它可以防止这种研磨攻击的发生。 图8：比特币和奇亚的难度调整说明。在比特币中，新纪元Dn（红色）的难度是用它之前的纪元Dc的时间戳（橙色）计算出来的。 在Chia中，计算新难度Tn的周期被向后移了四分之一个纪元。
5.3奇亚的难度调整
Chia中对难度T的调整与§5.1中讨论的比特币中的调整类似，但为了避免§5.2中概述的研磨攻击，调整不会在用于计算的时间戳被公布后立即启动，而是延迟几个区块。 具体来讲，我们在下面讨论Chia中一个纪元有2016个区块（即和比特币一样），目标到达时间是200秒（在比特币中是600秒），我们设置难度重置前的延迟适用于一个纪元的四分之一，即504个区块。 假设我们有一条长度为i的链，让2016除以i，且设置Tc为当前难度参数（用于i -1511到i+504的区块）让Tp作为之前的难度参数（用于i-3527到i-1512的区块）。回想一下，χj表示第j个数据块的时间戳，使得 将下一个难度参数Tn（对于i+505至i+2520的区块）设置为T’，将导致（预期）区块到达时间为200秒，假设专门用于耕作的空间和VDF的速度是上一个2016区块的平均水平。我们本质上将Tn设置为T’，但和比特币一样，我们不允许连续的难度参数波动大于4倍的情况发生。 让我们直观地说明为什么此调整可以防止来自5.2节的攻击。从理论上讲，恶意的农民仍然可以像§5.2所述那样发起严厉的攻击，但是现在还不足以计算出两个区块深度（即，图7中深度为i和i +1的区块）之前的（主干）链。 对于PoSpace（深度i + 2），他们面临着不同的挑战。但现在，他们需要计算一个长度为2的链条，加上难度调整启动前必须等待的504个区块，也就是深度为i+505。如果这个506块的分叉落后于诚实链，那么对手在i + 505深度处遇到许多挑战这一事实将不足以使对手赶超。另一方面，如果对手足够强大，可以以接近诚实链的速度计算很长（506区块）的分叉，那么由于区块生成时间的差异性，这个对手已经能够比诚实方更快地生成较短的链（但仍然足够长以至于能够发生双花），而且概率很高。
5.4 关于4的重要性
如§5.1所述，比特币不允许相邻纪元的难度参数变化超过4倍，我们在Chia中调整了这一规则。 4的选择可能看起来很随意，但在这一节中，我们将概述一种针对比特币的攻击，如果中本聪不是以4，而是以某个小于e≈2.718的值ξ来约束两个纪元之间的波动，那么这种攻击是可能的。 攻击主要是理论上的，原因有以下几点： 它需要51%的对手且其收益微不足道，而且攻击会产生一个时间戳非常不平衡的链，因此很容易被检测到。尽管如此，我们还是对攻击进行了更详细的阐述，因为波动边界值竟然打开了一个攻击矢量，它应该指导这个看似几乎不相关的参数的选择。 如前所述，在这次攻击中，我们考虑的是控制了大部分哈希算力的对手，称为51%的对手。 这样的对手可以进行双花，但为了不破坏对货币的信任，他们可能会选择不这样做，而是利用自己的资源从区块奖励和交易费用中尽可能多地榨取利润。51%的对手可以通过简单地忽略其他矿工产生的所有区块，这样每10分钟产生一个区块的预期，就可以确保最长链上100%的区块是他的（从而获得所有奖励）。对手可以通过增加更多的哈希算力来增加这个频率，但这只能增加一个纪元的频率，因为下一次的难度调整会让时间再次降到10分钟的目标频率。 如果对手后来再次将哈希算力降低到原来的水平，他们将为之前的增加付出代价，在整个纪元内以慢于10分钟的速度创建区块。从简单的计算可以看出，最好的策略就是保持哈希算力不变。这种说法忽略了波动边界ξ。在下一节中，我们将介绍，如果且仅当波动边界ξ小于e≈2.718时，51%的对手是有可能在保持难度不变的情况下，以快于目标时间10分钟的速度发布区块的。
5.4.1 ξ < e时的攻击 假设比特币使用的是波动边界ξ0和一些c=c(ξ)∈Z+，存在一个纪元链(每个纪元长度为c块)，其中第一个纪元的难度为D-start，最后一个纪元之后的难度(根据链中包含的时间戳计算)为D-end，使得 1）难度按固定系数D-end=D-start.（1-δ）下降。 2）链的平均区块形成时间（由时间戳表示）最多为10分钟。 通过以上两点，51%的对手可以在不增加难度参数且生成一个平均区块的时间严格低于10分钟的情况下，产生一条链。他们按照上面的方法生成并公布链，然后附加一个平均块生成时间严格小于10分钟的纪元。在这个纪元之后，难度就变成了Dend*（D-start/ D-end）= D-start，所以又回到了初始难度，而上一个纪元的区块生成时间，也是整个链条的生成时间，严格低于10分钟。 现在我们将阐述如何构造一个满足上述1）和2）点的链。图9中给出了一个说明。设ξ0为某个小常数。让Z := 2016* 600表示比特币一个纪元的目标时间（以秒为单位）。我们将考虑一个包含1/E个纪元的链，让Xi表示第i个纪元的时间除以Z（这里的时间是指本纪元最后一个区块的时间戳与前一个纪元的时间戳之差），所以如Xi=1表示第i个纪元的平均区块到达时间正好是10分钟。我们在区块中设置了时间戳，所以第一个纪元过的极快，而其他纪元需要的时间比目标稍长。具体而言，我们将Xi设为 这个1/E纪元链生成的总时间是 我们假设1/E>ξ，那么在第一个纪元之后，难度就会随（最大允许系数）ξ系数增长。之后，它以1/(1+E)的系数减少1/- 1epochs，因此最后变为 当E趋近于0时，上述最后一项趋近于1/e，即 因此，对于任何ξ0，使D-end严格小于所谓的D-start。 图10：算法9计算的Clκ,h的模拟样本图示：l=100，h=99，κ=1至10(底部κ=1，顶部κ=10)。我们看到，随着κ的增加，（由h个诚实的农户耕种长度l的链条）时间如何从1（=l/（h+1））向1/e≈0.3678下降。
5.4.2 最佳攻击 我们所描述的特殊攻击只有在ξ<e的情况下才有效，但不难看出，这不仅是充分的，而且是必要的。也就是说，如果且仅当ξ<e时，就存在一个平均区块生成时间低于目标，且末端难度不大于开头的链。< e的情况下才有效，但不难看出，这不仅是充分的，而且是必要的。也就是说，如果且仅当ξ<e时，就存在一个平均区块[="" size][="" font][="" color][="" i][="" align][color=rgb(51," 51,="" 51)]
6.链增长和k
在本节中，我们将对Chia区块链进行初步的安全分析。我们从[GKL15]获取灵感，[GKL15]介绍和分析了比特币主干。
6.1 我们的理想设置
正如前言中所讨论的，我们的分析是在一个理想化的环境中，其中：I.我们没有网络延迟；II.我们没有难度重置；III.对手计算VDF的速度不会比诚实方快；IV.而且PoSpace是理想化的，也就是说，它们绝对不允许进行时间记忆权衡。我们考虑这种理想化的环境，这样我们就可以专注于实际的挑战。即使有上述限制，对Chia的分析也是非凡的。这与比特币形成鲜明对比，在比特币中，一旦我们做出假设i.、ii.和假设iv.的类比，那么基本的安全属性（非零链质量、活跃度和持久性）就是微不足道的，而假设iv.对比特币来说意味着PoW是理想化的。我们有信心，不过目前还没有弄清楚细节，在我们目前的分析中，消除上述限制可以使用现有的或直接的技术来完成（代价是实现较弱的数量界限和有更多的技术证明）。更具体地说，比特币骨干论文[GKL15]考虑了网络延迟，他们的后续文章[GKL17]也考虑了难度重置。对Chia来说，消除一和二的限制应该是可能的。正如备注3中所讲，在Chia中，我们实际上可以容忍显著的网络延迟而不会降低安全性。至于iii.，让对手比诚实方快一个系数ζ>1来计算VDF，与增加对手空间一个系数ζ的效果是一样的，所以这一点很容易被考虑进去。我们还可以回顾一下，我们假设每个农民奉献的空间完全相同（N位），我们在注释8中讨论了如何舍弃这个假设。除了上面讨论的假设外，我们当然总是假设加密构建区块是安全的。尤其是，我们假定签名方案在满足所选消息攻击时不可伪造的标准安全性概念，并且哈希函数具有抗碰撞性（当用于链接时）或（更强的假设）其行为类似于随机函数（当用于将不可预测的价值映射到统一的挑战时）。
6.2 随机变量Clκ,h模拟链式增长
为了正式论证和模拟Chia的安全性，我们定义κ，h，l∈Z+为一个随机变量Clκ,h，其分布是长度l的第一条路径出现在我们理想化的环境中所需要的时间，在这个环境中，h个诚实的农民使用参数κ，T=1，η=1来耕种一条链（并且至少有一个诚实的时间领主来最终确定区块）。我们将难度T和计算一步VDF所需的时间η固定为1，只是因为增长一条链的时间在T和η中是线性的，所以这些参数是无趣的，我们可以通过固定这些参数来保持较低的参数数量（不过，正如在备注6中所概述的那样，难度可以重置的事实使事情变得复杂）。我们将这个变量的期望值表示为
采样Clκ,h的伪代码详见算法9。
注释11（如果k>1时，如何开始采样Clκ,h？）在定义κ>1的Clκ,h时，我们遇到的一个困难是如何定义采样的 "初始配置"。我们可以假设一开始只有一个区块可以扩展，但（除了创世区块）老实的农民在每个深度都有κ> 1个区块可以扩展，所以这将高估了种植链所需的时间。我们可以假设在起始时间有κ块，但这将低估了时间，因为在实际的链条中，给定深度的那些κ块将在不同的时间最终确定。在定义Clκ,h时，我们仍然选择了这个选项（即在算法9的第2行，我们从时间0开始使用κ块），但由于链几乎在我们开始采样后就开始以 "典型 "的方式表现出来（这在图3中可以看到），Clκ,h是一个很好的近似值，无论实际的起始配置是什么，都可以很好地近似地反映出种植链所需的实际时间。继续看，我们在§6.4章节中定义θκ为大l（其实是为liml→∞）的原因只是为了让精确的起始架构没那么重要。
6.3 Clκ,h的分析界限
对于κ=1，利用以下事实不难确定Cl1,h的准确期望值。命题1（统一随机变量的k阶统计）让X1，...，Xn分别表示[0，1]中的每个均等值。那么这些Xi的第k个最小值的期望是 k/(n+1)。论点1（k=1链式增长）
证明。让Zi通过对h个随机变量X1，......Xh进行随机抽样，iid在[0，1]中呈均匀分布，则
根据命题1，我们有
根据线性期望，我们有
由于遵循严格意义上的大数路径总是会提高增长速度，对于任何l，κ，h，我们有
幸运的是，这种加速并不是无限的。即使κ到了无穷大，它最多可以加快链式增长的系数为e≈2.718。论点2（链式增长上限）。对于任意l，h，
证明见附录A。
6.4 ιi 和θi
了解clκ,h作为κ的函数的表现至关重要，原因有二。第一，我们需要知道在极限κ → ∞时会发生什么，以了解潜在的对手（可以运行无限数量的VDF服务器）可以多快速地增长链。第二，我们需要了解小κ的情况，以便为诚实的农民设定一个好值。继续阅读，你会发现设置κ=3似乎是最好的权衡。由于我们只有对极端情况κ=1和κ=∞的分析界限，所以我们将依靠对两者之间数值的模拟。第12页的图3说明了1≤κ≤4的链式增长的模拟情况。这个数字可能会让我们相信，与κ=1的情况相反，当κ→∞时，链确实以一个无限制的系数快速增长。幸运的是，根据论点2，情况并非如此，使用更大的κ可以得到的最大加速是e≈2.718。在图10中，我们模拟了一个更大的κ=10的情况，在这里，这种收缩变得比较明显。我们将θκ∈[0，1]定义为可以通过延长κ而不是只延长一条链来加快链的生长速度的因素：
我们在大l和h的极限中定义这个值，但它的收缩速度非常快，所以我们可以通过对相当小的有限l、h进行采样Clκ,h来获得良好的近似值。我们之所以考虑l中的极限值，是考虑到备注11中阐述的取样的初始配置的问题。我们有：θ1=1（根据定义）θ∞ ≥ 1/e ≈ 0.367（根据论点1和2）∀i : θi+1 < θi（多多益善）θi，i = 1，......，100的模拟值如第11页图2所示（用蓝线表示）。我们将ιi定义为遵循κ=i策略的诚实农民必须控制的那部分空间，这样他们就能比控制剩余1∞ιi部分空间并遵循κ=∞策略的恶意农户更快地种植链。我们将在下一节使用这个值来陈述Chia有趣的安全属性。我们要求
在证明这个简单的说法之前，我们先观察一下，作为理智检查，对于i=∞，我们得到ι∞≤1/2（用θ∞≥1/e），这是合理的，因为在这里，诚实的农夫和恶意的农夫做的事情是完全一样的，所以有一半的空间（即和恶意的农夫一样多）就足够了。 在本节的下半部分，我们将推导出式(7)。如果s /θi= s’/θ∞，则遵循以s为空间、κ= i策略的农民可以以与对手（遵循κ=∞策略）相同的速度种植空间为s’的链。使用θ∞≥1 / e可得出
在下面的最后一步中使用此方法，我们可以给出恶意农民可以控制的总空间的分数s’/(s’+ s)的下限为
图11：该图说明了已实现的链质量——即保证来自诚实矿工/农户的区块的分数ρ（y轴）——假设他们持有总哈希能力/空间的ι部分（x轴）。绿线表示理想的理想界限ρ=ι，其中没有任何策略比诚实的采矿策略更好。蓝线说明了比特币链质量ρ= 1∞1ιι，这与自私的采矿攻击相匹配[ES14]。对于Chia，我们表明，只要诚实的农民遵循κ=i的策略，如果ι>ιi，则ρ>0。图中，ι1=e/(1+e)≈0.73106(分析证明)，ι3≈0.6151(通过模拟，Chia将用κ=3)，ι∞=0.5(琐碎)。在所有情况下，我们都不知道随着ι从ιi到1的增加，ρ是如何从0到1的（虚线）。
6.5 奇亚骨干
在§6.4中，我们建立了如果诚实的农民至少控制了总空间的ιi部分，那么遵循κ=i策略的诚实农民比可以并行计算无限数量的VDF的恶意农民（从而遵循κ=∞策略）可以更快地增长一条链。我们用分析法证明了ι1≈0.731，用模拟法证明了ι3≈0.615。在Chia中，诚实的农民会遵循κ=3的策略并进行耕作。因此，有必要假设遵循κ策略的诚实农民至少控制了ικ部分空间，否则就有可能出现双花等攻击。在本节中，我们表明，假设这也足以保证Chia的有意义的安全属性。具体来说，我们考虑在[GKL15]中为比特币引入的链质量概念： 如果在链的任何足够长的部分（如诚实的各方所见），至少有ρ部分的区块必须是由诚实的矿工贡献的，则链的质量为ρ∈[0，1]。如果矿工控制了ι∈[0，1]部分哈希算力，我们理想的情况是希望他们贡献出ρ=ι部分的区块，因此他们的区块奖励份额与他们贡献的资源份额相对应，图11中的绿线表明了这一点。 链质量可能看起来并不是区块链最重要的属性，但它意味着持久性（一旦一个区块在链上足够深，它将永远留在那里）和活跃性（所有交易最终将被添加到链上，并最终足够深，因此它们可以被视为确认）等自然属性。[GKL15]表明，比特币实现的链质量为ρ=1-(1-ι)/ι，如图11中蓝线所示。虽然这比 "公平 "的ρ=ι要差得多，但这是人们所能期望的最好结果，因为这个上限与自私的挖矿攻击相匹配[ES14]。对于Chia，我们证明，如果诚实的农户使用κ=i策略，那么只要ι>ιi（其中ιi是比上一节介绍的恶意农户更快地发展链条所需的空间分数），链条质量就是非零。与比特币不同的是，我们目前还不知道随着诚信农民控制的空间分数ι从ιi增加到1，链质量ρ到底是如何提高的，也就是图11中(ιi，0)和(1，1)点之间的虚线到底是如何表现的。论点3（奇亚的链质量）在§6.1的理想化环境中，对于任何i∈Z+，以下论证成立：如果诚实的农民遵循κ=i的策略，并且控制了超过ιi的部分空间（也就是说，我们有h个诚实的农民，每个农民控制了N个比特的空间，还有一个恶意的农民，拥有m-N个比特的空间，其中mh+h>ιi），那么链条质量是非零。在证明这个定理之前，我们首先需要证明以下内容：论点4（无减缓论证）在§6.1的理想化环境中，对手无法减缓链的增长。也就是说，无论对手做什么，诚实方都会看到一条链，（在预期中）至少和对手不在场时一样长。如果对手拥有更大的空间，并且可以比诚实的农民更快地计算VDF，这种情况甚至是成立的（但我们需要假设签名方案是安全的）。需要注意的是，这个论证本身并没有给出任何有意义的安全保证，它只是说在诚实方看来，总会有一条链至少和对手不在场时一样长，但这条链可能只包含对手生成的区块（链质量为0），对手甚至可能替换掉整条链子（没有持久性）。论点4的证明。我们假设对手知道身份，也就是所有诚信农户的公钥pk，但却不知道对应的秘钥。正如在备注2中已经讨论过的，正因为如此，对手将无法预测诚实农民的空间证明的质量。我们声称，正因为如此，每当对手发布一个区块时，只能（在预期中）增加链的增长速度。 如果这个区块被诚实的农民忽略了（因为它不在这个深度的前κ区块内），这就非常清晰了。否则，诚实的农民就会扩展这个区块，而不是他们本来会扩展的其他区块。但从不知道秘钥的对手的角度来看，新块和被踢出的块所具有的品质分布是完全一样的。因为新的区块必须在被踢出的区块之前进行最终确定，而这只能提高链成长的速度。论点3 的证明。假设矛盾是链质量为零。这意味着，诚实方所观察到的整条链仅包含对手所耕种的区块。根据论点4，这条链至少与诚实的农民在没有对手的情况下所开采的链一样长。这是自相矛盾的，因为根据定义，一个对手控制的空间小于1-ιi的部分，不可能比遵循i=κ策略的诚实农民更快地发展链条。
参考文献
[AAC+17] Hamza Abusalah, Jo¨el Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, and Leonid Reyzin. Beyond hellman’s timememory trade-offs with applications to proofs of space. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 357–379. Springer, Heidelberg, December 2017.[BBBF18] Dan Boneh, Joseph Bonneau, Benedikt B¨unz, and Ben Fisch. Verifiable delay functions. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 757–788. Springer, Heidelberg, August 2018.[BBF18] Dan Boneh, Benedikt B¨unz, and Ben Fisch. A survey of two verifiable delay functions. Cryptology ePrint Archive, Report 2018/712,2018. https://eprint.iacr.org/2018/712.[CP18] Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequential work. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 451–467. Springer, Heidelberg, April / May 2018.[DFKP15] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 585–605. Springer, Heidelberg, August 2015.[ES14] Ittay Eyal and Emin G¨un Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Nicolas Christin and Reihaneh Safavi-Naini, editors, FC 2014, volume 8437 of LNCS, pages 436–454. Springer, Heidelberg, March 2014.[GKL15] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 281–310. Springer, Heidelberg, April 2015.[GKL17] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol with chains of variable difficulty. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 291–323. Springer, Heidelberg, August 2017.[Pie18] Krzysztof Pietrzak. Simple verifiable delay functions. Cryptology ePrint Archive, Report 2018/627, 2018. https://eprint.iacr. org/2018/627.[PPK+15] Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Jo¨el Alwen, Georg Fuchsbauer, and Peter Gaˇzi. Spacemint: A cryptocurrency based on proofs of space. Cryptology ePrint Archive, Report 2015/528, 2015.http://eprint.iacr.org/2015/528.[Wes18] Benjamin Wesolowski. Efficient verifiable delay functions. Cryptology ePrint Archive, Report 2018/623, 2018. https://eprint.iacr.org/2018/623.
链质量的缺失证明
在这一节中，我们证明了状态，并证明了定理1，论点2随是该定理的必然推论。对于h，l∈Z+，让Th,l表示深度l的全h-ary树，其中每个边都标有从[0，1]中选取的值iid。这棵树中一条路径的权重是这条路径上的边的标签之和。我们考虑下列随机变量:
按照算法9中的采样结果。也就是说，给定Th,l，我们考虑从根部到枝叶的路径，从根部开始，在每一级都跟踪权重最低的κ路径（如果κ≤h，则有hl条）。对于仅跟踪一个或所有路径的重要特殊情况，我们引入以下变量。
是指从Th,l的根开始的路径（长度l）的权重，在每一个节点上，我们按照最小值的边缘（直到到达枝叶）。
是Th,l中从根到叶的任何路径的最小权重。
图12：当h=2和l=3时，变量Tlh、Hlh、Alh、Zlh的结果。Yl：是统一从[0，1]中选择的l iid值之和。Z`h：是min {Yl[1]，。 。 。 ，Yl[hl]}，其中每个Yl是如上所述的iid值。我们用相应的小字母表示这些变量的期望值，例如，hl h表示E[Hl h]。注意，对于l =1，我们有H1h ∼A1h ∼Z1h，尤其是h1h=a1h=z1h。Hlh对应于诚实的农民利用h空间耕作一条长度l的路径所需的时间，他们总是扩展找到的最好的证明。Alh对应的是对抗式（或理性）耕作，在这种情况下，人们会扩展出所有可能的链。引入Zlh只是出于技术上的考虑，它比Alh更容易分析，由论点 5可知它是Alh的下限。论点5。对于任意h，l，以及所有x∈[0，l]，以下情况均成立：
因而也有
证明。Pr[Zlh≤x]以及Pr[Alh≤x]都考虑了这样一个事件：hl路径中至少有一条路径，每条路径的长度l，且每条边缘被赋予的权重是[0，1]中的统一值，权重最多为x。 唯一不同的是，在后者中，边缘权重是相关的（因为树中的许多路径共享边缘）。长度≤x（或任何其他谓词）的预期路径数在Zlh中与在Alh中完全相同。但从直观上看，在Zlh中，至少有一条路径是短的概率更大，因为在Alh中，长度是正相关的。我们省略了以使这个论点正式化。我们证明论点1，它指出
根据定义cl∞,h=alh≤hlh=cl1,h，为了证明Lemma 2，我们必须限制alh可以比hlh小多少。我们要问的具体问题是，如果诚实的农民有空间h，那么我们能给对手的空间M=M(h)的上限是什么(扩大所有路径)，使他们不能比诚实方更快地发展链条。根据以下定理，设置M=h/e是必要的。定理1.当h=eM(其中e≈2.718)，l/h<1时< span="">
证明。Yl的累计分布函数为
我们将考虑x=l/eM=l/h的情况，因为当l/h<1时，上述之和只有一项。使用< span="">ll/el1 ≤ l!,可以得到
因此，受联合约束
第一步利用定理 5，当hlh=l/(eM+1)时，第二步利用上式进行计算
相当于
</e的情况下才有效，但不难看出，这不仅是充分的，而且是必要的。也就是说，如果且仅当ξ<e时，就存在一个平均区块生成时间低于目标，且末端难度不大于开头的链。 | 
发表于 2021-5-2 00:52:27
