Bulletproofs

# Bulletproofs
Range proof を効率的に実行するための仕組み

## 記法
| 記号 | 意味 | 注釈 |
|------------|-------------|-------------|
| $\mathbb{Z}_p ^*$ | $\mathbb{Z}_p$ から $0$ を除外した集合 | |
| $\mathbf{k}^n $| $(\mathbf{k}^0, \mathbf{k}^1,\ ...\ ,\mathbf{k}^{n-1})$ | $\mathbf{k} \in \mathbb{Z}_p ^* $ | 
| $\mathbf{a}$ | ベクター | |
| $\mathbf{a}_{[:n]}$ | $\mathbf{a}$ の $0$ から 要素$n-1$ までの要素 | |
| $\mathbf{a}_{[n:]}$ | $\mathbf{a}$ の $n$ 以降の要素 | |
| $\mathbf{a} \circ \mathbf{b}$ |  $\mathbf{a,b}$ の要素ごとの積 | |
| $\langle \mathbf{a,b} \rangle$ | $\mathbf{a,b}$ の内積 | |
| ?= | 左辺と右辺が一致しているかを確認 | |

### Vector Polynomial
$n$ は多項式の次数

$ p(x) = \displaystyle \sum_{i=0}^d \mathbf{p_i} \cdot x^{i} \in \mathbb{Z}_p^n $

例

$ n = 2 $
$ d = n-1 = 1 $
$ \mathbf{p_0} = [2, 3] \in \mathbb{Z}_p^2 $ 
$ \mathbf{p_1} = [3, 4] \in \mathbb{Z}_p^2 $ 
$ p(x) = \mathbf{p_0} \cdot x^0 + \mathbf{p_1} \cdot x^1 $
$ p(x) = [2, 3] + [3, 4] \cdot x $

$x=5$ で評価
$ p(5) = [2, 3] + [3, 4] \cdot 5 $
$ p(5) = [2, 3] + [15, 20] $
$ p(5) = [17, 23] \in \mathbb{Z}_p^2 $

### Vector Polynomial の内積
$l(x), r(x)$ が Vector Polynomial だとして、

$ \langle l(x), r(x) \rangle = \displaystyle \sum_{i=0}^d \displaystyle \sum_{j=0}^i \langle \mathbf{l_i}, \mathbf{r_i} \rangle \cdot x^{i+j} \in \mathbb{Z}_p^n $

例

$ n = 2 $
$ d = n-1 = 1 $
$ l(x) = [2, 3] + [3, 4] \cdot x $
$ r(x) = [3, 5] + [1, 2] \cdot x $

$ \langle l(x), r(x) \rangle = \langle \mathbf{l_0}, \mathbf{r_0} \rangle \cdot x^{0+0} + \langle \mathbf{l_1}, \mathbf{r_0} \rangle \cdot x^{1+0} + \langle \mathbf{l_1}, \mathbf{r_1} \rangle \cdot x^{1+1} $
$ = \langle \mathbf{l_0}, \mathbf{r_0} \rangle + \langle \mathbf{l_1}, \mathbf{r_0} \rangle \cdot x + \langle \mathbf{l_1}, \mathbf{r_1} \rangle \cdot x^2 $
$ = \langle [2, 3], [3, 5] \rangle + \langle [3, 4], [3, 5] \rangle \cdot x + \langle [3, 4], [1, 2] \rangle \cdot x^2 $
$ = (6 + 15) + (9 + 20) \cdot x + (3 + 12) \cdot x^2 $
$ = 21 + 29 \cdot x + 15 \cdot x^2 $

$x=2$ で評価

$ = 21 + 29 \cdot 2 + 15 \cdot 2^2 $
$ = 21 + 58 + 60 $
$ = 139 $

## Inner-Product Argument
証明者が、以下が成り立つ $\mathbf{a,b}$ を知っていることを、検証者に納得させる。

$ P = \mathbf{g^{a} h^{b}} \in \mathbb{Z_p} $
$ c = \langle \mathbf{a,b} \rangle $

### 前提
- $a, b$ の長さは同じで、$2$ の倍数
- $ \mathbf{g, h} \in \mathbb{G}^n $
- $ \mathbf{a, b} \in \mathbb{Z}_p^n $
- $ P = \mathbf{g^{a} h^{b}} \in \mathbb{Z_p} $
- $ c = \langle \mathbf{a,b} \rangle $

#### 検証者と証明者が知っているもの
$ \mathbf{g, h} $
$ P, c $

#### 証明者だけが知っているもの
$\mathbf{a,b}$

### 証明方法
証明者が検証者に $\mathbf{a,b}$ を送る
検証者が
$ P = \mathbf{g^{a} h^{b}} \in \mathbb{Z_p} $
$ c = \langle \mathbf{a,b} \rangle $
を計算して、前提の $ P, c $ と一致することを確認する。

## Improved Inner-Product Argument
Inner-Product Argument の改良版。
証明者が、以下が成り立つ $\mathbf{a,b}$ を知っていることを、検証者に納得させる。

$ P = \mathbf{g^{a} h^{b}} \cdot u^{\langle \mathbf{a,b} \rangle} \in \mathbb{G} $

### 前提
- $a, b$ の長さは同じで、$2$ の倍数
- $ \mathbf{g, h} \in \mathbb{G}^n $
- $ u \in \mathbb{G} $
- $ p $ は群が定義される体の位数
- $ \mathbf{a, b} \in \mathbb{Z}_p^n $
- $ P = \mathbf{g^{a} h^{b}} \cdot u^{\langle \mathbf{a,b} \rangle} \in \mathbb{G} $

### ハッシュ関数

