区块链中的树

2025年10月10日#BlockChain15

AI 生成的摘要

本文讨论了区块链中的几种树结构，包括Merkle树、Trie树、Merkle Patricia树和Verkle树。 1. **Merkle树**：用于对数组求哈希，传统方法的时空复杂度为$O(n)$，而Merkle树通过计算路径上的哈希，将复杂度降低到$O(logn)$，但需要额外的存储空间。 2. **Trie树**：基于前缀索引，适合存储前缀相似的数据。其深度取决于最长字符串的长度，适用于前缀字典查找。 3. **Merkle Patricia树**：将Merkle树扩展为16叉树，父节点记录16个子节点的指针和一个值字段，指针为子节点的哈希值，支持哈希和索引功能，减少数据库请求次数。 4. **Verkle树**：基于KZG构造的16叉树，进一步优化了状态树的管理。

Merkle 树#

问题：对一个数组求哈希（n 个元素）

传统方案：将每个数据拼接然后哈希，时空复杂度都是 $O (n)$

使用 merkle 树：只需计算路线上的哈希，时空复杂度都是 $O (logn)$；代价是总存储空间变大（需要存哈希树），但是依旧是 $O (n)$

Trie 树#

根据前缀进行索引，适用于前缀相似的数据存储

深度最劣为最长字符串的长度（也就是时间复杂度），但不一定是二叉树

适用于前缀字典的查找

Merkle Patricia 树#

把 Merkle 树的二叉变为 16 叉

父节点记录 16 个叉的指针，再加一个 value 字段表示自己的数值

这里的指针，就是子节点的哈希值，存在一个key-value DB里协助反向查找

同时负责哈希和索引两个功能

16 叉减少深度 -> 减少数据库的请求次数

Rollup 的 State Tree#

对 map 和 value 进行分离

Verkle Tree#

基于 KZG

依此构造 16 叉树