Bulletproofs
Bulletproofは、双線形ペアリングと呼ばれる暗号理論の概念に基づいています。双線形ペアリングは、暗号通貨のプロトコルにおいて、異なるグループに属する要素を結びつけることができる数学的な関数です。Bulletproofは、この双線形ペアリングを使用して、ベクトルの内積に関する証明を生成します。
Bulletproofは、ベクトルの内積に関するプルーフを生成する際に、線形形式を使用しています。線形形式は、線形代数学における行列とベクトルの積の概念に基づいており、行列とベクトルの積を用いて内積を表現することができます。この方法により、ベクトルの内積に関するプルーフをより効率的に生成することができます。
また、Bulletproofは、非対称ペアリングを使用して、暗号通貨のトランザクションの検証を行います。非対称ペアリングは、双線形ペアリングの一種で、異なる群から要素を選ぶことができます。これにより、Bulletproofは、トランザクションの送信者が所有している秘密鍵を使用して、トランザクションの正当性を検証することができます。
Bulletproofは、一種のベクトルコミットメントであることができます。ベクトルコミットメントは、複数の値をまとめてコミットするための技術であり、個々の値がどのように変更されたかを証明するために使用されます。Bulletproofは、ベクトルの内積に関するプルーフを生成するために、ベクトルコミットメントを使用します。
具体的には、Bulletproofは、ベクトルコミットメントによってコミットされた値の内積に関するプルーフを生成します。このプルーフにより、コミットされたベクトルが変更されていないことを検証することができます。Bulletproofは、ベクトルコミットメントを使用することで、暗号通貨のプロトコルにおける様々な証明を生成することができます。
Pedersen Commitment
有限体の2つのベクトル$ \vec{a}, \vec{b} \in \mathbb{F}_p^nのcommitmentを
$ P = \vec{g}^{\vec{a}} \vec{h}^{\vec{b}} \in \mathbb{G}
とする。ここで$ \mathbb{G}は楕円曲線であり、$ \vec{g} \in \mathbb{G}^n, $ \vec{h} \in \mathbb{G}^nは$ \mathbb{G}のgeneratorからなるベクトル。また$ \vec{g}^{\vec{a}} = \prod_{i} g_i^{a_i} \in \mathbb{G} という表記を用いている。このcommitmentをpedersen commitmentという。 pedersen commitmentはbinding性(異なる2つの入力に対して同じcommitmentになるような入力の組を見つける確率的多項式時間アルゴリズムが存在しないこと)を持つ。 Inner Product Argument (IPA)
BulletProofの中心的な目的は、次のinnner product argumentを証明するプロトコルを構築すること
「与えられた$ P \in \mathbb{G}, $ \vec{g}, \vec{h} \in \mathbb{G}^n,$ \vec{a}, \vec{b} \in \mathbb{F}_p^n, $ c \in \mathbb{F}_pに対して $ P = \vec{g}^{\vec{a}} \vec{h}^{\vec{b}}と$ c = \vec{a}\cdot \vec{b}が成り立つ」
つまりcommitmentが正しく$ \vec{a}, $ \vec{b}にcommitされており、$ \vec{a}, $ \vec{b}の内積が$ cであることを検証するためのプロトコルを構築したい。
ただし、これよりもう少しrelaxした、次のargumentを証明するプロトコルを先に構成し、それを用いてIPAを証明する
「与えられた$ P, u \in \mathbb{G}, $ \vec{g}, \vec{h} \in \mathbb{G}^n,$ \vec{a}, \vec{b} \in \mathbb{F}_p^nに対して $ P = \vec{g}^{\vec{a}} \vec{h}^{\vec{b}} u^{\vec{a}\cdot \vec{b}}が成り立つ」
Split & collapse
上記のargumentを$ \log n程度のverifier complexityで証明するために、split & collapseの手法を取る。基本的なアイデアは次の通り
まず$ n' := n/2として$ \vec{a}, \vec{a}', \vec{b}, \vec{b}' \in \mathbb{F}_p^{n'}, $ c \in \mathbb{F}_pに対するhashを
$ H\left(\vec{a}, \vec{a}^{\prime}, \vec{b}, \vec{b}^{\prime}, c\right)=\vec{g}_{\left[: n^{\prime}\right]}^{\vec{a}} \cdot \vec{g}_{\left[n^{\prime}:\right]}^{\vec{a}^{\prime}} \cdot \vec{h}_{\left[: n^{\prime}\right]}^{\vec{b}} \cdot \vec{h}_{\left[n^{\prime}:\right]}^{\vec{b}^{\prime}} \cdot u^c \in \mathbb{G}
と定義する。pedersen commitmentのbinding性より、このhashもbinding性を持つ。このbinding性を活用して下記のプロトコルを構成する
1. proverは
$ L = H(\vec{0},\vec{a}_{[:n^{\prime}]}, \vec{b}_{[n^{\prime}:]},\vec{0}, \vec{a}_{[:n^{\prime}]}\cdot \vec{b}_{[n^{\prime}:]})
$ R = H(\vec{a}_{[n^{\prime}:]},\vec{0}, \vec{0},\vec{b}_{[:n^{\prime}]}, \vec{a}_{[n^{\prime}:]}\cdot \vec{b}_{[:n^{\prime}]})
$ P = H(\vec{a}_{[:n^{\prime}]},\vec{a}_{[n^{\prime}:]}, \vec{b}_{[:n^{\prime}]},\vec{b}_{[n^{\prime}:]}, \vec{a} \cdot \vec{b})
を計算し、$ L, $ Rをverifierに送る。
2. Verifierは$ x \in \mathbb{F}_pをproverに渡す。
3. proverは
$ \vec{a}' = x \vec{a}_{:n/2} + x^{-1}\vec{a}_{n/2:}
$ \vec{b}' = x^{-1} \vec{b}_{:n/2} + x\vec{b}_{n/2:}
を計算し、verifierに渡す。ただし$ \vec{a}_{:n/2}, $ \vec{a}_{n/2:}はそれぞれ$ aの最初半分のベクトル、最後半分のベクトルを表す。
$ \vec{a}, $ \vec{b}で乱数結合の取り方が微妙に異なることに注意
4. verifierは
$ P':= L^{x^2} P R^{x^{-2}}
を計算し、
$ P' \overset{?}{=} H(x^{-1} \vec{a}',x \vec{a}', x \vec{b}', x^{-1} \vec{b}', \vec{a}' \cdot \vec{b}' )
を検証する。
--------------------------------------------
不正なproverにとって、$ L^{x^2} P R^{x^{-2}} = H(x^{-1} \vec{a}',x \vec{a}', x \vec{b}', x^{-1} \vec{b}', \vec{a}' \cdot \vec{b}' )
を満たすような$ L, R, P, \vec{a}', \vec{b}'を見つけ出すのは$ Hのbinding性より難しい為、このプロトコルは健全性を持つ