加载中…
个人资料
区块链的作坊
区块链的作坊
  • 博客等级:
  • 博客积分:0
  • 博客访问:31,240
  • 关注人气:9
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

比特币:一种点对点的电子现金系统(三)

(2017-05-22 19:06:19)
标签:

比特币

二叉树

merkle

区块链

作者:中本聪

转自:8btc.com巴比特

 

 

11. 计算

       设想如下场景:一个攻击者试图比诚实节点产生链条更快地制造替代性区块链。即便它达到了这一目的,但是整个系统也并非就此完全受制于攻击者的独断意志,比方说凭空创造价值,或者掠夺不属于攻击者的货币。这是因为节点将不会接受无效的交易,而诚实的节点永远不会接受一个包含了无效信息的区块。一个攻击者能做的,最多是更改他自己的交易信息,并试图拿回他刚刚付给别人的钱。

       诚实链条和攻击者链条之间的竞赛,可以用二叉树随机漫步(Binomial Random Walk)来描述。成功事件
成功事件定义为诚实链条延长了一个区块,使其领先性+1,而失败事件则是攻击者的链条被延长了一个区块,使得差距-1。

       攻击者成功填补某一既定差距的可能性,可以近似地看做赌徒破产问题(Gambler's Ruin problem)。假定一个赌徒拥有无限的透支信用,然后开始潜在次数为无穷的赌博,试图填补上自己的亏空。那么我们可以计算他填补上亏空的概率,也就是该攻击者赶上诚实链条,如下所示[8]:
       p=诚实节点制造出下一个节点的概率
       q=攻击者制造出下一个节点的概率
       qz=攻击者最终消弥了z个区块的落后差距

比特币:一种点对点的电子现金系统(三)

        假定p>q,那么攻击成功的概率就因为区块数的增长而呈现指数化下降。由于概率是攻击者的敌人,如果他不能幸运且快速地获得成功,那么他获得成功的机会隨着时间的流逝就变得愈发渺茫。我们考虑一个收款人需要等待多长时间,才能足够确信付款人已经难以更改交易了。我们假设付款人是一个支付攻击者,希望让收款人在一段时间内相信他已经付过款了,然后立即将支付的款项支付给自己。虽然收款人届时会发现这一点,但为时已晚。

        收款人生成了新的一对密钥组合发送给付款人。这将可以防止以下情况:付款人预先准备好一个区块链然后持续对此区块进行运算,直到运气让他的区块链超越了诚实链条,方才立即执行支付。当此情形只要交易一旦发出,攻击者就开始秘密地准备一条包含了该交易替代版本的平行链条。

        然后收款人将等待交易出现在首个区块中,然后等到z个区块链接其后。此时,他仍然不能确切地知道攻击者已经进展了多少个区块,但是假设诚实区块将耗费平均预期时间以产生一个区块,那么攻击者的进展就是一个泊松今布,分布的期望值为比特币:一种点对点的电子现金系统(三)

        当此情形,为了计算攻击者追赶上的概率,我们将攻击者取得进展区块数量的泊松分布的概率密度,乘以在该数量下攻击者依然能够赶上的概率。

比特币:一种点对点的电子现金系统(三)

化为如下形式。避免对无限数列求和:

比特币:一种点对点的电子现金系统(三)

写为如下C语言代码:

#include

double AttackerSuccessProbability(double q, int z)

{

   double p=1.0-q

  double lambda = z*(q/p);

  double sum = 1.0;

  int i, k;

  for (k=0; k<=z; k )

{

  double poison = exp(-lambda);

  for(i=1; i<=k; i )

  poison *= lambda/i;

  sum -= poisson * (1 -pow(q/p, z-k));

  }

    return sum;

}

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

当q=0.1时

z=0  P=1.0000000

z=1  P=0.2045873

z=2  P=0.0509779

z=3  P=0.0131722

z=4  P=0.0034552

z=5  P=0.0009137

z=6  P=0.0002428

z=7  P=0.0000647

z=8  P=0.0000173

z=9  P=0.0000046

z=10 P=0.0000012

当q=0.3时:

z=0 P=1.0000000

z=5 P=0.1773523

z=10 P=0.0416605

z=15 P=0.0101008

z=20 P=0.0024804

z=25 P=0.0006132

z=30 P=0.0001522

z=35 P=0.0000379

z=40 P=0.0000095
z=45 P=0.0000024

z=50 P=0.0000006

求解令P<0.1%的z值。

为使P<0.001,则:

q=0.10 z=5

1=0.15 z=8

q=0.20 z=11

q=0.25 z=15

q=0.30 z=24

q=0.35 z=41

q=0.40 z=89

q=0.45 z=340

12. 结论

       我们在此提出了一种不需要信用中介的电子支付系统。我们首先讨论了通常的电子货币的电子签名原理,虽然这种系统为所有权提供了强有力的控制,但是不足以防止双重支付。为了解决这个问题,我们提出了一种采用工作量证明机制的点对点网络来记录交易的公开信息,只要诚实的节点能够控制绝大多数的CPU计算能力,就能使得攻击者事实上难以改变交易记录。该网络的强健之处在于其结构上的简洁性。节点之间的工作大部分是彼此独立的,只需要很少的协同。每个节点都不需要明确自己的身份,由于交易信息的流动路径并无任何要求,所以只需要尽其最大努力传播即可。节点可以随时离开网络,而想重新加入网络也非常容易,因为只需要补充接收离开期间的工作量证明链条即可。节点通过自己的CPU计算力进行投票,表决他们对有效区块的确认,他们不断延长有效地区块链来表达自己的确认,并拒绝在无效的区块之后延长区块以表示拒绝。本框架包含了一个P2P电子货币系统所需要的全部规则和激励措施。

 

参考文献:

[1]W Dai(戴伟),a scheme for a group of untraceable digital pseudonyms to pay each other with   money and to enfocecontracts amongst themselves without outside help(一种能够借助电子假名在群体内部相互支付并迫使个体遵守规则且不需要外界协助的电子现金机制),“B-money”http://www.weidai.com/bmoney.txt,1998

[2]H. Massias, X.S.Avila, and J.-J.Quisquater,"Design of a secure timestamping service with minimal trucst requirements,"(在最小化信任的基础上设计一种时间戳服务器)In 20th Symposium on Information Theory in the Benelux, May 1999。

[3]S.Haber,W.S.Stornetta,"How to time-stamp a digital document,"(怎样为电子文件添加时间戳)In Journal of Cryptology, vol3, No.2, pages 99-111,1991.

[4]D.Bayer, S.Haber, W.S.Stornetta, "Improving the efficiency and reliability of digital time-stamping,"(提升电子时间戳的效率和可靠性)In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[5]S.Haber, W.S.Stornetta, "Secure names for bit-strings,"(比特字串的安全命名)In Proceeding of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997

[6]A.Back, "Hashcash-a denial of service counter-measure,"(哈希现金——拒绝服务式攻击的克制方法)http://www.hashcash.org/papers/hashcash.pdf, 2002.

[7]R.C.Merkle, "Protocols for public key cryptosystems"(公钥密码系统的协议)In Proc.1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.

[8]W.Feller,"An introduction to probability theory and its applications,"(概率学理论与应用导论)1957.

 

 

 

 

 

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有