CN110800255B

CN110800255B - 更新区块链世界状态默克尔帕特里夏字典树子树

Info

Publication number: CN110800255B
Application number: CN201980003023.9A
Authority: CN
Inventors: 张文彬
Original assignee: Alibaba Group Holding Ltd; Advanced New Technologies Co Ltd
Current assignee: Ant Chain Technology Co ltd
Priority date: 2019-03-04
Filing date: 2019-03-04
Publication date: 2023-03-31
Anticipated expiration: 2039-03-04
Also published as: US10691676B1; WO2019101229A3; EP3593490A4; JP2020522149A; WO2019101229A2; TWI706666B; CN110800255A; AU2019203849B2; KR102322729B1; EP3593490A2; CA3058225C; AU2019203849C1; KR20200107772A; CA3058225A1; JP6830549B2; SG11201908978UA; TW202040964A; AU2019203849A1

Abstract

本文实施方式包括通过多次迭代遍历世界状态MPT的子树，在每次迭代，针对子树的当前节点，执行以下操作之一：将世界状态MPT的当前节点添加到更新树，并且移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为所述扩展节点引用的节点，将世界状态MPT的当前节点添加到更新树，并且移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为子树的当前节点的槽指向的节点，将更新树发送到用于使用更新树更新本地存储的子树的客户端。

Description

更新区块链世界状态默克尔帕特里夏字典树子树

背景技术

分布式账本系统(DLS)，也可称为共识网络和/或区块链网络，使参与的实体能够安全地且不可篡改地存储数据。在不引用任何特定用例的情况下，DLS通常被称为区块链网络。区块链网络的示例类型可以包括公有区块链网络、私有区块链网络和联盟区块链网络。公有区块链网络向所有实体开放使用DLS，并开放参与共识处理。私有区块链网络针对特定实体提供，该实体集中控制读写权限。联盟区块链网络针对选择的实体组群提供，该实体组群控制共识处理，并且联盟区块链网络包括访问控制层。

哈希树可以用于区块链网络存储信息。例如，区块链网络的世界状态(例如，区块链网络中的节点(账户)的状态)可以被存储在哈希树中。哈希树的示例包括维护区块链网络内的所有节点(账户)的世界状态的世界状态默克尔帕特里夏字典树(Merkle PatriciaTrie，MPT)。随着区块链网络增长，世界状态信息相应地增加，从而产生复杂的数据密集型哈希树。

不是区块链网络内的所有节点都需要维护区块链的世界状态。例如，参与将交易添加到区块链网络内的区块链的所谓的共识节点(全量客户端)维护世界状态哈希树以能够参与共识处理。仅在区块链网络内进行交易的其他节点(轻量客户端)不需要维护世界状态，或者甚至不需要知道世界状态。然而，这样的节点需要知道他们自己的状态和在区块链内与他们交易的其他节点的状态(例如，局部状态)。考虑到世界状态哈希树的大小和复杂度以及轻量客户端使用的设备的资源限制，需要资源和带宽高效的数据结构以及用于更新数据结构以维护区块链网络的局部状态的处理。

发明内容

本文实施方式包括一种计算机实现的方法，用于生成世界状态默克尔帕特里夏字典树MPT的子树并更新该子树。

在一些实施方式中，操作包括：区块链网络的共识客户端创建包括世界状态MPT的根节点并且最初没有其他节点的更新树；该共识客户端多次迭代地对子树的至少一部分执行遍历，在每次迭代中，针对该子树的当前节点，执行以下操作之一：确定该子树的当前节点和该世界状态MPT的当前节点是叶节点并且他们的值不相等，作为响应，将该世界状态MPT的当前节点添加到该更新树，确定该子树的该当前节点和该世界状态MPT的该当前节点是扩展节点，作为响应，将该世界状态MPT的该当前节点添加到该更新树，并且移动至遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为所述扩展节点引用的节点，确定该子树的当前节点和该世界状态MPT的当前节点是分支节点，并且他们的值不相等，作为响应，将该世界状态MPT的当前节点添加到更新树，确定该子树的当前节点和该世界状态MPT的当前节点是分支节点，并且他们的值相等，作为响应，移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为该子树的当前节点的槽指向的节点；由该共识客户端将该子树的该更新树发送到该区块链网络的非共识客户端，该非共识客户端使用该更新树更新本地存储的子树以提供更新的子树，该更新的子树提供与该非共识客户端关联的账户的状态。其他实施方式包括相应系统、设备和编码在计算机存储设备上被配置为执行方法的操作的计算机程序。

这些和其他实施方式均可可选地包括以下特征中的一个或多个：操作还包括在至少一次迭代期间，查找世界状态MPT中的相应节点，并提供搜索路径，该搜索路径中的一个或多个节点被标记为中间节点，并被标记为不在子树中；响应于确定该子树的当前节点和该世界状态MPT的当前节点是分支节点，并且当前迭代是该子树的当前节点被考虑的首次迭代，将该子树的当前节点的值与该世界状态MPT的当前节点的值进行比较；响应于确定该子树的当前节点是根节点，终止遍历；该本地存储的子树是通过一次或多次地用更新树的节点替换该子树的节点，并将该更新树的节点插入该子树来更新的；响应于共识客户端从非共识客户端接收到的请求而创建该更新树；响应于确定该子树的根节点的值与该世界状态MPT的该根节点的值不同而创建该更新树。

本文还提供了耦接到一个或多个处理器并且其上存储有指令的一个或多个非暂态计算机可读存储介质，当所述指令由所述一个或多个处理器执行时，所述指令将促使所述一个或多个处理器按照本文提供的方法的实施例执行操作。

本文还提供了用于实施本文提供的所述方法的系统。该系统包括一个或多个处理器以及耦接到所述一个或多个处理器并且其上存储有指令的计算机可读存储介质，当所述指令由所述一个或多个处理器执行时，所述指令将促使所述一个或多个处理器按照本文提供的方法的实施例执行操作。

应了解，依据本文的方法可以包括本文描述的方面和特征的任意组合。也就是说，根据本文的方法不限于本文具体描述的方面和特征的组合，还包括所提供的方面和特征的任意组合。

以下在附图和描述中阐述了本文的一个或多个实施例的细节。根据文和附图以及权利要求，本文的其他特征和优点将显而易见。

附图说明

图1描绘了可用于执行本文实施方式的环境的示例。

图2描绘了根据本文实施方式的概念架构的示例。

图3描绘了世界状态默克尔帕特里夏字典树(Merkle Patricia Trie，MPT)的示例。

图4描绘了根据本文实施方式的基于图3的示例性世界状态MPT生成的子树的示例。

图5A和图5B描绘了可根据本文实施方式执行的处理的示例。

图6描绘了包括更新的图3的示例世界状态MPT。

图7描绘了根据本文实施方式的基于图6的示例性世界状态MPT的包括更新的图4的子树。

图8A和图8B描绘了可根据本文实施方式执行的处理的示例。

图9描绘了根据本文实施方式的装置的模块的示例。

图10描绘了根据本文实施方式的装置的模块的示例。

各附图中的相同附图标记表示相同的元件。

具体实施方式

本文实施方式包括计算机实现的方法，用于生成世界状态默克尔帕特里夏字典树(MPT)的子树并更新该子树。在一些实施方式中，操作包括通过多次迭代遍历世界状态MPT的子树，并且在每次迭代中，针对该子树的当前节点，执行以下操作之一：将世界状态MPT的当前节点添加到更新树，并移动至遍历的下一次迭代，其将子树的当前节点设置为由扩展节点引用的节点；将世界状态MPT的当前节点添加到更新树，并移动至遍历的下一次迭代，其将子树的当前节点设置为子树的当前节点的槽指向的节点。所述操作还包括将更新树发送到客户端以使得该客户端使用更新树更新本地存储的子树。

