关于可验证延迟函数的一个文雅介绍

我在密码学领域探索新概念已经有一段时间了。自从我上一次在这篇时事通讯中写关于密码学的文章以来，更是如此(我上一次与密码学相关的出版物是我的Zokrate教程和ZKP游戏)。今天，我将分享我对一个概念所做的简短研究的笔记，这个概念我已经听说了一段时间了，密码领域的项目正在广泛探索这个概念：可验证延迟函数。

免责声明：这本出版物可能最终会相当混乱，因为它是我在研究VDF时在“非数字”笔记本上记录笔记的结果。我将尽力而为。

“可验证的延迟函数是以可验证的方式放慢速度的一种方式”。这是我见过的关于VDF的最具说明性的定义(顺便说一句，出自这个令人敬畏的演讲)。但我们为什么要放慢脚步呢？这些全新的原语有何用途？答案是随机性。

在区块链上找到随机性是很困难的。智能合约的执行必须是确定性的，但对于某些应用程序来说，随机性可能会很方便。为了实现这一点，开发人员试图从网络中的信息(如未来的块散列、块难度或时间戳)中获取随机性来源。不幸的是，所有这些方案都有一个关键的限制：每个人都可以观察到他们所做的选择是如何影响链上产生的随机性的。在本文中，您有几个使用块信息作为熵源的易受攻击的随机性实现的示例。

除了智能合约，随机性对于区块链系统运行中的其他关键部分也很重要，比如在证明赌注协议中选举领导人：

他说：“另一个相关的问题是选举证明赌注协议的负责人和验证员。在这种情况下，事实证明，能够影响或预测随机性允许采矿者影响他们何时被选择来开采区块。有各种各样的技术可以解决这个问题，例如Ouroboros的可验证的秘密共享方案。然而，他们都面临着同样的陷阱：必须有一个不串通的诚实多数人在场。

考虑到这些问题，Boneh等人。2018年引入了可验证延迟函数(VDF)的概念。

VDF是需要适度顺序计算才能计算的函数，但一旦找到解决方案，任何人都很容易验证它是否正确。

VDF向输出引入了强制时间延迟，这样恶意攻击者就不能通过预测未来值来影响它。有效的VDF必须具有以下属性：

顺序：任何人都可以在t个顺序步骤中计算f(X)，但是拥有大量处理器的对手不能用明显更少的步骤来区分f(X)的输出和随机结果。如果我们要解决上述问题，这一点真的很重要。恶意行为者在计算VDF时不应该能够区分输出和中间状态，这使他比“接下来会发生什么”更有优势。

可有效验证：给定输出y，任何观察者都可以在短时间内验证y=f(X)(具体地说是log(T))。

这篇文章中关于VDF的一个有趣的注意事项。为什么不能将哈希链视为VDF？

在跳到VDF构造之前，让我们检查一下为什么“显而易见”但不正确的方法解决这个问题失败了。一种这样的方法是重复散列。如果某个散列函数h的计算需要t个步骤来计算，那么使用f=h(h(.h(X)作为VDF肯定会满足上述顺序要求。实际上，不可能用并行性来加速此计算，因为散列的每个应用程序都完全依赖于前一个应用程序的输出。但是，这不能满足VDF的可有效验证要求。任何试图验证f(X)=y的人都必须重新计算整个哈希链。我们需要对我们的VDF进行评估，计算所需的时间比验证所需的时间要长出指数倍。“。

那么，VDF的最佳候选者是什么呢？让我们按照这里的示例进行操作。我们要构建的特定VDF是在一个未知阶数的有限组上的操作(即，在一组具有明确上限和特定数量的未知元素的数字上)。构建有限群的一个好方法是定义一组模为N的数上的所有运算(其中N可以是像两个安全素数p和q的乘法一样奇特的东西)。

其中x是输入值，散列到组中，T是公知的延迟参数，并确定延迟的持续时间，y是输出。我们在有限群上运算，所以从现在开始我们将去掉模N(认为这是隐含的)。

通过这种构造，这个简单的函数已经满足了它成为有效的VDF候选者所需的基本属性之一，即它是连续的。在计算的每一步，我们都需要为下一次迭代进行前一次操作，因为我们不知道组的顺序，从而使其成为串行的。要计算x^2^T，我们必须用从0到T的i来顺序计算x^2^i，因为在每一步中，我们都需要确保结果落在有限的吞吐范围内。这也是为什么我们说T是延迟函数的原因，我们需要T步才能得到最终输出。

“重复的平方计算是不可并行化的，直到最后一次平方才显示最终结果。这些特性都是因为我们不知道G的顺序。这一知识将允许攻击者使用基于群论的攻击来加快计算速度。“。

好的，我们有了一个顺序函数，现在我们需要使它有效地可验证，这样验证器就不需要再次遵循完整的T个步骤。这可以通过构建一个证明来实现。在本例中，证明者和验证者将运行交互协议来执行VDF的验证。

要证明VDF，验证者需要选择一个随机数L，并将其发送给证明者。现在证明者用2^T除以L得到商q和余数r。他计算x^q并将其与y一起发送给验证者。

验证器现在计算(2^T)mod L，并检查y是否等于(x^Q)^L*x^r。如果是这样，那么它实际上意味着验证器完全知道VDF的输出，因此“经受”了T个步骤的计算。为了清楚起见，让我们在这里总结一下交互协议：

验证者：生成随机L并发送给验证者。验证者：计算：(q，r)=(2^T)/L然后：pi=x^q发送给证明者(y，pi)验证者：计算：R=(2^T)mod L检查：y=pi^L*x^r。

瞧，瞧！已验证VDF执行。该证明也可以使用非交互证明来构建和验证，但是需要外部的随机性来源。

他说：“目前有三个候选建筑符合VDF要求。每一种方法都有其潜在的缺点。第一个是在Boneh等人的VDF原始论文中概述的。并使用内射有理映射。但是，评估此VDF需要相当大量的并行处理，导致作者将其称为“弱VDF”。后来，Pietrzak和Wesolowski在未知顺序的分组重复平方的基础上，独立得出了极其相似的构造。

但毫无疑问，了解VDF周围发生的一切的最好资源是VDF研究。我希望我有时间阅读和观看这个网站上所有令人印象深刻的内容(我会成为VDF方面的专家：)。在这里你可以找到关于这个领域的最新论文、演讲和许多精彩的知识。下面您可以看到VDF的许多子字段的图表。

实际上，最让我感兴趣的领域之一(浏览一下VDF研究的内容)是VDF的软硬件协同设计。在这个演讲中可以找到一个很好的例子：

所以你想看VDF的运作，对吗？我找到的最简单的方法是使用这个repo，它包括Boneh的VDF的Rust实现。首先，您需要按如下方式安装该工具(在执行这些步骤之前，请确保在您的计算机中安装了Rust)：

可以尝试的一件很酷的事情(如果您有时间的话)是将延迟参数(我们在上面的示例中设置为100)增加到某个较高的值(例如10000)，看看计算vdf需要多长时间，同时验证结果几乎是立即执行的。但这就是VDF的意义所在，对吧？

关于这种加密原语和它们的潜在用途，我还有很多需要学习的地方，但是第一次接触它们是非常有趣的。下周见！

最后，我给你们留下了两个有趣的视频，它们肯定会比我更好地解释VDF是什么。好好享受吧！