カルダノの 処理能力を最大化する「インプット・エンドーサー」のすべて【超訳】

6月10日にIOGにより配信された、「Ouroboros-Leios」の解説動画を全文翻訳しました。
本動画では、カルダノの取引処理能力をさらに向上させる「インプット・エンドーサー」の仕組みを、IOGのチーフ・サイエンティストのアゲロス・キアイアス教授が徹底解説。ブロックチェーン・ネットワークにおける処理能力の基本的な仕組みから分かりやすく説明しています。今後のカルダノのアップデートの根幹となる話題なので、ぜひチェックしてみてください！

---

こんにちは。エジンバラ大学教授、ブロックチェーン技術研究所所長、Input Output Globalのチーフサイエンティストのアゲロス・キアイアス(Aggelos Kiayias)です。
このビデオでは、「ウロボロス・プロトコル」のスケーリングに関する研究の進歩について紹介します。
ウロボロスは、Bitcoinブロックチェーンと同様の分散性を持ちながら、Proof of Stakeに基づく「Longest Chain Protocol（最長チェーン優先プロトコル、ブロックがフォークした場合、最長のチェーンを持つものを正とする検証方式）」です。
これは例えば、参加者の人口が継続的に変動することを処理する能力があるということです。Bitcoinとは異なり、Proof of Workのプロトコルで必要とされるエネルギー消費を使うことなく、この分散性を実現することができます。

「最長チェーン優先プロトコル」における限界値を考える

一方で、この「最長チェーン優先プロトコル」は、性能特性が悪いと思われています。なぜそうなのかを考えてみましょう。コンセンサス・プロトコルに求められる性能とはどのようなものでしょうか？

コンセンサス・プロトコルの性能を簡単に可視化する方法は、パイプに見立てて考えることです。幅はスループット（処理能力）で、長さはセトルメント（合意形成）時間です。
ここで望ましいのは、スループットは広く、セトルメント時間が短いことです。
ここでは、スループットに焦点を当ててお話をしましょう。
最長チェーン優先プロトコル（Longest Chain Protocol）の問題点を説明し、どのように逆転し、分散性を失うことなく、より良いスループットを得ることができるかを紹介します。

「最長チェーン優先プロトコル」では、1秒あたりのトランザクション数に換算したスループットを「f x B」と表現します。ここで、fは「1秒あたりのブロック生成率」、Bは「1ブロック内のトランザクション数」です。

・ f x B =1秒あたりのトランザクション数スループット
・f＝1秒あたりのブロック生成率
・B＝1ブロック内のトランザクション数

ここでは簡単にするために、すべてのトランザクションが同じ大きさであると仮定します。よってこの場合、トランザクションを「伝送データの主な単位」として使うことができます。
これから述べる議論は、たとえ別の指標を使ったとしても同じになるはずです。
この「 f × B」の式から、「f が大きければスループットが良くなる」ことがわかります。しかし、ここで問題になるのは「f をどの程度大きくしていいのか？」ということです。

さて、この問題は、私たちが何年もかけて詳細に研究してきたものです。
そして、2021年の「ACM コンピュータ・コミュニケーション・セキュリティ シンポジウム」で発表した最新の解析によって、これらのプロトコルの安全性に対する必要十分条件として、この式を導き出すことができました。ここで、

・Δ＝ブロック伝送(block propagation)のためのネットワーク遅延
・pA＝敵対的当事者(adversarial parties)の相対的なパワー
・pH＝誠実な当事者(honest parties) の相対的なパワー

と定義します。
これが「ブロック生成率＝ f」に与える影響を理解するためには、ブロックに対するネットワークの遅延を理解する必要があります。

そして、これは複雑な問題ですが、シンプルな抽象化が必要になります。このブロック伝送遅延に類似する現象を、今回の目的に合わせて抽象化すると、上図の式となります。

では、これを分解してみましょう。ここで、この大文字Cは、「ネットワーク内の2つのピア間の1秒あたりのトランザクション」に換算した、通信リンクの実際のスループットを表しています。
したがってB/Cは、1つのリンク上でブロックをプッシュするのに必要な時間を表します。
しかし、私たちは多くのピアが互いに接続されたP2Pネットワーク上にあり、これは一定の直径（大文字D、diameter）を持つことになります。最悪の場合、このDを掛け合わせる必要があります。
そして最後に、小文字dは、送信する必要のあるデータ量とは無関係に持つことになる、固定的な遅延です。

これらをまとめると、最長チェーン優先プロトコルのスループットの上限が導き出され、スループットはこの量より小さくなります。
そしてご覧の通り、これはブロックサイズに依存せず、予想通り、通信リンクのスループットに比例し、ネットワークの直径に反比例しています。

最長チェーン優先プロトコルのスループットは、非常に非効率だと判明

さて、ここで典型的なパラメータ設定として、

・敵対側vs誠実側＝45％ vs 55％
・ネットワークの直径＝5 hop   （*hopは送信者→受信者までの経路数）

