今更だけどブロックチェーンの勉強始めました　#1 概要

はじめ

今回は、マイニング時のブロックのハッシュ値計算について。
(全体的な処理の流れはこちら

これから、Bitcoinの参照実装(https://github.com/bitcoin/bitcoin) のマイニングの流れを見ていく。

ブロックの定義
ブロックハッシュ値の計算
PoWのロジック(次回)

この流れで見ていく。

マイニングの概要についてはこちら

実装見ていくのは、コードを追っているだけなので、自分で見たほうが早いかも。

実装

1.ブロックチェーンの要、ブロックの定義から。

[primitives/block.h]
ざっと見ていると、ブロック情報のシリアライズ(バイト列化)、ブロックのハッシュの計算のメソッドが書いてある。

class CBlockHeader
{
public:
    // header
    int32_t nVersion;
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    uint32_t nTime;
    uint32_t nBits;
    uint32_t nNonce;
…
    ADD_SERIALIZE_METHODS;

    template <typename Stream, typename Operation>
    inline void SerializationOp(Stream& s, Operation ser_action) {
        READWRITE(this->nVersion);
        READWRITE(hashPrevBlock);
        READWRITE(hashMerkleRoot);
        READWRITE(nTime);
        READWRITE(nBits);
        READWRITE(nNonce);
    }
…
    uint256 GetHash() const;
…
};


class CBlock : public CBlockHeader
{
…
    ADD_SERIALIZE_METHODS;

    template <typename Stream, typename Operation>
    inline void SerializationOp(Stream& s, Operation ser_action) {
        READWRITEAS(CBlockHeader, *this);
        READWRITE(vtx);
    }
…

2.ハッシュ値の計算方法について

GetHash()がそれっぽい。

[primitives/block.cpp]

uint256 CBlockHeader::GetHash() const
{
    return SerializeHash(*this);
}

[hash.h]

template<typename T>
uint256 SerializeHash(const T& obj, int nType=SER_GETHASH, int nVersion=PROTOCOL_VERSION)
{
    CHashWriter ss(nType, nVersion);
    ss << obj;
    return ss.GetHash();
}
…
/** A writer stream (for serialization) that computes a 256-bit hash. */
class CHashWriter
{
private:
    CHash256 ctx;

    const int nType;
    const int nVersion;
public:

    CHashWriter(int nTypeIn, int nVersionIn) : nType(nTypeIn), nVersion(nVersionIn) {}

    int GetType() const { return nType; }
    int GetVersion() const { return nVersion; }

    void write(const char *pch, size_t size) {
        ctx.Write((const unsigned char*)pch, size);
    }

    // invalidates the object
    uint256 GetHash() {
        uint256 result;
        ctx.Finalize((unsigned char*)&result);
        return result;
    }

    template<typename T>
    CHashWriter& operator<<(const T& obj) {
        // Serialize to this stream
        ::Serialize(*this, obj);
        return (*this);
    }
};

/** A hasher class for Bitcoin's 256-bit hash (double SHA-256). */
class CHash256 {
private:
    CSHA256 sha;
public:
    static const size_t OUTPUT_SIZE = CSHA256::OUTPUT_SIZE;

    void Finalize(unsigned char hash[OUTPUT_SIZE]) {
        unsigned char buf[CSHA256::OUTPUT_SIZE];
        sha.Finalize(buf);
        sha.Reset().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash);
    }

    CHash256& Write(const unsigned char *data, size_t len) {
        sha.Write(data, len);
        return *this;
    }

    CHash256& Reset() {
        sha.Reset();
        return *this;
    }
};

処理順は以下のような流れになっている様だ。

CBlockHeader::GetHash()
  SerializeHash()
  -> CHashWriter <<
  -> CHashWriter::GetHash()
    -> CHash256::Finalize()
      -> CSHA256::Finalize()

これでブロックのSHA256ハッシュ値が取得できるようだ。

分かったような分からんような。
ストリーム、シリアライズの方法。

ストリームって何？

ストリーム (プログラミング) - Wikipedia

ストリーム（stream）とはデータを「流れるもの」として捉え、流れ込んでくるデータを入力、流れ出ていくデータを出力として扱う抽象データ型である。ファイルの入出力を扱うもの、メモリバッファの入出力を扱うもの、ネットワーク通信を扱うものなどさまざまなものがある。

とりあえずここにデータを入れたら、逐次処理されていく感じなのかな。

なぜストリームなの？

SHA256のハッシュ値の計算は、先頭から256bit(64byte)毎に区切って読み取ってハッシュ値を計算して、それを次の計算に用いる。
入れたデータを指定量毎に逐次処理するのには、ストリームが良いのかも。
入れたデータをストックしなくて良い要件だとこうなのかな。

SHA256について

http://landau.jp/blog/165/
(http://wiz-code.net/vb/algorithm/sha256/
(https://www.jstage.jst.go.jp/article/essfr/4/1/4_1_57/_pdf

それを踏まえて

[hash.h]

template<typename T>
uint256 SerializeHash(const T& obj, int nType=SER_GETHASH, int nVersion=PROTOCOL_VERSION)
{
    CHashWriter ss(nType, nVersion);
    ss << obj;
    return ss.GetHash();
}

/** A writer stream (for serialization) that computes a 256-bit hash. */
class CHashWriter
{
…
    template<typename T>
    CHashWriter& operator<<(const T& obj) {
        // Serialize to this stream
        ::Serialize(*this, obj);
        return (*this);
    }
};

s << obj
objをシリアライズ
return ss.GetHash()
ハッシュ値を返す。

::Serializeってどこにある？

　ADD_SERIALIZE_METHODSマクロで各クラスに定義を追加している

ADD_SERIALIZE_METHODSって何？

[serialize.h]

# define ADD_SERIALIZE_METHODS                                         \
    template<typename Stream>                                         \
    void Serialize(Stream& s) const {                                 \
        NCONST_PTR(this)->SerializationOp(s, CSerActionSerialize());  \
    }                                                                 \
    template<typename Stream>                                         \
    void Unserialize(Stream& s) {                                     \
        SerializationOp(s, CSerActionUnserialize());                  \
    }

・template<typename Stream> inline void Serialize(Stream& s, char a    ) { ser_writedata8(s, a); }
・template<typename Stream> inline void Serialize(Stream& s, int8_t a  ) { ser_writedata8(s, a); }

Serializeは、各クラスのSerializationOpを呼んでいる。

ser_writedata8の部分、扱うバイト数によって色々ある

(抜粋)

template<typename Stream> inline void ser_writedata8(Stream &s, uint8_t obj)
{
    s.write((char*)&obj, 1);
}
template<typename Stream> inline void ser_writedata16(Stream &s, uint16_t obj)
{
    obj = htole16(obj);
    s.write((char*)&obj, 2);
}
template<typename Stream> inline void ser_writedata16be(Stream &s, uint16_t obj)
{
    obj = htobe16(obj);
    s.write((char*)&obj, 2);
}
template<typename Stream> inline void ser_writedata32(Stream &s, uint32_t obj)
{
    obj = htole32(obj);
    s.write((char*)&obj, 4);
}
template<typename Stream> inline void ser_writedata64(Stream &s, uint64_t obj)
{
    obj = htole64(obj);
    s.write((char*)&obj, 8);
}
template<typename Stream> inline uint8_t ser_readdata8(Stream &s)

実際に、ストリームにデータを書き込んでいるのはこの関数の様に見える。

SerializationOp

    template <typename Stream, typename Operation>
    inline void SerializationOp(Stream& s, Operation ser_action) {
        READWRITE(this->nVersion);
        READWRITE(hashPrevBlock);
        READWRITE(hashMerkleRoot);
        READWRITE(nTime);
        READWRITE(nBits);
        READWRITE(nNonce);
    }

READWRITE

[serialize.h]

# define READWRITE(...) (::SerReadWriteMany(s, ser_action, __VA_ARGS__))
# define READWRITEAS(type, obj) (::SerReadWriteMany(s, ser_action, ReadWriteAsHelper<type>(obj)))

ストリームにデータを入れているのか？

template<typename Stream, typename... Args>
inline void SerReadWriteMany(Stream& s, CSerActionSerialize ser_action, const Args&... args)
{
    ::SerializeMany(s, args...);
}

template<typename Stream>
void SerializeMany(Stream& s)
{
}

template<typename Stream, typename Arg, typename... Args>
void SerializeMany(Stream& s, const Arg& arg, const Args&... args)
{
    ::Serialize(s, arg);
    ::SerializeMany(s, args...);
}

Serializeは、結局s.write((char*)&obj, 1);などの処理。ストリームに入れている。

SerializeManyは可変長引数の場合にも対応出来るようにしているのだろう。
args... がない場合は処理が何もないので、そのへんで再帰関数のストップをかけている様だ。
こんな実装もあるのか。

s.write()の先

CHashWriter::write
  -> CHash256::Write
    -> CSHA256::Write

この先の話。SHA256。

[crypto/sha256.h]

/** A hasher class for SHA-256. */
class CSHA256
{
private:
    uint32_t s[8];
    unsigned char buf[64];
    uint64_t bytes;

public:
    static const size_t OUTPUT_SIZE = 32;

    CSHA256();
    CSHA256& Write(const unsigned char* data, size_t len);
    void Finalize(unsigned char hash[OUTPUT_SIZE]);
    CSHA256& Reset();
};

[crypto/sha256.cpp]

CSHA256& CSHA256::Write(const unsigned char* data, size_t len)
{
    const unsigned char* end = data + len;
    size_t bufsize = bytes % 64;
    if (bufsize && bufsize + len >= 64) {
        // Fill the buffer, and process it.
        memcpy(buf + bufsize, data, 64 - bufsize);
        bytes += 64 - bufsize;
        data += 64 - bufsize;
        Transform(s, buf, 1);
        bufsize = 0;
    }
    if (end - data >= 64) {
        size_t blocks = (end - data) / 64;
        Transform(s, data, blocks);
        data += 64 * blocks;
        bytes += 64 * blocks;
    }
    if (end > data) {
        // Fill the buffer with what remains.
        memcpy(buf + bufsize, data, end - data);
        bytes += end - data;
    }
    return *this;
}
void CSHA256::Finalize(unsigned char hash[OUTPUT_SIZE])
{
    static const unsigned char pad[64] = {0x80};
    unsigned char sizedesc[8];
    WriteBE64(sizedesc, bytes << 3);
    Write(pad, 1 + ((119 - (bytes % 64)) % 64));
    Write(sizedesc, 8);
    WriteBE32(hash, s[0]);
    WriteBE32(hash + 4, s[1]);
    WriteBE32(hash + 8, s[2]);
    WriteBE32(hash + 12, s[3]);
    WriteBE32(hash + 16, s[4]);
    WriteBE32(hash + 20, s[5]);
    WriteBE32(hash + 24, s[6]);
    WriteBE32(hash + 28, s[7]);
}

[crypto/common.h]

void static inline WriteBE32(unsigned char* ptr, uint32_t x)
{
    uint32_t v = htobe32(x);
    memcpy(ptr, (char*)&v, 4);
}

ビッグエンディアンか。

Write()でどんどん書き込んでいって、途中の計算結果がbytesに記憶されている。
終わったらFinalize()を呼んで何か最後の処理をして、Finalize()の引数に出力する。
次の計算するときにはReset()を呼ぶ感じ。

...なにやってたんだっけ？

ハッシュ値の計算方法

CBlockHeader::GetHash()
  SerializeHash()
  -> CHashWriter <<
  -> CHashWriter::GetHash()
    -> CHash256::Finalize(&result)
    -> return result;

class CHash256 {
…
void Finalize(unsigned char hash[OUTPUT_SIZE]) {
        unsigned char buf[CSHA256::OUTPUT_SIZE];
        sha.Finalize(buf);
        sha.Reset().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash);
    }

`sha.Reset().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash);`は何やってるの？

なぜ、１回ハッシュ計算して得た値をもとに、もう一回ハッシュ値を計算しているのか、意味不明。

どうやら、ダブルハッシュというらしい。
"length extension attackの対策"との事らしいが。。

length extension attackはMerkle-Damgård constructionで構築されているhash関数すべてで可能です。

結局 CBlockHeader::GetHash()の流れ

CBlockHeader::GetHash()
-> SerializeHash(CBlockHeadder)
  -> CHashWriter << CBlockHeader
  | -> CBlockHeader::Serialize(CHashWriter, CBlockHeader)
  |   -> CBlockHeader::SerializationOp(CHashWriter, CSerActionSerialize()) 
  |     -> READWRITE(this->nVersion);
  |     | -> SerReadWriteMany(nVersion, CSerActionSerialize())
  |     |   -> SerializeMany(CHashWriter, nVersion)
  |     |     -> Serialize(CHashWriter, nVersion)
  |     |       ->  ser_writedata~~(CHashWriter, nVersion)
  |     |         -> CHashWriter::write(nVersion, ~~)
  |     |           -> CHash256::Write(nVersion)
  |     |           ->  CSHA256::Write(nVersion)
  |     -> READWRITE(hashPrevBlock);
  |     -> READWRITE(hashMerkleRoot);
  |     -> READWRITE(nTime);
  |     -> READWRITE(nBits);
  |     -> READWRITE(nNonce);
  -> CHashWriter::GetHash()
    -> CHash256::Finalize(&result)
      -> CSHA256::Finalize(buf)
      -> CSHA256::Reset()
      -> CSHA256::Write(buf)
      -> CSHA256::Finalize(buf)
    -> return result

おわり

hashMerkleRoot(マークル木), SHA256, ダブルハッシュ, Merkle-Damgård constructionとか気になる部分はあるけれど、
とりあえずハッシュ値計算の関数呼び出しの流れは把握できた。