Diem 区块链认证数据结构规范：Merkle 累加器、稀疏 Merkle 树与客户端验证实战

区块链金融科技【免费下载链接】diemDiem’s mission is to build a trusted and innovative financial network that empowers people and businesses around the world.项目地址https://gitcode.com/gh_mirrors/di/diem点击查看免费下载本文是 DiemLPNDiem Payment Network协议认证数据结构Authenticated Data Structure的完整技术规范解读。它详细说明 Diem 区块链中账本状态Ledger State与交易输出如何组织成不可篡改的历史以及客户端如何利用 Merkle 树根哈希作为认证器Authenticator在不可信服务器上安全地查询交易、账户状态与事件。读完本文你将掌握 Merkle 累加器与稀疏 Merkle 树的精确定义、证明格式与验证算法并理解TransactionInfo、LedgerInfo等核心数据结构在客户端验证链路中的实际用法。全文以 authenticated_data_structures.md 为主干并结合仓库源码如 storage/accumulator、types/src/proof进行纵深补充。概述版本化数据库与认证模型Diem 区块链的所有数据都存储在一个**单一版本化数据库single versioned database**中。版本号是一个无符号 64 位整数u64其数值等于系统已执行的交易数量。在每个版本i数据库保存一个三元组(Tᵢ, Oᵢ, Sᵢ)分别代表交易Transaction、交易输出Transaction Output与账本状态Ledger State。给定一个确定性的执行函数Apply三元组的含义是针对账本状态Sᵢ₋₁执行交易Tᵢ产生输出Oᵢ和新的账本状态Sᵢ即Apply(Sᵢ₋₁, Tᵢ) - ⟨Oᵢ, Sᵢ⟩创世交易T₀在空数据库上执行产生创世状态S₀。这一版本化模型是整个认证数据结构的语义基础每个版本都对应一棵完整的状态树快照而历史则通过累积的方式被不可篡改地记录下来。本规范文档主要回答三个问题账本状态与交易输出是什么、如何表示它们如何构成不可变的账本历史共识协议提交commit之后客户端在查询服务器时如何验证响应。交易的具体格式与Apply函数的完整定义由 Move 虚拟机规范另行描述原文档以 XXX 占位待补本文聚焦于认证数据结构本身。Merkle 树与证明基础Diem 协议中的认证数据结构全部基于 Merkle 树。与所有 Merkle 树一样树的根哈希是一个短小的认证器authenticator它构成对整个大树承载大量数据的绑定承诺binding commitment。当客户端向不可信服务器查询树的某一部分时服务器返回结果并附带一个短小的证明proof客户端用证明与已知的根哈希即可验证结果的正确性。哈希函数约定本文使用的哈希函数遵循 Diem 的 密码学规范。该规范明确Diem 内部哈希统一使用SHA3-256作为唯一算法用于所有内部数据结构的哈希计算同时引入**域分离domain separation**机制——每个 Diem 数据结构在哈希时都会拼接以其类型对应的域分隔符由 ASCII 前缀DIEM::与类型的序列化名称组成以避免序列化字节串的歧义和碰撞攻击。在 crates/diem-crypto/src/hash.rs 中可以看到占位符哈希的生成方式fn create_literal_hash(word: str) - HashValue { let mut s word.as_bytes().to_vec(); assert!(s.len() HashValue::LENGTH); s.resize(HashValue::LENGTH, 0); HashValue::from_slice(s).expect(Cannot fail) }即将字符串字节拼接补零至 32 字节得到一个没有已知原像pre-image的HashValue。Merkle 累加器与稀疏 Merkle 树的占位符哈希正是由此生成hash.rs。Merkle 累加器Merkle Accumulator定义Merkle 累加器是一种只追加append-only的二叉树用于存储对象列表。其规则如下每个叶子的值是一个HashValue等于对应对象的密码学哈希每个内部节点的值是一个HashValue等于其两个子节点哈希拼接后的哈希树的根哈希即根节点的值。树的确切形态由已追加的对象总数决定。对于存储k个对象的累加器令n为大于等于k的最小 2 的幂。累加器的结构等价于一棵具有n片叶子的完美二叉树其中最左边k片叶子对应所有对象最右边n-k片叶子是占位节点任何只含占位节点的子树都会被压缩成单个占位节点。占位节点的值定义为将字节数组bACCUMULATOR_PLACEHOLDER_HASH补零至 32 字节后作为HashValue。该哈希没有已知原像。上图展示了累加器随对象不断追加而演变的形态0 个到 5 个对象占位节点逐步被真实子树替换。从源码看累加器实现区分了冻结节点Frozen Node与非冻结节点Non-frozen Nodestorage/accumulator/src/lib.rs当一片叶子的所有后代都是非占位节点时该节点即冻结其哈希值在后续追加中不再改变。存储层只持久化冻结节点非冻结节点在访问时动态生成从而保证物理存储也是纯追加的append-only。APIMerkle 累加器支持以下操作原文档的 trait 定义trait MerkleAccumulatorT { /// Appends next object to the existing tree. fn append(self, object: T); /// Queries the index-th object. Returns the object with a proof if the /// object exists in the tree. Errors if the tree has less than index1 /// objects in total. fn get_with_proof(self, index: usize) - Result(T, AccumulatorProof); /// Similar to get_with_proof but queries a range of objects starting from /// first_index. fn get_range_with_proof( self, first_index: usize, num_objects: usize, ) - Result(VecT, AccumulatorRangeProof); }仓库中对应的实际实现位于 storage/accumulator/src/lib.rs提供了append、get_proof单叶包含证明、get_range_proof范围证明以及get_consistency_proof一致性证明用于证明完整累加器与较小累加器的一致性供状态同步场景使用。追加过程的关键实现是append_one把新叶子压入冻结子树根列表后按照叶子数二进制中尾部 1 的个数执行若干次合并最右侧两个子树操作storage/accumulator/src/lib.rs。AccumulatorProof 的格式与验证格式对于树中的任意对象从该对象到根节点存在一条路径。对象的AccumulatorProof由路径上的所有兄弟节点组成。兄弟节点从下到上排列即靠近底部的兄弟位于列表开头。struct AccumulatorProof { siblings: VecHashValue, }例如查询索引为 3 的对象O时兄弟列表为[A, B, C]其结构见下图在仓库中AccumulatorProof的定义位于 types/src/proof/definition.rs并有常量约束pub const MAX_ACCUMULATOR_PROOF_DEPTH: usize 63; pub const MAX_ACCUMULATOR_LEAVES: LeafCount 1 MAX_ACCUMULATOR_PROOF_DEPTH;即累加器最大叶子数被硬性限制为 2⁶³任何超过 63 个兄弟节点的证明都会被拒绝见下文验证第 1 步。验证流程验证时假定客户端知道累加器共有k个对象客户端已获得该累加器的根哈希H客户端查询第i个对象i k。服务器返回对象O与证明siblings后客户端按以下步骤验证确保证明中兄弟节点的数量不超过 63利用索引i判断每个兄弟节点是其父节点的左孩子还是右孩子对对象O求哈希得到对应叶子的值将叶子与证明中的兄弟节点逐层合并重建根节点并得到根哈希将计算出的根哈希与已知根哈希H比较当且仅当两者相等时对象与证明才被信任。验证伪代码如下fn verify_accumulator_proof( index: usize, known_root_hash: HashValue, obj: Object, proof: AccumulatorProof, ) - Result() { // We assume that the accumulator will never have more than 2^63 leaves, // which should be reasonable in real world scenarios. We do a sanity check // here to ensure that if the proof is too long, it gets rejected // immediately to avoid wasting further computation. ensure!(proof.siblings.len() 63); let mut current_hash hash(obj); for sibling in proof.siblings { if sibling.is_left_child(index) { current_hash hash(sibling || current_hash); } else { current_hash hash(current_hash || sibling); } } ensure!(current_hash known_root_hash); Ok(()) }注意sibling.is_left_child(index)的判断贯穿整个循环index的二进制位从低位到高位依次决定了每一层兄弟节点位于当前节点左侧还是右侧这也是证明验证无需任何树结构元数据、仅凭索引即可完成的原因。稀疏 Merkle 树Sparse Merkle Tree定义Diem 协议中的稀疏 Merkle 树用于存储键值映射所有键都是 256 位字节数组值可以是任意可序列化为二进制 blob 的对象。稀疏 Merkle 树同样是二叉树每片叶子对应映射中的一个条目。与只追加、不可变的 Merkle 累加器不同稀疏 Merkle 树支持更新已有条目、添加新条目和删除条目。给定一个键值映射稀疏 Merkle 树按前缀树prefix tree方式构造理论上可表示 2²⁵⁶ 个条目。为了直观文档使用 4 位键举例。下图展示了一棵含 3 个条目键为0b0100、0b1000、0b1011的树一棵 2²⁵⁶ 规模的树显然无法直接表示因此采用两项优化假设实际场景中树总是极端稀疏的占位节点压缩完全由空节点构成的子树被替换为一个占位节点见下图结合下文可知占位节点的值由字节串bSPARSE_MERKLE_PLACEHOLDER_HASH补零至 32 字节得到。单叶子树压缩只含一片叶子的子树被直接替换为对应的叶子节点见下图。叶子节点的值定义为SparseMerkleLeafNode对象的哈希struct SparseMerkleLeafNode { /// The 256-bit key is usually generated by hashing the original key, for /// the purpose of making sure the keys are evenly distributed, so a /// HashValue is used here. key: HashValue, /// Hash of the object. The reason of this being the hash of the value /// instead of the value itself is that, in some cases for a non-membership /// proof, this needs to be presented to the client. Using a hash avoids the /// need to present the client the entire blob, which could potentially be /// large. See later section on proof format for more details. value_hash: HashValue, }与 Merkle 累加器一致内部节点的值是左右子节点哈希拼接后的哈希根节点的值即树的根哈希。API稀疏 Merkle 树支持以下操作trait SparseMerkleTreeT { /// Inserts a new key-value pair into the tree if the key did not exist, /// otherwise update the value corresponding to the key. fn put(self, key: HashValue, value: T); /// Queries the object indexed by the key. Returns a tuple where the first /// element is the object, None if the key does not exist. The second /// element is the proof. fn get_with_proof(self, key: HashValue) - (OptionT, SparseMerkleProof); /// Similar to get_with_proof but queries a range of objects. fn get_range_with_proof(self, start_key: HashValue, end_key: HashValue) - (VecT, SparseMerkleRangeProof); }原文档同时指出虽然支持从树中删除条目但Diem 协议目前并不使用删除功能。SparseMerkleProof 的格式与验证格式稀疏 Merkle 树同时支持成员证明membership proof与非成员证明non-membership proofstruct SparseMerkleProof { leaf: OptionSparseMerkleLeafNode, siblings: VecHashValue, }成员证明场景当被查询的键存在于树中时证明与AccumulatorProof非常相似——siblings是从对象到根节点路径上的所有兄弟节点leaf为Some(node)其中 node 正是被查询的叶子节点。严格来说此时leaf并非必需键已知值哈希可由对象算出但保留它可以使成员证明与非成员证明的格式统一。仍以上面那棵 3 条目的树为例若客户端查询键0b1011服务器返回对象O证明中的leaf为Some(0b1011, Hash(O))siblings为[A, B, C]如下图所示非成员证明场景当被查询的键不存在时从根节点沿着键指定的路径向下根据最终遇到的叶子节点有两种情况若查询的键是0b1100沿路径最终到达节点B一个占位节点。这说明树中没有任何键具有0b11前缀也就意味着0b1100不存在。此时leaf为Nonesiblings为[X, C]。若查询的键是0b1010沿路径最终到达节点O有数据键为0b1011。这说明0b1011是该子树中唯一的键因此0b1010不存在——否则此位置会出现一个内部节点而非叶子O。此时leaf为Some(0b1011, Hash(O))siblings为[A, B, C]。注意这里使用的是对象O的哈希而非O本身这可以在对象很大时显著减小证明体积。验证流程验证时假定客户端已获得该稀疏 Merkle 树的根哈希H客户端查询键K。服务器返回对象O或None与证明后客户端按以下步骤验证若服务器声称键存在proof.leaf必须是Some。检查leaf.key是否等于K、leaf.value_hash是否等于对象的哈希然后以Hash(leaf)作为叶子节点的值。若服务器声称键不存在a) 若proof.leaf为Some检查leaf.key不等于K并检查K与leaf.key的公共前缀位长度不小于证明中兄弟节点的数量这保证了该叶子确实位于键K的搜索路径末端而非被任意修剪然后以Hash(leaf)作为叶子节点的值。b) 若proof.leaf为None以占位节点的值作为叶子节点的值。利用键K判断每个兄弟节点是父节点的左孩子还是右孩子有了叶子节点值后将其与兄弟节点逐层合并重建根节点得到根哈希将计算出的根哈希与已知根哈希H比较当且仅当两者相等时对象与证明才被信任。验证伪代码如下fn verify_sparse_merkle_proof( key: HashValue, known_root_hash: HashValue, object: OptionObject, proof: SparseMerkleProof, ) - Result() { // Since the depth of the sparse Merkle tree is at most 256 (the length of // HashValue in bits), the proof should not consist of more than 256 // siblings. Reject very long proofs immediately to avoid wasting further // computation. ensure!(proof.siblings.len() 256); let leaf match object { Some(obj) { match proof.leaf { Some(leaf_node) { ensure!(leaf_node.key key); ensure!(leaf_node.value_hash hash(obj)); hash(leaf_node) } None bail!(Invalid proof.), } } None { match proof.leaf { Some(leaf_node) { ensure!(leaf_node.key ! key); ensure!(common_prefix_bits_len(key, leaf_node.key) proof.siblings.len()); hash(leaf_node) } None SPARSE_MERKLE_PLACEHOLDER_HASH, } } }; let mut current_hash leaf; for sibling in proof.siblings { if sibling.is_left_child(key) { current_hash hash(sibling || current_hash); } else { current_hash hash(current_hash || sibling); } } ensure!(current_hash known_root_hash); Ok(()) }由于HashValue长度为 256 位即 32 字节稀疏 Merkle 树深度最多为 256因此证明中兄弟节点数超过 256 会被直接拒绝。Diem 数据结构由 Merkle 原语构建 LPN上一节描述了构成 LPNDiem Payment Network认证数据结构的两大基本构件。本节说明如何用它们构建 LPN 的具体对象。这些对象的类型定义位于 types/src 下的 Rust 代码中例如AccountStateBlob、TransactionInfo等并通过 BCS 序列化与上述哈希约定参与认证。账本状态Ledger State账本状态代表 Diem 生态的事实真相包括在给定版本下每个用户持有的代币数量。每个验证者validator必须知道最新版本的账本状态才能执行新交易。具体而言账本状态是一个从AccountAddress到二进制 blobAccountStateBlob表示账户状态的映射type LedgerState SparseMerkleTreeAccountStateBlob;每个AccountAddress被哈希为 256 位的HashValue然后将每个(hash(address), account_state_blob)元组作为键值对插入稀疏 Merkle 树。基于密码学哈希函数的性质无论地址如何生成所得的稀疏 Merkle 树都以压倒性概率是平衡的。这棵稀疏 Merkle 树代表整个账本状态其根哈希即状态根哈希state root hash——同一版本下任何账户状态都可以用状态根哈希作为认证器进行验证。当交易执行后状态树被更新、新树被创建时高效实现通常会复用前一版本中未变化的部分形成持久化数据结构persistent data structure即写时复制Copy-on-Write模式如下图所示账户Accounts逻辑层面一个账户是 Move 资源和模块的集合物理层面一个账户是访问路径access path到字节数组值的有序映射。账户存入账本状态时该有序映射使用BCSBinary Canonical Serialization序列化成二进制 blobAccountStateBlob再插入稀疏 Merkle 树type Path Vecu8; struct AccessPath { address: AccountAddress, path: Path, } type AccountState BTreeMapPath, Vecu8; struct AccountStateBlob { blob: Vecu8, } impl FromAccountState for AccountStateBlob { fn from(account_state: AccountState) - Self { Self { blob: bcs::to_bytes(account_state), } } }关于访问路径的精确定义原文档以 TODO: link to definition of access path 标注待补可结合 Move 虚拟机与 Move 框架规范进一步了解。交易与交易输出Transaction and Transaction Output每笔交易会更新一个或多个账户从而产生新的账本状态。虽然账本状态的变化是交易的直接输出但为了客户端查询便利还额外生成了三类信息交易发出的事件列表contract events交易执行期间消耗的 gas 数量指示交易执行结果的主要状态码major status code。事件Events每笔交易发出的事件列表存储在独立的 Merkle 累加器MerkleAccumulatorContractEvent中。事件按 Move VM 输出的顺序依次追加到累加器。该累加器的根哈希即事件根哈希event root hash充当任意事件的认证器。ContractEvent的详细定义见 公共数据结构规范其V0版本包含key、sequence_number、type_tag与event_data四个字段。账本历史Ledger History账本历史由所有已提交的交易及其输出构成。Diem 使用TransactionInfo类型同时表示交易与其输出因此任意TransactionInfo对象都可以作为对应交易及其输出的认证器——包括执行该交易后每个账户的状态struct TransactionInfo { /// The hash of the transaction. transaction_hash: HashValue, /// The root hash of the ledger state at the end of this transaction. state_root_hash: HashValue, /// The root hash of the Merkle accumulator that stores all the events /// emitted by this transaction. event_root_hash: HashValue, /// The amount of gas consumed during this transaction execution. gas_used: u64, /// The major status code that indicates the transaction execution result. major_status: StatusCode, }账本历史本身是一个 Merkle 累加器。它以单个条目表示创世交易与创世状态开始随着更多交易被提交上链越来越多的TransactionInfo对象被追加到累加器中type LedgerHistory MerkleAccumulatorTransactionInfo;因此账本历史累加器的根哈希可以认证所有TransactionInfo对象进而认证链上发生的一切——包括所有交易、当前与历史账本状态、所有发出的事件。网络运行时共识协议会周期性地分发带签名的LedgerInfo其中包含该根哈希客户端即可用它验证任何链接到累加器根的数据。LedgerInfo及其签名封装LedgerInfoWithSignatures的定义见 公共数据结构规范LedgerInfo包含commit_info: BlockInfo含version、executed_state_id等与consensus_data_hash当超过 2f 个验证者对LedgerInfo签名后即构成具有法定效力的LedgerInfoWithSignatures其signatures为按账户地址排序的 Ed25519 签名映射且要求签名总投票权 2f。客户端认证实战三个典型场景前文已说明 Merkle 累加器与稀疏 Merkle 树两大构件以及基于它们构建的 Diem 数据结构。下面给出几个客户端利用这些数据结构认证服务器响应的具体示例。本节始终假定客户端已获得最新的LedgerInfo及其足够多的签名因此客户端知道账本历史累加器的最新根哈希它是LedgerInfo结构的一部分。场景一证明一笔交易要证明交易T是在版本v提交的交易使用TransactionInfoWithProof。验证只需两步先用从根到叶子的累加器证明验证TransactionInfo对象的正确性再利用其中的交易哈希验证交易本身struct TransactionInfoWithProof { // The accumulator proof from the root of the ledger history accumulator to // the TransactionInfo object at version v. This proves that the // transaction_info object below is correct. ledger_info_to_transaction_info_proof: AccumulatorProof, // The TransactionInfo object at version v. Since it has the hash of the // transaction, verifying that transaction_info.transaction_hash matches // the tranasction should convince the verifier that the transaction is // correct. transaction_info: TransactionInfo, }即第一层累加器证明账本历史根 →TransactionInfo保证了transaction_info对象可信transaction_info.transaction_hash与交易T的哈希一致则证明T确实以版本v提交。场景二证明一个账户状态要证明版本v时某账户的状态使用AccountStateProof。首先按场景一的方式验证版本v处的TransactionInfo对象然后将TransactionInfo内的状态根哈希与从交易信息到账户的稀疏 Merkle 证明结合验证账户状态struct AccountStateProof { transaction_info_with_proof: TransactionInfoWithProof, transaction_info_to_account_proof: SparseMerkleProof, }这条链路清晰地展示了两个 Merkle 原语的配合累加器证明回答这个版本的TransactionInfo是否真实稀疏 Merkle 证明回答在这个状态下该账户的余额/资源是否真实。二者级联最终锚定到共识签名的LedgerInfo根哈希上构成完整的信任链。场景三证明事件与历史数据扩展虽然原文档正文以证明交易与证明账户状态两个示例收尾但从前文的数据结构可以看出更一般的模式由于TransactionInfo内含event_root_hash客户端可以通过账本历史累加器证明 →TransactionInfo→ 事件累加器证明的级联验证任意版本任意事件的真实性同理历史版本的账户状态也可以通过历史版本的TransactionInfo.state_root_hash配合该版本的状态树证明来验证。所有验证最终都收敛到同一个共识锚点——被超过 2f 验证者签名的LedgerInfo根哈希。实现参考在仓库中定位关键代码如果你想深入阅读源码以下路径可供参考Merkle 累加器核心算法storage/accumulator/src/lib.rs追加、证明生成、一致性证明、范围证明支持HashReader抽象将树与存储解耦内存态累加器InMemoryAccumulatortypes/src/proof/accumulator/mod.rs只存储各满子树的根最多 O(log n) 个节点不可变追加返回新实例证明类型定义与深度约束types/src/proof/definition.rsAccumulatorProof、SparseMerkleProof、MAX_ACCUMULATOR_PROOF_DEPTH 63、MAX_ACCUMULATOR_LEAVES 2^63占位符哈希crates/diem-crypto/src/hash.rsACCUMULATOR_PLACEHOLDER_HASH、SPARSE_MERKLE_PLACEHOLDER_HASH由字符串补零生成无已知原像哈希与密码学约定specifications/crypto/README.mdSHA3-256、域分离、BCS 序列化相关数据结构定义公共数据结构规范AccountAddress、HashValue、LedgerInfo、LedgerInfoWithSignatures、ContractEvent等。使用注意事项本文描述的证明验证逻辑要求客户端预先可信地获得根哈希。在 Diem 网络中这一信任根来自共识层只有被超过 2f 验证者签名即总投票权 2f的LedgerInfoWithSignatures才构成可验证的提交承诺参见 data_structures.md 与共识规范累加器证明的兄弟数上限 63 对应MAX_ACCUMULATOR_LEAVES 2^63稀疏 Merkle 证明的兄弟数上限 256 对应HashValue的位长——两者都是验证时的强制安全检查用于抵御超长证明导致的资源浪费稀疏 Merkle 树当前不支持删除操作的使用协议层未启用状态更新通过写时复制复用未变化子树形成持久化结构。通过本文你应当已经能够读懂 Diem 认证数据结构的完整设计从 Merkle 累加器与稀疏 Merkle 树两大原语到账本状态、交易输出与账本历史的组装再到客户端验证交易与账户状态的具体流程。这套机制是 Diem 区块链无需信任服务器即可验证一切数据的基石。赞分享区块链金融科技【免费下载链接】diemDiem’s mission is to build a trusted and innovative financial network that empowers people and businesses around the world.项目地址https://gitcode.com/gh_mirrors/di/diem点击查看免费下载相关推荐Aptos累加器Merkle树与区块链状态证明的终极解决方案Aptos累加器Merkle树与区块链状态证明的终极解决方案 还在为区块链状态验证的复杂性和低效性而烦恼吗Aptos累加器Merkle Accumulat区块链Web3AionUi命令行工具使用指南高级用户必备技巧AionUi命令行工具使用指南高级用户必备技巧 AionUi是一款免费、本地运行的开源GUI应用专为Gemini CLI、Claude Code、Codex人工智能AI 应用大模型AI Agent交互助手前端Diem 区块链的 Merkle 证明Proof数据完整性验证的原理、机制与源码实现Diem 区块链的 Merkle 证明Proof数据完整性验证的原理、机制与源码实现 Proof证明是 Diem 区块链上验证数据真实性的核心机制所区块链金融科技创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考