电商网站建设要多少钱,工程项目管理系统,沈阳网站建设简维,免费引流推广方法1. 引言
前序博客#xff1a;
利用多核的Rust快速Merkle tree
Anoushk Kharangate 2023年论文《Asynchronous Merkle Trees》#xff0c;其对Merkle tree数据结构进行修改#xff0c;使得可跨多线程异步计算。
开源代码实现见#xff1a;
https://github.com/anoushk1…1. 引言
前序博客
利用多核的Rust快速Merkle tree
Anoushk Kharangate 2023年论文《Asynchronous Merkle Trees》其对Merkle tree数据结构进行修改使得可跨多线程异步计算。
开源代码实现见
https://github.com/anoushk1234/async-merkle-treeRust
Merkle tree应用广泛有各种变种如
Jellyfish Merkle TreeSparse Merkle Tree
但这些都存在一个共同的问题
当用Merkle Tree来处理大数据集时计算该tree的开销将大幅增加。此外插入单个叶子节点将需要重构整棵树。
在某些情况下插入叶子节点时的计算时间应尽可能短且对于数据并行处理的场景需要能异步计算。《Asynchronous Merkle Trees》论文中
提出了并行处理一组数据批量异步所构建的Merkle Tree在每次插入时无需重新计算该tree。
2. Asynchronous Merkle TreesAMT
Asynchronous Merkle TreesAMT有如下关键属性
1节点类型包含3种特殊节点 1.1Digest节点仅简单用作另一batch node的placeholder。1.2Layer CheckpointLC节点1.3Compound节点 2个LC节点组成一个Compound节点。一个LC节点和一个Compound节点组成另一Compound节点。 2排序每个特殊节点必须包含一个order bit以表示是其父节点的左子节点还是右子节点。3Segregation隔离每个节点必须有一个batch bit以表示其属于哪个batch。
某Merkle Tree T T T其遵循如下要求
1 T T T的高度为 h h h其中 h log 2 ( n ) h\log_2(n) hlog2(n) n n n为叶子节点数2 T T T必须最多有 M M M个节点其中 M ∑ n h n 2 M\sum_{n}^{h}\frac{n}{2} M∑nh2n3叶子节点表示为 N i N_i Ni其中 { i ∈ N ∣ 0 ≤ i ≤ 2 D } \{i\in N|0\leq i \leq 2^D\} {i∈N∣0≤i≤2D}
将以上Merkle Tree T T T扩展为创建AMT其遵循如下要求
1异步附加的叶子称为Batches B B Bbatches的数量和其叶子必须提取已知。2以大量Digest Nodes D i D_i Di来初始化该treeDigest Nodes D i D_i Di用作其它batches节点的placeholder。 如上图所示以3层Merkle tree为例当附加红色batch叶子时需重新计算 N 11 N_{11} N11和 N 12 N_{12} N12无法异步附加。 对应的AMT为4层 对应每个节点必须包含如下数据
1Batch一个整数值用于表示该节点属于哪个batch 对于Compound节点可将其设置为与现有batch id不冲突的某特殊整数值来表示该节点不属于特定batch。 2Order一个整数值为0或1以表示左节点或右节点。3Data实际的数据哈希值。 Merkle tree系列博客
利用多核的Rust快速Merkle treeMerkle tree proofMerkle tree及其在区块链等领域的应用Sparse Merkle Tree以太坊EIP-1186RPC-Method to get Merkle Proofs - eth_getProofproof of solvency偿付能力证明方案以太坊中的modified Merkle Patricia Trie以太坊Eth2 deposit merkle treePolygon zkEVM中的Merkle treeMerkle tree for non-membership proofPolygon zkEVM Merkle tree的circom约束Zcash中的merkle tree
