Part 3: Cumulative weights and w

在part2中，我们学习了unweighted random walk选择算法。本章节，我们将学习更高级的变形算法：the weighted random walk。

算法the weighted random walk的其中一个核心作用是避免lazy tips 被选择认证。这里，lazy tips 的定义为，新加入的交易在选择tangle 中的交易认证时，选择一个旧的交易认证，而不是选择最近的tip 交易认证。一方面，我们知道，一笔交易只有被认证了，才会对tangle 的状态作出变更，并将该笔被认证的交易进行网络广播，然后在由别的tangle 节点进行状态变更。换言之，如果一笔新交易选择了一笔旧交易（已经被认证过）再次进行认证，虽然说，旧交易能被认证成功，但该交易已经被执行状态变更，因此，该就交易不会在二次变更。这样一来，不仅没有新的tip 交易被认证，而且对于整体的tangle 网络来说也不会有一点帮助。

图1-1

在图1-1 的例子中，交易14 则被认为时lazy tip,因为它选择了交易1 和交易 3 两笔已经被认证过的交易再次进行认证。如果我们使用的是uniform random 的tip 选择算法，交易14 同样可能不会被选择。同样，在part2 所介绍的 unweighted walk算法会有同样的问题，甚至会更严重，因为根据unweighted walk选择算法，在游历者选择过程中，不管是 tip 交易还是非tip 交易，它的选择概率是一致的，但游历者是从genesis 交易开始选择，换言之，lazy tip的出现概率会大于uniform random 算法。

那么，如何来处理lazy tip 所带来的问题？在提出解决方案前，这里可以明确的是，我们无法强制任何的交易去选择较新的tip，因为这会与去中心化的理念想违背。相反，任何新交易都可以自愿选择tangle 中的任意一笔交易进行认证。另外，我们也不能提供一个自认为可靠的规则去强制新到来交易进行选择认证。

我们的解决方案是通过一种系统内置的激励行为，带权重的随机游历，即the weighted random walk来尽量避免lazy tip 被选择。具体的策略是，每一笔交易都会一个累计权重( term cumulative weight)来指明自身的重要性。累计权重的定义非常简单：统计直接或间接证明该交易的交易数即可。例如图1-2 的例子中，交易[3] 的累计权重为5(交易[5] 为直接认证交易，交易[7]、[8]、[10]为间接认证一共为4，但计算时，都会加上自身，则为5)。

图1-2

我们在通过图1-3 的例子来阐述为什么该算法可以有效的避免lazy tip 被选择。根据定义，交易[16]为lazy tip。如果交易[16]被选择，前提条件时游历者必须游历到交易[7],因此，会面临 交易[9] 以及交易[16] 两个选择，而交易[9] 的累计权重为7，远大于交易[16]的累计权重1，因此，交易[9]会大概率被选择并进行移动，而交易[16] 基本不可能被选择。这样一来，则可以避免lazy tip 被选择认证。

图1-3

这时，我们会有个疑问：the weighted random walk 中的随机性还需要吗？因此，我们提出一种变形算法the super-weighted random walk。该算法的核心则是在the weighted random walk的基础上进行调整。即在路径选定过程中完全按照累计权重因素，不涉及任何概率运算。按照新变形的算法，tangle 的图形会大致演变成图1-4。

图1-4

从图4-1的例子中，我们可以看出如果，整个tangle 网络一直使用the super-weighted random walk算法，walker 只往权重大的交易游历，这样一来会带来新的问题，会有大量的交易将永远无法被选择认证。

为了尽量规避the super-weighted random walk算法所引伸出的问题。我们提出了另一个解决方案。回想一下，the super-weighted random walk仅通过权重因素来精确得出walker 交易选择路径，但细想一下，我们无需这么精确，我们只需尽量偏向权重高的交易即可。所以，我们引进一个新的参数α。参数α 意味着偏向累积权重的重要性。精确的定义可在白皮书中查看，当然这篇文章 也从数学角度给出准确的定义。

图1-5

虽然说白皮书有详尽的定义，但还是来概要说明一下该参数的具体含义。如果我们设定参数α 值为0，则意味着该算法会回退成unweighted walk。反之，如果α 的值特别高，算法则会进化成 super-weighted walk。因此，我们需要寻找一个相对平衡的值，来确保既可以尽量避免lazy tip 被选择，也可以尽量避免tip 永不被选择的情况出现。而 确认一个理想的α 值是IOTA 一个重要的研究课题。

具体的方式是通过设定一种指定的规则，在该规则下，使得walker在随机游历过程中的每一步，都可以计算出具体的概率。该规则称为马尔可夫链蒙特卡罗技术（ Markov Chain Monte Carlo，简称MCMC）。在马尔可夫链中，下一步的概率计算不依赖于前一步，而是遵循预先确定的规则。

图1-6

到这里，本文完毕。我们将在下意章节中，详细讲解 一笔交易认证 另一笔交易是什么含义，并且 进一步了解何时可以确认一笔交易。