LayerXのリサーチャーが考える、Account/Balanceモデルのシャーディングの課題

シャーディングやEthereum、CBC Casperについて研究

岡南直哉氏：「Account/Balanceモデルのシャーディングと課題点」というタイトルで岡南が発表します。

まず自己紹介です。Layer XのResearcherとして働いていまして、2019年の7月からシャーディングやEthereum、CBC Casperについて研究しています。今、筑波大のM1でして、春から大学院で勉強しています。

たまに競プロとかCTFとかKaggleとか……競プロというのはアルゴリズムのコンテストだったり、CTFというのはセキュリティのコンテストだったり、Kaggleは機械学習のコンテストなんですけど、こういうのに暇なときに出ています。

今日の目次というかアジェンダです。中村さんの圧倒的な勉強会がありましたが、簡単にAccount/Balanceモデルのシャーディングについてまず説明しまして、そのあと、課題点を説明します。

そして解決策もちょっと紹介してから、その課題点とけっこう深く関わる「Load Balancing for Sharded Blockchains」という研究を紹介します。こちらの研究はWTSC’20という国際ワークショプで発表いたしました。最後にQ&Aを設けています。

今回のセッションのゴールは、こうしたAccount/Balanceモデルのシャーディングの課題点と解決策を通じて、シャーディングの理解を深めることです。みなさんのシャーディングの理解が深まれば幸いです。

Account/Balanceモデルのシャーディングの基礎

まずAccount/Balanceモデルのシャーディングについて、トランザクションモデルという、こうした基礎なところから、お話します。

これはブロックチェーンにおいて、どのようにトランザクションを管理・表現するかのモデルでして、大きく2つあります。UTXOモデルとAccount/Balanceモデルです。明確な違いとして、アカウントと残高が明示的であるかどうかがあります。Bitcoinだとアカウントと残高という概念が抽象化されていまして、逆にEthereumとかだとアカウントと残高が明示的に結びついています。

Shared Blockchainでも、このUTXOモデルとAccount/Balanceモデルとでけっこう違っていまして、今回はAccount/BalanceモデルのEthereum 2.0と、先ほどNSDIで発表があったと中村さんが言っていたMonoxideについて解説していきたいと思います。

Account/Balanceモデルはスマートコントラクトの実装に適していまして、その分、トランザクションの負荷や手数料に、より気を遣う必要があります。

さっきのおさらいなんですけれども、すごく簡単にまとめると、シャーディングというのはブロックチェーンをたくさん作って並列化する技術のことです。これでスケーラビリティが向上します。具体的に何をするものかといいますと、トランザクションを検証するバリデータとトランザクションのこれら集合を分割します。

ちょっと図を見ていただきたいんですけれども、バリデータ・検証・トランザクションとありまして、この矢印が、バリデータがトランザクションを検証することを表しています。バリデータが4人・トランザクションが4つあったときに、こうやって4×4の検証が行なわれます。

「シャーディングによってバリデータ集合・トランザクション集合が分割されると、この検証の数が大幅に減るよね」というのが、簡単なシャーディングのイメージです。

Account/Balanceモデルのシャーディングにおける3つの課題

Account/Balanceモデルにおいては、アカウント集合も分割しなければならなくて、トランザクション、バリデータに加えてアカウントも分割しましょうという話になります。

このシャード間のトランザクションというのがけっこうキーポイントになっていまして、クロスシャードトランザクションといいます。

これはあるシャードから別のシャードへのトランザクションのことなんですけれども、通常のトランザクション、普通の例えばシャーディングしていないブロックチェーンにおけるトランザクションとかより、非常にその負荷が大きかったり手数料が高かったり、またそのレイテンシーが高いといった問題があります。

これらのAccount/Balanceモデルのシャーディングにおける課題点を簡単に3つ紹介したいと思います。

1つは、先ほど中村さんがおっしゃっていた、バリデータのシャッフルの話のオーバーヘッドについて。2つめは、クロスシャードトランザクション。この負荷が大きかったり、手数料が高くなってしまうクロスシャードトランザクションによって、そのUXが、どう悪化してしまうのか。あとは、その影響とか。そして3つ目が、特定シャードへの負荷集中といった現象です。これらの3つについて詳しく紹介していきます。

