特定シャードへの負荷集中にどう対応すべきか？　LayerXの研究成果を共有

負荷を分散するためのプロトコルの研究

岡南直哉氏（以下、岡南）：ここから本題になるんですけれども、研究紹介に入ります。先ほど言った課題点、3つ紹介したんですけれども、後ろの2つですね。クロスシャードトランザクションによるUXの悪化と特定シャードへの負荷集中。今回の研究は、この2つにフォーカスを当てました。

In-protocol Load Balancingというのを我々は提案していて、先ほども言ったんですけれども、これはプロトコルで直接みんなのアカウントを動かして負荷分散しようねという研究になります。そうすることでよりユーザー全体の、パレート最適な、みんなの幸せの総和が最大の状態になるという研究です。

どうやってこれを実現するかといいますと、まずシャードから負荷分散に必要な負荷情報を集めます。その情報をもとにオンチェーンでアカウントの割り当て問題を最適化として定式化します。それを公開していろんなプレイヤーに解いてもらって競わせて、それをもとにもっともいい解を提出してきたやつを採用して報酬を与えて、その解をもとに定期的にアカウントを割り当て直すというものがIn-protocol Load Balancingです。

定期的に割り当て直すことで利己的なシャード移動のインセンティブ自体が下がるので、さっき言ったユーザーの利己的な行動で負荷分散するのとごちゃごちゃになることもあんまり少なくなって、いい結果が得られます。

これはざっくりとしたイメージ図なんですけれども、まずメインチェーン（コンセンサスノード）が負荷情報を収集します。シャードというのは、負荷情報をある程度ためておく必要があるんですけれども、まず得て、それを最適化問題として定式化。プレイヤーが問題を取得して、それをプレイヤーが解く。次にその解を提出して、メインチェーンでその解を評価して報酬を与えるみたいな、こういった流れになっています。

まず最初の負荷情報の収集の話なんですけれども、シャードが、ある期間にそのシャードに関係するアカウント間での取引情報を集めておく必要があります。ある期間というのは、例えばEthereum 2.0だったら1エポックだったりとか。これは別に任意でいいんですけれども、そのブロックチェーンにふさわしい期間を選べばいいんですけれども、例えば1エポックとしましょう。

アカウント……先ほどからアカウントアカウント言ってますけど、これは何かといいますと、ウォレットとコントラクトのことですね。これの取引情報を集める必要があります。

この取引情報というのは、例えば「あるアカウントAとあるアカウントBが取引しましたよ」というのをそのままビーコンチェーンとかメインチェーンに刻むというのはちょっと非効率なので、負荷情報、つまり二次元のグラフのやりとりとして圧縮して保存します。Ethereum 2.0だったら、その負荷情報はビーコンチェーンに刻まれます。

ただ、全体のデータ量、例えばその負荷情報自体のデータ量がけっこう大きくなったらダメなんですよね。例えばアクティブアカウント。今取引をしているアカウントの数をnとしたときに、この取引情報、つまり負荷情報というのはO(n^2)になってしまいます。

これってけっこう大きい計算量でして、これが問題になるので、データ量が大きいサイズになってしまうときは、ランダムサンプリング、つまりアクティブアカウントから例えば30パーセント選んでとか、もしくは負荷の大きい順。結局負荷の大きいアカウントがけっこう負荷集中に影響するので、負荷の大きい順にアカウントを選択するみたいな、そういった工夫が必要になります。

シャードはビーコンチェーンにこの負荷情報を提出しまして、負荷情報の収集は完了します。これはシャードのステートルートを刻むのと同じやり方です。

負荷分散問題の定式化

ここからブロックチェーンとはあんまり関係ない話になってしまって恐縮なんですけれども、負荷分散問題の定式化の話です。これは最適化問題の話なんですけれども、どういった問題の定式化がいいかといいますと、負荷を分散させたいので、最大負荷のシャードの負荷、つまりボトルネックですよね、そのボトルネックを最小化しようみたいな形式が考えられます。

下のこの数式とかは、雰囲気でちょっと捉えていただければいいんですけれども、こういった定式化になっています。

