slides2
ブロックチェーンの数理と実装



DaiLambda, Inc.
Jun FURUSE/古瀨 淳
応用数理I,社会数理概論I, Nagoya university, 2023-04-21

Errata

ブロック生成の追加条件

ブロックにはサイズ上限がある。
(Bitcoin では上限 1MB、 \(O\) の平均サイズは 500~600B。)

バリデータは手数料収入 \(\sum_i f_{O_i}\) が最大になるよう \([ O_i ]\) を選ぶ

  • 手数料が低い \(O\) は無視されがち

Segwit 拡張が入ってブロックサイズが現在最大 4MB。

また、これを Bin packing問題 と言ってしまったと思いますが、正しくは 0-1 Knapsack 問題 です。

ブロックチェーンの数学とデータ構造

  • 計算量
  • ハッシュ
  • ハッシュを使ったデータ構造
  • 暗号、電子署名

計算量

入力サイズ \(n\) に対して計算量がどれくらい増加するか

  • 時間計算量: 計算時間
  • 空間計算量: メモリ使用量

\(O\)記法

関数 \(f(n)\) が \(n\) が十分大きい時 \(g(n)\) に比例もしくはそれ以下に抑えられる時、

\[f(n) = O(g(n))\]

と書く。

計算量表示によく使われる。

代表的な時間計算量

固定長四則演算: \(O(1)\)

二分探索: \(O(\mathrm{log}~n)\)

線形探索: \(O(n)\)

ソート: \(O(n~\mathrm{log}~n)\)

O-1 Knapsack問題: \(O(2^n)\)

ハッシュ

ハッシュ: データの指紋

ハッシュ関数 \(H\)

任意の長さのデータから固定長 (ex. 256bits) のデータを得る:

\[H : \bigcup_{n\in\mathbb{N}} 2^n → 2^{256}\]

データの区別
鳩の巣原理から単射ではありえないが、
「ほとんどの場合」、 \(x \neq y\) ならば \(H(x) \neq H(y)\)
偽造しにくい
ある \(h\) に対して \(H(x) = h\) になる \(x\) を探すのが難しい

ハッシュ関数として望まれる性質

一様性

偏りがあってはいけない。 \(\chi^2\) 検定で検査

高速

\(H(x)\) の計算は高速: \(x\) が \(b\) bit として \(O(b)\)

逆算は困難

衝突攻撃への耐性
ある \(h\) に対し \(H(x) = h\) となる \(x\) を見つけにくい: 平均\(2^n/2\)回
誕生日攻撃への耐性
\(H(x) = H(y)\) となる \(x \neq y\) を見つけにくい: 平均\(2^{n/2}\)回

ハッシュ関数実装

自作せず、性質がよく確かめられているもの(by NSA)を使う:

MD5
128bit、もはや安全ではない
SHA-1
160bit、もはや安全ではない
SHA-2 (SHA256, SHA512)
今の所、安全とされている。SHA-1 と同じようなアルゴリズム
SHA-3 (Keccak)
SHA-1,2 とは違うアルゴリズム。 SHA-2 が破られた時に。
BLAKE3
SHA-3 より高速

利用法: データ同一性確認

チェックサムとして。

データが偽造/されていない、壊れていないことを確認できる。

(ただし、どんなハッシュもわずかながら衝突する可能性がある)

例: OpenOffice

利用法: ハッシュテーブル

ハッシュテーブル \((H,n,B)\): 連想配列の実装に使う

  • ハッシュ関数 \(H\)
  • バケット配列 \(B\) とそのサイズ \(n\)。\(n\) は比較的小さい。

キー \(k\) に対してバケット \(B[H(k) ~\mathrm{mod}~ n]\) を使う。

  • \(使用データ数 << n\) ならば衝突はほぼない: \(O(1)\) アクセス可能。

衝突前提: \(H(k) ~\mathrm{mod}~ n\) が衝突しても良い

  • 配列各要素には複数の \((キー,値)\) の組を置けるようにする。
  • データ数が多くなると衝突しがち。性能は落ちる。
    対処例: 時々 \(n\) を大きくして \(B\) を作り直し衝突を減らす。

利用法: Proof of Work

逆算の難しさを利用

\(H_b(x)\) : \(H(x)\) の上 \(b\) bits のみ取る関数

\(H_b(S_{n} ~||~ [O_i] ~||~ \mathrm{nonce}) = 0\) となる \(\mathrm{nonce}\) を見つける

(\(||\) : 文字列の連結)

ハッシュ関数の一様性と逆算の難しさから \(O(2^b)\) の時間と
エネルギーが必要。 (\(b\) による難易度調整)

Proof of Work 成功の確率

\(P_b(n)\): \(n\) 回試行した際に \(H_b(x) = 0\) になる \(x\) が見つかる確率

\(Q_b(n)\): \(n\)回やっても見つからない確率: \[P_b(n) = 1 - Q_b(n)\]

\(H_b(x)\) の一様性を仮定すると、

\[Q_b(n) = ((2^b-1)/2^b)^n\]

単位時間確率 \(\lambda t = 1/2^b\) のポアソン過程ともみなせる:

\[Q_b(n) = e^{-\lambda t} (\lambda t)^n\]

Proof of Work 成功の確率

\(P_b(n)\): \(n\) 回試行した際に解を見つけられる確率

\[P_8(1,183) \approx 0.99\]

\[P_{10}(4,735) \approx 0.99\]

\[P_{16}(303,103) \approx 0.99\]

\[P_{24}(77,594,623) \approx 0.99\]

\[P_{32}(19,864,223,743) \approx 0.99\]

課題: Proof of Work

自分の学籍番号 NUS:xxxxxxxxx に対し Bitcoin の proof of work パズルを行い、できるだけ長い先頭 0 ビット数を持つ nonce を探してください。

詳しくは

https://dailambda.jp/nus-blockchain-2023/pow/

PoW 以外のブロックチェーンでのハッシュ利用

データ同一性判定にも幅広く使われている:

  • 状態 \(S\)、ブロック \(B\)、送金命令 \(O\) などはハッシュで判別する
    (全体を比べるにはデータサイズ大きすぎる)
    例: BLdiTUZcSRX7YC1sQ4J1M8FRdRNF5bSWRuc4wi5HRA8eDLhs73Y
  • これらのハッシュは決して衝突しないと仮定!!

木状データ構造とハッシュ

Patricia 木

基数木(Radix tree) とか Patricia trie とも。
これはハッシュ使っていない

文字列による連想配列に使う: ファイルシステムなど

  • 各辺は非空文字列を持つ
  • 同じノードから伸びる辺は接頭字を共有しない (ex. om と ote はダメ)
  • 検索、挿入、削除は \(O(l)\) (\(l\) はキーの長さ)

“Practical Algorithm to Retrieve Information Coded In Alphanumeric”

Hash trie

Hash tree とも。Patricia 木だが、キー \(k\) ではなく、\(H(k)\) をラベルに使う

  • どんなキー値も \(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 木