ランダムオラクル付きSNARG/PCP の非存在証明はビットコインにどう関係するか？

はじめに

このブログではこれまでにビットコインの台帳の計算履歴の縮約可能性について何回か解説してきました。SNARK¹、STARK²、SNARKとSTARKの組み合わせ³などです。
そのメリットは上記の記事でも解説しているように、IBD(Initial Block Dowload; 初期ブロックダウンロード)時間の短縮と、それに伴うネットワーク分散化の改善です。現状新しくネットワークに参加しようとすると、2025年8月時点で664GBのデータをダウンロードして処理する必要があり、新しくノードを立ち上げようとするユーザーにとっては負担になっています。
このデータダウンロード時間を改善すると期待されているのがSTARK,SNARKといった計算履歴の証明を行うプロトコル(STARKは厳密にはSNARGではないが、以下まとめてSNARGと呼ぶ)です。
実際にZeroSync⁴, Shinigami⁵などのプロジェクトはチェーンヘッダー部分のSNARGと証明を完成させるなど一定の成果を挙げています。

しかし、チェーンヘッダー部分のSNARG証明と、チェーン本体のSNARG証明では困難さが大きく違います。具体的にはマークル木等の計算で大量のSHA256関数をチェーン本体で使用しています。SHA256関数をSNARGで算術化して証明をしようとすると非常にコストがかかることが知られています。そのためチェーン全体を証明することが現実的ではないという問題があります。以下は概算です。最大4000個程度のトランザクションがブロック内に存在するため、署名検証と各種ブロックのハッシュ計算等のコストを考えると、マークルツリー計算（最低4000x2）とトランザクションのECDSA署名検証(4000)を処理する必要があり、最低でも（スクリプトの計算実行証明やUTXOセットまわりの計算を除外しても）ブロックヘッダー証明の10000倍以上の証明コストがかかると思われます。

上記のように単純にSHA256関数を算術回路に変換する証明は高いコストがかかるので、何か他の方法を探したくなります。問題の本質はSNARGの内部で行われるSHA256計算証明が重いということにあるので、SHA256計算を外部で行うようなSNARGの亜種を考えてみます。すなわち、外部ランダムオラクル呼び出しを行ったということだけを記録して、オラクル自体の計算過程は証明に含めないようなSNARGがもし存在すれば、ランダムオラクル呼び出し・計算自体の整合性確認はSNARG証明の外部で行うことで、証明コストを軽くできるはずです。

複雑性クラスCの相対化

一般に複雑性クラスCに対してオラクルOを呼び出せるようにした、新しい複雑性クラスを C^Oのように書き 「オラクルOで相対化されたクラスC」や「オラクルO付きクラスC」のように呼びます。ここで考えたい問題は、「ROMで相対化したにも関わらず、SNARG同様に証明・検証を行うことができるクラス\text{SNARG}^\text{ROM}が存在するかどうかです。そして、先に結論を言ってしまえば、このようなクラスで非自明な計算を行えるようなものは存在しないというのが論文⁶の成果です。また、同様にPCP⁷でもそのような証明・検証が行えるようなクラスは存在しないことが示されています⁸。

ランダムオラクルアクセス付きSNARGの証明が難しい直感的な理由

正直、PCPやSNARGは人間の常識や直感と大きくかけ離れた世界なので、あまりこのような説明に意味はないかもしれないですが(SNARGやPCPが実現可能ということ自体が全く直感的ではないですよね？)、難しい理由の説明をしてみます。

(算術化されていない)ランダムオラクルがn回使われるような計算を考えてみます。SNARGの性質から、非自明な検証を行いたいのであれば、n回の実行証明は n回よりもさらに少ない回数で検証できる必要があります。しかも、検証者はn回の実行のうち1回も間違った計算を見逃さないようにしなければなりません。
もし算術化してもよければ、既存の知られた手法によってオラクルの中身を算術回路に変換し、n回よりも少ない回数でまとめて計算検証することができます。しかし、前提から言って算術化は禁止されているので、オラクルをオラクルとしたまま、n回より少ない回数でまとめて検証する必要があります。もしもランダムオラクルではなく、単純なオラクルであり、オラクルの実行1回目と2回目に何らかの入出力の関連性が見いだせるのであれば、まとめて検証することができるかもしれません。しかし、ランダムオラクルの性質上、入出力の関連性を見出すこともできないため、「まとめて検証」というのは難しそうに見えます。
これが算術化無しで、非自明な計算量では直感的に難しそうな理由です。論文⁶ではこの説明をより厳密化して、不可能性を証明しています。

AROM(算術化ランダムオラクル)等を使用した効率化

上記の通り、単純にROMをSNARGの外で検証する方向性は不可能であることが証明されてしまいました。
しかし、単純に値のハッシュ値を返すようなROMを外部に置くのではなく、さらに補助的な情報を返してくれるようなオラクルであればどうでしょうか。

署名付きROM (Signed ROM; SROM)⁹と呼ばれるオラクルは、ランダムオラクルの値に加えて、オラクルが正当性を保証してくれる署名を付与して返却してくれます。これであればランダムオラクルの値が正しいかを、署名部分を見るだけで判定できることになります。しかし、現実世界でSROMを実現する方法はTEEを使う方法以外知られていません。すなわちSROMについては署名者に対する信頼が必要であり、現状採用が難しいです。

また、SROMとは別のアプローチで、LDROM (Low Degree ROM; 低次ROM), LCROM (線形符号ROM; Linear Code ROM)¹⁰と呼ばれるものがあります。これは署名を付与するような仕組みではなく、裏側で一貫性を確保できているかを確認するためのバックドアがついたROのようなものなのですが、現実世界で実装する方法が知られていません。

さらに AROM¹¹というものも存在します。AROMはランダムオラクルの出力に加えて、そのランダムオラクルを計算する過程のデータを返してくれるものです。例えばsha256をランダムオラクルに見立ててAROMを実行すると、sha256の計算過程も同時に返してくれます。さらに、計算過程が正しいかどうかを判定できる関数を返してくれます。SROMやLDROMよりは現実味がありますが、まだ実際のAROMを実装したという話はありません。

上記のSROM, LDROM, AROMについて、これらのオラクルアクセスを許可したSNARGが理論上は可能であることが知られています。

単純なROMをオラクルとするのではなく、ROMに追加情報を与えたものをオラクルの出力とするような方向性であれば、今後も証明生成時間を削減できる可能性がありそうです。

参考文献