HFリサーチ”BIP-MMHF” - Develop with pleasure!

ブロックサイズの拡張（1M→2M）を目的としたハードフォークに注目が集まっているけど、ブロックサイズとは別に↓のような問題を解消するためにブロックヘッダの構造についてもそろそろ変更が必要じゃないかと思う。

extra nonceの確保
現在のハッシュレートではとても既存のnonce領域では足りず、タイムスタンプやコインベースの値がextra nonceとして使われている。
segwitのコミットメント領域の確保
BIP-141のsegwitはソフトフォークとして提案されており、segwitの署名を含むトランザクションのコミットメントはコインベーストランザクションの出力の１つにOP_RETUNRを使って追加する仕様になっている。もともとOP_RETUNRの導入やサイズ拡張については賛否あったのを考えると、それをコアとなる機能の一部として採用するのは皮肉な結果にも思える。本来は従来のマークルルートと同様、ブロックヘッダに専用の領域として定義すべきものだと思う。

ただ、このようなブロックヘッダの構造に変更を加える場合は当然ながらハードフォークが発生する。
ハードフォークが行われるとチェーンの分岐が考えられ、チェーンの分岐を技術的に防ぐことは現状不可能で、社会的なコンセンサスの形成が必要になる。

というのを考慮するとハードフォークは気軽に行えないので、個人的にはサイズ拡張だけでなく↑のようなブロックヘッダの拡張も合わせて計画し、実施した方が現実的なんじゃないかと思う。（まぁ何を加える加えないで政治的対立がまた発生しそうな気もする）

ではどういう拡張が考えられるのか、ハードフォークに関するリサーチが↓のサイトにまとめられている。

今回は１つめの、ブロックサイズとnonceのスペースを拡張し、Native merge-miningをサポートするLuke-jrによる提案（2016年2月に提案されたけどまだBIPにはなってない）↓について見てみる。（残念ながらマージマイニングのサポート方法についてはまだ詳しく記載されていない）

https://github.com/luke-jr/bips/blob/bip-mmhf/bip-mmhf.mediawiki

動機

Bitcoinのマイニングは、有効なブロックを見つけるためにデータを変更してハッシュ値を計算する必要がある。32bitのnonceはブロックヘッダに直接設定する。このnonceのスペースを使い尽くしても目的のハッシュが見つからないと、マイナーはトランザクションデータを変更しなければならない。その場合、コインベーストランザクションのscriptSigを変更することで、マークルルートの値が別の値に変わり、新しいマークルルートで再びnonceを変えながらハッシュ計算を続ける。しかしこのプロセスは複雑だしハードウェアにアウトソースするのに適していないが、現在のハッシュレートではそうせざるを得ない。この問題についてはハードウェアにアウトソースできるようnonceのスペースを拡張することで解決できる。

※他のブロックサイズの制限や、マージマイニングについての動機はまだ書かれていない

仕様

ブロックヘッダのフィールド

各ブロックは↓のヘッダフィールドで構成されるようになる。

最大600bitのnonceフィールド
- PoW計算の最終段階で直前に変更可能な32bitのclass 1 nonce。
- 24bitのclass 2 nonce
- 32bit〜544bitの可変長のclass 3 nonce
前のブロックのハッシュ
32bitのタイムスタンプ
ブロック高
8bitのmerge-mining-hardforkのデプロイのビットフィールド
16bitのハードフォークのデプロイのビットフィールド
32bitのソフトフォークのデプロイに使用するビットフィールド（現在のBIP-9のようなもの）

これに加えてブロックにはトランザクションのセットが含まれる。

トランザクションは前のブロックからUTXO stateを更新する必要がある。UTXO stateに存在しないデータを使用しようとするトランザクションは無効となる。

有効なUTXOを使用する入力のwitnessは、その入力が参照するpubkey scriptに対して有効なものかチェックする。このチェックに失敗すると、そのブロックは無効である。

ブロック内のトランザクションの総コストはXXXを超えてはならず、またsigopsの合計がXXXを超えてはならない。（ XXXの値はまだ決まってないみたい。）

マークルツリーのアルゴリズム

マークルツリーの構成にも変更が加わる。各オブジェクトについて、マークルツリーでそのダイジェスト値を計算する。各ダイジェストはハッシュとそのノードに含まれる値の合計値で構成される。

例えば、トランザクションのマークルツリーのダイジェストは↓の３つのフィールドで構成されるようになる。

uint256 hash;  // SHA-256ハッシュ
uint64 fees;   // このノード以下のトランザクションで支払われる総手数料
uint64 size;   // このノード以下のトランザクションの合計サイズ

