VDF(可验证延迟函数)概述、用途和方案
Archer
发表于 2023-1-3 14:22:53
52
0
0
此项目的目的是创建一个相对完整的针对可验证延迟函数的知识库,并以此来帮助成立一个能够合作开发 VDF 开源硬件的自由社区。
-- Maxwell Foley
我们的立场是:VDF 研究能够给区块链社区提供一个绝佳的机会来促进硬件设计中的公开性,公平性以及更好的教育普及。因为这是第一次由一家大型区块链平台带头努力,为普通大众而不是为少部分私人公司获利而开发 ASIC 硬件。
我们先讨论一些基础概念,介绍 VDF 的工作原理以及它的目的,然后,如果可以的话,在后续的章节中进入越来越复杂的技术领域并最终接近实现方案。
我们希望这篇文章写得通俗易懂,任何有一定区块链基础知识的人都能够理解,并且任何有兴趣的人都可以获得其中的知识。, T! m/ G1 A- I; w
如果你在文档中发现任何错误或者想要为后续内容作贡献,请用 Telegram 联系我们:Qi Hardware’s Telegram Group# H) |9 p C" P2 x
什么是VDF?VDF 代表可验证延迟函数(Verifible Delay Function)。3 R1 {8 G& c, |$ k
可验证延迟函数是指在可用的硬件上需要花费很长时间(例如一个小时,这是我们所指的延迟)来计算的任意函数,但是这些函数的输出可以立刻被验证。0 x! e+ y( U) U
如果我们拿人来举例子的话,我们可以想象有一个叫 Alex 的人坐在办公桌上,我们让他用 55 作为输入去计算一个 VDF 函数并告诉我们函数的输出。他努力地计算了一个小时,然后擦擦他额头上的汗水,并告诉了我们输出是809。另一个人,Bob,站在 Alex 的旁边并瞥见了这个输出。他在自己的笔记本上划了几下然后说:“这个输出是对的!” 他不用花费一个小时来做和 Alex 相同的计算就能知道 Alex 的计算是对的。 一旦输出被放在了 Bob 的面前,他很容易就能验证这是对的。
我们稍后会解释其中的原理,但是现在把它当成一个已知的函数特性就好。
VDF 有什么用途?VDF 能够用于很多不同的领域,但是我们感兴趣的是用它在区块链上生成随机数。0 q- T; D# Q5 v+ s/ v% Y# X
我们为什么要生成随机数?主要的原因是我们(“我们” 指以太坊社区)想要用权益证明替换现在以太坊运行的工作量证明机制。在工作量证明(“挖矿”)中,出块者要相互竞争,他们投入大量的能源用机器不断运算,用运算解出谜题之后才能发布出块。而在权益证明中,一个用户只要拥有 32 个以太币就能发布区块,他们不需要浪费电能;但是因为没有竞争,我们需要找到一个方法来从整体上选择(在某一时间)谁能够发布区块,为了保证公平我们至少得保证这个过程具备一定的随机性。
为什么要用这种特殊的方法在区块链上生成随机数?不能直接用普通软件吗?首先,计算机并不能从无到有生成真正的随机数,因为一个计算机程序只是一一系列精密指令的集合,它并不能进行创造或者随机应变。我们需要给计算机提供用于随机函数的 “种子”,或者来自现实世界的随机性来源,来支持它进行数学运算,并最终在一定区间内产生我们相要的随机数。一个典型的随机性来源是特定时刻系统时钟的毫秒数,每次运行程序是它都有所不同并且难以预测。像 random.org 这样最复杂的随机数生成器会利用大气中空气分子的波动来构造随机数,因为它更加难以预测。4 d( H" N7 [& v( T
在区块链上,每一台参与的计算机都会按照相同的顺序来执行所有操作(虽然不一定在相同时间),并且应该拥有相同的输出。所以我们需要一种所有参与者能同意的随机性来源,唯一的可能来源就是发布在区块链上的数字本身。- ^) P* m- a* C6 h
举例来说,与其让每台计算机各自使用其系统时钟上的毫秒数来作为随机源,不如使用前一个区块时间戳上的毫秒数,因为至少所有参与者能够就此达成一致。但是这个想法有很大的问题!即,出快者能够完全控制提交区块时的毫秒数!假设一个参与者发现:如果 RNG (随机数生成器)将 444 作为输入,他们就能获得提交下一个区块的权力;那么当他们组装当前块时,他们只需记录一个以 444 结尾的毫秒数,便可获得下一个区块的出块权;如是反复,他们将完全垄断区块的生成。5 |9 r% Q5 k* Z' {" \6 P! X
很显然我们可以用别的,不那么容易被利用的东西来用作 RNG 的种子,但核心原理是一样的:出块者总是能够影响区块内容,而只要我们使用区块中的数据作为随机数源,他们就会肆意利用这一优势来提高他们获得子块出块权的概率。' i1 h( f0 u5 }9 x) _& q
现在,假设我们不用上一个区块的时间戳作为随机源,我们用一个小时之前发布的区块的时间戳,作为输入运行一个 VDF。这样一来,出块者控制随机数源输入的难度就高了很多,因为出块时他们不知道用哪个时间戳能够提升他们在一小时后发布另一个区块的几率,因为这将花费一整个小时来计算!实际上,用时间戳仍然不是一个好办法,但是我们已经离可行的方案十分接近了。基本上,这就像所有出块者都拿着彩票并且等待幸运号码被公布。VDF 确保了没有人能够 “作弊并且获得优先权”。# {. w5 g1 F' b, V7 L/ H/ c/ f
VDF 和 POW 共识机制有什么区别?在工作量证明的挖矿系统中,矿工们根据给定的输入(即他们自主选择的交易所组成的区块)付出大量资源来寻找一个相应的值 (即 “区块 nonce”),找到了 nonce 就意味着矿工挖到了区块。给定这个输入,任何人都可以立即验证出这个 nonce 是符合要求的。. {0 o/ x( d5 {2 Y. J' u/ G
POW 和 VDF 主要的不同在于 POW “挖矿” 的过程是可以并行的,意味着有越多的计算机设备参与 “挖矿” ,就能越快找到最优的 nonce 值。VDF 可验证延迟函数是一个只能按顺序运算的函数,增加更多的设备并不能提升计算效率。在 VDF 算法下,无论一个参与者有多少计算设备,都一定是在大致相同的时间内算出结果(校对注:此处是指如果这些设备的效率都差不多的话),否则,VDF 所强调的 “延迟” 就不容易实现,很容易被拥有许多计算设备的人所 “攻破”。, q7 o% t$ |8 q! \( z0 F
可验证延迟函数的计算过程并不是一场比赛,也没有什么竞争,它的目标是让所有参与者都能近乎同时算出同样的解。! C8 H; R# q/ e# ]! M, D
同样,和工作量证明机制不同,我们不期望出块者自己运行 VDF(详细原因稍后解释), 也不是一种为了提交有效区块而必须支付的 “税”(校对注:意指 PoW 中出块就像给协议交税),重要的是某些人在运行 VDF 算法(任何人都可以参与),而 VDF 可以使得随机数的产生过程更加公平。
对于区块链领域来说,除了随机数生成更公平以外, VDF 还有哪些应用?在最初的介绍 VDF 的文章中,除了以上我们的描述,还提出了两个应用案例。 [/ X, G9 _$ F& z1 N- I. Z
数据复制证明
其中之一是重复证明机制,假设有一些数据你希望永久地、安全地保存下来,即使发生了不可抗的灾难性事件,也不受影响。你因此需要花钱请人备份数据,让你的数据在 100 个设备上备份。
如果你想确认你请的人没有骗你并且让你的数据在 100 台设备上备份,你可以访问他们其中一台设备,比如 100 个设备中的第 78 号,让设备显示你的数据来证明他们确实已经备份。设备按照你的要求显示数据,你在当下也很开心……但是最终你意识到你没有办法确认 78 号设备确实已经备份,因为它可以向 1 号设备询问并获得相关数据。尤其是在互联网如此发达的今天,数据的获取已变得相当便捷,也许他们只存储在一台设备上,以此节省费用和资源,但虚假宣传说自己做了 100 个备份。
你可以让每一个存储数据的设备同时运行一个不同的 VDF,而不仅仅是存储数据。虽然从原始数据中产生 VDF 结果会耗去几个小时,但你可以从 VDF 结果中近乎即时获得原始数据。如果他们可以给你经过 VDF 处理后的数据结果,那么你就能确信是独立的设备存储着数据,因为这样不可能从其他设备获取和计算数据。8 U' b) [: O) r+ }
防止虚假历史账本攻击
VDF 的另一个应用是可以加强 POS 共识机制的安全性,POS 共识机制的一个安全问题是恶意攻击者可能伪造账本历史并提供给新加入网络的用户。因为新加入网络的用户总是需要从其他节点获取账本数据,这样的攻击下他们无法分辨那些节点是诚实的,哪些节点是恶意的。攻击者很可能在这个虚假账本中给自己安排比真实账本中更多的钱。
在工作量证明系统中,制造假的账本数据是不可能的,因为出块者需要耗费大量能源来计算 nonce 值,如果 nonce 值无效会立刻被其他 “矿工” 检查到。因此,为了创造一个可信的虚假账本,攻击者需要花费与挖掘整个比特币历史到目前为止所花费的电量大致相同的电量,这显然是不可能的,但是在 POS 共识机制中并没有这样的限制。7 Y/ { {. Y' n3 R+ @
但是使用 VDF,我们可以构造出一个系统,在这个系统中我们可以证明数据确实是过去产生的。例如,如果在某一点上,我们将区块链账本中的数据输入一个要运行一年时间的 VDF,那么一年后,我们将能够证明该账本数据的历史至少有一年,而任何伪造者都无法做到这一点。* }+ J- t, B9 t9 Q2 d+ U; K
产生随机数除了使用 VDF 还有其他方法么?VDF 是作为 RANDAO 的系统升级方法被提出来的(一个叫 Justin Drake 的研究人员提出),而 RANDAO 也会被用来在 Ethereum 2.0 时代产生随机数(随机数生成),RANDAO 是一种虚拟委员会,在该委员会中,创建区块的每个参与者都被要求向网络提供一个随机数。然后 RANDAO 将以某种方式组合它所收到的所有输入,作为我们随机性函数的种子。! F+ _ W- A! P( e, X4 ?
该随机数方案防止作弊的方法是要求发送者先发送随机数的密文,然后再发送随机数的明文。这就相当于一个游戏,所有玩家的牌面都朝下,只有在所有玩家都发完牌之后,玩家才能一张一张地把翻开纸牌。而以太坊 2.0 的方案是这样的:首先每个节点都必须提交一个公钥给链上的其他节点,当所有节点都完成提交之后,所有节点都将使用他们刚提交的公钥给同一个数字签名。最终生成的加密签名将用于随机数池。! A% W, C" H3 P$ ^ P
VDF 的目的不是取代 RANDAO, 而是改善 RANDAO,将 RANDAO 的随机数输出作为 VDF 的输入。1 d, d8 o5 n8 q# p3 {/ V
我们之所以同时使用 RANDAO 和 VDF 而不是仅仅使用链上的某个值来运行 VDF,理由与我们之前提出的时间戳概念类似,主要是为了双重安全性。如果 VDF 无法使用(比如量子计算机的可以比一般的计算机更快地运行 VDF ),我们仍然有 RANDAO 可以使用,也许这并不是最好的办法 (下一章将会详细介绍),但是至少系统不至于完全崩溃。
为什么 VDF 是现有解决方案的改进?有一种可以在 RANDAO 随机数系统中作弊的方法,但是只有在其他人都已经亮出底牌(就是提交给随机函数的数字),而你是最后一个亮出底牌的人;或者你与其他还没有亮出底牌的人串通,才可以实现作弊。这种方式很简单——想象一下,你看着所有已经公开的牌,意识到它们组合起来的结果是你 “赢得” 这场游戏(即获得下一个区块的打包权力);那么你就不用公开你原本想要提交的数字了,这样你的份就不会被算进去,而你会如愿获得出块权。这看起来没什么大不了的,但用户能够对随机数生成的任何一丝影响都是不好的:为数十亿美元提供安全保护的随机函数不能以这种方式被 “泄漏”!8 u6 U# {$ m6 ^* y5 l4 K
一个经常被考虑的解决方案是需要某种类型的保证金来参与生成随机数,如果参与者作弊,那么我们可以剥夺他的保证金,并且让这种处罚远多于他们作弊可以获得的收益。在以太坊 2.0 中,随机数是由出块者产生的,而每个出块者必须抵押至少 32 个以太坊才能参与出块,为了使这个系统正常工作,我们必须惩罚那些企图欺骗网络或离线太久的人,惩罚的方式就是拿走他们的 32 个以太的一部分或全部。所以有人可能会认为我们可以像惩罚其他形式的不良行为一样惩罚随机数生成过程中的作弊行为。- g: ~: Z0 E8 h7 a
问题是,我们的惩罚可能不够严厉,不足以使威吓作恶者。这是因为 RANDAO 不仅用于选择出块者,而且是用于以太坊上需要随机数种子才能良好运行的应用程序;所以需要抵押多少 ETH 没有确切的结论。假设有人运行一个以太坊彩票应用程序,在这个游戏中,中奖者将获得价值数百万美元的以太坊。即使我们拿走了出块者抵押的所有的 32 个以太坊,一个出块者仍然可以通过操纵彩票结果赚得盆满钵满! S, ~2 {) H" d
实际上,我们只能惩罚作弊者很小的一笔钱,因为如果有人不参加最后一轮的随机数生成,那可能是作弊,也可能只是网络条件差。如果迫使人们冒着他们的互联网服务出现轻微问题便损失大量金钱的风险来成为一个出块者,出块者就变成一个吃力不讨好的事情了。这对于整个以太坊网络的安全也不是好事。0 v8 T5 \( p+ h( I; ~8 [. p* ]
VDF 的延迟在实际中有多久?当前的方案将延迟时间设计为 102.4 分钟,或者说比1.5 小时略长一些。
这是因为出块的速度是 6s ,并且需要 64 个块作为一个时段来执行 RANDAO 合约。这就是说总共需要 6.4 分钟,同时意味着只要解决 VDF 的时间超过 6.4 分钟,就无法在合约结束前 “欺骗” 或者使 RANDAO 合约出错。(事实上,如果需要攻击成功,你仍然需要更快速地算出来)6 \2 Z/ C1 v! Z) M/ [. d. L: o
那么我们为什么要将 VDF 的延迟设置为 102.4 分钟,而不是 6.4 分钟呢?这是因为我们预计那些攻击者将会尝试创造专用的硬件(这被称之为 ASIC ,类似于专门发明来挖比特币的专用计算设备),它将会比一般人用的计算机更快地解决 VDF 的问题,然后就可以作弊了。我们通过将延迟设置为比周期(epoch)时间长很多来保护系统,这样即使硬件制造商创造出的计算机能比普通计算机更快地解决 VDF ,他们依然无法作弊。
因此 102.4 分钟这个数字可以说是我们预计普通计算机算出 VDF 的时长,某些人可能会尝试提高运算速度,但就算他们成功也不至于快到可以成功攻击 RANDAO 合约。
如果计算 VDF 需要 1.5 小时,这是否意味着我们可以每隔 1.5 小时才能获得一个新的随机数?不是的。这是因为我们可以平行地运行几个不同开始点和结束点的 VDF 。我们在每个周期(6.4分钟)中启动一个(VDF),意味着在第一个 VDF 开始运行后的 102.4 分钟中,我们每隔 6.4 分钟就能获得一个随机数。此后,每个随机数在区块链中都能被任何人用于任何功能。, N( k! B5 j9 w# j& q
在以太坊 2.0 中,谁能够运行 VDF ?在 Justin Drake 讲述的设计方案中,区块的生产者并不需要或者预期自己会运行 VDF 。相反,在区块生产者执行 RANDAO 合约之后,另一个被称之为 “评估者” 的团队会使用 RANDAO 的输出运行 VDF 。
显然,我们无法阻止同一个人使用不同的计算机同时担当区块生产者和 VDF 的评估者,要去阻止也是不合适的。" @: ?+ i, I2 y1 i
一旦评估者完成计算,他们会向区块生产者广播 VDF 的输出。9 U/ v+ N4 [% L5 E
对于系统来说,只需要单个准确的评估程序。 VDF 只有一个可能的输出,所以只需要一个人去执行它,然后就可以向其他人广播这个输出了。在这一点上,基于函数的可验证性,其他所有人都可以看到评估者是诚实的。5 w5 f6 U! a- P' B
如何能够激励用户运行或者评估 VDF ?为什么要花费电能?首先,我们估计为以太坊运行 VDF 只需要 160 瓦的电能,这仅仅比你在卧室中开着吊扇耗费的要多一些。每天花费大约 40 美分。所以这并不是一个很大的消耗。$ G/ v9 ]( ?$ E& }. e. a: G
但运行 VDF 也是有奖励的。区块生产者负责验证评估者广播的 VDF 结果。为了防止区块生产者偷懒,只是等着其他人听取评估者的意见而不是自己动手, Drake 建议我们可能要想想如何激励第一个听取并正确广播 VDF 输出的验证者。( H5 {: r, t7 O& n1 |9 @+ D2 V
这可以作为加快运行 VDF 的激励,因为区块生产者和 VDF 评估者可以是同一个人。他们的 VDF 运行得越快,他们就越有可能赶在其他评估者之前广播他们自己 VDF 的输出,这也就意味着他们能够获得奖励。
这是一件好事,因为 VDF 评估者最好能够尽快运行该函数且不会偷懒。这将会使以太坊网络一切顺利,一切安全。" t+ Q$ s' C% ]% }, f7 \* K; \
为什么以太坊基金会要花费 1500 万美元去研究 VDF ?首先,说以太坊花费 1500 万美元去研究 VDF 的报道并不准确,他们只是试图将这些资金集合起来,并和其他计划使用 VDF 的区块链协议共担成本。" Z1 D% m4 q: p" @- t$ G
无论如何,这笔资金会被用在研发生产用于 VDF 的 ASIC 硬件上,这些硬件对于任何一个以太坊的用户来说都是开放的,是可用的。请记住,为了使我们的算法安全,我们需要确保没有人比普通用户运行 VDF 的速度快很多倍。如果我们假设普通用户在标准的 CPU 上运行这些算法,那么制造一个可以将运行速度提高十倍的芯片是非常容易的。但是,如果以太坊基金会自主研发生产芯片并发放给其他人使用,那么任何作恶者都需要有一个超过以太坊基金会十倍的项目(来达到他们的目的)。即使他们可以筹集更多的资金,即使他们技术能力很强,这也是非常困难的一件事。
成为第一个吐槽的人