STARKの原理

STARKとは

STARK(Scalable Transparent ARgument of Knowledge)は証明システムの一種です。証明システムとは、ある数学的なステートメント、例えば「フィボナッチ数列の第$32$項は$2178309$である」を検証者に納得させるために証明者と検証者の間で行うプロトコルのことです。STARKは証明システムの中でも以下の特徴を持っているので、頭文字を取ってSTARKと名付けられました。

• Scalable: ステートメントを直接計算するのに必要な時間を$T$としたとき、証明の生成時間は$\mathcal{O}(T \log T)$であり、検証時間は$\mathcal{O}(\log T)$である
• Transparent: Trusted setup(信頼できる第三者による事前のセットアップ)を必要としない
• ARgument of Knowledge: ある知識を持っていることの証明ができる

Scalableは証明と検証が比較的高速で実行できることを意味します。Transparentは、zk-SNARKで必要であったtrusted setupが必要ないことを意味します。最後のArgument of Knowledgeは、単なるステートメントだけでなく、「私は〇〇という条件に当てはまる解を知っている」などの知識の所有に関するステートメントを証明することができることを意味します。

STARKとSNARKの比較

類似の証明システムである SNARK(Succinct Non-interactive ARgument of Knowledge)と比べると、trusted setup を必要とせず、健全性(偽装証明ができないこと)がハッシュ関数の安全性のみに依存するという長所があります。ハッシュ関数の安全性は量子コンピューターで破られないと信じられているため、STARKは量子耐性を持つと考えられています^[1]。一方で、一般的に SNARK よりも証明のサイズが大きく検証コストが高いという短所もあります。なお SNARK について馴染みのない方は、zk-SNARKs の原理をおすすめします。

また、SNARK は任意の計算に適応できる一方、STARK は繰り返しの構造がある計算(for ループを回し続けるようなもの)でないと非効率的になってしまうという問題もあります。一方で、そのような繰り返し構造のある計算においては、STARKのほうが効率的に実行でき、またループ上限を設定せずに実行できます。

VM(仮想マシン)は状態遷移の for ループで実装されており、またループの上限は存在しません。従って STARK は VM の証明に向いており、近年 zkVM の文脈で注目を集めています。

STARKの概観

フィボナッチ数列の第$n$項を証明するのを例にとって、STARK の証明の流れを説明します(図)。ステートメントを証明するのに必要な中間状態(フィボナッチ数列の場合は、初項から第$T$項までの値)を$[a_0, \ldots, a_{T-1}]$とし、これをtraceと呼びます。この trace をある多項式$C(X)$に変換し、

ステートメントが正しい$\leftrightarrow$多項式$C(X)$は多項式$Z(X)$で割り切れる

という問題に変換します。ここで$Z(X)$は既知の、簡単に計算できる多項式です。この多項式によるステートメントの表現をAIR(Arithmetic Intermediate Representation)といいます。

多項式$C(X)$は多項式$Z(X)$で割り切れるということは、ある多項式$D(X)$が存在して$C(X) = D(X)Z(X)$が成り立つことを意味します。

検証者と証明者は次のように対話を行います。

検証者はランダムな値$x$に選び、証明者に送ります。証明者はその$x$に対する$C(x)$と$D(x)$を送り返します。検証者は$C(x) = D(x)Z(x)$が成り立つか検証します。この操作を複数繰り返したのち、検証者が「$C(X)$は$Z(X)$で割り切れる」ことに納得したらステートメントを受け入れます。

このように検証者が送信した値に基づいて証明者が値を送り返す証明系のことをIOP(Interactive Oracle Proofs)と呼びます。また、検証者が公開のランダムな値を証明者に送るプロトコルをPublic Coin Protocolといいます。

STARK はこのように IOP による対話式証明ですが、public coin な IOP はFiat-Shamiar 変換によって、非対話式証明に変換できます。

数学の準備

有限体と群に関して必要な予備知識を解説します。ただ群や体を初めて見る方には説明不足の部分が多いので、適宜他の記事等をご参照ください。

有限体

体とは、(ゼロ除算を除いて)四則演算が定義された集合のことです。体の集合の要素の数が有限であるとき、有限体といいます。$\mathbb{F}_p$は、$p$を素数として$0$から$p-1$までの$p$個の整数からなる集合上に、整数と同じ和算減算積算(の$\mod p$を取ったもの)を入れたものと定義します。除算については、積算の逆演算として定義します。すなわち$x$の逆元$x^{-1}$は、

