Merkle tree existential function modified for the first time

Merkle Tree The existential function is modified for the first time

Blockchain learning notes （ Two ）

---

Determine whether a certain data is on the tree

How to verify that a certain data is on the tree , You can build a tree by , Sort the hash values before building .
If some data is in the leaves , Then connect the hash value of the corresponding sibling node with its own hash value , Then get the new hash value through the hash algorithm , And so on , Finally, we get a hash value without siblings , Compare it with the root , If the same , Then it proves that the data exists .
If some data is not in the leaves , By comparing the size of the hash value , Then get the hash value of two adjacent nodes of the hash value corresponding to the data , Prove that these two hash values are adjacent in the tree .
（ It is more convincing than simple traversal ）

---

The relevant code implementation is as follows ：

void tree::buildBaseLeafes(vector<string> base_leafs) // Create a leaf node list 
{
    
	cout << " The hash value corresponding to the data : " << 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 << " After the hash value is sorted :" << 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) // Create corresponding nodes for each string , And set the hash value through this string 
	{
    
		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; // The hash value of the leaf node you want to verify 
	int t = 0;

	// If base[0]  That is, there is one node in the leaf node hash Value is equal to it 
	for (int i = 0; i < base[0].size(); i++)
	{
    
		if (base[0][i]->getHash() == act_hash)
		{
    
			el_node = base[0][i];// Point to the node 
			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 << " The hash value used :" << endl;
		cout << endl;
		cout << " Leaf nodes adjacent to hash values :" << endl;
		cout << el_node_t_1->getHash() << endl;
		cout << el_node_t_2->getHash() << endl;
		cout << endl;
		if (t % 2 == 0) {
    
			cout << " The node where the above two hash values are located has the same parent node ..." << 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 << " The node where the above two hash values are located does not have the same parent node ..." << endl;
			string act_hash_t_1 = el_node_t_1->getHash();
			string act_hash_t_2 = el_node_t_2->getHash();
			int cor = 0;// Judge whether the two nodes converge to the same parent node 
			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 << " The hash value used :" << endl;
		cout << act_hash << endl;

		do  // verification merkle tree Have you changed  
		{
    
			// The hash of the parent node is the hash of the left child string+ Hash of right child string
			// If el_node The left node of the parent node of is el_node
			if (el_node->checkDir() == 0)
			{
    
				// It's the left child   Left child's hash string+ Hash of right child 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); // Reach the root node 

		return act_hash == merkleRoot ? 1 : 0;
	}
}

---

At the end

Tips ： Please refer to the previous article for the source code ： Merkle Tree structure （C++ Realization ）

This code is for reference only , If you have any professional questions, please leave a message in the comment area .