- A+
01
VDF 定义
给定延迟时间t,可验证延迟函数f必须同时保证:
- 连续性:任何人都可以在t个连续步骤内计算f(x),但任何拥有大量处理器的攻击者无法通过更少的步骤将f(x)的输出和随机数区分开来;
- 可高效验证性:给定输出y,任何观察者都可以在很短时间(即log(t))内验证y = f(x)。
换句话说,VDF函数在计算方面(即便是在高度并行的处理器上)花费的时间要比在单个处理器上进行验证所花费的时间要多得多。此外,验证者接受错误的VDF输出的可能性必须非常小(验证者在初始化时由安全参数λ进行选择)。在达到最终结果之前,任何人都无法将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
VDF 候选结构
目前总共有三种候选结构满足VDF的要求,只是每种都有自身的缺点。第一种结构是由Boneh等人在最初的VDF论文(https://eprint.iacr.org/2018/601.pdf)中概述的,他们使用单射有理映射(injective rational maps)。
- 为了设立VDF函数,需选择一个时间参数T,一个阶数未知的有限阿贝尔群G,以及一个哈希函数H;
- 假设输入是X,通过计算y = g2T 让g = H(x)对VDF进行求值。
重复平方计算是不可并行的,并且在完成最后的平方运算之前是无法揭示出计算结果的。这是因为我们不知道阿贝尔群G的阶数。但这将导致攻击者通过使用群论(group theory)来加速计算过程。现在,假设某人断言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):
- 证明者计算v = g^(2^(T/2)) 并将v发送给验证者;
- 验证者将 {1, … , 2^1}中的随机数r发送给证明者;
- 证明者和验证者对 g₁= g^(r) v 和z₁= v^(r z)进行计算;
- 证明者和验证者递归地证明z₁ = g₁^(2^(T/2))
上述方案可以通过Fiat-Shamir启发式算法来实现非交互。借此,证明者通过对(G,g,z,T,v)进行哈希,在递归的每个等级生成一个挑战r,并在证明中附加v。在这种情况下,证明中就包含了 log₂ T 个元素,并要求接近于(1 + 2/√T) T。
03
Pietrzak方案的安全性分析
- 当计算递归中的第二步时,我们将得到g₁ = g^(r) v,其中 v = g^(2^(T/2)) m,并需要展示g₁^(T/2 )= v^(r) zm;
- 左边的m项是m^(T/2);
- 右边的m项是m^(r+1);
- 由于m的阶数为d,当r+1 = T/2 mod d时这两个数会相等,这种情况发生的概率是1/d。
如果你想进一步了解为什么低阶假设是Pietrzak方案完备性的充要条件,可以查看Boneh最近关于VDF结构的调查报告: http://crypto.stanford.edu/~dabo/papers/VDFsurvey.pdfPietrzak方案的安全性分析假定的是,参与者可以很容易地生成一个满足低阶假设的未知的阶数群。下面我们将看到,目前已知的群都不能满足这些限制条件,保证没有任何一方能够推翻该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的现状和未解决的问题
正如上文所述,Pietrzak 和 Wesolowski 的方案都是依赖于生成未知的阶数群。对于使用RSA群的方案来说,很难在没有受信任第三方的参与下完成的。但类群似乎是一个可行的解决方式。
- 我的微信
- 这是我的微信扫一扫
- 我的电报
- 这是我的电报扫一扫