白皮书

双花攻击

Tangle白皮书讲述了两种双花攻击方式：

• 寄生链攻击
• 大权重区块攻击

过程如下：

1. 攻击者付钱购买商品，然后商家等待该交易累积足够的权重，则给攻击者发货
2. 攻击者在付钱的同时，开始在暗地里用自己的算力来支持双花交易，待商家发货的时候且确认自己在tips选择规则上有优势时，广播支持双花交易的寄生链/大权重双花交易
3. 根据tips选择的规则，攻击者拥有优势，则双花交易的寄生链/大权重双花交易会被后面新来的交易所引用（支持），那么双花交易被全网认可，而原交易失效。最终，商户没收到钱，但把商品发给交易者了。

寄生链攻击

思考寄生链的问题本质上是思考，网络认可的主链的标准是怎么样的？

• 平等对待所有的tips，即每个tips被选择的概率相同
• 最长链上的tips更应该被选择

但上述两个标准都不能解决寄生链问题，对于寄生链，可以在末端无成本地添加任意个数的tips，同时寄生链可以弄得任意长。

而Tangle在解决这个问题得过程中，网络认可得主链标准为累计算力，即如果tips支持得链路累计的算力越大，这条链路更值得支持。这一点体现在游走算法中。

游走算法

1. 考虑累计权重在[W, 2W]之间的交易，W是一个足够大的值
2. 从步骤1中的交易中随机选择N个交易，分别作为N次游走的起点
3. 每次游走从x->y，从高累计权重走到tips。若x->y为可能，则说明y支持x。转移概率( $H_i$为交易i的累计权重)如下：
   $P(x->y) = \frac{exp(-a(H_x-H_y))}{\sum_{z:x->z}{exp(-a(H_x-H_y))}}$
4. 必存在最先到达tip的两条路径，选择该两条路径对应的两个tips作为新交易支持的对象（注：必须舍弃路径太短，太快的结果，因为很有可能是Lazy Tips，下文会说明）

游走算法解决了寄生链的问题

在主网和寄生链分叉的地方，随机游走需要选择下一站，是主网的交易y1还是寄生链的交易y2。已知 $H_{y1}>H_{y2}$，所以 $H_x-H_{y1}<H_x-H_{y2}$，通过exp放大差异，所以 $exp(-a(H_x-H_{y1}))>>exp(-a(H_x-H_{y2}))$，所以寄生链被选择的概率很小。
$P(x->y) = \frac{exp(-a(H_x-H_y))}{\sum_{z:x->z}{exp(-a(H_x-H_y))}}$

游走算法同时解决了Lazy Tips问题

在Tangle中每笔交易在发出时理论上要选择2个tips（tip指的是在交易发起者视野中从未被人支持过的交易）去支持的，但支持的过程需要验证整个交易流的合法性，比较浪费时间。

因此，有的交易的发起者会选择两个累计权重足够大的交易进行支持（Tangle不能强制让你去支持tips，因为网络是异步的，不能确认交易发起者的视野）。因为累计权重大的交易已经被网络很大程度确认了，就不需要浪费时间确认其合法性，但这样不利于整个网络（累计权重轻的tips总需要有人去验证确认）。这些直接支持“老交易”的新交易成为Lazy Tips。

游走算法必须保证这些Lazy Tips不会被游走算法所选择，即不能平等对待这些Tips。

同上“游走算法解决了寄生链的问题”， $P(x->y_{lazy}) << P(x->y_{normal})$

a的取值

a的取值决定了 $H_x$与 $H_y$差异的放大程度
$P(x->y) = \frac{exp(-a(H_x-H_y))}{\sum_{z:x->z}{exp(-a(H_x-H_y))}}$

当a足够大时，游走路径变得不那么随机。此时若 $H_{y1}$稍稍大于 $H_{y2}$，但因为a的放大作用，最后游走时以绝对的概率选择y1，这不是我们想要的。为什么？想象以下，在某个时刻的每笔交易选择tips的过程中，游走的路径都一样。首先这笔交易两个都引用了相同的tips，然后再同一时刻不同交易都引用了相同的tips，那么tips的数量会很多很多（消除了一个，新增了约为 $\lambda$那么多个），tips的数量不收敛是个很大的问题

关于游走算法的其他问题

会不会存在这样的问题，交易为了自己的交易第一次被确认快一些，可能会分析整个Dag，得到tip被选中的概率分布，然后选择概率最大的tip。首先，如果每个人都这么做就会发生类似a取值太大的问题。

然而，怎么去避免这个问题，可以改变游走的方式，让路径可以以一定概率向上回溯。然后，怎么才算解决了这个问题呢？当你要统计某个时刻的tips的分布所需要的时间远大于游走所需要的时间，那么当统计完分布后，tips的情况已经改变了，因为同一时刻的采用游走的交易已经接入了，形成的新的tips。

大权重区块攻击

寄生链的问题采用了累计权重为标准进行tips的选择。但是，我们有没有想过累计权重这个东西是否靠谱，引申到权重是否靠谱？

在比特币采用的是最长链标准，即一个交易被越多的区块所引用，那么这个交易被回滚的概率就会越小。所以，比特币中有六区块确认说法。

然后，在Tangle中我们采用累计权重的标准。那么同理，一个交易的累计权重越大，那么其越难被回滚吗？一个很反直觉的结果，就是不是这样的。这里用到的是大权重攻击，下面回从数学上分析，为什么其结果与比特币的不同。