$H(\mathbf{a}, \mathbf{a'}, \mathbf{b}, \mathbf{b'},c) = \mathbf{g} ^ { \mathbf{a} } _ {[:n']} 
 \cdot \mathbf{g} ^ { \mathbf{a'} } _ {[n':]} \cdot \mathbf{h} ^ { \mathbf{b} } _ {[:n']} \cdot \mathbf{h} ^ { \mathbf{b'} } _ {[n':]} \cdot u^c $

演算・は準同型写像で、以下が成り立つ
$ H(\mathbf{a}_1, \mathbf{a'}_1, \mathbf{b}_1, \mathbf{b'}_1, c_1) \cdot H(\mathbf{a}_2, \mathbf{a'}_2, \mathbf{b}_2, \mathbf{b'}_2, c_2) = H(\mathbf{a}_1 + \mathbf{a}_2, \mathbf{a'}_1 + \mathbf{a'}_2, \mathbf{b}_1 + \mathbf{b}_2, \mathbf{b'}_1 + \mathbf{b'}_2, c_1 + c_2) $

### 証明方法

1. $n$ を $a$ の長さに設定する
1. $n' = n / 2$
1. 証明者が $ L, R \in\mathbb{G} $ を計算して、検証者に送る
    $ L = H(\mathbf{0}^{n'}, \mathbf{a}_{[:n']}, \mathbf{b} _ {[n':]}, \mathbf{0}^{n'}, \langle \mathbf{a} _{[:n']}, \mathbf{b} _{[n':]} \rangle) $

    $ R = H( \mathbf{a}_{[n':]}, \mathbf{0}^{n'}, \mathbf{0}^{n'}, \mathbf{b} _{[:n']},  \langle \mathbf{a} _{[n':]}, \mathbf{b} _{[:n']} \rangle)$

    ちなみに $P$ は
    $ P = H( \mathbf{a} _{[:n']}, \mathbf{a} _{[n':]}, \mathbf{b} _{[:n']}, \mathbf{b} _{[n':]}, \langle \mathbf{a}, \mathbf{b} \rangle ) $

1. 検証者が $ x \in \mathbb{Z}_p $ を、証明者に送る
1. 証明者が、$ \mathbf{a}', \mathbf{b}' $ を計算して、検証者に送る
    $ \mathbf{a}' = x \mathbf{a} _{[:n']} +  x^{-1} \mathbf{a} _{[n':]} \in \mathbb{Z}_p^{n'} $
    $ \mathbf{b}' = x^{-1} \mathbf{b} _{[:n']} +  x \mathbf{b} _{[n':]} \in \mathbb{Z}_p^{n'} $
1. 検証者が $ (L, R, \mathbf{a}', \mathbf{b}') $ を使って $ P' = L^{(x^2)} \cdot P \cdot R^{(x^{-2})} $ を計算して、以下が成り立てば、証明者の主張を受け入れる。
    $ P' = H(x^{-1}  \mathbf{a}', x \mathbf{a}', x \mathbf{b}', x^{-1}  \mathbf{b}', \langle \mathbf{a}', \mathbf{b}' \rangle) $

### 6 についての補足
$H$ は準同型写像なので、$ L^{(x^2)} \cdot P \cdot R^{(x^{-2})} $ は、上記の $L, R, P$ の各要素を、適宜 $x^2$ か $x^{-2}$ を乗じながら足し上げる形になって、

$ L^{(x^2)} \cdot P \cdot R^{(x^{-2})} = H(\mathbf{a} _{[:n']} + x^{-2} \mathbf{a} _{[n':]}, x^2 \mathbf{a} _{[:n']} + \mathbf{a} _{[n':]}, x^2 \mathbf{b} _{[n':]} + \mathbf{b} _{[:n']}, \mathbf{b} _{[n':]} + x^{-2} \mathbf{b} _{[:n']}, \langle \mathbf{a}', \mathbf{b}' \rangle) $

となる。

$ \langle \mathbf{a} _{[:n']}, \mathbf{b} _{[n':]} \rangle ^{x^2} + \langle \mathbf{a}, \mathbf{b} \rangle + \langle \mathbf{a} _{[n':]}, \mathbf{b} _{[:n']} \rangle ^{x^{-2}} = \langle \mathbf{a}', \mathbf{b}' \rangle $ 

となるのは、一見わかりにくい。例えば、$n = 4, n' = 2$ で、

$ \mathbf{a} = [a_1, a_2, a_3, a_4] $
$ \mathbf{b} = [b_1, b_2, b_3, b_4] $

とすると、

$ \langle \mathbf{a} _{[:n']}, \mathbf{b} _{[n':]} \rangle ^{x^2} = \langle [a_1, a_2], [b_3, b_4] \rangle ^{x^2} $
$ = (a_1 b_3 + a_2 b_4) ^ {x^2} $
$ = x^2 a_1 b_3 + x^2 a_2 b_4 $

$ \langle \mathbf{a}, \mathbf{b} \rangle = \langle [a_1, a_2, a_3, a_4], [b_1, b_2, b_3, b_4] \rangle$
$ = a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4 $

$ \langle \mathbf{a} _{[n':]}, \mathbf{b} _{[:n']} \rangle ^{x^{-2}} = \langle [a_3, a_4], [b_1, b_2] \rangle ^{x^{-2}} $
$ = (a_3 b_1 + a_4 b_2) ^ {x^{-2}} $
$ = x^{-2} a_3 b_1 + x^{-2} a_4 b_2 $

$ \mathbf{a}' = x \mathbf{a} _{[:n']} +  x^{-1} \mathbf{a} _{[n':]} $
$ = x [a_1, a_2] + x^{-1} [a_3, a_4] $
$ = [x \cdot a_1, x \cdot a_2] + [x^{-1} \cdot a_3, x^{-1} \cdot a_4] $
$ = [x \cdot a_1 + x^{-1} \cdot a_3, x \cdot a_2 + x^{-1} \cdot a_4] $
 
$ \mathbf{b}' = x^{-1} \mathbf{b} _{[:n']} +  x \mathbf{b} _{[n':]} $
$ =  x^{-1}  [b_1, b_2] + x [b_3, b_4] $
$ = [x^{-1} \cdot b_1, x^{-1} \cdot b_2] + [x \cdot b_3, x \cdot b_4] $
$ = [x^{-1} \cdot b_1 + x \cdot b_3, x^{-1} \cdot b_2 + x \cdot b_4] $

$ \langle \mathbf{a}', \mathbf{b}' \rangle = \langle [x \cdot a_1 + x^{-1} \cdot a_3, x \cdot a_2 + x^{-1} \cdot a_4], [x^{-1} \cdot b_1 + x \cdot b_3, x^{-1} \cdot b_2 + x \cdot b_4] \rangle $
$ = (x \cdot a_1 + x^{-1} \cdot a_3) \cdot (x^{-1} \cdot b_1 + x \cdot b_3) + (x \cdot a_2 + x^{-1} \cdot a_4) \cdot (x^{-1} \cdot b_2 + x \cdot b_4) $
$ = (a_1 b_1 + x^2 a_1 b_3 + x^{-2} a_3 b_1 + a_3 b_3) + (a_2 b_2 + x^2 a_2 b_4 + x^{-2} a_4 b_2 + a_4 b_4) $
$ = (x^2 a_1 b_3 + x^{-2} a_3 b_1) + (a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4) + (x^2 a_2 b_4 + x^{-2} a_4 b_2) $
$ = (x^2 a_1 b_3 + x^2 a_2 b_4) + (a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4) + ( x^{-2} a_3 b_1 + x^{-2} a_4 b_2) $

$ \langle \mathbf{a} _{[:n']}, \mathbf{b} _{[n':]} \rangle ^{x^2} + \langle \mathbf{a}, \mathbf{b} \rangle + \langle \mathbf{a} _{[n':]}, \mathbf{b} _{[:n']} \rangle ^{x^{-2}} = $ 
$ = (x^2 a_1 b_3 + x^2 a_2 b_4) + (a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4) + (x^{-2} a_3 b_1 + x^{-2} a_4 b_2) $

と、一致する。

### 再帰を使った証明の縮小

証明の最後のステップでのチェック

$ P' = H(x^{-1}  \mathbf{a}', x \mathbf{a}', x \mathbf{b}', x^{-1}  \mathbf{b}', \langle \mathbf{a}', \mathbf{b}' \rangle) $

は、

$ P' = \mathbf{g} _{[:n']} ^{x^{-1} \mathbf{a}'} \cdot \mathbf{g} _{[n':]} ^{x \mathbf{a}'} \cdot \mathbf{h} _{[:n']} ^{x \mathbf{b}'} \cdot \mathbf{h} _{[n':]} ^{x^{-1}  \mathbf{b}'}  \cdot u^{\langle \mathbf{a}', \mathbf{b}' \rangle} $
$ P' = (\mathbf{g} _{[:n']} ^{x^{-1}} \cdot \mathbf{g} _{[n':]} ^x)^{\mathbf{a}'} \cdot (\mathbf{h} _{[:n']} ^x \cdot \mathbf{h} _{[n':]} ^{x^{-1}})^{\mathbf{b}'} \cdot u^{\langle \mathbf{a}', \mathbf{b}' \rangle} $

で、

$ P' = (\mathbf{g} _{[:n']} ^{x^{-1}} \circ \mathbf{g} _{[n':]} ^x)^{\mathbf{a}'} \cdot (\mathbf{h} _{[:n']} ^x \circ \mathbf{h} _{[n':]} ^{x^{-1}})^{\mathbf{b}'} \cdot u^{\langle \mathbf{a}', \mathbf{b}' \rangle} $

と計算結果が変わらない。
「$\circ$」した場合でも最終的には要素全て足し上げるので「$\cdot$」と同じ結果になる。

これを利用して、検証者に $\mathbf{a}', \mathbf{b}'$ を送る代わりに、Inner Product Argument を $n$, ジェネレーター、入力データーを都度半分に圧縮しながら実行して、$n=1$の場合以前の実行では $L, R$、$n=1$ の場合には $a, b$ を検証者に送るようにする。

$(L_1, R_1),\ ...\ ,\ (L_{log_2 n}, R_{log_2 n}),\ (a, b)$

こうすることで、証明者と検証者の間での通信を、$2n$ から $2 \lceil log_2 (n) \rceil \in \mathbb{G} + 2 \in \mathbb{Z}_p$ に抑えることができる。 

### Multi-Exponentiation
長さ $n$ の $\mathbf{g}$, $\mathbf{h}$ から、長さが半分の $n'$ の $\mathbf{g}'$, $\mathbf{h}'$ をつくるには

$ x \in \mathbb{Z} _ {p} $ (random)
$\mathbf{g}' = \mathbf{g} ^{x^{-1}} _{[:n']} \circ \mathbf{g} ^x _{[n':]} \in \mathbb{G} ^{n'}$
$\mathbf{h}' = \mathbf{h} ^x _{[:n']} \circ \mathbf{h} ^{x^{-1}} _{[n':]} \in \mathbb{G} ^{n'}$

の計算が必要で $2n$ かかる。
これを $n$ が $1$ になるまで繰り返すと、合計 $4n$ の時間がかかる。

全体の過程で計算される、ジェネレーターに掛けられる係数をまとめて、最後に１度に掛けることによって、合計時間を $2n$ に短縮することができる。

$n=1$ の時点では、$a, b$ は 単一のスカラ値、$\mathbf{g}, \mathbf{h}$ は、単一の $\mathbb{G}$ 上の要素になっている。　

$ g = \displaystyle \prod_{i=1}^n g_i^{s_i} \in \mathbb{G}$
$ h = \displaystyle \prod_{i=1}^n h_i^{1 / s_i} \in \mathbb{G}$

$s_i$ の定義は以下の様になる。

for $i=1,...,n$: 
$ s_i = \displaystyle \prod_{j=1}^{log_2(n)} x_j^{b(i,j)} $
$ b(i,j) $ は、$i-1$ の $j$番目のビットが $1$ ならば $1$。そうでなければ $0$。

これを使うと全体のチェックが以下に集約できる

$ \mathbf{g} ^{a \cdot \mathbf{s}} \cdot \mathbf{h} ^{b \cdot \mathbf{s} ^{-1}} \cdot u^{a \cdot b} \ ?= P \cdot \displaystyle \prod_{j=1}^{log_2(n)} L_j^{(x^2_j)} \cdot R_j^{(x_j^{-2})} $

## Pedersen Commitment
$v, \gamma \in \mathbb{Z}_p $, $g, h, V \in \mathbb{G}$ で、

ランダムネス $\gamma$ の $v$ への Pedersen Commitment $V$ は、
$ V = h^{\gamma} g^v $

加法準同型性がある。

どんな値に対しても、ランダムネスを調整することで、同じコミットメントを作ることができるので、コミットメントからは値を特定することができない。

## Confidential Transaction
Transaction の量を Pedersen Commitment で置き換える。

個々の量がわからなくても、コミットメントの加法準同型性を利用して合計を取ることで、Input、Output、Fee の合計が0であることがチェック可能。

### コミットメントの合計が 0 であることを確認する方法
$C = xG + aH$ が、隠す値が $a$ で、Blinding Factor（=ランダムネス）が $x$ の Pedersen Commitment だとする。
この場合、値が 0 の場合、コミットメントは $C = xG$ になるので、これを利用する。

1. コミットメントのハッシュに対して、秘密鍵＝Blinding Factor $x$ で署名する
1. コミットメント $C = xG$ を公開鍵にする
1. コミットメントを公開鍵として署名が検証できれば合計は 0。

適当な署名値を用意して、コミットメントと一致する公開鍵を解くことを防ぐためにコミットメントに対して署名する。

### マイナスの値

巡回群の要素を使って値を表しているので、値をオーバーフローさせることで、マイナスの値と同じ効果を持つ値を作ることができる。例えば、位数が $11$ だとして、$3 + 9 = 12 = -1 \bmod 11$

マイナスの値を使うと
$(1 + 1) - (-5 + 7) == 0$

のような、不正なトランザクションが作れてしまうので、コミットメントに含まれる値が特定の範囲内にあること保証する Range Proof をトランザクションに追加する。

### 単純なRange Proof

#### 0 確認の応用
$C$ が $1$ へのコミットメント $C = xG + 1H$ だった場合、
Blinding Factor で署名を作ると、$C' = C - 1H$ を公開鍵にすると、署名の検証が通る。
この 1 は任意の整数で置き換え可能。

#### Ring Signature
複数の署名のうち、どれか一つの署名の検証が通れば、全体が通るもの。
どの署名の検証が通ったかはわからない。

#### 0 確認の応用と Ring Signature の組み合わせ

例えば、$ C' = C - 1H $ として、
$ \lbrace C, C' \rbrace $ という Ring Signature をつくると、
仮に、$C$ が $0$ へのコミットメントの場合は、$C$ に対する署名検証が通り、
$C$ が $1$ へのコミットメントの場合は、$C'$ に対する署名検証が通るので、Ring Signature は正しくなる。
$C$ が、そのどちらへのコミットメントでもない場合には、Ring Signature は不正になる。

#### Range Proof の構築
0 確認の応用と Ring Signature の組み合わせを使うと、例えば、値が 0 から 7 の間にあることを証明する Range Proof を、以下の様に構成できる。

1. 値 $c$ に対する Pedersen Commitment $C$ をつくる
1. $Cn$ が $c$ の $n$ ビット目に対するコミットメントで、$C1 + C2 + C3 = C$ となるような  $C1, C2, C3$ をつくる 
1. $Cn'$ を以下の様につくる
    $ C1' = C1 - 1H $
    $ C2' = C2 - 2H $
    $ C3' = C3 - 4H $
1. 以下の 3 つの Ring Signature をつくる
    $ \lbrace C1, C1' \rbrace $
    $ \lbrace C2, C2' \rbrace $
    $ \lbrace C3, C3' \rbrace $
1. 全ての Ring Signature が正しければ、値は範囲内。そうでなければ値は範囲外

## Inner-Product Range Proof
Bulletproofs の論文で説明されているもの。
証明者が コミットメント $V$ が、特定の範囲の値 $v$ に対するものであることを、$v$ を公開せずに、検証者に納得させる。

### 証明の詳細

- $n$ は値のレンジのビット数
- $\upsilon$ は証明の対象になる値
- $V$ は $\upsilon$ の Pedersen Commitment
- $\gamma$ は、Pederseon Commitment で使うランダムネス
- $g, h$ は、使う群上の要素

として、以下を証明する。
$ \lbrace (g, h, V \in \mathbb{G}; n, \upsilon, \gamma \in \mathbb{Z}_p): V = h^{\gamma} g^{\upsilon} \land v \in [0,2^n - 1]  \rbrace $

1. $ \langle \mathbf{a}_L, \mathbf{2}^n \rangle = \upsilon$ となるように $\mathbf{a}_L = (a_1,\ ...\ ,a_n) \in \lbrace 0,1 \rbrace ^n$ を定義
1. 証明者が $\mathbf{a}_L$ のコミットメント $ A \in \mathbb{G} $ を作成
1. 証明者が、以下が成立する $\mathbf{a}_L \in \mathbb{Z}_p^n$ と $\upsilon, \gamma \in \mathbb{Z}_p$ を知っていることを検証者に納得させる
    $a$. $ V = h^{\gamma} g^{\upsilon} $
    $b$. $ \langle \mathbf{a}_L, \mathbf{2}^n \rangle = \upsilon $
    $c$. $ \mathbf{a}_R = \mathbf{a}_L - \mathbf{1} ^n $
    $d$. $ \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n $　

### 制約 c, d の役割
$ \mathbf{a}_L $ の各要素は $\mathbb{Z}_p$ の要素なので、$0$ か $1$ であるとは限らない。
$c$ で、$ \mathbf{a}_L $ の各要素から $1$ を引いた $ \mathbf{a}_R $ を作ると、$ \mathbf{a}_L $ の要素が $1$ であれば、$ \mathbf{a}_R $ の要素が $0$、$ \mathbf{a}_L $ の要素が $0$ であれば、$ \mathbf{a}_R $ の要素が $1$ というように、どちらかの要素が $0$ になり、$d$ で内積を取ると結果が $0$ になる。

この制約を入れることで、$\mathbf{a}_L = (a_1,\ ...\ ,a_n) \in \lbrace 0,1 \rbrace ^n$ であることが保証される。

### b 〜 d の条件を一つにまとめる

証明者が $ \mathbf{b} = \mathbf{0}^n $ であることを検証者に納得させるには、検証者にランダムな $ \mathbf{y} $ を送ってもらって、$ \langle \mathbf{b}, \mathbf{y}^n \rangle = 0 $ を示せばよい。

これを利用して、$b$ 〜 $d$ の条件を、検証者が選んだランダムな $\mathbf{y} \in \mathbb{Z}_p $ を使う前提で、以下の様に書き換える。

$b$. $ \langle \mathbf{a}_L, \mathbf{2}^n \rangle = \upsilon $
$c$. $ \langle \mathbf{a}_L - \mathbf{1}^n - \mathbf{a}_R, \mathbf{y}^n  \rangle = 0 $
$d$.  $ \langle \mathbf{a}_L, \mathbf{a}_R \circ \mathbf{y}^n  \rangle = 0 $

さらに、検証者が選んだランダムな $z \in \mathbb{Z}_p $ を使って、一つの式にまとめる。

$ z^2 \cdot \langle \mathbf{a}_L, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a}_L - \mathbf{1}^n - \mathbf{a}_R, \mathbf{y}^n  \rangle + \langle \mathbf{a}_L, \mathbf{a}_R \circ \mathbf{y}^n  \rangle = z^2 \cdot \upsilon $

