异步Merkle Tree

这篇具有很好参考价值的文章主要介绍了异步Merkle Tree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 引言

前序博客:

  • 利用多核的Rust快速Merkle tree

Anoushk Kharangate 2023年论文《Asynchronous Merkle Trees》,其对Merkle tree数据结构进行修改,使得可跨多线程异步计算。

开源代码实现见:

  • https://github.com/anoushk1234/async-merkle-tree(Rust)

Merkle tree应用广泛,有各种变种,如:

  • Jellyfish Merkle Tree
  • Sparse Merkle Tree

但这些都存在一个共同的问题:

  • 当用Merkle Tree来处理大数据集时,计算该tree的开销,将大幅增加。此外,插入单个叶子节点,将需要重构整棵树。

在某些情况下,插入叶子节点时的计算时间,应尽可能短,且对于数据并行处理的场景,需要能异步计算。《Asynchronous Merkle Trees》论文中:

  • 提出了并行处理一组数据,批量异步所构建的Merkle Tree,在每次插入时,无需重新计算该tree。

2. Asynchronous Merkle Trees(AMT)

Asynchronous Merkle Trees(AMT)有如下关键属性:

  • 1)节点类型:包含3种特殊节点:
    • 1.1)Digest节点:仅简单用作另一batch node的placeholder。
    • 1.2)Layer Checkpoint(LC)节点
    • 1.3)Compound节点:
      • 2个LC节点组成一个Compound节点。
      • 一个LC节点和一个Compound节点,组成另一Compound节点。
  • 2)排序:每个特殊节点必须包含一个order bit,以表示是其父节点的左子节点,还是右子节点。
  • 3)Segregation隔离:每个节点必须有一个batch bit,以表示其属于哪个batch。

某Merkle Tree T T T,其遵循如下要求:

  • 1) T T T的高度为 h h h,其中 h = log ⁡ 2 ( n ) h=\log_2(n) h=log2(n) n n n为叶子节点数
  • 2) T T T必须最多有 M M M个节点,其中 M = ∑ n h n 2 M=\sum_{n}^{h}\frac{n}{2} M=nh2n
  • 3)叶子节点表示为 N i N_i Ni,其中 { i ∈ N ∣ 0 ≤ i ≤ 2 D } \{i\in N|0\leq i \leq 2^D\} {iN∣0i2D}

将以上Merkle Tree T T T,扩展为,创建AMT,其遵循如下要求:

  • 1)异步附加的叶子称为Batches B B B,batches的数量和其叶子必须提取已知。
  • 2)以大量Digest Nodes D i D_i Di来初始化该tree,Digest Nodes D i D_i Di用作其它batches节点的placeholder。

异步Merkle Tree,基础理论,基础理论
如上图所示,以3层Merkle tree为例,当附加红色batch叶子时,需重新计算 N 11 N_{11} N11 N 12 N_{12} N12,无法异步附加。
对应的AMT为4层:
异步Merkle Tree,基础理论,基础理论
异步Merkle Tree,基础理论,基础理论
对应每个节点必须包含如下数据:

  • 1)Batch:一个整数值,用于表示该节点属于哪个batch
    • 对于Compound节点,可将其设置为(与现有batch id不冲突的)某特殊整数值,来表示该节点不属于特定batch。
  • 2)Order:一个整数值,为0或1,以表示左节点或右节点。
  • 3)Data:实际的数据哈希值。

异步Merkle Tree,基础理论,基础理论文章来源地址https://www.toymoban.com/news/detail-801880.html

Merkle tree系列博客

  • 利用多核的Rust快速Merkle tree
  • Merkle tree proof
  • Merkle tree及其在区块链等领域的应用
  • Sparse Merkle Tree
  • 以太坊EIP-1186:RPC-Method to get Merkle Proofs - eth_getProof
  • proof of solvency(偿付能力证明)方案
  • 以太坊中的modified Merkle Patricia Trie
  • 以太坊Eth2 deposit merkle tree
  • Polygon zkEVM中的Merkle tree
  • Merkle tree for non-membership proof
  • Polygon zkEVM Merkle tree的circom约束
  • Zcash中的merkle tree