引入数学基础

• 泊松分布
  $P(N(t) = n)=\frac{(\lambda t)^{n}exp(-\lambda t)}{n!}$
  上述公示表述的是N(t)服从参数为 $\lambda t$的泊松分布，物理意义为，在时间t的到来了n个客人的概率，而期望为 $\lambda t$与方差为 $\lambda t$，即单位时间流入的客人数为 $\lambda$。
• 指数分布
  $P(X \leq t)=1-P(N(t)=0)=1-exp(-\lambda t)$
  上述公式表述的是在时间t内有客人流入的概率。该分布概率密度指的是在时刻t流入一个客人的概率密度，为上述公式的导数。服从参数为 $\lambda$指数分布，期望(有1个客人流入的时间)为 $\frac{1}{\lambda}$与方差为 $\frac{1}{{\lambda}^2}$。
• 伽马分布
  $P(X_1+X_2+...+X_n \leq t) = 1-\sum_{i=0}^{n-1}P(N(t)=i)\\=1 - \sum_{i=0}^{n-1}\frac{(\lambda t)^{i}exp(-\lambda t)}{i!}$
  上述公式表述的是在时间t内有至少n个客人流入的概率。该分布概率密度服从参数为 $(n, \lambda)$的伽马分布，我们可以看出指数分布服从 $(1, \lambda)$的伽马分布。期望（有n个客人流入的时间）为 $\frac{n}{\lambda}$与方差为 $\frac{n}{{\lambda}^2}$。

大权重区块攻击成功的概率

假设用二进制：

1. $\mu$为攻击者算力， $\lambda$为正常算力
2. 一个难度为 $n_0$的区块相当于工作量为 $2^{n_0}$一个难度为 $n_0$的区块相当于工作量为 $2^{n_0}$。
3. 攻击者挖到至少一个难度为 $n_0$的区块所用的期望时间取 $\frac{2^{n_0}}{\mu}$
4. 攻击者挖到至少一个难度为 $n_0$的区块所用的时间服从参数为 $\frac{\mu}{2^{n_0}}$的指数分布

怎么定义攻击成功？就是商家在交易的累计难度为 $n_0$时（时间为 $t_0$），攻击者能够产生难度不小于 $n_0$的区块。其中 $W^{n_0}$为攻击者生成难度为 $n_0$所需要的时间。我们可以计算攻击成功的概率：
$E(t_0)=\frac{2^{n_0}}{\lambda} \qquad (1)$
$P(W^{n_0}<t_0)=1-exp(-t_0 \mu2^{-n_0})\qquad (2)$
我们采用 $t_0$为其期望，即把(1)带入(2)得到
$P(W^{n_0}<t_0)=1-exp(-\frac{\mu}{\lambda})\approx\frac{\mu}{\lambda}\qquad (3)$

分析(3)我们可以得知攻击成功的概率只与(攻击者算力/诚实者算力)有关，与等待时常 $t_0$和累计难度 $2^{n_0}$都没有关系。这说明了什么？不像比特币你等待越久，越多的区块支持你，你的交易越难被回滚。在Tangle中，无论你的累计难度有多高等待时常有多长，都不代表你交易被回滚的概率越小，这个概率时常数，只与算力比有关。

因此，Tangle需要限制某个区块的难度大小，这样相当于退化到比特币的模型，攻击者最好的方法都是一直生产上线难度的区块。

比特币模型到底有什么不同

在比特币双花攻击成功概率一文的分析方法是和白皮书的方法同出一源，可能看不出端倪，我们现在从另外的角度审视比特币。

上面大区块攻击的分析中，相当于分析比特币双花攻击成功概率一文中的第二部分，即直接考虑谁的累计难度大，而没有考虑第一部分中攻击者累计权重小但最后能追上诚实者的概率。所以对于比特币我们也直接分析第二部分。

其实比特币的n确认机制相当于，诚实算力生产了n个区块，而攻击者（算力小于诚实者）也生产了n个区块的概率会差不多指数下降，所以等的n越大，那么就越安全。

这里设 $n_0$为比特币区块的难度要求，商家采用 $n$确认机制，共用时也是 $t_0$，则被攻击成功的概率为 $P(W_{1}^{n_0} + W_{2}^{n_0}+...+W_{n}^{n_0}<t_0)$，满足参数为 $(n,\frac{\mu}{2^{n_0}})$的伽马分布，所以攻击成功的概率为
$P(攻击成功)=1 - \sum_{i=0}^{n-1}\frac{(\frac{\mu}{2^{n_0}} t_0)^{i}exp(-\frac{\mu}{2^{n_0}} t_0)}{i!}$

同理因为 $E(t_0)=n\frac{2^{n_0}}{\lambda}$，取 $t_0$为其期望，所以
$P(攻击成功)=1 - \sum_{i=0}^{n-1}\frac{(\frac{\mu}{\lambda} n)^{i}exp(-\frac{\mu}{\lambda} n)}{i!}$

下面截图为z确认 $P(攻击成功)$的值，可以看出随着z的增大，攻击成功的概率几乎是指数下降的。

分析

综上，我们可以思考本质的问题是什么，其实就是靠累计得到的难度是线性的，而只挖一个难度大的可以抵消这种线性累计（这个跟指数分布这个东西有关）。所以，只要限制好大区块的大小，理论上tangle也是能够获得类似比特币的安全性。

更多精彩内容