05月21, 2018

Something About IOTA[02_The Tangle]

本文归纳总结了IOTA的核心结构Tangle及几种Tips的选择算法。

Tangle

IOTA的核心在于被称为缠结(Tangle)的数据结构,Tangle是一种特殊的有向图)结构。

alt

其中每一个方块(vertex)代表一个交易,当一个新交易加入Tangle时,该交易会先选择(依照不同的选择策略)Tangle中两笔交易来验证批准。未经批准的交易被称为Tip,如上图中的方块6。

Poisson Point Process

在现实交易的场景中,交易发生的频率不是恒定的,该现象可以用泊松点描述——用变量λ表示传入交易的速率。 还要引入一个变量h用来表示传入交易的“不可见”时间,用来模拟真实场景下,交易的准备与传播过程。

  • 当λ的值很小时,传入交易的频率很低,Tangle会形成一个链条。

alt

  • 当λ的值很大时,代表传入交易的频率变高,因为有变量的h存在,所以此时Tip都只能看见Tangle中最左侧的创世交易块(genesis)。

alt

Tip Selection Algorithm

Tip的选择算法是Tangle发展的关键因素。

The Unweighted Random Walk

无权重随机行走(the unweighted random walk) Alt text

该选择算法会从genesis开始向Tip移动,在每个交易向多个该交易证明者(approver)选择时,采取完全随机的选择策略,即对于每一个证明者的选择率是相同的。

The Weighted Random Walk

加权随机行走(the weighted random walk在完全随机选择的算法中会出现一种现象: alt

  • Lazy Tip 图中交易14因为随机选择指向了(证明批准)交易1与交易3,而从Tangle的横向时间维度可知这两笔交易发生在很久之前且并没有违反IOTA对新入交易的规定(选择两个Tip并证明),可其做法在当前时间对整个tangle的发展无意义,这种Tip被称为懒Tip。
  • 所以引入与The Unweighted Random Walk对应的选择算法 ##### The Weighted Random Walk来规避Lazy Tip的出现。 该算法引入累积权重( cumulative weight)这一概念来表示该交易的重要程度。 当前交易所有的批准者数量 + 1就为该交易的累计权重值,也就是当前交易的批准者越多该交易(与其之后的链上的所有交易)就越容易被选中。 alt
如图中交易3的累计权重 = 交易57810 = 4 + 1 = 5

alt 此时再回到同样的问题中去,上图中对于一个新入的交易在随机行走的过程中到达交易7时,此时Tip Selection面临两个选择——交易9(累计权重7) 或者 交易16(累计权重1),在加权随机游走的情况下会大概率走向交易9,从而淘汰Lazy Tip交易16。

The Weighted Random Walk将权重值与随机结合,权重值高的交易拥有更大概率的选中该可能,反之亦然。此种算法也是IOTA选择的Tip Selections算法,即马尔科夫链蒙特卡洛 (Markov Chain Monte Carlo)Alt text

The Super-weighted Random Walk

超级权重随机行走,该算法完全按照交易的积累权重行走,用来验证随机性行走的必要性。 alt 在该种算法下,随着时间的推进处于中层的高权重交易会越发的密集,上下两层遗留许多Tips被tangle抛弃。


参考:

  1. 《The Tangle: an illustrated introduction》p1-p3.

本文链接:https://check321.net/post/IOTA_02.html

-- EOF --

Comments

请在后台配置评论类型和相关的值。