[C++知识库]Merkle Tree 构建（C++实现）

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.<node.h>

#pragma once
#include <iostream>
#include <sstream>
#include "sha256.h"
#include <string>
#include <vector>
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 否则则返回1
	return parent->getChildren(0) == this ? 0 : 1;
}

node::~node() {}

2.<sha256.h>

#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 <algorithm>
#include <cassert>
#include <iterator>
#include <sstream>
#include <vector>

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.<tree.h>

#pragma once
#include "node.h"
#include <iostream>
#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_nodes
			new_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压入base

		cout << "该层的结点有 " << 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_node
		if (el_node->checkDir() == 0)
		{
			//是左孩子就 做孩子的哈希string+右孩子的哈希string
			act_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 <iostream>
#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的相关代码，仅供学习参考，如有相关专业问题请在评论区留言。