cpp 区块链模拟示例(七) 补充 Merkle树

Merkle 树

完整的比特币数据库(也就是区块链)需要超过 140 Gb 的磁盘空间。因为比特币的去中心化特性,网络中的每个节点必须是独立,自给自足的,也就是每个节点必须存储一个区块链的完整副本。随着越来越多的人使用比特币,这条规则变得越来越难以遵守:因为不太可能每个人都去运行一个全节点。并且,由于节点是网络中的完全参与者,它们负有相关责任:节点必须验证交易和区块。另外,要想与其他节点交互和下载新块,也有一定的网络流量需求。

在中本聪的 比特币原始论文 中,对这个问题也有一个解决方案:简易支付验证(Simplified Payment Verification, SPV)。SPV 是一个比特币轻节点,它不需要下载整个区块链,也不需要验证区块和交易。相反,它会在区块链查找交易(为了验证支付),并且需要连接到一个全节点来检索必要的数据。这个机制允许在仅运行一个全节点的情况下有多个轻钱包。

为了实现 SPV,需要有一个方式来检查是否一个区块包含了某笔交易,而无须下载整个区块。这就是 Merkle 树所要完成的事情。

比特币用 Merkle 树来获取交易哈希,哈希被保存在区块头中,并会用于工作量证明系统。到目前为止,我们只是将一个块里面的每笔交易哈希连接了起来,将在上面应用了 SHA-256 算法。虽然这是一个用于获取区块交易唯一表示的一个不错的途径,但是它没有利用到 Merkle 树。

来看一下 Merkle 树:

cpp 区块链模拟示例(七) 补充 Merkle树

每个块都会有一个 Merkle 树,它从叶子节点(树的底部)开始,一个叶子节点就是一个交易哈希(比特币使用双 SHA256 哈希)。叶子节点的数量必须是双数,但是并非每个块都包含了双数的交易。因为,如果一个块里面的交易数为单数,那么就将最后一个叶子节点(也就是 Merkle 树的最后一个交易,不是区块的最后一笔交易)复制一份凑成双数。

从下往上,两两成对,连接两个节点哈希,将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程,直到仅有一个节点,也就是树根。根哈希然后就会当做是整个块交易的唯一标示,将它保存到区块头,然后用于工作量证明。

Merkle 树的好处就是一个节点可以在不下载整个块的情况下,验证是否包含某笔交易。并且这些只需要一个交易哈希,一个 Merkle 树根哈希和一个 Merkle 路径。

最后,来写代码:

 package main

 import (
"crypto/sha256"
"fmt"
"encoding/hex"
) type MerkleTree struct{
RootNode * MerkleNode
} type MerkleNode struct{
Left *MerkleNode
Right *MerkleNode
Data []byte
} func NewMerkleTree(data [][]byte) * MerkleTree{
var nodes []MerkleNode
if len(data)% != {
data = append(data,data[len(data)-])
} for _,datum := range data{
node := NewMerkleNode(nil,nil,datum)
nodes = append(nodes,*node)
} for i := ;i < len(data)/;i++{
var newLevel []MerkleNode for j := ;j < len(nodes);j += {
node := NewMerkleNode(&nodes[j],&nodes[j+],nil)
newLevel = append(newLevel,*node)
}
nodes = newLevel
} mTree := MerkleTree{&nodes[]}
return &mTree
} func NewMerkleNode(left,right *MerkleNode,data []byte)*MerkleNode{
mNode := MerkleNode{} if left == nil && right == nil{
hash := sha256.Sum256(data)
mNode.Data = hash[:]
}else{
prevHashes := append(left.Data,right.Data...)
hash := sha256.Sum256(prevHashes)
mNode.Data = hash[:]
} mNode.Left = left
mNode.Right = right return &mNode
}
//============================================================== func testNewMerkleNode1(){
data := [][]byte{
[]byte("node1"),
[]byte("node2"),
[]byte("node3"),
} n1 := NewMerkleNode(nil,nil,data[])
n2 := NewMerkleNode(nil,nil,data[])
n3 := NewMerkleNode(nil,nil,data[])
n4 := NewMerkleNode(nil,nil,data[]) n5 := NewMerkleNode(n1,n2,nil)
n6 := NewMerkleNode(n3,n4,nil) n7 := NewMerkleNode(n5,n6,nil) fmt.Println("n5 = ",hex.EncodeToString(n5.Data))
fmt.Println("n6 = ",hex.EncodeToString(n6.Data))
fmt.Println("n7 = ",hex.EncodeToString(n7.Data))
} func testNewMerkleNode2(){
data := [][]byte{
[]byte("node1"),
[]byte("node2"),
[]byte("node3"),
}
// Level 1
n1 := NewMerkleNode(nil, nil, data[])
n2 := NewMerkleNode(nil, nil, data[])
n3 := NewMerkleNode(nil, nil, data[])
n4 := NewMerkleNode(nil, nil, data[]) // Level 2
n5 := NewMerkleNode(n1, n2, nil)
n6 := NewMerkleNode(n3, n4, nil) // Level 3
n7 := NewMerkleNode(n5, n6, nil) rootHash := fmt.Sprintf("%x", n7.Data)
mTree := NewMerkleTree(data) fmt.Println("roothash =\t",(rootHash))
fmt.Println("mTree =\t\t",hex.EncodeToString(mTree.RootNode.Data))
} func main() {
testNewMerkleNode1()
testNewMerkleNode2()
}