これを書き換えて、

$ \delta (y, z) = (z - z^2) \cdot \langle \mathbf{1}^n, \mathbf{y}^n \rangle - z^3 \langle \mathbf{1}^n, \mathbf{2}^n \rangle \in \mathbb{Z}_p $

として、

$ \langle \mathbf{a}_L - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n \rangle = z^2 \cdot \upsilon + \delta (y, z) $ 　(39)

ここまでで、証明対象が一つの内積になった。
検証者が選んだ任意の $z$ について、(39) を成り立たせることができることを証明者が示す。
 
(39) の右辺の $ (z - z^2) \cdot \langle \mathbf{1}^n, \mathbf{y}^n \rangle - z^3 \langle \mathbf{1}^n, \mathbf{2}^n \rangle \in \mathbb{Z}_p $ は検証者が手元で計算できることに注意。

### 証明の手順

1. 証明者が $ \upsilon, \gamma $ から、$ \mathbf{a}_L $ を作り、さらにそこから $ \mathbf{a}_R $ を作る。そして $ \mathbf{a}_L, \mathbf{a}_R $ のコミットメント $A$ と、$ \mathbf{a}_L, \mathbf{a}_R $ を秘匿するために新たに導入する $ \mathbf{s}_L, \mathbf{s}_R \in \mathbb{Z}_p^n $ へのコミットメント $S$ を検証者に送る。

    （計算の詳細）　
     1. $ \mathbf{a}_L \in \lbrace 0, 1 \rbrace ^n s.t. \langle \mathbf{a}_L, \mathbf{2}^n \rangle = \upsilon $
     1. $ \mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n \in \mathbb{Z}_p^n $
     1. $ \alpha \in \mathbb{Z}_p $ (random) 
     1. $ A = h^{\alpha} \mathbf{g}^{\mathbf{a}_L} \mathbf{h}^{\mathbf{a}_R} \in \mathbb{G} $ （$A$ は $ \mathbf{a}_L, \mathbf{a}_R $ へのコミットメント）
     1. $ \mathbf{s}_L, \mathbf{s}_R \in \mathbb{Z}_p^n $ （秘匿ベクターをランダムに選択）
     1. $ \rho \in \mathbb{Z}_p $ (random) 
     1. $ S = h^{\rho} \mathbf{g}^{\mathbf{s}_L} \mathbf{h}^{\mathbf{s}_R} \in \mathbb{G} $ （$S$ は $ \mathbf{s}_L, \mathbf{s}_R $ へのコミットメント）
