企业官网建设流程全解析

Fuel TS SDK 默克尔树模块 @fuel-ts/merkle 全解：二进制树、求和树与稀疏树实现与实战

【免费下载链接】fuels-tsFuel Network Typescript SDK项目地址: https://gitcode.com/GitHub_Trending/fu/fuels-ts

@fuel-ts/merkle是 fuels-ts 仓库（Fuel Network TypeScript SDK）中专门处理默克尔树（Merkle Tree）的底层子模块，为 Fuel 链上数据完整性校验提供三类核心原语：用于计算根与构造包含证明的二进制默克尔树、可携带数值求和的 Sum Merkle Tree，以及能对任意 key 高效给出非包含证明的稀疏默克尔树。读完本文，你将掌握该模块的目录职责、哈希域编码规则、增删改查与证明生成的完整 API，并能读懂其单元测试是如何用固定向量校验根值的。

模块定位：fuels-ts 的密码学证明工具箱

@fuel-ts/merkle官方定位是“a sub-module for interacting with Fuel”，即 SDK 中负责默克尔树数据结构的专用包，供区块头校验、交易与事件证明等链上数据交互场景复用。整个包按职责被划分为四个子目录（见 包 README）：

• src/binary— 二进制默克尔树（binary merkle tree）相关工具，用于构造树、计算根与生成证明；
• src/common— 多棵树共享的常量与工具，供测试与部署默克尔树使用；
• src/sum— 带叶子求和能力的求和树，用于计算“携带累加和的默克尔树根”；
• src/sparse— 稀疏默克尔树（sparse merkle tree）工具，以高效的非包含证明著称。

从 包入口 src/index.ts 可以看到，模块对外只 re-export 了两个命名空间：export * from './binary'与export * from './sparse'。进一步查看 binary/index.ts 与 sparse/index.ts：二进制目录对外导出全部工具函数，而稀疏目录仅导出SparseMerkleTree类。也就是说，common与sum是面向包内部（或 monorepo 内部源码引用）实现的模块，公共入口对外暴露的核心能力是「二进制树函数集」与「SparseMerkleTree类」，这一点在使用时需要留意。

包自身配置（见 package.json）确认了以下事实：当前版本为0.103.0，许可证为Apache-2.0，仅依赖两个 monorepo 内部包——提供哈希算法的@fuel-ts/hasher与提供大整数运算的@fuel-ts/math；产物经tsup构建为dist/index.js（CommonJS）、dist/index.mjs（ESM）与dist/index.d.ts（类型声明），并声明 Node.js^20 || ^22 || ^24的 engines 支持范围。

安装与引入方式

README 给出了两种安装路径，均面向真实消费场景，直接可用：

# 仅安装默克尔树子模块 pnpm add @fuel-ts/merkle # 或 npm add @fuel-ts/merkle # 推荐方式：安装完整 SDK 伞形包 fuels（内部已聚合全部子模块） pnpm add fuels # 或 npm add fuels

安装后在代码中按需引入即可：

// 二进制默克尔树工具函数 import { calcRoot, constructTree, getProof } from '@fuel-ts/merkle'; // 稀疏默克尔树类 import { SparseMerkleTree } from '@fuel-ts/merkle';

二进制默克尔树：计算根与生成包含证明

二进制默克尔树是最经典的默克尔树形态：叶子两两成对哈希，逐层向上直至单一根。包内实现见 binaryMerkleTree.ts，配套的共享常量定义在 common/common.ts：

export const EMPTY = '0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'; export const ZERO = '0x0000000000000000000000000000000000000000000000000000000000000000'; export const MAX_HEIGHT = 256;

其中EMPTY即空串的 SHA-256 摘要（对应空树的根），ZERO是 32 字节零占位值，MAX_HEIGHT = 256是稀疏树路径长度上限。

哈希域编码：模拟 abi.encodePacked 的域分隔前缀

