0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@andrry7777

Bitcoinマイニングが気になって、まずはSHA-256をDartで生実装してみた

0
Posted at

背景

Bitcoin のマイニングに興味を持って調べていたところ、Proof of Work のコア計算に SHA-256 が使われていることを知りました。

SHA-256 自体をちゃんと理解したら、マイニングの仕組みも理解できて億万長者じゃん★

と思い、本記事を作成しました。

結論

SHA-256 は

  • 入力を規定の形に整える
  • 32bit の値をひたすら回転・XOR・加算する
  • それを 64 round 回す

という、かなり脳筋アルゴリズムでした。

SHA-256 の全体像

SHA-256 の流れはざっくりこうです。

  1. 入力をバイト列にする
  2. padding を入れて、長さが 512bit の倍数になるよう整える
  3. 512bit ごとのブロックに分割する
  4. 各ブロックを 32bit × 64 語のスケジュールに展開する
  5. 8 個のワーキング変数を 64 round 更新する
  6. 最後に 256bit の digest を出力する

以下、この 1 から 6 に対応させながら見ていきます。

1. 入力をバイト列にする

アプリケーション開発では、文字列をそのまま文字列として扱うことが多いと思います。
ただし SHA-256 が直接扱うのは String ではなく、あくまで byte の並び です。

なので最初にやることは、「文字列を UTF-8 の byte 列に変換する」です。

static Uint8List hashUtf8(String message) {
  return hashBytes(utf8.encode(message));
}

たとえば "abc" は UTF-8 にすると 3 byte です。

"a" -> 0x61
"b" -> 0x62
"c" -> 0x63

ここでは「SHA-256 は文字列を見ているのではなく、最終的には byte 配列を見ている」と押さえれば十分です。

2. padding を入れて、長さが 512bit の倍数になるよう整える

SHA-256 は入力を 512bit ごとの固定長ブロックで処理します。
なので、長さが中途半端な入力でも必ずその形に揃える必要があります。

そのために入れるのが padding です。

元データ || 1 || 0...0 || 元データ長(64bit)

コードにするとこうなります。

static List<int> padMessage(List<int> messageBytes) {
  final padded = List<int>.from(messageBytes);
  final messageLengthInBits =
      BigInt.from(messageBytes.length) * BigInt.from(8);

  padded.add(0x80);

  while (padded.length % 64 != 56) {
    padded.add(0x00);
  }

  for (var shift = 56; shift >= 0; shift -= 8) {
    final byteValue = (messageLengthInBits >> shift).toInt() & 0xff;
    padded.add(byteValue);
  }

  return padded;
}

やっていることは 3 つだけです。

  1. 元データの後ろに 1bit だけ足す
  2. その後ろを 0 で埋める
  3. 最後の 64bit に「元データの長さ」を入れる

ここで混乱しやすいポイント 1: 56 は bit ではなく byte

56 は 56 bit ではなく 56 byte です。

  • 1 block = 64 byte = 512 bit
  • 最後の 8 byte = 64 bit は長さ欄に使う
  • だからその直前の 56 byte 地点まで 0 埋めする

つまり、

56 byte + 8 byte = 64 byte

というだけです。

ここで混乱しやすいポイント 2: なぜ元データ長を入れるのか

もし長さを書かなければ、

  • "abc"
  • "abc" + たくさんの 0

の区別がつきにくくなります。

そこで「元のデータは何 bit だったか」を末尾に明示して、入力を一意に復元しやすい形にしています。

3. 512bit ごとのブロックに分割する

padding が終わったら、あとは 64 byte ごとに順番に処理します。

static Uint8List hashBytes(List<int> messageBytes) {
  final paddedMessage = padMessage(messageBytes);
  var state = List<int>.from(_initialHashValues);

  for (var offset = 0; offset < paddedMessage.length; offset += 64) {
    final chunk = paddedMessage.sublist(offset, offset + 64);
    state = compressChunk(chunk, initialState: state);
  }

  return _stateToBytes(state);
}

この chunk が、SHA-256 の 1 ブロックです。

ここで大事なのは、各ブロックが独立しているわけではないことです。
前のブロックの計算結果を、次のブロックへ引き継ぎます。

つまりイメージとしては、

block 0 を処理 -> state 更新
block 1 を処理 -> さっきの state を使ってさらに更新
block 2 を処理 -> また続きを更新

というストリーム処理に近いです。

4. 各ブロックを 32bit × 64 語のスケジュールに展開する

1 ブロックは 64 byte ですが、そのまま 1 byte ずつ処理するわけではありません。
SHA-256 は基本的に 32bit 単位で計算するので、まずは 64 byte を 32bit の値へ組み替えます。

そのうえで、最終的に 64 個の値へ拡張します。

4-1. まず 4 byte を 1 つの 32bit 値にまとめる

SHA-256 は 4 byte を 1 つの 32bit 値として扱います。

int _toWord(int b0, int b1, int b2, int b3) {
  return ((b0 << 24) | (b1 << 16) | (b2 << 8) | b3) & _mask32;
}

abc の先頭は padding 後にこうなります。

0x61 0x62 0x63 0x80

これを 1 つの 32bit 値としてまとめると 0x61626380 になります。

4-2. 16 個の値を 64 個に拡張する

