Merkle 认证树Merkle Authentication Tree是我做数据完整性验证和批量凭证管理时很常用的一种结构。很多场景需要验证“这一条数据是否真的属于某一整批数据”但又不想为了验一条数据把整个数据集重新拉下来。Merkle 树的思路是从一个种子seed出发按固定规则生成一批叶子节点再逐层向上合并哈希最终得到唯一根哈希。验证时只需要根哈希和一条很短的认证路径就能判断某个叶子在不在树里。这个结构比把所有哈希拼成一个列表更省空间也更适合千级、万级甚至百万级数据的离线校验。这篇文章会从最小一棵树讲起再逐步扩展到上千叶子的构建、认证路径生成和生产化接口设计。适合刚接触 Merkle 树、需要在项目里落地的开发者也适合想搞清楚认证路径为什么可靠的人。1. 先想清楚这颗种子和这些叶子到底指什么1.1 认证树的基本形态Merkle 树通常是一棵二叉树底层是叶子节点。每个叶子来自一条待验证数据每个内部节点是左右子节点哈希合并后的哈希树的顶层只有一个根节点也就是根哈希。标题里的“种子”指的是确定整组叶子内容的初始输入。比如把业务主键、文档编号或测试数据都从同一个 seed 派生出来。叶子并不一定必须来自 seed业务上它们可能是数据库记录、文件内容、用户凭证。但为了让树可以被重复构建叶子的生成规则必须固定。如果一棵树的所有叶子都可以从 seed 和编号重新算出来那这颗种子就是整棵树的源头。这也是“From One Seed to a Thousand Leaves”的意思一个 seed配合固定规则可以派生出大量叶子验证时不需要把所有叶子都交给对方只需要给出根哈希和一条路径。1.2 和哈希列表相比优势在哪如果只是校验一批数据有没有被改动最简单的做法是每条数据算一个哈希组成哈希列表再把所有哈希拼接起来算一个总哈希。但验证某一条数据时验证方要么拿到全部哈希列表要么需要重新计算全部数据。数据量一大传输和计算成本都很高。Merkle 树把数据组织成树形结构。验证一条数据只需要从对应叶子出发沿着路径拿到每一层的兄弟哈希。需要提供的数据量从 O(n) 变成 O(log n)。1000 条数据大约只需要 10 个兄弟哈希100 万条数据大约只需要 20 个兄弟哈希。这个扩展性正是认证树最大的价值。1.3 适合什么场景不适合什么场景适合的场景有文件完整性校验、日志防篡改、批量凭证登记、区块链状态摘要、云存储多块校验、版本发布清单校验。这些场景的共同特点是“一次构建、多次验证”而且验证方并不想拥有完整数据集。不适合的场景是频繁修改单个叶子。比如一个数据实体需要不断更新每次更新都要重算从叶子到根的一条路径。如果业务更新频率很高整体代价可能比直接全量哈希还高。Merkle 树更适合数据不变、只做认证或者以追加为主、很少修改的场景。还要区分“默克尔树”和“默克尔认证树”。普通默克尔树通常只关心完整性认证树则强调能够为某个叶子生成可验证的路径证明。实现上差别不大但设计接口时要考虑 proof 的生成和校验而不只是计算根哈希。标题里的 Authentication Tree重点就在这种带路径认证的使用方式上。1.4 Merkle 根只是摘要不是签名这里要强调一个边界Merkle 根只证明这组数据在结构上自洽并不证明它来自某个可信方。攻击者如果能够伪造整棵树也可以伪造根。所以生产环境通常会对根哈希做签名或者把它放在可信存储中。验证方信任的应该是签名过的根而不是随便收到的 root。理解了这一点就不会把 Merkle 树当成数字签名来用。Merkle 树解决的是“数据完整性”和“批量认证”问题而不是“身份认证”问题。2. 先跑通最小演示四片叶子验证完整链路2.1 环境与输入约定先用 4 个叶子跑通不要一上来就追求 1000 片。小规模树能帮你验证规则规则对了规模扩大只是循环次数的事。语言选择上本机用 Java 比较多但下面这个逻辑换成 Python、Go、TypeScript 都成立。核心只有三件事选择哈希算法一般用 SHA-256。约定叶子内容的字节生成方式。约定左右子节点拼接顺序。环境要求不高普通的 JDK 8 以上就能跑不需要额外依赖。如果用 Python需要 Python 3 内置的 hashlib。无论哪种环境最关键的是让输入字节完全可控。2.2 叶子节点如何生成假设 seed 是demo-seed我们生成 4 片叶子leaf0 sha256(demo-seed-0)leaf1 sha256(demo-seed-1)leaf2 sha256(demo-seed-2)leaf3 sha256(demo-seed-3)字符串统一用 UTF-8 编码分隔符用短横线。这个约定要写死后续所有环境都要一致。不要使用Object.toString()之类会随环境变化的内容作为叶子输入。2.3 从叶子向上合并代码怎么写Java 里用MessageDigest.getInstance(SHA-256)。每次计算时重新创建MessageDigest实例可以避免线程安全问题。核心逻辑是把两个 byte[] 拼接成一个 byte[]再计算哈希。import java.nio.charset.StandardCharsets; import java.security.MessageDigest; public class SimpleMerkleTree { public static byte[] sha256(byte[] input) throws Exception { MessageDigest md MessageDigest.getInstance(SHA-256); return md.digest(input); } public static byte[] concat(byte[] a, byte[] b) { byte[] result new byte[a.length b.length]; System.arraycopy(a, 0, result, 0, a.length); System.arraycopy(b, 0, result, a.length, b.length); return result; } public static String hex(byte[] bytes) { StringBuilder sb new StringBuilder(); for (byte b : bytes) { sb.append(String.format(%02x, b)); } return sb.toString(); } public static void main(String[] args) throws Exception { String seed demo-seed; int leafCount 4; byte[][] level new byte[leafCount][]; for (int i 0; i leafCount; i) { byte[] data (seed - i).getBytes(StandardCharsets.UTF_8); level[i] sha256(data); } while (level.length 1) { int nextSize (level.length 1) / 2; byte[][] nextLevel new byte[nextSize][]; for (int i 0; i nextSize; i) { int leftIndex i * 2; int rightIndex leftIndex 1; if (rightIndex level.length) { nextLevel[i] sha256(concat(level[leftIndex], level[rightIndex])); } else { // 奇数个节点时把最后一个节点直接复制到上一层 nextLevel[i] level[leftIndex]; } } level nextLevel; } System.out.println(root hex(level[0])); } }为什么用 while 循环逐层合并因为树的层数是 log2(叶子数)每层数量减半。当叶子数是 2 的幂时合并过程非常整齐当叶子数不是 2 的幂时奇数节点需要约定处理方式。上面代码选择“直接复制最后一个节点”这种规则可以跑通但后文会建议一个更稳妥的方案先把叶子补齐到 2 的幂。2.4 怎么判断演示结果是对是错运行后输出一个 64 位十六进制字符串这就是根哈希。判断标准很简单同样的 seed 和同样的输入规则每次运行输出必须一致。改变任意一个叶子的数据根哈希必须变化。左右节点交换顺序根哈希必须变化。从 4 片叶子改成 3 片叶子根哈希大概率不同除非哈希碰撞。如果输出不一致先检查字符串拼接、编码和是否误用了随机函数。很多人第一次跑失败不是算法写错而是输入的字节内容前后不一致。3. 从四片叶子扩展到一千片构建规则和性能边界3.1 叶子数量变化后树高和路径长度怎么算标准二叉 Merkle 树中如果 N 是叶子数树高约等于 ceil(log2(N))。证明一条叶子需要经过的兄弟节点数量就是树高。叶子数量约树高一条认证路径包含的兄弟哈希数量以 SHA-256 计算约多大42264 字节1644128 字节100010最多 10约 320 字节1000014最多 14约 448 字节100000020最多 20约 640 字节这里的“约”是因为如果叶子数量不是 2 的幂树不是完全平衡的。多数实现会把最后一个节点复制或者补齐到 2 的幂让所有叶子在同一深度。补齐会让路径长度稳定为 k其中 k ceil(log2(N))。补齐规则必须固定否则跨语言验证会对不上。3.2 用 seed 确定一千个叶子规则要固定代码上把 4 改成 1000 就得到 1000 个叶子int leafCount 1000; for (int i 0; i leafCount; i) { byte[] data (seed - i).getBytes(StandardCharsets.UTF_8); level[i] sha256(data); }这里有三个容易出错的地方分隔符。用-还是_还是空字符串必须写死。编号从 0 开始还是从 1 开始必须与验证端一致。编码统一 UTF-8。如果某个环境默认用 GBK根哈希立刻变。我查资料时还看到一种写法类似long n numericConvertUtil.toDecimalNumber(database, seed); long n (n - s ...)。这种代码第一眼就有问题同一个作用域声明两次long n编译会直接报错。它的本意可能是先调用工具类把业务主键和 seed 转成一个数字再参与节点计算。思路可以接受但放在 Merkle 树里要特别注意转换规则必须固定字段顺序不能乱返回类型不要用 int 截断否则同一份数据在不同环境重建时根哈希一定不一致。如果要生成 1000 个内容不同的叶子推荐用sha256(seed - index)这种可复现规则而不是依赖随机数。随机数只适合测试不适合正式认证树因为验证端无法只凭 seed 重建同一棵树。3.3 批量构建时内存、并发和 IO 怎么处理1000 个叶子并不大。完整树的叶子层是 1000 * 32 字节约 32KB加上上层节点总量约 64KB。普通机器没有任何压力。但真实场景中叶子往往来自大文件或数据库记录不能把所有原始数据都加载进内存。所以批量构建的原则是先把每条数据哈希成 32 字节的叶子原始数据用完就释放。只保留叶子哈希数组作为树的输入。如果叶子太多比如百万级可以把叶子哈希分批写入临时文件再分块构建。叶子哈希阶段可以用多线程并行但上层合并阶段不适合无限并发因为每层依赖上一层结果。正式场景建议先跑一个 100 叶子的构建任务记录内存和耗时再按比例估算 1000 叶子。不要一上来就开最大并发否则日志一多问题反而不容易定位。3.4 验收一个批量构建任务要看哪些指标不要只看“最终输出一个 root 就是成功”。构建任务至少要看六项指标输入seed、叶子数量、叶子内容规则、哈希算法。输出根哈希、可选树高、可选叶子哈希列表。稳定性同一输入多次构建根哈希完全一致。耗时单条叶子平均耗时、总构建耗时。内存峰值内存是否在接受范围。可复现性换一台机器、换一种语言实现根哈希是否一致。只要这六项都明确批量构建才算验证过。以后出问题优先核对输入规则而不是怀疑算法。4. 认证路径才是核心生成 Proof 并验证4.1 Proof 由哪些节点组成要证明第 i 片叶子属于这棵树路径上需要每一层兄弟节点的哈希。假设有 4 片叶子证明第 1 片index1第 0 层叶子 1 是右节点兄弟是叶子 0方向是 left。第 1 层父节点是 hash(leaf0 leaf1)它在这一层是左节点兄弟是 hash(leaf2 leaf3)方向是 right。所以 Proof 是[(left, leaf0Hash), (right, node23Hash)]。验证时从 leaf1 开始先拼接兄弟 left 当前得到父节点。再拼接当前 兄弟 right得到根。和预期 root 比较。方向不能错。这是认证路径最容易出错的地方。4.2 生成 Proof 的代码逻辑用补齐到 2 的幂的方式最简单。先写一个函数构建完整层级import hashlib def sha256(data: bytes) - bytes: return hashlib.sha256(data).digest() def build_levels(leaves_hex): # leaves_hex: List[str]每个叶子是 64 位十六进制 level [bytes.fromhex(h) for h in leaves_hex] # 补齐到 2 的幂 size 1 while size len(level): size 1 level level [level[-1]] * (size - len(level)) levels [level] while len(level) 1: next_level [] for i in range(0, len(level), 2): next_level.append(sha256(level[i] level[i 1])) levels.append(next_level) level next_level return levels def generate_proof(levels, index): proof [] for level in levels[:-1]: sibling_index index ^ 1 sibling level[sibling_index] direction left if sibling_index index else right proof.append((direction, sibling.hex())) index // 2 return prooflevels[:-1]是因为最后一层是根不需要从根取兄弟。补齐到 2 的幂后每层都有完整的左右节点奇偶问题自然消失。4.3 验证的完整过程和常见误区验证代码如下def verify_proof(leaf_hex, proof, root_hex): node bytes.fromhex(leaf_hex) for direction, sibling_hex in proof: sibling bytes.fromhex(sibling_hex) if direction left: node sha256(sibling node) else: node sha256(node Merkle认证树：从种子到千叶的构建与Proof验证
Merkle 认证树Merkle Authentication Tree是我做数据完整性验证和批量凭证管理时很常用的一种结构。很多场景需要验证“这一条数据是否真的属于某一整批数据”但又不想为了验一条数据把整个数据集重新拉下来。Merkle 树的思路是从一个种子seed出发按固定规则生成一批叶子节点再逐层向上合并哈希最终得到唯一根哈希。验证时只需要根哈希和一条很短的认证路径就能判断某个叶子在不在树里。这个结构比把所有哈希拼成一个列表更省空间也更适合千级、万级甚至百万级数据的离线校验。这篇文章会从最小一棵树讲起再逐步扩展到上千叶子的构建、认证路径生成和生产化接口设计。适合刚接触 Merkle 树、需要在项目里落地的开发者也适合想搞清楚认证路径为什么可靠的人。1. 先想清楚这颗种子和这些叶子到底指什么1.1 认证树的基本形态Merkle 树通常是一棵二叉树底层是叶子节点。每个叶子来自一条待验证数据每个内部节点是左右子节点哈希合并后的哈希树的顶层只有一个根节点也就是根哈希。标题里的“种子”指的是确定整组叶子内容的初始输入。比如把业务主键、文档编号或测试数据都从同一个 seed 派生出来。叶子并不一定必须来自 seed业务上它们可能是数据库记录、文件内容、用户凭证。但为了让树可以被重复构建叶子的生成规则必须固定。如果一棵树的所有叶子都可以从 seed 和编号重新算出来那这颗种子就是整棵树的源头。这也是“From One Seed to a Thousand Leaves”的意思一个 seed配合固定规则可以派生出大量叶子验证时不需要把所有叶子都交给对方只需要给出根哈希和一条路径。1.2 和哈希列表相比优势在哪如果只是校验一批数据有没有被改动最简单的做法是每条数据算一个哈希组成哈希列表再把所有哈希拼接起来算一个总哈希。但验证某一条数据时验证方要么拿到全部哈希列表要么需要重新计算全部数据。数据量一大传输和计算成本都很高。Merkle 树把数据组织成树形结构。验证一条数据只需要从对应叶子出发沿着路径拿到每一层的兄弟哈希。需要提供的数据量从 O(n) 变成 O(log n)。1000 条数据大约只需要 10 个兄弟哈希100 万条数据大约只需要 20 个兄弟哈希。这个扩展性正是认证树最大的价值。1.3 适合什么场景不适合什么场景适合的场景有文件完整性校验、日志防篡改、批量凭证登记、区块链状态摘要、云存储多块校验、版本发布清单校验。这些场景的共同特点是“一次构建、多次验证”而且验证方并不想拥有完整数据集。不适合的场景是频繁修改单个叶子。比如一个数据实体需要不断更新每次更新都要重算从叶子到根的一条路径。如果业务更新频率很高整体代价可能比直接全量哈希还高。Merkle 树更适合数据不变、只做认证或者以追加为主、很少修改的场景。还要区分“默克尔树”和“默克尔认证树”。普通默克尔树通常只关心完整性认证树则强调能够为某个叶子生成可验证的路径证明。实现上差别不大但设计接口时要考虑 proof 的生成和校验而不只是计算根哈希。标题里的 Authentication Tree重点就在这种带路径认证的使用方式上。1.4 Merkle 根只是摘要不是签名这里要强调一个边界Merkle 根只证明这组数据在结构上自洽并不证明它来自某个可信方。攻击者如果能够伪造整棵树也可以伪造根。所以生产环境通常会对根哈希做签名或者把它放在可信存储中。验证方信任的应该是签名过的根而不是随便收到的 root。理解了这一点就不会把 Merkle 树当成数字签名来用。Merkle 树解决的是“数据完整性”和“批量认证”问题而不是“身份认证”问题。2. 先跑通最小演示四片叶子验证完整链路2.1 环境与输入约定先用 4 个叶子跑通不要一上来就追求 1000 片。小规模树能帮你验证规则规则对了规模扩大只是循环次数的事。语言选择上本机用 Java 比较多但下面这个逻辑换成 Python、Go、TypeScript 都成立。核心只有三件事选择哈希算法一般用 SHA-256。约定叶子内容的字节生成方式。约定左右子节点拼接顺序。环境要求不高普通的 JDK 8 以上就能跑不需要额外依赖。如果用 Python需要 Python 3 内置的 hashlib。无论哪种环境最关键的是让输入字节完全可控。2.2 叶子节点如何生成假设 seed 是demo-seed我们生成 4 片叶子leaf0 sha256(demo-seed-0)leaf1 sha256(demo-seed-1)leaf2 sha256(demo-seed-2)leaf3 sha256(demo-seed-3)字符串统一用 UTF-8 编码分隔符用短横线。这个约定要写死后续所有环境都要一致。不要使用Object.toString()之类会随环境变化的内容作为叶子输入。2.3 从叶子向上合并代码怎么写Java 里用MessageDigest.getInstance(SHA-256)。每次计算时重新创建MessageDigest实例可以避免线程安全问题。核心逻辑是把两个 byte[] 拼接成一个 byte[]再计算哈希。import java.nio.charset.StandardCharsets; import java.security.MessageDigest; public class SimpleMerkleTree { public static byte[] sha256(byte[] input) throws Exception { MessageDigest md MessageDigest.getInstance(SHA-256); return md.digest(input); } public static byte[] concat(byte[] a, byte[] b) { byte[] result new byte[a.length b.length]; System.arraycopy(a, 0, result, 0, a.length); System.arraycopy(b, 0, result, a.length, b.length); return result; } public static String hex(byte[] bytes) { StringBuilder sb new StringBuilder(); for (byte b : bytes) { sb.append(String.format(%02x, b)); } return sb.toString(); } public static void main(String[] args) throws Exception { String seed demo-seed; int leafCount 4; byte[][] level new byte[leafCount][]; for (int i 0; i leafCount; i) { byte[] data (seed - i).getBytes(StandardCharsets.UTF_8); level[i] sha256(data); } while (level.length 1) { int nextSize (level.length 1) / 2; byte[][] nextLevel new byte[nextSize][]; for (int i 0; i nextSize; i) { int leftIndex i * 2; int rightIndex leftIndex 1; if (rightIndex level.length) { nextLevel[i] sha256(concat(level[leftIndex], level[rightIndex])); } else { // 奇数个节点时把最后一个节点直接复制到上一层 nextLevel[i] level[leftIndex]; } } level nextLevel; } System.out.println(root hex(level[0])); } }为什么用 while 循环逐层合并因为树的层数是 log2(叶子数)每层数量减半。当叶子数是 2 的幂时合并过程非常整齐当叶子数不是 2 的幂时奇数节点需要约定处理方式。上面代码选择“直接复制最后一个节点”这种规则可以跑通但后文会建议一个更稳妥的方案先把叶子补齐到 2 的幂。2.4 怎么判断演示结果是对是错运行后输出一个 64 位十六进制字符串这就是根哈希。判断标准很简单同样的 seed 和同样的输入规则每次运行输出必须一致。改变任意一个叶子的数据根哈希必须变化。左右节点交换顺序根哈希必须变化。从 4 片叶子改成 3 片叶子根哈希大概率不同除非哈希碰撞。如果输出不一致先检查字符串拼接、编码和是否误用了随机函数。很多人第一次跑失败不是算法写错而是输入的字节内容前后不一致。3. 从四片叶子扩展到一千片构建规则和性能边界3.1 叶子数量变化后树高和路径长度怎么算标准二叉 Merkle 树中如果 N 是叶子数树高约等于 ceil(log2(N))。证明一条叶子需要经过的兄弟节点数量就是树高。叶子数量约树高一条认证路径包含的兄弟哈希数量以 SHA-256 计算约多大42264 字节1644128 字节100010最多 10约 320 字节1000014最多 14约 448 字节100000020最多 20约 640 字节这里的“约”是因为如果叶子数量不是 2 的幂树不是完全平衡的。多数实现会把最后一个节点复制或者补齐到 2 的幂让所有叶子在同一深度。补齐会让路径长度稳定为 k其中 k ceil(log2(N))。补齐规则必须固定否则跨语言验证会对不上。3.2 用 seed 确定一千个叶子规则要固定代码上把 4 改成 1000 就得到 1000 个叶子int leafCount 1000; for (int i 0; i leafCount; i) { byte[] data (seed - i).getBytes(StandardCharsets.UTF_8); level[i] sha256(data); }这里有三个容易出错的地方分隔符。用-还是_还是空字符串必须写死。编号从 0 开始还是从 1 开始必须与验证端一致。编码统一 UTF-8。如果某个环境默认用 GBK根哈希立刻变。我查资料时还看到一种写法类似long n numericConvertUtil.toDecimalNumber(database, seed); long n (n - s ...)。这种代码第一眼就有问题同一个作用域声明两次long n编译会直接报错。它的本意可能是先调用工具类把业务主键和 seed 转成一个数字再参与节点计算。思路可以接受但放在 Merkle 树里要特别注意转换规则必须固定字段顺序不能乱返回类型不要用 int 截断否则同一份数据在不同环境重建时根哈希一定不一致。如果要生成 1000 个内容不同的叶子推荐用sha256(seed - index)这种可复现规则而不是依赖随机数。随机数只适合测试不适合正式认证树因为验证端无法只凭 seed 重建同一棵树。3.3 批量构建时内存、并发和 IO 怎么处理1000 个叶子并不大。完整树的叶子层是 1000 * 32 字节约 32KB加上上层节点总量约 64KB。普通机器没有任何压力。但真实场景中叶子往往来自大文件或数据库记录不能把所有原始数据都加载进内存。所以批量构建的原则是先把每条数据哈希成 32 字节的叶子原始数据用完就释放。只保留叶子哈希数组作为树的输入。如果叶子太多比如百万级可以把叶子哈希分批写入临时文件再分块构建。叶子哈希阶段可以用多线程并行但上层合并阶段不适合无限并发因为每层依赖上一层结果。正式场景建议先跑一个 100 叶子的构建任务记录内存和耗时再按比例估算 1000 叶子。不要一上来就开最大并发否则日志一多问题反而不容易定位。3.4 验收一个批量构建任务要看哪些指标不要只看“最终输出一个 root 就是成功”。构建任务至少要看六项指标输入seed、叶子数量、叶子内容规则、哈希算法。输出根哈希、可选树高、可选叶子哈希列表。稳定性同一输入多次构建根哈希完全一致。耗时单条叶子平均耗时、总构建耗时。内存峰值内存是否在接受范围。可复现性换一台机器、换一种语言实现根哈希是否一致。只要这六项都明确批量构建才算验证过。以后出问题优先核对输入规则而不是怀疑算法。4. 认证路径才是核心生成 Proof 并验证4.1 Proof 由哪些节点组成要证明第 i 片叶子属于这棵树路径上需要每一层兄弟节点的哈希。假设有 4 片叶子证明第 1 片index1第 0 层叶子 1 是右节点兄弟是叶子 0方向是 left。第 1 层父节点是 hash(leaf0 leaf1)它在这一层是左节点兄弟是 hash(leaf2 leaf3)方向是 right。所以 Proof 是[(left, leaf0Hash), (right, node23Hash)]。验证时从 leaf1 开始先拼接兄弟 left 当前得到父节点。再拼接当前 兄弟 right得到根。和预期 root 比较。方向不能错。这是认证路径最容易出错的地方。4.2 生成 Proof 的代码逻辑用补齐到 2 的幂的方式最简单。先写一个函数构建完整层级import hashlib def sha256(data: bytes) - bytes: return hashlib.sha256(data).digest() def build_levels(leaves_hex): # leaves_hex: List[str]每个叶子是 64 位十六进制 level [bytes.fromhex(h) for h in leaves_hex] # 补齐到 2 的幂 size 1 while size len(level): size 1 level level [level[-1]] * (size - len(level)) levels [level] while len(level) 1: next_level [] for i in range(0, len(level), 2): next_level.append(sha256(level[i] level[i 1])) levels.append(next_level) level next_level return levels def generate_proof(levels, index): proof [] for level in levels[:-1]: sibling_index index ^ 1 sibling level[sibling_index] direction left if sibling_index index else right proof.append((direction, sibling.hex())) index // 2 return prooflevels[:-1]是因为最后一层是根不需要从根取兄弟。补齐到 2 的幂后每层都有完整的左右节点奇偶问题自然消失。4.3 验证的完整过程和常见误区验证代码如下def verify_proof(leaf_hex, proof, root_hex): node bytes.fromhex(leaf_hex) for direction, sibling_hex in proof: sibling bytes.fromhex(sibling_hex) if direction left: node sha256(sibling node) else: node sha256(node