More than 1 year has passed since last update.

Improved Inner Product Argument の検証

Last updated at 2023-04-11Posted at 2023-04-10

Range Proof は、いくつかの検証式について、左辺の要素を足し合わせたものの加法逆元に右辺の要素を足していって、結果が加法単位元になれば成功という形で簡単に検証できる。ただ、Improved Inner Product Argument (以下 IIPA) を使う場合には、検証過程が複雑になる。

IIPA 対応部分の証明の検証

以下、証明の IIPA にかかわる部分がどのように検証されていくのかを、一番単純な 2 ラウンドのケースで見ていく。

2 ラウンドの IIPA の計算結果

$a=[a_1,a_2], b=[b_1,b_2]$ が IIPA への入力ベクター, $G_1,G_2$, $H_1,H_2, u$ が IIPA で使うジェネレーター、$c_factor$　が一部の Range Proof の実装で使われている $u$ の係数に掛け合わせる要素とすると、2 ラウンドの IIPA の結果は以下の通りになる。

$a = a_1 \cdot x_1 + a_2 \cdot x_1^{-1}$
$b = b_1 \cdot x_1^{-1}+b_2 \cdot x_1$
$Ls[0] = G_2^{a_1}+H_1^{b_2 y^{-1}} + u^{a_1 b_2 \cdot c_factor}$
$Rs[0] = G_1^{a_2}+H_2^{b_1 y^{-1}} + u^{a_2 b_1 \cdot c_factor}$

全ラウンドでの x と x 乗法逆元の復旧

IIPA の結果検証には、全ラウンドでの x と x 乗法逆元が必要になるので、証明の過程で x と x の乗法逆元が作った手順に従ってそれらの値を復元する。例えば Fiat-Shamir で各ラウンドの $L,R$ から x と x 乗法逆元を作っている場合は、こんな感じで $x$ と $x^{-1}$ を復元する。

Scalars xs, x_invs
for i in 0..num_rounds {
    fiat_shamir <- Ls[i]
    fiat_shamir <- Rs[i]
    Scalar x = fiat_shamir.Get()
    xs.add(x)
    x_invs.Add(x.invert())
}

ジェネレーターの係数の計算

IIPA に渡したジェネレーターのベクターは、係数を掛けられながら徐々に圧縮されて、最終的に一つのジェネレーターになる。

圧縮済みのジェネレーターは、入力として渡された 2 つのジェネレーターベクター $\mathbf{G}, \mathbf{H}$ の要素に係数 $\alpha, \beta$ が掛かったもの $G_1^{\alpha_1}, G_2^{\alpha_2}, ..., G_n^{\alpha_n}$ and $H_1^{\beta_1}, H_2^{\beta_2}, ..., H_n^{\beta_n}$ で構成されている。その構成要素は検証に必要になるので、入力ジェネレーターに掛け合わせて構成要素を作るための係数を計算する。この計算では、上で計算したラウンドごとの $x$ と $x^{-1}$ が必要になる。

このコードで、係数を計算できる。

gen_exps[1 << num_rounds; 1]
gen_exps[0] = x_invs[0]
gen_exps[1] = xs[0]

for i in 1..num_rounds {
    sl = 1 << (i + 1)
    s = sl -1
    while s > 0 {
        gen_exps[s] = gen_exps[s / 2] * xs[i]
        gen_exps[s - 1] = gen_exps[s / 2] * x_invs[i]
        s -= 2
    }
}

ここで作った gen_exps を、$G_i$ に頭から、$H_i$ に後ろから掛け合わせて、構成要素を作る。$n$ をラウンド数だとすると、$\alpha_i, \beta_i$ は以下のようになる。

$\alpha_1 = $ gen_exps$[0], \alpha_2 = $ gen_exps$[1], ...$
$\beta_1 = $ gen_exps$[n-1], \beta_2 = $ gen_exps$[n-2], ...$.

検証式の初期状態

$0 = \mathbf{G}^{\mathbf{bL} + \mathbf{sL}x} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x}$

左辺の $0$ は最後まで変わらないので、以下の説明では省略する。

