Merkle Tree 构建（C++实现）

区块链学习笔记（一）

一、相关知识简要介绍

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash，下图为一个简单的Merkle树的结构。

在比特币网络中，Merkle树被用来归纳一个区块中的所有交易，同时生成整个交易集合的数字指纹，且提供了一种校验区块是否存在某交易的高效途径。

Hash是一个把任意长度的数据映射成固定长度数据的函数。例如，对于数据完整性校验，最简单的方法是对整个数据做Hash运算得到固定长度的Hash值，然后把得到的Hash值公布在网上，这样用户下载到数据之后，对数据再次进行Hash运算，比较运算结果和网上公布的Hash值进行比较，如果两个Hash值相等，说明下载的数据没有损坏。可以这样做是因为输入数据的稍微改变就会引起Hash运算结果的面目全非，而且根据Hash值反推原始输入数据的特征是困难的。

生成一棵完整的Merkle树需要递归地对Hash节点对进行Hash，并将新生成的hash节点插入到Merkle树中，直到只剩一个Hash节点，该节点就是Merkle 树的根。在比特币的 Merkle树中两次使用到了SHA256算法，因此其加密哈希算法也被称为 double-SHA256。

(本次Merkle Tree构建过程使用的hash函数为SHA-256)

二、Merkle Tree构建及检验相关代码

1.

#pragma once#include #include #include "sha256.h"#include #include using namespace std;class node{private:string hash_str;node* parent;node* children[2];public:node();node* getParent();void setChildren(node* children_l, node* children_r);node* getChildren(int index);void setParent(node* parent);string getHash();int checkDir();node* getSibling();void setHash(string hash_str);virtual ~node();};node::node(){parent = nullptr;children[0] = nullptr;children[1] = nullptr;}//设置哈希值void node::setHash(string hash_str){this->hash_str = sha2::hash256_hex_string(hash_str);}node* node::getParent(){return parent;}void node::setParent(node* parent){this->parent = parent;}void node::setChildren(node* children_l, node* children_r){children[0] = children_l;children[1] = children_r;}node* node::getSibling() //是左孩子得到右孩子，是右孩子得到左孩子{//得到该节点的父节点node* parent = getParent();//判断父节点的左孩子和本节点是否相同//相同返回右孩子，不同返回左孩子return parent->getChildren(0) == this ? parent->getChildren(1) : parent->getChildren(0);}node* node::getChildren(int index){return index <= 1 ? children[index] : nullptr;}string node::getHash(){return hash_str;}int node::checkDir(){//如果其父节点的左孩子是该节点 返回0 否则则返回1return parent->getChildren(0) == this ? 0 : 1;}node::~node() {}

2.

