MimbleWimble
トランザクションベースの通貨システムに必要な要素
input = output を検証可能
output > 0 を検証可能
1 -> 5 , -4 みたいなことをされるとコインを生成できてしまうため
言葉の定義
存在するのはコミットメントのみ(JPYにおける硬貨みたいな)
コミットメント : $ r*G + v*H
G,H : 楕円曲線暗号の生成元 (G ≠ H)
r : blinding factor (秘密鍵)
v : コインの量
r,vが知っていれば,コミットメントを使い,トランザクションを作成できる(使っていない状態で知られてはならない)
コミットメントに対してr,vを知っていることが所有していることにつながる.
input = output をどう示すか
送金額を秘匿している以上,(inputの合計金額) = (outputの合計金額) を示さなければならない.
簡単な場合から一般的な場合に話を広げる.
1) 自分のコミットメントだけで送金する場合
これは簡単である.以下の2つのコミットメント($ C_1, C_2)を持っているとする
$ C_1 = r_1*G + v_1 * H
$ C_2 = r_2*G + v_2 * H
アウトプットのコミットメントを$ C_3 = r_3*G + v_3 * Hとすると,$ C_1 + C_2 = C_3を検証すれば良い
Goal: $ C_1 + C_2 = C_3 \Rightarrow v_3 = v_1 + v_2 without $ r_1, r_2, v_1, v_2
proof:
$ C_1 + C_2 - C_3 = 0
$ \Leftrightarrow (r_1*G + v_1 * H) + (r_2*G + v_2 * H) - (r_3*G + v_3 * H) = 0
$ \Leftrightarrow (r_1 + r_2 - r_3)*G + (v_1 + v_2 - v_3) * H = 0
(楕円曲線上の和の交換法則,スカラー倍の分配法則)
離散対数問題が効率的に解かれてなければ,$ r_3 = r_1 + r_2 \ , \ v_3 = v_1 + v_2
結論)
送信者:$ r_1, r_2から$ r_3 = r_1 + r_2を管理すれば良い.
検証者:$ C_1 + C_2 = C_3を確認すれば良い
2)他者に送金する場合
結論)
送受信者:$ C_{output} - C_{input}に対応した署名を提出する.
検証者 :提出された署名が$ C_{output} - C_{input}によって検証できることを確認する.
1)と同様の方法ではうまくいかないことが簡単な送金でわかる.
アリス($ C_a) → ボブ($ C_b)を考える($ C_a = r_a*G + v_a * H, $ C_b = r_b*G + v_b * H)
$ v_a = v_bだが,1)の検証方法では$ r_a = r_bとなる.
これでは送金したアリスが$ r_b, v_bを知っているので$ C_bを使って送金ができてしまう.
そこで,$ r_b≠ $ r_aなる$ r_bで②と同様の計算を行う
$ C_b - C_a = (r_b - r_a)*G + (v_b - v_a)* H……③
ここで,$ v_b - v_a = 0ならば③ = $ (r_b - r_a)*Gとなり,これは秘密鍵$ r_b - r_aに対応した公開鍵となるので,$ r_b - r_aで作成した署名を③で検証できる.
逆にその署名を示すことができれば,$ v_b - v_a = 0を現実的に確かめられたこととなる.
すなわち以下の順序でTransactionを作成する.
ⅰ) アリスはボブに送金額 $ v_a とblinding factor $ r_a(複数インプットやお釣りがある場合はその和)を伝える.
ⅱ) ボブはblinding factor $ r_b をランダムに決め,$ r_b - r_aを計算.
ⅲ) ボブは$ r_b - r_aで署名を作成
ⅳ) ボブはアリスからのコミットメント,自身のコミットメント,署名からトランザクションを作成
output > 0 をどう示すか
Range Proofと呼ばれる
前提知識
証明者:自身の鍵ペアを含む複数の公開鍵,署名を提出
検証者:複数の公開鍵のどれか1つに対応する秘密鍵によって署名されたことを検証(どれなのかはわからない)
コミットメントの性質
証明者は数量が含まれていない(v = 0)コミットメントにのみ署名を行える
気持ち
数量をbit表現における各bitに分割し,bitごとに( 0 or 1 )の証明を行う.
リング署名により,各bitにおいて,0なのか1なのかは検証者にはわからない(数量の秘匿)
手順 + 具体例
具体例の前提
簡単のため数量は3桁の2進数とする(7までの自然数)
コミットメント C の数量をrange proof
$ C = 85*G + 2*H (数量:2)
証明者
1. 数量をbit表現における各bitに分割したようなコミットメントに分割
数量をビット表現に $ 2 \rightarrow 010
blinding factorをビット表現の桁数分に乱数で分割 $ 85 \rightarrow 18 + 42 + 25
$ C \rightarrow C_3 + C_2 + C_1 ($ C_nはn桁めの数量)
$ C_3 = 18*G + 2^2*0*H = 18*G
$ C_2 = 42*G + 2^1*1*H = 42*G + 2*H
$ C_1 = 25*G + 2^0*0*H = 25*G
2. 各bitに分割したコミットメント($ C_n)に対して,$ c_n = C_n - 2^{n-1}*Hを計算し,($ C_n, c_n)に対しリング署名
($ C_n, c_nのどちらかは$ v = 0となる)
$ c_3 = C_3 - 2^2*H = 18*G - 4*H
$ c_2 = C_2 - 2^1*H = 42*G
$ c_1 = C_1 - 2^0*H = 25*G - 1*H
$ C_3, c_2, C_1は秘密鍵を知っている(blinding factor)ので,署名可能
($ C_1, c_1), ($ C_2, c_2), ($ C_3, c_3)それぞれのペアに対してリング署名(3つのリング署名)
3. 全てのnに対して($ C_n, c_n, ($ C_n, c_nのリング署名))を提出
検証者
分割したコミットメントの和が元のコミットメントになることを確かめる ($ \sum_n C_n = C)
それぞれ各bitの数量に対応することを検証 ($ c_n + 2^{n-1}*H = C_n)
全てのnに対して ($ C_n, c_n )のリング署名を検証
($ \underline{C_n > c_n})という大小関係から数量はバレないのか?
あらゆる数量に対して,大きい方$ C_nの和が元のコミットメントになる
ビットの0, 1に対して($ C_n, c_n)どちらに署名できるかは変わるが,どちらに対応したものなのかはわからない
→ どの数量のコミットメントであろうが,検証者が得られる情報は変わらず,数量はわからない
ブロック
参考
Confidential Transaction
Range Proof