Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bulletproofsにおける内積の証明

Bulletproof ZK Cryptography

Bulletproofsは2017年にBünzらが発表したゼロ知識証明システムの一種で、Trusted Setupを必要とせず、プルーフが非常に短く、その集約が可能であるという特性を持っている。最初はConfidential Transactionの秘匿した値がある範囲内にあることを証明するrange proofを効率的に実現するために提案されが、range proofに限らず、一般的な算術回路向けの非対話型ゼロ知識証明プロトコルとしても提案されている。

Bulletproofsがどのような仕組みでrange proofや算術回路で動作するのか見ていく前に、Bulletproofsのベースとなる内積の証明の仕組みについて理解する。

内積の証明

Bulletproofsの重要な構成要素の１つは、２つの異なるベクトルを持つPedersen Commitmentに対してベクトルの内積を計算するアルゴリズムにある。

よくConfidential TransactionやMimblewimbleで出てくる楕円曲線Pedersen Commitmentは

C = rG + aH

という形式のコミットメントで、rがブラインドファクター、aが秘匿するコインの量として使われる。

rやaはスカラー値だが、Bulletproofsの内積の証明では、これを拡張し、２つのベクトル {\textbf{a} = (a_0, a_1, ..., a_n)}, {\textbf{b} = (b_0, b_1, ..., b_n)}について

  • {c = \langle \textbf{a}, \textbf{b} \rangle}
  • {P = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle}

という関係が成立するベクトルa, bの知識を知っていることをa, bを明かすことなく検証者に確信させる（太字はスカラーではなく、G,Hを含めベクトルの表記で、 {\langle \rangle}は２つのベクトルの内積の表記）。

まず↑の２つのステートメントを、GとHとは異なるジェネレータBを利用したQ = wBを使って１つの式にする。このwは検証者がランダムに選択する。cの両辺にQを乗算すると、

  • {cQ = \langle \textbf{a}, \textbf{b} \rangle Q}

これをPの式に加算すると、

  • {P + cQ = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}

シンプルにするため、P' = P + cQとすると、

  • {P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}

というふうにシンプルにでき、このステートメントが成立することを証明する。

証明のプロセス

まず最初にベクトルを圧縮する。a, b, G, Hの要素の数をnとすると、以下の手順をk = log(n)回繰り返し、サイズを１にする。

ランダムな値xを選択し、ベクトルa, bを左右半分に分割し、半分に分割したベクトルにxおよび {x^{-1}}を乗算し、加算することでベクトルのサイズを半分にする。

f:id:techmedia-think:20200110164524j:plain

そしてa', b'に対応する新しいc'は

{c' = \langle \textbf{a'}, \textbf{b'} \rangle = \langle \textbf{a}_{lo} \cdot x + \textbf{a}_{hi} \cdot x^{-1}, \textbf{b}_{lo} \cdot x^{-1} + \textbf{b}_{hi} \cdot x \rangle}

となる。そして、c'は以下のようにも表現できる。

{c' = \langle \textbf{a}_{lo}, \textbf{b}_{lo} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{hi} \rangle + x^{2} \cdot \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle + x^{-2} \cdot \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}

ここで、 {L = \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle}、 {R = \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}とすると、↑の式は１つまえのcを使って以下のように表現できる。

{c' = c + x^{2} \cdot L + x^{-2} \cdot R}

各ラウンドのLとRを検証者に送り、k回ラウンドを繰り返すとベクトルa, bの要素の数は最終的に１つになるので、スカラー値となったa', b', c'を証明者に送ると、３つの値と各ラウンドのL, Rを使って逆の計算をすることでcの値を計算できる。この仕組がポイントの１つで、圧縮とその逆の計算を簡単にするためcで説明したが、実際は後述するようにP'を使った計算になる。

↑の圧縮はa, bだけでなくG, Hも同様に圧縮していく。結果、各ベクトルの次の状態は以下のように表現できる。

  • {\textbf{a}^{k-1} = \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}}
  • {\textbf{b}^{k-1} = \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}}
  • {\textbf{G}^{k-1} = \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i}}
  • {\textbf{H}^{k-1} = \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i}}

そしてステートメントP'についても以下のようになる。

{P'_{k-1} = \langle \textbf{a}^{(k-1)}, \textbf{G}^{(k-1)} \rangle + \langle \textbf{b}^{(k-1)}, \textbf{H}^{(k-1)} \rangle + \langle \textbf{a}^{(k-1)}, \textbf{b}^{(k-1)} \rangle \cdot Q}

展開すると

{P'_{k-1} = \langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}, \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i} \rangle + } {\langle \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}, \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i} \rangle + } {\langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}, \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i} \rangle \cdot Q}

となるが、これは↑のcとc'の関係と同じ変換を利用して、以下のように変換できる。

  • {P'_{k-1} = P'_k + x_{k}^{2} \cdot L_k + x_{k}^{-2} \cdot R_k}
  • {L_k = \langle \textbf{a}_{lo}, \textbf{G}_{hi} \rangle + \langle \textbf{b}_{hi}, \textbf{H}_{lo} \rangle + \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle \cdot Q}
  • {R_k = \langle \textbf{a}_{hi}, \textbf{G}_{lo} \rangle + \langle \textbf{b}_{lo}, \textbf{H}_{hi} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle \cdot Q}

各ベクトルの要素数が１になるまで圧縮を繰り返すとP'は最終的に

{P'_{0} = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0Q}

で、これは各ラウンドのLとRとxの値を使うと以下の式になる。

{P'_{0} = P'_{k} + \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}

P'を元のPに置き換えると式は以下のように変形できる。

{P + cwB = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0wB - \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}

ここまでの要素が揃うと以下の検証ができる。

  • 検証者は証明者から受け取った {P'_0}の構成要素であるスカラー値 {a^{(0)}_0, b^{(0)}_0}と各ラウンドのL, Rを使って、圧縮ラウンドの逆の計算をすることで算出した値が元のP'と合致するか検証し、合致すればスカラー値 {a^{(0)}_0, b^{(0)}_0}が正しいことを検証できる。
  • 検証者は {a^{(0)}_0, b^{(0)}_0}と各ラウンドのL, Rを使って↑のP + cwBの等式が成立するか直接検証することができる。 {a^{(0)}_0, b^{(0)}_0}がPを構成する式とcwBでcの式の両方に展開されるので、これをもって、Pとcの関係性の証明になる。

この検証をすることで、検証者はステートメント {P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}が成立することをベクトルa, bの値を知ることなく確認することができる。これがBulletproofsの内積の証明の仕組み。

ちなみに↑は証明者と検証者による対話が必要な形で記載しているが、これはFiat-Shamir変換により非対話型にすることができる。

このBulletproofsによる内積の証明ができると何が嬉しいの？と思うかもしれないが、これを冒頭で言ったようにCTやMimblewimbleで使われるrange proofの証明に利用できる。ある値が0〜2nの範囲内にあるというステートメントは内積で表現できるからだ。具体的なプロトコルについてはまた別の記事で解説したい。