本記事は@ushitora_anqou(以下、お魚さん)の開催した投稿大会に当たってせっかくだしそこに投げようかという気分で執筆されたものである。ちなみに間に合ってない。WordPress何もわからんので見づらいかも。なんか途中から口調が変わってるんですがまぁ執筆が日をまたいだのであれ。
主な登場人物
@nimdanaoto:筆者
@Vtb:同じサークルに所属するみかん。祖父が鯛の養殖をしてるらしい。彼との会話でアイデアが固まった。自作CPUしてたし興味あるんでねと思って声をかけたやつ。
@ushitora_anqou 初見はk/vmだったと思うんだけどCコンパイラが書ける頭おかしい(そういう名前の賞もらってたしほめことばに違いない)のがいるというのを覚えていたので、みかん経由で声をかけた魚。自然言語コンパイラ。
準同型暗号という、暗号文のまま計算ができる暗号がある
全ては、2019年２月末に聞いたこの言葉から始まった。私は暗号を含む理論担当だったわけだが、私はこのときまで暗号はRSA暗号しかまともに知らない(素数が好きだったので高校時代に素因数分解にハマっていたからこれだけ知っていた)状況だった。そんな中、４回生の特別研究のための研究室紹介に潜り込んだ私は、この１文を聞きおもろげだったので適当に調べ始めたわけである。
おそらくこんな記事を見ている人間なら理解はしてくれると思う文化として、何かその上で計算可能なものを見つけたら、チューリング完全かどうかを考えたり、CPUが作れるかということを考えるものである。マインクラフトが好例だろう。パワーポイントでチューリングマシンするのはどうかと思う。
幸いなことに、準同型暗号ではすでに任意の論理演算ができることがすぐにわかった。主流の準同型暗号ではある整数を法とした剰余環上の演算を考えるので、2を法とした足し算でXORを、掛け算でANDを作ることができる。まぁ、私が使っているTFHEは全然原理が違うどちらかといえば傍流なやつなので二項の論理ゲートは全てstraight-forwardに定義できるのだが。
論理ゲートができることがわかれば、次に考えるのはCPUができるかどうかである。ここまでは趣味的な意味ではごく自然な発想であった。
みかんの啓示
私はエピソード記憶が弱いので正確にどんな会話をしていたかは覚えていないのだが、部室でみかんと会話したことは覚えている。未踏の応募締切が近いのは知っていたので、何かアイデアがあるかという話になって、確かみかんから分散コンピューティングまわりのもの作るのはどうだろうかみたいな話になって、そこに準同型暗号上でCPUを作るアイデアを話して、あーそれ分散コンピューティング的にも嬉しいんでねーとなってVSPの原型のアイデアができた気がする。
成果報告書とかをみると、クラウドへのオフローディングを中心としたストーリーになっているが、応募書類の段階では分散コンピューティングの話とかになっているのはこのためである。実装のコアとなるアイデアはここでできたものだが、見せ方となる応用は二人の趣向の関係で分散コンピューティングが最初に思いついていたわけである。
ちなみに、この段階ではCPUといってもJVM的なもののほうがスタックマシンだしリソースが少なくなってええんでね？みたいな会話をしていたはず。
魚類現る
なんとなくのアイデアが出たはいいが、このアイデアには重大な欠陥が一つあった。明らかに既存のものをそのまま流用すると遅すぎるのである。私は電気電子の人間なので、TFHEの１ゲート10msをそのまま普通のCPUやらJVMやらのエミュレーションにつかったらとんでもなく遅くなることぐらいは最初からわかっていた。それを無理やり回避するには、CPUのISAを変えるなどコンパイラのレベルにまで影響する変更が必要だろうと予測されたのである。コンパイラもやろうと思ったのは、私自身がアセンブラなんてかけないので、自分(つまりおそらくはVSPに興味を持つような人間の多く)が使えないレベルのもの作っても哀しすぎでは？と思ったのと、いい具合にコンパイラかけそうな存在、つまりお魚さんがいたからである。
「きっとこの手の人は自分の好きなことがやれる口実を提供すれば釣れるし、関わってしまえば他のこともやってしまうに違いない」という当時の勝手な印象通り、ほぼ二つ返事みたいな感じで了承してくれたし、それ以外のことも色々やってくれた。確か学食の入り口そばの席でプレゼンして、その席にあった壁掛けディスプレイに私は頭をぶつけた気がする。
私は電気電子の人間なので、プロセッサを書くことはできたかもしれない(まぁ、経験を含むもろもろの問題でみかんに劣るし、そもそもみかんが居なかったらアイデアを相談する相手が居ないので形にならなかったとは思うが)がコンパイラは何もわからんのでお魚さんがいなければコンパイラがつくことはなかっただろう。そういえば結局一番働いていたのはお魚さんだと思う。多分ビリは私である。
お魚さんに声をかけたときには、Yosysを使ってVerilogからTFHE上でそれをエミュレートするための情報を得ようみたいな話は出来上がっていた。
ベッドの上の三日間
実のところ、お魚さんに声をかけた時点で３月に入っていて、未踏の応募締め切りまで１週間とかしかなかった。しかし、私は暗号の専門家どころか情報の人間ですらないので、応募書類を書くには知らないことが多すぎた。その結果、３日間ほど食事以外ほぼベッドの上から動かずに論文を読んで応募書類のためのアイデアを練る時間が発生することとなった。あれだけ一つのことに集中できたのはなかなか久しぶりのことであった。
お魚さんの自然言語コンパイラとしての機能はこの時点から観測されていて、細かい応募書類の言い回しとかの修正は彼によるところが大きい。
最終的には、内容を書きすぎて余白を狭くして参考文献のリストの改行をなくすとかいう暴挙をしていた。まぁ、３人も居たからこその物量とも言える。
PMはあなたのプロジェクトの分野の専門家とは限りません
応募書類を作って送って通れば次は２次審査になる。（PMにプレゼンをする）このときに、進捗的なものがあれば入れろと言う話があったので、応募書類を出してから気づいたHomomorphic Processorとよばれる競合する分野に関する話をした。明らかに反応が何を言っているんだろうこいつはという感じになっていた。プレゼン作るときはその筋の専門家に突っ込まれることを(素人なりに)想定して作っていたわけだが、その場には誰も暗号やセキュリティをメインとしている専門家など居なかったのである。興味は持ってもらえたし、熱意と何となく過ごそう的な印象は与えられたっぽいが、この段階で我々のプロジェクトを、そのコアのアイデアでさえ完全に理解できた人はあの場には居なかったはずである。なにせ、担当になった首藤PMですらあの段階どころか始まって１ヶ月ぐらい後までご理解頂いてなかったのだから。
そういえば竹内PMにはこの時点でそんな遅いんだったら計算処理を移譲せずに手元でやったほうが速いのでは？という質問を頂いた気がする。それは現状でもそのとおりといえばそのとおりで、他の採択プロジェクトを見ても感じられる通り、経産省のプロジェクトということもあってか明日使えるようなプロジェクトが望まれているように見える。そんな中、「明日ではなく十年後」というのを最初から認めてもらえる首藤PMに当たったのは運の良いことで、多数決では決まらないPM制の良い点(と言えるようにするには今後の我々の努力も関わるが)と言えるだろう。
そういえば２次審査の帰りに秋葉でいきなりステーキを初めて食べたのを覚えている。
礎となったV2TT
とりあえず採択されるまでの経緯っぽいことは書いたので、次は作ったもので特に私が関わったことの話をしよう。最初に作っていたのがV2TTである。こいつは、Yosysが吐いてきたJSONのネットリスト(最初はBLIFにするつもりだったのだがBLIF何もわからんかった)を読んで、それを静的に解析してTFHE上で実行するためのC++コードを吐くトランスパイラであった。この静的に解析するというのが問題で、並列性を引き出すのにそれぞれの論理ゲートが入力から論理ゲートを何段経由するかを数えて同じ段数のやつだけを一緒に実行するという形式にしたので、段ごとの数によってはCPUの稼働率が急落する感じになってしまった。しかし、V2TTの段階で第三世代のCPU(誕生石にちなんだ名前だったのでaquamarine)までは動作の確認が取れたのは大きかったと思う。
性能の問題に関してはみかんが原型を作ってお魚さんがリファインしたIyokanが解決し、V2TTは現在凍結されている。V2TTは本体となるPythonスクリプトは200行程度しかなく、まぁPoCとしては良かったのではないかと自己評価を下すところである。
書く予定じゃなかったpyFHE
次に作ったのがpyFHEである。こいつは応募当時の予定には存在しなかった。応募当時の予定ではTFHEのライブラリは既存のものを使うことを想定していたので、自前でフルスクラッチするつもりはなかったのである。じゃあなんでこいつが生えてきたのかと言うと、端的に言うと一瞬暇ができたからである。V2TTが一応できてしまったため、コンパイラとCPUの完成を待つ時間が少しだけ生まれた。何もしないのもあれなのと、最終的にはcuFHEと言うCUDAで書かれたTFHEライブラリに手を少し加えることになるだろうという見込みがあったため、そのときに少しはTFHEがわかっていないと困るだろうと考えたのである。それでPython3での実装を書き始め、結局フルスクラッチした上に原論文者の実装には統合されていなかったCircuit Bootstrappingと呼ばれる機能まで実装した。
pyFHEで得た教訓は、Pythonはなんだかんだ言ってやっぱり遅いと言うことである。私が書いたオリジナルの実装では一ゲート処理するのに10秒かかっており、次に見るお魚コンパイルを受けても１秒かかる状態で100倍ほど遅かった。CythonとかNumbaとかあるけれど、結局C/C++が生き残っているのにはやはりそれなりの理由があるのである。
お魚コンパイル事件
お魚コンパイル事件は、pyFHEの実装が知らない間に10倍速くなっていた事件である。お魚さんにpyFHEのコードを渡したら、なぜか10倍速いPythonコードになって返ってきた。Cythonとかを使ったという話ではなくて、numpyが効きやすいようにコードの意味を保ったまま書き換えたとのことであった。実は未だに自分のコードとお魚コンパイル後のコードが意味的に等価なのかどうかよく理解していない。まぁ動くんだからヨシ。
この事件は「お魚さんはコンパイラを書ける」が「お魚さんはコンパイラである」に変化した契機であった。その後お魚さんはTFHEの再実装としてaqTFHEも書いたのだが、そこまでしてもTFHEの原理を理解していないし論文も読んでないとのことであった。コンパイラは普通自分がコンパイルしているソースコードの意味は理解していないので、本当にコンパイラだなぁという気分になるところである。
闇に消えたjlFHE
pyFHEはだめだったが、当時の私はC++を書きたくなかった。C++はベターCだと思っていたし、Cでコードを書くには人生は短すぎるからである。そこでトライしたのがjuliaだったが、私にはjuliaは全然噛み合わなかった。なぜお前はそんなに配列と行列を区別しようとするのだ……
ちなみに未踏後に見つけた別の人が作った実装としてTFHE.jlがある。こいつはMulti-Keyも実装しているらしいのでいつか参考にするだろう。
なぜか速くなったTFHEpp
pyFHEで統合したCircuit Bootstrappingはアルゴリズムレベルでの高速化が期待できる代物で、C++実装でも使いたいものであった。しかし、TFHEの原論文者実装に組み込むのは私には困難なものであった。Cとの互換性を強く意識していたり、やけにアセンブラで書かれたところが多かったり、関数が細かく分割されすぎていたのが原因であろうと思う。読む分には読みやすい方のコードだと思うが、拡張性は低かった。３人の間ではえーでもフルスクラッチするより拡張するほうが早いんでねーという感じはあったし私もそうかもしれないとは思っていたのだが、pyFHEができていたしできなくはないはずだしそっちのほうが楽しいだろと思って年末年始に黙って作り上げたのがTFHEppである。そういうことが許されるのが我々のチームの良いところでもあり悪いところでもあった。つまり、お互いの専門範囲がよくわかっていない(プロセッサはできるかもと前に述べたが、それは理論的にはというレベルであってコンセプトはともかく実装に口出しできるほどわかっているわけではない。スーパースカラ何もわからん)ので結局のところ担当者が取り掛からないアイデアは実行されず、最終決定権はそれを作る人間にあったのである。お魚さんはバス係数が１と何度か言っていたが、まぁマジでそうである。
TFHEppは、拡張性を確保するためにアセンブラを極力廃し、C++17の機能も積極的に取り入れたつもりである。その結果、何故か10%ほど原論文者実装より速くなった。どうやら各種パラメータをランタイムに決めるのではなくconstexprにしたことでコンパイラの最適化が効きやすくなったことが原因だったらしい。しかし、FFTをする部分のコードは原論文者のアセンブラコードのほうが速く、そこはそのまま用いた。コンパイラによる最適化がアセンブラに勝つ場合とその逆を両方見れたので実に良い経験だったと思う。
C++はベターCではありません。
不備の多かったcuFHE
前に述べたように、CUDA版実装であるcuFHEを用いるのは既定路線であった。ので、TFHEppを書いた後にこれをいじってみたのだが、不備が多かった。結局、足りないゲートを生やしたりするのに自分たちでforkしたver.を使うことになった。いつのまにかみかんの手によってMultiGPUにも対応した。ゲートのテストはお魚さんの手によってテンプレートの塊になった。あんな機能があるとは……
CUDAを書くのは高校時代からの夢だったので楽しかったのは間違いない。一つ夢を叶えたのである。
計画だけされたFFHEE
cuFHEはNTTを使っている都合で、Circuit Bootstrappingを導入するのが難しかった。そこでFFTを使ったバージョンを作ろうと計画されたのがFFHEEである。未踏期間中は結局ほぼ何もできなかったのだが、現在製作中なのでそのうちできると思う。果たしてスピードは出るのだろうか。
コミュニティについて
まぁ最後の方は適当な感想を書き残そうと思う。なんかTwitterで未踏コミュニティが云々みたいな話があったが、私はあんまりそういう意識はなかった。近い順にみかんとお魚さん、首藤PM、未踏事務局の方と同期であるBI-SGXのSさん、その他(まぁ細かく言えばもちろんその中でも明確な順番はあるけど)ぐらいの感じでコミュニティっていう気分はなかった。これは我々のプロジェクトが他の人にはアドバイスしづらい(準同型暗号なんてやっている人間はほとんど居ないし居てもまたその中でもTFHEは傍流なので)こともあって、放置されぎみだったこともあるだろう。まぁ、我々の場合は放置されてても自分たちで学習して好きにやっていたのでありがたかったが。PMと事務局の方にはお世話になりました。
採択は運です
どちらかといえば未だに決定論者の人間が運なんて言葉を言うのはアレなんですが、確率ロボティクス的な気分で言うとPMのことを知っているパターンなんてまずありえないので運というしかないでしょう。先にも述べましたが、VSPは採択時点で内容を理解していた人はおらず、首藤PMも正直これ大丈夫なのかなという思いもある中で採択されたと言っていました。未踏はまさしく未踏領域に踏み込むことを期待しているわけですので、そういうテーマも採択されることはあります。しかし同時に、わかっていて選んでるわけでもないのである程度乱択的な側面があるのは否めないでしょう。落ちたとしてもあなたのテーマが悪いとは限りません。
過去のテーマを参考にするかどうかですが、我々の場合過去に独自CPUとコンパイラをやった例があったので、今回はある意味そのスーパーセットになるので大丈夫だろうという考えと、FFTをやった例を知っていたので基礎研究的なものも許されるだろうという考えはありました。
大抵のアイデアはあなたが最初ではありません
人間の頭の個体差なんて大してありません。能力の根源はほぼ間違いなく才能ではなく環境です。少なくとも、その信念が今日の公教育制度の根底にあるものです。人間の体の構成なんて認知革命の頃ぐらいから大して変わらないんですから(もちろん、性別で内臓の種類が変わったり東洋人と西洋人で尻の穴の位置が違うとかそういう話はありますが、認知機能に大きな影響を与えるほどのものとは思えません。だからこそ今日の社会があるはずです)同じような環境に生きていれば同じような発想にたどり着くものです。あなたの特別な経験から来たとかでない限り、あなたのアイデアはおそらく他の人も思いついているはずです。実際、採択されてから同様のプロジェクトが公表されて方針転換を迫られた例は見ていますし、終了したタイミングの前後で公表された例もあります。VSPも、BrainfreezeとArcaneVMといったBrainfuckを動かせるCPU的なものをTFHE上で動かすものはプロジェクトが開始してから発見されました。(なぜそんなにBrianfuckが好きなのか……)
そういうことがあったとしても、柔軟に対応して続けられるかというのが大事だと思います。
かなりの実装力が要求される
まず言っておきますが、私はどちらかといえば理論屋です。実装力ではとてもじゃないですが少なくとも現状みかんやお魚さんには勝てません。お魚さんは逆に自分は実装の人間と評してます。なぜそれを先に前置きするかと言うと、未踏で要求されている実装力のレベルはみかんやお魚さんレベルだと思うからです。
先に述べたように、大抵のアイデアは他の人も思いついているはずです。では、なぜそれがやられていないように見えるか？その原因は多くの場合労力にあります。VSPも、準同型暗号ライブラリとCPUとコンパイラとISAと準同型暗号評価エンジンとUIを作ってつなげればそれで終わりで、考えるのは簡単です。しかし、実装には期間一杯かかってそれでも完全ではありませんでした。もしあなたが本当の意味でノーベルなアイデア(多くの人は自分のアイデアがそうだと思い込みがちな気はしますが)を持っているのでなければ、あなたのプロジェクトをノーベルにするのは実装力です。
首藤PMには、３人とも一人で一つの未踏プロジェクトができるレベルだという評を頂いたことがありますし、それは大変光栄ではあるのですが、まぁ正直私に関してはそれは過大評価だろうなと思っています。私は何をするにも行動せずに考えすぎるところがあるので、準同型暗号みたいな理論と深く関わる部分だけを作るならまだしも、他の部分までやるのは明らかに実装力不足で時間が足りなかったでしょう。また、準同型暗号のような理論的なところをじっくりとできたのは、他の二人が目に見える進捗を出し続けてくれたので、進捗の見えづらい基礎的なことをやっていてもプロジェクトとして進捗を疑われるような事態になることはまずなく、同時に自分も進捗を報告できるようにしたいという考えがモチベーションになったところがあります。私は飽き性なところもあるので、一人だったら３ヶ月位で飽きていたかもしれません。
本当に、一人で未踏プロジェクトを完遂できる人間はすごいと思います。おそらくですが、首藤PMから過大な評価を頂いたのは、3人で合計してみるとPMの中での未踏プロジェクトを完遂できる最低ライン的なものの３倍より大きく見えたからなのでしょうが、そのラインはどこか一要素でも最低を割ると意味のない基準で、それを一人で満たせるというのはすごいなぁと思います。
あなたのアイデアはあなたの子供です
最後に、どこで見かけた言葉だったか忘れたけれど、期間中にたまに思い出したのがこの言葉です。VSPを理論的な意味で本当に理解していたのはおそらく期間中では、下手すると今でも私だけで、VSPのここが既存研究と同じなのではないかとか、こういう脆弱性や欠陥があるのではないかという指摘が合った時に、VSPというアイデアを守れるのは私だけだろうという考えがときたま頭に浮かんでいました。
あなたがそのアイデアにどれだけの労力をかけたかなんてどうでもよいのです。自分の子供にかけた食費やら教育費やらの額が直接子供を助けるなんてことはないでしょう。与えた食事による免疫力の強化や学校で得た知識が守るのであって、そこには金額からの変換効率があり、ゼロであることもありえます。そのアイデアに思い入れがあるなら、適切なところに適切な労力を投入できるのはあなただけです。
まぁ、もちろん本物の生きた子供ではなく比喩なので、アイデアを放棄せざるを得ないことはよくあることです。そういうときには、どうにかして一部だけでも延命できないか、あるいは納得して放棄できるように十分に検証するのが、せめてもの行いだと思います。
長くなりましたがこんな感じで備考録としては十分かと。