二叉树的哈希函数在 binaryMerkleTree.ts 开头 实现，采用 1 字节域前缀（domain prefix）防止“叶子与内部节点同构”导致的碰撞攻击：

// hashLeaf：0x00 + data，模拟 abi.encodePacked export function hashLeaf(data: string): string { return hash('0x00'.concat(data.slice(2))); } // hashNode：0x01 + left + right export function hashNode(left: string, right: string): string { return hash('0x01'.concat(left.slice(2)).concat(right.slice(2))); }

代码注释明确说明这是“Slice off the '0x' on each argument to simulate abi.encodePacked”的做法——即拼接时去掉每个参数的0x前缀，等价于 Solidity 中abi.encodePacked的紧凑字节拼接语义。注意输入data、left、right均应为0x开头的定长十六进制字符串，slice(2)用来剔除前缀。

建树、求根与取证

包提供三个核心函数：

1. constructTree(data)— 自底向上构建整棵树，返回长度为2n - 1的节点列表（n 个叶子 + n-1 个内部节点）。叶节点哈希为hashLeaf(data[i])，内部节点哈希为hashNode(left.hash, right.hash)；每个节点都记录left/right孩子索引与parent索引（详见src/binary/types/node.ts中的Node类型），便于后续沿父链回溯取证。当叶子数为奇数时，最后一个叶子会直接“上提”到上一层（即经典的奇节点复制处理）。
2. calcRoot(data)— 只计算根而不保留整棵树。空数组输入直接返回常量EMPTY；否则逐层配对哈希，返回根节点哈希值。
3. getProof(nodes, id)— 从指定叶子/节点id出发，沿parent链向上遍历，每层收集“非本路径那一侧兄弟节点”的哈希（nodes[cur].left === prev时取右兄弟，反之取左兄弟），最终得到从叶到根的一条兄弟节点哈希序列，即该叶子的默克尔包含证明。

测试向量：根值与证明长度的确定性验证

二进制树单元测试 用固定向量给出了可复现的预期值：当data[i] = toHex(i, 32)、共 100 片叶子时，calcRoot的结果必须等于0x9e59abcd7c89011ba919f9141624acb32b4cc31c24e76c6d4f64b25093ef366c（该值来自 Go 参考实现，代码注释已注明）；constructTree的节点总数恰为2 * 100 - 1 = 199，列表最后一个节点的哈希即根；对第 0 号叶子取证，证明长度恰好为 7（即ceil(log2(100))），而对根自身取证则得到空证明[]。这些断言既是质量保证，也是理解“证明路径长度 ≈ 树高”的绝佳样例。

Sum Merkle Tree：让每个内部节点都携带累加和

Sum Merkle Tree 在普通二进制树的基础上，为每个叶子关联一个数值（sum），并让每个内部节点的sum等于其左右子树sum之和（实现见 sumMerkleTree.ts，使用@fuel-ts/math的bn()进行加法并以toHex输出）。从实现结构看，这类树适合需要在证明中一并携带聚合数值（如余额、权重、供应量）的链上场景。

其哈希域编码与二进制树严格对齐但内容更丰富（sumMerkleTree.ts#L13-L34）：

// 叶子：0x00 + value(32字节) + data export function hashLeaf(value: string, data: string): string { return hash('0x00'.concat(toHex(value, 32).slice(2)).concat(data.slice(2))); } // 内部节点：0x01 + leftSum(32字节) + leftHash + rightSum(32字节) + rightHash export function hashNode(leftValue, left, rightValue, right): string { return hash( '0x01' .concat(toHex(leftValue, 32).slice(2)) .concat(left.slice(2)) .concat(toHex(rightValue, 32).slice(2)) .concat(right.slice(2)) ); }

