Chia VDF 算法原理剖析
source link: https://www.jinse.com/blockchain/1094633.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Chia VDF 算法原理剖析
随着爆火产品Chia的出现，挖矿行业又有了更新颖亲民的玩法，即低门槛的硬盘挖矿方式，这种挖矿方式让越来越多的普通人能够参与到挖矿中来，一起感受区块链行业的热潮。
根据Chia的白皮书介绍，Chia采用的共识机制是空间证明（POS, Proof Of Space）和时间证明(POT, Proof Of Time)。POS主要用来证明用户的确有未使用空间可以用来存储，而POT则用来保证整个系统的安全性，其主要算法是VDF 可验证延迟函数（Verifiable Delay Function），VDF得出的运算结果必须经历一定的时间，并且可以由网络中的任何节点快速认证，增加POS获得出块权的概率。
Verifiable：即经过一定次数的计算后，prover可以快速生成一个小的proof来证明计算有效性，verifier不用重复执行计算就可以得知计算的正确性；
Delay：即prover只有执行正确次数的计算后，才能得到正确的结果，不会出现没达到指定次数前，就得到正确结果的情况；
Function：即结果是确定性的，输入x，就会得到y。
Figure 1 POT
VDF的计算
基于Chia的设计模式，如果某个节点的VDF计算速度高于其他节点，有可能会发起某种安全攻击。因此，为了避免这一威胁，Chia希望节点中运行的VDF算法是最高效的，所以基本没有什么优化空间。为此，Chia还举办了两次VDF效率竞赛，以高额的奖励来吸引业内精英参与到本次活动中来，广泛汲取大家的智慧，来获取效率最高的VDF。
如上图所示，Chia里用到的VDF算法其实很简单，就是对一个数x进行连续的T次平方计算，x是一个未知阶的群组（a group of unknown order）的元素。为什么是未知阶的群组，其中缘由也很简单：
如果群组的阶为d，那么根据群组的性质：x2^T = x(2^T) % d
就会存在未达到指定次数T，就得到正确结果，这与Chia的设计不一致；因此，群组的阶是无法被知道的；生成未知阶的群组的方式有两种：
基于RSA的群；
虚二次域类群；
当选择基于RSA的方式时，群的阶N=pq，其中p、q都是很大的素数且不可公开，因此，计算这种群的阶的难度就和分解大数N一样困难。所以被认为是安全的，但是，这种方式需要可信设置，即p、q由可信第三方生成，或许也可以用MPC的方式，但是总之，它需要可信设置；
而基于虚二次域的类群可以消除可信设置，因为一个满足|d|=3 mod 4关系的负大素数生成的类群，计算其阶是困难的（为什么困难，将在另外一篇文章里详细阐述，涉及数学概念较多，将尽量写的简明易懂些），由于这个大素数可以公开，因此这种方式可以很容易的生成无须可信设置的未知阶的群。
了解了背后的数学概念，下面让我们再看一下，基于虚二次域类群的元素的平方应该如何计算，如下图所示（算法参考NUDUPL论文）：
Figure 2 if a < L
Figure 3 if a > L
NUDUPL算法为目前为止，计算虚二次域平方的最有效的方法，这也是在两次VDF算法竞赛中，参赛者们选用最多的方法。图2、图3展示了算法的两个主要分支，其中m = (a,b,c)、M = (A,B,C)都是群中元素的表示形式。
VDF的证明
由图1可知，prover除了需要做T次计算外，还需要生成一个证明，来证明计算的正确性，关于VDF的正确性论证，这篇论文中给出了两个经典的方法，Chia采用的是Wesolowski的论证方法，此方法的过程如下图所示：
算法本身简单，且好理解。和论文中的Pietrzak算法相比，该算法生成证明更小，验证proof更快。
结 语
经过一段时间的研究和测试，Chia目前采用的VDF算法确实相当高效，从算法上，已经寻找不出可以大幅优化的点。“软的不行就来硬的”，这也是为什么我们仍然坚持把Chia的VDF算法研究的很深入的一个原因，目前已经着手硬件优化设计。从理论上讲，具有更高效率的VDF计算，可以获得更高的挖矿效率，这也是我们的目标。
Recommend
-
33
plotman: a Chia plotting manager This is a tool for managing Chia plotting operations. The tool runs on the plotting machine and provides the following funct...
-
7
绿色货币CHIA为何物？Chia Network深度分析 鸵鸟区块链要闻 2021-04-13 20:48 1930 摘要: Chia于2017年8月成立，...
-
7
Chia 的挖矿之路 | 灰度云矿市场观察在这个新算力时代，挖矿是区块链加密经济的底层支持与基建，永不落伍。…· 2 分钟前 ·阅读约 5 分钟伴随 Coinbase 将于 4 月 15 日在纳斯达克证券交易所上市的大事件到来，比特...
-
2
“Chia”！一加OnePlus 9R国内亮相 “Chia”！一加OnePlus 9R国内亮相 - 数码窝海外已经早早亮相的一加OnePlus 9R于今日下午正式登陆国内市场，并已经开启预售。虽然在早几日预热中，一加多次提到了迪迦奥特曼，但实际上并未有联名...
-
5
解读币圈新贵 Chia必读：预测行情都是假的，鬼知道下一秒有没任性的庄家来个拉升砸盘啥的。我倡导的是科学的投资理念，所有的分析都建立在科学的基础上，杜绝人为幻想。投资首先要做风险控制，别期望每次操作你都能赚钱。就像拳击比赛，赢得胜利...
-
5
一文了解热门项目Chia 徐坤的思享汇 2021-04-19 13:01 2051 摘要: 3月18日， Chia正式发布Chia 1.0主网，代币为X...
-
8
Files Permalink Latest commit message Commit time
-
8
Chia区块链JS开发包【chia-client】 发表于 2021-04-19...
-
1
继 Filecoin 之后，Chia 矿机热度爆发，「豪华创始团队」和「一线投资阵容」成为了 Chia 自带的光环，分布式存储赛道中出现了又一个明星项目 。 但另一方面，简陋矿机高价销售、传销式宣传风格、传投机资金入场，似乎让仍处于早期阶段的 Chia 项目变了味...
-
5
[研究] 可验证延迟函数（VDF）（一）一文搞懂 VDF 2019-05-26 研究 约 7811 字 预计阅读 16 分钟 次阅读 自从以太坊将可验证...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK