Bitcoin の Block Header を理解してマイニング結果を検証する

こんにちは、taxio です。

暗号通貨が世間を賑わせるようになってから数年が経ちました。 色々怪しかったり怪しくなかったりする話をたくさん聞きますが、そもそもシステムとして動いているという事実は確かです。 ということで、最近はその技術的バックグラウンドを知るべく、Satoshi Nakamoto の論文 や解説ブログ、BitcoinWiki を読んで、実際に自分で実装してみながら勉強しています。

今回はその中でもとっつきやすい Block Header に注目し、実際に自分で検証のコード (Go) を書きながら理解を深めてみます。

この記事では暗号通貨の用語が出てきますが、全て Bitcoin を前提にしています1

Transaction と Block

ブロックチェーン上での資産の取引は Transaction というデータで表現されます。 Block は複数の Transaction を持ち、平均して10分に1個が承認を経てブロックチェーンに追加されます。

Transaction が生まれたらすぐにブロックチェーンに追加される訳じゃないんですね。

Block に紐づく Transaction たちは Merkle Tree というハッシュ木2で情報が集約され、最終的にその Root Hash が Block に直接保存されます。

ざっくりとしたデータ構造を知りたい場合は、BigQuery にあるデータセット実際の Block の情報を直接見ると雰囲気が掴めると思います。

Block Header

Block は色々な情報を持っているのですが、特に以下の情報が 80 Byte にシリアライズされその Block のハッシュ化に使用されます。 この 80 Byte のことを Block Header と言います。

  • version (4 byte)
    • Block のバージョン
  • previous block header hash (32 byte)
  • merkle root hash (32 byte)
    • Block が持つ全 Transaction から Merkle Tree を作成した時の Root Hash
  • time (4 byte)
    • マイニングが始まった時間3
  • nBits (4 byte)
    • Target を算出するための情報
    • Block のハッシュ値は Target 以下になる必要がある
  • nonce (4 byte)
    • Block のハッシュ値を Target 以下にするために付ける任意の数字
    • マイニングのほとんどの時間はこの数字を求めるのに費やす

構造体にしてみるとこんな感じです。

type BlockHeader struct {
    Version        int32
    PrevHash       [32]byte
    MerkleRootHash [32]byte
    Time           uint32
    Bits           uint32
    Nonce          uint32
}

ハッシュ値を求める

さて、実際に Block Header からハッシュ値を計算してみましょう。 ハッシュ関数に渡す情報の作成は単純で、先程定義した構造体を上からバイト列にして繋げていくだけです。

func ReverseHashBytes(hash [32]byte) [32]byte {
    for i := 0; i < len(hash)/2; i++ {
        hash[i], hash[len(hash)-i-1] = hash[len(hash)-i-1], hash[i]
    }
    return hash
}

func (b *BlockHeader) Serialize() [80]byte {
    serialized := [80]byte{}

    bVersion := make([]byte, 4)
    binary.LittleEndian.PutUint32(bVersion, uint32(b.Version))
    copy(serialized[0:4], bVersion[:])

    bigEndianPrevHash := ReverseHashBytes(b.PrevHash)
    copy(serialized[4:36], bigEndianPrevHash[:])
    bigEndianMerkleRootHash := ReverseHashBytes(b.MerkleRootHash)
    copy(serialized[36:68], bigEndianMerkleRootHash[:])

    bTime := make([]byte, 4)
    binary.LittleEndian.PutUint32(bTime, b.Time)
    copy(serialized[68:72], bTime[:])

    bBits := make([]byte, 4)
    binary.LittleEndian.PutUint32(bBits, b.Bits)
    copy(serialized[72:76], bBits[:])

    bNonce := make([]byte, 4)
    binary.LittleEndian.PutUint32(bNonce, b.Nonce)
    copy(serialized[76:80], bNonce[:])

    return serialized
}

Block 内部では Byte 列は little-endian で扱われることに注意してください。

例として、以下のような Block Header を対象とします。

{
  "version": 1,
  "prev_hash": "00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81",
  "merkle_root_hash": "2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3",
  "time": 1305998791,
  "bits": 440711666,
  "nonce": 0,
}

構造体に当てはめて、実際にシリアライズしてみると以下のようになります。

header := BlockHeader{
  Version: 1,
  PrevHash: [32]byte{
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0xa3,
    0xa4, 0x1b, 0x85, 0xb8, 0xb2, 0x9a, 0xd4, 0x44,
    0xde, 0xf2, 0x99, 0xfe, 0xe2, 0x17, 0x93, 0xcd,
    0x8b, 0x9e, 0x56, 0x7e, 0xab, 0x02, 0xcd, 0x81,
  },
  MerkleRootHash: [32]byte{
    0x2b, 0x12, 0xfc, 0xf1, 0xb0, 0x92, 0x88, 0xfc,
    0xaf, 0xf7, 0x97, 0xd7, 0x1e, 0x95, 0x0e, 0x71,
    0xae, 0x42, 0xb9, 0x1e, 0x8b, 0xdb, 0x23, 0x04,
    0x75, 0x8d, 0xfc, 0xff, 0xc2, 0xb6, 0x20, 0xe3,
  },
  Time:  1305998791,
  Bits:  440711666,
  Nonce: 0,
}
fmt.Printf("Serialized:\n%x\n", header.Serialize())

// Serialized:
// 0100000081cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122bc7f5d74df2b9441a00000000

これを SHA-256 で2回ハッシュ化します。 2回ハッシュ化するのは Length Extension Attack4 というのを避けるためだそうです。

bitcoin.stackexchange.com

本来はこれで終了なのですが、後続の説明の分かりやすさのため、このハッシュ値を big-endian に直しておきます。

func (b *BlockHeader) Hash() [32]byte {
    serialized := b.Serialize()
    h1 := sha256.Sum256(serialized[:])
    h2 := sha256.Sum256(h1[:])
    return ReverseHashBytes(h2)
}

先程のデータを入れると以下のような情報が出てきます。

fmt.Printf("Hash:\n%x\n", header.Hash())

// Hash:
// da830f8941824ae65eb8cdacf37df88057c533f7e2168aceeae314b8a3d783d8

さて、これで Block のハッシュ値を求めることができましたが、実はこれで終わりではありません。

Target と Nonce

先程の例では da830f8941824ae65eb8cdacf37df88057c533f7e2168aceeae314b8a3d783d8 というハッシュ値を算出しました。 しかし先述したとおり、このハッシュ値は Target 以下にする必要があります。

そのために Nonce に色々な値を入れていくのですが、まずは目指すべき Target を Bits から算出しましょう。

Bits は先頭2byteが指数部で、残りの3byteが仮数部となっています。

例えば Bits が 0x1A44B9F2 だった場合、以下のようにして Target を算出します。

Target = 0x44B9F2 * 2 ^ (8 * (0x1A - 3))
       = 0x44b9f20000000000000000000000000000000000000000000000

これを実際にコードに落とし込んでいきましょう。 (もっとうまいこと Byte を使う方法はあると思いますが、適当に実装してしまっています...。)

func (b *BlockHeader) Target() [32]byte {
    exponent := b.Bits >> 24
    mantissa := b.Bits & 0x00FFFFFF

    targetStr := fmt.Sprintf("%x", mantissa) + strings.Repeat("0", (int(exponent)-3)*2)
    targetStr = fmt.Sprintf("%064s", targetStr)
    target, _ := hex.DecodeString(targetStr)

    ret := [32]byte{}
    copy(ret[:], target[:])

    return ret
}

しっかりと目的の Target が算出できていることがわかります。

fmt.Printf("Target:\n%x\n", header.Target())

// Target:
// 00000000000044b9f20000000000000000000000000000000000000000000000

さて、Target が求まったので、ハッシュ値と Target を比較するメソッドを定義して Nonce を探していきましょう。 Go には 256bit の unsigned integer は無いので、先頭から byte を比較していきます。

