🌟

STARKの原理

2022/12/31に公開約18,100字

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となります。これを素因数分解したときに素数qr個含まれているなら、|H| = q^rなる巡回部分群|H|が存在することが知られています[2]。巡回群とは、全ての元がある元gの冪の形g^nで書ける群のことをいいます。なお、gを生成元といい、生成元を巡回群の大きさだけ掛け合わせると1になります。

g^{q^r} = 1

すなわち、H\{g^0, g^1 , \ldots, g^{q^r -1}\}からなる群になります。rr = r_0 + r_1と2つの非負の数の和として表し、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^22^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}_ptwo 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以上なら、)T8倍の大きさを持つ部分巡回群G=\{g^0,\ldots,g^{N-1}\}, N = 2^{n+ 3}が存在ます。ここでGの生成元gHの生成元hと、h = g^8という関係を持ちます。fの定義域をGに拡大して、N個の要素からなるベクトル[f(g^0),\ldots,f(g^{N-1})]を作ります。これをReed Solomon Codewordと呼びます。

なお、今後Xは関数の変数、xXが取る具体的な値の意味で使うことにします。例えば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の節で説明したように、H8倍の大きさの巡回群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 GC(x) = D(x)Z(x)が成り立つなら、C(X)は「正しい」ことがわかります。

8分の7以上のx \in GC(x) = D(x)Z(x)が成り立つことは、ランダムな点xを数回サンプルしてチェックすれば検証できます。例えば5つのランダムな点xC(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) - AD_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)G7/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次なので、Yyに固定すれば、異なる2点s_i, s'_iでの評価g_i(s_i, y), g_i(s'_i, y)によってg_i(X, Y)は一意に決定することができます。いま、s_i, s'_iy = 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^2Yに置き換えることで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

  1. \alpha_0, \alpha_1, \alpha_2, \alpha_3 \leftarrow \mathcal{C}
  2. 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
  3. 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)
  4. 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

  1. 以下の手順を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の検証

  1. \alpha_0, \alpha_1, \alpha_2, \alpha_3 \leftarrow \mathcal{C}
  2. \mathcal{C} \leftarrow \textrm{mr}_2
  3. \beta_0, \ldots, \beta_{n-1} \leftarrow \mathcal{C}
  4. \mathcal{C} \leftarrow \textrm{mr}_{f_0}, \ldots, \textrm{mr}_{f_{n-1}} , C
  5. 以下の手順を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までお気軽にご連絡ください。

参考にした記事

脚注
  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)の表式を使って説明します。 ↩︎

Discussion

ログインするとコメントできます