本系列文章，翻译自IOTA的官方博客
在上一篇中，我们知道了无权重随机漫步算法，今天我们将介绍下一个高级点的：有权重随机漫步算法。
我们为什么要研究它呢？其中一个原因是，我们希望我们的tip选择算法能够避免惰性tips的出现。所谓惰性tip，是指那些验证了旧的交易而没有验证新交易的tip。说它懒是因为它不愿意更新到缠结的最新状态，而只是把它基于旧数据的交易广播出去，如果每个交易都懒，那就不会有新的交易被确认，对整个网络不利。
ex1.png
在上面的这个例子中，交易14是一个惰性tip，它验证了非常旧的交易。如果我们采用无权重随机漫步算法，交易14会像其他的交易一样被选择，它就没有被惩罚。
我们该如何解决这个问题呢？首先一条，我们不能强制参与者只验证最近的交易，因为这与去中心化的思想相冲突，应该允许交易验证任何一个交易。我们也无法找到一个可靠的方法来准确的预知每个交易什么时候到来。我们的解决方法是，构建一个激励系统，使得惰性交易难以被其他交易所验证。
我们的方案是什么呢？我们先引入一次概念：累积权重(cumulative weight)，用它来代表一个交易的重要性。累积权重的定义非常简单：计算一个交易的验证者个数，然后加1。我们需要找出一个交易的所有直接验证者和间接验证者。在下面的例子中，交易3的累积权重是5，因为它有四个验证者(直接验证者5,间接验证者7,8,10)。
cumulative-weight-1.png
为什么这种方法可行呢？让我们来看另一个惰性tip的例子。如下图所示，交易16是一个惰性tip。如果16号交易能被验证，那么随机漫步者就需要走到交易7，然后选择16而不选择9。但是，这不可能发生，因为16号交易的累积权重是1，而交易9的累积权重是7！这种真是一个抑制惰性行为的高效方法。
cumulative-weight-2.png
此时你可能会问，我们是不是可以完全去掉随机性。我们可以发明一个完全权重漫步者，在任何结点，我们都选择最大权重的那个交易，不存在任何随机可能。这样的话，我们将会得到这样的东西：
cumulative-weight-3.png
灰色的方块是tips，没有任何验证者。正常情况下，tips应该分布在右边，所以，有这么多tips散落在时间轴上，是很有问题的。那些左边的tips，将永远不会被验证。所以如果太依赖于权重就会有问题。
于是，我们需要一个方法来定义我们有多想漫步到一个给定的验证者。我们选择的具体的公式其实不重要，只要我们倾向于权重高的交易，同时有一个参数来控制这种倾向性的强度，就可以了。如此就引入一个参数\alpha，它代表一个交易的累积权重有多重要。白皮书中有它的准确定义，这里先不关心了。
cumulative-4.png
如果我们设置\alpha为0，我们就变成了无权重漫步。如果设置\alpha为一个很大的值，我们就变成了完全权重漫步。在二者之间，我们可以找到一个好的平衡点，既能惩罚懒惰行为又不会留下太多tips。确定一个理想的\alpha值，是IOTA的一个重要研究课题。
这种给随机漫步中每一步都确定一个可能性的方法，就叫做马尔可夫链蒙特卡洛方法(简称MCMC)。在一个马尔可夫链中，每一步都不依赖于前面一步，而是跟着一个事前确定好的规则走。向之前一样，我们也做一个仿真程序。
我们建议你玩一玩这个仿真程序，改变一下\alpha和\lambda，然后看看你能弄出什么有意思的缠结。下篇文章，我们将会详细介绍交易验证是什么意思，以及如何确定一个交易处于被确认状态。
网友评论