static List<int> buildMessageSchedule(List<int> chunkBytes) {
  final schedule = List<int>.filled(64, 0);

  for (var index = 0; index < 16; index++) {
    final base = index * 4;
    schedule[index] = _toWord(
      chunkBytes[base],
      chunkBytes[base + 1],
      chunkBytes[base + 2],
      chunkBytes[base + 3],
    );
  }

  for (var index = 16; index < 64; index++) {
    final s0 = _smallSigma0(schedule[index - 15]);
    final s1 = _smallSigma1(schedule[index - 2]);
    schedule[index] =
        (schedule[index - 16] + s0 + schedule[index - 7] + s1) & _mask32;
  }

  return schedule;
}
  • W[0] から W[15] は元データ
  • W[16] 以降は前の値から拡張

という構造です。
つまり最初の 16 個は「入力そのもの」、残り 48 個は「計算の都合で作る補助データ」です。

ここで使う sigma は、rotate と shift を使って値をうまく散らすための関数です。

5. 8 個のワーキング変数を 64 round 更新する

ここが SHA-256 の心臓部です。

  • a から h まで 8 個の作業用変数を用意する
  • 64 個の schedule を 1 個ずつ使う
  • 毎 round ごとに値を混ぜて更新する

という流れになっています。

static List<int> compressChunk(
  List<int> chunkBytes, {
  List<int>? initialState,
}) {
  final state = List<int>.from(initialState ?? _initialHashValues);
  final schedule = buildMessageSchedule(chunkBytes);

  var a = state[0];
  var b = state[1];
  var c = state[2];
  var d = state[3];
  var e = state[4];
  var f = state[5];
  var g = state[6];
  var h = state[7];

  for (var index = 0; index < 64; index++) {
    final temp1 =
        (h +
            _bigSigma1(e) +
            _choose(e, f, g) +
            _roundConstants[index] +
            schedule[index]) &
        _mask32;

    final temp2 = (_bigSigma0(a) + _majority(a, b, c)) & _mask32;

    h = g;
    g = f;
    f = e;
    e = (d + temp1) & _mask32;
    d = c;
    c = b;
    b = a;
    a = (temp1 + temp2) & _mask32;
  }

  state[0] = (state[0] + a) & _mask32;
  state[1] = (state[1] + b) & _mask32;
  state[2] = (state[2] + c) & _mask32;
  state[3] = (state[3] + d) & _mask32;
  state[4] = (state[4] + e) & _mask32;
  state[5] = (state[5] + f) & _mask32;
  state[6] = (state[6] + g) & _mask32;
  state[7] = (state[7] + h) & _mask32;

  return state;
}

ここでやっているのは、

  • 8 個の 32bit 値を持つ
  • それを 64 回更新する
  • 最後に元の state に足し戻す

だけです。

本当にこれだけです。
ただし、更新ルールがよくできていて、少し入力が違うだけで出力が大きく変わるようになっています。

5-1. round の中で使う補助関数

rotate

int _rightRotate(int value, int amount) {
  final normalized = value & _mask32;
  return ((normalized >>> amount) | ((normalized << (32 - amount)) & _mask32)) &
      _mask32;
}

普通の右シフトは、右に押し出した bit が消えます。
rotate は、押し出した bit を左端に戻します。

choose

int _choose(int x, int y, int z) {
  return ((x & y) ^ ((~x) & z)) & _mask32;
}

これは bit ごとに

  • x が 1 なら y
  • x が 0 なら z

を選ぶ関数です。

majority

int _majority(int x, int y, int z) {
  return ((x & y) ^ (x & z) ^ (y & z)) & _mask32;
}

これは bit ごとの多数決です。

アプリケーション開発者向けに雑に言うと、

  • rotate: 値の並びをずらして再配置する
  • choose: 条件分岐を bit 単位でまとめてやる
  • majority: 3 つの候補から多数派を取る

という役割です。

6. 最後に 256bit の digest を出力する

64 round の計算が終わったら、内部で持っている 8 個の 32bit 値を 32 byte に並べ直します。

Uint8List _stateToBytes(List<int> state) {
  final digest = Uint8List(32);
  for (var index = 0; index < state.length; index++) {
    final word = state[index];
    final base = index * 4;
    digest[base] = (word >>> 24) & 0xff;
    digest[base + 1] = (word >>> 16) & 0xff;
    digest[base + 2] = (word >>> 8) & 0xff;
    digest[base + 3] = word & 0xff;
  }
  return digest;
}

これで最終的な 256bit のハッシュ値が得られます。
普段よく見る ba7816bf... のような表記は、この 32 byte を 16 進文字列に直したものです。

定数の正体

初期値 _initialHashValues は、最初の 8 個の素数の平方根の小数部分から作られています。
一方、_roundConstants は最初の 64 個の素数の立方根の小数部分から作られています。

つまり「なんか適当に並べた値」ではなく、恣意性が少ないように選ばれた定数です。

まとめ

実装してみて感じたのは、SHA-256 は

  • 入力を決まった形に整える
  • 固定の定数とビット演算で混ぜる
  • それを 64 round 回す

という、かなりストレートな構造だということでした。
シンプルだからこそ破られない。なんかアニメの強キャラみたいでいいですね。

終わりに

気になる点があれば是非コメントお願いします！

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?