Bulletproofsを利用したrange proofの仕組み

techmedia-think.hatenablog.com

↑でBulletproofsの基本となる内積の証明の仕組みについて書いたので、今回はこれがCTやMimblewimbleなどで必要とされるrange proofにどう適用されるのか見ていく。

range proofとは？

CTと同様Mimblewimbleなどでもコインの量を秘匿するのに以下のような楕円曲線を利用したPedersen Commitmentが採用されている。

C = xG + aH

xはBlinding Factor（MWでは秘密鍵に該当）で、aがコインの量。コインの量をこのようなコミットメントCにすることで、外部からaの値を分からなくしている。具体的な仕組みが知りたい場合は、以前撮影したMWのGBEC動画を参照↓

goblockchain.network

このようなPedersen Commitmentを使ってコインの量を秘匿する場合には、コインの量aが決められた正の範囲（0〜2⁶⁴など）にありマイナスやオーバーフローをしていないことを証明する（マイナスやオーバーフローしているとコインのインフレーション（生成）が可能になる）range proofが必要になる。

CTの初期の提案では、このrange proofにBorromean Ring Signatureを使用するものになっていた。ただしこの証明のサイズの大きさ（数百バイトのTxに対してrange proofのサイズが2.xKBなど）がCT導入のハードルとなっていた。この問題を解消するために提案されたのがBulletproofだ。

Bulletproofを利用したrange proof

Bulletproofを利用したrange proofプロトコルを表す図が↓

f:id:techmedia-think:20200108100156p:plain

ぱっと見ても？？？なので、具体的にどういうことをやっているのか見ていこう。

range proofの内積表現

図の左上にあるように、range proofで証明したいのはある値vが0 ≦ v < 2ⁿの範囲内にあること。例えばn = 4で、v = 5の場合、5が ${0〜2^{4}-1}$ の範囲内にあることを証明する。

証明者は最初にランダムな値γを選択し、値vへのコミットメントを作成する（CTやMWのアウトプットに相当）。

${V = γ\tilde{B} + vB}$

vがある範囲内にあることを証明する場合、図の左上の2番めの枠のようにvは以下の２つのベクトルの内積として表現することができる。

vのビット表現 ${a_L \in ｛0, 1｝^{n}}$ 。v = 5の場合は ${a_L = (0, 1, 0, 1)}$ というベクトル
2ⁿのベクトル。つまり ${(2^{n-1}, 2^{n-2}, ..., 2^{0})}$ というベクトル

この2つのベクトルの内積は、 ${＜a_L, 2^{n}＞ = v}$ になる。（n = 4で、v = 5の場合、 ${2^{3}・0 + 2^{2}・1 + 2^{1}・0 + 2^{0}・1 = 5}$ ）

このような内積を使った表現をした場合、証明するステートメントは↓

2つのベクトルの内積が値vであること（ ${＜a_L, 2^{n}＞ = v}$ ）。
${a_L}$ のベクトルの各値が0か1であること。 ${a_L}$ の各要素から1を引いたベクトルを ${a_R = a_L - 1}$ とすると、この２つのベクトルの各要素を乗算した結果のベクトルの要素は全て0になること ${a_L \circ a_R = 0^{n}}$ 。また、 ${(a_L - 1) - a_R = 0}$ 。

これが図の左上の部分。

ステートメントの結合とBlinding Factorを使った内積のブラインド

続いて、↑の1と2のステートメントをチャレンジスカラーを使って結合し、Blinding Factorを追加する。

まずその前に、証明者が ${a_L}$ を直接公開しては意味がないので（値を公表することになる）、range proofを作成する証明者は、↑の実質vの値を指す ${a_L}$ へのコミットするVector Commitmentを作成する。このVector Commitment Aはランダムな値αを選択し、 ${A = α\tilde{B} + a_LG + a_RH}$ を計算することで作られる。
さらに、２つのブラインドベクトル ${s_L, s_R}$ を選択し、同様にランダムな値pを選択して ${s_L, s_R}$ へコミットするVector Commitment ${S = p\tilde{B} + s_LG + s_RH}$ を計算する。
証明者は、検証者にこのAとSを送信する。
AとSを受け取った検証者はチャレンジとしてランダムな値yとzを選択し、証明者に送る。

この検証者が選択したyを使って、内積＜0ⁿ, yⁿ＞ = 0であるため、上記の１と２のステートメントは暗黙的に以下のように表現できる。

${＜a_L, 2^{n}＞ = v}$
${＜a_L - 1 - a_R, y^{n}＞ = 0}$
${＜a_L, a_R \circ y^{n}＞ = 0}$

さらに検証者が選択したzを使って、上記３つのステートメントを１つのステートメントに結合できる↓

${z^{2}v = z^{2}＜a_L, 2^{n}＞ + z＜a_L - 1 - a_R, y^{n}＞ + ＜a_L, a_R \circ y^{n}＞}$

このステートメントをより単純な項を持つように分割し、再配置する↓

