区块链应用落地案例探讨——质数链Primecoin

小雨社区

原创

10-09

分享嘉宾

董佶圣,北大软微系博士,Sunny King团队与Primecoin foundation成员。 Sunny King做为区块链技术的奠基人之一,为行业提供了最有突破性和原创性的共识算法, 其2013年发布第二条链质数链(Primecoin),使PoW在比特币的基础上变得真正有意义 质数链是一个真正区块链落地应用的一个案例,它的运行是在不断寻找孪生素数。

首先介绍一下我们团队的背景,Sunny King可以说是区块链技术的奠基人之一,为行业提供了非常具有突破性和原创性的共识算法。其中,权益证明机制(Proof of Stake,PoS)最早由Sunny King提出,它和中本聪提出的PoW共识机制被全球加密货币社区共称为加密货币大小王牌,现在也越来越多地受到主流数字货币的青睐。


Sunny King开创的点点币最先使用了PoS共识机制,并一度成为全球市值前三名的数字货币,也因此Sunny King被全球区块链社区与Vitalik Buterin和Daniel Larimer并称为区块链技术三大教主。最近我们团队在公链V SYSTEMS中发布了SPoS的PoS演进版本共识机制,解决了PoS此前的多个设计缺陷,也有效地抑制了其他变种PoS的中心化问题。


今天我的分享主题是我们团队的另外一个重要案例——质数币Primecoin,它的核心技术仍然着眼于共识机制,试图解决目前PoW的算力浪费问题,将无意义的PoW计算过程变成对科研有潜在意义的质数寻找过程。我们就从PoW开始谈起~


现行多数主流数字货币依然采用传统PoW方法进行采矿,而这样的挖掘算法没有现实意义,表面上看就是在浪费电而已,用电费换取数字货币的价值。我们以比特币为例来看,下面这张图是我刚刚从digiconomist.net网站上截下的,是目前比特币运行的核心数据。



从图中可以看到,比特币每年挖矿所需的耗电量大约73.12TWh,换算单位1TWh=10^9KWh,1KWh就是我们常说的1度电,这大约相当于700万个普通美国家庭的耗电量,碳排放量约是3*10^7吨。


更直观地看,比特币的耗电量大概与一个中等国家的耗电量相当,图中所示,比特币可以排名位于奥地利和委内瑞拉之间,大概在第40名的位置。



另外,由于比特币的TPS较低,每笔比特币交易耗电量约为400000笔visa交易,因此PoW的问题显而易见且被诟病已久。


鉴于PoW的上述缺陷,更多样的共识机制替代方法不断被提出,如被Peer Coin、Tendermint、Casper、Ouroboros等多种主流货币所青睐的PoS机制或者衍生出的DPoS机制;PoA/PoB/PoC/PoD…等等可以简称为PoX的各类共识机制;DAG等高并发可扩展的算法;以及各式各样的混合共识算法。


但这些共识算法虽然各自“鼓吹”自身性能的优越,却或多或少存在其他的问题,且安全性未得到大规模的验证,多数还没有被广泛采用。我们试图使用一种方法,既可以保留经检验的PoW算法模型,又可以将资源浪费问题完美化解,这就是Primecoin的核心思想。


简单而言,Primecoin是一种具有数学价值的数字货币,它是全世界第一个为数学问题而提出的电子货币,也是第一个拿出可行的解决方案的基于工作量证明(PoW)的加密货币。


我们为什么选取质数(或称素数)这样一种特殊的数学元素作为我们的核心思考方向呢?我们可以从质数的发展历程细细道来。


质数的发展源远流长,质数最早可以追溯至古埃及人的幸存记录中。在莱因德数学纸草书中的古埃及分数展开时,对质数与对合数有着完全不同的类型。而对质数具体研究的最早记录来自古希腊,在欧几里得《几何原本》中,算术基本定理、无限多个质数问题、如何构建完全数等等与质数有关的重要定理都被记录在册。


埃拉托斯特尼筛法、威尔逊定理、试除法、费马小定理、素数定理(数论中最重要的定理之一)等等与质数相关的问题在之后不断促进着基础数学学科的发展。1742年,哥德巴赫在给欧拉的信中提出了著名世界近代三大数学难题之一的哥德巴赫猜想:任一大于2的偶数都可写成两个质数之和。这一问题不仅难倒了大数学家哥德巴赫和欧拉,即使到今天也未完全解决。


