比特币地址碰撞概率

504439418

校稿：

原文中对比“买彩票中500万概率”的表达方法有错误，应该如下表达。

结论1：碰撞特定比特币地址的概率

结论2：碰撞任意有币地址的概率（生日攻击）

正文：

关于比特币地址的碰撞概率，好像还没有特别详细的论证。其实这是一个非常重要的问题。因为它直接影响到大众对比特币安全的信心。

严谨的碰撞概率计算，需要考虑的因素太多，算式也复杂。所以，以下的分析仅在数量级上，进行简单的逻辑推算和对比。

准确度不高，仅供娱乐。

先把结论给不想看过程的朋友：

结论1：碰撞特定比特币地址的概率

结论2：碰撞任意有币地址的概率（生日攻击）

下面我来看看这两个结论的推导过程。

当然，推导之前，我们首先要把比特币地址研究透彻。

比特币地址不是公钥

这句话可能出乎很多人意料。

其实，严谨的说法应该是：

我们看一下比特币地址的生成过程就比较清楚了。

比特币地址的生成过程

（说明: 有些数字以"0x"开头，意思是此数字使用十六进制表示法。"0x"本身没有任何含义，它是C语言流传下来的，约定俗成的写法，比如0xA就是十进制的10。另外，1个字节 = 8位二进制 = 2位十六进制）。

第一步，随机选取一个32字节的数、大小介于1 ~ 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141之间，作为私钥。

第二步，使用椭圆曲线加密算法（ECDSA-secp256k1）计算私钥所对应的非压缩公钥。 (共65字节， 1字节 0x04, 32字节为x坐标，32字节为y坐标）关于公钥压缩、非压缩的问题另文说明。

第三步，计算公钥的 SHA-256 哈希值

第四步，取上一步结果，计算 RIPEMD-160 哈希值

第五步，取上一步结果，前面加入地址版本号（比特币主网版本号“0x00”）

第六步，取上一步结果，计算 SHA-256 哈希值

第七步，取上一步结果，再计算一下 SHA-256 哈希值（哈哈）

第八步，取上一步结果的前4个字节（8位十六进制）

第九步，把这4个字节加在第五步的结果后面，作为校验（这就是比特币地址的16进制形态）。

第十步，用base58表示法变换一下地址（这就是最常见的比特币地址形态）。

base58

简单介绍一下base58。Base58其实就是58进制表示法。

Base58编码表：

实际值	编码值		实际值	编码值		实际值	编码值		实际值	编码值
0	1		16	H		32	Z		48	q
1	2		17	J		33	a		49	r
2	3		18	K		34	b		50	s
3	4		19	L		35	c		51	t
4	5		20	M		36	d		52	u
5	6		21	N		37	e		53	v
6	7		22	P		38	f		54	w
7	8		23	Q		39	g		55	w
8	9		24	R		40	h		56	y
9	A		25	S		41	i		57	z
10	B		26	T		42	j
11	C		27	U		43	k
12	D		28	V		44	m
13	E		29	W		45	n
14	F		30	X		46	o
15	G		31	Y		47	p

打个比方，十进制的"58"，用16进制表示就是3A，用base58表示就是"21"（因为1是0，所以2是1），而十进制的"68"，Base58表示就是"2B"。

为什么使用这个奇怪的编码呢？（搞编程的同学注意一下，比特币使用的Base58和常用的base58的字典顺序有区别。）

引用中本聪在源码base58.h中的注释：

椭圆曲线加密算法、SHA-256哈希算法、RIPEMD-160哈希算法

这三个算法的原理，一句两句说不清楚，先忽略了。以后再写文章详细介绍吧（不要打我）。

只说用途：

• 椭圆曲线加密算法：把任意随机数当做私钥，生成公钥形成密码对。私钥保密，公钥公开。私钥签名的信息，可用公钥验证签名的真实性。签名无法伪造。
  
• SHA-256哈希算法：把任意大小的数据，经特定算法混淆后，生成一个256位二进制长度的数，作为原数据的摘要信息。（可正向验算，无法反推）RIPEMD-160哈希算法：把任意大小的数据，经特定算法混淆后，生成一个160位的二进制长度的数，作为原数据的摘要信息。（可正向验算，无法反推）
  

地址可以没有公钥

搞清楚比特币地址的产生步骤，我们可以得出以下结论。

• 仅有比特币地址，无法反推出公钥。合法的比特币地址不一定有对应的公钥。
  

比如这个：

它是这样构造出来的：

有意思的是，真的有人往这个地址里发币（大约3个币，这些币相当于被销毁了），看这里: https://blockchain.info/address/1111111111111111111114oLvT2

比特币地址碰撞

地址的来历搞清楚了，我们来分析一下如何碰撞。

拿全零地址："1111111111111111111114oLvT2"举例。

仅随机碰撞出该地址对应的公钥是没有意义的。因为比特币交易需要私钥签名才有效。

所以，如果你想使用这个地址里的比特币，前提是拥有这个地址对应公钥的私钥。

也就是说，你需要：

• 随机生成一个私钥。
  
• 计算该私钥对应的公钥.
  
• 用公钥算出比特币地址。
  
• 与目标地址对比，看看是否一致。如果不一致，回到第1步。
  

根据比特币地址理论总数，容易的看出，单次碰撞成功的理论概率是：

由于每次碰撞至少需要3次SHA-256运算，我们放宽为2次。

在不考虑其他运算的情况下，假设你有1E/每秒的算力（ E = 2^60 相当于当前比特币全网算力的10倍）进行破解。那么，每秒碰撞该地址成功的概率：

假设你可以活 2^32秒 = 4294967296秒 ≈ 136.2年，你在有生之年碰撞该地址成功的概率为：

这是个什么概念呢？

我们看双色球命中500万的概率：

用这个概率除以碰撞概率：

所以，结论是：假设，你掌握了比特币当前全网算力的10倍，花136年不间断地，碰撞一个特定比特币地址。碰撞成功的概率，相当于买福彩双色球中了333103亿次500万。(注意单位是亿)（注：结论有错误，见校稿。）

考虑生日攻击

当前，有币的地址大约为300万个。看这里：http://btc.ondn.net/search

我们把这个数字翻1万倍。假设有343亿个有比特币的地址（2^35 ≈ 343亿，相当于每个地球人有5个有余额的地址，火星人的先不算了，呵呵)