全ラウンドの L と R を、検証式の右辺に追加する

まず、全ラウンドの $L$ と $R$ にラウンドごとの $x^2$ と $x^{-2}$ を掛けたものを、検証式の右辺に追加する。最終ラウンドでは、$L, R$ は計算されないので、2 ラウンドの場合は一組の $L^2$ と $R^{-2}$ が追加されることになる。

L

$Ls[0] \cdot x_1^2$

$=(G_2^{a_1} + H_1^{b_2} + u^{a_1 b_2 \cdot c_factor})^{x_1^2}$

$= G_2^{a_1x_1^2}+H_1^{b_2 x_1^2} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2}$

R

$Rs[0] \cdot x_1^{-2}$

$= (G_1^{a_2}+H_2^{b_1 \cdot y^{-1}} + u^{a_2 b_1 \cdot c_factor})^{x_1^{-2}}$

$= G_1^{a_2x_1^{-2}} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$

L + R

$Ls[0] \cdot x_1^2 + Rs[0] \cdot x_1^{-2}$

$= G_2^{a_1x_1^2}+H_1^{b_2 x_1^2} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2} + G_1^{a_2 x_1^{-2}} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$

$= G_1^{a_2x_1^{-2}} + G_2^{a_1x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2} + u^{a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$

$= G_1^{a_2 x_1^{-2}} + G_2^{a_1 x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2 + a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$

この時点での検証式は

$G^{bL + sLx} \cdot H^{bR + sRx} + G_1^{a_2 x_1^{-2}} + G_2^{a_1 x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2 + a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$

ジェネレーター u 部分の検証

次に、検証式の右辺に $u^t$ と $u^{a \cdot b \cdot c_factor}$ の加法逆元を追加する。

2 ラウンドの IIPA での、$a \cdot b \cdot c_factor$ は、

$(a_1 \cdot x_1+a_2 \cdot x_1^{-1})(b_1 \cdot x_1^{-1}+b_2 \cdot x_1) \cdot c_factor$

$= (a_1 \cdot b_1 + a_1 \cdot b_2 \cdot x_1^2 + a_2 \cdot b_1 \cdot x_1^{-2} + a_2 \cdot b_2) \cdot c_factor$

$= a_1 \cdot b_1 \cdot c_factor + a_1 \cdot b_2 \cdot x_1^2 \cdot c_factor + a_2 \cdot b_1 \cdot x_1^{-2} \cdot c_factor + a_2 \cdot b_2 \cdot c_factor$

となる。この要素を $u$ に掛けたものの加法逆元を、検証式に追加すると、

$\mathbf{G}^{\mathbf{bL} + \mathbf{sL}x} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + G_1^{a_2 x_1^{-2}} + G_2^{a_1 x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2 + a_2 b_1 \cdot c_factor \cdot x_1^{-2}} - u^{a_1 \cdot b_1 \cdot c_factor + a_1 \cdot b_2 \cdot x_1^2 \cdot c_factor - a_2 \cdot b_1 \cdot x_1^{-2} \cdot c_factor + a_2 \cdot b_2 \cdot c_factor}$

$= \mathbf{G}^{\mathbf{bL} + \mathbf{sL}x} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + G_1^{a_2 x_1^{-2}} + G_2^{a_1 x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} + u^{a_1 b_2 \cdot c_factor \cdot x_1^2 + a_2 b_1 \cdot c_factor \cdot x_1^{-2}} - (u^{a_1 \cdot b_1 \cdot c_factor} + u^{a_1 \cdot b_2 \cdot x_1^2 \cdot c_factor - a_2 \cdot b_1 \cdot x_1^{-2} \cdot c_factor} + u^{a_2 \cdot b_2 \cdot c_factor})$

$u^{a_1 \cdot b_1 \cdot c_factor} + u^{a_1 \cdot b_2 \cdot x_1^2 \cdot c_factor - a_2 \cdot b_1 \cdot x_1^{-2} \cdot c_factor} + u^{a_2 \cdot b_2 \cdot c_factor}$ の第 2 項と第 3 項が、検証式の　$u^{a_1 b_2 \cdot c_factor \cdot x_1^2 + a_2 b_1 \cdot c_factor \cdot x_1^{-2}}$ を打ち消して、上のような検証式になる。

また、$u^{a_1 \cdot b_1 \cdot c_factor} + u^{a_1 \cdot b_2 \cdot x_1^2 \cdot c_factor - a_2 \cdot b_1 \cdot x_1^{-2} \cdot c_factor} + u^{a_2 \cdot b_2 \cdot c_factor}$ の第 1 項と第 4 項は

$a_1 \cdot b_1 \cdot c_factor + a_2 \cdot b_2 \cdot c_factor$

$= (a_1 \cdot b_1 + a_2 \cdot b_2) \cdot c_factor$

$= \langle a, b \rangle \cdot c_factor$

$= t \cdot c_factor$

で、$u^t = u^{a_1 \cdot b_1 \cdot c_factor + a_2 \cdot b_2 \cdot c_factor}$ なので、$u^t$ を検証式に足すことで、検証式の残りの $u$ 項が打ち消されて、以下の項が検証式に残る。

$\mathbf{G}^{\mathbf{bL} + \mathbf{sL}x} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + G_1^{a_2 x_1^{-2}} + G_2^{a_1 x_1^2} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}}$

入力ジェネレーターベクター G, H に係数を掛けたものを追加する

G ジェネレーター

各 $G_i$ ジェネレーターについて、

Scalar gi_exp[i] = (a * gen_exps[i]).Negate()

を計算して、$G_i$ ジェネレーターに gi_exp を掛けたものを検証式に追加する。

2 ラウンドの場合、gen_exps は、

gen_exps[0] $=x^{-1}_1$
gen_exps[1] $=x_1$

なので、

gi_exps[0] $=-(a_1 \cdot x_1 + a_2 \cdot x_1^{-1}) \cdot x^{-1}_1 = -(a_1 + a_2 \cdot x_1^{-2})$
gi_exps[1] $= -(a_1 \cdot x_1 + a_2 \cdot x_1^{-1}) \cdot x_1 = -(a_1 \cdot x_1^2 + a_2)$

となる。$G_i$ ジェネレーターに掛けてみると、

$-G_1^{a_1 + a_2 \cdot x_1^{-2}} - G_2^{a_2 + a_1 \cdot x_1^2}$

$= -G_1^{a_1} - G_2^{a_2} - G_1^{a_2 \cdot x_1^{-2}} - G_2^{a_1 \cdot x_1^2}$

検証式に追加して、

$= \mathbf{G}^{\mathbf{bL} + \mathbf{sL}x} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - G_1^{a_1} - G_2^{a_2}$

次に、検証式に $\mathbf{G}^{-z \cdot \mathbf{1}^n}$ を追加する。

$\mathbf{G}^{\mathbf{bL} + \mathbf{sL}x - \mathbf{z}} \cdot \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - G_1^{a_1} - G_2^{a_2}$

また、

$l(x) = \mathbf{bL} - z \cdot 1^n + \mathbf{sL} \cdot x$

で、$l(x)$ は、$[l_1, l_2]$ として IIPA に渡されて、IIPA で $[a_1, a_2]$ として処理されるので、

$G_1^{a_1} + G_2^{a_2} + \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - G_1^{a_1} - G_2^{a_2}$

となり、はじめと終わりの $G_i$ 項が打ち消し合って、結果検証式は

$\mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}}$

