深度解析：51%攻击的成功概率和时间 [代码+计算] | 火星技术贴

极客社区，教你如何甄别项目技术，搭建技术狂人交流舞台，分享区块链财富密码。  致力于打造一个平等、自由、安全、开放的高质量社区。

51%攻击的成功概率和时间

Satoshi的论文的描述了指定算力的攻击成功的概率计算方式 本文试图通过已有的block计算实际51%攻击的概率和需要的时间 通过分析目前已经生成的block时间和密度分布计算实际51%攻击的概率和需要的时间

Satoshi计算的基于泊松分布的理论概率

理论概率计算方式来自Satoshi的论文 https://bitcoin.org/bitcoin.pdf

中文版 http://www.8btc.com/wiki/bitcoin-a-peer-to-peer-electronic-cash-system

下面截图来自中文版本: 

如果p>q，则攻击者掌握了一半以上的算力，那么概率上永远是赢的。该事件（攻击者胜出）的概率是固定，且N次事件之间是相互独立的，那么这一系列随机过程符合泊松分布(Poisson Distribution)。Z个块时，攻击者胜出的期望为lambda：
攻击者在攻击时已经偷偷的计算了k个块，那么这k个块概率符合泊松分布(下图左侧部分)，若k<=z，那么追赶上后续z-k个块的概率为(q/p)z-k，即， 展开为如下形式：

c lang 版本：

#include

python 版本：

def  attackerSuccessProbability(q, z):   sum =1.0   p = 1.0 - q    lamba = z * (q/p)   i = 0;   k = 0;   for k in range(z +1):      poisson = exp(-lamba)      for i in range(1,k+1):          poisson *=(lamba/i)      sum -=poisson * (1 - pow(q/p, z-k))         return sum

对其进行运算，我们可以得到如下的概率结果，发现概率对z值呈指数下降。

当q=0.1时

z=0 P=1.0000000z=1 P=0.2045873z=2 P=0.0509779z=3 P=0.0131722z=4 P=0.0034552z=5 P=0.0009137z=6 P=0.0002428z=7 P=0.0000647z=8 P=0.0000173z=9 P=0.0000046z=10 P=0.0000012

当q=0.3时

z=0 P=1.0000000z=5 P=0.1773523z=10 P=0.0416605z=15 P=0.0101008z=20 P=0.0024804z=25 P=0.0006132z=30 P=0.0001522z=35 P=0.0000379z=40 P=0.0000095z=45 P=0.0000024z=50 P=0.0000006

求解令P<0.1%的z值:

q=0.10 z=5q=0.15 z=8q=0.20 z=11q=0.25 z=15q=0.30 z=24q=0.35 z=41q=0.40 z=89q=0.45 z=340

当q = 0.51时，成功概率已经大于1:

z=0 P=1.000000z=1 P=1.014415z=2 P=1.020987z=3 P=1.025839z=4 P=1.029825z=5 P=1.033268z=6 P=1.036329z=7 P=1.039102z=8 P=1.041648z=9 P=1.044010

**注意：以上是假定符合泊松分布,来计算的，但实际上由于目前算力被各大矿池垄断，二项分布更准确一些

asdfaoeu计算的基于二项分布的概率

asdfaoeu在这里 http://www.reddit.com/r/Bitcoin/comments/1946jp/how_to_calculate_the_probability_of_a_double/
有按二项分布计算的结果及计算代码  https://gist.github.com/anonymous/5022462

51%攻击成功需要的理论时间估算

   z=1  t=190 (分钟)   z=2  t=380   z=3  t=570   z=4  t=760   z=5  t=950   z=6  t=1140   z=7  t=1330   z=8  t=1520   z=9  t=1710   z=10 t= 1900

大概2小时内，6个block内, 51%的算力，追上的概率为40%左右
当然这个很不准确，因为实际时间会根据A，B生成block的需要时间的概率密度上下浮动

基于已有的block时间计算的概率

Satoshi的论文给出了51%攻击的理论概率，但是实际上的攻击成功概率要受很多因素影响,包括但不限于:

算力变化：
算力一直增长，总体趋势一直向上,所以生成block的实际时间其实小于10分钟，在9分钟左右

难度变化：
难度每隔2016block，大约2周调整一次，实际上由于算力增长，一直小于2周

time变化:
timestamp,在不同miner之间并不一致，所以有同步导致的影响

挖矿算法：
如果nonce正好落在开始计算的数字附近, 运气， 比如矿池总是从0开始计算nonce,nonce恰好落在0附近，如果相反则需要更多的时间

实际概率计算

如何计算实际的51%的攻击概率呢？
bitcoin创建到现在总计产生30多万个block, 我们可以用这30多万个block的时间来估算51%攻击实际的概率和需要的时间
以下以6个confirm为例，来计算实际可能的概率
正常的 blockchain, 我们称之为C