func (b *BlockHeader) IsValidHash() bool {
    hash := b.Hash()
    target := b.Target()
    for i := 0; i < len(hash); i++ {
        h := hash[i]
        t := target[i]
        if h != t {
            return h < t
        }
    }
    return true
}

ここは気合なのですが、なんやかんやで Nonce: 2504433986 を発見したとします。

header.Nonce = 2504433986
fmt.Printf("Hash:\n%x\n", header.Hash())
fmt.Printf("Target:\n%x\n", header.Target())
fmt.Printf("Valid: %v\n", header.IsValidHash())

// Hash:
// 00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d
// Target:
// 00000000000044b9f20000000000000000000000000000000000000000000000
// Valid: true

ちゃんと Target 以下のハッシュ値が算出されましたね。

実際の Block のデータを用いて検証してみる

ここまでで Block Header の情報を用いて、

ができるようになったので、実際に Bitcoin の Block を持ってきて検証してみましょう。

bitcoin explore」とかggって出てくる適当なサイトから Block 情報を引っ張ってきます。 今回は715405番目のハッシュ値 0000000000000000000b511bf20ecb6d0ea049862fa2741ed8098e508d98aa3c という Block を対象にします。

www.blockchain.com

計算するならこっちの方が扱いやすいかも。

https://blockchain.info/rawblock/0000000000000000000b511bf20ecb6d0ea049862fa2741ed8098e508d98aa3c

それぞれの情報を構造体に当てはめると以下のようになります。

header = BlockHeader{
  Version:        539656192,
  PrevHash:       [32]byte{
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x04, 0x0b, 0xd2, 0xd1, 0x6b, 0xba, 0x61,
    0x3c, 0xbc, 0xb0, 0x88, 0x40, 0x57, 0x06, 0x4c,
    0xc4, 0x48, 0x5f, 0x6d, 0x5c, 0x81, 0xab, 0xc0,
  },
  MerkleRootHash: [32]byte{
    0xf3, 0x5c, 0x86, 0x7f, 0x07, 0x03, 0xef, 0x74,
    0x1c, 0x99, 0x02, 0xdb, 0x60, 0x08, 0xd4, 0x17,
    0x93, 0x48, 0x0c, 0x7e, 0x8e, 0xa2, 0xf3, 0xa5,
    0x8e, 0x52, 0x12, 0x8c, 0xe1, 0xac, 0x88, 0xda,
  },
  Time:           1640265851,
  Bits:           386638367,
  Nonce:          933616665,
}

これを実際に計算してみると

fmt.Printf("Hash:\n%x\n", header.Hash())
fmt.Printf("Target:\n%x\n", header.Target())
fmt.Printf("Valid: %v\n", header.IsValidHash())

// Hash:
// 0000000000000000000b511bf20ecb6d0ea049862fa2741ed8098e508d98aa3c
// Target:
// 0000000000000000000ba21f0000000000000000000000000000000000000000
// Valid: true

しっかり 0000000000000000000b511bf20ecb6d0ea049862fa2741ed8098e508d98aa3c という元のハッシュ値が算出され、Target 以下になっていることも確認できました 🎉

余談ですが、Version が 539656192 というかなり凄い数字になっていることにお気づきでしょうか? 実は Version の 13-28 bit 目は任意の数値を入れることができるようになっており、これもマイニング時の探索パラメータとして使用されています。

github.com

実際の Version が知りたい場合は 0xE0001FFF で AND をとる必要があります。

おわりに

Block Header からハッシュ値を算出し、それを検証するコードを実装していきました。

実際には今のマイニングマシンでは 32bit の Nonce の全探索は一瞬で終わってしまうので、色々な工夫・アルゴリズムが生み出されています。 これらも実装していきたいですね。

今回のコードの全容はコチラ: https://go.dev/play/p/a_-6rrM3bex

ということで大遅刻の14日目の記事でした。

adventar.org

参考文献


  1. 例えば Ethereum とかだと、微妙に事情が違ったりするので

  2. ハッシュ木 - Wikipedia

  3. と言いつつある程度自由度があるので nonce のようにマイニングのパラメータとして利用されている

  4. Length extension attack - Wikipedia