异步Merkle Tree

2024-01-18 16:20
文章标签 异步 tree merkle

本文主要是介绍异步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。

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

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

在这里插入图片描述

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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/619566

相关文章

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Java 中实现异步的多种方式

《Java中实现异步的多种方式》文章介绍了Java中实现异步处理的几种常见方式,每种方式都有其特点和适用场景,通过选择合适的异步处理方式,可以提高程序的性能和可维护性,感兴趣的朋友一起看看吧... 目录1. 线程池(ExecutorService)2. CompletableFuture3. ForkJoi

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Spring Boot 中正确地在异步线程中使用 HttpServletRequest的方法

《SpringBoot中正确地在异步线程中使用HttpServletRequest的方法》文章讨论了在SpringBoot中如何在异步线程中正确使用HttpServletRequest的问题,... 目录前言一、问题的来源:为什么异步线程中无法访问 HttpServletRequest?1. 请求上下文与线

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法:wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一:使用wait/notify + synchronized代码示例关键

springboot的调度服务与异步服务使用详解

《springboot的调度服务与异步服务使用详解》本文主要介绍了Java的ScheduledExecutorService接口和SpringBoot中如何使用调度线程池,包括核心参数、创建方式、自定... 目录1.调度服务1.1.JDK之ScheduledExecutorService1.2.spring

异步线程traceId如何实现传递

《异步线程traceId如何实现传递》文章介绍了如何在异步请求中传递traceId,通过重写ThreadPoolTaskExecutor的方法和实现TaskDecorator接口来增强线程池,确保异步... 目录前言重写ThreadPoolTaskExecutor中方法线程池增强总结前言在日常问题排查中,

微服务架构之使用RabbitMQ进行异步处理方式

《微服务架构之使用RabbitMQ进行异步处理方式》本文介绍了RabbitMQ的基本概念、异步调用处理逻辑、RabbitMQ的基本使用方法以及在SpringBoot项目中使用RabbitMQ解决高并发... 目录一.什么是RabbitMQ?二.异步调用处理逻辑:三.RabbitMQ的基本使用1.安装2.架构

如何使用celery进行异步处理和定时任务(django)

《如何使用celery进行异步处理和定时任务(django)》文章介绍了Celery的基本概念、安装方法、如何使用Celery进行异步任务处理以及如何设置定时任务,通过Celery,可以在Web应用中... 目录一、celery的作用二、安装celery三、使用celery 异步执行任务四、使用celery