witnessのマークルツリーのダイジェストは↓の３つのフィールドで構成される。

uint256 hash;  // SHA-256ハッシュ
uint32 sigops; // このノード以下のトランザクションのsigopsの合計値
uint64 size;   // このノード以下のトランザクションの合計サイズ

以下の３つのbitがflagsバイトとして定義される。

FLAG_LEAF = 0x80
FLAG_PLURAL = 0x40
FLAG_MERKLE_ROOT = 0x20

残りのbitは予約されており、現在は全て0。

FLAG_LEAFはツリーの最下位レベルにのみセットする。
FLAG_PLURALは２つのハッシュを１つに圧縮する際にセットする。
FLAG_MERKLE_ROOTはマークルルートを計算するための最終的なハッシュステップにセットする。

トランザクションデータとwitnessのダイジェストは↓のように生成する。

トランザクションツリーを生成する際は、最初に↓のようにリーフダイジェストを生成する。

 uint256 hash = txid
unit64 fees = 入力のコインの合計 - 出力のコインの合計
uint64 size = witnessデータを除外してシリアライズしたトランザクションのサイズ

witnessツリーを生成する際は、最初に↓のようにリーフダイジェストを生成する。

uint256 hash = txid
uint32 sigops = トランザクションのsigop数
uint64 size = witnessデータを含むBIP-144でシリアライズしたトランザクションのサイズ

各ダイジェストのペア（左と右）から、その親ノードを↓で計算する。

flags = FLAG_PLURAL (or FLAG_PLURAL | FLAG_LEAF for the first pass)
    
compressed.hash = SHA256d(left.hash | left.fees | left.size | right.hash | right.fees | right.size | flags)
compressed.fees = left.fees + right.fees
compressed.size = left.size + right.size

ノードの数が奇数の場合、↓のようにして親ノードを計算する。（今までと同じように左ノードのデータをコピーして使うと手数料やデータサイズの計算がおかしくなるため、ゼロ値を使ってると思われる）

flags = 0 (or FLAG_LEAF for the first pass)
    
compressed.hash = SHA256d(left.hash | left.fees | left.size | 256 zeros | 64 zeros | 64 zeros | flags)
compressed.fees = left.fees
compressed.size = left.size

このダイジェストの数が１つになる（ルートノードになる）まで計算ステップを繰り返す。

最後にマークルツリーのルートを作成するためルートハッシュを計算する。（今までのようにルートノードハッシュがそのままマークルルートになる訳ではない）

flags = FLAG_MERKLE (or FLAG_MERKLE | FLAG_LEAF)
    
final_root_hash = SHA256d(root.hash | root.fees | root.size | element_count | 192 zeros | 64 zeros | 64 zeros | flags)

element_countは、8バイトの数値で、このツリーのリーフノード（トランザクション）の数

witnessツリーの場合は、合計部分は含まれずflagsは同じで計算はシンプル。手数料の部分をsigop数に置き換えれば良い。

動的メンバーシップマルチパーティ署名（DDMS）アルゴリズム

ハッシュTMR（トランザクションマークルルート）は、ブロックに含まれる全トランザクションのidを使ったマークルツリーアルゴリズムを実行することで生成される。

ハッシュWMR（Witnessマークルルート）は、ブロックに含まれる全トランザクションの（witnessデータを含む）完全なハッシュを使用したマークルツリーアルゴリズムを実行することで生成される。

ハッシュH-C（Header-C）は、↓のデータをSHA256して生成される（エンディアンについては未FIX）。

8バイト：トランザクションデータの標準サイズ
8バイト：トランザクションのコストの合計
8バイト：トランザクションのsigop数の合計
4バイト：トランザクション数
2バイト：ハードフォークデプロイ用のビットフィールド
4バイト：ソフトフォークデプロイ用のビットフィールド
32バイト：ハッシュTMR
32バイト：ハッシュWMR

ハッシュCMR（コミットメントマークルルート）は、最大2³²個の要素を持つハッシュH-Cのマークルツリーアルゴリズムを実行することで生成されるが、ハッシュH-Cにつながる部分木としてのみ検査される。ノードはマークルツリーの他のブランチに関して何も気にせず、H-Cの位置は以下のように計算する。

uint32_t lrot(uint32_t x, uint32_t n) {
  return (x << n) | (x >> (32 - n));
}

// nonceはclass 3 nonceの先頭4バイトでビッグエンディアンとして解釈される。
uint32_t vector_position_for_hc(uint32_t nonce, uint32_t vector_size) {
  const uint32_t chain_id = 0x62697463;  // "bitc"
  uint32_t a, b, c;
  a = (0xb14c0121 ^ chain_id) - lrot(chain_id, 14);
  b = (nonce ^ a) - lrot(a, 11);
  c = (chain_id ^ b) - lrot(b, 25);
  a = (a ^ c) - lrot(c, 16);
  b = (b ^ a) - lrot(a, 4);
  c = (c ^ b) - lrot(b, 14);
  a = (a ^ c) - lrot(c, 24);
  return a % vector_size;
}