1. 検証者が $y,z \in \mathbb{Z}^*_p $ をランダムに選択して、証明者に送る
1. 証明者が $y,z$ を使って、(39) の内積の左側の入力に $\mathbf{s}_L$ を含めた $l(x)$、右側の入力に $\mathbf{s}_R$ を含めた $r(x)$ と、$l(x), r(x)$ の内積 $t(x)$ を定義する。

    $ l(x) = (\mathbf{a}_L - z \cdot \mathbf{1}^n) + \mathbf{s}_L \cdot x \in \mathbb{Z}_p^n $
    $ r(x) = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n \in \mathbb{Z}_p^n $
    $ t(x) = \langle l(x), r(x) \rangle = t_0 + t1 \cdot x + t2 \cdot x^2 \in \mathbb{Z}_p $

    内積を Vector Polynomial の内積の定義に従って計算すると、

    $ t_0 = z^2 \cdot \upsilon + \delta (y, z) $
    $ t_1 = \langle \mathbf{l_1}, \mathbf{r_0} \rangle $
    $ t_2 = \langle \mathbf{l_1}, \mathbf{r_1} \rangle $

    となるが、実際はこれだと $l(x)$ の定数項と $r(x)$ 1 次の項をかけ合わせた項が欠けていて計算が合わないので、内積の定義を以下の様に修正する。

    $ t_0 = z^2 \cdot \upsilon + \delta (y, z) $
    $ t_1 = \langle \mathbf{l_1}, \mathbf{r_0} \rangle + \langle \mathbf{l_0}, \mathbf{r_1} \rangle $
    $ t_2 = \langle \mathbf{l_1}, \mathbf{r_1} \rangle $

    詳細については後述。$t_0$ は (39) の右辺 $ z^2 \cdot \upsilon + \delta (y, z) $ と等しい。