长期以来,素数被认为在纯数学以外的地方只有极少数的应用。到了1970年代,发明公共密钥加密这个概念之后,情况改变了,它变成了RSA等加密算法的基础,我们现在日常生活中信息安全时常被提及,却鲜有人知在它之下发挥重要作用的其实是素数。


最近,关于素数的数学成就也不断冲击着我们。国人数学家张益唐在不依赖未经证明推论的前提下,发现存在无穷多差小于7000万的素数对,从而在孪生素数猜想这个重要问题的道路上前进了一大步。也因此,张益唐获得了包括Morningside特别成就奖、Ostrowski奖、Frank Nelson Cole奖、Rolf Schock奖等多项大奖。


质数是数论中最重要的元素之一,研究质数对未来的数学、计算机科学可能有着巨大而深刻的影响,寻找质数可以帮助我们更好地认识质数的分布。同时,质数也被广泛用来测试电脑硬件,例如英特尔使用寻找质数的程序来测试上市前的Pentium Pro芯片。可以说,我们目前能用到高性能的电脑都直接受益于质数。


在素数领域,有两种著名的素数对。一种是孪生素数(twin primes),指p和p+2都是素数,比如3和5;另一种是索菲格曼素数(Sophie Germain primes),指p和2p+1都是素数,比如3和7


扩展索菲格曼的素数对定义,坎宁安得到了素数链的概念。第一类坎宁安链(Cunningham chain of first kind)指这样一串素数,其中每个素数都大于前一个素数的两倍,比如3,7,17,37;第二类坎宁安链(Cunningham chain of second kind)指链中的每个素数都小于前一个素数的两倍,比如3,5,7,13。上面这两种形式的变体叫做孪生倍链(bi-twin chain),是指由许多对孪生素数组成的链,其中每一对孪生素数都大概是前一对孪生素数的两倍。


我们举一个例子,按照上述定义,5和7是一对孪生质数,他们的平均值(中心)是6。我们将6乘2得到了另一个中心12,而11和13是另一对孪生素数。这样一来,5,7,11,13就是一个长度为4 的孪生倍链。


从孪生倍链的中心分离,我们就可以分别得到两类坎宁安链。其中,在各中心之下的是第一类坎宁安链(如5,11),在各中心之上的是第二类坎宁安链(如7,13)。我们将第一个中心称为该质数孪生倍链的“原点”,从这个原点开始,可以一直翻倍找到质数紧挨着中心数。


例如,211049, 211051; 422099, 422101; 844199, 844201就是一组较大的孪生倍链。更大更长的孪生倍链可以通过维基百科搜索到,其中排名第四五六位的都是由Primecoin完成的。

当然,除了上述素数构成外,素数还有一些其他可能存在的奇妙的结构,比如素数星座或素数元组之类,但这些更为罕见的模式并没有被证明,而是仅有启发式的公式。


因为PoW的本质是对工作量的多少进行判定,所以到底是在计算什么其实根本不重要,因此我们可以考虑将上述素数的有趣特征嵌入到计算哈希值的PoW过程中,用来完成工作证明,也就是说将原本无意义的挖矿计算转变为寻找质数的计算。由于目前寻找大素数仍是一个比较困难的问题,因此,如果我们能在计算过程中寻找到一些被证明确实是素数的大整数,这些素数可能会对未来的科研工作有所帮助。


因为数字货币的工作证明需要被全部网络节点有效验证,因此质数不能太大,比如创纪录的梅森素数,并且根据我们的理解,随着链长增加,找到素数链的难度是呈指数级增长的,但是验证一个合理大小的素数是非常有效的。因此我们采用了上述坎宁安链和孪生倍链作为我们的验证内容。


在具体的实现过程中,我们不要求对素数做严格的验证,因为这可能会带来效率上的负担。当节点在进行素数验证时,只需要进行经典费马检测(Fermat test)和欧拉-拉格朗日-里夫西兹检测(Euler-Lagrange-Lifchitz test)就可以了。通过这样检测的素数被称为伪素数,也就是说有可能是合数,但实际上在以2为底的条件下寻找到一个伪素数甚至比寻找素数还要难。我们会通过一个网站收集所有可能的素数,为以后的工作包括严格判定做准备。


具体的数学公式和推导过程我们只放一个结果,大家有兴趣的可以深入研究一下~


那如何让寻找素数和区块链的哈希结合到一起呢?不让已经寻找到的素数被之后的区块重用是需要解决的第一个问题。我们令Primecoin上每一个生产出新区块找到的孪生素数链的原点都可以被该区块头的哈希整除,这样一来,除法的商其实就可以确保矿工完成了对应的工作证明。


