攻击事件：发生在默克尔山上的验证绕过

erkle Mountain Range (MMR)在进行代码分析之前我们需要先了解一下 Merkle Mountain Range只有了解了这个数据结构是如何运行的才能理解攻击者是如何构造恶意的证明绕过相关的检查Merkle Mountain Range (MMR) 介绍Merkle Mountain RangeMMR是 Merkle Tree 的变体一种仅追加append-only的数据结构。经典的 Merkle Tree 是一棵完全二叉树——叶子数量必须是 2 的幂次而且一旦建好就不方便再往里追加数据。比如在 tornado 中采用的方案就是预先构建好高度为 64 的 merkcle tree叶子节点数量固定然后未被使用的叶子节点采用 0 数据填充。MMR 就是为了解决高效追加 高效证明这个问题而设计的。数据结构MMR 的数据结构为一排从高到低排列的完美二叉树因为像山峰从高到低排列所以叫Mountain Range。每棵树的根节点就叫一个peak山峰。新增过程每次新增一个新叶子时把新增叶子作为一棵高度为 0 的山放到最右边。进行合并检查如果最右边两座山的高度相同就把它们合并对两个根做一次哈希生成一个新的父节点形成一棵更高的山。重复步骤 2直到最右边两座山高度不同为止。此时 MMR 形成了一排从高到低排列的山峰形式。举例说明在原有两个叶子的 MMR 添加第 3 个叶子时旁边多出一座高度 0 的小山。继续添加第 4 个叶子时两座高度 0 的又合并成高度 1然后两座高度 1 的再合并成高度 2只剩一座大山。数学规律如果当前有 n 个叶子把 n 写成二进制每个为 1 的位对应一座山峰。例如n 11 0b1011表示有三座山峰高度分别为 3、1、0对应二进制位 821。所以山峰数量等于 n 的二进制中 1 的个数最多O(log n)座。MMR 根的计算虽然 MMR 可能有多个 peak但最终需要一个唯一的根哈希root来代表整个 MMR。Root 的计算流程如下从右往左选取两个 peak 值进行哈希获得一个 bag hash继续选取下一个 peak 值将 bag hash 和它哈希不断重复步骤 2 直到所有 peak 被选取最后得到的值就是 MMR rootMMR Inclusion ProofMMR inclusion proof 回答的问题是给定一个 MMR root证明某个叶子确实存在于 MMR 中。整个过程分为两个部分Mountain Proof和Peak Bagging。以图中 L5节点 8为例进行 MMR inclusion proof阶段一Mountain Proof这一阶段和普通 Merkle Tree 的 proof 完全一样。验证者手里有L5的原始数据首先算出H(8) Hash(L5_data)。然后 prover 提供了兄弟节点 9 的哈希值验证者计算H(10) Hash(H(8) || H(9))。这里有个关键细节——左右顺序不能搞反。MMR 的节点编号天然编码了位置信息验证者可以通过位置推算出谁在左、谁在右。接着上一层prover 提供H(13)验证者算H(14) Hash(H(10) || H(13))。再上一层prover 提供H(7)验证者算H(15) Hash(H(7) || H(14))。节点 15 就是这座山的 peak。到此为止山内阶段结束。验证者现在手里有了H(15)的值——这个值是自己一步步算出来的不是 prover 给的所以如果中间任何一步被篡改最终的H(15)都会不匹配。阶段二Peak Bagging一个 MMR 通常有多座山图中 11 个叶子产生了 3 座山peak 15h3、peak 18h1、peak 19h0。验证者已经通过阶段一已经算出了H(15)然后在 prover 提供的 proof 中获取H(18)和H(19)的值。bagging 阶段从最右边的 peak 开始两两向左折叠哈希。bag Hash(H(18) || H(19))root Hash(H(15) || bag)这个 root 就是整个 MMR 的根哈希验证者把算出的 root 和链上存储的可信 MMR root 做比较如果相同则证明 proof 有效L5 确实在这个 MMR 中。代码分析整个 MMR 验证的核心对应的是MerkleMountainRange.CalculateRoot()函数第一到第四部分对应mountain proof阶段一第五部分对应peak bagging阶段二第六部分是最终输出。接下来我们结合攻击者的输入进行分析排查出漏洞出现的位置以及攻击者是如何利用这个漏洞构造一次成功的攻击的。重点关注以下部分的参数完整版本的参数请自行查看host: 0x792a6236af69787c40cf76b69b4c8c7b28c4ca20 proof[1]: height:[stateMachineId: 3367, height: 9775932] multiproof[1]:[0x466dddba7e9a84a0f2632b59be71b8bd489e3334a1314a61253f8b827c9d3a36] **leafCount: 1** requests[1]: request[1]:[call DOT.changeAdmin()] **index: 1** kIndex: 0 其中 multiproof 的值是和height (3367, 9775932)对应的 MMR 的 rootMerkleMountainRange.CalculateRoot() 函数分析第一部分单叶特判if (leafCount 1 leaves.length 1 leaves[0].leaf_index 0) { return leaves[0].hash; }如果整个 MMR 只有一个叶子同时满足以下三个条件那 root 就是这个叶子本身的 hash不需要任何 proof 节点直接返回。leafCount 1MMR 只有 1 个叶子节点leaves.length 1需要验证的叶子节点数组长度为 1leaves[0].leaf_index 0所验证的第一个叶子节点的索引是 0从这个检查可以看出如果 MMR 的叶子数量只有 1 个的时候所传入的叶子索引值 leaves[0].leaf_index 应该为 0从攻击者的输入来看他所需要验证的 MMR 叶子节点数量为 1 leafCount: 1理应是符合这个分支的判定直接返回的。但是攻击者通过构造了一个恶意参数 requests[1].index: 1使得 leaves[0].leaf_index 0 的判断为 false从而绕过了这个判断。也正是这个关键步骤的绕过使得在后续的证明构建与验证过程中requests[1] 所对应的叶子节点始终没有参与到整个证明过程中。第二部分Peak 分解 迭代器初始化uint256[] memory subtrees subtreeHeights(leafCount); uint256 length subtrees.length; Iterator memory peakRoots Iterator(0, new bytes32); Iterator memory proofIter Iterator(0, proof);subtreeHeights(leafCount)把叶子数做二进制分解算出每座山的高度。比如leafCount 11 821返回[3, 1, 0]表示三座山高度分别是 3、1、0。然后初始化两个迭代器peakRoots是一个空数组用来收集每座山最终算出的 peak hashproofIter 是对传入的 proof 数组的游标后面每次需要 proof 节点时就从里面顺序取。由于传入的leafCount 1所以subtrees [0]proofIter指向的是传入的 root 值。第三部分主循环——逐座山处理uint256 current_subtree; for (uint256 p; p length; ) { uint256 height subtrees[p]; current_subtree 2 ** height;从左到右遍历每座山。current_subtree是一个累加器记录前 p1 座山总共覆盖了多少个叶子。比如第一座山高度 3覆盖2 ** 3 8个叶子第二座高度 1再加2 ** 1 2累计 10 个。这个值用来判断哪些待证明的叶子属于当前这座山。由于单个节点的 hight 为 0所以 current_subtree 1第四部分叶子分割 三路分支MmrLeaf[] memory subtreeLeaves new MmrLeaf; if (leaves.length 0) { (subtreeLeaves, leaves) leavesForSubtree(leaves, current_subtree); }leavesForSubtree以current_subtree为分界点把leaves切成两半leaf_index current_subtree的归入当前这座山subtreeLeaves剩下的留给后面的山重新赋值给leaves。然后进入三路分支if (subtreeLeaves.length 0) { if (proofIter.data.length proofIter.offset) { break; } else { push(peakRoots, next(proofIter)); } } else if (subtreeLeaves.length 1 height 0) { push(peakRoots, subtreeLeaves[0].hash); } else { push(peakRoots, CalculateSubtreeRoot(subtreeLeaves, proofIter, height)); }分支 A这座山里没有需要证明的叶子。那这座山的 peak hash 应该由 prover 直接提供——从 proof 里取一个。如果 proof 已经耗尽就 break 退出。分支 B这座山高度为 0只有一个叶子且恰好就是要证明的那个叶子。那 peak hash 就是叶子自身的 hash不需要任何 proof 节点。分支 C这座山里有需要证明的叶子且山的高度大于 0。调用CalculateSubtreeRoot做标准的 Merkle 多重证明——用subtreeLeaves和 proof 中的兄弟节点一层层向上合并算出这座山的 peak hash。三个分支都把结果 push 到peakRoots里。由于传入的leafCount: 1代表 MMR 只有 1 个叶子节点所以leavesForSubtree函数以current_subtree为分界点切成两半的值都是空的进入到subtreeLeaves.length 0分支把攻击者传入的 root 压入栈。第五部分Peak baggingunchecked { peakRoots.offset--; } while (peakRoots.offset ! 0) { bytes32 right previous(peakRoots); bytes32 left previous(peakRoots); unchecked { peakRoots.offset; } peakRoots.data[peakRoots.offset] keccak256( abi.encodePacked(right, left) ); }进入这段时peakRoots里已经收集了所有山的 peak hashoffset指向最后一个元素的下一个位置。先offset--把游标退到最后一个有效元素上。然后 while 循环从右向左折叠每次取出当前位置的值right和它左边的值left哈希后写回left的位置同时 offset 也回到了这个位置。下一轮再取这个新值和更左边的值继续折叠直到offset 0只剩一个值。用具体例子说明——假设peakRoots [P0, P1, P2]offset 从 2 开始第一轮取rightP2, leftP1算出bag1 H(P2, P1)写到位置 1第二轮取rightbag1, leftP0算出root H(bag1, P0)写到位置 0。循环结束。按照只有一个叶子节点处理只有一个 peak所以这部分会被跳过。第六部分返回 rootreturn peakRoots.data[0];经过 bagging最终结果就存在peakRoots.data[0]这就是整个 MMR 的 root hash。此时也就是返回了攻击者最开始传入的 root 值也就顺利地通过了验证了。在通过了 MMR 的校验以后HandlerV1合约会通过调用host.dispatchIncoming()函数执行request 中的内容也就是攻击者构建的获取 DOT 铸币权限的调用。接下来的操作就是铸造大量的 DOT并进行抛售获利。后记链上攻击事件不会等你有空的时候再发生发生了就只能抽空出来做攻击分析了。所以本篇文章重点在 rootcause 部分的内容对于跨链 ISMPMMR rootGovernance 这些部分的内容未能提及读者如果感兴趣的话可