とすると、最長チェーン優先プロトコルのスループットは、この通信リンク上で利用できるスループットに対して、わずか8％に過ぎないことがわかります。

つまり、「Longest Chain Protocol（最長チェーン優先プロトコル）」では、利用可能な通信スループット上限の92％が未使用のままになっているのです。これは実にもったいないことで、どうすることもできないように思われます。

「インプット・エンドーサー」で、スループットを最適化する

そこで、このスループットの制限をどう解決するか、現在進行中の研究を紹介しましょう。
Ouroborosは、トランザクションの過負荷時にバックプレッシャーをかけるネットワークインフラを利用しています。
システムは実現可能なものをブロックに吸収する一方、大量のトランザクションはプロデューサーのmempool（処理前の取引データを一時保存するメモリプール）に引き込まれて、処理される順番を待つことになります。高負荷時には、各トランザクションは処理待ちの状態となってしまいます。
ここで私たちの最初のイノベーションを紹介しましょう。
「インプット・エンドーサー・コンセプト（input=入力、endorser=裏書人）」により、メインチェーンのブロックに入ることが検討される前に、mempoolのセグメントをネットワークに解放することができます。

つまり、ブロックプロデューサー（ブロック生成ノード）は自分のmempool上のスペースを解放し、トランザクションを引き込むためのスペースを得ることができるのです。
一方、これらのmempoolは、P2Pネットワークにおいて「入力ブロック」という形で浮かんでいるような状態となります。

そしてこれを最大限に活用するには、このmempoolの分割をブロック・プロデューサーの集団全体で同時に行う必要があります。
このためには、入力ブロック間の重なりを極力少なくしなくてはいけません。スペクトラム拡散通信(spread spectrum communications)からヒントを得た符号化技術を活用することで、これを私たちは実現します。

入力されたブロックの有効性は、通常の「最長チェーン優先プロトコル」のブロックと同様にチェックされますが、ミスリル証明書の発行によっても証明されます。これにより、入力ブロックを証明によってのみメインチェーンに含まれる検証済みトランザクションのバッチに変換することになります。
これらのインプットブロック証明書は共同して自発的に作成されます。つまり、インプットブロック内のトランザクションのバッチは検証され、スクリプトはメインチェーンブロック検証のクリティカルパスの外側で実行されます。

カルダノのスループットが10倍向上する!?

現在、「最長チェーンのブロック」の目的は、これらの入力ブロックを整理するために使用されているに過ぎません。このため、ブロック生成側には、ネットワーク上に存在する有効な入力ブロックを受け入れる、独立した入力ブロック用mempoolが用意されています。
そしてこの慣習により、メインチェーンのブロックは、与えられた入力ブロックの順位付けを主目的とするため、今後は順位付けブロックと呼ばれることになります。
これにより、最終的な台帳は、入力ブロックに格納されたトランザクションによって決定されます。
そして、現在、これらはすでに検証済みであることを忘れないでください。最長チェーンが提供する連続性は、入力ブロックに存在する可能性のある二重払いを解決することを可能にしています。
また、入力ブロックの生産量が多いため、このような二重支出を排除できないことも覚えておいてください。
そしてこれは、拡張UTXOモデルが与えてくれる力を示すものでもあります。
この新たなメカニズムにおいては、スクリプトの実行（execution）と検証（validation）は、メインチェーンの検証のクリティカルパスの外側で行われます。二重支払いの解決はメインチェーン処理のままですが、UTXOグラフの競合の検出と解決に依存するだけの軽量な処理となりました。

このメカニズムを導入することで、最長チェーンのメカニズムを「トランザクションの運搬・処理」という重い仕事から切り離し、可能な限りシステムに負担をかけないようにスクリプト検証ができるようになりました。
そして、今回のテーマである「高スループット化」にとって最も重要なことは、最長チェーンプロトコル(longest chain mechanism)によって利用される“以外”のアイドリングネットワークを満たし、ウロボロスブロックチェーンのスループットをネットワークの理論的物理限界まで最大化できるようになったことです。

以上、今回紹介した仕組みをすべて盛り込んだ、現在開発中のOuroborosプロトコルの新バージョン「Ouroboros Leios」で実現できることを、簡単に紹介しました。

このように、既存のOuroboros Praosのブロックチェーンは、完全分散型で最適に近いスループット性能を実現できる基盤になります。
さらに、これまでの ledger combinersの研究から得た技術を使えば、入力ブロックの補完時間を短縮するために、追加の「ランキング・ブロックチェーン」を導入できることがすでに観測されています。その結果、高いスループットと高速なセトルメント(settlement)を同時に実現することが可能になります。
ただし、この技術の具体的な方法については、今後のトピックになる予定です。

【了】

---

【合わせて読みたい↓】
「Plutus（プルータス）」徹底解説！2022年6月HF【超訳カルダノ】
「Mithril ／ミスリル」とは？｜BCデータの分散型スナップショット【超訳カルダノ】