一种提高比特币私钥碰撞机率的思路

之前的文章里面我们提到了一个名为 LBC 的项目；它采用了遍历所有比特币私钥，bloomfilter所有未花费的币的地址来碰撞比特币私钥。

这个项目本身详尽 计算了这种碰撞成功的几率 ，目前碰撞空间大概在 2 ¹³⁶ 级别。

目前在一台最顶级的AWS GPU计算节点上面的碰撞效率是这样的:

AWS p2.8xlarge   32 vCores Xeon v4, 8x K80 GPUs (50% each)   ~80-88M/s

每秒钟大概碰撞8000w次；目前LBC这个项目最顶峰的时候，算力到了1G的级别，这样计算下来:

2^136 / 2^30 = 2 ^106

2 ¹⁰⁶ 级别的碰撞效率还是遥遥无期啊；

如果通读我们之前的文章就知道，比特币地址的生成，主要花费在ECDSA、SHA256, RIPEMD 这三个算法的操作之上，但其实用GPU计算，这三个步骤花费的时间是很少的，在整个碰撞过程中，其实大部分时间是耗费在bloomfilter上面的；

而bloomfilter的原理，采用的是多级HASHMAP，常理来看，这已经是判断一个元素是否存在某集合的极限效率了；

但是有一点我们不要忘记，比特币的地址采用base58编码，他的地址空间是有规律的，简单来说，就是所有比特币地址的前缀分布，是有规律可循的，他应该在base58的编码范围内成正态分布；而bloomfilter的HASHMAP是没有这种条件优化的，所以说bloomfilter的算法我们可以再改进一下，提升效率。

我分析了截至2018-12以前的所有比特币地址，简便起见，提取了所有的P2PKH地址(共 377059211个地址)，取其前4个字符地址前缀；执行:

sort 4prefix.addr|uniq -c|sort -nr

得到了所有地址前缀的分布列表，差不多是个正态分布。

列举一下最常用的地址前缀TOP10:

  23600 1bit
  23086 1btc
  21895 13vs
  21329 1gbx
  21267 1gbt
  21267 1gba
  21210 1gbb
  21206 1gbf
  21196 1gbu
  21189 1gbr

最常见的是1bit和1btc这两个前缀，各比第三名多出了10000个左右，这多出来20000个地址应该是Geek们自己生成的虚荣地址。

所有的比特币P2PKH地址，4字母前缀共有42877种组合。

好了，这就是我们可以优化的地方，把bloomfilter的第一级HASHMAP，采用这些前缀组合先来一把过滤，再去执行常规的Bloomfilter，碰撞效率会再提高一个数量级。

我在自己机器上实验了一下，在GTX750Ti 2G显卡上面，最终效率可以达到 10M/s。

瓶颈现在又变成了genaddress环节，我估计在一块RX480卡上面，可以达到和AWS顶配GPU一样的效率；

不过，效率提升十倍，也不过是 2 ¹⁰⁰ 的碰撞范围，还是遥遥无期啊。

更深入的分析

早期在bitcointalk.org论坛上，Laszlo Hanyecz曾经有过一个想法，就是随着硬件性能的发展，最终碰撞比特币私钥的收益会不会超过挖矿的收益？

中本聪当时的回答是，要达到这个碰撞算力很远很远。

我们来仔细分析一下：

比特币的地址生成是很容易硬件ASIC化的，如果用这种前缀过滤法，也不需要多少内存，所以可以近似认为：如果硬件化，比特币私钥碰撞的效率和挖矿效率是差不多的。

目前比特币全网算力在40EH左右，就是2 ⁶² ，这已经是相当于400w台蚂蚁S9的机器同时24X365 运行了；消耗的电力估计已经超过了上海市的居民用电，比特币矿机的能源消耗，完全可以说是抵得上一个小型国家的能源消耗了。

如果私钥碰撞达到2 ⁶² 级别，那么毛估估，碰撞几率就能减小到 ½ ⁶⁰ 级别了；

但是这个概率还是太低了。

而且另外一个无法预测的情况就是，将来人们的安全意识加强，一般一个地址只要用过就会丢弃掉，所以最终bloomfilter的条目变化会非常频繁，还要考虑一个数量级的损耗。

目前测算，随着手续费用的提高，即使多次减半，将来挖矿的收益估计很长期稳定1-10btc/block级别，在如果将来以1年时间碰撞一个私钥的概率期望测算的话，一年大概是2 ³⁰ 秒，这样碰撞效率至少要提高到 2 ⁹⁰ 级别，才能达到 破解私钥得利 > 挖矿得利 的效果；

算力提高到2 ⁹⁰ ，不管用什么技术，即使是量子计算，也很难想象能到这个量级啊；

而且，即使到了这一天，把RIPEMD替换成一种碰撞空间更大的算法就OK了。

这样看来，bitcoin的安全性还是无懈可击。