a16z、Lattice Joltを発表：証明速度が3倍に、量子攻撃にも耐性

翻訳：深潮 TechFlow

深潮 TechFlow による解説： zkVMは常に「証明が遅すぎる、サイズが大きすぎる」と批判されてきましたが、a16zは今回、楕円曲線を格子暗号に置き換えることで、証明速度を3倍に高速化し、証明サイズを100KB未満に抑えました。これは、従来の楕円曲線方式を速度で凌駕する唯一の耐量子方式であり、検証のオンチェーンコストやプライバシーアプリケーションに直接的な影響を与えます。

本日、私たちはLattice Joltを正式にリリースします。これは、私たちのオープンソースzkVM（ゼロ知識仮想マシン）の最新バージョンです。Joltは元々、現時点で最速かつ最もシンプルなzkVMであり、そのアーキテクチャは変わりません。しかし、基礎となる暗号が変更されました。楕円曲線から格子暗号へと置き換えられました。この1つの変更により、同時に3つのことがもたらされます。

Joltが耐量子安全性を持つようになりました。
proverとverifierの速度が2～3倍高速化しました。
Lattice Joltは、すべての耐量子zkVMの中で最も短い証明を実現します。現在は100 KB未満ですが、今後さらに圧縮可能です。証明をチェーンに記録したり、ネットワーク経由で転送したりする場合、証明が小さいほど検証コストが低くなります。

これらの特性は、zkVMのあらゆるユースケースをカバーします。同じproverで、GPU上では数十億のCPUサイクルを処理でき、スマートフォン上でも数百万サイクルを証明できます。どちらの場合も、開発者は通常のプログラムを書くだけで、専門知識が必要な回路を手作業で記述する必要はありません。これが、Joltが「万能SNARK」と呼ばれる理由です。

しかし、より大きなストーリーは、Lattice JoltがSNARKの設計と採用に与える意味です。現在、実運用されている耐量子SNARKのほとんどすべてがハッシュベースです。Lattice Joltは、格子ベースのSNARKがより高速でコンパクトになり得ることを証明しました。デジタル署名も同じ変遷をたどっています。ハッシュ方式は保守的な選択肢ですが、格子方式こそが世界が大規模に導入しつつあるものです。SNARKもこの道を辿ると予想しており、このブログ記事の後半でその理由を説明します。

楕円曲線を格子に置き換える

Joltが以前使用していた多項式コミットメント方式はDoryと呼ばれ、システム全体で楕円曲線暗号に依存する唯一のコンポーネントでした。Lattice JoltはDoryをAkitaに置き換えました。Akitaは、Module-SIS格子仮定に基づく新しい多項式コミットメント方式です。Lattice Joltは、この十分に研究された標準的な仮定に基づき、完全な128ビットセキュリティを目標としています。

Module-SISとその兄弟であるModule-LWEは同じ仮定のファミリーに属し、世界のデジタルインフラはこのファミリーへと移行しつつあります。これらの仮定は、デジタル署名標準ML-DSAだけでなく、鍵確立標準ML-KEMも支えており、後者はすでに世界で最も広く展開されている耐量子プリミティブです。

Akitaの開発と実装は、LayerZeroの研究者とエンジニアが主導し、カーネギーメロン大学、南カリフォルニア大学の研究者、およびa16z cryptoのエンジニアリングおよび研究チームが共同で参加しました。

Lattice Joltがより高速な理由

Lattice Joltは耐量子安全であるだけでなく、置き換え対象となった楕円曲線バージョンよりも高速です。

高速化の主な理由は単純です。楕円曲線ではJoltは256ビットの体上で動作する必要がありましたが、格子暗号では128ビットの体で同等のセキュリティレベルを達成できます。Jolt proverの主要な処理は体要素の乗算（本質的には巨大な数値の乗算）であるため、数値のサイズが半分になると、乗算ごとに数倍高速化されます。

Doryを使用したJoltはすでに高速でした。前回のパフォーマンスアップデートでは、JoltはノートPC上で1秒あたり約70万のRISC-V（RV64IMAC）サイクルを証明でき、その後の最適化により、楕円曲線版のJoltは1秒あたり100万サイクルを超えました。

Lattice Joltは、同じマシン上で1秒あたり200万サイクル以上を証明できます。

過去6ヶ月の大半は、Akitaの開発とJoltへの統合だけでなく、Joltコードベースの全面的な書き換えにも費やされました。Joltは以前からGPU上で良好に動作していましたが、今回の書き換えにより、GPU実装の構築と最適化が容易になりました。

