LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@rivarten

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

Last updated at Posted at 2019-05-18

今更だけどブロックチェーンの勉強始めました　#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とか気になる部分はあるけれど、
とりあえずハッシュ値計算の関数呼び出しの流れは把握できた。

2
1
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
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?