用C++代码实现Merkle树

Merkle树，也称为哈希树或证书链树，是一种数据结构，常用于数字签名、内容寻址存储等场景，通过构建一棵由节点组成的树，每个内部节点是其两个子节点的哈希值，顶层节点即根节点通常代表整个数据集的摘要。以下是使用C++简单实现Merkle树的一个示例：

#include <openssl/sha.h>
#include <vector>

// 哈希函数
std::string hash(const std::string& data) {
    unsigned char hash[SHA256_DIGEST_LENGTH];
    SHA256((unsigned char*)data.c_str(), data.size(), hash);
    std::stringstream ss;
    for (int i = 0; i < SHA256_DIGEST_LENGTH; ++i) {
        ss << std::hex << static_cast<int>(hash[i]);
    }
    return ss.str();
}

// 构建Merkle树节点
struct MerkleNode {
    std::string value;
    std::string hash;
    MerkleNode* left;
    MerkleNode* right;
};

// 创建一个新的MerkleNode
MerkleNode* create_node(const std::string& value) {
    MerkleNode* node = new MerkleNode();
    node->value = value;
    node->hash = hash(value);
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

// 合并两个节点到新的MerkleNode
MerkleNode* combine_nodes(MerkleNode* a, MerkleNode* b) {
    if (!a || !b) return a ? a : b;
    return new MerkleNode{
        .value = "",
        .hash = hash(a->hash + b->hash),
        .left = combine_nodes(a->left, b->left),
        .right = combine_nodes(a->right, b->right)
    };
}

// 构建Merkle树
MerkleNode* build_merkle_tree(const std::vector<std::string>& values) {
    std::vector<MerkleNode*> nodes;
    for (const auto& value : values) {
        nodes.push_back(create_node(value));
    }

    while (nodes.size() > 1) {
        size_t size = nodes.size();
        nodes.resize(size / 2);

        for (size_t i = 0; i < size; i += 2) {
            nodes.push_back(combine_nodes(nodes[i], nodes[i + 1]));
        }
    }

    return nodes.empty() ? nullptr : nodes[0]; // 根节点
}

在这个例子中，`build_merkle_tree`函数接收一个字符串向量作为输入，递归地合并节点直到只剩下一个根节点。