异步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模板网!

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

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

相关文章

  • GraphSAGE的基础理论

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

    2023年04月15日
    浏览(51)
  • API安全基础理论

    API(Application Programming Interface,应用程序编程接口)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件的以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。通过淘宝API,就算不知道如何操作,也能将产品或服务与其他产品或服务进

    2024年02月13日
    浏览(47)
  • SaaS 架构基础理论(一)

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

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

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

    2024年02月15日
    浏览(56)
  • 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日
    浏览(40)
  • FPGA时序约束--基础理论篇

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

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

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

    2024年02月09日
    浏览(84)
  • fMRI基础理论知识学习

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

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

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

    2024年02月06日
    浏览(44)
  • 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日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包