• 关于 Eval

1、证明 π 不是必须的，如果仅仅通过 y 就能验证的话； 2、在 y 的计算中，不允许有随机数的引入（为了保证唯一性），但是在 π 的生成过程中可以引入； 3、为了保证串行性，Eval 在拥有不超过关于 t 的多项式对数 ****(Poly-log)个并行处理器时，运行时间必须为 t； 4、为什么 Eval 要允许一定程度的并行计算达到时间 t 呢？因为可能并没有构造能够完美地让并行和串行计算时间完全相同，所以我们需要容忍一定量的不太显著的并行加速。

• 关于 Verify

1、Verify 中不引入随机数，也就是说，它是确定性算法； 2、Verify 的运行时间要比 t 小得多，具体来讲，他们在运行时间上拥有指数级别的差距（Exponential gap）。

基于上述定义，VDF 还有一些拥有特殊性质的变种：

1、可解码 VDF （Decodable VDF）：如果对于一个 VDF 方案，存在一个算法对于任意 x∈X 能够从 y∈Y 反向计算出 x，那么这个 VDF 就是可解码 VDF。在这样的情况下，证明 π 是不需要的。当然，一个平凡的构造是，将 π 放进 y 里面； 2、增量 VDF （Incremental VDF）：如果在 Setup 算法中，参数 t 没有被唯一确定，而是允许在 Eval 的输出之一 π 中指定，这样的 VDF 被称作增量 VDF。一种效果类似的构造是，在 Setup 中设定 t 为一个单位的时间，如果想要在计算阶段达到不同的延迟时间，例如 T=nt，只需要串行 n 次 Eval 即可。但是这样的构造会导致 n 倍的证明长度，增量 VDF 不会产生额外的证明； 3、陷门 VDF （Trapdoor VDF）：如果某个 VDF 方案存在一个算法，使得知道某一秘密值 sk 的人能够通过这个算法迅速由 Eval 的输入得到 Eval 的输出，那么这个 VDF 是陷门 VDF。更直观的理解是，陷门 VDF 有一个后门可以让人绕过延迟限制迅速算出结果。 4、弱 VDF （Weak VDF）：如果我们放宽限制，允许「即使在 Eval 中使用多项式（Polynomial）个并行处理器才能在 t 时间算出结果」这样的情况出现，这样的 VDF 被称作弱 VDF。弱 VDF 在实际应用中会更加消耗诚实参与者的算力（因为相比 VDF 而言需要更多的并行处理器才能达到 t 时间）。但如果将 VDF 用于生成公共可验证的随机数，可以将计算任务交给一个诚实参与者，其他参与者等着验证。这时，这样的唯一计算者是可能拥有足够多的处理器的。

上述文章提到了使用连续的哈希操作是一种防止并行的计算加速的手段，但是这样的手段非常低效，不符合 VDF 的定义。我们希望能够找到一种验证更加迅速的防并行的构造方式。考虑这样的一个例子：

首先选择一个数 λ=161 ，然后然后对于任意的输入 x，我们执行下面的的操作 t 次：

1、计算 k=X2 2、取 k 除以 λ 的余数得到 l 3、令 k 取 l，返回第一步，如果是最后一次操作，输出结果 y

假设我们的输入 x=11，t=8 那么结果为 95，事实上，如果我们让 t 取不同的值，把结果都记录下来，可以得到下述表格：

更一般地讲，如果 a≡b mod m 代表 a 和 b 分别除以 m 的余数相同的话，那么上述操作实际上就是计算：

如果我们知道 λ 的因式分解，例如 161=7×23，那么我们可以通过两次指数运算来快速计算出 y 的值。首先计算函数?(161)=(7?1)×(23?1)=132，然后计算 2 t 除以 ?(161) 的余数：

然后计算 x124 除以 λ的余数：

上述过程比起连续平方 8 次看似没有减轻多少工作量，但实际上当 t 和 λ 非常大（t≈230）时，远比连续平方快得多。一般地，函数

如果

这个函数被称之为欧拉函数（Euler’s Totient Function）。上述例子可以一般化为：

因此，如果没有任何人知道 λλ 的因式分解，也就无法快速计算出 ?(λ)，从而只能重复 t 次平方操作使用

计算出 y。

事实上，这个构造可以使用群论得到更加本质的友们。我们发现，由于模运算 y 的值是小于 λ 的，而所有小于 λ 且与 λ 互素的数一起组成了一个群（Group） [8]，这个群被称作整数模 λ 乘法群 [9]，记作 (Z/λZ)。这个群的阶（Order），也就是元素个数就等于欧拉函数 ?(λ) 的值。因此，关键问题落在了讲解生成这样的知道阶的群。

目前主要有两种方法：

1、使用 RSA 群 2、使用虚二次域的类群（The class group of an imaginary quagratic number field）

RSA 群的生成与 RSA 加密算法类似，选取大素数 p 和 q，其中 p=2 m+1，q=2n+1 且 m，n 均为素数。令 N=pq，则 (Z/NZ) 即为所需群。然而一个很显然的问题是，这其中涉及到了 trusted setup，我们必须相信生成 N 的参与者不会泄露 p 和 q。我们也可以使得群生成算法使用公共随机数来直接选取足够大的 N 使得因式分解 N 非常困难，但是这样的 N 需要非常大以至于这样的方法非常不现实。第二种方法解决了第一种方法的问题，但是由于第二种方法友们起来涉及概念较多，本篇文章不会涉及。同时，对于结果 yy 的快速验证需要用到证明系统，有兴趣的读者可以参考 Boneh 的一篇综述 [10]。

学术界第一次正式提出 VDF 的概念是在 Boneh 的论文中，他在论文中给出了 VDF 的应用场景以及形式化的模型，安全分析和一般构造方法。之后出现了分别出现了两篇 VDF 的构造论文，分别是 Wesolowski 的 Efficient VDF[11] 以及 Pietrzak 的 Simple VDF[12]。两者都利用在不知道阶的群中连续做平方运算的方法来构造 VDF，不同的是，他们生成证明的构造有所区别。简单来讲，Wesolowski 的证明更短，验证更快；但是 Pietrzak 的构造中，生成证明的速度更快，同时证明系统依赖的安全假设更弱。2019 年 Feo 等人 [13] 使用超奇异同源 (Supersingular Isogenies) 以及双线性对（Bilinear Pairings）构造 VDF。相比于 Wesolowski 和 Pietrzak 的工作，他们的构造本身就是非交互的，不需要经过转换，同时不需要证明 π 即可完成验证，但是他们的构造中 Setup 耗费的时间更长，更为主要的是，目前还只能进行 trusted setup。

在应用领域，Chia Network [14] 计划使用 VDF 来支持他们的 Proof-of-Space；以太坊研究团队也打算在以太坊 2.0 中引入 VDF，以期在以太坊 2.0 信标链中使用 RANDAO + VDF 随机选取出块人。最初 [15] 以太坊计划使用 RANDAO + VDF 的方案。但由于以太坊 2.0 的计划瞬息万变，截至文章最后修改前，以太坊信标链计划将区块间隔限制到 6 秒，64 个区块为一个 epoch，因此一个 epoch 为 6.4 分钟，每一个 epoch 需要进行一次出块人切换，因此 VDF 的时间参数最少应设置为 6.4 分钟，但是目前以太坊计划将其设置为 102.4 分钟，目的是防止潜在的攻击者利用特殊硬件加速 VDF。

来源链接：mp.weixin.qq.com

 2/2   首页 上一页 1 2