为本文实施方式提供进一步的背景，并且如上所述，分布式账本系统(DLS)，又可称为共识网络(例如，由点对点节点组成)和区块链网络，使参与的实体能够安全地、不可篡改地进行交易和存储数据。虽然“区块链”一词通常与特定网络和/或用例相关联，但是本文所使用的区块链一般指在不参考任何特定用例情况下的DLS。

区块链是以交易不可篡改的方式存储交易的数据结构。因此，区块链上记录的交易是可靠且可信的。区块链包括一个或多个区块。链中的每个区块通过包含在链中紧邻其之前的前一区块的加密哈希值(cryptographic hash)链接到该前一区块。每个区块还包括时间戳、自身的加密哈希值以及一个或多个交易。已经被区块链网络中的节点验证的交易经哈希处理并编入默克尔(Merkle)树中。Merkle树是一种数据结构，在该树的叶节点处的数据是经哈希处理的，并且在该树的每个分支中的所有哈希值在该分支的根处连接。此过程沿着树持续一直到整个树的根，在整个树的根处存储了代表树中所有数据的哈希值。声称是存储在树中的交易的哈希值可以通过确定其是否与树的结构一致而被快速验证。区块链是用于存储交易的去中心化或至少部分去中心化的数据结构，而区块链网络是通过广播、验证和确认交易等来管理、更新和维护一个或多个区块链的计算节点的网络。

如上所述，区块链网络可作为公有区块链网络、私有区块链网络或联盟区块链网络被提供。本文参考联盟区块链网络进一步详细描述了本文实施方式。然而，可以预期，本文实施方式可以在任何适当类型的区块链网络中实现。虽然本文描述的技术被指示为与联盟区块链网络相关，但是所述技术可以在进行改变或不做改变的情况之下用于其他类型的区块链网络，包括公有区块链网络和私有区块链网络。

通常，联盟区块链网络在参与实体之间是私有的。在联盟区块链网络中，共识处理由可被称为共识节点的授权的节点集控制，一个或多个共识节点由相应的实体(例如，金融机构、保险公司)操作。例如，由十(10)个实体(例如，金融机构、保险公司)组成的联盟可以操作联盟区块链网络，每个实体可以操作联盟区块链网络中的至少一个节点。

在一些示例中，在联盟区块链网络内，全局区块链作为跨所有节点复制的区块链被提供。也就是说，所有共识节点相对于全局区块链处于完全共识状态。为了达成共识(例如，同意向区块链添加区块)，在联盟区块链网络内实施共识协议。示例共识协议包括但不限于实用拜占庭容错(PBFT)、工作量证明(POW)、权益证明(POS)和权限证明(POA)。

鉴于以上背景，本文进一步详细描述了本文实施方式。更具体地，并且如本文进一步详细描述的那样，本文实施方式执行深度优先前序遍历(depth-first pre-ordertraversal)以改进在MPT中寻址的次序，并在遍历过程中利用两个账户节点(叶节点)之间的特定类型的节点，在本文被称为过渡节点。

更详细地，本文实施方式基于世界状态MPT T0和地址列表L0提供世界状态子树，在本文被称为子树T2。本文实施方式通过首先从地址列表L0构建子树(在本文称为子树T1)，随后在子树T1中执行深度优先前序遍历，避免针对每个地址从根节点至叶节点查找路径。通过深度优先前序遍历依次查找账户节点地址和过渡节点地址。如果在两个账户节点之间存在过渡节点，则从第一账户节点返回到过渡节点，且从过渡节点查找至另一账户节点。以这种方式，对第二账户节点的搜索不需要从根节点处开始，而从过渡节点处开始。

如本文还进一步详细描述的，本文实施方式降低了对处理器和存储的要求。例如，针对每个地址，保存了从根节点至其相应叶节点的路径，并合并这些路径中的重叠节点。更具体地，如果在两个账户节点之间存在过渡节点，不存储从根节点至每个账户节点(即，与账户地址对应的每个叶节点)的完整路径，而是仅保存从过渡节点至下一账户节点的路径。以这种方式，至多个账户节点的路径被合并，这提高了效率并避免了由重叠路径造成的操作和存储浪费。

图1描绘了可用于执行本文实施方式的环境100的示例。在一些示例中，示例环境100使实体能够参与到联盟区块链网络102中。示例环境100包括计算系统106、108以及网络110。在一些示例中，网络110包括局域网(LAN)、广域网(WAN)、因特网或其组合，并且连接网络站点、用户设备(例如，计算设备)和后台系统。在一些示例中，可以通过有线和/或无线通信链路来访问网络110。在一些示例中，网络110使得与联盟区块链网络102通信以及在联盟区块链网络102内部进行通信成为可能。通常，网络110表示一个或多个通信网络。在一些情况下，计算系统106、108可以是云计算系统(未示出)的节点，或者计算系统106、108均可以是包括由网络互联的多个计算机并用作分布式处理系统的独立的云计算系统。

在所描绘的示例中，计算系统106、108可以各自包括能够作为节点参与至联盟区块链网络102中的任何适当的计算设备120。示例计算设备包括但不限于服务器、台式计算机、膝上型计算机、平板计算设备以及智能电话。在一些示例中，计算系统106、108承载一个或多个由计算机实施的服务，用于与联盟区块链网络102进行交互。例如，计算系统106可以承载第一实体(例如，参与者A)的由计算机实施的、例如交易管理系统的服务，第一实体使用该交易管理系统管理其与一个或多个其他实体(例如，其他参与者)的交易。计算系统108可以承载第二实体(例如，参与者B)的由计算机实施的、例如交易管理系统的服务，例如，第二实体使用该交易管理系统管理其与一个或多个其他实体(例如，其他参与者)的交易。在图1的示例中，联盟区块链网络102被表示为节点的点对点网络(Peer-to-Peer network)，且计算系统106、108分别提供参与联盟区块链网络102的第一实体和第二实体的节点。

图2描绘了根据本文实施方式的概念架构200的示例。示例性概念架构200包括分别对应于参与者A、参与者B和参与者C的参与者系统202、204、206。每个参与者(例如，用户、企业)参与到作为点对点网络提供的区块链网络212中，该点对点网络包括多个节点214，至少一些节点将信息不可篡改地记录在区块链216中。如图中进一步详述，尽管在区块链网络212中示意性地描述了单个区块链216，但是在区块链网络212上提供并维护了区块链216的多个副本。

在所描绘的示例中，每个参与者系统202、204、206分别由参与者A、参与者B和参与者C提供或代表参与者A、参与者B和参与者C，并且在区块链网络中作为各自的节点214发挥作用。如这里所使用的，节点通常是指连接到区块链网络212且使相应的参与者能够参与到区块链网络中的个体系统(例如，计算机、服务器)。在图2的示例中，参与者对应于每个节点214。然而，可以预期，一个参与者可以操作区块链网络212内的多个节点214，和/或多个参与者可以共享一个节点214。在一些示例中，参与者系统202、204、206使用协议(例如，超文本传输协议安全(HTTPS))和/或使用远程过程调用(RPC)与区块链网络212通信或通过区块链网络212进行通信。

节点214可以在区块链网络212内具有不同的参与程度。例如，一些节点214可以参与共识处理(例如，作为将区块添加到区块链216的矿工节点)，而其他节点214不参与此共识处理。作为另一示例，一些节点214存储区块链216的完整的副本，而其他节点214仅存储区块链216的一部分的副本。例如，数据访问特权可以限制相应的参与者在其相应系统内存储的区块链数据。在图2的示例中，参与者系统202、204存储区块链216的相应的完整副本216'、216”。