バリデータのシャッフルによるオーバーヘッドの問題と解決策

まず1つ目の、バリデータのシャッフルによるオーバーヘッドの話です。あるシャードのバリデータはランダムに割り当てられるんですけれども、割り当てられたときに、攻撃者が例えば賄賂を渡してそのシャードのバリデータを支配して、シャードを乗っ取ろうとする攻撃があります。

これを防ぐためにバリデータを定期的にシャッフルします。例えば数日ごととかにバリデータをシャッフルすることで、この攻撃をある程度防ぐことができます。

ただ、バリデータというのはステートを持つ必要があって、シャッフルのたびに別のシャードのステートを毎回ダウンロードしなくてはいけません。あらかじめ持っててもいいんですけど、基本的にはダウンロードしなくてはいけません。

この問題点は、通信コストが非常にかかることです。例えば数時間だったりとか、通信環境が悪ければ数日かかったりすることもあって、そもそもバリデータとして参加できないようなケースもあります。攻撃を防ぐために条件を厳しくしすぎると、通信環境がいい人しか参加できず、中央集権化してしまうといった問題があります。

解決策としては、先ほど中村さんも軽く紹介していたんですけど、Stateless clientといって、フルノードはステートを保存しなくていいというのがあります。

詳しくはこのリンク先を見てほしいんですけれども、状態遷移に少し変更を加えます。そうすることでステートではなくてステートルートだけもてばよくなっていまして……。また、それだけではなくて、ステートの検証をユーザーに協力してもらえることでこれが実現するといったものがStateless clientです。これによってストレージ負荷が小さくなって、先ほどの問題を緩和することができます。

クロスシャードトランザクションによるUXの悪化

次の課題点、クロスシャードトランザクションによるUXの悪化です。先ほども言ったんですけれども、負荷が大きくなったり、それによって手数料が大きくなったり、レイテンシーが高くなってしまうという、クロスシャードによってどれだけそのユーザーのUX、もしくはバリデータのUXが悪化してしまうのか？　そして、どんな現象が起こってしまうのか？　というのはまだまだぜんぜん詳細な分析は行なわれていないものです。

これは排他制御や2相コミットをベースにしていまして、先ほど中村さんから紹介があったYankingだったりとかっていうのは本当にストレージ負荷とか計算負荷とかがかかるものでして、通常のトランザクションより重いものになっています。

これによってどういった悪化現象があるかの一例として、負荷集中現象というのがあります。次でちょっとご紹介します。

なぜ特定シャードへ負荷が集中してしまうかですが、まず、アカウントの配置の仕方の問題があります。

Ethereum 2.0だと、基本的にはアカウントアドレスのプレフィックスをもとにアカウントを配置するという決まりがあります。例えば「プレフィックス0x00から始まるアカウントアドレスだったらShard 0。0x01から始まるアカウントアドレスだったらShard 1」みたいな感じで割り当てます。これってただランダムに割り当てているだけなので、そのアカウントがどういったトランザクションを発行するのかとかに関してまったく考慮してないんです。

例えばそのアカウントがむちゃくちゃ人気なコントラクトで、偶然そのトップ1・トップ2の取引とか負荷があるコントラクトが集まったりとか、別に集まらなくても、トップ1のコントラクトだけ、なんか（負荷が）異常に高かったりすると、そのシャードだけ異常に負荷が高くなってしまいます。

もう1つはユーザーの利己的な行動という問題です。これはそもそもまず前提として、ユーザーとアカウントは1対多の関係にあって、ユーザーはいくつもアカウントを作ることができます。例えばトランザクションの手数料を安くしたいユーザーがいたとして、頻繁に利用するアカウント、例えば頻繁に利用するゲームだったりとか頻繁に利用するDeFiのアプリケーションとか、そうしたアカウントに属するシャードに属したほうが、手数料が安くなります。

