- どんなキー値も \(H_b(k)\) は \(b\) bit の文字列になる。
- \(b\)
を固定すれば、キー値の大きさに関係ない操作コスト \(O(1)\)
- \(H_b\) がまともならば (ex.
SHA-256) 衝突は気にしない、ことにしてよい
- \(k\)
は記録されないので、キーの列挙はできない
ブロックチェーン状態 \(S\)
のハッシュ
\(S\)
は巨大な連想配列=ファイルシステム(> 1GB)になっている。
\(S_n = B_n(S_{n-1})\)
を作った時、\(S_n\)
のハッシュをどう計算する？
たとえば、全てのキー \(k\) と値
\(v\) を連結してハッシュを計算:
\[H({\Large(||)}_{(k,v)\in S_n} k ~||~
v)~~~~~~\small ||~は文字列連結\]
これは全ファイルを舐める必要があり、遅すぎる。
\(S\)のデータサイズに比例。
何か良い方法は？ → Merkle 木
Merkle 木
木の各ノードにハッシュを置く
ノードのハッシュはその子ノードのハッシュを連結したもののハッシュ:
- \(H(n) = H( H(n_1) ~||~ H(n_2)
)\)
- \(H(n_1) = H ( H(n_{11}) ~||~ H(n_{12})
)\)
- \(H(n_2) = H ( H(n_{21}) ~||~ H(n_{22})
)\)
- \(H(n_{11}) = H(v_{11})\)
- …
(これも
Hash木
と呼ばれるので困ったものです)
Merkle 木のハッシュ計算
Merkle
木に変更が加えられた場合、新しい木のハッシュ計算は変更部分だけ行えば良い。
\(v_{12}\) だけが \(v'_{12}\)
に変更された場合、変更されたノードとその親のハッシュ計算だけ行う:
- \(\color{green} H(n'_{12}) =
H(v'_{12})\)
- \(\color{green} H(n'_{1}) =
H({\color{black} H(n_{11}})~||~H(n'_{12}))\)
- \(\color{green} H(n') =
H(H(n'_{1})~||~{\color{black} H(n_{2}}))\)
ハッシュ再計算数は一変更あたり \(O(\mathrm{log}~m)\) (\(m\)は総ノード数)。
ブロックチェーン状態 \(S\)
のハッシュ
各ブロック \(B\)
はブロックチェーン状態 \(S\)
のほんの一部しか変更しない (< 10,000)。
\(S\) を Merkle tree
を使って実装すると \(S_n = B(S_{n-1})\)
の計算時に 高速に \(S_n\)
のハッシュを計算できる。
Merkle Patricia 木
ブロックチェーン状態 \(S\)
はファイルシステムなので、 正確には Merkle
木ではなく、各辺にラベルのついた Merkle Patricia 木を使う。
(実際のファイルシステムはフォルダ構造がありより複雑)
ブロックチェーン用台帳ファイルシステム
Merkle Patricia
木を使って、堅牢高速なファイルシステムをどう構築するか:
- ディスク上のデータ表現の最適化
- Single Writer Multiple Reader の実現
- 古い履歴の削除
いろいろあるが、割愛します。
Merkle proof
ユーザーはノードにファイル内容(残高など)を問い合わせる。
ここでのノードはブロックチェーンのノード。木のノードではない
「状態 \(S\) でのあるファイルの内容
\(v_{12}\) を教えて
ノードはデータをユーザーに返すが、悪意あるノードはいくらでも嘘をつける。帰ってきたのは本当に正しい値なのか?
簡単な解決案:
- 複数のノードに同じ質問をして回る
- 違う返答があった場合、数の多いものが正直な答えだろう。おそらく…
もうちょっとカッコいい方法は?: Merkle proof
Merkle proof
存在を証明したい値と、そこからルートノードのハッシュを計算できる最低限の情報を持つ
Merkle 木の部分木。
\(v_{12}\) の Merkle proof は:
- \(v_{12}\) と \(H(n_{11})\), \(H(n_2)\)
ここから、ルート Merkle ハッシュ \(H(n)\) を計算できる：
- \(H(n_{12}) = H({\color{blue}
v_{12}})\)
- \(H(n_{1}) =
H({\color{blue}H(n_{11})}~||~H(n_{12}))\)
- \(H(n) =
H(H(n_{1})~||~{\color{blue}H(n_{2})})\)
Merkle proof のサイズは \(O(\mathrm{log}~m)\)
\(m\) は総ノード数 (\(\approx ファイル数\))
Merkle proof
ユーザーは状態 \(S\)
のルートノードハッシュ \(H(S)\)
を知っているとする。
ノードから Merkle proof を取得してルートハッシュを計算し、 \(H(S)\)と比べることで返答の正しさを確認できる。
- \(H(n_{12}) =
H({\color{blue}v_{12}})\)
- \(H(n_{1}) =
H({\color{blue}H(n_{11})}~||~H(n_{12}))\)
- \(H(n) =
H(H(n_{1})~||~{\color{blue}H(n_{2})})\)
- \({\color{blue}H(S)} \stackrel{???}=
H(n)\)
ルート Merkle ハッシュ \(H(S)\)
ユーザーはどうやって \(H(S)\)
を手に入れますか?
- ノードから。
- ノードは嘘をつけるが…\(H(S)\)
はブロックチェーンの合意形成の鍵。嘘をつくノードはあまり考えられない。
- \(H(S)\)
は高速に取得できるようになっているので、複数のノードから聞いてまわればよい
- ノード以外にも \(H(S)\)
のリストを公開しているブロックチェーンエクスプローラサービスがある
ここでもハッシュは衝突しない…
Merkle 木でもハッシュは衝突しないことになっている:
- 状態 \(S\) はその Merkle
ハッシュで識別
- Merkle proof もハッシュ衝突しないことを仮定
ハッシュ衝突を作り出せると:
- \(S\)
と同じハッシュを持つ自分に有利な \(S'\) を偽造できる。
- 偽の Merkle proof を作って相手に信じ込ませることができる。
ハッシュ衝突の心配するのを止める
実際、 SHA-256 衝突の例は知られていない
ありうるハッシュ値の数は:
\[2^{256} \approx 10^{77} \approx
N_{\mathrm{Edd}} / 1000\]
\(N_{\mathrm{Edd}}\) :
エディントン数。観測可能宇宙での陽子の数
(とはいえ今この瞬間に衝突が起こるかもしれない…)
もしブロックチェーンでハッシュ衝突が起こったら
現状起こる気はしないが…
アルゴリズムの脆弱性が見つかり、衝突耐性が下がる可能性はある。(既知の例:
MD5, SHA-1)
もし攻撃手法が見つかったら
安全なハッシュ関数に差し替えて対処する。
ハードフォーク、ガバナンス問題
中央管理者のいないブロックチェーンでどう発見された脆弱性を修正するか。(後日)
暗号
共通鍵暗号
秘密をやりとりする双方が同じ鍵を持つ
公開鍵暗号
秘密鍵 \(s\)、公開鍵 \(p\) :
- 公開鍵 \(p\) は公表する
- 公開鍵 \(p\) から秘密鍵 \(s\) は求められない
- 平文 \(m\) を送りたい相手の公開鍵
\(p\) を使って暗号化
- 暗号文は秘密鍵 \(s\) でしか平文
\(m\) に復号できない
公開鍵電子署名
ブロックチェーンでは暗号よりもむしろ電子署名が使われる。
公開鍵暗号を使用。
- メッセージ(のハッシュ) \(h\)
に秘密鍵 \(s\) で署名 \(\sigma\) を作成
- 公開鍵 \(p\), メッセージと署名
\((h, \sigma)\) を作る
- \((p, h, \sigma)\) から、\(s\) を知っている人しか \(\sigma\) を作成できないことを確認
電子署名方式
楕円曲線暗号がよく使われる。ハッシュのようにいくつか種類がある:
- Secp256k1: Bitcoin, Ethereum, Tezos
tz2
- Ed25519: Tezos
tz1
- P256: Tezos
tz3
- BLS12-381
楕円曲線暗号
\(E : y^2 = x^3 + ax + b\)
楕円でもなんでもない…
楕円曲線から暗号システムを作る
\(E\) : 曲線上の点
\(O\) : 無限遠点
\(E \cup \{O\}\) は加群をなす:
- 単位元 : \(O\)
- 逆元: \(-P\): \(P\) の \(x\) 軸対象にある点
- \((+)\) : \(P + Q = R\)
ただし \(-R\) : 直線 \(PQ\) と \(E\) のもう一つの交点
巡回群 \(G\)
先ほどの\(E \cup \{O\}\)
の加群から適当な \(P \neq O\)
を選び、
素数位数の巡回群 \(G\)
を構成する:
\[G := \langle P \rangle := \{ O, P, 2P,
3P, .., (p-1)P \} ~~~ p は大きい素数\]
四則演算をサポート
\(G = Z/pZ\)
なので、除算を導入でき、有限体 \(F_p\)
になる。
楕円曲線関数の離散対数問題
素数 \(p\) が \(2^{2048}\) くらいに大きい \[G = \langle P \rangle = \{ O, P, 2P, .., (p-1)P
\}\] に対し、
- ある \(a\) に対し、 \(aP \in G\) を \(a\) と \(P\) から計算するのは簡単
- \(P, aP \in G\) から \(a\) を逆算するのはほとんど不可能
この一方向性が暗号のキモ
ECIES (楕円曲線暗号)
- A の秘密鍵: \(s \in Z_{\#G}\)
- A の公開鍵: \(p = sP \in G\)
B は 平文 \(m\) を暗号化して A
に送りたい
- 乱数 \(r\) を選ぶ
- \(k = rp\) を計算 (\(= rsP\))
- \(c = \mathrm{Enc}(k,m)\), 共通鍵
\(k\) による暗号化
- \((rP, c)\) を B に渡す
A は暗号分 \((rP,c)\)
を復号したい
- \(s\) を知っているので \(rP\) と \(s\) から \(k =
rsP\) を計算できる。
- \(m = \mathrm{Dec}(k,c)\), 共通鍵
\(k\) による復号化
ECDSA (楕円曲線デジタル署名)
- 秘密鍵: \(s \in Z_{\#G}\)
- 公開鍵: \(p = sP \in G\)
- メッセージのハッシュ: \(h \in
Z_{\#G}\)
- ランダムな整数 \(k \in
Z_{\#G}\)
- \(r = kP ~の~ x 座標\)
- 署名: \(\sigma = (r,
(h+rs)/k)\)
署名 \(\sigma =
(r,t)\) の確認
\((hP+rp)/t = (hP+rsP)/t = (h+rs)/t P =
kP\)
になるので、結果の \(x\) 要素と
\(r\) が同じなら、 \(s\) と \(k\) を知っている人しか \(\sigma\) を作れないことがわかる。
Playstation 3™️
ECDSA署名: \(\sigma = (r,
(h+rs)/k)\)
Sony の秘密鍵 \(s\)
による署名がないゲームは動かない、
はずだった
Jailbreak
\(k\) を固定してしまった…
- \(r = kP ~の ~x~座標\) も固定
- 二つの署名 \(\sigma_1 = (r,
(h_1+rs)/k)\) と \(\sigma_2 = (r,
(h_2+rs)/k)\) から
- \((h_1 - h_2)k\) が計算できる
- \(h_1\) と \(h_2\) は既知なので \(k\) が求まる
- \(k\) がわかれば \((h_i+rs)/k\) から \(s\) も求まる
自作ゲームに \(s\)
で署名をして動かすことができる
XXX
https://community.trustwallet.com/t/browser-extension-wasm-vulnerability-postmortem/750787
ECDSA の実装
- Secp256k1: Bitcoin, Ethereum, Tezos
tz2
- Ed25519: Tezos
tz1
- P256: Tezos
tz3
ブロックチェーンでの電子署名の利用
- 秘密鍵 \(s\)
を作成し、死守する
- 公開鍵 \(p\)
はブロックチェーンへ登録 \(p \approx
アカウント名\)
- 送金命令 \(O\) へのECDSA署名を
\(s\)
で行い、アカウントへの操作の権利を持っている(= \(s\) を知っている)ことを証明する
秘密鍵 \(s\) が漏洩すれば、攻撃者は
\(O\) を偽造できる
=
そのアカウントはおしまい。
BLS12-381
楕円曲線暗号の実装
楕円曲線: \(y^2 = x^3 + 4\)
- \(p\) : 381 bit の素数 (BLS12-381
の 381)
- \(G_1 = F_p\)
- \(G_2 = F_{p^2}\)
- \(G_T = F_{p^{12}}\) (BLS12-381 の
12)
安全で効率的なペアリング関数で知られる。
ペアリング関数
巡回群 \(G_1 = \langle P \rangle\),
\(G_2 = \langle Q \rangle\), \(G_T\)
双線形性を持つペアリング関数
\(e(\_, \_)\)
\(e : G_1 * G_2 \rightarrow
G_T\)
\(e(x, y+w) = e(x,y) * e(x,w)\)
\(e(x+z, y) = e(x,z) * e(z,y)\)
これらから、
\(e(aP,bQ) = e(P,Q)^{ab} = e(P,abQ) =
e(bP,aQ) = ~..\)
係数 \(a\), \(b\) を移動できる。
(相変わらず \(aP\) から \(a\) を知ることはできないが)
ペアリング関数を使った BLS 公開鍵署名
- 秘密鍵: \(s \in Z_{\#G_2}\)
- 公開鍵: \(p = sQ \in G_2\)
- メッセージのハッシュ: \(h \in
Z_{\#G_1}\)
- 署名: \(\sigma = shP \in G_1\)
とすると、
\[e(\sigma, Q) = e(shP, Q) = e(hP, sQ) =
e(hP,p)\]
\(s\) が何か知らない者でも、\(e(hP,p)\) と \(e(\sigma, Q)\) が等しい ことを計算すれば
\(\sigma\) を作ったものが \(p = sQ\) となる \(s\) を知っていると確認できる。
ペアリングチェック関数
先ほどの \[e(\sigma, Q) = e(hP,p)\]
は、
\[e(hP,p) * e(-hP,p) = 1\]
と変形できるので、\(\{(x_i, y_i)\}_i \in
G_1 * G_2\) の集合をもらい、
\[PC(\{(x_i,y_i)\}) = e(x_1,y_1) ~*~ ..
~*~ e(x_n,y_n) \stackrel{?}= 1\] を計算する関数が提供されている。
\(G_T\)
のことを考えなくて済む。
BLS12-381 とゼロ知識証明
ゼロ知識証明
ある知識を知っていることを、
その知識そのものを公開せずに証明する。
例: 公開鍵署名
「自分はメッセージ \(m\)
に対してこの署名 \(\sigma\) を
作成できる秘密鍵 \(s\)
を知っている」
例: 平方根
「自分はある数 \(n\) の平方根 \(\sqrt n\) を知っている」
匿名コイン
Zcash の Sapling
アルゴリズムで使われている。
送金量や送金先を秘匿しつつ、送金が正当だと証明する。