对应的constructTree(sums, data)在每层计算父节点时同时求出子sum之和（bn(pNodes[j].sum).add(pNodes[j + 1].sum)）并写入父节点；calcRoot(sums, data)返回根节点Node（而非裸哈希），从而能直接读取根上聚合出的总和；getProof(nodes, id)返回的Proof对象同时携带sideNodes（兄弟哈希）与nodeSums（兄弟求和），验证方可基于这些信息重算“证明路径上的和”。

需要再次提醒：sum目录未出现在 顶层 index.ts 的 re-export 列表里，属于包内/仓库内部使用模块，若在 monorepo 源码层面引用，应使用相对路径导入而非公共包入口。

稀疏默克尔树：面向任意 256 位 key 的高效成员/非成员证明

稀疏默克尔树（Sparse Merkle Tree, SMT）解决的核心问题是：当 key 空间极大（如 256 位哈希地址）而实际叶子稀少时，普通默克尔树无法为“key 不存在”给出简洁证明。SMT 把整棵“逻辑上 2^256 层”的树按需物化：绝大多数路径上没有任何叶子，用统一的零占位符（ZERO）表示，从而只需存储与叶子数成比例的节点，同时天然支持非包含证明（证明某个 key 当前不存在）。

核心类与节点编码

SparseMerkleTree类定义于 sparseMerkleTree.ts，内部用MapStore（{ [hash]: preimage }字典，见 utils.ts）保存哈希到其原始数据的映射；构造时root初始化为ZERO，空子树即零占位符。其增删查 API 为：

• update(key, value)：先计算sideNodes定位旧叶子，再经updateWithSideNodes把新叶子插入到 key 对应路径，更新沿途内部节点，最后setRoot提交新根；
• delete(key)：若 key 处本无叶子（旧叶为ZERO或路径上实际是其他 key）则直接返回当前根（删除无效果），否则逐层把兄弟叶子/占位符上提或压缩；
• prove(key)：生成证明对象SparseMerkleProof；
• proveCompacted(key)：对证明做位掩码压缩后再返回。

树节点编码规则在 treeHasher.ts 中统一：

// 叶子值编码：0x00 + key + hash(data) export function hashLeaf(key: string, data: string): [string, string] { const value = '0x00'.concat(key.slice(2)).concat(hash(data).slice(2)); return [hash(value), value]; } // 内部节点编码：0x01 + left + right export function hashNode(left: string, right: string): [string, string] { const value = '0x01'.concat(left.slice(2)).concat(right.slice(2)); return [hash(value), value]; } // 通过首字节前缀区分叶子(0x00)与内部节点(0x01) export function isLeaf(data: string): boolean { return data.slice(0, 4) === leafPrefix; // leafPrefix = '0x00' }

前缀 0x00 / 0x01 不仅实现哈希域分离，还让parseLeaf/parseNode/isLeaf可以在不查表的情况下仅凭首字节识别节点类型。路径行走使用getBitAtFromMSB(key, i)（从最高位起逐位取 key 的比特），配合MAX_HEIGHT = 256的循环把节点放到正确高度；countCommonPrefix(key1, key2)则用于更新时计算新旧叶子的最长公共前缀，决定是否需要以及在哪一层建立分叉内部节点。

成员与非成员证明：SparseMerkleProof 与验证

证明对象SparseMerkleProof（见 types/sparseMerkleProof.ts）包含三个字段：SideNodes（沿 key 路径的全部兄弟节点哈希）、NonMembershipLeafData（非成员证明中“挡在 key 路径上的那个不相关叶子”的原始数据，若没有则为空串）、SiblingData（目标叶子被找到时的兄弟节点数据）。

验证逻辑verifyProof(proof, root, key, value)位于 proofs.ts：

