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

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

sky 队长 船龄 8.8年 来源 blockindex.info
 54447  4

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 double AttackerSuccessProbability(double q, int z){    double sum    = 1.0;    double p      = 1.0 - q;    double lambda = z * (q / p);    int i, k;    for (k = 0; k <= z; k++) {        double poisson = exp(-lambda);        for (i = 1; i <= k; i++)            poisson *= lambda / i;        sum -= poisson * (1 - pow(q / p, z - k));    }    return sum;}

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%攻击成功需要的理论时间估算

Satoshi论文中只说了攻击成功的概率,没有计算攻击成功需要的时间

以下以固定算力估计算51%攻击成功需要的时间

rateA :A 诚实节点 49% 算力

rateB :B 攻击节点 51% 算力

A B都在各自的blockchain分支上计算

计算 B偷挖n个块后需要多长时间超过A?

A 和 B 概率固定的时候

固定概率计算, B偷挖n个block后经过一段时间后超过A,这是A挖了m个block

rateA = 100 *10/49 #A 计算一个块需要的分钟数

rateB = 100 *10/51 #B 计算一个块需要的分钟数

m *rateA = (m + n) * rateB #超过1个块才能有效攻击

(rateA - rateB) = n rateB

m = n * rateB /(rateA - rateB)

需要的时间为 t = m * 10(分钟)

计算结果为结果吧:

   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%攻击分析

参考

生成block的曲线分布

生成block的曲线分布(排序后)

生成block的时间密度分布

49%和51%算力生成block的时间密度分布对比

官方的wiki对51%攻击问题的解释 https://en.bitcoin.it/wiki/Weaknesses#Attacker_has_a_lot_of_computing_power

51%攻击视频介绍 https://www.youtube.com/watch?v=6luEMwSAS0I

http://www.reddit.com/r/Bitcoin/comments/1946jp/how_to_calculate_the_probability_of_a_double/

http://personal.maths.surrey.ac.uk/st/J.Deane/Teach/se202/poiss_bin.html

http://bitcoin.stackexchange.com/questions/658/what-can-an-attacker-with-51-of-hash-power-do

关于双花攻击成功率的讨论

不同的PoW机制和遭受51%攻击的山寨币】 http://www.8btc.com/different-proof-of-work-mechanisms-and-several-altcoins-that-have-been-hit-with-a-51-attack

Ghash.io:你想干什么?http://www.8btc.com/51atack

51%攻击解析 http://www.8btc.com/51attack

工作证明与挖矿 http://618.io/2013/08/03/proof-of-work-and-mining/

Analysis of hashrate-based double-spending http://arxiv.org/pdf/1402.2009v1.pdf

权益证明PoS 创始人Sunny King对于针对PPC实施51%攻击的成本给出了权威的解读。并从通胀率的角度,指出了6-7年后对BTC实施攻击的成本, 对PPC实施51%攻击的成本. http://bbs.btcman.com/forum.php?mod=viewthread&tid=19150&fromuid=4242

51%攻击解说-没那么可怕,多等几个确认就可以应对 http://www.bit-sky.com/index.php/2014-01-27-19-37-19/2014-02-03-15-31-33/898-51

Ghash.io曾实施过双重支付(51%攻击) http://bbs.btcman.com/forum.php?mod=viewthread&tid=18993&fromuid=4242

Ghash可能掌控超过51%算力 http://bbs.btcman.com/forum.php?mod=viewthread&tid=18994&fromuid=4242

比特币开发人员Peter Todd 出售了自己50%的比特币,坦言不如以前有信心了http://www.reddit.com/r/Bitcoin/comments/281ftd/why_i_just_sold_50_of_my_bitcoins_ghashio/

GAVIN ANDRESEN 对GHASH高算力发表看法 | 比特币基金会首席科学家Gavin andresen在6月13号对Ghash.io算力接近50%的情况发表了个人的看法。Gavin认为在Ghash挖矿的矿工应该撤出Ghash矿池,转入其他小矿池或加入p2pool。http://gavintech.blogspot.com/2012/05/neutralizing-51-attack.html

Ghash.io声明 https://ghash.io/ghashio_press_release.pdf

Ghash.io算力过半,CEX.IO不表态,引发51%攻击恐慌 http://bbs.btcman.com/thread-19181-1-1.html

【黑镜子】Mike Hearn曝矿池仍然使用0.8版本,以收取较高的交易手续费。“实际上目前挖矿因为矿池的存在并没有竞争,因为似乎控制矿池的数十人达成了一致,不允许较低的手续费,因为手续费是他们收入的重要来源。” "但绝大部分原因在于已经支离破碎的交易费市场" -- 详戳: http://bbs.btcman.com/forum.php?mod=viewthread&tid=19198&fromuid=4242

GHash.IO:我们永远不会发动51%攻击 http://www.coindesk.com/ghash-io-never-launch-51-attack/ http://www.8btc.com/ghash-io-never-launch-51-attack

  • 全部
  • 最佳
  • 3122365857 船员 船龄 6.8年 2015-11-06 19:18:08
    希望不会有人这样干,我的算力本来就少得可怜。
  • kwl01skz 船员 船龄 8.7年 2014-10-11 19:33:35
    http://8btc.com/data/attachment/forum/201408/01/080838cb84i4v4248vi4v2.png
    图:相同时间内,诚实矿工挖出10个块,恶意矿工挖出15个块,这种情况有可能发生,但是二项分布公式会报错,因为它没有考虑这种情况。
  • kwl01skz 船员 船龄 8.7年 2014-10-11 19:21:00
    二项分布是不准确的。
  • 极乐净土 水手 船龄 7.8年 2014-10-11 13:04:50
    总体来说 是攻击者和诚实者在竞争, 但诚实者和诚实者也是在竞争的,
    在诚实链条上高度H0的块被签名出来后,所有的诚实者展开挖矿竞争,当有人发现H1高度的块的时候,其他诚实者的竞争者已经的计算的算力都作废了,再次在H1高度继续挖矿。这样诚实者的算力是不是浪费了。
登录 账号发表你的看法,还没有账号?立即免费 注册
推荐教程
换一批