比特币的挖矿经历了从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)的算法了。大师也有失算的时候。
==================================
区块链与数字货币
待字闺中官方区块链社区——做区块链社区中的精品社区。
往期推荐:
1、头条易读遵循行业规范,任何转载的稿件都会明确标注作者和来源;
2、本文内容来自“待字闺中”微信公众号,文章版权归待字闺中公众号所有。