微信扫一扫
分享到朋友圈

抗ASIC挖矿算法Scrypt

作者:待字闺中 来源:待字闺中 公众号
分享到:

04-03

比特币的挖矿经历了从CPU,到GPU,到FPGA,到ASIC的过程,本来中本聪的意愿是“一CPU一票”,真正让比特币的挖矿成为一个民主公平的过程。可是,由于利益的诱惑,人们开始使用特制的芯片来实现SHA-256哈希算法,让使用CPU的用户基本没有机会得到区块生成激励,进一步使得原本设想的去中心化,一步一步集中到很有实力的中心化的矿池手上而不再是美好的去中心化。


SHA-256算法的原理图如下。c是一个将768位的输入压缩成一个256位输出的压缩函数,它是一个具有碰撞阻力的哈希函数。一个变长的输入,通过分成很多定长的512位的块,然后迭代调用c来获取最后的256位Hash值。从原理可以看出,用很少的存储就能用芯片实现快速的计算,特别适合ASIC实现。



那么问题来了,如何能设计一种新的算法能抗ASIC呢?


没有什么能难倒聪明的人类的,问题总是会有答案的。在莱特币中率先使用了抗ASIC的挖矿算法Scrypt,核心理念是在算力(CPU)和内存(RAM)之间达到一种平衡。内存(RAM),对于ASIC,还是CPU来说,制造成本和访问速度是区别不大的。那么,Scrypt迫使矿工要么有大的内存来缓存中间的Hash结果来提高计算速度和效率;或是没有大的内存,那就必须重复的计算Hash来大量消耗计算能力。


Scrypt实现的伪代码:



从第9行可以看到,V[j]实际上是使用内存中缓存的之前计算的SHA-256的Hash值来减少了一系列SHA-256的计算,是不是很像动态规划中使用缓存来保存之前计算的状态来减少重复计算。如果没有很大的内存(RAM),那么我们看到第5行所做的预先计算就不能使用了。这时,必须在需要的时候再重新计算。而V[j]是前面V[j-1]的SHA-256计算值,而V[j-1]是前面V[j-2]的SHA-256计算值,等等,这么下来,得到V[j]的时间复杂度是O(N)。考虑第6-9行的循环,所以,整个算法,在没有内存(RAM)缓存的情况下,是O(N*N)(平方)的时间复杂度;在有内存缓存的情况下却是O(N)(线性)的时间复杂度。当N很大的时候,平方计算是个很费时的过程,这时,矿工就需要平衡内存和计算力了,因为强大的计算力不再有优势。


中本聪估计是从人类本是善良的假设出发,采用了简单的SHA-256来挖矿,否则,TA一定会使用类似于Scrypt这种需要平衡内存(RAM)和算力(CPU)的算法了。大师也有失算的时候。


==================================

区块链与数字货币


   待字闺中官方区块链社区——做区块链社区中的精品社区。


往期推荐:


阅读9697
举报0
关注待字闺中微信号:gh_81abae3e5d59

用微信扫描二维码即可关注
声明

1、头条易读遵循行业规范,任何转载的稿件都会明确标注作者和来源;
2、本文内容来自“待字闺中”微信公众号,文章版权归待字闺中公众号所有。

评论
更多

文章来自于公众号:

邮箱qunxueyuan#163.com(将#换成@)
微信编辑器
免责声明
www.weixinyidu.com   免责声明
版权声明:本站收录微信公众号和微信文章内容全部来自于网络,仅供个人学习、研究或者欣赏使用。版权归原作者所有。禁止一切商业用途。其中内容并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。如果您发现头条易读网站上有侵犯您的知识产权的内容,请与我们联系,我们会及时修改或删除。
本站声明:本站与腾讯微信、微信公众平台无任何关联,非腾讯微信官方网站。