内容简介：在区块链上实现随机性是很困难的。当开发者试图在链上获取一个随机值时，时常犯的一个错误是使用诸如未来区块的哈希、区块难度或时间戳等量（quantities）来获取随机值。这种方式的问题在于，这些量很容易受到矿工的操控。比如，假设我们运行一个链上博彩游戏，用户需要猜测下一个区块的哈希是偶数还是奇数。某个矿工可以打赌是偶数，而如果他挖矿的下个区块哈希是奇数，则他将丢弃这个区块。通过丢弃哈希是奇数的区块会在一定程度上增加该矿工中彩的几率。在现实世界中，有许多通过区块变量（block variables）生成“随机
在区块链上实现随机性是很困难的。当开发者试图在链上获取一个随机值时，时常犯的一个错误是使用诸如未来区块的哈希、区块难度或时间戳等量（quantities）来获取随机值。这种方式的问题在于，这些量很容易受到矿工的操控。比如，假设我们运行一个链上博彩游戏，用户需要猜测下一个区块的哈希是偶数还是奇数。某个矿工可以打赌是偶数，而如果他挖矿的下个区块哈希是奇数，则他将丢弃这个区块。通过丢弃哈希是奇数的区块会在一定程度上增加该矿工中彩的几率。
在现实世界中，有许多通过区块变量（block variables）生成“随机性”的例子，但这些例子都面临着一个无法避免的问题， 即从计算角度来说，观察者很容易就能够知道自己做出的选择将对链上生成的随机性带来怎样的影响 。另一个相关的问题是在权益证明协议中选出领导者（leaders）和验证者（validators）。在这种情况下，有能力影响或预测随机性的矿工可以对自身何时被选中去挖矿和生成区块进行干预。有很多种技术用于克服这一问题，比如共识算法Ouroboros的可验证密钥共享机制（VSS）。然而，这些技术都存在同样的缺陷： 大多数参与者必须诚实且不会串谋。 在上述两种情况下，攻击者很容易明白不同的输入将如何影响伪随机数生成器（PRNG）生成的结果。 因此，Boneh等人对可验证延迟函数（VDF，即verifiable delay functions）进行了定义，详见：https://eprint.iacr.org/2018/601.pdf。VDF是一些需要一定量的连续计算来进行求值的函数，但是一旦找到了解决方案，任何人都可以很容易地验证该方案的正确性。我们可以将VDF看成对伪随机数生成器的输出进行时间延迟，这种延迟可以阻止恶意行为对伪随机数生成器的输出造成影响，因为在任何人完成对VDF的计算之前，所有的输入都将确定下来。在选出领导者方面，VDF可以在很大程度上对可验证随机函数（verifiable random functions）加以改善。基于VDF只需通过任何一个诚实的参与者便可以选出领导者，而无需要求大多数参与者都是诚实的。这一方案还将提高系统的鲁棒性，因为 即使再多的并行计算（parallelism）也无法对VDF计算进行加速，并且任何非恶意参与者都可以轻易地验证其他人的VDF输出的正确性。
01
VDF 定义
给定延迟时间t，可验证延迟函数f必须同时保证：- 连续性：任何人都可以在t个连续步骤内计算f(x)，但任何拥有大量处理器的攻击者无法通过更少的步骤将f(x)的输出和随机数区分开来；
- 可高效验证性：给定输出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
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进行求值。
现在，假设某人断言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))
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方案的安全性分析假定的是，参与者可以很容易地生成一个满足低阶假设的未知的阶数群。下面我们将看到，目前已知的群都不能满足这些限制条件，保证没有任何一方能够推翻该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的现状和未解决的问题
此外，Wesolowski方案假设存在某些群，它们能够满足一种称为自适应基本假设（adaptive root assumption）的要求，这在数学文献中还没有得到深入的研究。这一领域还存在其他一些未解决的问题，包括构造抗量子VDF，以及ASIC在实践中破坏VDF结构安全性的可能性。至于VDF在行业中的采用方面，一些区块链领域的公司正尝试在共识算法中使用VDF。比如Chia使用了上文中提到的重复平方运算技术。以太坊基金会似乎也在开发一个伪随机数生成器使RANDAO与VDF相结合。虽然这两个项目将对区块链社区非常有益，但这一领域的研究仍处于早期阶段。【文章版权归原作者所有，其内容与观点不代表Unitimes立 场。编译文章仅为传播更有价值的信息】(备注：本文翻译自作者文章，正文内容涉及一些数字上标和下标的情况，为方便理解，请参考原文。英文原文链接见“版权信息”。)
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- Golang学习笔记之延迟函数(defer)
- [QWorker] Delay 函数新增 ARepeat 参数用来实现重复延迟作业
- go 学习笔记之咬文嚼字带你弄清楚 defer 延迟函数
- RabbitMQ延迟消息的延迟极限是多少？
- RabbitMQ延迟消息的延迟极限是多少？
- 延迟静态绑定——static
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