#pragma once#ifndef PICOSHA2_H#define PICOSHA2_H#ifndef PICOSHA2_BUFFER_SIZE_FOR_INPUT_ITERATOR#define PICOSHA2_BUFFER_SIZE_FOR_INPUT_ITERATOR \1048576 #endif#include #include #include #include #include namespace sha2 {typedef unsigned long ulong;typedef unsigned char uchar;static const size_t k_digest_size = 32;namespace detail {inline uchar mask_8bit(uchar x) { return x & 0xff; }inline ulong mask_32bit(ulong x) { return x & 0xffffffff; }const ulong add_constant[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 ulong initial_message_digest[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 };inline ulong ch(ulong x, ulong y, ulong z) {return (x & y) ^ ((~x) & z);}inline ulong maj(ulong x, ulong y, ulong z) {return (x & y) ^ (x & z) ^ (y & z);}inline ulong rotr(ulong x, std::size_t n) {assert(n < 32);return mask_32bit((x >> n) | (x << (32 - n)));}inline ulong bsig0(ulong x) {return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22);}inline ulong bsig1(ulong x) {return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25);}inline ulong shr(ulong x, std::size_t n) {assert(n < 32);return x >> n;}inline ulong ssig0(ulong x) {return rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3);}inline ulong ssig1(ulong x) {return rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10);}template <typename RaIter1, typename RaIter2>void hash256_block(RaIter1 message_digest, RaIter2 first, RaIter2 last) {assert(first + 64 == last);static_cast<void>(last);ulong w[64];std::fill(w, w + 64, 0);for (std::size_t i = 0; i < 16; ++i) {w[i] = (static_cast<ulong>(mask_8bit(*(first + i * 4))) << 24) |(static_cast<ulong>(mask_8bit(*(first + i * 4 + 1))) << 16) |(static_cast<ulong>(mask_8bit(*(first + i * 4 + 2))) << 8) |(static_cast<ulong>(mask_8bit(*(first + i * 4 + 3))));}for (std::size_t i = 16; i < 64; ++i) {w[i] = mask_32bit(ssig1(w[i - 2]) + w[i - 7] + ssig0(w[i - 15]) +w[i - 16]);}ulong a = *message_digest;ulong b = *(message_digest + 1);ulong c = *(message_digest + 2);ulong d = *(message_digest + 3);ulong e = *(message_digest + 4);ulong f = *(message_digest + 5);ulong g = *(message_digest + 6);ulong h = *(message_digest + 7);for (std::size_t i = 0; i < 64; ++i) {ulong temp1 = h + bsig1(e) + ch(e, f, g) + add_constant[i] + w[i];ulong temp2 = bsig0(a) + maj(a, b, c);h = g;g = f;f = e;e = mask_32bit(d + temp1);d = c;c = b;b = a;a = mask_32bit(temp1 + temp2);}*message_digest += a;*(message_digest + 1) += b;*(message_digest + 2) += c;*(message_digest + 3) += d;*(message_digest + 4) += e;*(message_digest + 5) += f;*(message_digest + 6) += g;*(message_digest + 7) += h;for (std::size_t i = 0; i < 8; ++i) {*(message_digest + i) = mask_32bit(*(message_digest + i));}}}template <typename InIter>void output_hex(InIter first, InIter last, std::ostream& os) {os.setf(std::ios::hex, std::ios::basefield);while (first != last) {os.width(2);os.fill('0');os << static_cast<unsigned int>(*first);++first;}os.setf(std::ios::dec, std::ios::basefield);}template <typename InIter>void bytes_to_hex_string(InIter first, InIter last, std::string& hex_str) {std::ostringstream oss;output_hex(first, last, oss);hex_str.assign(oss.str());}template <typename InContainer>void bytes_to_hex_string(const InContainer& bytes, std::string& hex_str) {bytes_to_hex_string(bytes.begin(), bytes.end(), hex_str);}template <typename InIter>std::string bytes_to_hex_string(InIter first, InIter last) {std::string hex_str;bytes_to_hex_string(first, last, hex_str);return hex_str;}template <typename InContainer>std::string bytes_to_hex_string(const InContainer& bytes) {std::string hex_str;bytes_to_hex_string(bytes, hex_str);return hex_str;}class hash256_one_by_one {public:hash256_one_by_one() { init(); }void init() {buffer_.clear();std::fill(data_length_digits_, data_length_digits_ + 4, 0);std::copy(detail::initial_message_digest,detail::initial_message_digest + 8, h_);}template <typename RaIter>void process(RaIter first, RaIter last) {add_to_data_length(std::distance(first, last));std::copy(first, last, std::back_inserter(buffer_));std::size_t i = 0;for (; i + 64 <= buffer_.size(); i += 64) {detail::hash256_block(h_, buffer_.begin() + i,buffer_.begin() + i + 64);}buffer_.erase(buffer_.begin(), buffer_.begin() + i);}void finish() {uchar temp[64];std::fill(temp, temp + 64, 0);std::size_t remains = buffer_.size();std::copy(buffer_.begin(), buffer_.end(), temp);temp[remains] = 0x80;if (remains > 55) {std::fill(temp + remains + 1, temp + 64, 0);detail::hash256_block(h_, temp, temp + 64);std::fill(temp, temp + 64 - 4, 0);}else {std::fill(temp + remains + 1, temp + 64 - 4, 0);}write_data_bit_length(&(temp[56]));detail::hash256_block(h_, temp, temp + 64);}template <typename OutIter>void get_hash_bytes(OutIter first, OutIter last) const {for (const ulong* iter = h_; iter != h_ + 8; ++iter) {for (std::size_t i = 0; i < 4 && first != last; ++i) {*(first++) = detail::mask_8bit(static_cast<uchar>((*iter >> (24 - 8 * i))));}}}private:void add_to_data_length(ulong n) {ulong carry = 0;data_length_digits_[0] += n;for (std::size_t i = 0; i < 4; ++i) {data_length_digits_[i] += carry;if (data_length_digits_[i] >= 65536u) {carry = data_length_digits_[i] >> 16;data_length_digits_[i] &= 65535u;}else {break;}}}void write_data_bit_length(uchar* begin) {ulong data_bit_length_digits[4];std::copy(data_length_digits_, data_length_digits_ + 4,data_bit_length_digits);ulong carry = 0;for (std::size_t i = 0; i < 4; ++i) {ulong before_val = data_bit_length_digits[i];data_bit_length_digits[i] <<= 3;data_bit_length_digits[i] |= carry;data_bit_length_digits[i] &= 65535u;carry = (before_val >> (16 - 3)) & 65535u;}for (int i = 3; i >= 0; --i) {(*begin++) = static_cast<uchar>(data_bit_length_digits[i] >> 8);(*begin++) = static_cast<uchar>(data_bit_length_digits[i]);}}std::vector<uchar> buffer_;ulong data_length_digits_[4];ulong h_[8];};inline void get_hash_hex_string(const hash256_one_by_one& hasher,std::string& hex_str) {uchar hash[k_digest_size];hasher.get_hash_bytes(hash, hash + k_digest_size);return bytes_to_hex_string(hash, hash + k_digest_size, hex_str);}inline std::string get_hash_hex_string(const hash256_one_by_one& hasher) {std::string hex_str;get_hash_hex_string(hasher, hex_str);return hex_str;}namespace impl {template <typename RaIter, typename OutIter>void hash256_impl(RaIter first, RaIter last, OutIter first2, OutIter last2, int,std::random_access_iterator_tag) {hash256_one_by_one hasher;hasher.process(first, last);hasher.finish();hasher.get_hash_bytes(first2, last2);}template <typename InputIter, typename OutIter>void hash256_impl(InputIter first, InputIter last, OutIter first2,OutIter last2, int buffer_size, std::input_iterator_tag) {std::vector<uchar> buffer(buffer_size);hash256_one_by_one hasher;while (first != last) {int size = buffer_size;for (int i = 0; i != buffer_size; ++i, ++first) {if (first == last) {size = i;break;}buffer[i] = *first;}hasher.process(buffer.begin(), buffer.begin() + size);}hasher.finish();hasher.get_hash_bytes(first2, last2);}}template <typename InIter, typename OutIter>void hash256(InIter first, InIter last, OutIter first2, OutIter last2,int buffer_size = PICOSHA2_BUFFER_SIZE_FOR_INPUT_ITERATOR) {sha2::impl::hash256_impl(first, last, first2, last2, buffer_size,typename std::iterator_traits<InIter>::iterator_category());}template <typename InIter, typename OutContainer>void hash256(InIter first, InIter last, OutContainer& dst) {hash256(first, last, dst.begin(), dst.end());}template <typename InContainer, typename OutIter>void hash256(const InContainer& src, OutIter first, OutIter last) {hash256(src.begin(), src.end(), first, last);}template <typename InContainer, typename OutContainer>void hash256(const InContainer& src, OutContainer& dst) {hash256(src.begin(), src.end(), dst.begin(), dst.end());}template <typename InIter>void hash256_hex_string(InIter first, InIter last, std::string& hex_str) {uchar hashed[k_digest_size];hash256(first, last, hashed, hashed + k_digest_size);std::ostringstream oss;output_hex(hashed, hashed + k_digest_size, oss);hex_str.assign(oss.str());}template <typename InIter>std::string hash256_hex_string(InIter first, InIter last) {std::string hex_str;hash256_hex_string(first, last, hex_str);return hex_str;}inline void hash256_hex_string(const std::string& src, std::string& hex_str) {hash256_hex_string(src.begin(), src.end(), hex_str);}template <typename InContainer>void hash256_hex_string(const InContainer& src, std::string& hex_str) {hash256_hex_string(src.begin(), src.end(), hex_str);}template <typename InContainer>std::string hash256_hex_string(const InContainer& src) {return hash256_hex_string(src.begin(), src.end());}}// namespace sha2#endif// PICOSHA2_H