$$x \cdot x^{-1} \equiv 1 \mod p$$

と定義され、$y/x := y x^{-1}$として除算が定義されます。

例

$\mathbb{F}_5 = \{0, 1, 2, 3, 4\}$であり、

$$\begin{align} &4 + 1 = 0\\ &2 - 3 = 4 \\ &2\cdot 3 = 1 \\ &4/3 = 4 \cdot 3^{-1} = 4 \cdot 2 = 3 \end{align}$$

などと計算されます。

フェルマーの小定理

$a$を素数$p$の倍数ではない整数とすると、

$$a^{p-1} \equiv 1 \mod p$$

が成り立ちます(フェルマーの小定理)。

このことから$x \in \mathbb{F}_p$の逆元は、$x^{-1} = x^{p-2}$であることがわかります。

群

$\mathbb{F}_p^*$を$\mathbb{F}_p$から$0$を除いた集合とします。$0$を除いているので、すべの元に対し逆元が存在します。従って、$\mathbb{F}_p^*$は乗法に関する群と考えることができます。$\mathbb{F}_p^*$の集合としての大きさ$|\mathbb{F}_p^*|$は$p-1$となります。これを素因数分解したときに素数$q$が$r$個含まれているなら、$|H| = q^r$なる巡回部分群$|H|$が存在することが知られています^[2]。巡回群とは、全ての元がある元$g$の冪の形$g^n$で書ける群のことをいいます。なお、$g$を生成元といい、生成元を巡回群の大きさだけ掛け合わせると$1$になります。

$$g^{q^r} = 1$$

