把一整张表压成一个指纹

一棵能用的 Merkle 树只要二十行，而且你会跑出和这本书一模一样的根：

import hashlib, time
sha = lambda b: hashlib.sha256(b).digest()

def build(vals):
    layer = [sha(str(v).encode()) for v in vals]
    layers = [layer]
    while len(layer) > 1:
        layer = [sha(layer[i] + layer[i+1]) for i in range(0, len(layer), 2)]
        layers.append(layer)
    return layers

def open_at(layers, i):                    # 打开第 i 格：收集一路的兄弟
    path = []
    for lv in range(len(layers) - 1):
        path.append(layers[lv][i ^ 1])
        i >>= 1
    return path

def verify(root, i, v, path):              # 验证：自己一层层算上去
    node = sha(str(v).encode())
    for sib in path:
        node = sha(sib + node) if i & 1 else sha(node + sib)
        i >>= 1
    return node == root

N = 65536
vals = list(range(N))
t = time.perf_counter()
layers = build(vals)
root = layers[-1][0]

print('叶子 %d，层数 %d，根 %s…' % (N, len(layers)-1, root.hex()[:24]))
print('建树 %.0f ms，共 %d 次 SHA-256' % ((time.perf_counter()-t)*1000, 2*N-1))

path = open_at(layers, 700)
print('路径 %d 个哈希 = %d 字节' % (len(path), 32*len(path)))
print('验证通过：', verify(root, 700, vals[700], path))
print('把值改掉：', verify(root, 700, 12345, path))
print('34 次查询 %.1f KB' % (34*(len(path)*32+2)/1024))

叶子 65536，层数 16，根 4f238f7bc1484bb1dc0e0ea5…
建树 55 ms，共 131071 次 SHA-256
路径 16 个哈希 = 512 字节
验证通过： True
把值改掉： False
34 次查询 17.1 KB

那个根 4f238f7b… 和书里印的完全一样——这本书用 JavaScript 生成，你用 Python 跑，结果逐字节相同。这就是哈希函数的意义。

值得亲手试的两件事：(1) 把 N 改成 1024 或 1048576，看层数怎么变（10 和 20），路径字节数怎么变（320 和 640）。(2) 把 path 里任何一个哈希改一个字节，验证立刻变 False。

python3 mk.py # 本机 55 毫秒

在线跑：python.org/shell（N 调到 4096 更快）。注意生产实现要处理叶子数不是 2 的幂的情况，还要防「第二原像攻击」（叶子和内部节点用不同的前缀哈希）。