打字猴:1.70386798e+09
1703867980 质数币
1703867981
1703867982 到2015年为止,唯一在实际中被应用的被证明具有有效工作的系统是质数币(Primecoin)。质数币的主要挑战是为质数找到一个“坎宁安链”(Cunningham chain)。坎宁安链是指k个质数的序列P1,P2,…,Pk,以使得Pk=2Pi-1+1。也就是说,你选一个质数,然后把这个质数乘以2再加1以得到下一个质数,直到你得到一个和数(非质数)。含有2,,5,11,23,47就是一个长度为5的坎宁安链,按照这个规则所获得的第六个数字95并不是质数(95=5×19)。最长的已知的坎宁安链的长度是19(从79,910,197,721,667,870,187,016,101开始),有一个被推测以及被广泛认可但没有被证明过的理论认为,存在一条任意的长度为k的坎宁安链。
1703867983
1703867984 现在,要把这个理论变成一个可计算的解谜算法,我们需要三个关键的参数m、n和k,稍后我们会具体解释。对于给定的一个解谜挑战x(上一个区块的哈希函数值),我们选择x上的前m位数。我们可以认为任何长度为k的链或者大于k的答案是正确的,这条链上的第一个质数是一个n位质数并且和x一样有m位的首段数据(n≥m)。值得注意的是,我们可以调整n和k的值,来让这个解谜变得更加困难。增加k的值(需要的链的长度)使得问题难度指数型增长,而增加n的值(链上的第一个质数的长度)使得问题难度线性增长,这就可以让我们对问题难度进行微调。其中,m的值只需要足够大,使得在知道前一个区块的值之前的预先计算方法变得没有意义。
1703867985
1703867986 其他我们所讨论的属性看起来已经都有了:结果可以很快被校验,问题本身是无关过程的,题库可以无限大(假设对质数分布的知名数学推导是正确的),然后解谜可以通过算法做到自动生成。实际上,这个解谜算法已经被质数币用了两年,并且对许多给定的k值产生了坎宁安链里最大的质数。质数币还做了进一步的扩展,在其工作量证明中涵盖了其他类似的质数链,包括“第二”坎宁安链,其中Pi=2Pi-1。
1703867987
1703867988 这验证了在某些限定的情况下,有效工作量证明是具有实际运用的。当然,寻找大的坎宁安链有用与否,是有争议的。坎宁安链当然也代表了我们已知数学知识宝库的一小部分,其在未来可能会有一些应用场景,但在目前还没有实际的应用出现。
1703867989
1703867990 永久币和存储量证明
1703867991
1703867992 另外一种有效工作量证明叫存储量证明(proof of storage),也被称为可恢复性证明(proof of retrievabitlity)。不同于需要一个单独计算的解谜算法,我们可以设计一个需要存储大量数据被运算的解谜算法,如果这个数据是有用的,那么矿工在挖矿硬件设备上的投资就可以被用于大范围分布式存储和归档系统。
1703867993
1703867994 让我们看一下永久币(Permacoin),这是第一个用于共识机制的存储量证明方案。首先我们讨论一个大文件F,我们假设所有人都认可F的价值并且这个文件不会被改变。例如,当一个加密数字货币上线时,由一个可信任的分发者选择F,这有点类似于任何一个加密数字货币启动时都需要一个创世区块,理想状况下这个文件会具备公共价值。例如,大型强子碰撞(Large Hadron Collider,简称LHC)的实验数据,这个数据已经达到了几百拍字节(petabytes,用PB表示)的大小,对这些数据的备份是很有价值的。
1703867995
1703867996 当然,因为F存储量非常巨大,大多数参与者都无法对整个文件进行存储,但我们已经知道,在不需要了解整个文件的情况下,如何使用密码学里的哈希函数来确保每个人都对F认可。最简单的方法是,每个人都认可H(F), 但更好的方法是用一个大型梅克尔树来代表F,所有的参与者都认可梅克尔树的根值。现在,每个人都认可F的价值,证明F的任意一部分是正确的就变得很有效率。
1703867997
1703867998
1703867999 在永久币系统中,每一个矿工M存储着任意F文件的子集FMF。为了实现这一点,当矿工产生一个公钥KM来接受资金时候,他们就对该公钥进行哈希运算以生成一个区块FM的虚拟随机数集,他们必须存储这个数集以实现挖矿的目的。这个子集就会变成某个固定数量的区块k1的一部分,我们必须在这里做一个假设,当矿工开始挖矿的时候,他们有办法获得这些区块——可能是从一个标准文件源地址下载下来(见图8.2)。
1703868000
1703868001
1703868002
1703868003
1703868004 图8.2 在永久币系统中选择一个文件的随机区块
1703868005
1703868006 注:在这个案例中,k1=6,k2=2。在实际应用中,这些参数会大很多。
1703868007
1703868008
1703868009 一旦矿工在本地存储了FM,这个解谜算法就非常类似于传统的SHA-256挖矿了。给定前一个区块的哈希值x时,旷工选择一个临时随机数n,将其进行哈希运算并产生一个虚拟随机数子集FM,nFM,这个子集包含了k2
1703868010
1703868011 校验一个解谜算法的结果需要以下几个步骤:
1703868012
1703868013 ● 校验FM,n是由矿工的公钥KM和临时随机数n共同产生的。
1703868014
1703868015 ● 通过检验其在梅克尔树节点到全局统一的树根路径,来检验FM,n中的每一个区块是正确的。
1703868016
1703868017 ● 校验H(FM,n‖n)的值比目标难度要小。
1703868018
1703868019 我们很容易看出,为什么解谜过程需要矿工在本地存储所有的FM,n。对于每一个临时随机数,矿工都需要计算FM,n中随机子集的哈希值,如果通过远程访问一个存储空间来获取文件,就会非常慢,几乎不可能实行。
1703868020
1703868021 不同于Scrypt算法的案例,如果k2足够大,并没有一种可行的类似于时间内存的权衡方案。如果矿工仅仅在本地存储了一半的FM,并且k2=20,那么在他们找到一个不需要从网络中取回任何文件区块的临时随机数之前,他们必须要尝试100万次,降低一定量的存储负担会以计算量指数型增长为代价。当然,由于k2梅克尔树路径要在所有的路径中被传输和校验,如果k2设得太大,也会使运算变得非常低效。
1703868022
1703868023 k1的设定也可以有所权衡。更小的k1意味着矿工需要更少的本地存储空间,因此这种挖矿就更加民主化(更多的人可以参与)。然而,这也意味着,大量的矿工即使有能力提供更大的存储空间,他们也没有动力去存储多于k1个F区块。
1703868024
1703868025 同样,这是一个对完整的永久币做了细微简化的方案,但是对我们理解整个设计的关键部分来说是足够的了。最大的应用挑战,当然是找到一个合适的大文件,这个文件要有一定的重要意义,同时也是公共的,需要保存多个备份。如果F文件本身随着时间的推移会发生变化,或者随着时间的变化而调整难度,这样会使方案变得更加复杂。
1703868026
1703868027 长期的挑战和经济意义
1703868028
1703868029 总结一下本节内容,有效工作量证明是一个非常自然的目标。考虑到一个好的共识机制所需要的其他解谜算法,实行起来也有相当大的挑战。即使如此,至少本文所举的两个案例——质数币和永久币——在技术上是可行的,虽然它们也都有一些技术方面的缺陷(主要都是需要更长的时间去验证解谜结果)。此外,对比在比特币挖矿中动辄数百万美元的投入以及大量电力的消耗,这两种加密数字货币的应用都对社会公益有一些贡献。
[ 上一页 ]  [ :1.70386798e+09 ]  [ 下一页 ]