この結果なんですけれども、非常に難しいクラスの問題でして、専門用語では、この混合整数非線形最適化問題またNP困難というかなり難しい問題でして……。これは本当にオンチェーンで解くのは全然できなくて、普通のコンピュータとかで解かせないとちょっとコストに見合わないよねという定式化結果になっています。

こういったクラスの問題はヒューリスティクスといわれる、「なんかわからないけど、こういった方法で解くとめちゃくちゃいい解が得られるよね」というアルゴリズム、もしくはソルバ、商用でいろいろ数理最適化のソルバが出ているんですけれども、それで解くのが一般的になっています。

さっきのコンペティションベースって「なんでコンペティションベース？　普通にオンチェーンでやればいいじゃん？」みたいな疑問が生まれてくる方も中にはいらっしゃったかもしれないですけれども、これの理由としては、「この負荷分散モデルの定式化結果がめちゃくちゃ難しくて、これをオンチェーンで直接するのはもうぜんぜんできないよね」というのが背景にあって、こういった定式化をしています。

ただ、この定式化のやり方というのはいろいろ考えられまして……。結論は、ただ単にUXが上がればいいんですよね。なので、よりよい問題性質の定式化、つまり解きやすい問題の定式化があるかもしれません。

コンペティション形式で解を集める

次に、コンペティション形式にして解を集める話をします。オンチェーンで最適化問題を公開するんですけれども、最もいい解を提出したプレイヤー、つまり、何人参加するかはちょっとよくわからないですけれども、それに報酬を与えます。

報酬はどこから来るかというと手数料ですね。つまり、ブロックのマイニング報酬みたいなものから与えられるなど、いろいろ考え方があるんですけれども、いわゆるProof of Workのアルゴリズムになっています。プロトコルです。

これはどれぐらいの期間でやるかというと、先ほども言ったんですけれども、1エポックですね。Ethereum 2.0だったら64ブロックみたいな感じで行ないます。

この解の検証はオンチェーンで行ないます。この解の検証自体はぜんぜんコストかからないのでオンチェーンでやっても大丈夫という話です。

ただ、解を提出したときに別のプレイヤーがその解を奪ってちょっと良くして提出しちゃうとアンフェアなので、その解の暗号化なども工夫が考えられて、いわゆる暗号学的にはコミットメントスキームと言われるプロトコル、アルゴリズムが必要になります。

ヒューリスティクス問題の解き方と、その評価

では実際にそのプレイヤー、つまりコンペティションに参加するプレイヤーがどういった問題の解き方をすればいいかという話をちょっと簡単に紹介します。

特定の問題に対してアドホックにアルゴリズムを組むというのがヒューリスティクスなんですけれども、ヒューリスティクスの中でも「どんな問題にも使えちゃうよ」みたいなこれは、メタヒューリスティクスと呼ばれるものです。

例えば焼きなまし法というのが有名なんですけれども。最初はいろんな解……この図を見ていただくと、この黒い曲線ですね。下にいけばいくほどいい解です。なので、これは局所最適解で、こっちも局所最適解で、こっちは大域的最適解なんですけれども、ここ（グラフ真ん中の一番下に落ちている場所）にいきたいです。

焼きなまし法のアルゴリズムは、最初は、いろんないい解も悪い解にもわーって行くんですけれども、徐々にその動きが小さくなってきまして、局所最適解に陥らずに大域的局所解にいくよというものです。

この実際の提案を簡単に評価・実験しました。Ethereum 2.0の仕様をベースにシミュレーションしたんですけれども、例えばビーコンチェーンとかYankingなどの仕組みを参考にしてシミュレーションしました。

シミュレーションのサイズとしましては、アカウント数が1,000、シャード数8としました。実際のEthereum 2.0って、おそらくアカウント数数十万とか、シャード数が最初は64なんですけれども、そこまで1つのコンピュータではシミュレーションできないので、こういった数値にしています。

利己的なロードバランシングと、先ほど言ったユーザーの利己的な行動によって負荷分散がちょっと起こるよねという話と、これはただ自然な現象なので何もしてないのと一緒なんですけれども、これとプロトコルで直接ロードバランシングした結果を比べてみたというのが今回の実験です。

結果としましては、一応この図ちょっと見てほしいんですけれども、時間が経つにつれて総手数料がどんどん下がっていきます。

