「秘密計算の数理最適化への応用」の振り返り

2024/06から2024/10までの5ヶ月の間、Etheruem Foundationの研究助成金のもと「MPCベースの秘密計算の数理最適化への応用」に取り組んでいた。これはEFのenricoとnamとの共同研究であった。
MPCアルゴリズム構築においてぶつかった課題感について記述しながら、5ヶ月間の取り組みを振り返る。
 背景EFのLearning Grantという、自分で好きなテーマを学んでアウトプットするグラントが終了した2024年6月のタイミングでenricoに誘われてgridlockというプロジェクトに参加した。
スロベニアなどの一部企業では、政府エージェンシーが各企業の請求書を毎月集めて「ネッティング」と言われる処理をしている。ネッティングはいわゆる割り勘アプリ「walica」の企業版で、たとえば企業AとBが相互に請求書をもっている場合、小さい方の金額を引くことで片方の請求書を処理する必要がなくなる。このようになるべく請求書を少なくすることをネッティングという。
このネッティングを普通に解くと超難しいので、最小費用流問題という数理最適化問題に一般化して解くことが知られている。このあたりについては詳しくは下記を参照にしてほしい。
A Note On Securely Finding Minimum Mean Cycle
https://drive.google.com/file/d/1Lo6ls_2friG6HvNDs3foVSw4HyLnpoHD/vie
しかし、スロベニアではこのネッティングへの参加率が最大8%ほどに留まっている。これは請求書を政府に開示したくないというプライバシーの懸念から来ている。そこで、MPCで動作する最小費用流問題アルゴリズムを提案することにした。ここでは「誰が」「誰に」「いくら請求する」という情報を隠したまま最小費用流問題を解く。
企業は請求書をMPCノードに送信し、MPCノードが最小費用流アルゴリズムを実行し、更新版の請求書を返す。
 取り組み 1. 先行研究を捜索するまずは既存の先行研究を探し、現状を整理するところから始まった。いくつか見つかった中でAlyらの研究を改善するところから取り組むことにした。Alyは最小費用流問題アルゴリズムの一種である最小平均閉路消去法のMPCアルゴリズムを提案した。
 2. 小さなことから取り組み、巨人の肩に乗る我々は、まずこのプロトコルの計算量を2オーダーほど改善し、それを論文としてETH Researchに投稿した。これは小さな改善だが、小さくてもアウトプットしていくことで自分たちが分野における貢献者であることをアピールすることができる。
その後、この提案をもとにAlyと連絡を取り、ミーティングをしてディスカッションすることができた。他の先行研究者のAndrew MillerやTomazをはじめとする同分野の研究者ともコンタクトを取り、協力を得ることができた。
 3. 更に改善していくAlyの一番の問題として「グラフを完全グラフとして扱わなければいけない」ことがあった。これは、セキュアに実行するためにグラフトポロジーも隠したいので、存在しないエッジも存在するかのようにふるまわなければならない。そうすると、最適化問題は常に最悪シナリオ上の実行となり、非常に非効率だった。
そこでセキュアシャッフルに目をつけた。荒木らは、先にグラフのノードラベルをシャッフルしてからトポロジーを公開してプロトコルを実行することで効率的に実行する方法を提案しており、我々もこれを応用できるだろうと考えた。
それに加えて、最小平均閉路消去法よりもはるかに効率的で多項式時間で実行できるネットワークシンプレックス法を用いて、実装した。この時点で実行時間は40分ほどだった。ちなみに最小平均閉路消去法は40時間走らせても実行が半分も終わらなかった。
さらに、グラフを分割して並列で最小費用流問題アルゴリズムを実行する方法も実装し、さらなる高速化が期待された。
 4. 課題にぶつかるここで2つの課題が発生する。
まず、Andrewの指摘により、ノードラベルをシャッフルしただけでは匿名化は不十分だということが判明した。我々はgraph perturbationというグラフ匿名化アルゴリズムを用いてこれを解決した。これは、ランダムにグラフを追加/削除することでもとのノードが変換後のノードのどれにあたるか、その候補を絞りきれないようにするアプローチだ。ただ、この実装により最適化の効果が15%ほど薄れてしまった。
次の課題がデータ依存性である。すべての最小費用流問題アルゴリズムにはループの終了条件というものがあり、この条件はデータに依存している。攻撃者はこの終了条件によってエッジの値を推測することができてしまう可能性がある。なので、終了条件を厳密に実装せずに、事前に決められた回数を必ずループするようにしなければいけなかった。そうするといくつかのループは無駄な実行をする必要があるため、2~3倍ほど遅くなってしまった。
 5. 最終的に最終的にプロトコルはWAN環境下で4~5時間で実行できるというところで落ち着いた。これは当初目標であった8時間を大幅に上回る形となった。見立てではAlyらの先行研究から100倍程度の改善だろう。
今は論文執筆に取り組んでいるが、この研究はEthereumにとって重要性が低いことから研究自体はここで打ち切りとなった。
 学び今回の研究での学びは非常に大きかった。enricoはよく「明日のミーティングまでにこれできる？」という無茶振りをしてくることから、とにかくやるしかない状況に自分を追い込むことができた。それにより「ちょっとアルゴリズム理解できないし実装できるかわかんないな」ということも、やればできるということがわかった。これは自分を勇気付ける習慣に繋がった。
それ以外にもenricoはミーティング中でもチャットでも「分からないことあれば遮っていいから聞いて」といつも背中を押してくれました。おかげで英語でのディスカッションの作法にも慣れました。
また、結果を小出しにしながら自分の存在をアピールすることで周囲を巻き込む立ち回りを学んだ。ここで巻き込むことができた先行研究者のTomazは我々のために現実世界によくシミュレートされたB2B取引データセットを用意してくれた。このデータ特性をもとに更にアルゴリズムをチューニングすることができた。
そして、アプリケーションのアルゴリズム最適化には限界があることも大きな学びとなった。ことMPCにおいては、パフォーマンスとプライバシーのトレードオフから逃れることは難しく、プライバシーをいくら犠牲にできるかという妥協点を模索するのが研究のコアな部分にあった。これを損なわないまま実行時間を高速化するには、より低レベル（コンパイラなど）での分散化や、分散グラフアルゴリズムなどの並列化技法のほうが良いという結論に至った。
MPC/FHEのユースケースとして最適化問題が解けると面白くなりそうというモチベーションから研究を始めたが、実際にはこのネッティングは最重要な問題ではないこともわかった。ネッティングに参加してないことによるコストは企業にとっては許容範囲内であり、現実として「アタック」されている危機ではない。なので今が最適なタイミングではなかった。しかしこのプロトコルはいつかイーサリアムのスケーラビリティやライトニングネットワークのリバランス問題に活用されていくだろう。
 次へわたしは次はZKVMに取り組む。ZKVMはイーサリアムにとって最重要問題であり、Jolt, RISC-Zero, SP1などがありながらもまだまだパフォーマンスにおける課題が山積みとなっている。また最近発表されたNexusはあのGens Groth博士が主導していることもあり、注目の高い研究分野となっている。わたしもこれに取り組み、Ethereumのスケーラビリティ問題を解決する。