MimbleWinmbleをチョット整理 (トランザクションの構造と署名)
理解を深めるためにトランザクションの構造と署名の仕方をキャッチアップ。
Referencesに記載したブログや資料が大変ためになりました :bow:
お勉強
References
一般的なコミットメント
r ... blinding factor
$ commitment = Hash(r || data)
持ってるデータを相手に明かさずに、あるデータを知っていること / あるメッセージをある時点で書いたことを証明するコミュニケーションの手段
公開フェーズでコミットされた値を相手に明かす
中身を封じたままメッセージを渡すことができる(送信側のメリット)
封じられたメッセージを送信者が後から書き換えることはできない(受信側のメリット)
コイン投げの例
離れたところにいるAliceとBobがコイン投げで賭け事を行うとする
Aliceは表・裏どちらに張るかを予め宣言し、Bobがコインを投げ、結果を伝える
何も仕掛けが無いと、Aliceは実際のコインを確認できないので、Bobは自分が勝つように嘘をつけばいい
コミットメントを使う場合は下記のようにギャンブルが実施される
Aliceはコインの表・裏を選んで、その値をコミットし(コミットメントを生成し)、コミットメントをBobに伝える
Bobはコインを投げる、結果をAliceに伝える
BobにはAliceの選んだ値は解らない
Aliceはコミットした値をBobに伝える
Bobはコミットした値から検証用のコミットメントを生成し、Aliceから受け取ったコミットメント= 検証用のコミットメントであることを確かめる
コミットメントからコミットの復元ができない(Bob側がAliceの選択を盗み見ること)かつAlice側が選んだ値以外の値で同じコミットメントを生成できない限り、AliceもBobもずるができない
署名 vs コミットメント
どちらでも言質が取れる
署名は言質の中身が相手に見えてしまう
手紙に差出人のサインをして渡すイメージ
コミットメントは中身を明かさずに言質を取る
手紙に鍵がないと絶対に解けない封をして相手に予め渡しておく
あとで答え合わせ
コミットメントにまつわる用語や性質
コミットメントは2つのフェーズから構成される
コミットフェーズ
a value is chosen and specified
公開フェーズ(reveal phase)
the value is revealed and specified
性質:
秘匿性 ... 受信者がコミットフェーズ終了時にコミットされた値の情報を知りえないことを保証する。
完全秘匿 ... コミットされた値とコミットメントが完全に独立(無限の計算能力を持ってもコミットされた値がわからない)
計算量秘匿 ... 現実的な計算能力ではコミットされた値の識別ができない
拘束性 (binding property)
送信者が公開フェーズにコミットした値を違う値に書き換えができないことを保証する
秘匿性と同じ意味で、完全拘束と計算量拘束の2パターンが存在する
コミットメント方式は完全秘匿 か 完全拘束のどちららか1つしか満たすことができない
便利な性質をもったコミットメントへの欲求
cmをコミットメントとしたとき、下記のようなコミットメントが構成できるとすると便利そうである
コミットメントの加算が可能(コミットメント同士を足すと足し算した結果のコミットメントになる)
$ cm(b_1, d_1) + cm(b_2, d_2) = cm(b_1 + b_2, d_1 + d_2)
$ cm(b_1, d_1) - cm(b_1, d_1) = 0
additive homomorphic bit commitmentと呼ばれる
単純なハッシュ関数を使うとこの性質は満たされない(そりゃそうだ)
こんなときに足し算できるコミットメントマンがいてくれたらなー
https://gyazo.com/5384244951d8506c8178ab753feb18a6
Pedersen Commitmentへ
s ... 秘密鍵
G ... basepoint
$ p = sG として公開鍵$ pを生成
(pとGがわかってもsはわからないよ!(楕円曲線上の離散対数問題))
楕円曲線上の点は加群をなすので $ p_iを公開鍵とすると
$ p_1 + p_2 = s_1G + s_2G = (s_1 + s_2)G
コミットメントとして
$ cm(x,a) = xG + aH
$ x ... blinding factor (送信側しか知らない値)
$ a ... コミットする値 (mimblewimble送金の場合はコインの量)
H は楕円曲線上のGとは相異なる点であり $ H = qG と書くことができる。qは誰にも知られていない(G, Hからqは計算できない、楕円曲線上の離散対数問題)
(具体的な作り方としては生成元であるGを適当なハッシュ関数に通して点Hを得る)
このとき
$ cm(x_1, a_1) + cm(x_2, a_2) = x_1G + a_1 H + x_2 G + a_2 H = (x_1 + x_2) H + (a_1 + a_2) G = cm(x_1 + x_2, a_1 + a_2)
が成り立つ。
コミットメントとして利用するために必要な性質を持っていることを検証しておくと、
$ xG + aH = yG + bH
が $ x != y, a != bの下で成り立つとすると
$ H = (a-b)^{-1}(y-x)G
が成り立つことになる。これは離散対数HのGに対する楕円曲線上の離散対数を求めていることにほかならないので、離散対数問題が困難であるという過程の下、これを求めるのは難しい
Pedersen Commitmentはベクトル形式にした下記の形にも容易に拡張することができる。
https://gyazo.com/a534d0f5a52101eeab79cbc629edff87
沢山のデータを楕円曲線上の1点としてコミットできる。
$ G_i はハッシュ関数などを使うと容易に構成できる。(Hを作るのと同様)
MimbleWimbleのやっていること
tx_outのコイン量(送金額)をpedersen commitmentで置き換える
https://gyazo.com/ec64ddad670057b6effaa4ec9e711c9c
https://gyazo.com/3c86548a6576755bb9f6fed3883b2ffc
ビットコインの場合
tx_out : value + scriptPubKey
mimbleWimbleの場合
xG + aH (32byte)(ロックスクリプトは存在しない
x, aを知らない第三者にはコインの量が解らない
commitmentは楕円曲線上の1点なので公開鍵とみなせる
通貨として必要な性質を満たせるの?
ここで考慮しないといけないことは3つ
インプットのコイン量の和 - アウトプットのコイン量の和 + 手数料 = 0
bitcoinのUTXOモデルにおける検証と大まかに言うと同じ(雑)
additive homomorphicなので、手数料を適切に設定すれば成り立つ。
マイナスの金額の送金ができないこと(例えばmod 5 だとすると 3=-2なので、マイナスの金額を扱えないようにする必要がある
Range proofを用いる
更にいうとRange ProofにRing Signatureを使う
ScriptPubKeyがないのにどうやって送金するねん問題
アドレスないってどういうこっちゃ
mosa_siru.icon < addressや公開鍵のかわりに、相手のIPやendpointが必要。専用の通信チャネルが必要なかんじ
受信者側が受信者のみが知り得る値を使って(=秘密鍵)署名をする
トランザクションの作り方
Grinでは直接 excessを送らず、送信者と受信者の署名を集約してノードにブロードキャストする
例を見ながら考える & 楕円曲線上の署名検証の仕組みを考えると受信者側のみが知っているブラインドファクターと、ブラインドファクターのexecessを秘密鍵として扱えることが分かる
未解決な疑問
man in the middle 的なのは防げるのか (Alice -> Bobに送信する時に盗聴されても盗まれない?)
通信路は暗号化されている前提だろうなぁ...
手数料トランザクションをマイナーに付与するためにどのような仕組みを用いているのか
そもそもビットコインってどうなってるんだっけか.
差分が手数料になるわけだけど、ブロックを繋げた人がブラインドファクターを設定して適当に署名する?
ブロックのつなげ方がわからないとだめだな。
Mimble Wimbleの場合は受信者が署名を生成する。
インプットになっているコミットメントに対応するブラインドファクターは使うことができないのだろう(ビットコインでOUTが紐付いている使用済みトランザクションを秘密鍵を持っていても使用することができないように)
トランザクションの構造
インプット
アウトプット
トランザクションカーネル
手数料
excess
excessを利用した署名
lock_height
を持つ
Grinのブロックを垣間見る
Grinでは
送信者は受信者に向けて (excess) * G を送る
受信者は(excess)自体はわからないので 、お互いのblinding factorから署名を作って署名集約をするらしい。(ノードでは集約された署名を検証するのだろう)
https://gyazo.com/62800ce2aeeba85a86e9d3b327dca5fa
Range Proofさわり
Pedersen Commitmentの嬉しみ
$ C = cm(r, a) = rG + aH
署名を要求することで、aの値を検証することができる
例えば
Alice -> BobにCを送る
BobはC - Hに(正しい)署名をするようにAliceに求める
$ C^{'} = C - H = rG + (a-1)H
a =1ならば Hの項が消えるのでrを知っているAliceは署名を行える
a != 1の場合は Hの項が消えないので $ rG + (a-1)H への署名の検証が通らない(署名できない)
$ C - kHをつきかえして署名させると $ kに対して同様の仕組みで署名をさせることでaを検証できる $ \{ C, C^{'} \} にリング署名をすることを考える
a = 1のとき $ C^{'}に署名ができる (rで署名できる)
a = 0のとき $ Cに署名ができる (rで署名できる)
a がどちらかであることの証明になる
$ C_i = C - 2^{i-1}H として
同様に
$ \{ C, C_{2} \} にリング署名をすることを考える
a = 2のとき、$ C_{2} に署名できる
a = 0のとき$ Cに署名できる
0 < a < 32を示したい場合は、下記を用いたリング署名を提供すれば良い
$ C_1 = C - H
$ C_2 = C - 2H
$ C_4 = C - 4H
$ C_8 = C - 8H
$ C_{16} = C - 16H
(足りないコミットメントは組み合わせて作れるが、署名はどうなんだろう? -> 考えられてない)
mosa_siru.icon < 3もってて C1 + C2 に署名できたとしても、{C1, C2, C4, C8, C16}に署名できるかよくわからない。。
Grinで使っている署名集約の仕組みのおさらい
Schnorr署名と署名集約
署名者の秘密鍵 $ s \in \mathbb{Z}_q 公開鍵 $ v = g^{-s}
署名:
1.$ r \in \mathbb{Z}_qをランダムに選び $ x= g^{r}を計算する
2. $ c = H(m,x) を求めす
3. $ y = r + sc (\mod q)を計算する
署名文 $ \sigma = (c, y)
検証:
message $ m
署名文 $ \sigma = (c,y)
1. $ g^{y}v^{c} = g^{y}g^{-sc} = g^{r} = xを計算する
2. $ c = H(m, x)
が成り立てば受理
$ x,x_1, x_2 .... private keys
$ X, X_1, X_2 ... public keys
$ X = xG
m ... 署名対象のメッセージ
$ r をランダムに選んだ乱数として
メッセージへの署名
$ (R, s) = (rG, H(X, R, m)x)
検証
$ sG = R + H(X, R, m)X
集約
$ X = \sum X_{i}
とする
各署名者は$ r_i(ナンス)をランダムに選んで $ R_i = r_iG を作る
$ R = \sum R_i
とする
各署名者はメッセージmに対して $ \sigma_i = H(X,R,m)x_iを生成する(署名
$ \sigma = \sum \sigma_iとして
$ (R, \sigma)が署名
検証は
$ sG = R + H(X,R,m)X
らしい(Hがhomomorphicじゃない場合ってこれ検証できるのか?)
これが元論文
もう少ししっかり数式を追うぞ。
https://gyazo.com/ea433d57076a0ea96f35b90cd8ba1975g
https://gyazo.com/b9bc33dded90186ea9108cb6e9005212
https://gyazo.com/a342f49fdcfea54852bec085bdb6d21b
https://gyazo.com/04552a7388338da668b9221f9dbb8a00
Goで書かれたクライアントコード