Altcoins Talks - Cryptocurrency Forum
Local => 中文 (Chinese) => 媒体 => Topic started by: billy.ryoko on October 23, 2018, 05:39:01 AM
-
在区块链上实现随机性是很困难的。当开发者试图在链上获取一个随机值时，时常犯的一个错误是使用诸如未来区块的哈希、区块难度或时间戳等量（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)。
换句话说，VDF函数在计算方面（即便是在高度并行的处理器上）花费的时间要比在单个处理器上进行验证所花费的时间要多得多。此外，验证者接受错误的VDF输出的可能性必须非常小（验证者在初始化时由安全参数λ进行选择）。在达到最终结果之前，任何人都无法将f(x)的输出与其它随机数区分开，这一点非常重要。
假设在一场博彩游戏中，用户需要提交一个16位（16 bits）的整数，而获奖号码则是通过向需要20分钟进行计算的VDF提供种子（seed）来确定的。如果某个攻击者在进行了1分钟的VDF计算之后就能知道VDF输出中的4位（4 bits），那该攻击者就能够更改自己所提交的整数，使自己中彩的几率提高了16倍！
http://m.8btc.com/yitaifang-vdf