となる。

H ジェネレーター

各 $H_i$ ジェネレーターについて、

Scalar hi_exp = (b * y_inv_pow[i] * gen_exps[n - 1 - i]).Negate()

を計算して、$H_i$ ジェネレーターに hi_exp を掛けたものを検証式に追加する。y_inv_pow は　$y^0, y^{-1}, y^{-2}, ...$ の配列。

2 ラウンドの場合、gen_exps は、

gen_exps[0] $=x^{-1}_1$
gen_exps[1] $=x_1$

なので、

hi_exps[0] $= -((b_1 \cdot x_1^{-1}+b_2 \cdot x_1) \cdot y^0 \cdot x_1) = -(b_1 + b_2 \cdot {x_1^2})$
hi_exps[1] $= -((b_1 \cdot x_1^{-1}+b_2 \cdot x_1) \cdot y^{-1} \cdot x^{-1}_1) = -(b_1 \cdot y^{-1} \cdot x_1^{-2} + b_2 \cdot y^{-1})$

となる。$H_i$ ジェネレーターに掛けてみると、

$-H_1^{b_1 + b_2 \cdot {x_1^2}} - H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2} + b_2 \cdot y^{-1}}$

$= -H_1^{b_1} - H_1^{b_2 \cdot {x_1^2}} - H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - H_2^{b_2 \cdot y^{-1}}$