参与区块链网络的节点可被称为客户端，其以点对点方式与其他客户端连接。如上所述，客户端(节点)可不同程度地参与区块链网络。例如，客户端可包括全量客户端和轻量客户端。

在一些示例中，全量客户端参与共识处理，并维护区块链的状态(例如，存储并持续更新区块链)。因此，每个全量客户端下载并验证被添加到区块链的每个区块，并因此下载并验证了每个区块中的每个交易。在图2的示例中，参与者系统202、204可被视为全量客户端(全量节点)。

在一些示例中，轻量客户端(轻量节点)使用户能够访问区块链系统并与区块链系统交互。轻量客户端不参与共识处理，并且不同步整个区块链。因此，轻量客户端可被称为非共识节点。而轻量客户端连接到一个或多个全量客户端，轻量节点据此与区块链交互。也就是说，轻量客户端不是直接与区块链交互，而是使用全量节点作为媒介与区块链交互。因此，与全量客户端相比，轻量客户端需要明显更少(例如，更小的数量级)的计算资源和存储。然而，轻量客户端可能不能够访问区块链的全部，而仅能够查看或访问他们被授权访问的数据。在图2的示例中，参与者系统206可被视为不具有区块链216的副本的轻量客户端。

区块链(例如，图2的区块链216)由一系列区块组成，每个区块存储数据。示例性数据包括表示两个或多个参与者之间的交易的交易数据。尽管本文通过非限制性示例使用了“交易”，但是可以预期，任何适当的数据(例如，文档、图像、视频、音频)可以存储在区块链中。示例交易可以包括但不限于有价物(例如，资产、产品、服务、货币)的交换。交易数据不可篡改地存储在区块链中。也就是说，交易数据不能被改变。

在将交易数据存储在区块中之前，对交易数据进行哈希处理。哈希处理是将交易数据(作为字符串数据提供)转换为固定长度哈希值(也作为字符串数据提供)的处理。对哈希值进行去哈希处理(un-hash)以获得交易数据是不可能的。哈希处理可确保即使交易数据轻微改变也会导致完全不同的哈希值。此外，如上所述，哈希值具有固定长度。也就是说，无论交易数据的大小如何，哈希值的长度都是固定的。哈希处理包括通过哈希函数处理交易数据以生成哈希值。示例性哈希函数包括但不限于输出256位哈希值的安全哈希算法(SHA)-256。

多个交易的交易数据被哈希处理并存储在区块中。例如，提供两个交易的哈希值，并对它们本身进行哈希处理以提供另一个哈希值。重复此处理，直到针对所有要存储在区块中的交易提供单个哈希值为止。该哈希值被称为默克尔(Merkle)根哈希值，并存储在区块的头中。任何交易中的更改都会导致其哈希值发生变化，并最终导致Merkle根哈希值发生变化。

通过共识协议将区块添加到区块链。区块链网络中的多个节点参与共识协议，并执行将区块添加到区块链中的工作。这样的节点被称为共识节点。上文介绍的PBFT用作共识协议的非限制性示例。共识节点执行共识协议以将交易添加到区块链。

更详细地，共识节点生成区块头，对区块中的所有交易进行哈希处理，并将所得的哈希值成对地组合以生成进一步的哈希值，直到为区块中的所有交易提供单个哈希值(Merkle根哈希值)。将此哈希值添加到区块头中。共识节点还确定区块链中最新的区块(即添加到区块链中的最后一个区块)的哈希值。共识节点还向区块头添加随机数(nonce)值和时间戳。

通常，PBFT提供容忍拜占庭错误(例如，故障节点、恶意节点)的实用拜占庭机器状态复制。这通过假设错误将在PBFT中发生(例如，假设存在独立的节点失效和/或由共识节点发送的篡改消息)来实现。在PBFT中，在包括主共识节点和备共识节点的序列中提供共识节点。主共识节点周期性地改变，通过区块链网络内的所有共识节点就区块链网络的全局状态达成一致，将交易添加到区块链中。在该处理中，消息在共识节点之间传输，并且每个共识节点证明消息是从指定的对等节点接收的，并验证在交易期间消息未篡改。

在PBFT中，共识协议是在所有共识节点始于相同的状态的情况下分多个阶段提供的。首先，客户端向主共识节点发送调用服务操作(例如，在区块链网络内执行交易)的请求。响应于接收到该请求，主共识节点将该请求组播到备共识节点。备共识节点执行该请求，并各自向客户端发送恢复。客户端等待直到收到阈值数量的恢复。在一些示例中，客户端等待接收到f+1个副本，其中，f为区块链网络内可以容忍的错误共识节点的最大数量。最终结果是，足够数量的共识节点就将记录添加到区块链的顺序达成一致，该记录被接受或者被拒绝。

在一些区块链网络中，用加密处理来维护交易的隐私。例如，如果两个节点想要保持交易隐私，以使得区块链网络中的其他节点不能看出交易的细节，则这两个节点可以对交易数据进行加密。示例加密处理包括但不限于对称加密和非对称加密。对称加密是指使用单个密钥既进行加密(从明文生成密文)又进行解密(从密文生成明文)的加密处理。对称加密中，同一密钥可用于多个节点，因此每个节点可对交易数据进行加密/解密。

非对称加密使用密钥对，每个密钥对包括私钥和公钥，私钥仅对于相应节点是已知的，而公钥对于区块链网络中的任何或所有其他节点是已知的。节点可以使用另一个节点的公钥来加密数据，并且该加密的数据可以使用其他节点的私钥被解密。例如，再次参考图2，参与者A可以使用参与者B的公钥来加密数据，并将加密数据发送给参与者B。参与者B可以使用其私钥来解密该加密数据(密文)并提取原始数据(明文)。使用节点的公钥加密的消息只能使用该节点的私钥解密。

非对称加密用于提供数字签名，这使得交易中的参与者能够确认交易中的其他参与者以及交易的有效性。例如，节点可以对消息进行数字签名，而另一个节点可以根据参与者A的该数字签名来确认该消息是由该节点发送的。数字签名也可以用于确保消息在传输过程中不被篡改。例如，再次参考图2，参与者A将向参与者B发送消息。参与者A生成该消息的哈希值，然后使用其私钥加密该哈希值以提供为加密哈希值的数字签名。参与者A将该数字签名附加到该消息上，并将该具有数字签名的消息发送给参与者B。参与者B使用参与者A的公钥解密该数字签名，并提取哈希值。参与者B对该消息进行哈希处理并比较哈希值。如果哈希值相同，参与者B可以确认该消息确实来自参与者A，且未被篡改。

