以太坊研究 | 可验证延迟函数（VDF）介绍

01

1. 连续性：任何人都可以在t个连续步骤内计算f(x)，但任何拥有大量处理器的攻击者无法通过更少的步骤将f(x)的输出和随机数区分开来；
2. 可高效验证性：给定输出y，任何观察者都可以在很短时间（即log(t)）内验证y = f(x)。

假设在一场博彩游戏中，用户需要提交一个16位（16 bits）的整数，而获奖号码则是通过向需要20分钟进行计算的VDF提供种子（seed）来确定的。如果某个攻击者在进行了1分钟的VDF计算之后就能知道VDF输出中的4位（4 bits），那该攻击者就能够更改自己所提交的整数，使自己中彩的几率提高了16倍！

在谈及VDF的结构之前，让我们先看看为何一个“明显”但不正确的方法无法解决这一问题。这样的方法就包括重复进行哈希运算（repeated hashing）：如果某个哈希函数h的计算需要 t 个步骤，那通过使用 f = h(h(...h(x))) 作为VDF函数将肯定能够满足上面所提到的连续性要求。

确实，参与者将无法通过并行计算来加速计算，因为任何一个哈希的运用都完全取决于前一个哈希的输出。然而，这并不满足第二个条件，即VDF函数的高效验证需求。在这种方法中，任何想要验证 f(x) = y 的参与者都将需要重新计算整条哈希链。我们需要的是，在VDF求值时，在计算时耗费的时间比在验证时耗费的时间更多，而非更少。

02

1. 为了设立VDF函数，需选择一个时间参数T，一个阶数未知的有限阿贝尔群G，以及一个哈希函数H；
2. 假设输入是X，通过计算y = g2T 让g = H(x)对VDF进行求值。

现在，假设某人断言VDF的输出是某个数字z（可能等于或不等于y）。这意味着z=g^(2^((T/2)) )和v=g^(2^((T/2)) )。由于这两个等式有同样的指数，通过核查一个随机的线性组合（linear combination，如v^(r) z = (g^(r)v)^(2^(T/2))，其中r是{1, … , 2^(λ)}中的随机数，λ是安全参数）来同时对它们进行验证。更正式地说，证明者（prover）和验证者（verifier）需执行以下的交互式证明方案（interactive proof scheme）：

1. 证明者计算v = g^(2^(T/2)) 并将v发送给验证者；
2. 验证者将 {1, … , 2^1}中的随机数r发送给证明者；
3. 证明者和验证者对 g₁= g^(r) v 和z₁= v^(r z)进行计算;
4. 证明者和验证者递归地证明z₁ = g₁^(2^(T/2))

03

Pietrzak方案的安全性分析

1. 当计算递归中的第二步时，我们将得到g₁ = g^(r) v，其中 v = g^(2^(T/2)) m，并需要展示g₁^(T/2 )= v^(r) zm；
2. 左边的m项是m^(T/2)；
3. 右边的m项是m^(r+1)；
4. 由于m的阶数为d，当r+1 = T/2 mod d时这两个数会相等，这种情况发生的概率是1/d。

Pietrzak方案的安全性分析假定的是，参与者可以很容易地生成一个满足低阶假设的未知的阶数群。下面我们将看到，目前已知的群都不能满足这些限制条件，保证没有任何一方能够推翻该VDF协议。

比如，我们试着使用大家都惯用的群：整数模两个大素数的乘积（RSA群）。这些群具有未知的阶数，因为找到阶数将需要对一个大整数进行因式分解。然而，这些群并不满足低阶假设的要求。确实，元素-1的阶数总是2。但这种情况可以通过将RSA群G除以子群{1，-1}得出商数（quotient）来解决。事实上，如果G的模数是强素数（使得p-1/2也是素数）的乘积，那么在取得上述商之后，除了1之外没有其他低阶的元素了。

这一安全分析意味着RSA群对于Pietrzak的VDF方案是安全的，但还有一个问题：为了生成一个RSA群，参与者必须知道如何对模数N进行因式分解。设计一个无需信任的RSA群选择协议，但没人知道模数N的因式分解，这在该领域中是一个有趣而重要且有待解决的问题。

实现Pietrzak方案的另一个工作途径涉及使用虚二次数语的类群。该群系可以通过让受信任的第三方进行选择来避免上述问题。简单地选择一个大的负素数也能够产生群，但即使对选择这个素数的人来说，要确定这个群内的阶数在计算上也是不可行的。然而，与RSA群不同，在二次数域的类群中找到低阶元素的难度并没有得到深入的研究。这类方案在落地之前还需要进行更多的研究。

04

VDF的现状和未解决的问题