1. 証明者が $t_1, t_2$ のコミットメント $T_1, T_2$ を計算して、証明者に送る
    $ \tau_1, \tau_2 \in \mathbb{Z}_p $ (random)
    $ T_1 = g^{t_1} h^{\tau_1} \in \mathbb{G} $
    $ T_2 = g^{t_2} h^{\tau_2} \in \mathbb{G} $
1. 検証者がランダムな $ x \in \mathbb{Z}_p^* $ を選択して、証明者に送る
1. 証明者が $l(x), r(x)$ を $x$ で評価した $\mathbf{l}, \mathbf{r}$、とその内積 $\hat{t}$ を計算する。また、コミットメントのランダムネス作成に使われた値をまとめた、$\tau_x, \mu$ も計算する。そして、$\mathbf{l}, \mathbf{r}, \hat{t}, \tau_x, \mu$ を検証者に送る

    （計算の詳細）　
    $ \mathbf{l} = l(x) = \mathbf{a}_L - z \cdot \mathbf{1}^n + \mathbf{s}_L \cdot x \in \mathbb{Z}_p ^n $
    $ \mathbf{r} = r(x) = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n \in \mathbb{Z}_p ^n $
    $ \hat{t} = \langle \mathbf{l}, \mathbf{r} \rangle \in \mathbb{Z}_p $
    $ \tau_x = \tau_2 \cdot x^2 + \tau_1 \cdot x + z^2 \cdot \gamma \in \mathbb{Z}_p $
    $ \mu = \alpha + \rho \cdot x \in \mathbb{Z}_p $
