什么是可验证延迟函数（VDF）

今天药忘吃喽~ 2022-08-31 15:13 128阅读 0赞

### 文章目录 ###

*  什么是可验证延迟函数（VDF）
 *  VDF用途
 *   *  VDF 对于一些从公共来源获取随机数的方法非常有用
     *  解决 Nothing-at-stake Attack
     *  减轻 Long-range Attack
     *  副本证明（Proof of Replication）
 *  参考

# 什么是可验证延迟函数（VDF） #

VDF 这个概念最初由斯坦福大学密码学教授 Dan Boneh 等人在其论文 [Verifiable Delay Function][] 中给出。该篇文章于 2018 年发表在密码学顶级会议之一的 CRYPTO 上。

VDF 是一类数学函数，能够使得该函数的计算需要至少一段已知的时间，即使是在同时使用少量 CPU 进行并行计算的情况下。

VDF 通常会接受一个输入以及一些参数（安全参数、时间参数等），输出一个结果以及相应的证明（可以为空，如果结果能够自带证明）。**验证者会依据输入、参数、输出以及结果来判断 VDF 的结果是否正确。**

VDF 满足以下性质：

1.  VDF 的结果的检验应当是非常有效率的。
2.  唯一性（Uniqueness）：对于任意一个 VDF 的输入，应当有唯一的输出结果能够通过检验。也就是说，不存在两个不同的输出，他们有相同的输入。**如果输出结果包含“结果”和关于结果的“证明”两部分，那么证明部分可以不具有唯一性，但需要保证“验证者因为证明而验证通过，但是输出结果却不是正确的结果”这件事发生的概率小到可以忽略不计。**
3.  串行性（Sequentiality）：攻击者即使能够提前计算很长时间（但不是任意长的时间），并且拥有很多并行处理器（但不是任意多的处理器），利用各种计算方法（确定地计算或是连蒙带猜），能够以少于 tt 的时间计算出 VDF 结果的概率可以小到忽略不计（并不是 0，因为也许攻击者真的就运气好到猜中了呢？）。

> VDF 能够抵抗并行计算加速，这意味着为了计算 VDF，应当完成一系列串行才能完成的任务，后一个任务必须依赖于前一个任务。

这时，对哈希函数有所了解的读者可能会想到一种方案：连续将一个输入哈希 tt 次。这样的方案的确是无法通过并行算法显著地加速的，**但是这样得到的结果，其验证将会非常没有效。验证者需要重复哈希 tt 次的计算，即使保留一些中间结果，验证的工作量和计算的工作量也是常数级别的差距。**

从这个例子我们可以看出，在这样的定义下，可验证延迟函数的构造并没有想象中的那么简单。

事实上，对于上面并不严谨的定义，去掉任何一个性质都会导致我们能够非常轻易地构造出可验证延迟函数：

*  如果不要求验证结果是高效的，也就是说没有显著地比计算结果更快，那么我们可以通过刚才提到的连续哈希的方案进行构造。
 *  如果我们不需要它保证唯一性，那么早在 2013 年 Mahmoody 等人的工作 [Publicly Verifiable Proofs of Sequential Work][] 就已经实现了这一点。
 *  如果它不保证串行性，那么显然构造方法就更多了。

# VDF用途 #

## VDF 对于一些从公共来源获取随机数的方法非常有用 ##

区块链上的随机数一直是一个热门话题。无论是在一些权益证明（Proof-of-Stake, PoS）共识协议的设计里，还是在智能合约平台，譬如 Ethereum 和 EOS，上一些非常火爆的游戏类应用，随机数都占据了核心的地位。同时，很多这些应用中，实际设计的随机数获取方案还非常不成熟，以至经常会有应用因为不安全的随机数而被黑客攻击的新闻出现。

VDF 对于一些从公共来源获取随机数的方法非常有用。比如从股票市场或者是从 PoW 区块链上获取。这些随机源拥有足够的随机性（更严格地讲，是最小熵）。但是高频交易者可以影响股价，同时，PoW 区块链的矿工也可以通过不广播自己挖出的区块来降低自己不想要的随机数结果的出现概率。但是这样的攻击方式成立的前提条件是攻击者有时间在其他诚实参与者之前预测出随机数结果。VDF 恰好能阻止这一点。如果将 VDF 的时间参数 tt 设置到足够长（比如 10 个块的间隔），将最新的区块头作为输入扔进 VDF 中，输出作为随机数结果。那么攻击者只能在 10 个块之后才能知道随机数的结果是什么，那个时候想要再改变结果已经很难了（需要 fork 10 个区块）。

