Blockchain

Bitcoin puzzle transaction

这是一笔神奇的比特币交易…

2015年1月16日，比特币的链上出现了一笔神奇的交易，这笔交易有一个输入，256个输出，每个输出的大小从以1 mBTC的幅度递增，直到最后第256个输出。

在这笔交易发出后的短短几秒之内，前20个输出就被花费掉了。随后，21-50陆陆续续被花费：

同年的8月份，Ryan Castellucci大佬发布了比特币脑钱包crack工具brainflayer，他在用brainflayer crack私钥的时候，发现了一个有趣的现象，下面这些私钥，对应的正好是上面那笔交易输出的接收方：

第n个私钥对应的输出价值为n mBTC，同时第n个私钥从右边起n个bit位为随机，其余全为0。前20笔输出立即被花费，一定是有机器人在监控着比特币网络，不断检查一些弱私钥对应的地址中是否有余额，有便转走。

我们知道，比特币私钥是一个256位的二进制数，总共有pow(2, 256)种组合，现阶段想要通过随机尝试的方式找到碰撞几乎是不可能的，上面提到的那笔交易，很有可能是发出者为了查探目前黑客们的老底，按照上面的私钥规律，只需要从0开始尝试所有私钥，不断加1，就有可能把所有256笔输出拿走，而根据相邻两笔输出被花费的时间差，就可以大致判断目前的黑客们手里的计算资源有多少了。

这个规律被发现后，有人甚至发起了一个分布式项目Large Bitcoin Collider来专攻这个puzzle，从0开始一个个尝试所有私钥，根据项目网站上公布的消息，截止2017年11月15日，他们已经成功算出了第54笔输出的私钥0x236fb6d5ad1f43。不过目前（2019-11-03）来看，第63笔输出已经被花费掉了，从64开始断断续续有几个地址上的钱被转走，106之后就没有动过了。

估计是为了鼓励大家撸起袖子加油干，这个交易的发起人把161以后的所有输出分配到了前面的地址，现在如果能crack掉第n个地址，能够拿到的奖励是0.1 * n个BTC。

我就静静地做一个吃瓜群众:-) 哪能啊，当然得自己动手玩玩啦。

首先，得把这笔交易的输出对应的地址拿下来：

1
2
3
4
5
6
7
8
9
10
11
12
13
import json
import requests as req

ret = req.get('https://blockchain.info/rawtx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15')
tx = json.loads(ret.text)

with open('addresses.txt', 'w') as f:
    addr_list = []
    for out in tx['out']:
        addr_list.append(out['addr'])
    for addr in addr_list:
        f.writelines(addr)
        f.write('\n')

为了使用brainflayer，我们得把地址转换成ripemd160格式：

1
2
3
4
5
6
7
8
9
10
11
import sys
import base58

def addr_to_hash160(addr):
    hash160 = base58.b58decode(addr)
    return hash160.hex()[2:-8]

for line in sys.stdin:
    print(addr_to_hash160(line.rstrip()))

#run: cat 'addresses.txt' | python3 addr_to_hash160.py > addr.hex

然后得去编译一下brainflayer：

1
2
git clone https://github.com/ryancdotorg/brainflayer
cd brainflayer && make

编译成功的话你会看到一个叫做hex2blf的工具，是为了从上面的地址列表中构建出一个bloom filter，bloom filter是一个概率数据结构，用来检测某个地址是否在我们的256个地址列表里面：

1
hex2blf addr.hex addr.blf

现在就可以开始寻宝之旅了:)

1
brainflayer -v -b addr.blf -I 0000000000000000000000000000000000000000000000000000000000000001

上面这条命令让brainflayer从1开始尝试所有私钥，判断生成的地址是不是在我们的256个地址列表里面。当然，如果真想crack这个puzzle，我们得站在前人的肩膀上，目前第63个输出已经被转走了，所以我们可以从这里开始算，第64个输出对应的私钥倒数第64位为1，对应的hex格式为000000000000000000000000000000000000000000000000c000000000000000。

自增1太慢，可以每次自增2，当然这样就有可能恰好错过了正确的私钥：

1
brainflayer -n 1/2 -v -b addr.blf -I 000000000000000000000000000000000000000000000000c000000000000000

下面是我从第54笔输出开始算的截图，好几个小时过去了，除了最开始的第54笔输出，搜索了34亿个地址，一无所获…

当然，因为brainflayer现在的实现是单线程的，完全没有发挥出现代多核计算机的能力，所以这个搜索速度应该还有几个数量级的提升空间，但比起多一个随机的比特位所带来的计算复杂度的提升，还是小小小小小巫见大巫了…