区块链技术博客
www.b2bchain.cn

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

第24983篇文章邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击,说明解释了邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击,是很好的区块链入门技术文章网站,提供了相应的代码的进行解释,并且把原理说的很清晰

来源:链闻ChainNews (ID:chainnewscom)

作者:邹传伟

中本聪在比特币白皮书技术部分(第 6-9 页)讨论了比特币分布式账本面对双花攻击的安全问题,核心是诚实节点和恶意节点在挖矿中的竞争。这部分内容非常重要,但中本聪的表述非常简略,省去了关键论证过程。区块链行业中有专家对这部分内容做了说明,但都存在一些疏漏之处。本文在前人工作的基础上,试图给出一个严谨解析。

比特币挖矿的数学过程

比特币挖矿的本质上通过不断运行哈希计算,以找出一个符合要求的 Nonce,使其前若干位等于 0。如果将 Nonce 视为一个十六进制小数,那么其可以视为一个在 0 和 1 之间均匀分布的随机变量,合格 Nonce 需小于α(如果要求 Nonce 前β位等于 0,那么α=2-β)。α由比特币算法根据全网算力调整。

用Η表示全网算力,含义是每秒可运行哈希计算的次数。用随机变量τ表示找到合格 Nonce 的时点,τ是概率论上的停时概念。因为不同次哈希计算的结果相互独立,所以对任意 t>0,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

因此,随机变量τ的累积概率分布函数等于

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(1) 表示参数为-ln(1-α)Η的指数分布。根据指数分布的性质,找到一个合格区块的平均时间为

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

用 T 表示平均出块时间(即 10 分钟)。那么,存在如下关系

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(2) 就是比特币的难度系数调整机制。

诚实节点与恶意节点之间的挖矿竞争

假设全网算力 H 不变,诚实节点与恶意节点的算力分别为 Hg和 Hb,H=Hg+Hb。它们找到合格区块的时间分别为τg和τb。根据前文的分析,和均服从指数分布,参数分别是

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

诚实节点先找到合格区块的概率是

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

同理,恶意节点先找到合规区块的概率是

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(3) 和 (4) 说明,先找到合规区块的概率与算力成正比。

恶意节点从落后追赶诚实节点的问题

假设全网算力 H、诚实节点的算力 Hg和恶意节点的算力 Hb均保持不变。假设恶意节点落后诚实节点个区块,接下来考虑恶意节点赶上诚实节点的概率。站在恶意节点的角度,引入如下计数函数

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

其中,-z 表示初始时恶意节点落后诚实节点 z 个区块。Ii(τb<τg) 表示第 i 个合格区块是否由恶意节点生成。若是,则 L(n) 增加 1;否则,L(n) 减少 1。换言之,L(n) 刻画了在 n 个区块后,恶意节点领先于诚实节点的区块数量(小于 0 则表示恶意节点落后于诚实节点的区块数量)。

恶意节点与诚实节点之间开展的是「最长链竞争」。用 qz表示恶意节点赶上诚实节点的概率,数学表述是:

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(6) 的含义是,恶意节点从落后 z 个区块出发,能超越诚实节点 1 个区块的概率。

考虑第 1 个区块的情况(i=1)。如果这个区块由恶意节点生成,则恶意节点领先于诚实节点的区块数量变为-z+1,此情形的概率为 Pr(τb<τg)=q;反之,这个区块由诚实节点生成,恶意节点领先于诚实节点的区块数量变为-z-1,此情形的概率为 Pr(τb>τg)=p。因此,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

另外,q-1=1。但仅凭 (7) 和这个边界条件不足以求解,需要将这个问题转换为「赌徒破产」问题(Gambler’s Ruin Problem)。

假设恶意节点在落后诚实节点 N 个区块后放弃追赶(N 是一个很大的正整数),恶意节点在超越诚实节点 1 个区块后赢得「最长链竞争」。这两种情况都对应着「最长链竞争」停止,表示成「赌徒破产」问题是:

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

其中, τc也是概率论上的停时概念,L( τc)=-1 表示恶意节点赢得「最长链竞争」,L( τc)=-N 表示恶意节点退出「最长链竞争」。此时,(6) 等价于

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(7) 仍然成立,但有两个边界条件:

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(7) 可以等价表述为,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

也就是

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

迭代可知,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

将上述迭代结果累加起来可得,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(12)

考虑边界条件 (10),存在两种情况。

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

第一,q>p (也就是恶意节点占优)。因为 q/p>1,所以

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

第二,q<p (也就是诚实节点占优)。因为 q/p<1,所以

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

(二) p=q=0.5

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

在上述求解过程中,N->∞的含义是恶意节点为了赢得「最长链竞争」可以容忍任何大的成本。这当然是一个过于理想化的假设,只考虑了恶意节点从落后追赶诚实节点在技术上的可行性。实际上,恶意节点会衡量追赶的成本和收益,在很多情况下成本超过收益,说明追赶即使在技术上可行,在经济学上不可行。这会为比特币分布式账本带来安全保障。

这就对应着比特币白皮书第 6 页给出的如下公式。需要说明的是,比特币白皮书讨论的是恶意节点从落后追平诚实节点的概率,而 (15) 给出的是恶意节点至少超过诚实节点 1 个区块的概率。

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

分布式账本面对双花攻击的安全性

这是比特币白皮书重点讨论的问题。此问题的关键是泊松过程与指数分布之间的关系。如果从任意时点开始统计区块生成数量,由此得到的计数过程就是泊松分布:

1、任意两个不重叠的时间段内区块生成数量是互相独立的随机变量;

2、在任意长度为的时间段内,区块生成数量服从泊松分布

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

换言之,在相邻两个区块之间的时间间隔服从参数为-ln(1-α)H 的指数分布时,与其对应的计数过程服从参数为-ln(1-α)H 的泊松过程。

在双花攻击中,假设交易发起者等待了 z 个区块。这些区块由诚实节点生成,对应的时间等于

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

假设恶意节点在这个时间段内在私下生成区块,累计生成区块生成数量 Z 服从泊松分布,参数等于

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

这对应着比特币白皮书第 7 页的如下公式:

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

根据泊松分布的定义,

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

在时 0<=Z<=z,恶意节点落后的区块数为 z-Z;在 Z>=z+1 时,恶意节点已完成双花攻击。因此,恶意节点双花成功的概率等于(只讨论 q<p 的情形)

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击

邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击 由www.b2bchain.cn 提供
文章整理自网络,只为个人学习与分享使用
链接地址https://www.b2bchain.cn/?p=24983

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 邹传伟:从数学角度深入论证比特币分布式账本如何应对双花攻击
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们