3.

#pragma once#include "node.h"#include #include "sha256.h"using namespace std;class tree{private:string merkleRoot;int makeBinary(vector<node*>& node_vector);void printTreeLevel(vector<node*> v);vector<vector<node*>> base; //里面存的是一个个节点列表public:tree();void buildTree();void buildBaseLeafes(vector<string> base_leafs);int verify(string hash);virtual ~tree();};tree::tree() {}int tree::makeBinary(vector<node*>& node_vector) //使叶子节点成为双数{int vectSize = node_vector.size();if ((vectSize % 2) != 0) //如果元素个数为奇数，就把再最后一个节点push_back一次{node_vector.push_back(node_vector.end()[-1]); vectSize++;}return vectSize;}void tree::printTreeLevel(vector<node*> v) {for (node* el : v){cout << el->getHash() << endl;}cout << endl;}void tree::buildTree() //建造merkle tree{do{vector<node*> new_nodes;makeBinary(base.end()[-1]); //传入尾元素 即一个节点列表for (int i = 0; i < base.end()[-1].size(); i += 2){node* new_parent = new node; //设置父亲节点 传入最后一个元素 即一个节点列表的第i和i+1个base.end()[-1][i]->setParent(new_parent);base.end()[-1][i + 1]->setParent(new_parent);//通过两个孩子节点的哈希值设置父节点哈希值new_parent->setHash(base.end()[-1][i]->getHash() + base.end()[-1][i + 1]->getHash());//将该父节点的左右孩子节点设置为这两个new_parent->setChildren(base.end()[-1][i], base.end()[-1][i + 1]);//将new_parent压入new_nodesnew_nodes.push_back(new_parent);cout << "将 " << base.end()[-1][i]->getHash() << " 和 " << base.end()[-1][i + 1]->getHash() << " 连接,得到对应父节点的哈希值 " << endl;}cout << endl;cout << "得到的对应父节点的哈希值:" << endl;printTreeLevel(new_nodes);base.push_back(new_nodes); //将新一轮的父节点new_nodes压入basecout << "该层的结点有 " << base.end()[-1].size() << " 个:" << endl;} while (base.end()[-1].size() > 1); //这样每一轮得到新一层的父节点，知道得到根节点 退出循环merkleRoot = base.end()[-1][0]->getHash(); //根节点的哈希值cout << "Merkle Root : " << merkleRoot << endl << endl;}void tree::buildBaseLeafes(vector<string> base_leafs) //建立叶子节点列表{vector<node*> new_nodes;cout << "叶子结点及对应的哈希值: " << endl;for (auto leaf : base_leafs) //给每一个字符串创建对应节点，并通过这个字符串设置哈希值{node* new_node = new node;new_node->setHash(leaf);cout << leaf << ":" << new_node->getHash() << endl;new_nodes.push_back(new_node);}base.push_back(new_nodes);cout << endl;}int tree::verify(string hash){node* el_node = nullptr;string act_hash = hash; for (int i = 0; i < base[0].size(); i++){if (base[0][i]->getHash() == hash){el_node = base[0][i];}}if (el_node == nullptr){return 0;}cout << "使用到的哈希值:" << endl;cout << act_hash << endl;do//验证merkle tree是否改变过 {//父节点的哈希是左孩子的哈希string+右孩子的哈希string//如果el_node的父节点的左节点是el_nodeif (el_node->checkDir() == 0){//是左孩子就 做孩子的哈希string+右孩子的哈希stringact_hash = sha2::hash256_hex_string(act_hash + el_node->getSibling()->getHash());}else{act_hash = sha2::hash256_hex_string(el_node->getSibling()->getHash() + act_hash);}std::cout << act_hash << endl;el_node = el_node->getParent();} while ((el_node->getParent()) != NULL); //到达根节点return act_hash == merkleRoot ? 1 : 0;}tree::~tree() {}

4.主函数main.cpp

#include #include "tree.h"#include "sha256.h"using namespace std;int main(){string check_str = "";cout << "输入 Merkle Tree的叶子结点的数据，以‘;’作为结束符: " << endl;vector<string> v; while (1) //输入叶子节点{string str;cin >> str;if (str != ";"){v.push_back(str);}else{break;}}tree ntree;ntree.buildBaseLeafes(v);cout << "构建Merkle树过程:" << endl << endl;ntree.buildTree();cout << endl;cout << "想验证的数据: " << endl;cin >> check_str; //输入想验证的叶子节点check_str = sha2::hash256_hex_string(check_str);cout << "想验证的数据的哈希值: " << check_str << endl;if (ntree.verify(check_str))//验证有无这个节点 树有无改变{cout << endl << endl;cout << "Merkle树上存在验证的数据的叶子结点" << endl;}else{cout << "Merkle树上不存在验证的数据" << endl;}return 0;}

写在最后

以上为使用C++构建Merkle Tree的相关代码，仅供学习参考，如有相关专业问题请在评论区留言。