Tangle:図解入りの紹介 第三回:累積重みと重み付きランダムウォーク

Translate this article into English

シェアする

前回は重みなしランダムウォークについて説明しましたが、今回はより高度な重み付きランダムウォークについて学びます。

重み付きランダムウォークを学ぶ理由から説明しましょう。私たちのチップ選択アルゴリズムに望むことは怠け者チップを選ばないことです。怠け者チップとは最近の取引ではなく古い取引を選ぶチップのことです。怠け者と呼ぶ理由はtangleを最新の状態に保とうとせず、古いデータに基づく取引だけを広めるからです。これでは新しい取引が承認されないので、ネットワークのためにはなりません。

上図の例では、取引14は怠け者チップで、とても古い取引を承認しています。もし一様ランダムチップ選択アルゴリズムを使うと、取引14は他の取引と同じようにおそらく承認されるので、ペナルティを受けることはまったくありません。重みなしランダムウォークを使うことは、少なくともこの特別な例ではこのような悪い振る舞いを促すことになります。

この問題にどう対処すればいいでしょうか? 最近の取引だけを承認するよう強制することは分散化の構想と調和しないので不可能です。取引はその取引が認めたものを承認します。各取引がいつ発生したかを正確に知る確実な方法もないので、この方法を強制することはできません。

私たちのソリューションは古い取引を承認するような振る舞いに対抗するインセンティブの仕組み持つシステムを構築することなので、私たちのシステムでは怠け者チップは誰からも承認されないことになります。

私たちの戦略はランダムウォークにバイアスをかけることなので、怠け者チップが選ばれる可能性は低くなります。ここで取引の重要さを示す用語として累積重み(Cumulative Weight)という言葉を使うことにします。累積重みの定義はとても簡単です。ある取引を承認する取引の数を数え、それに1を加えます。直接、間接両方の承認者を数えます。下図の例では、取引3は自分を承認する取引が4つあるので累積重みが5となります(取引5は直接、取引7、8、10は間接)。

なぜこの方法がうまくいくのでしょうか? 怠け者チップの別の状況を見てみましょう。下図の例で、取引16は怠け者チップです。この取引16が承認されるためには、ランダムウォーカーは取引7に到達し、その後取引9を経由して取引16を選ばなければなりません。しかし、このような状況が起こる可能性は低いです。なぜなら取引16の累積重みは1で、取引9の累積重みは7だからです! この方法は怠け者チップを阻止するのに有効です。

ここで次のような質問があるかもしれません。ランダムさは必要にならないでしょうか? 各接続点で確率的な要素は考慮せずにもっとも重みの大きい取引を選ぶという超重み付けランダムウォークを発明することもできます。すると状況は下図のようになります。


超重み付けランダムウォーク。常にもっとも重みの大きい取引が選ばれる

灰色の四角形はどの取引からも承認されていないチップです。図の右端にチップがあるのは普通のことですが、時系列に沿ってこれだけ多くのチップが広がっているのは問題です。これらのチップは放っておかれたチップで今後も承認されることはありません。

この状況はバイアスをかけ過ぎたことによる不都合な点です。どの接続点でももっとも重みの大きい取引を選ぶことを強制すると、チップの大多数は決して承認されないでしょう。承認された取引が中央回廊のように残り、忘れられたチップは脇に追いやられます。

私たちには、ある接続点で特定の承認取引に向かう起こりやすさを定義する方法が必要です。重みの大きい取引にバイアスを与え、このバイアスの強さを操作するパラメータがあれば、式の正確な形は重要ではありません。そのため、取引の累積重みの重要さを設定するパラメータαを新たに導入します。正確な定義はホワイトペーパーに記載されていますが、要望があれば今後の投稿で詳しく説明します。


重み付けランダムウォーク:青色の取引の数字は累積重みと次のウォークで選ばれる確率を表す

αをゼロにすると重みなしウォークに戻ります。αに非常に大きな値を設定すると超重み付けウォークになります。怠け者の振る舞いを罰することと、放っておかれるチップが多くなりすぎないようにすることの間に、ちょうどいいαの値を見つけることができます。理想的なαの値を決定することはIOTAの重要な研究テーマです。

ランダムウォークの各ステップで確率を決める規則を定める方法はマルコフ連鎖モンテカルロ法、またはMCMC法と呼ばれます。マルコフ連鎖では各ステップは以前のステップに左右されず、あらかじめ決められた規則に従います。

いつものように今回の新しいアイディアを実証するシミュレーションをご紹介します。αとλの値を変えたときにどのような面白いtangleができ上がるか試してみてください。次回は、取引Aが取引Bを承認するとはどういうことかを詳しく説明し、取引が承認されたと考えられるのはいつなのかを定義します。

新しいIoTの技術を使っているIOTAは、今後IoT化が進むにつれて注目に値する通貨です。どのような特徴を備え、決算が行われていくのかを解説しています。また最近のニュースから、MIOTAの今後の可能性についても考察しています。

The Tangle: an illustrated introduction, Part 3: Cumulative weights and weighted random walks