STARKs Part I
This article is the Japanese translation of [STARKs, Part I: Proofs with Polynomials](https://vitalik.ca/general/2017/11/09/starks_part_1.html) originally written on 2017 Nov 09.
Eli Ben-Sasson さんに多大なる手助け、説明、そして査読いただき、またこの記事で使われるいくつかの例を考えていただき、何よりこれらすべての発明いただいたことに多大なる感謝をもうしあげます。ならびに、Hsiao-wei Wang さんの査読にも感謝いたします。
ZK-SNARKs についてはもう耳にしたことがあるという前提で話をしたいのですが、
ZK-SNARKs とはゼロ知識証明をつかった技術であり、あらゆるユースケースに備え、検証計算からプライバシー保護がなされた暗号通貨までに渡り使える一般的用途をもつ技術です。
これに対して ZK-S`T`ARKs については聞いたことがないという人はいるかもしれません。それは新しく開発されたもので、ZK-SNARKsのいとこにあたるものです。
ZK-S`T`ARKs の `T` は transparent つまりは透明性を意味します。ZK-STARKs は、 ZK-SNARKs の主要な弱点、つまりプロトコルを信用しなければならない Trusted Setup 問題を見事に解決したものです。さらに暗号学的前提をさらに簡素にしてくれてもいるのです。楕円曲線や、ペアリング、the knowledge-of-exponent の前提といったものを必要とせず、その代わりに、単にハッシュと情報理論に依存するよう改善されています。
これが意味するところは、量子コンピュータを使った攻撃にも耐えるということです。
しかしながら、コストがかかります。
証明のサイズは、288 byte だったものが、数百キロバイトまで膨れ上がります。
このコストが見合わないような使用例はもちろんあるでしょうが、
とりわけ、信用を最小化したいという、パブリックブロックチェーンの文脈では、十分コストに見合うことでしょう。
かつ、楕円曲線が破られる、あるいは量子コンピュータの実用化に大きな進展などがあった場合などに、必ず役立つことでしょう。
さて、ではどのようにして、この新しいゼロ知識証明が動いているのでしょうか。
まずはじめに、一般的なゼロ知識証明がどのようなものだったということを復習しましょう。
まず前提として、公開する関数と、秘密にする入力値、公開する出力値の三つを持っていることとしましょう。
あなたは、 $ f(x) = y $ をみたすような、 $x$ を持っているということを証明したいのですが、 $x$ がなんであるかの情報は与えたくありません。
さらに、f を証明の正しさを損なうことなく、より高速に計算したいような状況だったとしましょう。
いくつか使用例を見てみましょう。
- $f$ が、普通のノートパソコンだと二週間かかり、データセンターにある大きいパソコンで二時間かかる計算だったとします。あなたはその $f$ つまりは走らせるコードをデータをデータセンターに送りつけ、データセンターがそれを走らせ、素の結果を証明つきで返信してくれるものとします。あなたは、その証明が正しいということを数ミリ秒で検証することができ、送られてきた答えが正しいということを知ることができます。
- あなたが、次のような内容の暗号化されたトランザクションをもっているものとします。「 $X_1$ は私の古い残高だ。 $X_2$ は私の新しい残高だ。 $X_3$ はあなたの古い残高だ。 $X_4$ はあなたの新しい残高だ。」というようなものです。あなたは、このトランザクションの有効性を示す証明つまりは、古い残高と新しい残高が非負であり、自分の残高の減額とあ相手の残高の増分が一致しているということを示す証明書をひとつ作成したいとします。 $x$ は暗号鍵のペアとし、 $f$ はそのトランザクションをもう一つ入力値と公開されたものとしてもつような関数であり、鍵のペアを（秘密の）引数としてとり、検査をし、検査を通れば $1$ を返し、そうでなければ $0$ を返すようなものとなります。当然 $y$ の値は検査が通れば $1$ となります。
- Ethereum のようなブロックチェーンをもつような状況を考えます。あなたは、例えば、ノードを Genesis Block からダウンロードを始めるのには時間がかかるので、過去のトランザクションに興味がなく、あなたの財布への入金を取り扱うような最新のブロックが正しいとという証明が欲しいとします。あなたは、フルノードに大して、そのブロックの正しさの証明が欲しいとします。 $x$ は何ギガバイトに及ぶ、全ブロックチェーンのデータであり、 $f$ はそのデータをブロック毎に処理し、その有効性を検証し、最後のブロックのハッシュ値を出力する関数です。そして、 $y$ は、フルノードからあなたがダウンロードしたブロックのハッシュ値です。（かなり大掛かりな検査に思えるかもしれませんが、同期に数日かかる現状と比べると劇的に早くなるはずです。）
さて、これらすべての例に対する困難とは一体なんなのでしょうか。
ゼロ知識であること、つまりはプライバシーの確保は比較的容易に達成することができます。
任意の計算を三色グラフ問題のようなものの一例に変換する方法は、幾通りもあります・ここでグラフを三色に色付けすることは、もとの問題の解に相応し、
伝統的なゼロ知識証明プロトコルを使い、有効な三色グラフを持っているということをそれを明らかにすることなく、証明するのに使います。
詳細は、この2014年の[ Mattew Green による素晴しい記事](https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/)を参照して下さい。
本質を端的に、かつ明らかにしておくということは、より困難です。
直感的にいうと、計算に関わることを端的かつ明示的に証明することが困難である理由は、
計算というものがとても壊れやすく繊細なものだからです。
もしあなたが、長くかつ複雑な計算をもっていたとし、悪魔の呪文で、計算の任意の途中過程において 0 と 1 を反転することができたとします。
ほとんどの場合において計算結果をまったく違ったものにするには、一ヶ所さえ反転させてやれば済むのです。
そのため、計算の正確性を計るために、ランダムにサンプリングするといったようなことは難しいのです。というのは、ランダムなサンプリングによって、その悪魔の1ビットをサンプルすることを容易く逃してしまうからです。
しかしながら、高度かつ複雑な数学を使えば、それを可能にすることができることがわかります。
一般的な考えとして、より高度な直感で伝えるとすれば、これを遂行するプロトコルは、[ erasure coding ](https://en.wikipedia.org/wiki/Erasure_code) で用いられているものに似たような数学を利用しています。 erasure coding とは、データに障害耐性を持たせるのにしばしば使われる技術です。
もし、ひとつのデータ片をもっていて、それをひとつの直線として符号化したとすると、あなたは、その直線から4点選び取ることができます。
これら4点のうち任意の2点があれば、もとの直線を再構成するには十分であり、それゆえ、その2点から、他の2点の情報も得ることができる、といったようなものです。
さらに、データに対して、本の少し変化を与えたとすると、これらの4点のうち少なくとも3点が正しいということが保証されています。
今、データを直線として符号化しましたが、データを1000000次多項式として符号化することも可能です。 2000000個の点を多項式上に選ぶことができ、1000001個のデータから、これらを復元することができます。元のデータにおけるどんな偏差が変化するには、少なくとも1000000個の点が必要となるでしょう。
ここで紹介したアルゴリズムは、エラーの強度を持たせる目的で、多項式に深く依存していると言えるでしょう。
# A Somewhat Simple Example
あなたが今、多項式 $P$ が、 $1$ から $1000000$ までの任意の整数 $x$ に対して、 $0 \le P(x) \le 9$ を満たしていることを証明したいとします。
これは『値域検査』と呼ばれるシンプルなタスクです。『値域検査』というのは、例えば口座の集合に対して、トランザクションの集合を適用したとき、すべての口座の残高が非負整数であるかどうかなどの検査に使われるようなものです。
もし値域が $0 \le P(x) \le 9$ の範囲内ならば、値が正しい数独パズルを構成していることの部分的な検証ととれるでしょう。
伝統的なこれの証明方法は、 $1000000$ 個の点全てを表示し、検証するというものです。
しかしながら、われわれは、 $1000000$ ステップより小さいステップで証明できるのかということを知りたいのです。
単にランダムな検査を多項式 $P$ の評価に対して適用するだけではできません。
常に、悪意ある証明者が、 $999999$ 箇所では制約を満たすものの、最後の一つだけ制約を満たさないようなものを思いつく危険性があり、
いくつかの値に対するサンプリングでは必ず、その問題の値を捕捉できません。
では、われわれに何ができるのでしょうか。
問題を数学上で、少し変形してみましょう。
$ C(x) $ を多項式を検査するための制約条件とします。もし、 $0 \le x \le 9$ ならば $C(x) = 0$ をとり、それ以外の場合は、非零の数となるものとします。
これは、単に $C(x) = x(x-1)(x-2) ... (x-9)$ とすることで構築することができます。
（今は、 $x$ は整数であり、それ以外の場合は考慮に入れる必要はありません。）
さて、問題は今、次のように変形され、
『任意の $1$ から $1000000$ の整数 $x$ に対し、 $C(P(x)) = 0$ を与えるような $P$ をあなたが知っているということを証明してください。』となります。
$Z(x) = (x-1)(x-2) ... (x-1000000)$ とすると、多項式 $Z$ は、任意の $1$ から $1000000$ の整数 $x$ に対し、 $0$ をとることは数学的事実として知られており、つまりは、『 $C(P(x)) = Z(x)D(x)$ となるような、 $P(x)$ と $D(x)$ を知っている』とさらに置き換えることができます。
ここで、 $C(P(x))$ さえ知っていれば、 $D(x)$ を求めるのは簡単です。単に[長い多項式の割り算](https://www.purplemath.com/modules/polydiv2.htm)を行うか、
[高速フーリエ変換](https://en.wikipedia.org/wiki/Fast_Fourier_transform)を使って速く解くこともできます。
さて、これで、もとの問題を、数学的に明快で、解くのが簡単にみえる問題に変形することができました。
さてこれをどのようにして証明しましょう。
証明のプロセスを、証明者と検証者間の３ステップのコミュニケーションとして捉えてみましょう。
つまり、証明者が、ある情報を送信し、検証者があるリクエストを送信し、さらに証明者が情報をおくる、というようなコミュニケーションです。
まず最初に、証明者は、Merkle 木を作成し、1 から 10億 (10億です) の任意の整数 $x$ に対して、 $P(x)$ と $D(x)$ の評価をコミットし、
そのルートハッシュを検証者に送信します。
これは、100万個の点を含み、さらに残り 9億9900万個 の点の点をも含んでいます。
我々は、検証者が、これら全ての点における多項式 $Z(x)$ を評価した値をすでに知っているものと仮定します。
$Z(x)$ は、このスキームに関していえば、皆が計算の前に知っていなければならない公開鍵のような役割を果たします。
（そのすべてを保管するスペースがないようなクライアントであれば、単にそのマークルルートを保存すればよく、
検証者が探索しなければいけないすべての値のブランチをも提供するように要求すればよいでしょう。
代替的方法としては、ある $x$ に対して $Z(x)$ の計算がとても簡単になるような、有限体を選ぶことができます。）
そのコミットを受信したあとで、検証者は、1 から 10億までの値のなかから、任意の 16 個の値 $x_i$ を取り出し、
$P(x_i)$ と $D(x_i)$ の Merkle 枝を提供するよう依頼します。
証明者は、これらの値を提供し、検証者は 1. 前もって提供されている Merkle ルートに、その Merkle ブランチが適合するかを検証し、 2. 16 個のすべてのケースにおいて、
$C(P(x)) = Z(x)D(x)$ が成立するかを検証します。
我々は、この証明が『完全性』をみたしているということはわかります。
つまり、もし、あなたが適切な証明をしっているならば、計算し証明を正しく構築すれば必ず16個のチェックを通ることが保証されます。
しかし、『健全性』の方はどうでしょう。
つまり、もし、悪意のある証明者が、壊れた $P(x)$ を提供したとしましょう。その壊れた箇所を捕捉するのに必要な最小の確率とは一体どれくらいになるのでしょうか。
次のように計算できます。
$C(P(x))$ は、1,000,000次多項式が、10次多項式に入り込んだものですから、10,000,000次多項式となります。
一般論として、異なる二つの $N$ 次数多項式があれば、両者の一致する点の個数は高々 $N$ 個だということを知っています。
つまり、
ある x に対して、Z(x)D(X) と常に等しくなるようなどんな多項式とも一致しないような10,000,000次多項式があれば、
つまりは、多項式が異なってしまえば、必然的に、少なくとも 990,000,000 個の点の全てで、不一致となります。
そのため、１ラウンドであっても、不一致する値を得る可能性は、99%となり、
16 回検査することで、不一致を捕捉する可能性は、 $1 - 10^{32}$ まで膨れ上がります。
つなり、証明者が嘘の多項式を提供するということは、ハッシュの衝突を計算する問題と同様に、困難なものであることがわかります。
さて、我々は今一体何をしたのでしょうか。
多項式を使って、嘘の解におけるエラーを増殖させ、元の問題で見つけるには直接検査すれば100万回検査する必要があった解を、たったの1回で99%エラーを発見できるような検査プロトコルの解へと変貌させたのです。
われわれは、この３ステップコミュニケーションのメカニズムを、証明者と検証者のやり取りが必要でない証明へと変換することができます。
一回証明者が発信し、それを検証者が検証するだけで良いというものです。これには、 [Fiat-Shamir heuristic](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) が用いられます。
証明者は、最初に $P(x)$ と $D(x)$ の値をもったマークル木を作成し、そのルートハッシュを計算します。
ルートそれ自体は、証明者が提供する必要のあるブランチを決定するためのエントロピー源となります。
計算は、すべて証明者の側で行われます。データからマークル木のルートの計算プロセスと、そのルートをつかって監査されるマークル木の枝を選び出すプロセスによって、効率性が向上し、検証者とのやりとりの必要性がなくなります。
悪意のある証明者ができる唯一の悪事とは、 $1-10^{32}$ の確率で健全な証明を繰り返し計算したあげく、幸運により見つけ出すこととなります。
つまりは、少なくとも $1-10^{32}$ の確率で与えられた嘘の証明が検査にひっかかります。
悪意ある証明者が、嘘の証明をつくろうとすれば数十億年かかることになるでしょう。
# Going Further
この技術の持つ力について、描写するために、少し非自明なことをやってみましょう。
100万番目のフィボナッチ数を知っていることを証明してみましょう。
これを遂行するために、ひとつの計算テープを表現する多項式に関する知識をあなたが持っているということを証明します。
$P(x)$ は、 $x$ 番目のフィボナッチ数を表現するものとします。
多項式を検査する制約は三つのx座標の変数を引数にとり、 $C(x_1,x_2,x_3) := x_3 - x_2 - x_1$ とします。
つまりは、もし $P(x)$ がフィボナッチ数を表現するとしたら、 $C(P(x),P(x+1),P(x+2)) = 0$ となることを理解しておいてください。
問題を翻訳すると、『 $C(P(x),P(x+1),P(x+2)) = Z(x)D(x)$ を満たすような、 $P$ と $D$ を知っているということを証明します。』となります。
証明の監査の対象となる16個の要素に対して、それぞれ $P(x)$ 、 $P(x+1)$ 、 $P(x+2)$ と $D(x)$ のマークル木の枝を提供する必要があります。
証明者は、さらに、 $P(1) = P(0) = 1$ を証明するのに必要なマークル枝も提供する必要があります。
その他の場合は、すべて先ほどと同じようにします。
さて、これを実際に遂行するには、二つ解決しなければならない問題があります。
一つ目の問題は通常の数でこれをやると、『解』は実践的に効率的なものとはならないということです。
通常の数は、容易く計算到達が困難な巨大数となってしまうからです。
100万番目のフィボナッチ数は、208988 桁あります。
もし、実践で、端的かつ明確なものを求めるのならば、
通常の数で多項式を取り扱うのでなく、有限体を使う必要があります。
有限体とは、数の体系で、我々が好む $a(b+c) = ab + ac$ や $(a^2-b^2) = (a+b)(a-b)$ といったようなものを満たすようなものですが、
それぞれの数は、データとしてある定数量の空間しか使わないことが保証されています。
そうすると、100万番目のフィボナッチ数に関する証明には、巨大な数の演算を有限体上で行うためにさらに複雑な設計が必要となります。
もっとも簡素かつ可能な有限体は、合同演算により定義される体です。
つまり、任意の計算式 $a + b$ を $a + b mod N$ で置き換えます。減算や乗算に対しても同様で、除算に対しては、[合同逆元](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) を用います。
例えば、$N=7$ とすると、$3+4=0, 2+6=1, 3\times4=5, 4/2=2$ となります。
もう少し学習したい方は[この記事](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)内で "prime field" あるいは、"finite field" を検索してください。
二つ目の問題として、上で描いた健全性の証明のスケッチでは、ある一種の攻撃を無視しています。
証明者が検証者に対して渡さなければならない
$1000000$ 次多項式上の値 $P(x_i)$ と $9000000$ 次多項式上の値 $D(x_i)$ の代わりに、攻撃者が相対的に次数の低いそれら多項式上にないような値をコミットしたならばどうなるでしょうか。すると「無効な $C(P(x_i))$ は、有効な $C(P(x_i))$ と比べて、少なくとも 9億9000万点で異なる」というロジックが使えなくなり、攻撃がより簡単になってしまいます。
例えば、攻撃者はすべての $x_i$ に対し、乱数 $p_i$ を生成し、 $d_i = C(p_i)/Z(x_i)$ を計算し、これらの値を $P(x_i)$ と $D(x_i)$ の代わりにコミットします。
これらの値は、100万次以下の低次元の多項式のものではないであろうが、テストを通り抜けてしまうことでしょう。
この可能性というのは、やや難解かつ複雑な道具を使って、効率よく防御できることがわかっています。
そしてこの道具を使って、あなたは STARKs という名における数学的革命を構築を述べることができるのです。
また、その解決には制限があります。どんな1000000次多項式からも離れたデータのコミットを取り除くことができます。
（つまり、そのデータを1000000次多項式にするためには、すべての値の20%を変える必要があります。）
しかしながら、一つや二つの座標でのみ異なる値をとるような多項式を取り除くことはできません。
つまり、これらの道具が提供していることは『近接の証明』です。
つまり、 正しい多項式を表す $P$ や $D$ の大部分の点における正しさです。
これまででわかったように、これは証明をつくるのには十分ではあるが、二つの『捕捉』があります。
一つ目は、この制限が導入するエラーに対する余地を広げ、少ない要素で検証ができるようにするということです。
二つ目は、もし『境界条件の検査』を行っていたとすると、（フィボナッチの例では、 $P(1)=P(0)=1$ ）『近接の証明』を拡張して、大部分がおなじ多項式上にあるということだけでなく、これら二つの指定された点が、その多項式上にあるということを証明する必要があります。
このシリーズの[次のパート](/ethereum/412-STARK2.md/)では、『近接の検査 proximity checking』に対する解についてより詳細に描写し、
三つ目のパートでは、より複雑な制約条件の関数をフィボナッチ数や値域の問題のような例ばかりでなく、より一般的な任意の計算に対して、どのようにして構築していくのか見ていこうと思います。