この第 2 項と第 3 項が、検証式の $H_1, H_2$ を打ち消す。結果は、

$\mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{b_2 x_1^2} + H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - H_1^{b_1} - H_1^{b_2 \cdot {x_1^2}} - H_2^{b_1 \cdot y^{-1} \cdot x_1^{-2}} - H_2^{b_2 \cdot y^{-1}}$

$= \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}}$

次に、以下を計算して、$H_i$ ジェネレーターに掛けたものを検証式に追加する。y_pow は　$y^0, y^{1}, y^{2}, ...$ の配列。

hi_exps[i] = (z * y_pow[i] + z^2) * y_inv_pow

2 ラウンドの IIPA では以下の要素が作られる。

$H_1^{z + z^2} + H_2^{(z \cdot y + z^2) \cdot y^{-1}}$

$= H_1^{z + z^2} + H_2^{z + z^2 \cdot y^{-1}}$

検証式に追加すると、

$\mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} - H_1^{b_1} - H_1^{b_2 \cdot y^{-1}} + H_1^{z + z^2} + H_2^{z + z^2 \cdot y^{-1}}$

$= \mathbf{H}^{\mathbf{bR} + \mathbf{sR}x} + H_1^{z + z^2} + H_2^{z + z^2 \cdot y^{-1}} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}}$

$= H_1^{bR[0] + sR[0] \cdot x + z + z^2} + H_2^{bR[1] + sR[1] \cdot x + z + z^2 \cdot y^{-1}} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}}$

$= H_1^{bR[0] + z + sR[0] \cdot x + z^2} + H_2^{bR[1] + sR[1] \cdot x + z + z^2 \cdot y^{-1}} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}}$

ここで、

$r(x)=\mathbf{y}^n \circ (\mathbf{bR} + z \cdot \mathbf{1}^n + \mathbf{sR} \cdot x) + z^2 \cdot \mathbf{1}^n$

$\mathbf{y}^n$ は、$y^0, y^1, y^2, ...$ なので、2 ラウンド IIPA での、$r(x)$ を $r_1, r_2$ 形式で表すと、

$r_1 = bR[0] + z + sR[0] \cdot x + z^2$

$r_2 = bR[1] \cdot y + z y + sR[1] \cdot xy + z^2$

となる。

Scalar hi_exp = (b * y_inv_pow[i] * gen_exps[n - 1 - i]).Negate()

では、検証式の $H_i$ ジェネレーターに y_inv_pow$=y^0, y^{-1}, y^{-2}, ...$ が掛けたので、同じ様に $r_1, r_2$ に $y^0, y^{-1}, y^{-2}, ...$ を掛ける。すると、

$r_1 \cdot y^0 = r_1 = bR[0] + z + sR[0] \cdot x + z^2$

$r_2 \cdot y^{-1} = bR[1] + z + sR[1] \cdot x + z^2 \cdot y^{-1}$

となるので、検証式の第 1, 2 項の係数を置き換えて、

$H_1^{r_1} + H_2^{r_2 \cdot y^{-1}} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}}$

$r_i$ は、IIPA の $b_i$ なので、置き換えて

$H_1^{b_1} + H_2^{b_2 \cdot y^{-1}} - H_1^{b_1} - H_2^{b_2 \cdot y^{-1}} = 0$

これで右辺と左辺がどちらも $0$ になるので、検証が成立する。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up