1. 検証者は、$ \mathbf{a_R} \circ \mathbf{y}^n $ へのコミットメントを作るジェネレーター $ \mathbf{h'} = \mathbf{h}^{\mathbf{y}^{-n}} \in \mathbb{G}^n $ を準備して、$ \mathbf{l} = l(x)$、$ \mathbf{r} = r(x) $、$ t(x) = \langle \mathbf{l}, \mathbf{r} \rangle $ が成り立つことを確認する。　

    （計算の詳細）
    $ h'_i = h_i^{(y^{-i+1})} \in \mathbb{G} \ \forall i \in [1,n] $
    $ g^{\hat{t}} h^{\tau_x} \ ?= V^{z^2} \cdot g^{\delta (y, z)} \cdot T_1^x \cdot T_2^{x^2} $ (65) // $\hat{t}$ と $t(x)$ が一致していることをチェック
    $ \hat{t}\ \ ?= \langle \mathbf{l}, \mathbf{r} \rangle \in \mathbb{Z}_p $ ($\hat{t}$ が正しいことをチェック)
    $ P = A \cdot S^x \cdot \mathbf{g}^{-z} \cdot (\mathbf{h}')^{z \cdot \mathbf{y} + z^2 \cdot \mathbf{2}^n} \in \mathbb{G} $ (66) // $l(x), r(x)$ へのコミットメントを計算
    $ P\ \ ?= h^u \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}')^{\mathbf{r}} $ (67) // $\mathbf{l}, \mathbf{r}$ がコミットメントと一致することを確認
    $ \hat{t}\ \ ?=　\langle \mathbf{l}, \mathbf{r} \rangle \in \mathbb{Z}_p $ (68)

## Fiat-Shamir Heuristic
検証者にランダムな値を選択させる代わりに、その時点でのトランスクリプトに対するハッシュ値を使う。例えば、

$y = H(\lbrace V,n \rbrace, A, S)$
$z = H(A, S, y)$

のように、Range Proof のパラメーターや、作成時点までに作られた値を元にハッシュを計算して、その値でランダムな値を代替する。

### Inner Product Argument を使った効率改善
(67), (68) は
$ P\ \ ?= h^u \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}')^{\mathbf{r}} $ (67) 
$ \hat{t}\ \ ?=　\langle \mathbf{l}, \mathbf{r} \rangle \in \mathbb{Z}_p $ (68)

で、Inner Product Argument は、証明者が、

$ P = \mathbf{g^{a} h^{b}} \in \mathbb{Z_p} $
$ c = \langle \mathbf{a,b} \rangle $

が成り立つ $\mathbf{a,b}$ を知っていることを、検証者に納得させるものなので、

