Merkle Tree 存在性功能第一次修改

区块链学习笔记（二）

---

判断某个数据是否在树上

如何验证某个数据在树上，可以通过构建树的时候，将哈希值进行排序后再构建。
如果某个数据在树叶中，则通过把相应的兄弟结点的哈希值与自身的哈希值连接，再通过哈希算法得到新的哈希值，以此类推，最终得到一个没有兄弟结点的哈希值，将其与树根比对，如果一样，则证明该数据存在。
如果某个数据不在树叶中，则通过比较哈希值大小，进而得到该数据所对应的哈希值的相邻的两个节点的哈希值，证明这两个哈希值在树中相邻即可。
（与简单的遍历相比更具说服力）

---

相关代码实现如下：

void tree::buildBaseLeafes(vector<string> base_leafs) //建立叶子节点列表
{
    
	cout << "数据对应的哈希值: " << endl;
	for (int i = 0; i < base_leafs.size(); i++) {
    
		cout << base_leafs[i] << " : ";
		base_leafs[i] = sha256::hash256_hex_string(base_leafs[i]);
		cout << base_leafs[i] << endl;
	}
	cout << endl << endl;

	sort(base_leafs.begin(), base_leafs.end());
	cout << "哈希值排序后:" << endl;
	for (int i = 0; i < base_leafs.size(); i++) {
    
		cout << base_leafs[i] << endl;
	}
	cout << endl << endl;

	vector<node*> new_nodes;

	for (auto leaf : base_leafs) //给每一个字符串创建对应节点，并通过这个字符串设置哈希值
	{
    
		node* new_node = new node;
		new_node->setHash(leaf);
		new_nodes.push_back(new_node);
	}

	base.push_back(new_nodes);
	cout << endl;
}

int tree::verify(string hash)
{
    
	node* el_node = nullptr;
	node* el_node_t_1 = nullptr;
	node* el_node_t_2 = nullptr;
	string act_hash = hash; //想验证的叶子节点的哈希值
	int t = 0;

	//如果base[0] 即叶子节点中有一个节点的hash值和其相等
	for (int i = 0; i < base[0].size(); i++)
	{
    
		if (base[0][i]->getHash() == act_hash)
		{
    
			el_node = base[0][i];//指向该节点
			break;
		}
		if (i < base[0].size() - 1) {
    
			if (act_hash > base[0][i]->getHash() && act_hash < base[0][i + 1]->getHash()) {
    
				el_node_t_1 = base[0][i];
				el_node_t_2 = base[0][i + 1];
				t = i;
			}
		}
	}
	if (el_node == nullptr)
	{
    
		cout << endl;
		cout << "使用到的哈希值:" << endl;
		cout << endl;
		cout << "哈希值相邻的叶子节点:" << endl;
		cout << el_node_t_1->getHash() << endl;
		cout << el_node_t_2->getHash() << endl;
		cout << endl;
		if (t % 2 == 0) {
    
			cout << "以上两个哈希值所在节点有同一个父节点..." << endl;
			el_node_t_1 = el_node_t_1->getParent();
			do {
    
				if (el_node_t_1->checkDir() == 0)
				{
    
					std::cout << el_node_t_1->getSibling()->getHash() << endl;
				}
				else
				{
    
					std::cout << el_node_t_1->getSibling()->getHash() << endl;
				}

				el_node_t_1 = el_node_t_1->getParent();
			} while ((el_node_t_1->getParent()) != NULL);
		}
		else {
    
			cout << "以上两个哈希值所在节点没有相同的父节点..." << endl;
			string act_hash_t_1 = el_node_t_1->getHash();
			string act_hash_t_2 = el_node_t_2->getHash();
			int cor = 0;//判断两个节点是否汇合到同一个父节点
			if (el_node_t_1->checkDir() == 0)
			{
    
				act_hash_t_1 = sha256::hash256_hex_string(act_hash_t_1 + el_node_t_1->getSibling()->getHash());
			}
			else
			{
    
				act_hash_t_1 = sha256::hash256_hex_string(el_node_t_1->getSibling()->getHash() + act_hash_t_1);
			}

			if (el_node_t_2->checkDir() == 0)
			{
    
				act_hash_t_2 = sha256::hash256_hex_string(act_hash_t_2 + el_node_t_2->getSibling()->getHash());
			}
			else
			{
    
				act_hash_t_2 = sha256::hash256_hex_string(el_node_t_2->getSibling()->getHash() + act_hash_t_2);
			}
			do {
    
				if (act_hash_t_1 != act_hash_t_2) {
    
					std::cout << el_node_t_1->getSibling()->getHash() << endl;
					el_node_t_1 = el_node_t_1->getParent();
					std::cout << el_node_t_2->getSibling()->getHash() << endl;
					el_node_t_2 = el_node_t_2->getParent();

					if (el_node_t_1->checkDir() == 0)
					{
    
						act_hash_t_1 = sha256::hash256_hex_string(act_hash_t_1 + el_node_t_1->getSibling()->getHash());
					}
					else
					{
    
						act_hash_t_1 = sha256::hash256_hex_string(el_node_t_1->getSibling()->getHash() + act_hash_t_1);
					}

					if (el_node_t_2->checkDir() == 0)
					{
    
						act_hash_t_2 = sha256::hash256_hex_string(act_hash_t_2 + el_node_t_2->getSibling()->getHash());
					}
					else
					{
    
						act_hash_t_2 = sha256::hash256_hex_string(el_node_t_2->getSibling()->getHash() + act_hash_t_2);
					}

				}
				else {
    
					cor = 1;
					el_node_t_1 = el_node_t_1->getParent();
				}
			} while ((el_node_t_1->getParent()) != NULL && cor == 0);
			do {
    
				std::cout << el_node_t_1->getSibling()->getHash() << endl;
				el_node_t_1 = el_node_t_1->getParent();
			} while ((el_node_t_1->getParent()) != NULL);
		}

		return 0;
	}

	else {
    
		cout << "使用到的哈希值:" << endl;
		cout << act_hash << endl;

		do  //验证merkle tree是否改变过 
		{
    
			//父节点的哈希是左孩子的哈希string+右孩子的哈希string
			//如果el_node的父节点的左节点是el_node
			if (el_node->checkDir() == 0)
			{
    
				//是左孩子就 左孩子的哈希string+右孩子的哈希string
				act_hash = sha256::hash256_hex_string(act_hash + el_node->getSibling()->getHash());
			}
			else
			{
    
				act_hash = sha256::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;
	}
}

---

写在最后

提示：源代码请参考前一篇文章 ： Merkle Tree 构建（C++实现）

此代码仅供学习参考，如有相关专业问题请在评论区留言。