Living a Simple Life is a Happy Life

有饭吃,自由自在,就非常开心

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

| Comments

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

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

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

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

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

1
2^136 / 2^30 = 2 ^106

2106 级别的碰撞效率还是遥遥无期啊;

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
  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一样的效率;

不过,效率提升十倍,也不过是 2100 的碰撞范围,还是遥遥无期啊。

更深入的分析

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

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

我们来仔细分析一下:

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

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

如果私钥碰撞达到262级别,那么毛估估,碰撞几率就能减小到 ½60 级别了;

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

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

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

算力提高到295,不管用什么技术,即使是量子计算,也很难想象能到这个量级啊;

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

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

Comments