最初の成果はApple Metal実装であり、Appleハードウェアに大きな高速化をもたらしました。（Metalは、MacBookやiPhoneなどのデバイスに搭載されたGPU上でコードを実行するためのAppleのフレームワークです。）

GPUアクセラレーション版Lattice Joltは、MacBook上で1秒あたり1000万以上のRV64IMACサイクルを証明できます。
純粋なCPU版Lattice Joltは、同じマシン上で1秒あたり200万サイクル以上を証明できます。
さらに、楕円曲線版Joltも、Metalを搭載したMacBook上で、現在1秒あたり約400万サイクルで動作します。

つまり、今回のリリースにより、MacBook上のJoltは、1秒あたり約100万サイクル（楕円曲線版、純粋CPU）から、1000万サイクル以上（格子版、Metal使用）へと向上しました。

これらの数値を大局的に見てみましょう。4年前に初めてSNARK proverのオーバーヘッドについて記述した際、計算の証明は直接実行するよりも数百万倍高価でした。Lattice Joltはこのオーバーヘッドを約1万倍にまで削減しました。これで終わりではなく、エンジニアリングおよびプロトコルレベルの最適化の余地はまだ残っています。

証明サイズはproverの速度と同様に重要です。100 KB未満というLattice Joltの証明は、他の耐量子zkVM（200 KB以上から約600 KB以上まで様々）よりもはるかに小さくなっています。

格子に変更したことで、Joltの元々優れていたメモリ使用量もさらに改善されました。proverのメモリ使用量は、サイクルあたり約300バイトから200バイトに減少しました。これは、スマートフォン上で数百万のRISC-Vサイクルを証明できることを意味します。

近日公開予定の関連論文では、Lattice Joltにゼロ知識性が追加される予定であり、これはプライバシーアプリケーションに必要な特性です。

なぜハッシュではなく格子なのか

長年にわたり、SNARKコミュニティの注目（および実質的にすべてのプロダクション導入）は、耐量子安全性への道筋としてハッシュベースSNARKに集中してきました。

しかし、LaBRADOR、Greyhound、LatticeFold、SuperNeo、そしてAkitaの直接の前身であるHachiを網羅する、格子SNARKと格子コミットメントに関する一貫した研究の流れも存在してきました。Lattice Joltはこれらの研究に基づき、高性能zkVMアーキテクチャに格子コミットメント層を導入し、同時に、格子ベースSNARKが速度とコンパクトさにおいて比類のないものであることを証明します。

これは驚くべきことではありません。前述の通り、同じパターンがデジタル署名でもすでに発生しています。

暗号学者は多くの仮定に基づいて署名を構築してきました。ハッシュ署名は通常、最も保守的な選択肢と見なされます。そのセキュリティ仮定は単純で古いからです。しかし、世界は主に格子署名へと向かっています。なぜなら、それらはより短く、より高速だからです。

ML-DSA署名は約数KBです。
NISTが標準化したハッシュ代替案であるSLH-DSAは、数倍大きくなります。
暗号化と鍵交換については、状況はさらに明確です。ハッシュ方式の選択肢はなく（不可能であることが証明されています）、耐量子導入は圧倒的に格子ベースです。ML-KEM（NISTが2024年に確定した主要な鍵確立標準）は、すでに主要ブラウザやコミュニケーションアプリにデフォルトで導入され、ネットワーク上の多数のTLS接続で使用されています。

SNARKと署名の間の類推は表面的なものではありません。デジタル署名は本質的に、許可されたメッセージに対する秘密鍵の知識の証明です。SNARKはこのパラダイムを、狭いステートメントから任意の計算へと拡張します。したがって、SNARKの長期的な暗号の展望が署名や暗号化のそれと完全に異なるのであれば、それは奇妙なことです。

ここには、明確にすべき誤解もあります。ハッシュSNARKは、「ハッシュ関数のみに依存する」ため、保守的な耐量子選択肢としてしばしば語られます。これは、基礎となるハッシュ関数が非代数的である場合にのみ当てはまります。

現在、ほとんどのハッシュベースSNARKの導入は、ハッシュが正しく評価されたことを低コストで証明するために、SNARKフレンドリーな代数ハッシュ構造（Poseidonなど）に依存しています。これは、再帰（ここでは、有効なSNARK証明を保持していることの証明を指します）にとって特に重要です。これらの構造は標準的なハッシュ関数よりも多くの構造を持ち、その暗号解析は未熟です。

