1. Merkle樹簡(jiǎn)介

??如上圖所示,Merkle 樹的葉子節(jié)點(diǎn)為交易序列,對(duì)每一筆交易進(jìn)行 Hash(SHA 256算法) 之后,然后對(duì)得到的 Hash 節(jié)點(diǎn)進(jìn)行拼接再次進(jìn)行 Hash 運(yùn)算,如此遞歸直到遞歸至根節(jié)點(diǎn)。

??如上圖所示 Merkle 樹的優(yōu)點(diǎn)在于可快速驗(yàn)證某個(gè)區(qū)塊是否存在指定交易,如要驗(yàn)證 H k H_k Hk?是否存在于該區(qū)塊中,只要將 H L 、 H I J 、 H M N O P 、 H A B C D E F G H_L、H_{IJ}、H_{MNOP}、H_{ABCDEFG} HL?、HIJ?、HMNOP?、HABCDEFG?節(jié)點(diǎn)得到,然后從下到上不斷 Hash,最后與根節(jié)點(diǎn)的 Hash 值進(jìn)行比較,就可以快速判斷交易是否在該區(qū)塊中。
2. 構(gòu)建Merkle樹
- 頭文件及Merkle節(jié)點(diǎn)類型
# include <iostream>
# include <functional>
# include<string>
using namespace std;
typedef struct MerkleNode {
MerkleNode* Left;
MerkleNode* Middle;
MerkleNode* Right;
MerkleNode* parent;
size_t data;
};
struct MerkleTree {
MerkleNode* RootNode;
}root;
- 創(chuàng)建三叉merkle所需函數(shù)
/* 創(chuàng)建merkle樹 */
MerkleNode* queue[100000];
int front = 0, rear = 0, new_rear = 0;
int n;
// 字符串加密
size_t encrypt(string strInput)
{
hash<string> Hash;
size_t hashVal = Hash(strInput);
return hashVal;
}
// size_t轉(zhuǎn)換為字符串
string type_convert(size_t input)
{
string output = to_string(input);
return output;
}
// 字符串拼接
string concat(string one, string two,string three)
{
string output = one + two + three;
return output;
}
// 初始化葉子節(jié)點(diǎn)
void init_leaf_node(MerkleNode*& node,size_t data)
{
node = (MerkleNode*)malloc(sizeof(MerkleNode));
node->data = encrypt(type_convert(data));
node->Left = NULL;
node->Middle = NULL;
node->Right = NULL;
}
// 對(duì)最后一個(gè)節(jié)點(diǎn)進(jìn)行拷貝
MerkleNode* copy_node(MerkleNode* node)
{
MerkleNode* new_node = (MerkleNode*)malloc(sizeof(MerkleNode));
new_node->Left = NULL;
new_node->Middle = NULL;
new_node->Right = NULL;
new_node->data = node->data;
return new_node;
}
// 初始化分枝節(jié)點(diǎn)
void init_branch_node(MerkleNode* Left, MerkleNode* Middle, MerkleNode* Right)
{
MerkleNode* node = (MerkleNode*)malloc(sizeof(MerkleNode));
node->Left = Left;
node->Middle = Middle;
node->Right = Right;
Left->parent = node;
Middle->parent = node;
Right->parent = node;
node->data = encrypt(concat(type_convert(Left->data), type_convert(Middle->data), type_convert(Right->data)));
queue[new_rear++] = node;
}
// 根據(jù)隊(duì)列中的節(jié)點(diǎn)生成其父節(jié)點(diǎn)
void create_new_layer()
{
// 補(bǔ)足剩余節(jié)點(diǎn)
int remainder = rear % 3;
int res = 0;
if (remainder != 0)
{
res = 3 - remainder;
MerkleNode* node = queue[rear - 1];
for (int i = 0; i < res; i++)
{
queue[rear++] = copy_node(node);
}
}
int loop = (rear + res) / 3;
for (int i = 0; i < loop; i++)
{
MerkleNode* Left = queue[front++];
MerkleNode* Middle = queue[front++];
MerkleNode* Right = queue[front++];
init_branch_node(Left, Middle, Right);
}
rear = new_rear;
new_rear = 0;
front = 0;
}
// 創(chuàng)建merkle樹
void create_merkle_tree(MerkleTree*& root)
{
while (rear != 1)
{
create_new_layer();
}
root = (MerkleTree*)malloc(sizeof(MerkleTree));
root->RootNode = queue[rear-1];
root->RootNode->parent = NULL;
}
// 輸入數(shù)據(jù)
void init_data()
{
cout << "請(qǐng)輸入交易序列個(gè)數(shù):";
cin >> n;
cout << "請(qǐng)輸入每一筆交易(中間以空格隔開):";
for (int i = 0; i < n; i++)
{
MerkleNode* node;
size_t data;
cin >> data;
init_leaf_node(node, data);
queue[rear++] = node;
}
}
3. 生成SPV路徑
SPV路徑生成代碼:
/* 生成SPV路徑 */
size_t spv_queue[100010];
MerkleNode *sequence[100010];
int seq_front = 0, seq_rear = 0;
int spv_front = 0,spv_rear = 0;
int spv_flag[100010], flag_idx = 0;
void init_all_node_sequence(MerkleNode* node)
{
sequence[++seq_rear] = node;
while (seq_front != seq_rear)
{
MerkleNode* new_node = sequence[++seq_front];
if (new_node->Left != NULL)
{
sequence[++seq_rear] = new_node->Left;
}
if (new_node->Middle != NULL)
{
sequence[++seq_rear] = new_node->Middle;
}
if (new_node->Right != NULL)
{
sequence[++seq_rear] = new_node->Right;
}
}
seq_front = 0;
}
void init_spv_path(int idx,MerkleTree *root)
{
MerkleNode* head_node = root->RootNode;
init_all_node_sequence(head_node);
int cnt;
if (n % 3 == 0)
{
cnt = 3;
}
else if((n + 1) % 3 == 0) {
cnt = n + 1;
}
else {
cnt = n + 2;
}
int seq_idx = seq_rear - (cnt - idx);
cout << "該交易的哈希值為:" << sequence[seq_idx]->data<< endl;
MerkleNode* node = sequence[seq_idx];
while (node->parent)
{
MerkleNode* parent = node->parent;
if (node == parent->Left)
{
spv_flag[flag_idx++] = 0;
spv_queue[++spv_rear] = parent->Middle->data;
spv_queue[++spv_rear] = parent->Right->data;
}
else if (node == parent->Middle)
{
spv_flag[flag_idx++] = 1;
spv_queue[++spv_rear] = parent->Left->data;
spv_queue[++spv_rear] = parent->Right->data;
}
else {
spv_flag[flag_idx++] = 2;
spv_queue[++spv_rear] = parent->Left->data;
spv_queue[++spv_rear] = parent->Middle->data;
}
node = node->parent;
}
}
void print_spv_path(int idx)
{
cout << "交易序列號(hào)" << idx << "的SPV路徑為:";
while (spv_front != spv_rear)
{
cout << spv_queue[++spv_front] << " ";
}
cout << endl;
spv_front = 0;
cout << "生成交易在其兄弟節(jié)點(diǎn)中的位置序列為(0為L(zhǎng)eft,1為Middle,2為Right):";
for (int i = 0; i < flag_idx; i++)
{
cout << spv_flag[i] << " ";
}
}
4. 驗(yàn)證SPV路徑
SPV路徑驗(yàn)證代碼:文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-850560.html
/* 驗(yàn)證SPV路徑 */
size_t root_hash, spv_path[1010], hash_val;
int spv_length;
void judge_spv_path()
{
cout << "請(qǐng)輸入merkle樹根節(jié)點(diǎn)哈希值:";
cin >> root_hash;
cout << "請(qǐng)輸入SPV路徑長(zhǎng)度:";
cin >> spv_length;
cout << "請(qǐng)輸入SPV路徑(中間用空格隔開):";
for (int i = 0; i < spv_length; i++)
{
cin >> spv_path[i];
}
int pos_cnt, pos_sqe[100010];
cout << "請(qǐng)輸入交易位置序列個(gè)數(shù):";
cin >> pos_cnt;
cout << "請(qǐng)輸入交易位置序列(中間用空格隔開):";
for (int i = 0; i < pos_cnt; i++)
{
cin >> pos_sqe[i];
}
cout << "請(qǐng)輸入要查詢的交易哈希值:";
cin >> hash_val;
int path_idx = 0, pos_idx = 0;
while (path_idx != spv_length)
{
size_t one = spv_path[path_idx++];
size_t two = spv_path[path_idx++];
if (pos_sqe[pos_idx] == 0)
{
hash_val = encrypt(concat(type_convert(hash_val), type_convert(one), type_convert(two)));
}
else if (pos_sqe[pos_idx] == 1)
{
hash_val = encrypt(concat(type_convert(one), type_convert(hash_val), type_convert(two)));
}
else {
hash_val = encrypt(concat(type_convert(one), type_convert(two), type_convert(hash_val)));
}
pos_idx++;
}
cout << "SPV計(jì)算得到的哈希值為:" << hash_val <<endl;
cout << "頭節(jié)點(diǎn)哈希值為:" << root_hash << endl;
if (hash_val == root_hash)
{
cout << "SPV路徑驗(yàn)證成功?。?!" << endl << endl << endl;
}
}
5. 三叉Merkle樹創(chuàng)建、SPV生成及驗(yàn)證總程序
# define _CRT_SECURE_NO_DEPRECATE
# include <iostream>
# include <functional>
# include<string>
using namespace std;
typedef struct MerkleNode {
MerkleNode* Left;
MerkleNode* Middle;
MerkleNode* Right;
MerkleNode* parent;
size_t data;
};
struct MerkleTree {
MerkleNode* RootNode;
}root;
/* 創(chuàng)建merkle樹 */
MerkleNode* queue[100000];
int front = 0, rear = 0, new_rear = 0;
int n;
// 字符串加密
size_t encrypt(string strInput)
{
hash<string> Hash;
size_t hashVal = Hash(strInput);
return hashVal;
}
// size_t轉(zhuǎn)換為字符串
string type_convert(size_t input)
{
string output = to_string(input);
return output;
}
// 字符串拼接
string concat(string one, string two,string three)
{
string output = one + two + three;
return output;
}
// 初始化葉子節(jié)點(diǎn)
void init_leaf_node(MerkleNode*& node,size_t data)
{
node = (MerkleNode*)malloc(sizeof(MerkleNode));
node->data = encrypt(type_convert(data));
node->Left = NULL;
node->Middle = NULL;
node->Right = NULL;
}
// 對(duì)最后一個(gè)節(jié)點(diǎn)進(jìn)行拷貝
MerkleNode* copy_node(MerkleNode* node)
{
MerkleNode* new_node = (MerkleNode*)malloc(sizeof(MerkleNode));
new_node->Left = NULL;
new_node->Middle = NULL;
new_node->Right = NULL;
new_node->data = node->data;
return new_node;
}
// 初始化分枝節(jié)點(diǎn)
void init_branch_node(MerkleNode* Left, MerkleNode* Middle, MerkleNode* Right)
{
MerkleNode* node = (MerkleNode*)malloc(sizeof(MerkleNode));
node->Left = Left;
node->Middle = Middle;
node->Right = Right;
Left->parent = node;
Middle->parent = node;
Right->parent = node;
node->data = encrypt(concat(type_convert(Left->data), type_convert(Middle->data), type_convert(Right->data)));
queue[new_rear++] = node;
}
// 根據(jù)隊(duì)列中的節(jié)點(diǎn)生成其父節(jié)點(diǎn)
void create_new_layer()
{
// 補(bǔ)足剩余節(jié)點(diǎn)
int remainder = rear % 3;
int res = 0;
if (remainder != 0)
{
res = 3 - remainder;
MerkleNode* node = queue[rear - 1];
for (int i = 0; i < res; i++)
{
queue[rear++] = copy_node(node);
}
}
int loop = (rear + res) / 3;
for (int i = 0; i < loop; i++)
{
MerkleNode* Left = queue[front++];
MerkleNode* Middle = queue[front++];
MerkleNode* Right = queue[front++];
init_branch_node(Left, Middle, Right);
}
rear = new_rear;
new_rear = 0;
front = 0;
}
// 創(chuàng)建merkle樹
void create_merkle_tree(MerkleTree*& root)
{
while (rear != 1)
{
create_new_layer();
}
root = (MerkleTree*)malloc(sizeof(MerkleTree));
root->RootNode = queue[rear-1];
root->RootNode->parent = NULL;
}
// 輸入數(shù)據(jù)
void init_data()
{
cout << "請(qǐng)輸入交易序列個(gè)數(shù):";
cin >> n;
cout << "請(qǐng)輸入每一筆交易(中間以空格隔開):";
for (int i = 0; i < n; i++)
{
MerkleNode* node;
size_t data;
cin >> data;
init_leaf_node(node, data);
queue[rear++] = node;
}
}
/* 生成SPV路徑 */
size_t spv_queue[100010];
MerkleNode *sequence[100010];
int seq_front = 0, seq_rear = 0;
int spv_front = 0,spv_rear = 0;
int spv_flag[100010], flag_idx = 0;
void init_all_node_sequence(MerkleNode* node)
{
sequence[++seq_rear] = node;
while (seq_front != seq_rear)
{
MerkleNode* new_node = sequence[++seq_front];
if (new_node->Left != NULL)
{
sequence[++seq_rear] = new_node->Left;
}
if (new_node->Middle != NULL)
{
sequence[++seq_rear] = new_node->Middle;
}
if (new_node->Right != NULL)
{
sequence[++seq_rear] = new_node->Right;
}
}
seq_front = 0;
}
void init_spv_path(int idx,MerkleTree *root)
{
MerkleNode* head_node = root->RootNode;
init_all_node_sequence(head_node);
int cnt;
if (n % 3 == 0)
{
cnt = 3;
}
else if((n + 1) % 3 == 0) {
cnt = n + 1;
}
else {
cnt = n + 2;
}
int seq_idx = seq_rear - (cnt - idx);
cout << "該交易的哈希值為:" << sequence[seq_idx]->data<< endl;
MerkleNode* node = sequence[seq_idx];
while (node->parent)
{
MerkleNode* parent = node->parent;
if (node == parent->Left)
{
spv_flag[flag_idx++] = 0;
spv_queue[++spv_rear] = parent->Middle->data;
spv_queue[++spv_rear] = parent->Right->data;
}
else if (node == parent->Middle)
{
spv_flag[flag_idx++] = 1;
spv_queue[++spv_rear] = parent->Left->data;
spv_queue[++spv_rear] = parent->Right->data;
}
else {
spv_flag[flag_idx++] = 2;
spv_queue[++spv_rear] = parent->Left->data;
spv_queue[++spv_rear] = parent->Middle->data;
}
node = node->parent;
}
}
void print_spv_path(int idx)
{
cout << "交易序列號(hào)" << idx << "的SPV路徑為:";
while (spv_front != spv_rear)
{
cout << spv_queue[++spv_front] << " ";
}
cout << endl;
spv_front = 0;
cout << "生成交易在其兄弟節(jié)點(diǎn)中的位置序列為(0為L(zhǎng)eft,1為Middle,2為Right):";
for (int i = 0; i < flag_idx; i++)
{
cout << spv_flag[i] << " ";
}
}
/* 驗(yàn)證SPV路徑 */
size_t root_hash, spv_path[1010], hash_val;
int spv_length;
void judge_spv_path()
{
cout << "請(qǐng)輸入merkle樹根節(jié)點(diǎn)哈希值:";
cin >> root_hash;
cout << "請(qǐng)輸入SPV路徑長(zhǎng)度:";
cin >> spv_length;
cout << "請(qǐng)輸入SPV路徑(中間用空格隔開):";
for (int i = 0; i < spv_length; i++)
{
cin >> spv_path[i];
}
int pos_cnt, pos_sqe[100010];
cout << "請(qǐng)輸入交易位置序列個(gè)數(shù):";
cin >> pos_cnt;
cout << "請(qǐng)輸入交易位置序列(中間用空格隔開):";
for (int i = 0; i < pos_cnt; i++)
{
cin >> pos_sqe[i];
}
cout << "請(qǐng)輸入要查詢的交易哈希值:";
cin >> hash_val;
int path_idx = 0, pos_idx = 0;
while (path_idx != spv_length)
{
size_t one = spv_path[path_idx++];
size_t two = spv_path[path_idx++];
if (pos_sqe[pos_idx] == 0)
{
hash_val = encrypt(concat(type_convert(hash_val), type_convert(one), type_convert(two)));
}
else if (pos_sqe[pos_idx] == 1)
{
hash_val = encrypt(concat(type_convert(one), type_convert(hash_val), type_convert(two)));
}
else {
hash_val = encrypt(concat(type_convert(one), type_convert(two), type_convert(hash_val)));
}
pos_idx++;
}
cout << "SPV計(jì)算得到的哈希值為:" << hash_val <<endl;
cout << "頭節(jié)點(diǎn)哈希值為:" << root_hash << endl;
if (hash_val == root_hash)
{
cout << "SPV路徑驗(yàn)證成功?。?!" << endl << endl << endl;
}
}
int main()
{
cout << "================================================ Merkle樹構(gòu)建部分 ===================================================" << endl << endl;
init_data(); // 數(shù)據(jù)初始化(輸入相關(guān)數(shù)據(jù))
// 生成 Merkle 樹
MerkleTree* root;
create_merkle_tree(root);
cout << "merkle樹根哈希值為:" << root->RootNode->data << endl;
cout << "merkle樹構(gòu)建完成!" << endl << endl << endl;
// 生成SPV路徑
cout << "================================================ SPV路徑生成部分 ===================================================" << endl << endl;
int idx;
cout << "請(qǐng)輸入交易序號(hào)(i):";
cin >> idx;
init_spv_path(idx, root);
print_spv_path(idx);
cout << endl << endl << endl;
// 驗(yàn)證SPV路徑
cout << "================================================ SPV路徑驗(yàn)證部分 ===================================================" << endl << endl;
judge_spv_path();
return 0;
}
6. 程序運(yùn)行結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-850560.html
到了這里,關(guān)于【區(qū)塊鏈】C語(yǔ)言編程實(shí)現(xiàn)三叉Merkle樹的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!