すなわち、$H$は$\{g^0, g^1 , \ldots, g^{q^r -1}\}$からなる群になります。$r$を$r = r_0 + r_1$と２つの非負の数の和として表し、$g' := g^{q^{r_0}}$と定義すると$g'^{q^{r_1}}= 1$となります。従って、$H_{q^{r_1}} := \{g'^0, g'^1 , \ldots, g'^{q^{r_1} -1}\}$は$H$の巡回部分群であることがわかります。このことから、$\mathbb{F}_p^*$は$H_{q^1}$から$H_{q^{r}} = H$までの巡回部分群を含んでいることがわかります。

例

$\mathbb{F}^*_5 = {1, 2, 3, 4}$であり、$|\mathbb{F}^*_5| = 2^2$なので、$|\mathbb{F}^*_5|$は大きさ$2^2$と$2^1$の巡回部分群を含んでいます。実際、生成元を$g=3$とした

$$H_{2^2} = \{3^0=1, 3^1 = 3, 3^2 = 4, 3^3 = 2 \}$$

と、生成元を$g'=3^2 = 4$とした

$$H_{2^1} = \{4^0=1, 4^1 = 4 \}$$

が存在します。

Two adicity

STARKでは$q=2$の巡回部分群が好んで使われます。これはSTARKで使われる高速フーリエ変換が大きさが$2$の冪乗の巡回群上で効率が良いためです。上で説明したとおり、大きい巡回群から小さい巡回群を作るのは簡単なので、「大は小を兼ねる」でなるべく大きな$2^r$の巡回群を持つ$\mathbb{F}_p$が好んで使われます。$r$の値を$\mathbb{F}_p$のtwo adicityと呼びます。

STARKNETでは、$p = 2^{251} + 17\cdot 2^{192} + 1$が使われています。この場合$192$がtwo adicityであり、最大で$2^{192}$の大きさの巡回群が利用できることを意味します。

Reed Solomon Code

$T := 2^n$として$T$個の$\mathbb{F}_p$の元$[v_0,v_1,\ldots, v_{T}]$が与えられたとします。有限体$\mathbb{F}_p^*$の部分巡回群$H=\{h^0,\ldots,h^{T-1}\}$を取ってくると、$f(h^i) = v_i \quad (i = 0,\ldots, T-1)$を満たす多項式$f$を構成することができます。$f$は$\mathbb{F}_p$の係数を持つ高々$T-1$次の多項式で、ラグランジュ補間を利用して求めることができます。

$f$の定義域を拡大してみましょう。

($\mathbb{F}_p$のtwo adicityが$n+3$以上なら、)$T$の$8$倍の大きさを持つ部分巡回群$G=\{g^0,\ldots,g^{N-1}\}$, $N = 2^{n+ 3}$が存在ます。ここで$G$の生成元$g$は$H$の生成元$h$と、$h = g^8$という関係を持ちます。$f$の定義域を$G$に拡大して、$N$個の要素からなるベクトル$[f(g^0),\ldots,f(g^{N-1})]$を作ります。これをReed Solomon Codewordと呼びます。

なお、今後$X$は関数の変数、$x$は$X$が取る具体的な値の意味で使うことにします。例えば$f(X)$は$X$の関数であり、$f(x)$はそれに$X = x$が代入されたものです。

例

$\mathbb{F}_5$において$G = \{3^0, 3^1, 3^2, 3^3 \}$, $H = \{4^0, 4^1 \}$と置きます。$[4, 2]$なら、多項式は$f(1) = 4$, $f(4) = 2$を満たす一次多項式$f(X) = 2X + 2$であることがわかります。これを$G$に拡大すると、Reed Solomon Codewordは$[4, 3, 2, 1]$となります。

Merkle Tree Commitment

Commitmentとは大雑把にいうと、あるデータから生成された小さなデータであり、「秘匿性」と「拘束性」を持つもののことを指します。STARKにおいてはこのうち「拘束性」と呼ばれる性質が重要です。これは、データが後から改ざんされていないことを保証する性質です。データのhashを取ったものは拘束性を持ったcommitmentとみなせます。STARKではReed Solomon Codeword$[f(g^0),\ldots,f(g^{N-1})]$のcommitmentが必要で、これは各$f(g^i)$をMerkle treeのleafにセットし、root として出力されたものが commitment になります(図は$N=8$の例)。

また、あるleafの値がMerkle treeにcommitされていることは、Merkle rootとMerkle pathがあれば検証することができます。Merkle pathとは、そのleafからMerkle rootを計算するのに必要なHash値のことです。図は$f(g^4)$(赤色)に関するMerkle path(青色)を示しています。

AIR

フィボナッチ数列の$T$番目の値がある定数$A$であること($a_{T-1} = A$)を証明する場合を例に取り、AIRの構成方法を説明します。説明の都合上$T = 2^n$と置きます。フィボナッチ数列の初項から第$T-1$項までの値を$[a_0, \ldots, a_{T-1}]$とします。これをtraceと呼びます。大きさ$T$の$\mathbb{F}_p^*$の部分巡回群を$H=\{h^0,\ldots,h^{T-1}\}$とし、$P(h^i) = a_i$となる高々$T-1$次の$H$上の多項式$P(X)$を構成します。

フィボナッチ数列の条件式$a_{i+2} = a_{i+1} + a_i$は、$P(X)$で書き直すと

$$P(h^2 X) = P(hX) + P(X) \qquad (X=h^0,\ldots, h^{T-3})$$

となります。このことは$a_{i + 2} = P(h^{i + 2}) = P(h^2 \cdot h^i)$, $a_{i + 1} = P(h^{i + 1}) = P(h \cdot h^i)$, $a_{i} = P(h^{i})$からわかります。

また、フィボナッチ数列の初期条件$a_0 = 1$, $a_1 = 1$と、$T$番目の値が$A$であるという条件$a_{T-1} = A$は、次の式で書き表すことができます。

$$\begin{align} &P(1) = 1\\ &P(h) = 1\\ &P(h^{T-1}) = A \end{align}$$

与えられた$P(X)$がフィボナッチの制約式$P(h^2 X) = P(hX) + P(X)$を満たすかどうかは、$H$上のほぼすべての点でチェックする必要があり、簡潔に証明することができません。そこで、次のようなテクニックを使います。

定義域の拡大

Reed Solomon Codeの節で説明したように、$H$の$8$倍の大きさの巡回群$G$を構成し、$P(X)$を$G$上に拡張します。$G$上の多項式$C(X) := P(h^2 X) - P(h X) - P(X)$を定義すると、フィボナッチの制約式は

$$C(X)= 0 \qquad (X = h^0,\ldots, h^{T-3} )$$

と書くことができます。これはつまり、$C(X)$が$X = h^0,\ldots, h^{T-3}$において根を持つことを意味し、従って$Z(X):=(X-h^0) \cdots (X - h^{T-3})$で割り切れることを意味します。
$D(X) = C(X)/Z(X)$と置くと、最終的に制約式$P(h^2 X) = P(hX) + P(X) \quad (X=h^0,\ldots, h^{T-3})$は

$$C(X)=D(X)Z(X)$$

となります。この形に書き直すことのメリットは次のようになります。

いま$H$上で定義されている多項式2つの異なる多項式$f(X) \neq g(X)$があったとします。$f(X)$, $g(X)$は$G$の8分の7以上の点で異なります。なぜなら、$f(X) - g(X)$は高々次数$T$の多項式で、高々$T$個の根しか持たず、従って$f(X)$, $g(X)$は高々$T$個の点でしか一致しないからです($|G|= 8T$なので全体の高々8分の1の点でしか一致しません)。

「正しい」$C(X)$を「全ての$X = h^0,\ldots, h^{T-3}$で$0$になるもの」、「不正な」$C'(X)$を「$X = h^0,\ldots, h^{T-3}$のうち少なくとも1つの点で$0$にならないもの」としましょう。

$C'(X)$は$C(X)$と8分の7以上の$G$の点で異なっており、従って$C'(x) = D(x)Z(x)$は8分の7以上の$x \in G$で成立しません。このことの対偶を取ると、8分の7以上の$x \in G$で$C(x) = D(x)Z(x)$が成り立つなら、$C(X)$は「正しい」ことがわかります。

8分の7以上の$x \in G$で$C(x) = D(x)Z(x)$が成り立つことは、ランダムな点$x$を数回サンプルしてチェックすれば検証できます。例えば$5$つのランダムな点$x$で$C(x) = D(x)Z(x)$が成り立つなら、$C(x)$が不正である確率はおおよそ$(1/8)^5 = 2^{-15}$となります。このように定義域を拡大することで数回のランダムサンプリングだけで効率的に検証可能になります。

以上の説明では$C(X) := P(h^2 X) - P(h X) - P(X)$と$Z(X):=(X-h^0) \cdots (X - h^{T-3})$を使いましたが、$(X-h^0)\cdots (X - h^{T-1}) = X^{T} - 1$という便利な公式^[3]に合わせて、$C(X) := (P(h^2 X) - P(hX) - P(X))(X - h^{T-2})(X - h^{T-1})$, $Z(X) := X^{T} - 1$とおきなおすと^[4]、$Z(X)$が簡単に計算できるようになります。$Z(X)$は検証者も計算する必要があるので、$Z(X)$の計算コストを下げることは重要です。

境界条件

フィボナッチ数列の初期条件と終条件の式

$$\begin{align} &P(1) = 1\\ &P(h) = 1\\ &P(h^{T-1}) = A \end{align}$$

はまだ残っていました。これらも同様に多項式の割り算の形式に変換します。第一式について$C_1(X) =: P(X) - 1$と置きましょう。これは$X = 1$で根を持つので$X-1$で割り切れます。$D_1(X) := C_1(X)/(X-1)$と置くと、最終的に条件$P(1) = 1$は、

$$C_1(X) = (X-1) D_1(X)$$

と書くことができます。同様に$P(h) = 1$, $P(h^{T-1}) = A$に対応する$C_2(X) := P(X) -1$, $C_3(X) := P(X) - A$と$D_2(X) := C_2(X) / (X - h)$, $D_3(X) := C_3(X) / (X - h^{T-1})$を構成することができます。

これまでのまとめ

以上を総括すると、次のようなプロトコルが考えられます。
$T = 2^{n}$であり、$\mathbb{F}_p$のtwo adicityは$n+3$以上であるとします。

ステートメント:
$a_0 = 1$, $a_1 = 1$, $a_{i+2} = a_{i+1} + a_i$で定義される$\mathbb{F}_p$上のフィボナッチ数列において、$a_{T-1} = A$が成り立つ。

あらかじめ$|G| = 8T$となる$\mathbb{F}_p^*$の部分巡回群$G$を取っておき、$G$の生成元を$g$としたときの$h := g^8$を生成元とする巡回群を$H = \{h^0, \ldots, h^{T-1}\}$とします。

1. 証明者は、$[a_0, \ldots, a_{T-1}]$を計算し、$P(h^i) = a_i$ ($i=0,\ldots, T-1$)なる$H$上の多項式$P(X)$を求める。$P(X)$の定義域を$G$上に拡大し、$P(x)$ ($x \in G$)を各leafとするMerkle treeにcommitする。多項式$Z_0(X):= X^T - 1$, $Z_1(X) :=X - 1$, $Z_2(X) := X - h$, $Z_3(X) := X - h^{T-2}$, $C_0(X) :=(P(h^2 X) - P(h X) - P(X))(X - h^{T-2})(X - h^{T-1})$, $C_1(X) := P(X) -1$, $C_2(X) := P(X) - 1$, $C_3(X) := P(X) - A$を計算し、$D_i(X) := C_i(X)/Z_i(X)$ ($i = 0,1,2,3$)を求め、$(D_0(x), D_1(x), D_2(x), D_3(x))$ ($x \in G$)をleafとするMerkle treeにcommitする。$P(x)$, $(D_0(x), D_1(x), D_2(x), D_3(x))$のMerkle tree rootをcommitmentとして検証者に送信する。
2. 検証者は$x \in G$をランダムに選び、証明者に送信する。
3. 証明者は$P(x)$,$P(h x)$,$P(h^2 x)$, $(D_0(x), D_1(x), D_2(x), D_3(x))$と、そのMerkle Pathを検証者に提出する。
4. 検証者はMerkle Pathを検証した後、$Z_0(x):= x^T - 1$, $Z_1(x) := x - 1$, $Z_2(x) := x - h$, $Z_3(x) := x - h^{T-2}$と$C_0(x) := C(x) = (P(h^2 x) - P(h x) - P(x))(x - h^{T-2})(x - h^{T-1})$, $C_1(x) := P(x) -1$, $C_2(x) := P(x) - 1$, $C_3(x) := P(x) - A$を計算し、$C_i(x) \overset{?}{=} Z_i(x) D_i(x) \quad (i = 0,1,2,3)$を検証する。
5. 2~4を複数回(~10回)繰り返す。

以上の検証により、$P(X)$がフィボナッチ数列の制約$a_{i+2} = a_{i+1} + a_i$ ($i=0,\ldots, T-2$)と、初期条件$a_0 = 1$, $a_1 = 1$、終条件$a_{T-1} = A$を満たすtraceを表現する多項式であることがわかり、従ってフィボナッチ数列の$n$番目の項が$a_{n-1} = A$であることがわかります。

しかしながら、このプロトコルには脆弱性があります。$D_i(X)$が$T$よりも大きい次数を持っている場合、検証者を騙すことができます。

というのも、前節で「正しい」$C(X)$と「不正な」$C'(X)$が$G$の$7/8$以上の点で異なっていることを見ましたが、これは$C(X)$, $C'(X)$がともに$H$上で定義された次数$T-1$以下の多項式であるという前提条件の元でした。仮に$C'(X)$の次数を大きく取れば、$C(X)$とはほとんどの点で一致する不正な$C'(X)$を作ることができます^[5]。

$C(X)$の次数が$T$よりも小さい時、$D(X)$の次数も$T$よりも小さくなります。つまり、1~5ステップに加えて$D_i(X)$ ($i=0,1,2,3$)が$T$より小さい次数を持っていることを検証すればよいことになります。この検証をLow Degree Testing(LDT)といます。そしてSTARKで使われるLDTは次の節で解説するFRIと呼ばれるプロトコルです。

実はこれら4つの多項式のLDTは次の手順で1つにまとめることができます。

1. 検証者は$\alpha_0, \alpha_1, \alpha_2, \alpha_3 \in \mathbb{F}^*_p$をランダムに選び証明者に提出する。
2. 証明者は$f(X):=\alpha_0 D_0(X) + \alpha_1 D_1(X) + \alpha_2 D_2(X) + \alpha_3 D_3(X)$に対してLDTを行う。

検証者は$f(X)$が正しく$D_i(X)$から構成されていることを検証する必要がありますが、これはFRIの後で解説します。

FRI

FRI(Fast Reed—Solomon Interactive Oracle Proofs of Proximity)は、$G$上の多項式$f(X)$の次数が$T$より小さいことを$\mathcal{O}(T)$の証明コストと$\mathcal{O}(\log T)$の検証コストで証明できるLDTの一種です。

基本的はアイデアは次の通りです。以下では今後のノーテーションと統一するため$f_0 (X) := f(X)$と表記することにします。

$f_0 (X)$の中の$X^2$を全て$Y$に置き換え、$f_0(X) = g_0(X, Y = X^2)$の形に書き換えます。例えば、$f_0(X) = 1 + 2X + 3X^2 + 4X^3$なら、$g_0(X, Y) = 1 + 2X + 3Y + 4XY$となります。$g_0(X, Y)$の$X$の次数は高々1で、$Y$の次数は高々$T/2 - 1$であることに注意してください。

検証者が証明者に乱数$\beta_0$を渡し、証明者が$g_0(X, Y)$に$X = \beta_0$を代入することで、$f_1(Y) := g_0(\beta_0, Y)$は次数が$T/2$より小さくなります。これにより、「$f_0(X)$の次数は$T$より小さい」という主張が「$f_1(Y)$の次数は$T/2$より小さい」という主張に置き換わりました。これを再帰的に繰り返します。すなわち、$f_i(X) = g_i (X, X^2)$と検証者からもらった乱数$\beta_i$を使って$f_{i+1}(Y) := g_i (\beta_i, Y)$ ($i = 0, 1, \ldots, n-1$)を構成します。すると「$f_i(X)$の次数は$T/2^i$より小さい」という主張が「$f_{i+1}(X)$の次数は$T/2^{i+1}$より小さい」という主張と同値になります。最終的に「$f_n(X)$は定数関数」($2^n = T$)という主張まで同値変形したのち、$f_n(X)$から数点の$x$をサンプルして実際に定数関数であることを検証します。

いくつか注意点があります。$Y$には$X^2$が代入されるため、$f_i(X)$の定義域を$G^{(i)}$とおくと、$f_{i+1}(Y)$の定義域$G^{(i+1)}$は$G^{(i)}$のちょうど半分の大きさになります。これは各$y \in G^{(i+1)}$に対して、$y = x^2$となる$x \in G^{(i)}$がちょうど2個存在するためです。$G = G^{(0)}$は$8T = 2^{n+3}$の大きさを持っているので、$G^{(n)}$の大きさは$8$になります。

また検証者は証明者が正しく$f_{i+1}(Y)$を$f_{i}(X)$から構成したことを確認する必要があります。これは次のようにできます。$g_i(X, Y)$は$X$に対して1次なので、$Y$を$y$に固定すれば、異なる2点$s_i, s'_i$での評価$g_i(s_i, y)$, $g_i(s'_i, y)$によって$g_i(X, Y)$は一意に決定することができます。いま、$s_i$, $s'_i$を$y = s_i^2 = s'^2_i$ ($s_i \neq s'_i$)を満たすように取りましょう。すると$g_i(s_i, y) = f_i(s_i)$, $g_i(s'_i, y)=f(s'_i)$となります。この2点によって決まる直線$l_i(X) := \frac{f_i(s'_i) - f(s_i)}{s'_i - s_i} (X - s_i) + f_i(s_i)$^[6]が$l_i(\beta_i) \overset{?}{=} g_i(\beta_i, y) = f_{i+1}(y)$を満たすことを確認することで、$f_{i+1}(y)$が正しく構成されていることがわかります。

以上をまとめてみましょう。commit phaseとquery phaseに別れます。

Commit phase

1. 検証者は$\beta_0, \ldots, \beta_{n-1}$を$\mathbb{F}_p$からランダムに選び、証明者に送信する。
2. 証明者は$f_i(X)$の中の$X^2$を$Y$に置き換えることで$g_i(X, Y)$を構成し、$f_{i+1}(Y) := g_i(\beta_i, Y)$を計算する。$f_0(X)$, $f_1(X)$, ..., $f_{n-1}(X)$をそれぞれMerkle TreeにcommitしてMerkle rootを検証者に渡す(つまり合計で$n$個のMerkle rootを渡す)。また$f_{n}(x)$は定数$C$であり、これはそのまま検証者に渡す。

Query phase

1. 検証者は$x \in G^{(0)}$をランダムに選び、証明者に送信する。
2. 証明者は$s_0 = x$, $s_{i + 1} = s_{i}^2$として$s_i \in G^{(i)}$を計算する。また、$s_{i+1} = x^2$を満たす2点の$x \in G^{(i)}$のうち、$s_i$とは異なる方を$s'_i$とおく。$i = 0, \ldots, n-1$について$f_i (s_i)$, $f_i(s'_i)$とそのMerkle pathを検証者に提出する。
3. 検証者は送られてきたMerkle pathを検証したのち、$i = 0, \ldots, n-2$について$l_i(X) := \frac{f_i(s'_i) - f(s_i)}{s'_i - s_i} (X - s_i) + f_i(s_i)$が$l_i(\beta_i) \overset{?}{=} f_{i+1}(s_{i+1})$を満たすことを検証し、最後に$l_{n-1}(\beta_{n-1})\overset{?}{=}C$を検証する。
4. 1~3を複数回(数十回ほど)繰り返す。

Fiat-Shamiar Trasform

AIRの検証も、FRIによるLDTも、証明者と検証者が対話することによって行うIOP(Interactive Oracle Proofs)でした。ただし、STARKにおけるIOPは検証者が証明者に送信する値はすべて乱数という特徴があります。このようなIOPをPublic Coin Protocolといい、Fiat-Shamiar Transformと呼ばれる変換を使って非対話式の証明に変換できることが知られています。

そもそも、検証者が乱数を送る必要があるのは、証明者が自分の都合の良い乱数を選ぶことを防ぐためです。逆に言えば、証明者が乱数の出目を調整できないことが保証されていれば、証明者自身が乱数を生成しても問題ないことを意味します。

STARKのFiat-Shamiar Trasformは、Merkle tree commitmentを証明者が使う乱数のseed値にすることで行われます。乱数を調整するためには、Merkle rootを変える必要がありますが、そのためにはMerkle treeの内容も変える必要があります。つまり、悪意のある証明者にとっては偽装証明可能なMerkle treeのleaf値を保ったまま、Merkle rootを変える必要があり、大きな計算コストが発生します。この計算コストが非常に大きく、現実的な時間内で偽装証明が可能になる確率が無視できるほど小さいとき、Fiat-Shamiar Trasformは安全であるとみなされます。

ただし、Fiat-Shamiar Trasformの不適切な実装は容易にセキュリティホールを生み出します。すでにいくつかのFiat-Shamiar Trasformを用いたアプリケーションでFrozen Heartと呼ばれる脆弱性が発見されています。

Fiat-Shamiar Trasformの実装では、乱数生成器$\mathcal{C}$を使います。$\mathcal{C}$に値$a$を登録することを、$\mathcal{C} \leftarrow a$と表記することにします。$\mathcal{C}$はこれまでに登録されてきた値に基づき決定論的に$\mathbb{F}_p$の元を選びます。$\mathcal{C}$から$\alpha$が出力されるとき、$\alpha \leftarrow \mathcal{C}$と表記します。

STARK

最終的なSTARKのプロトコルは次のようになります。これまでに定義した記号に関しては定義を省略します。また、逐次証明を作成して提出するように書いていますが、実際は最後にまとめて提出します。

証明者の手順

$\mathcal{C}$を初期化しておく。

AIRの証明

1. 多項式$P(X)$, $(D_0(X), D_1(X), D_2(X), D_3(X))$をMerkle treeにcommitし、それぞれのMerkle root $\textrm{mr}_0$, $\textrm{mr}_1$を提出し、$\mathcal{C}$に登録する。$\mathcal{C} \leftarrow \textrm{mr}_0, \textrm{mr}_1$
2. 以下の手順を$l$回繰り返す。
   a. $x \leftarrow \mathcal{C}$
   b. $P(x)$,$P(h x)$,$P(h^2 x)$, $(D_0(x), D_1(x), D_2(x), D_3(x))$と、そのMerkle Pathを提出する。

FRI: commit phase

3. $\alpha_0, \alpha_1, \alpha_2, \alpha_3 \leftarrow \mathcal{C}$
4. $f(X) = \sum_i \alpha_i D_i(X)$を計算し、$f(X)$をMerkle treeにcommitする。そのMerkle root $\textrm{mr}_2$を提出し、$\mathcal{C}$に登録する。$\mathcal{C} \leftarrow \textrm{mr}_2$
5. $f_0(X)$, $f_1(X)$, ..., $f_{n}(X)$を次の手順で計算する。
   a. $\beta_i \leftarrow \mathcal{C}$
   b. $f_{i+1}(Y) = g_i(\beta_i, Y)$
6. $f_0(X)$, $f_1(X)$, ..., $f_{n-1}(X)$をそれぞれMerkle treeにcommitする。それらのMerkle root $\textrm{mr}_{f_0}$,..., $\textrm{mr}_{f_{n-1}}$を提出し、$\mathcal{C}$に登録する。$\mathcal{C} \leftarrow \textrm{mr}_{f_0}, \ldots, \textrm{mr}_{f_{n-1}}$
   また、定数$C := f_n(X)$を提出し、$\mathcal{C}$に登録する。$\mathcal{C} \leftarrow C$

FRI: query phase

7. 以下の手順を$m$繰り返す。
   a. $x \leftarrow \mathcal{C}$
   b. $(D_0(x), D_1(x), D_2(x), D_3(x))$とそのMerkle pathを提出する。
   c. $f_0 (s_0)$,...,$f_{n-1} (s_0)$, $f_0 (s'_0)$,...,$f_{n-1} (s'_0)$とそのMerkle pathを提出する。

検証者の手順

$\mathcal{C}$を初期化しておく。

AIRの検証

1. $\mathcal{C} \leftarrow \textrm{mr}_0, \textrm{mr}_1$
2. 以下の手順を$l$回繰り返す
   a. $x \leftarrow \mathcal{C}$
   b. $P(x)$,$P(h x)$,$P(h^2 x)$, $(D_0(x), D_1(x), D_2(x), D_3(x))$のMerkle pathを検証し、$x$に対応することを確認する。
   c. $C_i (x) \overset{?}{=} D_i(x) Z_i(x)$ ($i = 0,1,2,3$)を検証する。

FRIの検証

3. $\alpha_0, \alpha_1, \alpha_2, \alpha_3 \leftarrow \mathcal{C}$
4. $\mathcal{C} \leftarrow \textrm{mr}_2$
5. $\beta_0, \ldots, \beta_{n-1} \leftarrow \mathcal{C}$
6. $\mathcal{C} \leftarrow \textrm{mr}_{f_0}, \ldots, \textrm{mr}_{f_{n-1}} , C$
7. 以下の手順を$m$回繰り返す
   a. $x \leftarrow \mathcal{C}$
   b. $(D_0(x), D_1(x), D_2(x), D_3(x))$のMerkle pathを検証し、$x$に対応することを確認する。
   c. $f_0(x) \overset{?}{=} \sum_i \alpha_i D_i (x)$を検証する。
   d. $f_{i+1}(s_{i+1}) \overset{?}{=} l_i (\beta_i)$ ($i = 0, \ldots, n-2$)と$C \overset{?}{=} l_{n-1} (\beta_{n-1})$を検証する。

以上で非対話なSTARKを構成できました。

最後に

この記事の間違い等にお気づきになった方や、ご質問がある方は、twitterのDMまでお気軽にご連絡ください。

参考にした記事

• STARK paper
  https://eprint.iacr.org/2018/046

• DEEP FRI paper
  https://arxiv.org/abs/1903.12243

• Vitalik's STARK post
  https://vitalik.ca/general/2017/11/09/starks_part_1.html
  https://vitalik.ca/general/2017/11/22/starks_part_2.html
  https://vitalik.ca/general/2018/07/21/starks_part_3.html

• STARK101
  https://starkware.co/stark-101/

脚注

1. SNARKは離散対数問題の困難性に安全性の根拠を持つものが多く、量子耐性を持ちません

2. 有限アーベルの基本定理からの帰結です

3. 左辺の多項式が$X = h^0,\ldots,h^{T-1}$を根に持つことから証明できます

4. つまり$C(X)/Z(X)$分母分子に$(X - h^{T-2})(X - h^{T-1})$を掛けた形

5. 具体的には、$P'(X)$を適当に選び$C'(X):=(P'(h^2 X) - P'(hX) - P'(X))(X - h^{T-2})(X - h^{T-1})$を構成します。$D'(X) := C'(X)/Z(X)$は割り切れませんが、フェルマーの小定理$a^{-1} = a^{p- 2}$より$D(X) = C'(X) (Z(X))^{p-2}$と多項式の形で書くことができます。$X^{8T} = 1$を利用して$8T$以上の項を消去することができるので、$D'(X)$は最終的に次数が$8T$程度の多項式になります。このように構成しても$C'(X) = D'(X)Z(X)$は成立するので、$D'(X)$の次数を確認しない検証者は騙されてしまいます

6. 実は一般的に$m$個の点から定まる$m-1$次多項式を求めるのは、高速フーリエ(逆)変換を使うと$\mathcal{O}(m \log m)$のオーダーで効率的に実行できることが知られており、今回の場合でも$l_i(X)$を表式通りに計算するより高速フーリエ変換のテクニックを使うほうが効率的です。ただし、説明のわかり易さのために以降も$l_i(X)$の表式を使って説明します。