この図にはないんですけれども、クロスシャードトランザクションの数、つまり負荷が非常にかかって手数料もかかってレイテンシーも大きいよというクロスシャードトランザクションは約5分の1になっています。

ただ、モデルと仮定の妥当性、つまりシミュレーションの質はまだまだ改善できる余地があるかなとは思っていまして、例えば動的に、取引の分布ですね、アカウント間の取引の分布が変化していないので、ちょっとまだ不足点はあるかと思っていますが、結果としてIn-protocolで直接ロードバランシングしたほうがいい結果が得られました。

現実的なプロトコル開発に向けて現在も研究中

全体のまとめです。Account/Balanceモデルのシャーディングにおける課題として、3つ紹介しました。バリデータのシャッフルによるオーバーヘッドと、クロスシャードトランザクションによるUXの悪化、今回取り上げた特定シャードへの負荷集中。

今回の研究は、この特定シャードへの負荷集中といった課題や問題に対してどういったアプローチをとればいいかでして、その提案としましては、コンペティションベースのアカウントの動的割り当てがあります。現実的なモデル・仮定、プロトコル開発に向けて現在も研究中にあります。

以上です。というわけでちょっと質問タイムですかね。じゃあまず1つ目。

メタヒューリスティクスは量子アニーリングで効率的に解けるか？

（視聴者からの質問）メタヒューリスティクスは量子アニーリングで効率的に解ける問題のタイプでしょうか？

岡南：量子アニーリングって、個人的には……そうですね、メタヒューリスティクスなので、量子アニーリングというのはメタヒューリスティクスなんでも解けると思っているんですけれども、ただ、古典的なアニーリングと結果はそこまで変わらないのかなとは思っています。なので、answerとしては、yesではありますが、古典でも変わらないという感じです。

コンペティションとスケーラビリティ

（視聴者からの質問）コンペティションに参加するためには、全シャードのデータを持つ必要がありますが、そこはスケーラビリティを損ないうる仮定でしょうか？

岡南：全シャードのデータはもつ必要はなくて、シャードが負荷の情報を集めます。まず取引情報から負荷情報に加工して、それをビーコンチェーンに……。イメージとしましては管理するみたいな。またビーコンチェーンで最適化問題としてさらに加工してやるので、確かに先ほど僕が言った「データ量がO(n^2)になって大変だよ」みたいな問題はありますが、スケーラビリティを損なわない仮定ではあると考えています。

乱択アルゴリズムの採用の是非

（視聴者からの質問）アルゴリズムを各コンペティターが各々準備できるようにしてしまうと、最適化問題を解くのに有利なアルゴリズムを持っている計算ノードが有利になり、中央集権化になりませんか？ 無駄な探索はしますが、計算資源に比例したような乱択アルゴリズムの採用としたほうがいいような気もしますがどうなのでしょうか？

岡南：基本的に中央集権化の問題って、例えばコンセンサスアルゴリズムとかの話だと思っていて……。例えば、みんなの幸せのために協力してたんだからお金払うというのは別にいいかなと思っています。なので、中央集権化にはなりません。

次の「無駄な探索はしますが、計算資源に比例したうんぬん」というのは、実際、僕たちも乱択アルゴリズムを試したんですけれども、それはユーザーの利己的な行動で行なわれた負荷分散アルゴリズムのほうがいいという結果も得られたので、もし乱択アルゴリズムとかを採用したら、つまりオンチェーンでやろうとしたら、あんまりいい結果が得られないと考えています。

オンチェーンで行なう解の検証について

（視聴者からの質問）解の検証とオンチェーンで行なうイメージを詳しく教えていただけますか？

岡南：まず最適化問題として定式化するんですけれども、解を検証するというのはそこまでコストはかからないんですよね。

オンチェーンで行なうというのは、普通にバリデータがその解を評価します。「この解はいくらのスコアの解でした」みたいなやつを積み上げて、例えば100個集まったら、その中でどれがいいかを選択するというのをオンチェーンで行ないます。

ただ、いろんなノードがDoS攻撃みたいにどんどん解を送ってこられると非常に困ってしまうので、そこにはちゃんと手数料かかるようにしておく必要があります。

質問は以上といった感じになりますので、ここらで終わります。ありがとうございました。