历经五十年，默克尔树依然至高无上
- billatnapier
- 发布于 2天前
- 阅读 32
这篇文章深入探讨了默克尔树（Merkle Tree）的核心概念及其在网络安全、区块链和后量子密码学中的重要作用。文章追溯了默克尔树的发明者Ralph Merkle的贡献，并提供了一个详细的Zig语言实现示例，展示了默克尔树的构建、默克尔根的计算以及证明的生成和验证。
五十年后，Merkle Tree 依然至高无上
在过去的五十年里，我们在网络安全领域开发了许多方法，但很少有能与 Merkle Tree 的强大功能相媲美的。它是区块链的核心，并被提议作为实现 PKI (Public Key Infrastructure) 的更简化方式。虽然 RSA 和 ECC (Elliptic Curve Cryptography) 方法面临被 Shor's algorithm 破解的危险，但 Merkle Tree 基于哈希的方法依然强大且具有量子鲁棒性。
借助 Merkle Tree，Google 提议为所有有效的公钥发布一个 Merkle Root，并避免使用 X.509 证书。因此，让我们研究一下 Merkle Tree，并实现一些 Zig 代码来对其进行探索。
Ralph Merkle
我很幸运能与一些为互联网安全奠定基础的伟大人物交谈，昨天我与其中一位伟人进行了交流：Ralph C Merkle：
Ralph 是公钥密码学的共同发明人、加密哈希的发明人，创建了 Merkle 谜题，是 Merkle–Hellman 背包密码系统的共同发明人，并发明了 Merkle trees。他于 1974 年在加州大学伯克利分校获得计算机科学学士学位，并于 1979 年在斯坦福大学获得电气工程博士学位。最近，他是一名低温生物学研究员和演讲者。Ralph 曾是著名的 Xerox PARC (Palo Alto Research Center) 的研究科学家，也是 Zyvex 的纳米技术理论家。
Ralph 还曾是佐治亚理工学院的杰出教授、IMM 的高级研究员、奇点大学的教员以及 Alcor 生命延长基金会的董事会成员。1998 年，他因纳米技术理论共同获得了费曼奖。2010 年，他因发明公钥密码学而获得了 IEEE Richard W. Hamming 奖章，并于 2011 年入选国家网络安全名人堂。2020 年，他因“对公钥密码学、哈希算法、Merkle trees 和数字签名的发展做出基础贡献”而获得了 Levchin 奖。
Merkle Trees
在短短的五页中，Merkle 于 1979 年 9 月提交了他的专利，并阐述了后来成为我们所知的区块链的方法 [ 此处]：
该专利被授予斯坦福大学，其中概述了一种通过哈希树验证数据的方法，其中顶层哈希可用于验证区块内的所有数据：
在此，数据元素 Y1 和 Y2 被哈希，然后由此创建一个哈希，最终我们到达了树的顶部，在那里可以通过顶层哈希证明所有数据的有效性，并且任何更改都可以在树中快速追踪。这真是一个美丽的模式，只需说明它是什么，它就完成了。它有四个基本声明，但基本上它是围绕树的核心图形构建的。这是最美妙形式的美丽数学。它有许多核心应用，其中之一是 Bob 拥有多个私钥，这些私钥被哈希到公钥。每当 Bob 使用他的一个私钥时，他都可以向任何人展示他知道从他的私钥到他的公钥的路径——从而表明他“没有隐瞒”。
假设我们有两家银行每天处理数十亿笔交易，它们希望检查所有交易或一批交易是否已正确接收。一种方法是使用 Merkle tree（或哈希树），这是 Ralph Merkle 于 1979 年获得专利的一种方法 [ 此处]，其中每个非叶节点都是其子节点的哈希。然后，要检查所有交易，我们会计算哈希并计算一个根哈希，然后交换它。
所以假设我们有 Bob The Bank 和 Alice Online，他们之间进行交易。如果他们想在一天结束时检查他们的交易，他们可以各自通过对其子节点的哈希进行非叶节点哈希来计算哈希树：
Bob The Bank 随后会将根哈希发送给 Alice Online，Alice Online 就可以检查她是否计算出相同的值。如果他们一致，他们就拥有相同的交易集。但是，假设 Alice Online 只想搜索树的一个分支。我们可以在 Merkle trees 中通过仅将计算能力增加 log(N) 来实现这一点——其中 N 是树中节点的数量（而哈希列表会随节点数量而变化）。通过这种方式，我们可以检查交易 3 和 4 是否在树中。
记住我以便更快登录
Merkle trees 被用于许多应用程序中，包括 P2P 网络，以及比特币交易、Git 分发和 BitTorrent 协议。你还会在 Apache Cassandra 等 NoSQL 系统中找到它。另一个新应用是在后量子密码学中，例如用于 SPHINCS+。在区块链中，每个区块都包含一个 Merkle Tree 根哈希，它是该特定区块中所有交易的哈希 [ 此处]：
Zig 实现
以下代码使用 Zig 版本 0.15.1 编译，并集成了 SHA-256 哈希以生成 Merkle Tree [ 此处]：
const std = @import("std");
const MerkleTree = @import("merkle.zig");
pub const HASH_SIZE = 32;
/// Merkle tree 节点哈希类型
pub const Hash = [HASH_SIZE]u8;
pub fn main() !void {
var stdout_buffer: [4096]u8 = undefined;
var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
const stdout = &stdout_writer.interface;
const args = try std.process.argsAlloc(std.heap.page_allocator);
defer std.process.argsFree(std.heap.page_allocator, args);
var hash256_1: [std.crypto.hash.sha2.Sha256.digest_length]u8 = undefined;
var hash256_2: [std.crypto.hash.sha2.Sha256.digest_length]u8 = undefined;
var hash256_3: [std.crypto.hash.sha2.Sha256.digest_length]u8 = undefined;
var hash256_4: [std.crypto.hash.sha2.Sha256.digest_length]u8 = undefined;
std.crypto.hash.sha2.Sha256.hash(args[1], &hash256_1, .{});
std.crypto.hash.sha2.Sha256.hash(args[2], &hash256_2, .{});
std.crypto.hash.sha2.Sha256.hash(args[3], &hash256_3, .{});
std.crypto.hash.sha2.Sha256.hash(args[4], &hash256_4, .{});
const to_prove = try std.fmt.parseInt(usize, args[5], 10);
const leaves = &[_]Hash{
hash256_1,
hash256_2,
hash256_3,
hash256_4,
};
const allocator = std.heap.page_allocator;
var tree = try MerkleTree.MerkleTree.build(allocator, leaves);
defer tree.deinit();
const root = tree.root();
const proof = try tree.generateProof(to_prove);
defer allocator.free(proof);
const valid = tree.verifyProof(leaves[to_prove], to_prove, proof);
try stdout.print("\nData: {s}, {s}, {s}, {s}\n", .{ args[1], args[2], args[3], args[4] });
try stdout.print("\nLeaf 1 (SHA-256): {x}\n", .{hash256_1});
try stdout.print("Leaf 2 (SHA-256): {x}\n", .{hash256_2});
try stdout.print("Leaf 3 (SHA-256): {x}\n", .{hash256_3});
try stdout.print("Leaf 4 (SHA-256): {x}\n", .{hash256_4});
try stdout.print("\nMerkle Root {x}\n", .{root});
try stdout.print("\nProof for {s}: \n", .{args[to_prove + 1]});
for (0..proof.len) |i| {
try stdout.print(" {x}\n", .{proof[i]});
}
if (valid) {
try stdout.print("\nLeaf has been proven\n", .{});
}
try stdout.flush();
}Merkle Tree 代码基于 [ 此处]：
//! Merkle Tree
const std = @import("std");
const testing = std.testing;
/// Merkle Root 为 32 字节 (128 位)
pub const HASH_SIZE = 32;
/// Merkle Root 哈希类型
pub const Hash = [HASH_SIZE]u8;
/// 几个 Merkle tree 错误
pub const MerkleError = error{
EmptyLeaves,
InvalidProof,
InvalidLeafIndex,
OutOfMemory,
};
// 存储 Merkle tree
pub const MerkleTree = struct {
allocator: std.mem.Allocator,
leaves: []Hash,
root_hash: Hash,
/// 从叶子构建 Merkle tree
pub fn build(allocator: std.mem.Allocator, leaves: []const Hash) !MerkleTree {
if (leaves.len == 0) {
return MerkleError.EmptyLeaves;
}
// 叶子副本
const leaves_copy = try allocator.alloc(Hash, leaves.len);
errdefer allocator.free(leaves_copy);
@memcpy(leaves_copy, leaves);
// 获取根
const root_hash = try computeRoot(allocator, leaves);
return MerkleTree{
.allocator = allocator,
.leaves = leaves_copy,
.root_hash = root_hash,
};
}
/// 释放树的内存
pub fn deinit(self: *MerkleTree) void {
self.allocator.free(self.leaves);
}
/// 显示根
pub fn root(self: *const MerkleTree) Hash {
return self.root_hash;
}
/// 为特定叶子生成 Merkle 证明
pub fn generateProof(
self: *const MerkleTree,
leaf_index: usize,
) ![]Hash {
if (leaf_index >= self.leaves.len) {
return MerkleError.InvalidLeafIndex;
}
var proof: std.ArrayList(Hash) = .empty;
errdefer proof.deinit(self.allocator);
// 通过向上遍历树来构建证明
var current_level = try self.allocator.alloc(Hash, self.leaves.len);
defer self.allocator.free(current_level);
@memcpy(current_level, self.leaves);
var current_index = leaf_index;
while (current_level.len > 1) {
// 查找兄弟节点
const sibling_index = if (current_index % 2 == 0)
current_index + 1
else
current_index - 1;
// 如果兄弟节点存在，则将其添加到证明中
if (sibling_index < current_level.len) {
try proof.append(self.allocator, current_level[sibling_index]);
} else {
// 奇数个节点，复制最后一个节点
try proof.append(self.allocator, current_level[current_index]);
}
// 构建下一层
const next_level_size = (current_level.len + 1) / 2;
var next_level = try self.allocator.alloc(Hash, next_level_size);
for (0..next_level_size) |i| {
const left_idx = i * 2;
const right_idx = left_idx + 1;
const left = current_level[left_idx];
const right = if (right_idx < current_level.len)
current_level[right_idx]
else
current_level[left_idx]; // 如果是奇数则重复
next_level[i] = hashPair(left, right);
}
self.allocator.free(current_level);
current_level = next_level;
current_index = current_index / 2;
}
return proof.toOwnedSlice(self.allocator);
}
/// 验证 Merkle 证明
pub fn verifyProof(
self: *const MerkleTree,
leaf_hash: Hash,
leaf_index: usize,
proof: []const Hash,
) bool {
if (leaf_index >= self.leaves.len) {
return false;
}
var computed_hash = leaf_hash;
var current_index = leaf_index;
// 重构到根的路径
for (proof) |sibling_hash| {
computed_hash = if (current_index % 2 == 0)
hashPair(computed_hash, sibling_hash)
else
hashPair(sibling_hash, computed_hash);
current_index = current_index / 2;
}
// 检查计算出的根是否与实际根匹配
return std.mem.eql(u8, &computed_hash, &self.root_hash);
}
};
/// 从叶子计算 Merkle root
fn computeRoot(allocator: std.mem.Allocator, leaves: []const Hash) !Hash {
if (leaves.len == 0) {
return error.EmptyLeaves;
}
if (leaves.len == 1) {
return leaves[0];
}
var current_level = try allocator.alloc(Hash, leaves.len);
defer allocator.free(current_level);
@memcpy(current_level, leaves);
while (current_level.len > 1) {
const next_level_size = (current_level.len + 1) / 2;
var next_level = try allocator.alloc(Hash, next_level_size);
for (0..next_level_size) |i| {
const left_idx = i * 2;
const right_idx = left_idx + 1;
const left = current_level[left_idx];
const right = if (right_idx < current_level.len)
current_level[right_idx]
else
current_level[left_idx]; // 如果是奇数则重复
next_level[i] = hashPair(left, right);
}
allocator.free(current_level);
current_level = next_level;
}
const root = current_level[0];
return root;
}
/// 哈希一对节点以创建父节点
fn hashPair(left: Hash, right: Hash) Hash {
var hasher = std.crypto.hash.sha2.Sha256.init(.{});
hasher.update(&left);
hasher.update(&right);
var digest: [32]u8 = undefined;
hasher.final(&digest);
return (digest);
}在 Microsoft Windows 上，我们使用以下命令编译为可执行文件：
> zig build-exe zig_merkle.zig然后我们可以运行文件 zig_hash.exe。证明“scotland”的示例运行 [ 此处]：
Data: scotland, england, ireland, wales
Leaf 1 (SHA-256): cea6e08605496fcf871946f7ee8d5f26bfe32eeec8fdfd614d152d1bd3e6391c
Leaf 2 (SHA-256): d56d0ff69b62792a00a361fbf6e02e2a634a7a8da1c3e49d59e71e0f19c27875
Leaf 3 (SHA-256): 32f987ecd36719a12041719b7a729ecbe96f3d76e110121e60df0e599fe9e768
Leaf 4 (SHA-256): 6baade0e6ad44a503ff0d82b52fb878d3bfc5b61313e558fa03b7cbaeab2c311
Merkle Root 33d470e08bec389412d1aa152fe76becb7848e5243ee3756763986c91c5ee46c
Proof for scotland:
d56d0ff69b62792a00a361fbf6e02e2a634a7a8da1c3e49d59e71e0f19c27875
e83b0425ce1d656d693f227bdd441b4046f082868808772447c6a23516bac114
Leaf has been proven如果我们使用 Merkle Tree 可视化工具 [ 此处]，我们会得到：
并由以下定义：
你可以在 此处 尝试此代码。
结论
对于 Ralph，我向他的才智和动力致以崇高的敬意。Merkle Tree 仍然是我们网络安全领域中最安全的方法之一，其用途只会增加。对我来说，当有人提到区块链时，我就会想到 Merkle Trees。
- 原文链接： billatnapier.medium.com/...
- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
