STARKを用いてRISC-Vの実行履歴証明を行うフレームワークRISC Zeroの紹介

はじめに

この記事では、RISC Zero¹という、知識証明フレームワークについて紹介します。

RISC Zeroとは

RISC ZeroはRust製のSTARK²証明フレームワークです。Rustで書かれたプログラムをRISC-Vのアーキテクチャ向けのバイナリにコンパイルすることができます。そのコンパイルされたプログラムをzkVMという仮想マシン上で動かすと、メモリとレジスタの内容がCPU命令によって遷移していく巨大なテーブルを作成することができます。
そのテーブルの遷移の整合性を確認することで、STARKによるプログラム実行知識証明を行うことができます。

これを説明した以下画像は³から持ってきたものです。

ゲスト環境（実行を証明したい対象のプログラム、RISC-Vバイナリ）と、ホスト環境（実行を証明するときに外部からヒント（プライベートインプット）を与え、証明を受け取るためのプログラム）に分かれています。チュートリアルは 公式サイト⁴にあるとおりです。

これを説明した以下画像は ⁵から持ってきたものです。

また、STARKの検証回路自体を一つのプログラムとみなして、そのプログラムを検証コストの低いGroth16などのSNARKで証明することが可能です⁶。そのようにすれば、結果的にRISC-Vのコードの実行証明をEVMなどオンチェーン上で検証することができます。

他フレームワークとの違い

Cairo

Cairoはそのアーキテクチャ仕様の制約から、検証者が自分自身で公開インプットとプログラムを用意することができず、証明者から提供される公開インプットを信頼する必要があります⁷。

すなわち、Cairoでは公開インプットがファイルとしてプログラム本体とは分かれて出力され、そのファイルを入力として検証することができるものの、その公開インプット自体は人間が読める形式にはなっていません。公開インプットを人間が読める形式から変換されたものであると確信するためには、以下のいずれかが必要です。

1. メモリ上に展開される情報である公開インプットをパースするプログラムによって、検証者がプログラム全体を実行せずに独立して公開インプットの整合性を確認できるようにする
2. 検証者がプログラム全体を実行して、公開インプットの整合性を確認できるようにする

1については現状不可能ですが、⁸のCairo VM側の仕様変更で実装される予定とのことです。

2については現在実行可能な唯一の方法ですが、これはSTARKの検証者がプログラム全体を実行する必要があることになり本末転倒です。「手元で再計算を行うことを前提として、スマートコントラクト上で同じことを実行・検証しているのを事後的に確認したい」という需要があれば、役に立つ可能性もあります（ユースケースはよくわかりませんが）。

RISC Zero

RISC Zeroでは、ゲストプログラムとしてコンパイルされたものが公開インプットの全てであり、そのプログラムが正常に動作する入力が与えられたかどうかは、証明者から提供される入力を信頼せずに決定できます。証明(receipt)にはゲストプログラムがzkVM内部でコミットした情報も記録されており、プログラム全体を実行しなくても検証者は最終的に出力される値の整合性を調べることが可能です。

SP1

SP1⁹もRISC Zeroと同様にRISC-VアーキテクチャにコンパイルしたRustのコードをzkVM上で動かしてSTARKの実行履歴を作る仕組みのようです。RISC Zeroよりも証明の実行速度を高速化したものとのことです。

RISC Zeroの応用とその限界

STARKは知識証明の一種ですが、そもそも知識証明が必要とされる場面は多くありません。なぜならば、知識を証明したいならば、証明者は単にその知識を検証者に伝えるだけで十分であることがほとんどだからです。ゼロ知識証明であれば応用範囲は広いですが、SNARKの方ではより検証速度が速いGroth16のようなアルゴリズムが知られています。STARKでは証明者側が多大な計算量を負担することで検証者側がそのコストを負担しなくてすみますが、そのような制約が役に立つ場面は一般的なシステムにおいてはあまりないのが実情です。

STARKを機能として応用できる場面は大きく分けて2つ想定できます。

1. 暗号通貨のフルノードの高速同期
2. 暗号通貨のサイドチェーンや、他チェーンとのブリッジをトラストレスに行うための証明

1についてはCairoよりもRISC Zeroの方が適していそうです。理由としては、フルノードの高速同期を行うために必須なCairoのヒント機能がCairo v0にしかなく、Cairo v0はCairo v1に置き換えられてサポート対象外になる予定であるためです。ただ、いずれも巨大なデータを読み込んでパースするのには時間がかかるため、現状ZeroSync¹⁰の目指しているフルノードの完全検証＋高速同期を行うことは難しい可能性があります。

2についてはCairo, RISC Zeroいずれも利用可能なのですが、そもそもトラストレスなサイドチェーンを作るにあたって、チェーンのフォークが起きる可能性などを考慮すると、単純にzkSNARK, zkSTARKのようなゼロ知識証明を導入したところでスケーリング問題が解決しない可能性が高いと考えられます。これはデータ可用性問題（data availability problem）¹¹¹²の問題として知られています。

すべてのサイドチェーンは外部の状態変更を伴い、かつその状態変更の結果の候補のすべてを事前に予測することができません。さらに、状態Aから派生しうるB,Cの状態が相互に矛盾しているということがありえます。いずれかの状態からコインをメインのチェーンに戻した後、他の状態からコインをメインのチェーンに戻そうとする構成が可能であれば、それらの矛盾を検証する必要があります。
そして、その矛盾が検証できるためには、メインのチェーンにおいて外部の状態を知ることが必要であると思われるのですが、例えば外部の状態のコミットメントをメインのチェーンにおいて許可してしまうと、メインのチェーンではコミットメントが真正なものか検証できないというジレンマが発生してしまいます。

ただ、現在は BitVMのような完全トラストレスではない1-of-n型のトラストにより制約を緩和した手法が出てきているので、同様に1-of-n型のトラストによってサイドチェーンを構成できる可能性はあるかと思います。

参考文献