那么命中其中任意一个地址的概率：

再和中500万比一下：

咦，和中1000次500万的概率很接近了!

所以，结论是：假设，你掌握了比特币当前全网算力的10倍，花136年不间断地，碰撞所有存币地址。碰撞其中任意地址的概率，相当于买福彩双色球中1000次500万。 （注意，这些地址中50%以上存币量小于0.001BTC）（注：结论有错误，见校稿。）

后记

以上计算有很多省略的地方，计算时考虑最宽松情况。所以实际概率更小。

比特币系统的设计，让拥有算力的人倾向去算blockchain，因为比碰撞地址划算的多。

本文计算有错误疏漏，欢迎指正。但是指正了，我也不一定改。（开个玩笑，不要打我）

没中过1000次500万的同学，不要幻想算出别人的地址了，不如去玩骰子...洗洗睡吧。

喜欢《比特币地址碰撞概率》请捐款：

122222o5a3k6dy7WL5maBBpuvKUtZJhMk4

这个好看的地址是用币付宝的个性收款地址功能生成的。

参考文献：

• https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
  
• https://en.bitcoin.it/wiki/Base58Check_encoding
  
• http://procbits.com/2013/08/27/generating-a-bitcoin-address-with-javascript
  
• https://bitcointalk.org/index.php?topic=41718.0
  
• https://en.bitcoin.it/wiki/List_of_address_prefixes
  
• https://en.bitcoin.it/wiki/Wallet_import_formathttps://en.bitcoin.it/wiki/Private_key