Hi 游客

更多精彩,请登录!

比特池塘 区块链前沿 正文
在比特币创始论文的第11章中存在这样一个问题,就是为什么这个分布的期望为lamda=z*(q/p)?5 `. H& Y, |2 G) O0 d
11. 计算
" Y2 D3 l9 z: G; A1 \% m# P" N& N设想如下场景:一个攻击者试图比诚实节点产生链条更快地制造替代性区块链。即便它达到了这一目的,但是整个系统也并非就此完全受制于攻击者的独断意志了,比方说凭空创造价值,或者掠夺本不属于攻击者的货币。这是因为节点将不会接受无效的交易,而诚实的节点永远不会接受一个包含了无效信息的区块。一个攻击者能做的,最多是更改他自己的交易信息,并试图拿回他刚刚付给别人的钱。! G# l6 t! p: {' O" T
诚实链条和攻击者链条之间的竞赛,可以用二叉树随机漫步(Binomial Random Walk)来描述。成功事件定义为诚实链条延长了一个区块,使其领先性+1,而失败事件则是攻击者的链条被延长了一个区块,使得差距-1。
/ `/ H- w9 A* b2 L攻击者成功填补某一既定差距的可能性,可以近似地看做赌徒破产问题(Gambler’s Ruin problem)。假定一个赌徒拥有无限的透支信用,然后开始进行潜在次数为无穷的赌博,试图填补上自己的亏空。那么我们可以计算他填补上亏空的概率,也就是该攻击者赶上诚实链条,如下所示[8] :. R8 i) i7 j3 U! L* w
  假定p>q,那么攻击成功的概率就因为区块数的增长而呈现指数化下降。由于概率是攻击者的敌人,如果他不能幸运且快速地获得成功,那么他获得成功的机会随着时间的流逝就变得愈发渺茫。那么我们考虑一个收款人需要等待多长时间,才能足够确信付款人已经难以更改交易了。我们假设付款人是一个支付攻击者,希望让收款人在一段时间内相信他已经付过款了,然后立即将支付的款项重新支付给自己。虽然收款人届时会发现这一点,但为时已晚。
7 R( C# n4 Z; n" G8 z. U2 d5 H6 _2 W# F收款人生成了新的一对密钥组合,然后只预留一个较短的时间将公钥发送给付款人。这将可以防止以下情况:付款人预先准备好一个区块链然后持续地对此区块进行运算,直到运气让他的区块链超越了诚实链条,方才立即执行支付。当此情形,只要交易一旦发出,攻击者就开始秘密地准备一条包含了该交易替代版本的平行链条。
0 e4 x1 D- x* }! g' l- P: S然后收款人将等待交易出现在首个区块中,然后在等到z个区块链接其后。此时,他仍然不能确切知道攻击者已经进展了多少个区块,但是假设诚实区块将耗费平均预期时间以产生一个区块,那么攻击者的潜在进展就是一个泊松分布,分布的期望值为:
% z/ }  Z+ @8 f2 v1 B. M3 V( v 当此情形,为了计算攻击者追赶上的概率,我们将攻击者取得进展区块数量的泊松分布的概率密度,乘以在该数量下攻击者依然能够追赶上的概率。
! ]+ E, e2 [- [; t0 |' E  0 ]6 J% K* p: A: u4 e* F
化为如下形式,避免对无限数列求和:
  v5 o9 r0 g4 b9 y8 ]! w* f% T$ k  
4 o* P0 _5 f$ a# `2 t) Z. k下边是我对这个问题的理解:1 y; W3 A! c4 a3 Z4 o
首先看一下什么是泊松分布:在《泊松分布的来源—公式推导—应用》一文中,作者提出
# S" w5 m' R; ^在一个特定时间内,某件事情会在任意时刻随机发生(前提是,每次发生都是独立的,且跟时间无关)。当我们把这个时间段分成非常小的时间片构成时,可以认为,每个时间片内,该事件可能发生,也可能不发生。几乎可以不考虑发生多于一次的情况(因为时间片可被分的足够小)。+ l0 b' h) T9 [7 e/ X! h
当时间片分的越小,该时间片内发生这个事件的概率 p 就会成正比的减少。即:特定时间段被分成的时间片数量 n 与每个时间片内事件发生的概率 p 的乘积 n*p 为一个常数。这个常数表示了该事件在指定时间段发生的频度。' ~) C6 }+ W7 A: e4 h% E  m% s& j
这句话应该就是解决问题的关键。回到比特币论文中,因为特定时间段为生成z个区块,这个时间段被分成了z个时间片,每个时间片中攻击者获取下一个区块的概率为q/p,所以根据上述所说这个常数(lamda)为时间片数量和每个时间片内时间发生的概率的乘积,即lamda = z*(q/p);4 T$ i4 A* w! ]4 G1 g' l2 e
接下来就是泊松公式推导:
' x; r) k3 m8 O/ v( n" k看这段时间内,指定事件恰好发生 i 次的概率是多少?代入上面推导出来的公式得到:
/ |6 }% E8 u7 a  j( L7 c       n * (n-1)... (n-i+1) / i! * p^i * (1-p) ^ (n-i) => np(np-p)...(np-ip+p) / i! * ((1-p) ^ (-1/p))^(-np) / (1-p) ^i, ~$ W9 c/ Q! I4 X2 K) b% C
       当 n 趋向无穷大时,p 趋向 0 。而此时 (1-p)^(-1/p) 趋向 e 。注:详细推导过程如下: x) Q. S4 M& C" N; ?
      上面这个公式可以划简为 lamda ^ i / i! * e ^ - lamda (lamda=n*p)
( l8 h; H" A" B; x! C, E      这个公式推导过程不复杂,耐心点一看就明白。而这个关于 i 的分布就是著名的泊松分布了。  
+ W  e- e- U  g# a) V& A$ O+ k) n7 N' `& f2 I
回到论文中既为
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

梦语曦曦s 初中生
  • 粉丝

    0

  • 关注

    0

  • 主题

    13