为了提供本文实施方式的进一步背景，哈希树(也被称为默克尔树(Merkletree)，如上所述)是节点以及节点间边缘的树。Merkle树包括根节点、子节点和叶节点。在区块链网络中，Merkle树存储哈希值，如上所述。在Merkle树中，每个叶节点被标记有数据块的哈希值，每个非叶节点被标记有其子节点的标记的哈希值。Merkle树实现对诸如区块链的大数据结构的内容进行高效且安全的验证。字典树(trie，也被称为前缀树)是可用于存储用字母表达的串的多叉树结构。帕特里夏字典树(Patricia trie)是字典树的紧凑表示形式，其中作为唯一子节点的任何节点与其父节点合并。默克尔帕特里夏字典树(也被称为默克尔帕特里夏树(Merkle Patricia trie(树)或MPT)是包含Merkle树和帕特里夏字典树(前缀树)两者的树，其继承了两者的优点。MPT提供了数据的快速比较和更新。

更详细地，MPT可被描述为在256位二进制段与任意长度二进制数据(字节阵列)之间进行映射的永久易变的数据结构。在一些示例中，MPT可被实现为数据库。MPT提供标识键值对的给定集的单个值，该值可以是32字节序列或空字节序列。例如，当从根节点至叶节点遍历MPT时，相应键值对被提供。键通过遍历被累积，从每个分支节点获取单个四位元(nibble，即单个十六进制数，hex digit)，如下所述。在多个键共享同一前缀的示例中，或在具有唯一后缀的单个键的情况下，提供最优化节点。因此，当遍历MPT时，可从其他两个节点类型(扩展节点和叶节点)分别获取多个四位元。

在MPT中，叶节点被各自提供为两项(two-item)结构。一项对应于键中没有被键的累积和从根遍历的分支所考虑的四位元。使用十六进制前缀编码，并且要求函数的第二参数为真(true)。本文进一步详细描述叶节点和对应项的示例。扩展节点各自被提供为两项结构。一项对应于大小大于1的一系列四位元，所述一系列四位元由至少两个不同的键共享，所述至少两个不同的键经过了四位元键的累积和从根起被遍历的分支。使用十六进制前缀编码，并且要求函数的第二参数为假(false)。本文进一步详细描述了扩展节点和对应项的示例。分支节点被提供为17项结构，前十六项分别与键在遍历中在该点处的十六个可能的四位元值中的每个(例如，十六进制值0-f)相对应。第17项用于分支节点为终止节点的情况，并且因此键在遍历中在该点处终止。仅在必要时使用分支，可能不存在仅包含单个非零条目(entry)的分支节点。

在区块链网络中，MPT实现密码认证和性能平衡，并被用于世界状态数据管理以管理用户的账户状态(和智能合约)。在一些区块链网络中，提供了用于通过所谓的世界状态MPT查询账户的状态的接口。例如，可通过接口输入账户地址，区块链网络的节点(例如，全量客户端)返回账户的状态。当查询大量账户的状态时，接口被反复调用，每个账户的状态被返回。可注意到返回的数据(例如，账户、状态)是碎片化的并且不具有结构。虽然所述数据可在本地组装到状态树中，但是所产生的状态树与世界状态MPT通常不一致。因此，失去了MPT自身的优势，且操作和存储的性能相对较低。

如本文进一步详细描述的，本文实施方式执行深度优先前序遍历以改进MPT树中搜索地址的次序，并在遍历过程中利用两个账户节点(叶节点)之间在本文被称为过渡节点的特定类型的节点。更详细地，本文实施方式基于世界状态MPT T0和地址列表L0提供本文称为子树T2的世界状态子树。本文实施方式通过首先从地址列表L0构建本文称为子树T1的子树，随后在子树T1中执行深度优先前序遍历，避免针对每个地址从根节点起查找至叶节点的路径。通过深度优先前序遍历依次查找账户节点地址和过渡节点地址。如果在两个账户节点之间存在过渡节点，则第一账户节点被返回到过渡节点，从该过渡节点起查找至另一账户节点。以这种方式，对第二账户节点的搜索不需要在根节点处开始，而在过渡节点处开始。

如本文还进一步详细描述的，本文实施方式降低了对处理器和存储的要求。例如，针对每个地址，保存从根节点至其相应叶节点的路径，并合并这些路径中的重叠节点。更具体地，如果在两个账户节点之间存在过渡节点的话，不是存储从根节点至每个账户节点(即，与账户地址对应的每个叶节点)的完整路径，而是仅保存从过渡节点至下一账户节点的路径。以这种方式，至多个账户节点的路径被合并，这提高了效率并避免了由重叠路径造成的操作和存储浪费。

在一些实施方式中，并且如本文进一步详细描述的，给定世界状态MPT中的账户地址的列表，提供该地址列表的子树。本文实施方式采用深度优先前序遍历算法来改进MPT中的搜索地址的次序并提高节点的效率。此外，本文实施方式提供包括两个账户节点之间的过渡节点的节点遍历处理。为避免由从根节点开始查找每个账户节点造成的搜索浪费，实施方式包括保存从过渡节点至下一账户节点的路径，解决根节点至两个账户节点的路径的重叠。如本文所述，本文实施方式提高了效率并且避免了由重叠路径造成的操作和存储浪费。

参照示例性世界状态MPT进一步详细描述了本文实施方式。示例性世界状态MPT基于瑞士楚格的以太坊基金会(The Ethereum Foundation of Zug,Switzerland)提供的以太坊区块链应用平台。以太坊提供被称为以太币(ETH)的数字资产，以太币的最小单位被称为伟(Wei，WEI)。然而，预期可以在任何适当区块链网络和任何适当世界状态MPT中实现本文实施方式。

图3描绘了世界状态MPT 300的示例。应理解图3的示例性世界状态MPT 300相对简单化以帮助容易地理解本文实施方式。然而，预期可以利用具有不同复杂度(例如，成百上千个节点)的MPT来实现本文实施方式。在图3的示例中，MPT 300包括根节点302、分支节点304、306、扩展节点308和叶节点310、312、314。在一些示例中，叶节点310、312、314对应于区块链网络内的相应账户(账户_1、账户_2、账户_3)。示例性世界状态MPT 300还包括记录键值对的表320。在图3的示例中，表320包括分别对应于叶节点310、312、314的键值对322、324、326。

在一些示例中，图3的世界状态MPT 300由区块链网络内的多个客户端维护(例如，构建、更新)。例如，如上所述的全量客户端可参与共识处理，并维护区块链网络内的区块链的世界状态。这可包括，例如存储区块链的完整副本和世界状态MPT 300。示例性全量客户端包括如上所述的图2的参与者系统202、204。

如上所述，区块链网络可包括轻量客户端，该轻量客户端不维护区块链的世界状态，并且不存储区块链的完整副本和世界状态MPT 300。作为非限制性示例，轻量客户端可对区块链网络内的账户的子集(例如，账户_1、账户_2)感兴趣或仅可访问区块链网络内的账户的子集，并且既不对其他账户(例如，账户_3)感兴趣也不被授权访问其他账户。根据本文实施方式，轻量客户端可维护与世界状态MPT 300中提供的状态一致的账户的子集的状态。如本文进一步详细描述的，全量客户端生成MPT 300的子树，该子树表示世界状态MPT300的与账户的子集相关的部分。子树被提供给轻量客户端，并被周期性地更新以确保子树的状态与世界状态MPT 300的状态一致。

图4描绘了根据本文实施方式的基于图3的示例性世界状态MPT 300生成的子树400的示例。在图4中，示例性子树400包括分别对应于图3的世界状态MPT 300的根节点302、分支节点304、306、扩展节点308和叶节点310、312的根节点402、分支节点404、406、扩展节点408和叶节点410、412。叶节点410、412对应于相应客户端(例如，轻量客户端)，该客户端可以在区块链网络内访问的相应账户(账户_1、账户_2)。示例性子树400还包括记录键值对的表420。在图4的示例中，表420包括分别对应于叶节点410、412的键值对422、424。

图4的子树400不具有与图3的世界状态MPT 300的叶节点314对应的叶节点(例如，轻量客户端不可访问由叶节点314表示的账户(账户_3))。而分支节点406包括第10项中的占位符字符(*)。

根据本文实施方式，并且如本文详细描述的，子树400可由全量客户端针对轻量客户端生成。例如，轻量客户端可将对子树的请求提交给区块链网络。响应于该请求，全量客户端可基于轻量客户端可访问的账户和由全量客户端维护的世界状态MPT 300生成子树400。在一些示例中，来自轻量客户端的请求包括对应于轻量客户端可访问的账户的子集的地址列表。在一些示例中，由全量客户端确定轻量客户端可访问的账户的子集的地址列表，例如，在区块链网络内使用轻量客户端的唯一标识符索引访问控制表(ACL)。如本文进一步详细描述的，给定世界状态MPT 300和地址列表，全量客户端生成子树400，并将子树400返回到请求的轻量客户端。

图5A和图5B描绘了可根据本文实施方式执行的过程500、550的示例。在一些实施方式中，可以使用利用一个或多个计算设备执行的一个或多个计算机可执行程序来执行示例性处理500、550。例如，示例处理500、550可由全量客户端执行以在区块链网络内生成针对轻量客户端的子树。

具体参照图5A，示例性处理500可被执行以从世界状态MPT T0提供地址列表L1用于构建子树T2。

提供世界状态MPT T0和地址列表L0(502)。例如，世界状态MPT T0(例如，图3的世界状态MPT 300)和地址列表L0被提供作为用于由全量客户端生成地址列表的子树的输入(例如，全量客户端存储世界状态MPT 300并接收地址列表)。在一些示例中，地址列表L0中的每个地址是MPT T0的叶节点(例如，MPT 300的叶节点310、312、314)的地址。可在地址列表L0内提供任何次序的账户地址。在一些实施方式中，并且如本文所进一步详细描述的，深度优先前序遍历算法被用于在MPT树T0的节点上进行搜索。

从地址列表L0提供MPT树T1(502)。在一些示例中，地址列表L0基于表示允许特定轻量客户端访问的地址的列表的ACL。在一些示例中，地址列表L0提供将被包括在要创建的子树T2中的地址。在一些示例中，地址列表L0中的每个地址的值被默认为空字符串(例如，被称为空(null))，并且T1中的每个节点的值可被计算。创建空地址列表L1(504)。从T1的根节点开始执行节点遍历，并利用深度优先前序遍历来遍历T1(506)。如本文进一步详细描述的，示例性处理500递归地将相应地址列表L0中的地址的节点以及他们之间的过渡节点记录在地址列表L1中。

确定当前节点是否为叶节点(508)。如果当前节点是叶节点，则该节点对应于地址列表中的节点。该节点被标记(例如，为“账户节点”)，并且该节点的地址和标记被保存到地址列表L1(510)。遍历返回到叶节点的父节点(512)。如果当前节点不是叶节点，则确定当前节点是否为扩展节点(514)。如果当前节点是扩展节点，则节点的值指向对另一节点的引用，遍历移动到被引用的节点(516)。

如果当前节点不是扩展节点，则当前节点是分支节点，并确定是否第一次至该节点(520)。如果不是第一次，则确定当前节点的所有子节点是否已被遍历(522)。如果所有子节点已被遍历，则遍历返回至分支节点的父节点(512)。如果不是所有子节点都已被遍历，则该节点被标记为“过渡节点”，并且该节点的地址和标记被保存在L1中(524)，遍历移动至还没有被遍历的子节点(526)。如果是第一次至当前节点(分支节点)，则确定其值是否为空(例如，空字符串，也被称为空(null))(528)。如果其值为空，指示该节点对应于地址列表中的节点，则将该节点标记为“账户节点”，并且标记和地址被保存到L1(530)，且遍历移动到第一子节点(526)。

具体参照图5B，示例性处理550可被执行以从地址列表L1和世界状态MPT T0构建子树T2。如本文所述，子树T2包括与世界状态MPT T0相同的根节点，通过递归地执行以下操作从根节点起构建子树T2的剩余部分。

子树T2被提供有T0的根节点(552)。选择地址列表L1中被标记为“账户节点”的第一地址(554)。在T0中查找相应节点(556)。因此，提供从T0中的根节点至相应节点的搜索路径。将路径上的每个节点添加到T2(558)。选择地址列表L1中的下一地址(560)。确定与该地址对应的节点是否被标记为“账户节点”(562)。如果节点被标记为“账户节点”，则在T0中的当前节点开始，在T0中查找对应于该地址的节点，将路径上的每个节点添加到T2(564)。

如果节点没有被标记为“账户节点”，则确定该节点是否被标记为“过渡节点”(566)。如果该节点被标记为“过渡节点”，则在T0中的当前节点开始，对应于该地址的节点被确定并被提供作为T0中的(新的)当前节点(568)。账户节点至过渡节点的路径不被添加到T2。在遍历了地址列表L1中的所有地址之后，所产生的T2为原始世界状态MPT T0中的地址列表L0的子树。

如上所述，本文实施方式还涉及基于世界状态MPT更新子树。更具体地，由于世界状态记录所有节点(例如，用户、智能合约)的账户状态，因此记录在世界状态MPT中的数据量会很大。对于例如轻量客户端的客户端来说，大量数据是不相关的或不可访问的(例如，没有访问权限)。因此，并且如上所述，一些客户端可能仅愿意本地维护世界状态中与他们关联的一些用户(和智能合约)的账户状态。如本文所述，这通过向客户端(轻量客户端)提供客户端本地存储的世界状态MPT的子树来实现。

然而，由共识节点维护的世界状态(例如，在世界状态MPT中)被频繁地更新。因此，由客户端维护的子树也需要被周期地更新。通常，更新子树可包括将子树的最新数据与共识节点的世界状态MPT的数据同步。鉴于此，本文实施方式提供从更新的世界状态MPT确定子树的更新的状态，用于以高效带宽、高效处理器和高效存储器的方式更新子树。

图6描绘了包括更新的图3的示例性世界状态MPT 300。在图6的示例中，MPT 300包括根节点302、分支节点304、306、扩展节点308、叶节点310、312、314和叶节点318。在一些示例中，并且如上所述，叶节点310、312、314对应于区块链网络内的相应账户(账户_1、账户_2、账户_3)。叶节点318对应于(例如，在图3的世界状态MPT 300被提供之后)被添加到区块链网络的相应账户(账户_4)。示例表320记录分别对应于叶节点310、312、314的键值对322、324、326和对应于叶节点318的键值对328。因此，对世界状态MPT 300的更新包括叶节点318和相应的键值对328。

根据本文实施方式，并且如本文详细描述的，可基于全量客户端针对轻量客户端提供的一组更新来更新图4的子树400。例如，轻量客户端可将对更新的子树的请求提交给区块链网络。响应于该请求，全量客户端可基于由全量客户端维护的世界状态MPT 300(例如，图6中描述的)的当前状态确定对子树400的更新。在一些示例中，全量客户端生成一组更新(例如，与新的子树对照)，并将该组更新发送到轻量客户端。轻量客户端处理该组更新以更新子树400。

图7描绘了根据本文实施方式的基于图6的示例性世界状态MPT 300的包括更新的图4的子树。图7的示例性子树400包括分别对应于图3的世界状态MPT 300的根节点302、分支节点304、306、扩展节点308和叶节点310、312的根节点402、分支节点404、406、扩展节点408、叶节点410、412。叶节点410、412对应于相应客户端(例如，轻量客户端)，该客户端可以在区块链网络内访问的相应账户(账户_1、账户_2)。示例性子树400还包括记录键值对的表420。在图7的示例中，表420包括分别对应于叶节点410、412、414的键值对422、424、426。

如图4中那样，图7的子树400不具有与图3和图6的世界状态MPT 300的叶节点314对应的叶节点(例如，轻量客户端不可访问由叶节点314表示的账户(账户_3))。而分支节点406包括第10项中的占位符字符(*)。此外，图7的子树400不具有与图6的世界状态MPT 300的叶节点318对应的叶节点(例如，轻量客户端不可访问由叶节点318表示的账户(账户_4))。而分支节点404包括第16项中的占位符字符(*)。

图8A和图8B描绘了可根据本文实施方式执行的处理800、850的示例。在一些实施方式中，可使用利用一个或多个计算设备执行的一个或多个计算机可执行程序来执行示例性处理800、850。例如，示例性处理800可由全量客户端执行以在区块链网络内生成针对轻量客户端的子树的一组更新，示例性处理850可由轻量客户端执行以更新本地维护的子树。

具体参照图8A，示例性处理800可被执行以从世界状态MPT T0和子树T2提供一组更新(例如，被提供为更新的节点的子树T2’)。如本文所述，示例性处理800进行子树T2的节点(当前节点)与世界状态MPT T0的相应节点(当前节点)之间的成对节点比较，并将世界状态MPT T0的任何不同的节点添加到更新树T2’。

确定T0的根节点的值和T2的根节点的值(802)，并比较所述值(804)。如果所述值相同，则子树T2与MPT T0处于一致状态，并照此指示(806)。例如，可从全量客户端向请求更新的轻量客户端发送指示子树T2与世界状态一致的响应。如果所述值不同，则世界状态MPTT0自从子树T2被创建已被更新。因此，利用MPT T0的根节点创建更新树T2’，当前节点从子树T2的根节点移动到值被引用的节点(808)。也就是说，叶节点的值是存储在数据库(存储键值对)中的一些数据的键。因此，叶节点的值引用数据库中的真实数据。对于非叶节点，其值是另一节点的地址。也就是说，非叶节点指向(引用)另一节点。

确定是否第一次至子树T2中的当前节点(810)。如果是第一次至子树T2中的当前节点，则在MPT T0中查找对应于当前节点的地址的节点，并提供搜索路径(812)。在一些示例中，搜索路径是MPT T0内至相应节点的深度遍历。确定在搜索路径中是否存在任何中间节点(814)。如果搜索路径中存在一个或多个中间节点，则将中间节点添加到树T2’，并标签(标记)每个中间节点以指示他们是子树T2不包括的节点(816)。在一些示例中，如本文所述，标签被提供为用于标记节点的元数据。

确定T2中的当前节点是否为叶节点(818)。如果T2中的当前节点是叶节点，则确定T0中的当前节点是否是叶节点(820)。如果T0中的当前节点是叶节点，则比较T2和T0的当前节点的值(822)。如果所述值不同，则将T0中的当前节点添加到T2’(824)。如果所述值相同，则T2中的当前节点移动到父节点(826)。以这种方式，仅如果T0的当前节点是与T2的当前节点不同类型的节点，或与T2的当前节点具有不同的值，则T0的当前节点被添加到更新树T2’。如果T0的当前节点与T2的当前节点类型相同并且他们的值相同，则T0的当前节点不被添加到更新树T2’。如果T2中的当前节点不是叶节点，则确定T2中的当前节点是否是扩展节点(828)。如果T2中的当前节点是扩展节点，则T0中的当前节点被添加到T2’，T2中的当前节点移动到槽(slot)指向的节点(830)，示例性处理(800)返回循环。

如果T2中的当前节点不是扩展节点，则T2中的当前节点和T0中的当前节点均为分支节点。确定是否第一次考虑T2中的当前节点(832)。如果是第一次，则确定T2的当前节点的值与T0的当前节点的值是否不同(834)。如果所述值不同，则T0的当前节点被添加到更新树T2’(824)。如果所述值相同，则确定T2中的当前节点中指向T2中的另一节点的下一槽，T2的当前节点移动到槽指向的节点。也就是说，不考虑不指向T2中的另一节点的任何槽，即使其值不为空也不考虑，这是因为这种槽指向T0中不在T2中的节点。相应地，示例处理800提供槽比较，从第一槽开始，直到遇到具有不同值的槽为止，T2中的当前节点移动到由该槽指向的节点(836)，示例性处理800返回循环。

如果不是第一次至T2的当前节点(832)，则确定是否已经比较了T2的当前节点与T0的当前节点之间的所有槽(838)。如果已比较了所有槽，则示例处理800返回循环以移动到父节点(826)。如果未比较所有槽，则迭代地将剩余的非空的槽与T0的当前节点的槽进行比较，直到在剩余的槽中遇到不同的值为止(840)。T0的当前节点移动到该槽指向的节点(842)，示例性处理800返回循环。

随着示例性处理800递归地执行，并且子树T2的当前节点迭代地移动到父节点(826)，确定父节点是否是根节点(844)。如果父节点不是根节点，则示例性处理800返回循环以考虑与MPT T0相关的子树T2的(新的)当前节点。如果父节点是根节点，则返回更新树T2’(846)。更新子树由子树T2的所有根据更新的世界状态MPT T0而更新的节点组成。也就是说，更新树T2’仅包括子树T2的已根据更新的MPT T0而更新的那些节点。

具体参照图8B，示例性处理850可被执行以基于从全量客户端提供的更新树T2’在轻量客户端更新子树T2。也就是说，全量客户端仅需要将更新树T2’发送到轻量客户端，而不是全新创建的子树。由于更新树T2’仅包括更新的节点，相比于子树T2，其为更小的数据结构。因此，通过仅发送更新树T2’，节省了计算资源和带宽(例如，相对于将全新子树T2发送到轻量客户端)。在一些示例中，一旦接收到更新树T2’，轻量客户端就执行示例性处理850以本地更新子树T2。

从更新树T1的根节点开始，示例性处理850执行深度优先遍历以考虑每个节点(作为当前节点)。确定当前节点是否已被考虑(852)。如果当前节点已被考虑，则将下一节点选为当前节点(854)，示例处理返回循环。如果当前节点还没有被考虑，则确定当前节点是否具有标签(被标记)(856)。如果当前节点不具有标签，则确定地址在原始子树T2中的节点，并用来自更新树T2’的新节点替换旧节点(858)。如果当前节点具有标签(即，其地址在原始子树T2中不具有相应节点)，则节点被插入子树T2(860)。在遍历更新树T2’的所有节点之后，子树T2被更新以反映更新的MPT T0的相关更新。

图9描绘了根据本文实施方式的装置900的模块的示例。装置900可以是诸如联盟区块链网络的区块链网络中被配置为生成世界状态MPT的子树的区块链节点的示例实施方式。装置900可对应于上述实施方式，装置900可包括以下：生成器或生成单元902，用于提供世界状态MPT和用于存储区块链网络内的节点的地址的地址列表；执行器或执行单元904，用于遍历世界状态MPT；创建器或创建单元906，用于生成世界状态MPT的子树；发送器或发送单元908，用于将世界状态MPT的子树发送到区块链网络的非共识客户端。

图10描绘了根据本文实施方式的装置1000的模块的示例。装置1000可以是诸如联盟区块链网络的区块链网络中被配置为更新世界状态MPT的子树的区块链节点的示例实施方式。装置1000可对应于上述实施方式，装置1000可包括以下：生成器或生成单元1002，用于创建包括世界状态MPT的根节点并且最初不具有其他节点的更新树；执行器或执行单元1004，用于通过多次迭代遍历子树的至少一部分；发送器或发送单元1006，用于将子树的更新树发送到区块链网络的非共识客户端，非共识客户端使用所述更新树更新本地存储的子树以提供更新的子树，该更新的子树提供与非共识客户端关联的账户的状态。

在先前实施例中示出的系统、装置、模块或单元可以通过使用计算机芯片或实体来实现，或者可以通过使用具有特定功能的产品来实现。典型的实现设备是计算机，计算机可以是个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件收发设备、游戏控制台、平板电脑、可穿戴设备或这些设备的任意组合。

对于装置中各个单元的功能和角色的实施过程，可以参考前一方法中相应步骤的实施过程。为简单起见，这里省略了细节。

由于装置实施基本上对应于方法实施，对于相关部分，可以参考方法实施中的相关描述。先前描述的装置实施仅是示例。被描述为单独部分的单元可以是或不是物理上分离的，并且显示为单元的部分可以是或不是物理单元，可以位于一个位置，或者可以分布在多个网络单元上。可以基于实际需求来选择一些或所有模块，以实现本说明书方案的目标。本领域普通技术人员无需付出创造性劳动就能理解和实现本申请的实施方式。

再次参照图9，其可被解释为示出世界状态MPT的子树生成装置的内部功能模块和结构。世界状态MPT的子树生成装置可以是被配置为在区块链网络内生成世界状态MPT的子树的区块链节点的示例。再次参照图10，其可以被解释为示出世界状态MPT的子树更新装置的内部功能模块和结构。世界状态MPT的子树更新装置可以是被配置为在区块链网络内更新世界状态MPT的子树的区块链节点的示例。执行主体本质上可以是电子设备和包括以下的电子设备：一个或多个处理器；以及存储一个或多个处理器的可执行指令的存储器。

描述的主题的实施方式可单独包括一个或多个特征或者一个或多个特征的组合。例如，在第一实施方式中，操作可被执行为：创建包括世界状态MPT的根节点并且最初没有其他节点的更新树；通过多次迭代遍历子树的至少一部分，在每次迭代，针对子树的当前节点，执行以下操作之一：确定子树的当前节点和世界状态MPT的当前节点是叶节点并且他们的值不相等，作为响应，将世界状态MPT的当前节点添加到更新树，确定子树的当前节点和世界状态MPT的当前节点是扩展节点，作为响应，将世界状态MPT的当前节点添加到更新树，并且移动遍历的下一次迭代，该下一次迭代将子树的当前节点设置为由扩展节点引用的节点，确定子树的当前节点和世界状态MPT的当前节点是分支节点，并且他们的值不相等，作为响应，将世界状态MPT的当前节点添加到更新树，确定子树的当前节点和世界状态MPT的当前节点是分支节点，并且他们的值相等，作为响应，移动至遍历的下一次迭代，该下一次迭代将子树的当前节点设置到子树的当前节点的槽指向的节点；将子树的更新树发送到区块链网络的非共识客户端，非共识客户端使用更新树更新本地存储的子树以提供更新的子树，该更新的子树提供与非共识客户端关联的账户的状态。

以上和描述的其他实施方式可均可选地包括以下特征中的一个或多个：

在可与以下特征中的任何特征组合的第一特征中，操作还包括：在至少一次迭代期间，查找世界状态MPT中的相应节点，并提供搜索路径，搜索路径中的一个或多个节点被标记为中间节点，并被标记为不在子树中。

在可与以下特征中的任何特征组合的第二特征中，响应于确定子树的当前节点和世界状态MPT的当前节点是分支节点，并且当前迭代是子树的当前节点被考虑的首次迭代，将子树的当前节点的值与世界状态MPT的当前节点的值进行比较。

在可与以下特征中的任何特征组合的第三特征中，响应于确定子树的当前节点是根节点，终止遍历。

在可与以下特征中的任何特征组合的第四特征中，本地存储的子树是通过一次或多次地用更新树的节点替换子树的节点，并将更新树的节点插入子树来更新的。

在可与以下特征中的任何特征组合的第五特征中，响应于共识客户端从非共识客户端接收到的请求而创建更新树。

在可与以上特征中的任何特征组合的第六特征中，响应于确定子树的根节点的值与世界状态MPT的根节点的值不同而创建更新树。

本文中描述的主题、动作以及操作的实施可以在数字电子电路、有形体现的计算机软件或固件、计算机硬件中实现，包括本说明书中公开的结构及其结构等同物，或者它们中的一个或多个的组合。本文中描述的主题的实施可以实现为一个或多个计算机程序，例如，一个或多个计算机程序指令模块，编码在计算机程序载体上，用于由数据处理装置执行或控制数据处理装置的操作。载体可以是有形的非暂态计算机存储介质。可选地或附加地，载体可以是人工生成的传播信号，例如，机器生成的电、光或电磁信号，其被生成来编码信息用于传输到合适的接收器装置以供数据处理装置执行。计算机存储介质可以是或部分是机器可读存储设备、机器可读存储基板、随机或串行访问存储器设备或它们中的一个或多个的组合。计算机存储介质不是传播信号。

术语“数据处理装置”包括用于处理数据的所有类型的装置、设备和机器，包括例如可编程处理器、计算机或者多处理器或计算机。数据处理装置可以包括专用逻辑电路，例如FPGA(现场可编程门阵列)、ASIC(专用集成电路)或GPU(图形处理单元)。除了硬件，该装置还可以包括为计算机程序创建执行环境的代码，例如，构成处理器固件、协议栈、数据库管理系统、操作系统或者它们中的一个或多个的组合的代码。

计算机程序也可以被称为或描述为程序、软件、软件应用程序、app、模块、软件模块、引擎、脚本或代码，可以以任何形式的编程语言编写，包括编译或演绎性语言、说明或程序性语言；它可以配置为任何形式，包括作为独立程序，或者作为模块、组件、引擎、子程序或适合在计算环境中执行的其他单元，该环境可包括由通信数据网络互联的在一个或多个位置的一台或多台计算机。

计算机程序可以但非必须对应于文件系统中的文件。计算机程序可以存储在：保存其他程序或数据的文件的一部分中，例如，存储在标记语言文档中的一个或多个脚本；专用于所讨论的程序的单个文件；或者多个协调文件，例如，存储一个或多个模块、子程序或代码部分的多个文件。

本文描述的处理和逻辑流程可由一台或多台计算机执行一个或多个计算机程序进行，以进行通过对输入数据进行运算并生成输出的操作。处理和逻辑流程也可以由例如FPGA、ASIC、GPU等的专用逻辑电路或专用逻辑电路与一个或多个编程计算机的组合来执行。

适合于执行计算机程序的计算机可以基于通用和/或专用微处理器，或任何其他种类的中央处理单元。通常，中央处理单元将从只读存储器和/或随机存取存储器接收指令和数据。计算机的元件可包括用于执行指令的中央处理单元以及用于存储指令和数据的一个或多个存储器设备。中央处理单元和存储器可以补充有专用逻辑电路或集成在专用逻辑电路中。

通常，计算机还将包括或可操作地耦接至一个或多个大容量存储设备，以从一个或多个大容量存储设备接收数据或将数据传输到一个或多个大容量存储设备。大容量存储设备可以是例如，磁盘、磁光盘或光盘或固态驱动器。但是，计算机不需要具有这样的设备。此外，计算机可以嵌入在另一个设备中，例如移动电话、个人数字助理(PDA)、移动音频或视频播放器、游戏控制台、全球定位系统(GPS)接收器或例如通用串行总线(USB)闪存驱动器的便携式存储设备，仅举几例。

为了提供与用户的交互，本文描述的主题的实施例可以在计算机上实现或配置为与该计算机通信，该计算机具有：显示设备，例如，LCD(液晶显示器)监视器，用于向用户显示信息；以及输入设备，用户可以通过该输入设备向该计算机提供输入，例如键盘和例如鼠标、轨迹球或触摸板等的指针设备。其他类型的设备也可用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感官反馈，例如视觉反馈、听觉反馈或触觉反馈；并且可以接收来自用户的任何形式的输入，包括声音、语音或触觉输入。此外，计算机可以通过向用户使用的设备发送文档和从用户使用的设备接收文档来与用户交互；例如，通过向用户设备上的web浏览器发送web页面以响应从web浏览器收到的请求，或者通过与例如智能电话或电子平板电脑等的用户设备上运行的应用程序(app)进行交互。此外，计算机可以通过向个人设备(例如，运行消息应用的智能手机)轮流发送文本消息或其他形式的消息并接收来自用户的响应消息来与用户交互。

本文使用与系统、装置和计算机程序组件有关的术语“配置为”。对于被配置为执行特定操作或动作的一个或多个计算机的系统，意味着系统已经在其上安装了在运行中促使该系统执行所述操作或动作的软件、固件、硬件或它们的组合。对于被配置为执行特定操作或动作的一个或多个计算机程序，意味着一个或多个程序包括当被数据处理装置执行时促使该装置执行所述操作或动作的指令。对于被配置为执行特定操作或动作的专用逻辑电路，意味着该电路具有执行所述操作或动作的电子逻辑。

虽然本文包含许多具体实施细节，但是这些不应被解释为由权利要求本身限定的对要求保护的范围的限制，而是作为对特定实施例的具体特征的描述。在本说明书多个单独实施例的上下文中描述的多个特定特征也可以在单个实施例中的组合实现。相反，在单个实施例的上下文中描述的各种特征也可以单独地或以任何合适的子组合在多个实施例中实现。此外，尽管上面的特征可以描述为以某些组合起作用并且甚至最初如此要求保护，但是在一些情况下，可以从要求保护的组合中删除来自该组合的一个或多个特征，并且可以要求保护指向子组合或子组合的变体。

类似地，虽然以特定顺序在附图中描绘了操作并且在权利要求中叙述了操作，但是这不应该被理解为：为了达到期望的结果，要求以所示的特定顺序或依次执行这些操作，或者要求执行所有示出的操作。在一些情况下，多任务和并行处理可能是有利的。此外，上述实施例中的各种系统模块和组件的划分不应被理解为所有实施例中都要求如此划分，而应当理解，所描述的程序组件和系统通常可以一起集成在单个软件产品或者打包成多个软件产品。

已经描述了主题的特定实施方式。其他实施方式在以下权利要求的范围内。例如，权利要求中记载的动作可以以不同的顺序执行并且仍然实现期望的结果。作为一个示例，附图中描绘的处理无需要求所示的特定顺序或次序来实现期望的结果。在一些情况下，多任务和并行处理可能是有利的。

Claims

1.一种计算机实现的方法，所述方法用于更新区块链网络内的世界状态默克尔帕特里夏字典树MPT的子树，所述方法包括：

所述区块链网络的共识客户端创建包括所述世界状态MPT的根节点并且最初没有其他节点的更新树；

所述共识客户端通过多次迭代遍历所述子树的至少一部分，并且在每次迭代中，针对所述子树的当前节点，执行以下操作之一：

确定所述子树的当前节点和所述世界状态MPT的当前节点是叶节点并且他们的值不相等，且作为响应，将所述世界状态MPT的当前节点添加到所述更新树，

确定所述子树的当前节点和所述世界状态MPT的当前节点是扩展节点，且作为响应，将所述世界状态MPT的当前节点添加到所述更新树，并且移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为所述扩展节点引用的节点，

确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且他们的值不相等，且作为响应，将所述世界状态MPT的当前节点添加到所述更新树，

确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且他们的值相等，且作为响应，并且移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为所述子树的当前节点的槽指向的节点；

所述共识客户端将所述子树的所述更新树发送到所述区块链网络的非共识客户端，所述非共识客户端使用所述更新树更新本地存储的子树以提供更新的子树，所述更新的子树提供与所述非共识客户端关联的账户的状态。

2.如权利要求1所述的方法，还包括：

在至少一次迭代期间，查找所述世界状态MPT中的相应节点，并提供搜索路径，所述搜索路径中的一个或多个节点被标记为中间节点，并被标记为不在所述子树中。

3.如权利要求1所述的方法，其中，响应于确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且当前迭代是所述子树的当前节点被考虑的首次迭代，将所述子树的当前节点的值与所述世界状态MPT的当前节点的值进行比较。

4.如权利要求1所述的方法，其中，响应于确定所述子树的当前节点是所述根节点，终止所述遍历。

5.如权利要求1所述的方法，其中，所述本地存储的子树是通过一次或多次地用所述更新树的节点替换该子树的节点，并将所述更新树的节点插入该子树来更新的。

6.如权利要求1所述的方法，其中，响应于所述共识客户端从所述非共识客户端接收到的请求而创建所述更新树。

7.如权利要求1所述的方法，其中，响应于确定所述子树的根节点的值与所述世界状态MPT的所述根节点的值不同而创建所述更新树。

8.一种耦接到一个或多个计算机且其上存储有指令的非暂时性计算机可读存储介质，所述指令能够执行以更新区块链网络内的世界状态默克尔帕特里夏字典树MPT的子树，所述指令能够由所述一个或多个计算机执行以实现以下操作：

确定所述子树的所述当前节点和所述世界状态MPT的所述当前节点是分支节点，并且他们的值不相等，且作为响应，将所述世界状态MPT的所述当前节点添加到所述更新树，

确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且他们的值相等，且作为响应，移动至所述遍历的下一次迭代，该下一次迭代将所述子树的当前节点设置为所述子树的当前节点的槽指向的节点；

9.如权利要求8所述的计算机可读存储介质，进一步配置有可由所述一个或多个计算机执行的指令以实现以下操作：在至少一次迭代期间，查找所述世界状态MPT中的相应节点，并提供搜索路径，所述搜索路径中的一个或多个节点被标记为中间节点，并被标记为不在所述子树中。

10.如权利要求8所述的计算机可读存储介质，其中，响应于确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且当前迭代所述子树的当前节点被考虑的首次迭代，将所述子树的所述节点的值与所述世界状态MPT的当前节点的值进行比较。

11.如权利要求8所述的计算机可读存储介质，其中，响应于确定所述子树的当前节点是所述根节点，终止所述遍历。

12.如权利要求8所述的计算机可读存储介质，其中，所述本地存储的子树是通过一次或多次地用所述更新树的节点替换该子树的节点，并将所述更新树的节点插入该子树来更新的。

13.如权利要求8所述的计算机可读存储介质，其中，响应于所述共识客户端从所述非共识客户端接收到的请求而创建所述更新树。

14.如权利要求8所述的计算机可读存储介质，其中，响应于确定所述子树的根节点的值与所述世界状态MPT的所述根节点的值不同而创建所述更新树。

15.一种系统，包括：

一个或多个计算机；以及

耦接到所述一个或多个计算机并存储有指令的一个或多个计算机可读存储器，所述指令能够执行以更新区块链网络内的世界状态默克尔帕特里夏字典树MPT的子树，所述指令能够由所述一个或多个计算机执行所述指令以实现以下操作：

由所述共识客户端将所述子树的所述更新树发送到所述区块链网络的非共识客户端，所述非共识客户端使用所述更新树更新本地存储的子树以提供更新的子树，所述更新的子树提供与所述非共识客户端关联的账户的状态。

16.如权利要求15所述的系统，其中，所述一个或多个计算机可读存储器被进一步配置有能够由所述一个或多个计算机执行的指令以实现以下操作：在至少一次迭代期间，查找所述世界状态MPT中的相应节点，并提供搜索路径，所述搜索路径中的一个或多个节点被标记为中间节点，并被标记为不在所述子树中。

17.如权利要求15所述的系统，其中，响应于确定所述子树的当前节点和所述世界状态MPT的当前节点是分支节点，并且当前迭代是所述子树的当前节点被考虑的首次迭代，将所述子树的当前节点的值与所述世界状态MPT的当前节点的值进行比较。

18.如权利要求15所述的系统，其中，响应于确定所述子树的当前节点是所述根节点，终止所述遍历。

19.如权利要求15所述的系统，其中，所述本地存储的子树是通过一次或多次地用所述更新树的节点替换该子树的节点，并将所述更新树的节点插入该子树来更新的。

20.如权利要求15所述的系统，其中，响应于所述共识客户端从所述非共识客户端接收到的请求而创建所述更新树。

21.如权利要求15所述的系统，其中，响应于确定所述子树的根节点的值与所述世界状态MPT的所述根节点的值不同而创建所述更新树。