到了这里,关于异步Merkle Tree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据库基础理论

    数据:描述事务的符号记录,包含但不限于数字、 文字、图形、图像、声音、语言等。数据有多重形式,它们都可以经过数字化后存入计算机。 数据库:数据仓库。是长期存放在计算机内、有组织、可共享的大量数据的集合。数据库中的数据按照一定数据模型组织、描述和

    2024年01月21日
    浏览(50)
  • GraphSAGE的基础理论

    引入: GCN的缺点: 从大型网络中学习的困难 :GCN在嵌入训练期间需要所有节点的存在。这不允许批量训练模型。 推广到看不见的节点的困难 :GCN假设单个固定图,要求在一个确定的图中去学习顶点的embedding。但是,在许多实际应用中,需要快速生成看不见的节点的嵌入。

    2023年04月15日
    浏览(55)
  • SaaS 架构基础理论(一)

    《互联网时代的软件革命 SaaS架构设计》学习笔记 云计算提供的强大软硬件环境和基础服务,将逐渐成为支撑SaaS应用的基础设施。各个云计算平台所包含的大量具有自身特色的公共服务,将为SaaS应用的开发提供了丰富的资源。而统一整合各个云计算平台的公共服务,也成为

    2024年02月02日
    浏览(47)
  • 图论算法|深度优先搜索理论基础|797.所有可能的路径|广度优先搜索BFS理论基础|200. 岛屿数量

    dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 递归和回溯是相辅相成的 https://leetcode.cn/problems/all-paths-from-source-to-target/ 有向无环图(DAG): 有环无向图是指在图中存在至少一个环(Cycle)的无向图。环是

    2024年02月15日
    浏览(60)
  • FPGA时序约束--基础理论篇

    FPGA开发过程中,离不开时序约束,那么时序约束是什么?简单点说,FPGA芯片中的逻辑电路,从输入到输出所需要的时间,这个时间必须在设定的时钟周期内完成,更详细一点,即需要满足建立和保持时间。 时序约束可以让VIvado和Quartus等FPGA开发软件,在布线时检测综合出来

    2024年02月10日
    浏览(38)
  • 区块链原理与基础理论知识

    ​ 来源区块链 - 区块链基础知识 | Microsoft Learn,并结合自己的理解以及Chatgpt的帮助进行了梳理和改进,使其更易读和理解。 早在 1999 年,文件共享网络 Napster 就出现了,可方便用户在混合对等网络(之所以使用“混合”一词是因为它使用了中央目录服务器)上轻松共享音频

    2024年02月06日
    浏览(49)
  • k8s基础理论

    1.核心对象 NameSpaces Pod ServiceAccount ReplicaSet Deployment service和ingress persistenvolume和persistenvolumeclaim 2.控制器 etcd apiserver controller manager scheduler kubelet kube-proxy 3.相关插件 容器运行时 网络插件 flannel calico 4.关于pod生命周期 pod创建过程 pod删除过程 pod的质量保证 pod的节点亲和性 pod的节

    2024年02月04日
    浏览(49)
  • 音视频入门基础理论知识

    本节介绍了音视频的基本原理知识以及编码相关概念。 视频(Video) 泛指将一系列静态影像以电信号的方式加以捕捉、 纪录、 处理、 储存、 传送与重现的各种技术。 连续的图像变化 每秒超过 24 帧(frame,fps) 画面以上时, 根据 视觉暂留原理 , 人眼无法辨别单幅的静态画

    2024年02月09日
    浏览(85)
  • OSPFv3基础理论讲解

    目录 OSPF基础 OSPFv3概述 Router-id 链路本地地址在OSPFv3中的应用 OSPFv3的LSA与v2的区别 LSA头部信息 Router-LSA(1类) Network-LSA(2类) Intra-Area-Prefix-LSA(9类) Link LSA(8类) 产生几条1/2/8/9类LSA OSPFv3支持多实例 OSPFv3尾部跟踪认证 由于OSPF的扩展性不强,为了支持IPv6地址,重新定义了

    2023年04月19日
    浏览(41)
  • fMRI基础理论知识学习

    时隔多年,再次上线,重新经营csdn。自读研以来,不是干饭就是摆烂,实在颓废,能重新开始写博客,已然不易。在这里立下flag,争取以后每周都能写点什么东西,一来锻炼文笔,二来记录学习历程 我的研究方向与功能磁共振成像fMRI有关,此前从未接触过该领域,完全是从

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包