BitCoinにおけるブロックハッシュの生成プログラム

ブロックハッシュ

BitCoin等のネット通貨においてはハッシュ関数が重要な役割を果たしています。BitCoinではハッシュ関数としてSHA256が用いられています。

個人的に理解を深めるため、C++でSHA256の内部処理も含めたプログラムを作成してみました。このプログラムとブロックチェーンのデータを用い、Nonceを変えながらハッシュ値がTargetを下回るようなブロックを探すことで、BitCoinの採掘が可能です。ただ、現実的には速度や電気代を考えると、とても採算は取れないでしょう。採掘は今や専用ハードウェアを用いるのが主流になっています。

SHA256の入出力は本来はByte単位ですが、内部処理は32ビットで行っていますので、効率化のため入出力も32bit単位に限定して作成しました。また、BitCoinの処理に限定するということで、データのサイズも限定しています。

このプログラムではデータをByte列としては扱っていませんが、元々の規格では、Byte列にしたとき、BitCoinの規格はリトルエンディアン、SHA256の規格はビッグエンディアンを採用しており、データの格納順序が異なります。そのため、32ビット単位でのデータの受け渡しの際にも8bit単位の処理が必要となっています。

サンプルプログラム

main()関数でサンプルデータを入力していますので、実行すると以下のような結果が得られます。

-----------------------------------------------------------------------------
Version    : 00000003
PrevBlock  : 00000000000000000e8d3266c478c3102a7b54582fb90963aa0bed93747dff0d
MerkleRoot : 36a37dc0564f1496e74342d96ba7099d987e482891d7954ebe7188f5f5074e0f
TimeStamp  : 56075f35
Difficulty : 181287ba
Nonce      : 40828f90
Target     : 00000000000000001287ba000000000000000000000000000000000000000000
-----------------------------------------------------------------------------
BlockHash  : 0000000000000000076bbce0dec01b68dc7051ad653de46ffd2156bc7705c5cc

プログラムが枠をはみ出しているのは大目に見て下さい。

#include <stdint.h>
#include <iostream>
#include <iomanip>

using namespace std; 

// 右シフト
#define ShR(x,n) (x>>n)
// 右ローテート
#define RotR(x,n) ((x>>n)|(x<<(32-n)))
// 選択関数: xのbitが1→yを選択、xのbitが0→zを選択
#define Ch(x,y,z) ((x&(y^z))^z)
// 多数決関数: x,y,zのbitのうち、2つ以上が0→0、2つ以上が1→1
#define Maj(x,y,z) ((x&(y|z))|(y&z))

#define S0(x) (RotR(x, 2)^RotR(x,13)^RotR(x,22))
#define S1(x) (RotR(x, 6)^RotR(x,11)^RotR(x,25))
#define s0(x) (RotR(x, 7)^RotR(x,18)^ ShR(x, 3))
#define s1(x) (RotR(x,17)^RotR(x,19)^ ShR(x,10))