• 成员证明（value !== ZERO）：计算valueHash = hash(value)与叶子hashLeaf(key, value)，再按 key 的比特位从下往上依次与SideNodes配对hashNode，最终得到根并与root比对；
• 非成员证明（value === ZERO）：若NonMembershipLeafData为空，说明目标路径是零占位符，根应从ZERO出发逐层哈希重建；若非空，则解析该不相关叶子——若其actualPath === key说明 key 其实存在，证明失败并返回false，否则以该叶子的真实路径重建路径，只要重算的根匹配即证明 key 不存在。
• 函数返回[boolean, string[][]]元组：布尔值为校验结果，第二项是重建过程中写入的updates中间节点序列，便于链上/链下重放或在可验证计算中使用。

证明压缩：面向链上 Gas 的位掩码优化

鉴于 256 层路径中绝大多数兄弟节点是零占位符ZERO，直接传输SideNodes极为浪费。proofs.ts#L67-L89 提供的compactProof用一个与路径等长的BitMask（0/1）标记每个位置是否为占位符，把所有非零兄弟节点顺序抽取进compactedSideNodes，得到SparseCompactMerkleProof（结构含SideNodes、BitMask、NumSideNodes、NonMembershipLeafData、SiblingData，类型定义见 types/sparseCompactMerkleProof.ts）；反向的decompactProof按位掩码把零占位符填回原位置即可无损还原完整证明。同一目录下的 deepSparseMerkleSubTree.ts 进一步提供DeepSparseMerkleSubTree（DSMST）——基于若干条 compact 证明把完整 SMT 的“受关注分支”物化成本地子树，从而在离线状态下对子树继续做update并与远端完整树保持根一致。

可复现的树根测试向量

稀疏树单元测试 给出了完整的行为验证：

• 连续插入 100 个叶子（key = hash(toHex(i, 32))，value = toHex(42, 32)）后根必须等于0xdc0537167454509d360e0807b673b0bdfde730dd8ce944a43e397e3a16ac322b；
• 把其中一个叶子更新为新值（toHex(43, 32)）后根变为0x846fb76ccb1cd6f3a2802c658a6ab1befd658e25ff7a81e955e14da50fa77c02，再更新回原值则根精确复原到插入全部叶子后的根——这是 update 幂等可逆的强证据；
• 新增一个叶子后根变为0x97405008d58748206f15c393d58c94c94dcc58ed59c3cbec1f0faf58df27634b，随后delete该 key，根同样恢复到初始插入状态，验证删除路径的正确性；
• 在第二个用例中，测试先用proveCompacted为若干 key 生成压缩证明，通过dsmst.addBranchCompact加入 DSMST，再对同一 key 分别在全量SMT与DeepSparseMerkleSubTree上执行update，断言两者root完全相等——直观验证了压缩证明与局部子树方案的正确性。

验证方式与仓库证据链

• 上述两个测试文件位于 binaryMerkleTree.test.ts 与 sparseMerkleTree.test.ts，测试统一标注@group node（稀疏树额外标注@group browser，即同时覆盖 Node 与浏览器环境），并交由仓库根的 vitest workspace 统一驱动（相关配置可见 vitest.workspace.ts）。
• 想查看该模块的演进历史，可阅读 CHANGELOG.md；许可协议全文见 LICENSE（Apache-2.0）。如需在 fuels-ts 仓库内为它做贡献，请遵循仓库根目录 CONTRIBUTING.md 的流程。

小结

@fuel-ts/merkle用约四个子目录的紧凑实现，为 Fuel TypeScript SDK 补齐了默克尔树全家族能力：binary提供最常用的建树/求根/取证函数，sum让树内节点携带累加和以支撑聚合数值场景，sparse以 256 位 key 空间上的SparseMerkleTree提供成员与非成员证明，并借助SparseCompactMerkleProof的位掩码压缩与DeepSparseMerkleSubTree的局部子树实现降低链上验证成本。理解它最可靠的途径，是直接运行包内带固定向量断言的单元测试，再对照源码中的域分隔前缀与逐位路径算法逐层推演。

【免费下载链接】fuels-tsFuel Network Typescript SDK项目地址: https://gitcode.com/GitHub_Trending/fu/fuels-ts