[發明專利]構建區塊鏈世界狀態默克爾帕特里夏字典樹子樹

有效

• 申請號: 201980003201.8
• 申請日: 2019-03-04
• 公開（公告）號: CN110800008B
• 公開（公告）日: 2023-06-30
• 發明（設計）人: 張文彬
• 申請（專利權）人: 創新先進技術有限公司
• 主分類號: G06Q20/38
• 分類號: G06Q20/38;G06Q20/40
• 代理公司: 北京博思佳知識產權代理有限公司 11415
• 代理人: 艾佳

本文實施方式包括通過多次迭代遍歷世界狀態MPT，在每次迭代中，針對世界狀態MPT的當前節點，執行以下操作之一：將當前節點標記為賬戶節點，并將該當前節點的地址存儲在地址列表中，確定該當前節點是擴展節點，并且移動至遍歷的下一次迭代，該下一次迭代將該當前節點設置為擴展節點引用的節點，將該當前節點標記為過渡節點，并將該當前節點的地址存儲在地址列表中；基于地址列表創建世界狀態MPT的子樹，子樹的根節點包括世界狀態MPT的根節點，子樹的與世界狀態MPT的節點對應的一個或多個子節點的地址存儲在地址列表中。

背景技術

分布式賬本系統(DLS)，也可稱為共識網絡和/或區塊鏈網絡，使參與的實體能夠安全地且不可篡改地存儲數據。在不引用任何特定用例的情況下，DLS通常被稱為區塊鏈網絡。區塊鏈網絡的示例類型可以包括公有區塊鏈網絡、私有區塊鏈網絡和聯盟區塊鏈網絡。公有區塊鏈網絡向所有實體開放使用DLS，并開放參與共識處理。私有區塊鏈網絡針對特定實體提供，該實體集中控制讀寫權限。聯盟區塊鏈網絡針對選擇的實體組群提供，該實體組群控制共識處理，并且聯盟區塊鏈網絡包括訪問控制層。

哈希樹可以用于區塊鏈網絡存儲信息。例如，區塊鏈網絡的世界狀態(例如，區塊鏈網絡中的節點(賬戶)的狀態)可以被存儲在哈希樹中。哈希樹的示例包括維護區塊鏈網絡內的所有節點(賬戶)的世界狀態的世界狀態默克爾帕特里夏字典樹(Merkle?PatriciaTrie，MPT)。隨著區塊鏈網絡增長，世界狀態信息相應地增加，從而產生復雜的數據密集型哈希樹。

不是區塊鏈網絡內的所有節點都需要維護區塊鏈的世界狀態。例如，參與將交易添加到區塊鏈網絡內的區塊鏈的所謂的共識節點(全量客戶端)維護世界狀態哈希樹以能夠參與共識處理。僅在區塊鏈網絡內進行交易的其他節點(輕量客戶端)不需要維護世界狀態，或者甚至不需要知道世界狀態。然而，這樣的節點需要知道他們自己的狀態和在區塊鏈內與他們交易的其他節點的狀態(例如，局部狀態)。考慮到世界狀態哈希樹的大小和復雜度以及輕量客戶端使用的設備的資源限制，需要資源和帶寬高效的數據結構以及用于更新數據結構以維護區塊鏈網絡的局部狀態的處理。

發明內容

本文實施方式包括一種計算機實現的方法，用于生成世界狀態默克爾帕特里夏字典樹MPT的子樹并更新該子樹。

在一些實施方式中，動作包括：區塊鏈網絡的共識客戶端提供世界狀態MPT和用于存儲區塊鏈網絡內的節點的地址的地址列表，地址列表初始為空；共識客戶端通過多次迭代遍歷世界狀態MPT的至少一部分，并且在每次迭代中，針對世界狀態MPT的至少一部分的當前節點，執行以下操作之一：將當前節點標記為賬戶節點，并將當前節點的地址存儲在地址列表中，確定當前節點是擴展節點，并且移動至遍歷的下一次迭代，該下一次迭代將當前節點設置為擴展節點引用的節點，將當前節點標記為過渡節點，并將當前節點的地址存儲在地址列表中；共識客戶端基于地址列表創建世界狀態MPT的子樹，子樹的根節點包括世界狀態MPT的根節點，子樹的與世界狀態MPT的節點對應的一個或多個子節點的地址存儲在地址列表中；共識客戶端將世界狀態MPT的子樹發送到區塊鏈網絡的非共識客戶端，子樹提供與非共識客戶端關聯的賬戶的狀態。其他實施方式包括相應系統、設備和編碼在計算機存儲設備上被配置為執行方法的動作的計算機程序。

這些和其他實施方式均可可選地包括以下特征中的一個或多個：響應于確定當前節點是葉節點和值為空的分支節點之一，將當前節點標記為賬戶節點；響應于確定當前節點是分支節點，并且分支節點的所有子節點已被遍歷，將當前節點標記為過渡節點；在將當前節點標記為賬戶節點之后，遍歷的下一次迭代的當前節點包括賬戶節點的父節點；在將當前節點標記為賬戶節點和過渡節點之一之后，遍歷的下一次迭代的當前節點包括賬戶節點和過渡節點之一的子節點；基于地址列表創建世界狀態MPT的子樹至少部分地包括：針對地址列表中被標記為賬戶節點的地址，確定世界狀態MPT內的路徑，并將該路徑添加至子樹；遍歷包括深度優先前序遍歷。

本文還提供了耦接到一個或多個處理器并且其上存儲有指令的一個或多個非暫態計算機可讀存儲介質，當所述指令由所述一個或多個處理器執行時，所述指令將促使所述一個或多個處理器按照本文提供的方法的實施例執行操作。