${z^{2}v = z^{2}＜a_L, 2^{n}＞ + z＜a_L, y^{n}＞ - z＜a_R, y^{n}＞ - z＜1, y^{n}＞ + ＜a_L, a_R \circ y^{n}＞}$ ${z^{2}v + z＜1, y^{n}＞ = z^{2}＜a_L, 2^{n}＞ + z＜a_L, y^{n}＞ -z＜1, a_R \circ y^{n}＞ +＜a_L, a_R \circ y^{n}＞ }$ ${z^{2}v + z＜1, y^{n}＞ = ＜a_L, z^{2}2^{n}＞ + ＜a_L, zy^{n}＞ + ＜-z1, a_R \circ y^{n}＞ +＜a_L, a_R \circ y^{n}＞}$ ${z^{2}v + z＜1, y^{n}＞ = ＜a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}＞ + ＜-z1, a_R \circ y^{n}＞}$

右辺を結合するため、両辺に ${＜-z1, z^{2}2^{n} + zy^{n}＞}$ を加算し、単純化すると↓

${z^{2}v + z＜1, y^{n}＞ - ＜z1, z^{2}2^{n} + zy^{n}＞ = ＜a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}＞ + ＜-z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}＞}$ ${z^{2}v + (z - z^{2})＜1, y^{n}＞ - z^{3}＜1, 2^{n}＞ = ＜a_L - z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}＞}$

そこから内積以外の秘密の値でない項を以下のように定義すると↓

${δ(y, z) = (z - z^{2})＜1, y^{n}＞ - z^{3}＜1, 2^{n}＞)}$

（この値は検証者が提供したyとzを使って簡単に計算できる。）これを適用した最終的なステートメントは、

${z^{2}v + δ(y, z) = ＜a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}＞}$

となる。この式の右辺の内積は、左の要素に ${a_L}$ を持ち、右の要素に ${a_R}$ を持つ。そしてこの式の各パーツを以下のように定義する。

${l(x) = a_L - z1}$
${r(x) = y^{n} \circ (a_R + z1) + z^{2}2^{n}}$
${z^{2}v + δ(y, z) = ＜l(x), r(x)＞}$

ただこの段階ではl(x)とr(x)はブラインドされていない。つまり、このステートメントを証明する際にl(x)とr(x)の情報をそのまま送るとvの値が検証者に分かってしまうので、↑で選択したブラインドファクター ${s_L, s_R}$ を使用して、l(x)とr(x)を以下のようなブラインド多項式にする。

${l(x) = a_L + s_Lx - z1} = l_0 + l_1x$
${r(x) = y^{n} \circ (a_R + s_Rx + z1) + z^{2}2^{n} = r_0 + r_1x}$

${a_L, a_R}$ がそれぞれ ${a_L + s_Lx, a_R + s_Rx}$ に置き換わっただけ。 ${l_0 + l_1x}$ と ${r_0 + r_1x}$ はxの多項式として表現した場合の式で、 ${l_0, r_0}$ はxの多項式の次数０の項を、 ${l_1, r_1}$ は次数１の項をそれぞれ表している。ここでブラインドファクター ${s_L, s_R}$ に対してのみxが乗算されているため、 ${l_0, r_0}$ がブラインドされていない内積の左右の要素となる。つまり、

${＜l_0, r_0＞ = z^{2}v + δ(y, z)}$

である。このような式変形をすると以下のような多項式表現ができる↓

${t(x) = ＜l(x), r(x)＞ = t_0 + t_1x + t_2x^{2}}$

この多項式の各項（ ${t_0, t_1, t_2}$ ）はKaratsuba法を使うと以下のように表現できる↓

${t_0 = ＜l_0, r_0＞}$
${t_2 = ＜l_1, r_1＞}$
${t_1 = ＜l_0 + l_1, r_0 + r_1＞ - t_0 - t_2}$

ここで ${t_0 = ＜l_0, r_0＞ = ＜a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}＞}$ であるので、証明者が検証者にアンブラインドした内積の式が成立することを証明するためには、t(x)の定数項 ${t_0}$ が ${z^{2}v + δ(y, z)}$ であることと、t(x)が正しい多項式であることを証明すればいい。

ここまでが図の真ん中上部の緑の枠の部分（長かった。。）。

${t_0}$ の正しさの証明

続いて、↑の ${t_0 = z^{2}v + δ(y, z)}$ であることを証明する。

まず証明者はt(x)の係数へのコミットメントを作成し、チャレンジポイントxを使って多項式を評価することで、コミットメントが正しいt(x)へのコミットメントであることを検証者に証明する。

値vに対するコミットメントVは既に作ってあり、それが ${t_0}$ へのコミットメントにもなるので、新たに ${t_1, t_2}$ へのコミットメント ${T_1, T_2}$ を作成し、検証者に送信する。この時 ${V, T_1, T_2}$ には以下の関係がある。

t(x)をPedersen Commitmentにマッピングするのに、点Bを使用してまず値へのコミットメントを作る。

${t(x)B = z^{2}vB +δ(y, z)B + xt_1B + x^{2}t_2B }$

続いて、別の点 ${\tilde{B}}$ を使ってブラインドファクターとなる部分を作る。

${\tilde{t}(x)\tilde{B} = z^{2}\tilde{v}\tilde{B} + 0\tilde{B} + x\tilde{t_1}\tilde{B} + x^{2}\tilde{t_2}\tilde{B}}$

ここで ${\tilde{v}, \tilde{t_1}, \tilde{t_2}}$ はそれぞれ ${v, t_1, t_2}$ のブラインドファクター。そして ${t(x)B}$ と ${\tilde{t}(x)\tilde{B}}$ を加算してt(x)のPedersen Commitmentが作成できる↓