此外，VDF 也可以增强一些多方参与的随机数方案。比如 Commit-and-Reveal 方案中，攻击者可以拖到 Reveal 阶段的最后再决定是否揭示自己的承诺。如果我们去掉 Commit 阶段，并且协议的最后整合所有人的输入之后不直接作为随机数结果，而是放入 VDF 中，并且将 VDF 的时间参数 tt 设置到足够长（晚于最后提交期限），那么即使是最后一刻提交的人也无法知道随机数的结果，操纵结果也就无从谈起。与之相比较，其他的多方参与方案通常最多容忍小于一半的恶意节点，并且交互的开销要比上述方案更大。

## 解决 Nothing-at-stake Attack ##

**正如上一节所述，VDF 可以用于增强随机数生成方案的安全性，因此，在一些使用了随机数来选取 Leader 的共识协议中也可以使用 VDF 在增强其安全性**。一些节约能源的共识协议，例如 PoS，空间证明（Proof-of-Space）以及存储证明（Proof-of-Storage），为了防止 Nothing-at-stake attack，需要使用随机选举每隔一段时间选举出一个 Leader。这些协议使用的随机数方案大多只在诚实参与者占据大多数时保持安全。利用 VDF 可以降低这样的限制到至少存在一个诚实参与者。

> Nothing-at-stake Attack  
> PoS 区块链发生分叉时，共识参与者为了自己的利益会选择在不同的分叉链上同时进行抵押资产参与出块，这样分叉链有可能会一直存在并且分叉越来越多，严重危害系统的一致性，这样的攻击被叫做 Nothing-at-stake attack。在 PoW 链上进行这样的攻击需要分散算力，因此这样的攻击只适用于“节约能源”的共识协议。

…

## 减轻 Long-range Attack ##

几乎所有的 PoS 方案都面临 Long-range attack 的问题。目前 PoS 协议依赖于外部的时间戳服务来帮助他们解决这个问题——只要能判断哪一条链更老，就能阻止这样的攻击发生。VDF 能够帮助 PoS 解决这样的问题。VDF 相当于一种时间流逝的证明，对于给定的 VDF，该 VDF 至少需要多久才能得出结果是一个公共知识。因此，只需要在 PoS 链上包含 VDF 的输入与输出即可证明给定区块的历史。

> Long-range Attack  
> 在 PoS 协议中，任意时刻都有一组权益相关者拥有按照权益多少分配的投票权。PoS 假设大多数权益相关者并没有理由对系统造成破坏，因为这样反而会损害自己的权益。但是如果这些权益相关者在某一个时间点出售了自己的权益，这样的激励对他们来讲是无效的。这些已经出售了自己权益的曾经的权益相关者仍然可以在曾经某一个时间点轻易对（那时他们占据大多数权益） PoS 链分叉达到原有链的的长度，从中攫取额外的利益，这样的攻击被称作 Long-range attack。它在 PoW 上不太可能发生，因为对于 PoW 来讲，无论从哪一个时间点进行分叉，都必须要付出相应的算力才能追上原有的链，想要分叉的区块越多，付出的算力也就越多。

…

## 副本证明（Proof of Replication） ##

副本证明所需要解决的问题是，服务器如何向客户端证明自己在某一专门的存储介质上存储了指定的数据，即使这样的数据是可以从别的存储来源轻易获得的。注意副本证明是为了证明服务器拥有一份数据的副本，而不是证明它有这样的数据。举个例子，云存储服务提供商声称自己为客户的数据做了额外的两份冗余备份来保证用户数据的 availability，因此客户需要为这样的冗余备份交更多的钱。但是怎么证明云服务提供商有一共三份副本而不是两份或者只有一份呢？这就需要用到副本证明。**一种思路是利用在时间上不对称的编码方案（也就是编码很慢，但是解码很快），VDF 可以做到这一点**（事实上是可解码 VDF）。身份为

…

# 参考 #

\[研究\] 可验证延迟函数（VDF）（一）一文搞懂 VDF  
参考URL: https://blog.priewienv.me/post/verifiable-delay-function-1/

[Verifiable Delay Function]: https://eprint.iacr.org/2018/601
[Publicly Verifiable Proofs of Sequential Work]: https://eprint.iacr.org/2011/553