Note: ビットコインのブロックチェーン

BCCC 2017 で行った bitcon のブロックチェーン技術に関するノート。

• SHA2 … 米国系、RIPEMD 160 … 欧州系のアルゴリズム
• BASE58 エンコーディング … BitCoin 独自。人が見て間違いやすい文字を除外している。また人が書き記した時に誤りを検出できるようにチェックを追加している。\[{\rm base58check} = {\rm base58}({\rm version} + {\rm hash}({\it data}):[4])\]
• 署名アルゴリズムに ECDSA を使用している。楕円曲線は群になる性質がある。楕円曲線は秘密鍵から公開鍵の算出が容易。公開鍵は秘密鍵を \(G\) 回加算したもの。ビットコインは SECP256K1 のパラメータを使用している。
• ハッシュ関数や署名アルゴリズムの変更は hard fork によって行われる (全てのユーザに対して何月何日に変更せよという通知による)。
• HMAC … salt を使ったハッシュ化。\[{\rm hash}({\rm hash}({\it data}) || {\rm hash}({\it salt}))\]
• ビットコイン … 仕様に Little Endian, Big Endian 混在、マイナス値の補数が混在していてかなり厳しい。丸めや切り捨てはプロトコルで定義されておらず実装依存。
• 可変長整数 varint 型、0-252:実データ、253:次に 2B 続く、254:次に4B続く、255:次に8B続く。
• スクリプトはスタックマシン型のバイトコード。実装依存部分も結構あるようだが実行環境によって結果が変わらないか?
• マークルツリー。\[ \begin{align*} h(A), h(B), h(C), h(D) \\ \to & h(h(A), h(B)), h(h(C), h(D)) \\ \to & h(h(h(A), h(B)), h(h(C), h(D))) \end{align*} \] ツリー全体をダウンロードしなくても \(A\), \(h(B)\), \(h(h(C), h(D))\) だけあれば全体を検証できる (A がツリー内に存在することが保証できる)。
• Malleability … ECDSA で \(S\) の符号を反転しても署名は同じになる。\(S\) を反転させるとトランザクション ID が変わるから Mt.GOX は送信に失敗したかと勘違いして送金を繰り返しビットコインが奪われた。
• Script … ビットコインのスクリプト言語。最終結果が false であればトランザクションは無効とみなされる。助産命令 OP_DIV, OP_2DIV は存在するが無効化されている。
• OP_RETURN で検証処理は終了だが、その後に任意のデータを付加できる。拡張はそこを使って行っている。
• 非スタンダードなトランザクションは公式クライアントが中継しない。したがってブロックには取り込まれない (マイナーが取り込まなければ)。
• Q:スクリプトの改ざん対策は? A:トランザクションの一部なので署名されている。
• Q:スタックサイズの保証は? A:概ねトランザクションサイズと同じくらいか? ループがない(?)ので多くは必要ない。
• Q:演算がオーバーフローした時の挙動は? A:リファレンス実装の動きが仕様。
• Q:スクリプトを実行する物理マシンはマイナーのマシン? A:YES
• Q:スクリプトが失敗したときのトランザクション送信者へのフィードバックは? A:あるAPIライブラリを使っていればエラーが返る。
• Q:スクリプト実行の保証は? A:中継や全ノードのダウンロード時に全て検証される。
• Q:チューリング完全ではない? A:forのようなループがないので「処理」を記述するものではないが、コントラクトは記述できるので十分。
• BIP … RFC のようなものがある。
• MultiSig … 例えば 3 つの公開鍵のうち 2 の署名があれば送金できる。
• P2SH … Pay to Script Hash。複雑な送金を行うとスクリプトが長くなるため、入力データの中にスクリプトを埋め込む必要がある。通常のアドレスと区別するために P2SH は 0x05 で始まる。
• Redeem Script … 入力に埋め込まれたスクリプト。
• HD鍵 … 決定論的鍵生成方法。取引ごとにアドレスを変えたほうがプライバシーが高い。マスタードシード (乱数) に数値を付加してハッシュ化したものを秘密鍵を生成すればできる。例えば同じアカウントに対するデバイスごとの鍵とか。
• BIP32 では公開鍵と計算用の鍵 (Chain Code) を共有すれば新しい公開鍵を計算できる。無限に計算できるのでそのうち衝突しない? ➝ 128bit 幅のエントロピーを持つので衝突は難しいでしょう。32bit個生成しても 1/32bit の確率。
• ニーモニック … 人が書き写すことを考慮して単語にマッピングしたもの。
• HDウォレット … 複数の通貨で同じアドレスを使用できる。アドレスを計算し入出金履歴がないところまで到達したら終了。
• ビットコインでは MultiSig が使える。BIP45 には HD鍵を MultiSig の両方で使う時
• URL を支払いに使えるように拡張しよう = BIP72
• lock time はブロックに取り込まれないのでトランザクションが浮く状態 (中継されない)。check lock verify は取り出しのトランザクション側で送金できているけどまだ無効な状態。これは、商品の受け取りが完了してから出品者への支払いが行われるエスクローのような手続きを意図している。例えば、購入者が1週間の lock time で支払いトランザクションを発行する。商品を受け取ったら受け取り完了のトランザクションを発行する。支払いトランザクションが発動した時点で受け取り完了していれば送金されるし、されていなければ送金が失敗して元の口座に戻る。
• BIP65 … check lock verify。トランザクションに有効期限を設定。一定期限が過ぎたかをスクリプトが検証可能。
• bloom filter … 処理の前段で「確実に含まれていない」ことを保証する要素を除外するフィルタ。SPVノード (特定のアドレスのみのブロックを収集するノード) が他のノードからブロックを収集する時に使う。
• 通信切断時の再送方針は at least once。
• 1ブロック1MBまで。転送量を小さくしたい。サイズを大きくすると取引量が増える。上限を増やすのであれば hard fork が必要。
• 現状 (2016年11月) 秒 7 トランザクション程度しか処理できない。
• Proof of Work: Bitcoin はこのマイニング方式。ハッシュ値計算のためのマシンパワーが承認割合を決める方法。Proof of Stake: コインを持っている割合 (Stake) でブロックの承認割合を決める方法。マイニング不要 (電力消費なし)。攻撃を行うためには多くのコインを持たなければならず、自身の攻撃によってコインの価値が下がれば保有資産価値も下がるため攻撃のモチベーションが低くなる。