タングル図解 パート3:累積荷重と荷重ランダムウォーク

補足説明
この記事は原題『The Tangle: an Illustrated Introduction Part 3』の翻訳です。
ご参考までに公開します。必要だと思われる部分には言葉や構成を補っています。
トップ画像は『The Tangle: an Illustrated Introduction Part 3』より引用しております。

投稿者:Alon Gal
投稿日:2018年02月15日

前回は非荷重ランダムウォークについて学びました。今回はより高度な従兄(いとこ)のような荷重ランダムウォークについて学んでいきます。

最初に荷重ランダムウォークを勉強する動機付けから始めましょう。チップ選択アルゴリズムに行ってもらいたいことの一つは、怠惰な(lazy)チップたちを避けることです。怠惰なチップとは、新たなトランザクションではなく古いトランザクションを承認するチップのことです。「怠惰」という理由は、タングルの最新の状況を追い続けることなく、古いデータに基づいて自身のトランザクションをブロードキャスト(訳注:不特定多数の相手に向けて自身の取引データを送信すること)するだけだからです。これでは全く新しいトランザクションが確定され(confirmed)ないので、ネットワークの役に立ちません。

上の例では、14番のトランザクションが怠惰なチップです。非常に古いトランザクションを承認しています。もし一様ランダムチップ選択アルゴリズムが用いられたら、14番のトランザクションは他のチップ同様に承認される可能性があり、まったく罰を受けていない状態となります。非荷重ランダムウオークが使われたら、少なくともこの特殊な例では、このような悪い行動があたかも良いことかのように奨励すらされます。

この問題にどのように対処したらいいでしょう?新たなトランザクションだけを承認するように強制することは出来ません。非中央集権(decentralization)の考えと相容れないからです。トランザクションは、誰であれ自分が好きな相手を承認できます。またいつ新しいトランザクションが到達したかを正確に伝える確実な方法もなく、そのようなルールを押し付けることもできません。私たちの解決策は、そのような悪い行動を阻止するようなインセンティブが内蔵されたシステムを構築して、怠惰なチップが誰にも承認されないようにする、という方法です。

私たちは戦略としてランダムウォークを偏らせることによって、怠惰なチップたちが選ばれにくくなるようにします。各トランザクションの重要度を示すために累積荷重という用語が使われます。累積荷重の定義は非常に簡単です。各トランザクションにいくつの承認者がいるかを数えて、最後に1を足します。直接的な承認者と間接的な承認者のどちらも数に入れます。下の例では、3番のトランザクションは、自分を承認するトランザクションが4つ(5番は直接的な承認者、7番と8番と10番は間接的な承認者)ので、累積荷重は5となります。

どうしてこれが上手くいくのでしょうか?別の怠惰なチップのケースを見てみましょう。下の例では16番のトランザクションが怠惰なチップです。16番が承認されるためには、ランダムウォーカーは7番のトランザクションに到着してから9番ではなく16番のトランザクションを選ばなくてはなりませんが、そうなる可能性は低いです。なぜなら16番のトランザクションの累積荷重は1なのに対して、9番のトランザクションの累積荷重は7だからです。これは怠惰な行動を阻止する効果的な方法です。

ここで「そもそも無作為性(ランダムであること)って必要あるの?」と疑問に思うかもしれません。各分岐点で、いかなる蓋然性も関与させることなく最も重たい累積荷重のあるトランザクションを選ぶ、という”超”荷重ランダムウォークを創作すると、次のようなものができます。

”超”荷重ウオーク。一番荷重の重いトランザクションに向かってウォーク(歩行)して行く。
The Tangle: an Illustrated Introduction Part 3』より引用

灰色の四角は承認者がゼロのチップです。そのようなチップがいくつか図の右端にあることは正常なことですが、タイムライン全体にたくさん広がっている場合は問題です。そのようなチップは取り残されたトランザクションで、決して承認されることはありません。これはウォーク(歩行)を偏らせすぎた場合のマイナス面です。あらゆる時点で荷重の一番重たいトランザクションだけを選び続けたら、チップのほとんどが決して承認されなくなります。承認されたトランザクションだけが中央に通路のように連なって、忘れられたチップはサイドラインに取り残されます。

所与の分岐点から任意の承認者に向かってウォーク(歩行)していく可能性を決定する手段が必要ですが、より荷重の重たいトランザクションに何らかの偏りを与えて、その偏りがどのくらい強いかをコントロールするパラメーターがある限りは、私たちが選ぶそのための厳密な式は重要ではありません。ここで新しいパラメーター\(\alpha\)を導入します。\(\alpha\)はトランザクションの累積荷重がどのくらい重要かを設定します。その厳密な定義はホワイトペーパーにあります。もし希望があれば、もっと詳しい内容を書いて記事にするかもしれません。

荷重ランダムウォーク:青いトランザクションには累積荷重の値と次のステップとして選ばれる可能性が表示される。
The Tangle: an Illustrated Introduction Part 3』より引用

もし\(\alpha\)をゼロに設定すると、非荷重ウォークに逆戻りです。\(\alpha\)の値を非常に高くすると、超荷重ウォークとなります。両方の間に、怠惰な行動を罰しながらも、あまり多くのチップが取り残されることもない、というほど良いバランスが見つかります。理想的な\(\alpha\)の値の決定はIOTAの中で重要な研究課題です。

ランダムウォークの各ステップの可能性を決めるルールを設定する方法は、マルコフ連鎖モンテカルロ法、あるいはMCMC法と呼ばれています。マルコフ連鎖では各々のステップは先行のステップに依拠しませんが、予め決められたルールに従います。

毎回のことですが、以上のアイデアを実際に見せてくれるシュミレーションがあります。\(\alpha\)と\(\lambda\)の値を弄り回して、どんな風に面白いタングルが出来上がるか見てみてください。来週は「トランザクションAがトランザクションBを承認するとはどういうことなのか」ということの意味について詳しく述べて、「いつトランザクションが確定された(confirmed)と見なされるのか」を明確にします。

パート1:タングルの紹介
パート2:新しいトランザクションの到着率と遅延時間とランダムウォーク
パート4:承認者と残高(バランス)と二重支払い
パート5:コンセンサスと確定の信頼度とコーディネーター

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です