const uint32_t K[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

const uint32_t H0[8]= {
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};

// SHA256によるブロックハッシュ生成関数（32bit単位に限定）
void SHA(uint32_t *Hash, uint32_t *M, int s){
    int Len = 32-s*12; // s=1 -> Len=20, Blk=2
    int Blk = 3-s;     // s=2 -> Len=8,  Blk=1

    uint32_t H[8];
    for(int i=0; i<8; i++){
        H[i] = H0[i];
    }

    uint32_t W[64];
    int m = 0;
    for(int k=0; k<Blk; k++){
        for(int t=0; t<16; t++, m++){
            if(m<Len){
                W[t] = M[m];
            } else if(m==Len){
                W[t] = 0x80000000;
            } else if(t==15){
                W[t] = Len<<5;
            } else {
                W[t] = 0;
            }
        }
        for(int t=16; t<64; t++){
            W[t] = s1(W[t-2]) + W[t-7] + s0(W[t-15]) + W[t-16];
        }

        uint32_t h[8];
        for(int i=0; i<8; i++){
            h[i] = H[i];
        }
        for(int i=0; i<64; i++){
            uint32_t T1 = h[7] + S1(h[4]) + Ch(h[4],h[5],h[6]) + K[i] + W[i];
            uint32_t T2 = S0(h[0]) + Maj(h[0],h[1],h[2]);
            h[7] = h[6];
            h[6] = h[5];
            h[5] = h[4];
            h[4] = h[3] + T1;
            h[3] = h[2];
            h[2] = h[1];
            h[1] = h[0];
            h[0] = T1 + T2;
        }
        for(int i=0; i<8; i++){
            H[i] += h[i];
        }
    }
    for(int i=0; i<8; i++){
        Hash[i] = H[i];
    }
}

// 0-9,a-zの文字を数値に変換する関数
int c2i(char c){
    if('0'<=c && c<='9'){
        return c-'0';
    } else if('a'<=c && c<='f'){
        return c-'a'+10;
    } else if('A'<=c && c<='F'){
        return c-'A'+10;
    }
    return 0;
}

// ブロックの各フィールドにデータを格納
void Set(uint32_t *M, uint32_t Version, char *PrevBlock, char *MerkleRoot, uint32_t TimeStamp, uint32_t Difficulty, uint32_t Nonce){
    for(int i=0; i<20; i++){
        M[i] = 0;
    }

    char *Ptr[2] = {PrevBlock, MerkleRoot};
    for(int t=0; t<2; t++){
        int k = 64;
        for(int j=t*8+1; j<=t*8+8; j++){
            for(int i=0; i<4; i++){
                char c0 = c2i(Ptr[t][--k]);
                char c1 = c2i(Ptr[t][--k]);
                M[j] = (M[j]<<8) + (c1<<4) + c0;
            }
        }
    }

    uint32_t Value[4] = {Version, TimeStamp, Difficulty, Nonce};
    int Pos[4] = {0, 17, 18, 19};
    for(int t=0; t<4; t++){
        int ps = Pos[t];
        for(int i=0; i<32; i+=8){
            M[ps] = (M[ps]<<8) + (0xff & (Value[t]>>i));
        }
    }
}

// ブロックハッシュの目標値（target）を生成
void Target(uint32_t *T, uint32_t targ){
    for(int i=0; i<8; i++){
        T[i] = 0;
    }
    int s = (targ>>24)-3;
    if(s>=0 && s<30){
        for(int i=0; i<3; i++, s++){
            T[s>>2] += ((targ>>(i*8))&0xff)<<(((~s)&3)*8);
        }
    }
}

// フィールドを表示
void Show(uint32_t *M, int Len){
    for(int i=Len-1; i>=0; i--){
        for(int j=0; j<4; j++){
            cout << setw(2) << setfill('0') << hex << ((M[i]>>(8*j))&0xff);
        }
    }
    cout << endl;
}

int main(){

    // サンプルデータ
    uint32_t Version     = 3;
    char *PrevBlock  = "00000000000000000e8d3266c478c3102a7b54582fb90963aa0bed93747dff0d";
    char *MerkleRoot = "36a37dc0564f1496e74342d96ba7099d987e482891d7954ebe7188f5f5074e0f";
    uint32_t TimeStamp   = 1443323701;
    uint32_t Difficulty  =  403867578;
    uint32_t Nonce       = 1082298256;

    uint32_t M[20], T[8];
    Set(M, Version, PrevBlock, MerkleRoot, TimeStamp, Difficulty, Nonce);
    Target(T, Difficulty);

    cout << "-----------------------------------------------------------------------------" << endl;
    cout << "Version    : "; Show(M, 1);
    cout << "PrevBlock  : "; Show(M+1, 8);
    cout << "MerkleRoot : "; Show(M+9, 8);
    cout << "TimeStamp  : "; Show(M+17, 1);
    cout << "Difficulty : "; Show(M+18, 1);
    cout << "Nonce      : "; Show(M+19, 1);
    cout << "Target     : "; Show(T, 8);
    cout << "-----------------------------------------------------------------------------" << endl;

    uint32_t Hash[8];
    SHA(Hash, M, 1);
    SHA(Hash, Hash, 2);

    cout << "BlockHash  : "; Show(Hash, 8);

    return 0;
}