[]----->[]----->[]----->[]----->[]----->[]----->[] C blockchain

诚实节点计算的 A blockchain
攻击节点计算的 B blockchain

[]----->[]----->[]----->[]----->[]----->[]----->[] A blockchain        \         []----->[]----->[]----->[]----->[]----->[]----->[] B  blockchain

分别计算每连续6个block的生成时间间隔:
t1 = blk5.time – blk0.time t2 = blk6.time – blk1.time ….. tx = blkn.time – blk(n-5).time
这样得到100%算力的C的连续生成6个块的时间集合 {t1,t2,t3….tx} TC1
然后用同样的方法计算连续生成7个block的时间间隔, 得到100%算力的C的连续生成7个块的时间集合 {t1,t2,t3….} TC2
对TC1绘图，得到正常的C blockchain 连续生成6个block时间分布曲线
x为连续的6个block
y为生成连续的6个block的时间

对时间排下序得到下图,可以得到连续生成6个block需要的最少时间和最多时间

然后对T1计算，每间隔10秒内Tx的数目, 得到{len(T1…Tx),len(Tx+1….Tx+n)….}，得到密度分布曲线,如下

上图可以看出连续生成6个block需要的时间
把A和B看成一个独立的blockchain，则 A,B生成block概率的密度分布应该和C一致，但是由于A,B的算力下降，所以把时间轴等比缩放,
A 连续生成6个块需要的时间集合{t1,t2,t3….} TA = TC1 * 100/(1-49)
B 连续生成7个块需要的时间集合{t1,t2,t3….} TB = TC2 * 100/(1-51)

得到A，B的曲线(左边为A，右边为B),和A可能的连续生成6个block的时间集合TA，和B连续生成7个block的时间集合TB

如果此处对是否可以缩放的疑问,可以看下面的曲线，每隔20000个block分别计算密度分布，难度应该变化10倍左右，算力变化x倍，发现block生成时间密度曲线基本重合
现在问题转化为在TA中随机选一个时间，大于TB中任意元素的概率
代码如下:
AB为有序集合，从小到大依次排列
AB中任意取元素a,b, 计算a>b的概率

def AB (A,B):    N = []     qz = 0.0    for i,a in enumerate(A):       n = 0       for b in B:          if a<=b: break          else: n+=1       N.append(n)    return  float(sum(N))/(len(B) *len(A))

实际的计算结果

51% 算力攻击, height高度为280000~300000, 20000个block的生成时间密度计算成功的概率为

z=0 P=1.000000z=1 P=0.25991752883z=2 P=0.327356211643z=3 P=0.362791063488z=4 P=0.38572021231z=5 P=0.402129295953z=6 P=0.41492854999

如果觉得20000个样本不够，那么以height高度为200000~300000的, 100000个的生成时间密度计算成功的概率为

z=0 P=1.000000z=1 P=0.258909623337z=2 P=0.327897207064z=3 P=0.363898341947z=4 P=0.387023480539z=5 P=0.403786580212z=6 P=0.416886094841

实际攻击成功需要的时间

Tc2 < Tc1的时间范围, 就是{min(Tc2) ~ max(Tc1)}为最有可能的时间为
51% 算力攻击成时间密度计算成功的时间范围大概为

{452s ... 13514s}

51%攻击能造成什么破坏

修改自己的交易记录，这可以使他进行双重支付
阻止区块确认部分或者全部交易
阻止部分或全部矿工开采到任何有效的区块

51%攻击不能做什么

修改其他人的交易记录 , 因为没有privateKey
阻止交易被发出去（交易会被发出，只是显示0个确认而已）
改变每个区块产生的比特币数量
凭空产生比特币
把不属于他的比特币发送给自己或其他人

51%攻击防范

注意长时间的大规模算力消失
有大额交易时多等几个确认, 等待confirm超过2小时
实时检测soft fork chain
监控从矿池发出的大额交易
监控矿池算力变化,长时间不出块

其他注意事项

所以发起51%攻击必须在短时间内完成,理由如下：
当算力小于50%时候，攻击成功概率随着时间变小
当算力大于50%时候，攻击成功概率随着时间变大
当算力大于50%的时候，随着攻击时间变长，从算力看攻击成功率变大，但是失败的概率反而变大，因为长期的大规模算力消失，必然会引起社区注意
超过2小时，则bitcoin网络不会接收新的block, 这个是btc网络规定的

思考

TODO 什么时候开始攻击最合适，算力刚刚调整完毕开始攻击？ 从实际概率估算，经济学成本到底是多少 confirm几个块才安全? 等多长时间才安全? 指定时间，如何计算成功概率？ 指定概率，如何计算成功需要时间？* 实际的51%攻击分析