なので、基本的に人気なコントラクトがあるシャードにはどんどんアカウントが集まってきます。そうすることでクロスシャードトランザクションが減るので手数料が安くなる。

ただ一方で、人気すぎるシャードに属すると、どんどんその手数料が高くなってしまうんですね。これはなんでかというと、トランザクションの採用って基本的にオークション制なので、人気すぎるシャードにアカウントがどんどん集まってくると、そのトランザクション量も増えてきて、自分のトランザクションが採用できなくなってきたり採用されなくなってくるといった現象が起こるので、極端な負荷集中は起こらないとも言えます。

アプリケーションを複数シャードに配置する

こういった特定シャードへの負荷集中をどうやって解決すればいいかという話なんですけど、まず1つ目はアプリケーションを複数シャードに配置する。これはよく言われていることなんですけれども、例えばまったく同じアプリケーションを複数シャードにデプロイします。例えば取引所だったら取引所を、例えばEthereum 2.0だったら64個にデプロイするみたいな。

逆に普通に並列化できるようなアプリケーションだったら、1つのアプリケーションを複数シャードで並列化してスケーラビリティを実現するみたいな……。いろんなやり方があるんですけれども、これはなんかあんまりイマイチだなと思うところがあります。

例えば、先ほど言った取引所のような金融アプリケーションだったら、その流動性が小さくなります。64個分の取引所があったらその分64分の1になっちゃうので、あんまりよくないと……。

さらに、例えばUniswapみたいな並列化と相性の悪いアプリケーションもありまして……。今言ったような話ですね。これも部分的に並列化するテクニックもありまして、詳細はこのリンクをご参照ください。Uniswapみたいなシングルスレッドのアプリケーションは、あんまりこの解決策には適していないのかなとは考えています。

実際こうやって解決できるんですけれども、これでどれだけ改善するかはまだ詳細に分析されてもいません。

アカウントを動的にシャードに割り当てる

次の解決策なんですけれども、これが今回の研究の内容です。アカウントを動的にシャードに割り当てます。

まずGARETという、この間『Cluster Computing』というジャーナルに発表された研究がありまして、これはオンチェーンでトランザクション負荷を予測して、アカウントをグループごとに割り当てるという、負荷分散プロトコルの研究です。

アカウントをグループごとに割り当てるというのは、アカウントが多すぎるのでグループごとに割り当てないと計算量が大きくなってしまう。ですけれども、これである程度負荷分散ができるよ、負荷集中を緩和できるよという研究です。先月出た研究です。

我々がWTSCというマレーシアでやった国際ワークショップで発表した「Load Balancing for Sharded Blockchains」というのも少し似ていまして、あとで詳しく説明するのですが、これはどういったことかというと、負荷分散を最適化問題に定式化します。その問題を公開しまして競わせます。プレイヤーを競わせて、それのもとに最もいい解を提出してきた者に報酬をあげて、その最良の解を適用してアカウントを再割り当てするというのが「Load Balancing for Sharded Blockchains」の提案です。

GARETはユーザーの利己的な行動を考えていなくて、うちらはそれを考えましたということがちょっと違いかなと思います。

先ほどもちょっと話したんですけれども、ユーザーの利己的な行動によって負荷分散がちょっとできる。つまり、人気なシャードがどんどん人気になっていくと手数料が高くなってしまうので、極端な負荷集中が起こらないという話になります。そしてさらに人気なシャードへ移動するインセンティブをなくすことで、またより負荷分散を緩和できるのかなとも考えたりします。

また一方で、このユーザーの利己的な行動による負荷分散というのは、パレート最適みたいな全ユーザーの幸せの総和があまりよろしくないと、皆々が自分のUXを最適化しようとするので、みんなが協力してUXをよくしようねという解決策にはちょっと劣るかなと考えています。

なので、個人的にはIn-protocolで直接割り当てるさっきの解決策のほうがいいのかなと考えています。この「In-protocolよりも利己的な行動のほうがよくないね」というのは、簡易的なシミュレーションでも確認できます。