Merkle_go

c++需要导入之前的sha256  https://www.cnblogs.com/itdef/p/9435218.html

sha256.cpp    sha256.h

 // 1111.cpp: 定义控制台应用程序的入口点。
// #include "sha256.h"
#include <string>
#include <vector>
#include <iostream> using namespace std; typedef struct merklenode {
struct merklenode* left;
struct merklenode* right;
string data;
}MerkleNode; typedef struct merkletree {
MerkleNode* merkleNode;
}MerkleTree; MerkleNode* NewMerkleNode(MerkleNode* left, MerkleNode* right, string data) {
MerkleNode* mNode = new MerkleNode{}; if (left == nullptr && right == nullptr) {
string hash = sha256(data);
mNode->data = hash;
}
else {
string prevHashes = left->data + right->data;
string hash = sha256(prevHashes);
mNode->data = hash;
} mNode->left = left;
mNode->right = right; return mNode;
} MerkleTree* NewMerkleTree(vector<string> data) {
vector<MerkleNode*> nodes; if ((data.size() % ) != ) {
data.push_back(data[data.size() - ]);
} for (const auto& datum : data) {
MerkleNode* node = NewMerkleNode(nullptr, nullptr, datum);
nodes.push_back(node);
} for (int i = ; i < (data.size() / ); i++) {
vector<MerkleNode*> newLevel; for (int j = ; j < nodes.size(); j += ) {
MerkleNode* node = NewMerkleNode(nodes[j], nodes[j + ], "");
newLevel.push_back(node);
}
nodes = newLevel;
} MerkleTree* mTree = new MerkleTree{ nodes[] };
return mTree;
} void testNewMerkleNode1() {
vector<string> data{ "node1","node2","node3" }; MerkleNode* n1 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n2 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n3 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n4 = NewMerkleNode(nullptr, nullptr, data[]); MerkleNode* n5 = NewMerkleNode(n1, n2, "");
MerkleNode* n6 = NewMerkleNode(n3, n4, ""); MerkleNode* n7 = NewMerkleNode(n5, n6, ""); std::cout << "n5 = " << n5->data << std::endl;
std::cout << "n6 = " << n6->data << std::endl;
std::cout << "n7 = " << n7->data << std::endl;
} void testNewMerkleNode2() {
vector<string> data{ "node1","node2","node3" }; MerkleNode* n1 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n2 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n3 = NewMerkleNode(nullptr, nullptr, data[]);
MerkleNode* n4 = NewMerkleNode(nullptr, nullptr, data[]); MerkleNode* n5 = NewMerkleNode(n1, n2, "");
MerkleNode* n6 = NewMerkleNode(n3, n4, ""); MerkleNode* n7 = NewMerkleNode(n5, n6, ""); MerkleTree* mTree = NewMerkleTree(data); std::cout << "roothash = "<< n7->data << std::endl;
std::cout << "mTree = " << mTree->merkleNode->data << std::endl; } int main()
{
testNewMerkleNode1();
testNewMerkleNode2();
return ;
}

Merkle_cpp

参考

https://blog.csdn.net/simple_the_best/article/details/78462129

上一篇:cpp 区块链模拟示例(六) 交易


下一篇:cpp 区块链模拟示例(五) 序列化