Fuel TS SDK 默克尔树模块 fuel-ts/merkle 全解二进制树、求和树与稀疏树实现与实战【免费下载链接】fuels-tsFuel Network Typescript SDK项目地址: https://gitcode.com/GitHub_Trending/fu/fuels-tsfuel-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 中负责默克尔树数据结构的专用包供区块头校验、交易与事件证明等链上数据交互场景复用。整个包按职责被划分为四个子目录见 包 READMEsrc/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.jsCommonJS、dist/index.mjsESM与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.tsexport 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防止“叶子与内部节点同构”导致的碰撞攻击// hashLeaf0x00 data模拟 abi.encodePacked export function hashLeaf(data: string): string { return hash(0x00.concat(data.slice(2))); } // hashNode0x01 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)用来剔除前缀。建树、求根与取证包提供三个核心函数constructTree(data)— 自底向上构建整棵树返回长度为2n - 1的节点列表n 个叶子 n-1 个内部节点。叶节点哈希为hashLeaf(data[i])内部节点哈希为hashNode(left.hash, right.hash)每个节点都记录left/right孩子索引与parent索引详见src/binary/types/node.ts中的Node类型便于后续沿父链回溯取证。当叶子数为奇数时最后一个叶子会直接“上提”到上一层即经典的奇节点复制处理。calcRoot(data)— 只计算根而不保留整棵树。空数组输入直接返回常量EMPTY否则逐层配对哈希返回根节点哈希值。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)生成证明对象SparseMerkleProofproveCompacted(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用一个与路径等长的BitMask0/1标记每个位置是否为占位符把所有非零兄弟节点顺序抽取进compactedSideNodes得到SparseCompactMerkleProof结构含SideNodes、BitMask、NumSideNodes、NonMembershipLeafData、SiblingData类型定义见 types/sparseCompactMerkleProof.ts反向的decompactProof按位掩码把零占位符填回原位置即可无损还原完整证明。同一目录下的 deepSparseMerkleSubTree.ts 进一步提供DeepSparseMerkleSubTreeDSMST——基于若干条 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许可协议全文见 LICENSEApache-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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Fuel TS SDK 默克尔树模块 @fuel-ts/merkle 全解：二进制树、求和树与稀疏树实现与实战
Fuel TS SDK 默克尔树模块 fuel-ts/merkle 全解二进制树、求和树与稀疏树实现与实战【免费下载链接】fuels-tsFuel Network Typescript SDK项目地址: https://gitcode.com/GitHub_Trending/fu/fuels-tsfuel-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 中负责默克尔树数据结构的专用包供区块头校验、交易与事件证明等链上数据交互场景复用。整个包按职责被划分为四个子目录见 包 READMEsrc/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.jsCommonJS、dist/index.mjsESM与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.tsexport 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防止“叶子与内部节点同构”导致的碰撞攻击// hashLeaf0x00 data模拟 abi.encodePacked export function hashLeaf(data: string): string { return hash(0x00.concat(data.slice(2))); } // hashNode0x01 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)用来剔除前缀。建树、求根与取证包提供三个核心函数constructTree(data)— 自底向上构建整棵树返回长度为2n - 1的节点列表n 个叶子 n-1 个内部节点。叶节点哈希为hashLeaf(data[i])内部节点哈希为hashNode(left.hash, right.hash)每个节点都记录left/right孩子索引与parent索引详见src/binary/types/node.ts中的Node类型便于后续沿父链回溯取证。当叶子数为奇数时最后一个叶子会直接“上提”到上一层即经典的奇节点复制处理。calcRoot(data)— 只计算根而不保留整棵树。空数组输入直接返回常量EMPTY否则逐层配对哈希返回根节点哈希值。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)生成证明对象SparseMerkleProofproveCompacted(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用一个与路径等长的BitMask0/1标记每个位置是否为占位符把所有非零兄弟节点顺序抽取进compactedSideNodes得到SparseCompactMerkleProof结构含SideNodes、BitMask、NumSideNodes、NonMembershipLeafData、SiblingData类型定义见 types/sparseCompactMerkleProof.ts反向的decompactProof按位掩码把零占位符填回原位置即可无损还原完整证明。同一目录下的 deepSparseMerkleSubTree.ts 进一步提供DeepSparseMerkleSubTreeDSMST——基于若干条 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许可协议全文见 LICENSEApache-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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考