$ \mathbf{a} = \mathbf{l} $
$ \mathbf{b} = \mathbf{r} $
$ \mathbf{h} = \mathbf{h'} $
$ \mathbf{c} = \mathbf{\hat{t}} $
$ \mathbf{P} = \mathbf{P} h^{-u} $

とすると、証明のステップ 6 の $ \mathbf{l},  \mathbf{r} $ を送る部分を、Inner Product Argument の実行で置き換えることができる。

こうすることで、証明者が検証者に送る要素数 $2n$ の $ \mathbf{l}, \mathbf{r} $ を、$2 \cdot \lceil log_2(n) \rceil + 4$ に抑えることができて、効率が改善する。

### \<l(x), r(x)\> の計算の詳細

$ l(x), r(x) $ の項を次数ごとに整理すると
　
$ l(x) = (\mathbf{a}_L - z \cdot \mathbf{1}^n) + \mathbf{s}_L \cdot x 
 $
$ \mathbf{l_0} = \mathbf{a}_L - z \cdot \mathbf{1}^n $
$ \mathbf{l_1} = \mathbf{s}_L $

$ r(x) = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n \in \mathbb{Z}_p^n $
$ \mathbf{r_0} = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n $
$ \mathbf{r_1} = \mathbf{y}^n \circ \mathbf{s}_R $

上で修正した Vector Polynomial の内積の定義は

$ \langle l(x), r(x) \rangle = \langle \mathbf{l_0}, \mathbf{r_0} \rangle \cdot x^{0+0} + \langle \mathbf{l_1}, \mathbf{r_0} \rangle \cdot x^{1+0} + \langle \mathbf{l_0}, \mathbf{r_1} \rangle \cdot x^{0+1} + \langle \mathbf{l_1}, \mathbf{r_1} \rangle \cdot x^{1+1} $

なので、$t(x)$ の定義

$ t(x) = \langle l(x), r(x) \rangle = t_0 + t1 \cdot x + t2 \cdot x^2 \in \mathbb{Z}_p $

と照らし合わせてみると　

$t_0 = \langle \mathbf{l_0}, \mathbf{r_0} \rangle \cdot x^{0+0} = \langle \mathbf{a}_L - z \cdot \mathbf{1}^n , \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n  \rangle $
　
で、$\mathbf{S}_L, \mathbf{S}_R$ 導入前の内積の式 (39) の左辺と一致する。また、なので、(39) の右辺 $ t_0 = z^2 \cdot \upsilon + \delta (y, z) $ とも等しい。

$t_1, t_2$ については、　　

$ t_1 = \langle \mathbf{l_1}, \mathbf{r_0} \rangle + \langle \mathbf{l_0}, \mathbf{r_1} \rangle = \langle \mathbf{s}_L, \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n \rangle + \langle \mathbf{a}_L - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{s}_R \rangle = (\mathbf{s}_L \cdot \mathbf{y}^n \cdot \mathbf{a}_R + \mathbf{s}_L \cdot \mathbf{y}^n \cdot z \cdot \mathbf{1}^n + z^2 \cdot \mathbf{2}^n) + (\mathbf{a}_L \cdot \mathbf{y}^n \cdot \mathbf{s}_R - z \cdot \mathbf{1}^n \cdot \mathbf{y}^n \cdot \mathbf{s}_R) $

$ t_2 = \langle \mathbf{l_1}, \mathbf{r_1} \rangle = \langle \mathbf{s}_L, \mathbf{y}^n \circ \mathbf{s}_R \rangle = \mathbf{s}_L \cdot \mathbf{y}^n \cdot \mathbf{s}_R$

となる。

### (65) についての補足
$ g^{\hat{t}} h^{\tau_x} \ ?= V^{z^2} \cdot g^{\delta (y, z)} \cdot T_1^x \cdot T_2^{x^2} $ (65)

- 左辺は、$ \langle \mathbf{l}, \mathbf{r} \rangle $ が secret で、ランダムネスの $ \tau_x $ に、右辺のランダムネス部分が集約されている。
- 右辺は、コミットメントの secret 部分と $g^{\delta (y, z)}$ を足すと、$t(x)$ の右辺になる。

#### 左辺
$ t_0 = \upsilon \cdot z^2 + \delta (y, z) $
$ \hat{t} = \langle \mathbf{l}, \mathbf{r} \rangle \in \mathbb{Z_p} $
$ = t(x) = t_0 + t_1 \cdot x + t_2 \cdot x^2 $
$ = \upsilon \cdot z^2 + \delta (y, z) + t_1 \cdot x + t_2 \cdot x^2 $
$ t_x = \gamma \cdot z^2 + \tau_1 \cdot x + \tau_2 \cdot x^2 $

$ g^{\hat{t}} \cdot h^{t_x} $

#### 右辺
$ V = h^{\gamma} g^{\upsilon} \in \mathbb{G} $
$ {\tau}_1 \in \mathbb{Z} _ {p} $ (random)
$ {\tau}_2 \in \mathbb{Z} _ {p} $ (random)
$ T_1 = g^{t_1} h^{{\tau}_1} \in \mathbb{G}$
$ T_2 = g^{t_2} h^{{\tau}_2} \in \mathbb{G}$

$ V^{z^2} \cdot g^{\delta (y,z)} \cdot T_1^x \cdot T_2^{x^2} $
$= (h^{\gamma} g^{\upsilon})^{z^2} \cdot g^{\delta (y,z)} \cdot (g^{t_1} h^{{\tau}_1})^x \cdot (g^{t_2} h^{{\tau}_2})^{x^2}$
$= (h^{\gamma \cdot z^2} g^{\upsilon \cdot z^2}) \cdot g^{\delta (y,z)} \cdot (g^{t_1 \cdot x} h^{{\tau}_1 \cdot x}) \cdot (g^{t_2 \cdot {x^2}} h^{{\tau}_2 \cdot {x^2}})$
$= g^{\upsilon \cdot z^2} \cdot g^{\delta (y,z)} \cdot g^{t_1 \cdot x} \cdot g^{t_2 \cdot {x^2}} \cdot h^{\gamma \cdot z^2} \cdot h^{{\tau}_1 \cdot x} \cdot h^{{\tau}_2 \cdot {x^2}} $
$= g^{\upsilon \cdot z^2 + \delta (y,z) + t_1 \cdot x + t_2 \cdot {x^2}} \cdot h^{\gamma \cdot z^2 + {\tau}_1 \cdot x + {\tau}_2 \cdot {x^2}} $
$= g^{\hat{t}} \cdot h^{t_x} $

### (66) についての補足
$ P = A \cdot S^x \cdot \mathbf{g}^{-z} \cdot (\mathbf{h}')^{z \cdot \mathbf{y} + z^2 \cdot \mathbf{2}^n} \in \mathbb{G} $ (66)

$ \mathbf{h'} = \mathbf{h} ^ {(\mathbf{y} ^{-n})} = (h_1, h_2^{(y^{-1})}, h_2^{(y^{-2})}, ..., h_n^{(y^{-n + 1})} ) $

- $ A \cdot S^x $ の $h$ 成分を抜き出すと $ h^{\mu} $ になり、$\mathbf{g}$ 成分を抜き出したものと $ \mathbf{g} ^ {-z} $ を足すと、$ \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} = \mathbf{g} ^ {\mathbf{l}} $ になる。
- $ A \cdot S^x $ の $\mathbf{h}$ 成分を抜き出して、$\mathbf{h}'$ ベースに変換した後で、式中の $\mathbf{h}'$ 項と結合すると $ \mathbf{r} $ になる。


#### 右辺
$ \alpha \in \mathbb{Z} _ {p} $ (random)
$ \rho \in \mathbb{Z} _ {p} $ (random)
$ A = h^{\alpha} \mathbf{g} ^ { \mathbf{a}_L } \mathbf{h} ^ { \mathbf{a}_R } \in \mathbb{G} $
$ S = h^{\rho} \mathbf{g} ^ { \mathbf{s}_L } \mathbf{h} ^ { \mathbf{s}_R } \in \mathbb{G} $

$ P = A \cdot S^x \cdot \mathbf{g} ^{-z} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = (h^{\alpha} \mathbf{g} ^ { \mathbf{a}_L } \mathbf{h} ^ { \mathbf{a}_R }) \cdot (h^{\rho} \mathbf{g} ^ { \mathbf{s}_L } \mathbf{h} ^ { \mathbf{s}_R })^x \cdot \mathbf{g} ^{-z} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = (h^{\alpha} \mathbf{g} ^ {\mathbf{a}_L} \mathbf{h} ^ { \mathbf{a}_R }) \cdot (h^{\rho \cdot x} \mathbf{g} ^ {\mathbf{s}_L \cdot x} \mathbf{h} ^ {\mathbf{s}_R \cdot x}) \cdot \mathbf{g} ^{-z} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = (h^{\alpha} h^{\rho \cdot x}) \cdot (\mathbf{g} ^ {\mathbf{a}_L} \mathbf{g} ^ {\mathbf{s}_L \cdot x} \mathbf{g} ^{-z}) \cdot (\mathbf{h} ^ { \mathbf{a}_R } \cdot  \mathbf{h} ^ {\mathbf{s}_R \cdot x}) \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot (\mathbf{h} ^ { \mathbf{a}_R } \cdot  \mathbf{h} ^ {\mathbf{s}_R \cdot x}) \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot \mathbf{h} ^ {\mathbf{a}_R + \mathbf{s}_R \cdot x} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot ((\mathbf{h}')^{\mathbf{y}^n}) ^ {\mathbf{a}_R + \mathbf{s}_R \cdot x} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot (\mathbf{h}')^{\mathbf{y} \circ (\mathbf{a}_R + \mathbf{s}_R \cdot x)} \cdot (\mathbf{h}')^{z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot (\mathbf{h}')^{\mathbf{y} \circ (\mathbf{a}_R + \mathbf{s}_R \cdot x) \cdot z \cdot \mathbf{y}^n + z^2 \cdot \mathbf{2}^n } $
$ = h^{\alpha + \rho \cdot x} \cdot \mathbf{g} ^ {\mathbf{a}_L + \mathbf{s}_L \cdot x -z} \cdot (\mathbf{h}')^{\mathbf{y} \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) \cdot + z^2 \cdot \mathbf{2}^n } $

### (67) についての補足

$ P\ \ ?= h^u \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}')^{\mathbf{r}} $ (67)

#### 右辺
$ \mu = \alpha + \rho \cdot x \in \mathbb{Z} _ {p} $
$ \mathbf{l} = \mathbf{a}_L - z \cdot \mathbf{1}^n + \mathbf{S}_L \cdot x \in \mathbb{Z} ^n _ {p} $
$ \mathbf{r} = \mathbf{y} ^ n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n \in \mathbb{Z} ^n _ {p} $

$ h^\mu \cdot  \mathbf{g} ^ \mathbf{l} \cdot (\mathbf{h}') ^ \mathbf{r} $
$ = h ^ {\alpha + \rho \cdot x} \cdot \mathbf{g} ^ { \mathbf{a}_L - z \cdot \mathbf{1}^n + \mathbf{s}_L \cdot x }  \cdot (\mathbf {h'})^{\mathbf{y} ^ n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n} $
$ = h ^ {\alpha + \rho \cdot x} \cdot \mathbf{g} ^ { \mathbf{a}_L + \mathbf{s}_L \cdot x - z}  \cdot (\mathbf {h'})^{\mathbf{y} ^ n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n} $

## 参考文献
- [Bulletproofs: Short Proofs for Confidential Transactions and More](https://eprint.iacr.org/2017/1066.pdf)
- [Confidential Transactions - Investigation](https://elementsproject.org/features/confidential-transactions/investigation)