今更だけどブロックチェーンの勉強始めました　#2 Bitcoin参照実装を見ていく - ブロック、ハッシュ値計算

[今更だけどブロックチェーンの勉強始めました　#1 概要](https://qiita.com/rivarten/items/7dfe6f348368b5d9f46b)

#はじめ

今回は、マイニング時のブロックのハッシュ値計算について。
(全体的な処理の流れは[こちら](https://qiita.com/rivarten/items/7dfe6f348368b5d9f46b#%E5%87%A6%E7%90%86%E3%81%AE%E6%B5%81%E3%82%8C)

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

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

この流れで見ていく。

マイニングの概要については[こちら](https://qiita.com/rivarten/items/7dfe6f348368b5d9f46b#%E3%83%9E%E3%82%A4%E3%83%8B%E3%83%B3%E3%82%B0)

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

# 実装
### 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](https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%83%AA%E3%83%BC%E3%83%A0_\(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)

> ストリーム（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);`は何やってるの？

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

http://luca3104.hatenablog.com/entry/2018/03/31/220555

どうやら、ダブルハッシュというらしい。
"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とか気になる部分はあるけれど、
とりあえずハッシュ値計算の関数呼び出しの流れは把握できた。