除此之外,我们要求块头哈希需要有一个下界,因此在执行hashcash类工作时改变nonce值对主要的素数挖掘并没有太大帮助,因为通常需要在固定块头哈希之后生成筛选来完成证明。当然有一种情况例外,当改变nonce值且找到一个可以被一个小素数阶乘整除的块头哈希时会稍微有些帮助,但这只是一个很小的优势,且只能处理比较短的数。


素数链需要对挖矿难度进行调整,为了尽可能保证线性难度曲线,我们使用费马检验的剩余部分作为挖矿难度的指标。假设k是链长,链由p_0,p_1,……,p_{k-1}构成,r是链中下一个数p_k的费马检验余数,那么我们可以用p_k/r来衡量挖矿的难度。这样我们就可以得到一个包括分数部分的链长度,以表示难度系数,用如下公式计算d=k+(p_k-r)/p_k。而难度调整的规则与我们的点点币类似,通过对增减积分边界对链的长度进行上升或下降的调整,上升或下降的阈值在255/256<->1


在分析完可行性和难度调整后,我们来分析一下质数币的安全问题。类比比特币,主链协议确保只需超过一半的网络算力达成共识就可以达成链共识,同样,攻击者要超过50%的算力来控制或摧毁链,这是由hashcash的现行难度模型保证的。而在我们的primecoin中,同样需要50%的算力保证链的安全,但由于我们的难度曲线不是严格的线性关系,因此攻击者只需略低于50%的算力即可。目前我们还在进一步的跟进,不断调整对困难比的估计,以确保更好的安全性。


最后,我想放两句Vitalik对质数币的评价作为结尾。


“For the first time, we have a currency whose mining algorithm has a secondary value, and at the same time Primecoin, unlike so many other coins before it, actually makes serious attempts to improve on Bitcoin in unrelated aspects.”

“Primecoin may well be the first alternative coin to actually be better than Bitcoin.”


大概意思是,质数币第一次让挖矿过程产生了附加价值,并且很可能是第一种比比特币更好的替代货币。


问答分享


Q:感谢董博士的分享,尽管具有数学价值的数字货币理解起来确实抽象,但要为primecoin的理念之美点赞。问一个容易理解的问题:现在prime coin的挖矿方式是什么,是GPU? 有矿池或矿机吗?

A:对的,是GPU。现在有两个大的矿池,分别是coinsforall.io和xpmforall.org

Q:质数币里的数学背景很厉害,质数链最近技术方面有新的进展吗?

A:感谢大家。我们最近在逐步更新质数币的协议。主链上引入了txindex,address index,可以从链上读出地址的余额。安卓钱包可以使用测试链,方便体验。

Q:质数币的TPS是多少?

A:目前,质数币出块间隔大约一分钟(比特币大概十分钟,所以效率上是有提升的),其余部分的功能与比特币没有太大差异。我们更希望推广这种共识方式,并且让它适用于各类支付、认证、确权等应用场景。

Q:比特币每四年减半,质数币也有这样的设计吗?

A:质数币并不像比特币一样具有固定的总数上限,其他很多主流货币采用了这种方式。质数币的铸币率是由难度决定的,这也反映出它的安全性也会依赖于采矿市场,而非比特币的严重依赖交易费用。

Q:我很喜欢质数币里的数学,让工作量验证变成有意义的工作,既可以实现一种区块链发币,还能利用社会上的计算力推动数学科学的发展。真是天才的想法。据我所知,科学中还有很多计算量非常巨大,科学意义也重大的问题,比如湍流,三体问题等等。可否设计类似的pow机制,利用社会上的算力解决这些问题。

A:如果能做出这些pow机制,这对科学的贡献是非常大的,但目前这方面的尝试还很少,质数链向这个方向走了一步。我目前更擅长数学领域的研究,如果能有擅长其他领域研究人员加入进来思考这些问题更好。

本文旨在传递行业信息,不构成任何投资建议。文章仅代表作者观点,不代表小雨智媒官方立场。

Comments

no comments

Recommend to Read

币信

原创

10-31

关注
关注

真本聪RealSatoshi

原创

16 hrs ago

关注
关注

币圈基者

原创 首发

09-29

关注

ViaBTC

原创 首发

10-24

关注

区块链Sir

原创

09-28

关注

野花说

原创

10-21

关注

58COIN交易所

原创

09-23

关注

WBFex

原创

10-10

关注
加载更多