簡潔に言えば、私たちは代数的ハッシュ関数の安全性に確信を持っていません。それにもかかわらず、それらは現在、プロダクショングレードのSNARKシステムで広く使用されています。（ただし、進歩の兆候があります。イーサリアム財団は最近、それらの使用を廃止することを発表しました。）

代数的ハッシュは、導入済みのハッシュベースSNARKにおける唯一の隠れた仮定ではありません。多くのシステムは歴史的に、完全に証明された限界ではなく、推測的なproximity-gap限界を使用して具体的なセキュリティレベルを設定してきました。これらのうち、最も強力であると考えられていた限界のいくつかは、後に誤りであることが証明されました。

たとえ上記の推測に基づくハッシュベースのSNARKを避けたとしても、そのセキュリティ目標は通常128ビットを下回ります。なぜなら、完全な128ビットのセキュリティを実現するには、顕著なパフォーマンスオーバーヘッドが生じるからです。なぜでしょうか？ハッシュベースのSNARKは128ビットの体上で128ビットのセキュリティを達成できません。その信頼性誤差がn/|F|でスケーリングするためです。ここでnはおおよそ証明されるステートメントの規模、|F|は体のサイズです。したがって、128ビットの体上で10億ステップのステートメントを証明すると、約30ビットのセキュリティが失われ、100ビットを下回ります。対照的に、Lattice Joltの信頼性誤差はlog(n)/|F|でスケーリングするため、同じ体上でほぼ完全な128ビットのセキュリティを保持します（わずかなlog(n)の損失は標準的な技術で回復可能です）。

皮肉なことに、「保守的」な後量子選択肢として宣伝されているシステムの中には、実際には代数ハッシュ関数、推測的なproximity-gap限界、そして128ビット未満の目標セキュリティレベルに同時に依存しているものがある。したがって、ハッシュベースの SNARK は重要な方向性ではあるが、多くの人が思っているような低リスクの選択肢に自動的になるわけではない。

一つの Jolt、三つの基盤：曲線、格子、ハッシュ

私たちは一貫して、Jolt は単一の暗号学的基盤に縛られるべきではないと考えてきた。曲線ベース、ハッシュベース、格子ベースの成熟した高性能 SNARK を持つべきである。異なる仮定と性能特性が異なるシナリオに適する。

しかしデジタル署名を参照点とすると、格子ベースの SNARK が最も広く展開される後量子選択肢となるだろう。

Jolt はこの転換において異例の優位な立場にある。当初の Jolt 設計は、楕円曲線がコミットメントに特に有用な特性を活用した。これには疎なベクトルへの高速コミットメントが含まれる。格子コミットメントも同じ特性を持つ：ベクトルのほとんどの要素がゼロまたは小さい場合、ベクトルへのコミットメントコストは低く、Jolt はほぼそのようなベクトルにのみコミットする。この特性により、Jolt の残りの部分を変えずに Dory を Akita に置き換えることが可能になる。

私たちはハッシュベースの Jolt バージョンも構築する。しかし曲線ベースおよび格子ベースの Jolt と比較して、ハッシュベース版は空間効率が悪く、証明が大きく、さまざまな複雑な問題が存在する。これは最も有望なハッシュベース SNARK が二進体上で動作するためである。この数体系はハッシュ評価の証明に便利だが、CPU の演算方式とは一致しない。この不一致により、通常の CPU 乗算の証明が高コストになる。それでも、エコシステムはデジタル署名分野と同様に、各主要仮定族の下で zkVM を持つべきである。

万能 SNARK

Lattice Jolt は構築者が zkVM に求めるすべての要件を一度に満たす：後量子、透明、高速、コンパクト、そして空間効率が高い。LaBRADOR から Hachi への格子 SNARK 研究路線を本番級 zkVM に持ち込みながら、当初 Jolt を高速にした利点を一切放棄していない。

私たちの目標は、最も高性能な zkVM を誰でも使えるようにオープンソース化することだけでなく、特定のアプリケーション向けに SNARK を手動でチューニングする必要性を大幅に排除することにある。これは Jolt が手動チューニングされた証明器と同じ速さであることを要求するものではない。それは不可能な目標であり、CPU がすべてのタスクで専用 ASIC に匹敵することを要求するようなものだ。Jolt が許容可能なユーザー体験を提供するのに十分な速さであればよい。

クライアント側証明に関連する「小さな」ステートメント（今日、手動最適化回路がこれらのシナリオで支配的である）にとって、重要な基準はスマートフォン上で約1秒以内に証明を生成することである。Jolt はすでにこれに近づいており、さらに多くの加速案が進行中である。

格子 SNARK の時代はすでに到来している。