ハッシュH-B（Header-B）は、↓のデータをSHA256して生成される。

41バイトの定数：

77 77 77 77  01 00 00 00  00 00 00 00  00 00 00 00
00 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00
00 00 00 00  00 ff ff ff  ff

1バイト：以下の41〜103バイトのデータ長 - 3
41〜103バイト：
- シリアライズしたブロック高（BIP-34）
- 1バイト：マージマイニングハードフォークのデプロイ用のビットフィールド
- ハッシュCMR
- class 3 nonce
1バイト：前のデータ長（midstate圧縮用）
14バイトの定数：

01 00 00 00  00 00 00 00  00 00 00 00 00 00

ハッシュH-A（Header-A）は、↓のデータをSHA256して生成される。

3バイト：class 2 nonce
1バイト：定数0x60
32バイト：前のブロックのハッシュ
32バイト：ハッシュH-B
4バイト：タイムスタンプ
4バイト：現在のブロックのターゲット（difficulty）
4バイト：class 1 nonce

ハッシュH-Aはリトルエンディアンの数値として解釈され、現在のブロックターゲットと比較される。ハッシュ値がターゲット以下であればDDMS署名は有効。

ハードフォークのデプロイ用ビットフィールド

↓のハードフォークの性質上、ハードフォークのデプロイ用ビットフィールドはBIP-9のように機能する。

ノードは、ハードフォークに関してネットワーク全体の同意が示されるまで、starttimeを延期しなければならない。
マイニングノードは、ネットワーク全体がハードフォークに合意し、ノードのサポートをを確信するまでstarttimeを延期しなければならない。
認識していないハードフォークがネットワークの最長のチェーンでアクティベートされた場合、ノードのオペレーターがハードフォークを受け入れるか、拒否するか選択するまでノードは旧ルールの最後のブロックで停止する必要がある。
拒否されたハードフォークのビットがアクティベートされると、ノードはフォークポイントより前進するため代わりのPoWアルゴリズムに切り替える必要がある。
ハードフォークはそれが認識/実装されるまでノードはそれを受け入れない。ノードがアップグレードされるまで、ノードは認識していない、不参加状態になる。
シグナリング期間中XXX%以上がハードフォークを拒否する場合、ハードフォークはアクティベートしてはならない。

論拠

nonceのサイズ制限の１つの解決策は、ブロックヘッダ内のnonceのスペースを拡張することで、現在80バイトに固定されているブロックヘッダの長さを可変にするか、未使用のセクションを追加のnonceフィールドとして再利用できるようにするかのどちらかになる。ブロックサイズを拡張するのは、単純により多くのトランザクションを許容するようにするだけで充分。

しかし、こういったハードフォークは、旧ノードを壊すだけでなく、新しいブロックの受け入れを拒否し、新しいチェーンより短くても古いルールを守るチェーンを有効なチェーンとして受け入れることができてしまう。これはこのハードフォークを実装する際に、旧ノードが有効な空ブロックとして認識するハッシュを使用することで対処することができる。

後方互換生

このハードフォークは、明示的にこのハードフォークに対応していないノードでは（フルノードも軽量ノードも）無効になる。移行するには、全ノードがアップグレードを選択する必要があり、マイナーは圧倒的大多数がサポートを表明する必要がある。

まとめ＆所感

nonceは現在32bitなので、600bitになると19倍弱増えることになる。
BIP-9のようなソフトフォークのシグナリングを今はブロックのnVersionをビット列として解釈して使用しているが、ソフトフォーク、ハードフォーク、マージマイニング用の各デプロイ用、シグナリング専用のヘッダフィールドが設けられる。
マークルツリーを構成するアイテムも変わる。従来リーフノードにTXIDをセットし、２つのノードのハッシュを連結して親ノードのハッシュを計算し、それをルートノードまで繰り返すことでツリーを構成していたけど、そのノードにハッシュだけではなく、用途に応じた値（手数料やsigop数など）がセットされるようになる。
複数のアイテムを組み合わせて↑のようなマークルツリーのアルゴリズム考えるのも面白そう。
nonceが３つのパートで構成されるよう拡張され、そのハッシュの計算方法も新たに定義されるが、結構複雑になってる感がある。
旧ノードにとって空のブロックとして認識させる仕組みの部分が詳しく知りたい。