TWI754901B

TWI754901B - 更新狀態默克樹的方法及裝置、電腦可讀儲存媒體、和計算設備

Info

Publication number: TWI754901B
Application number: TW109107263A
Authority: TW
Inventors: 陸鍾豪
Original assignee: 開曼群島商創新先進技術有限公司
Priority date: 2019-08-30
Filing date: 2020-03-05
Publication date: 2022-02-11
Also published as: TW202109305A; WO2021036175A1; CN110688377A; CN110688377B

Abstract

本說明書實施例提供一種更新狀態默克樹的方法和裝置，其中，狀態默克樹用於儲存區塊鏈網路中帳戶的狀態。方法包括以下步驟：首先，確定狀態默克樹中由帳戶的狀態變化導致需要更新的待更新節點；然後，根據待更新節點，從狀態默克樹中提取出第一子樹和M個第二子樹，第一子樹包含狀態默克樹的根節點，每個第二子樹的根節點為待更新節點，且為第一子樹中最底層節點的子節點。然後，將M個第二子樹分配給N個工作線程，使得N個工作線程至少部分並行地處理M個第二子樹，得到更新後的各個第二子樹；於是，至少基於更新後的各個第二子樹的根節點的雜湊值，更新第一子樹，從而得到更新後的狀態默克樹。

Description

更新狀態默克樹的方法及裝置、電腦可讀儲存媒體、和計算設備

本說明書一個或多個實施例係有關區塊鏈技術領域，尤其有關更新區塊鏈中用於記錄帳戶狀態的狀態默克樹的方法及裝置。

在新一代區塊鏈中，例如在乙太坊中，新增了帳戶的概念，相應地，用戶可以透過區塊鏈平台創建帳戶。在這樣的場景中，區塊鏈平台作用為區塊鏈網路中的節點，用戶創建的帳戶為乙太坊中的外部帳戶。此外，諸如乙太坊的許多區塊鏈平台支援智慧合約，來執行更為豐富的交易。智慧合約可以由用戶創建，在創建之後也具有對應的合約帳戶。如此，區塊鏈網路中的帳戶可以包括外部帳戶和合約帳戶。

在區塊鏈網路的各個節點中，在節點本地的資料庫中以狀態默克樹(Merkle tree)的形式維持區塊鏈中全部帳戶(包括外部帳戶和合約帳戶)的狀態資料。隨著區塊鏈中交易的執行，帳戶狀態會發生變化，這就需要更新狀態默克樹。由於區塊鏈網路中帳戶眾多，交易執行頻繁，因此，常常需要頻繁地對狀態默克樹進行更新。

因此，需要一種有效的方案，能夠更加高效地對記錄帳戶狀態的狀態默克樹進行更新，以提升區塊鏈網路的整體性能。

本說明書一個或多個實施例描述了一種更新狀態默克樹的方法及裝置，透過並行處理的方式，提高狀態默克樹的更新效率，提升區塊鏈網路的整體性能。

根據第一態樣，提供了一種更新狀態默克樹的方法，所述狀態默克樹用於儲存區塊鏈網路中帳戶的狀態，所述方法透過區塊鏈網路中任意節點來執行，包括：確定所述狀態默克樹中由所述帳戶的狀態變化導致需要更新的待更新節點；根據所述待更新節點，從所述狀態默克樹中提取出一個第一子樹和M個第二子樹，所述第一子樹包含所述狀態默克樹的根節點，所述M個第二子樹兩兩之間沒有交集，每個所述第二子樹的根節點為待更新節點，且為所述第一子樹中最底層節點的子節點，其中，M為大於1的整數；將所述M個第二子樹分配給N個工作線程，使得所述N個工作線程至少部分並行地處理所述M個第二子樹，得到更新後的各個第二子樹，其中，N為大於1的整數；至少基於所述更新後的各個第二子樹的根節點的雜湊值，更新所述第一子樹，從而得到更新後的狀態默克樹。

根據一種實施方式，在確定狀態默克樹中由所述帳戶的狀態變化導致需要更新的待更新節點之前，上述方法還包括，執行交易集合中的各條交易，確定所述各條交易涉及的帳戶的狀態變化。進一步地，在一個實施例中，上述交易集合可以為從本地交易池中選定的多條交易構成的集合；在這樣的情況下，在得到更新後的狀態默克樹之後，可以將所述交易集合打包到待產生的第一區塊中，並將所述更新後的狀態默克樹的根節點的雜湊值記錄到所述第一區塊中。在另一實施例中，上述交易集合可以為待驗證區塊中包含的交易構成的集合；在這樣的情況下，在得到更新後的狀態默克樹之後，可以將所述更新後的狀態默克樹的根節點的雜湊值與所述待驗證區塊中記錄的狀態根的值進行比較，以驗證所述待驗證區塊。根據一種實施方式，透過以下方式來確定所述狀態默克樹中的待更新節點：在所述狀態默克樹中，從狀態發生變化的各個帳戶所對應的各個葉節點向根節點回溯，將回溯路徑上經過的所有節點確定為所述待更新節點。在一個實施例中，透過以下方式提取第一子樹：在所述狀態默克樹中，提取從根節點到預定層數的節點，作為所述第一子樹。在另一實施例中，透過以下方式提取第一子樹：在所述狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第一預設閾值，則提取從根節點到目前層的節點作為所述第一子樹。根據一種實施方式，透過以下方來式提取第二子樹：獲取所述第一子樹的最底層節點中的待更新節點，作為第一節點集合；獲取第一節點集合中各個節點的子節點中的待更新節點，作為第二節點集合；分別將第二節點集合中各節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為所述M個第二子樹。根據另一種實施方式，透過以下方式來提取第一子樹和第二子樹：在所述狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第二預設閾值，則提取從根節點到目前層的上一層的節點作為所述第一子樹，並將目前層中各個待更新節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為所述M個第二子樹。在一個實施例中，透過以下方式而將M個第二子樹分配給N個工作線程：分別對所述M個第二子樹和所述N個工作線程進行編號，使得各個第二子樹具有對應的第一編號，各個工作線程具有對應的第二編號；對於所述M個第二子樹中任意的第二子樹，確定其對應的第一編號對N取模的結果，將其分配給第二編號為該取模結果的工作線程。根據第二態樣，提供了一種更新狀態默克樹的裝置，所述狀態默克樹用於儲存區塊鏈網路中帳戶的狀態，所述裝置係部署在區塊鏈網路中任意節點中，包括：節點確定單元，配置成確定所述狀態默克樹中由所述帳戶的狀態變化導致需要更新的待更新節點；子樹提取單元，配置成根據所述待更新節點，從所述狀態默克樹中提取出一個第一子樹和M個第二子樹，所述第一子樹包含所述狀態默克樹的根節點，所述M個第二子樹兩兩之間沒有交集，每個所述第二子樹的根節點為待更新節點，且為所述第一子樹中最底層節點的子節點，其中，M為大於1的整數；並行處理單元，配置成將所述M個第二子樹分配給N個工作線程，使得所述N個工作線程至少部分並行地處理所述M個第二子樹，得到更新後的各個第二子樹，其中，N為大於1的整數；綜合更新單元，配置成至少基於所述更新後的各個第二子樹的根節點的雜湊值，更新所述第一子樹，從而得到更新後的狀態默克樹。根據第三態樣，提供了一種電腦可讀儲存媒體，其上儲存有電腦程式，當所述電腦程式在電腦中執行時，令電腦執行第一態樣的方法。根據第四態樣，提供了一種計算設備，包括記憶體和處理器，其特徵在於，所述記憶體中儲存有可執行碼，所述處理器執行所述可執行碼時，實現第一態樣的方法。根據本說明書實施例提供的方法和裝置，在需要更新狀態默克樹時，將狀態默克樹中需要更新的部分劃分為位於上層的根子樹，以及根子樹以下多個相互獨立的髒子樹；然後利用多個工作線程並行對多個髒子樹進行更新處理；最後基於各個工作線程對髒子樹的更新結果，更新根子樹，從而更新整個狀態默克樹。相比於傳統的從葉節點逐層向上串列進行更新處理的方式，並行處理多個髒子樹再進行匯總的方式可以顯著提高狀態默克樹的更新效率，進而提高整個區塊鏈網路的系統性能。

下面結合圖式，對本說明書提供的方案進行描述。如本領域技術人員所知，在區塊鏈網路中，以區塊的形式記錄交易資料，新產生的區塊經過網路中各個節點的共識之後，添加到區塊鏈上，從而實現資料的不可篡改。圖1是在一個實施例中區塊結構示意圖。需要理解，圖1的區塊結構是以乙太坊為例來進行舉例說明的；其他區塊鏈平台產生的區塊結構可以與之略有不同。如圖1所示，區塊鏈中每個區塊至少包括區塊頭和交易清單，區塊頭中記錄用於將本區塊連結到區塊鏈上的多種資訊，包括父區塊的雜湊值，時間戳記，要計算的隨機數等等，交易清單中包含產生本區塊的節點從交易池中選擇收入本區塊中的一系列交易。為了便於查找和驗證帳戶狀態和交易狀態，乙太坊的區塊中還包括三棵默克樹的根資訊(root)，這三棵默克樹分別為狀態樹、交易樹和收據樹，相應的根資訊分別為狀態根、交易根和收據根。其中，狀態默克樹用於記錄區塊鏈網路中所有帳戶的狀態資訊，交易樹用於記錄本區塊中的交易內容資訊，收據樹用於記錄本區塊中的交易收據資訊。交易樹和收據樹為針對本區塊中的交易一次性產生的默克樹，一般不需要更新，而狀態默克樹則需要根據帳戶狀態的變化頻繁更新，因此，本說明書實施例中主要關注狀態默克樹。狀態默克樹以樹狀結構儲存狀態鍵Key和狀態值Value的對應關係，樹中的節點透過雜湊進行連接，即基於子節點產生雜湊值，儲存在父節點中。在記錄帳戶狀態的情況下，Key為帳戶地址，Value為帳戶狀態或帳戶內容。在具體實施例中，該狀態默克樹例如可以是MPT(Merkle Patricia Tree)樹，該MPT樹的葉子節點為各個帳戶的帳戶狀態，葉子節點上方的各個父節點包括帳戶地址的至少一個地址字符和對應於其全部子節點的雜湊值。基於各層節點可以遞迴得到根節點的雜湊值，該根雜湊即為該狀態樹的狀態根，記錄在圖1所示的區塊中。圖2示出狀態默克樹的一個具體示例。在圖2的示例中，狀態默克樹具體為MPT樹，包括4個葉節點和葉節點到根節點之間的一系列枝幹節點。4個葉節點分別對應於4個帳戶，葉節點的值即為帳戶的狀態資料。具體地，對於外部帳戶來說，其狀態資料可以包括，目前餘額(balance)，已發起交易序號(Nonce)；對於合約帳戶來說，其狀態資料進一步包括，合約代碼的雜湊，合約中變數的狀態，其中，合約變數的狀態可以透過進一步的狀態默克樹來記錄。在其他區塊鏈中，帳戶的狀態內容可以在以上舉例基礎上有所修改或添加，本說明書對此不作限定。葉節點和根節點之間的每個枝幹節點記錄帳戶地址的一部分字符和一個雜湊值，其中，雜湊值基於該枝幹接點的各個子節點而確定。例如，葉節點1記錄帳戶1的狀態資料，該狀態資料的雜湊值記錄於葉節點1的父節點，節點2中，即節點2中的雜湊值基於其子節點，節點1的值而確定；節點3中的雜湊值基於其兩個子節點，節點2和節點4的雜湊值而確定，如此繼續向上遞迴，直到根節點。此外，從根節點開始，沿節點的父子關係歷經的各枝幹節點中記錄的地址字符共同構成對應帳戶的帳戶地址，所歷經的路徑構成通向對應帳戶的定址路徑。例如，沿著節點5-＞節點3-＞節點2的路徑，各枝幹節點中記錄的地址字符共同構成帳戶1的帳戶地址。如此，透過圖2所示的狀態默克樹，可以記錄多個帳戶地址對應的多個帳戶的帳戶狀態。在另一示例中，可以在圖2的MPT樹的基礎上進行進一步的改進、擴展。例如，在有些區塊鏈平台中，在MPT樹的節點關係和樹結構的基礎上，在狀態默克樹中進一步引入了擴展節點、分支節點，從而更有效地記錄大量帳戶的帳戶地址和帳戶狀態。需要理解，以上圖2僅僅是一個示例，用於說明狀態默克樹的具體形式。還可以存在其他具體形式的狀態默克樹，本說明書對此不作限定。透過圖2的示例可以看到，狀態默克樹中最底層的葉節點用於記錄帳戶的狀態資料。如本領域技術人員所知，隨著區塊鏈網路中交易的執行，帳戶的狀態會發生改變。而根據以上狀態默克樹的結構設定，一旦葉節點的值發生變化，其父節點就需要更新其中的雜湊值，進一步的一系列向上的父節點均需要更新雜湊值。而區塊鏈網路中交易的傳播和執行是非常頻繁的，因此，狀態默克樹就需要頻繁地更新。一般地，每次更新狀態默克樹時，從底層葉節點依次遞迴地向上更新各個父節點，直到更新根雜湊。然而，由於記錄全量帳戶的帳戶狀態，狀態默克樹是一棵非常龐大的默克樹。上述習知方式的計算效率仍然不能滿足需要。因此，在本說明書的實施例中，提出一種新的更新狀態默克樹的方法，其中，將狀態默克樹拆分為多個互相獨立的、有待更新的子樹，如此可以並行地更新處理各個子樹，最後將更新結果合併，從而大幅提升狀態默克樹的更新效率。圖3示出根據一個實施例的更新狀態默克樹的方法流程圖；該方法可以適用於公有鏈、私有鏈、聯盟鏈，在此不做限制。該方法透過區塊鏈網路中任意節點來執行，其中，節點可以透過任何具有計算、處理能力的裝置、設備、平台、設備集群來實現。更具體地，該方法可以透過節點中的虛擬機器來執行。如圖3所示，更新狀態默克樹的方法可以包括以下步驟：步驟31，確定狀態默克樹中由帳戶的狀態變化導致需要更新的待更新節點；步驟32，根據待更新節點，從狀態默克樹中提取出一個第一子樹和M個第二子樹，其中，第一子樹包含狀態默克樹的根節點，每個第二子樹的根節點為待更新節點，且為第一子樹中最底層節點的子節點；步驟33，將M個第二子樹分配給N個工作線程，使得N個工作線程至少部分並行地處理所述M個第二子樹，得到更新後的各個第二子樹；步驟34，至少基於更新後的各個第二子樹的根節點的值，更新第一子樹，從而得到更新後的狀態默克樹。以下結合乙太坊區塊鏈平台來詳細描述以上各個步驟的執行過程，但是上述方法也同樣地適用於具有類似功能的其他區塊鏈平台。在一個可選實施例中，在步驟31之前，首先執行步驟30，執行交易集合中的各條交易，確定各條交易涉及的帳戶的狀態變化。該步驟30例如可以是在打包區塊時執行，或在驗證新產生區塊時執行。具體地，在一個例子中，在打包產生新區塊時執行步驟30。可以理解，區塊鏈網路中的任意節點可以執行區塊打包來產生新區塊，以力求將自己產生的新區塊添加到區塊鏈上。進行區塊打包產生新區塊的節點又可以稱為記帳節點。在打包產生新區塊時，記帳節點會從本地的交易池中選取若干交易，構成交易集合，將該交易集合包含在待產生區塊中。此時，執行打包的記帳節點需要執行上述交易集合中的各條交易，確定交易引起的帳戶狀態的變化。在另一例子中，在驗證新產生區塊時執行步驟30。可以理解，當記帳節點產生新區塊後，會將該新區塊在區塊鏈網路中廣播。其他節點會接收到該新區塊，並對其進行驗證。驗證新區塊的節點又可稱為驗證節點。為了驗證該新區塊，驗證節點需要從該新區塊的交易清單中提取出其中包含的交易構成的交易集合，執行該交易集合中的各條交易，從而確定交易引起的帳戶狀態的變化。在確定出帳戶的狀態變化的基礎上，在步驟31，確定狀態默克樹中由帳戶的狀態變化導致需要更新的待更新節點。為了描述的直觀和簡單，下文中將需要更新的待更新節點稱為“髒節點”；相應地，不需要更新的節點又可稱為乾淨節點。換而言之，步驟31即用於確定狀態默克樹中的髒節點。如前所述，狀態默克樹中的葉節點用於記錄帳戶的狀態資料。因此，確定出帳戶狀態的變化，就可以確定出狀態默克樹中發生更新的葉節點。此外，由於狀態默克樹中的節點透過雜湊來進行連接，子節點的雜湊值係儲存在父節點中，因此，如果一個節點是髒節點，它的雜湊值需要更新，那麼它的父節點也必然是髒節點。因此，步驟31的確定髒節點的過程可以包括，在狀態默克樹中，從狀態發生變化的帳戶所對應的葉節點向根節點回溯，將回溯路徑上經過的所有節點均確定為待更新的髒節點。圖4示出在一個實施例中確定髒節點的示意圖。在圖4的示例中，假定帳戶A1，A2，A3，A4和A5的狀態均發生了變化，那麼與之對應的葉節點發生更新，這些葉節點用灰色塊來示出。從這些葉節點向根節點方向遍歷，所經過的所有節點均可以確定為髒節點，髒節點也用灰色來示出。在確定出待更新髒節點的基礎上，在步驟32，根據這些待更新節點，從狀態默克樹中提取出一個第一子樹和M個第二子樹，使得第一子樹包含狀態默克樹的根節點，第二子樹的根節點為待更新節點，且為第一子樹中最底層節點的子節點。為了描述的直觀和簡單，下文又將第一子樹稱為根子樹(由於其包含整個狀態默克樹的根節點)，將第二子樹稱為髒子樹。可以採用多種策略從狀態默克樹中提取出根子樹和多個髒子樹。根據一種實現策略，首先按照一定標準選取根子樹(第一子樹)，然後基於根子樹提取得到髒子樹(第二子樹)。具體地，在一個實施例中，預先設定根子樹的層數LN作為選取根子樹的標準。於是，在狀態默克樹中，將根節點到預定層數LN的節點，作為根子樹。如此，確保根子樹的層數，或者說深度，滿足預設要求。在另一實施例中，預先設定根子樹最底層節點中髒節點的數目N1，作為根子樹選取標準。根據這樣的策略，在狀態默克樹中，從根節點開始按照寬度優先的原則逐層遍歷，如果目前層中髒節點的數目小於上述預設數目N1，則繼續遍歷下一層；如果目前層中髒節點的數目大於或等於上述預設數目N1，則停止遍歷，提取從根節點到目前層的節點作為根子樹。如此，確保根子樹中每層髒節點的數目滿足預設要求。在其他實施例中，還可以設定其他標準來選取根子樹，例如，其中，髒節點的總數目達到一定要求，等等。在按照以上任一種標準選取出根子樹之後，基於根子樹提取得到髒子樹。具體地，可以獲取根子樹的最底層節點中的髒節點，作為第一節點集合；再獲取第一節點集合中各個節點的子節點中的髒節點，作為第二節點集合；然後，分別將第二節點集合中各節點作為起始節點，將從各個起始節點直到葉節點的子樹作為髒子樹。如此，可以確保，各個髒子樹之間沒有交集，並且髒子樹的根節點是根子樹中最底層節點的子節點。下面延續圖4的例子，描述基於圖4的狀態默克樹中的髒節點確定根子樹和髒子樹的過程。假定在一個例子中，預設的根子樹最底層節點中髒節點數目閾值N1=3。那麼從圖4的根節點開始，逐層遍歷。第二層L1中髒節點數目為2，低於上述閾值N1，繼續到下一層；第三層L2中髒節點數目為3，達到了上述閾值N1，由此，可以將根節點到L2層的節點作為根子樹(第一子樹)，如圖5所示。現在結合圖5進行描述。在確定出根子樹後，開始提取髒子樹。可以看到，根子樹的最底層節點中有3個髒節點(這3個髒節點構成前述的第一節點集合)，這3個髒節點共有6個子節點，這6個子節點中有4個髒節點(這4個髒節點構成前述的第二節點集合)。於是，分別以這4個髒節點為起始節點(即髒子樹的根節點)，將從起始節點直到葉節點的子樹作為髒子樹，從而得到4個髒子樹。透過以上方式，先確定出根子樹，再基於根子樹底層節點的子節點中的髒節點，得到髒子樹，從而將整個狀態默克樹劃分為根子樹、髒子樹和其他乾淨的子樹。可以看到，根子樹透過其最底層節點與髒子樹關聯。根據另一種實現策略，也可以首先按照一定選取標準來選取髒子樹，進而得到根子樹；或者根據一定劃分標準，在某一層節點處進行劃分，從而分別得到根子樹和髒子樹。具體地，在一個實施例中，預設另一髒節點數目閾值N2。在狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中髒節點的數目小於上述閾值N2，則繼續遍歷；如果大於或等於該閾值N2，則將目前層中的各個髒節點作為起始節點，獲取從起始節點直到葉節點的子樹作為髒子樹；另外，提取從根節點到目前層的上一層的節點作為根子樹。根據這樣的策略，可以確保得到的髒子樹的數目大於或等於N2。仍然結合圖4的狀態默克樹進行描述。在一個例子中，假定預設的髒節點數目閾值N2=4。從圖4的根節點開始，逐層遍歷。第一層L0、第二層L1和第三層L2中髒節點數目均達不到該閾值N2，繼續到下一層；到第四層L3，髒節點數目為4，達到了上述閾值N2，於是，將該層中的4個髒節點分別作為起始節點(即髒子樹的根節點)，將從起始節點直到葉節點的子樹作為髒子樹，從而得到4個髒子樹。另外，將該層的上一層，即L2層，到整個默克樹根節點的節點作為根子樹。於是，同樣得到圖5所示的根子樹和髒子樹。儘管得到同樣的子樹，但是採用的策略並不相同。事實上，對於一個狀態默克樹，採用不同策略有可能得到不同的根子樹和髒子樹分布。例如，如果將N2也設定為3，那麼根子樹將只包含L0到L1層的節點，L2層中的髒節點則作為髒子樹的根節點，得到3個髒子樹。不管採用何種策略，最後得到的根子樹是從狀態默克樹的根節點開始到一定深度的子樹，而髒子樹的根節點則為根子樹最底層節點的子節點，且為髒節點。如此可以確保，各個髒子樹的根節點係位於同一層級之中，各個髒子樹之間兩兩互斥，沒有交集，因此，可以獨立地進行更新計算。因此，對於以上確定出的根子樹和髒子樹，在步驟33，將各個髒子樹分配給多個工作線程，使得各個工作線程並行處理髒子樹，對其進行更新。需要理解，此處的工作線程可以是與前述執行步驟31至32的線程不同的線程。在一個實施例中，透過主線程執行步驟31至32，在確定出多個髒子樹後，將該多個髒子樹分配給多個工作線程並行進行更新處理。一般而言，狀態默克樹通常具有比較均衡的樹結構，即各個葉節點離根節點的層數距離不會相差太大。由於各個髒子樹的根節點係位於同一層級之中，因此，各個髒子樹的深度也基本相當，因此，更新各個髒子樹的計算量也相當，這進一步有利於各個髒子樹的並行更新。為了描述的清楚和方便，假定步驟32得到的髒子樹的數目為M，可用的工作線程的數目為N。在一個例子中，髒子樹的數目M小於或等於可用的工作線程數目N。此時，可以將各個髒子樹依次分配給不同的工作線程。於是，M個髒子樹各自在不同的工作線程中完全並行地進行更新處理。更新處理的過程可以是，從髒子樹的葉節點開始，逐層向上重新計算髒節點的雜湊，直到髒子樹的根節點，從而實現髒子樹的更新。在一個例子中，髒子樹的數目M大於可用的工作線程數目N。此時，可以採取取模的方式來分配髒子樹。具體地，可以分別對M個髒子樹進行編號，例如編號為T(0)到T(M-1)；另外，對N個工作線程也進行編號，例如編號為W(0)到W(N-1)。對於M個髒子樹中任意的子樹i，確定其對應的編號對N取模的結果i mod N，將其分配給編號為該取模結果的工作線程WT(i mod N)。例如，假定有5個工作線程，9個髒子樹。則將編號為1和6的髒子樹分配到工作線程1，將編號為2和7的髒子樹分配到工作線程2，等等。在這樣的情況下，有可能一個工作線程分配獲得多個髒子樹，那麼該工作線程依次對分配到的髒子樹進行更新處理。對於全部M個髒子樹而言，由於分布在N個工作線程中，因此這M個髒子樹可以實現部分並行處理。在一個實施例中，也可以不對M與N的大小關係進行判斷，不管其關係如何，均採用取模的方式來分配髒子樹。在實踐中，可以透過調整子樹來選取標準中的預設閾值，使得得到的髒子樹的數目M與可用工作進程N的大小相當，從而提高髒子樹更新的並行度。在各個工作進程分別對各個髒子樹進行更新後，可以將各個髒子樹更新後的根雜湊提供給主線程。於是，在步驟34，主線程至少基於更新後的各個根節點的雜湊值，更新根子樹，從而得到更新後的整個狀態默克樹。可以理解，由於髒子樹的根節點是根子樹最底層節點的子節點，因此，基於各個髒子樹更新後的根雜湊，以及相應的乾淨節點的雜湊值，可以更新根子樹中的最底層節點，進而向上逐層遞迴，更新更上層髒節點的雜湊值，直到根節點。此時，根子樹也得到了更新。更新後的根子樹、更新後的髒子樹以及不需更新的乾淨子樹，共同構成整個更新後的狀態默克樹。如前所述，更新狀態默克樹可以發生在打包產生新區塊時，或驗證新區塊時。在產生新區塊的情況下，在得到更新的狀態默克樹之後，將之前選定的交易集合打包到區塊中，並將更新後的狀態默克樹的根雜湊記錄到區塊中，即記錄到圖1的狀態根中。在驗證新區塊的情況下，在得到更新的狀態默克樹之後，將更新後的狀態默克樹的根節點的雜湊值與待驗證區塊的狀態根的值進行比較，兩者一致則驗證通過。在實踐中，對於每次狀態默克樹的更新，可以僅記錄更新的節點的相關資料，採用連結或指標的方式，將其與保持不變的節點資料結合在一起。透過以上過程可以看到，在需要更新狀態默克樹時，根據本說明書的實施例，將狀態默克樹中需要更新的部分劃分為位於上層的根子樹，以及根子樹以下多個相互獨立的髒子樹；然後利用多個工作線程並行對多個髒子樹進行更新處理；最後基於各個工作線程對髒子樹的更新結果，更新根子樹，從而更新整個狀態默克樹。相比於傳統的從葉節點逐層向上串列進行更新處理的方式，並行處理多個髒子樹再進行匯總的方式可以顯著提高狀態默克樹的更新效率，進而提高整個區塊鏈網路的系統性能。根據另一態樣的實施例，提供了一種更新狀態默克樹的裝置，所述狀態默克樹用於儲存區塊鏈網路中帳戶的狀態，該裝置係部署在區塊鏈網路中任意節點中，該節點可以體現為任何具有計算、處理能力的設備、平台或設備集群。圖6示出根據一個實施例的狀態默克樹的更新裝置的示意性方塊圖。如圖6所示，該更新裝置600包括：節點確定單元61，配置成確定所述狀態默克樹中由所述帳戶的狀態變化導致需要更新的待更新節點；子樹提取單元62，配置成根據所述待更新節點，從所述狀態默克樹中提取出一個第一子樹和M個第二子樹，所述第一子樹包含所述狀態默克樹的根節點，所述M個第二子樹兩兩之間沒有交集，每個所述第二子樹的根節點為待更新節點，且為所述第一子樹中最底層節點的子節點，其中，M為大於1的整數；並行處理單元63，配置成將所述M個第二子樹分配給N個工作線程，使得所述N個工作線程至少部分並行地處理所述M個第二子樹，得到更新後的各個第二子樹，其中，N為大於1的整數；綜合更新單元64，配置成至少基於所述更新後的各個第二子樹的根節點的雜湊值，更新所述第一子樹，從而得到更新後的狀態默克樹。在一個實施例中，裝置600還包括帳戶狀態確定單元60，配置成執行交易集合中的各條交易，確定所述各條交易涉及的帳戶的狀態變化。具體地，在一個實施例中，上述交易集合可以為從本地交易池中選定的多條交易構成的集合。在這樣的情況下，裝置600還包括區塊產生單元(未示出)，配置成，在得到更新後的狀態默克樹之後，將所述交易集合打包到待產生的第一區塊中，並將所述更新後的狀態默克樹的根節點的雜湊值記錄到所述第一區塊中。在另一實施例中，上述交易集合為待驗證區塊中包含的交易構成的集合。在這樣的情況下，裝置600還包括區塊驗證單元(未示出)，配置成，在得到更新後的狀態默克樹之後，將所述更新後的狀態默克樹的根節點的雜湊值與所述待驗證區塊中記錄的狀態根的值進行比較，以驗證所述待驗證區塊。根據一種實施方式，所述節點確定單元61配置成：在所述狀態默克樹中，從狀態發生變化的各個帳戶所對應的各個葉節點向根節點回溯，將回溯路徑上經過的所有節點確定為所述待更新節點。在一個實施例中，所述子樹提取單元62配置成：在所述狀態默克樹中，提取從根節點到預定層數的節點，作為所述第一子樹。在另一實施例中，所述子樹提取單元62配置成：在所述狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第一預設閾值，則提取從根節點到目前層的節點作為所述第一子樹。進一步的，在一個實施例中，所述子樹提取單元62還配置成：獲取所述第一子樹的最底層節點中的待更新節點，作為第一節點集合；獲取第一節點集合中各個節點的子節點中的待更新節點，作為第二節點集合；分別將第二節點集合中各節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為所述M個第二子樹。根據另一種實施方式，所述子樹提取單元62配置成：在所述狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第二預設閾值，則提取從根節點到目前層的上一層的節點作為所述第一子樹，並將目前層中各個待更新節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為所述M個第二子樹。根據一個實施例，所述並行處理單元63配置成：分別對所述M個第二子樹和所述N個工作線程進行編號，使得各個第二子樹具有對應的第一編號，各個工作線程具有對應的第二編號；對於所述M個第二子樹中任意的第二子樹，確定其對應的第一編號對N取模的結果，將其分配給第二編號為該取模結果的工作線程。根據另一態樣的實施例，還提供一種電腦可讀儲存媒體，其上儲存有電腦程式，當所述電腦程式在電腦中執行時，令電腦執行結合圖3所描述的方法。根據再一態樣的實施例，還提供一種計算設備，包括記憶體和處理器，所述記憶體中儲存有可執行碼，所述處理器執行所述可執行碼時，實現結合圖3所述的方法。本領域技術人員應該可以意識到，在上述一個或多個示例中，本發明所描述的功能可以用硬體、軟體、韌體或它們的任意組合來實現。當使用軟體來實現時，可以將這些功能儲存在電腦可讀媒體中或者作為電腦可讀媒體上的一個或多個指令或碼來進行傳輸。以上所述的具體實施方式，對本發明的目的、技術方案和有益效果進行了進一步詳細說明，所應理解的是，以上所述僅為本發明的具體實施方式而已，並不用來限定本發明的保護範圍，凡在本發明的技術方案的基礎之上，所做的任何修改、等同替換、改進等，均應包括在本發明的保護範圍之內。

60:帳戶狀態確定單元 61:節點確定單元 62:子樹提取單元 63:並行處理單元 64:綜合更新單元 600:更新裝置

為了更清楚地說明本發明實施例的技術方案，下面將對實施例描述中所需要使用的圖式作簡單地介紹，顯而易見地，下面描述中的圖式僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些圖式而獲得其它的圖式。 [圖1]是在一個實施例中區塊結構示意圖； [圖2]示出狀態默克樹的一個具體示例； [圖3]示出根據一個實施例的更新狀態默克樹的方法流程圖； [圖4]示出在一個實施例中確定髒節點的示意圖； [圖5]示出根據一個實施例提取的第一子樹和第二子樹的示意圖； [圖6]示出根據一個實施例的狀態默克樹的更新裝置的示意性方塊圖。

L0:第一層

L1:第二層

L2:第三層

L3:第四層

Claims

一種更新狀態默克樹的方法，該狀態默克樹用於儲存區塊鏈網路中帳戶的狀態，該方法透過區塊鏈網路中任意節點來執行，包括：確定該狀態默克樹中由該帳戶的狀態變化導致需要更新的待更新節點；根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹，該第一子樹包含該狀態默克樹的根節點，該M個第二子樹兩兩之間沒有交集，每個該第二子樹的根節點為待更新節點，且為該第一子樹中最底層節點的子節點，其中，M為大於1的整數；將該M個第二子樹分配給N個工作線程，使得該N個工作線程至少部分並行地處理該M個第二子樹，得到對應於該M個第二子樹之M個更新後的根雜湊，其中，N為大於1的整數；至少基於從該N個工作線程得到之該M個更新後的根雜湊，從該第一子樹的一或多個葉節點到該狀態默克樹的該根節點更新該第一子樹，從而得到更新後的狀態默克樹；以及在得到更新後的狀態默克樹之後，將該更新後的狀態默克樹的根節點的雜湊值與該待驗證區塊中記錄的狀態根的值進行比較，以驗證該待驗證區塊，其中，該交易集合為該待驗證區塊中包含的交易構成的集合。
如請求項1所述的方法，還包括，在確定該狀態默克樹中由該帳戶的狀態變化導致需要更新的待更新節點之前，執行交易集合中的各條交易，確定該各條交易涉及的帳戶的狀態變化。
如請求項2所述的方法，其中，該交易集合為從本地交易池中選定的多條交易構成的集合；該方法還包括，在得到更新後的狀態默克樹之後，將該交易集合打包到待產生的第一區塊中，並將該更新後的狀態默克樹的根節點的雜湊值記錄到該第一區塊中。
如請求項1所述的方法，其中，確定該狀態默克樹中由該帳戶狀態的變化導致需要更新的待更新節點，包括：在該狀態默克樹中，從狀態發生變化的各個帳戶所對應的各個葉節點向根節點回溯，將回溯路徑上經過的所有節點確定為該待更新節點。
如請求項1所述的方法，其中，根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹，包括：在該狀態默克樹中，提取從根節點到預定層數的節點，作為該第一子樹。
如請求項1所述的方法，其中，根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹，包括：在該狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第一預設閾值，則提取從根節點到目前層的節點作為該第一子樹。
如請求項5或6所述的方法，其中，根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹包括：獲取該第一子樹的最底層節點中的待更新節點，作為第一節點集合；獲取第一節點集合中各個節點的子節點中的待更新節點，作為第二節點集合；以及分別將第二節點集合中各節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為該M個第二子樹。
如請求項1所述的方法，其中，根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹包括：在該狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第二預設閾值，則提取從根節點到目前層的上一層的節點作為該第一子樹，並將目前層中各個待更新節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為該M個第二子樹。
如請求項1所述的方法，其中，將該M個第二子樹分配給N個工作線程包括：分別對該M個第二子樹和該N個工作線程進行編號，使得各個第二子樹具有對應的第一編號，各個工作線程具有對應的第二編號；以及對於該M個第二子樹中任意的第二子樹，確定其對應的第一編號對N取模的結果，將其分配給第二編號為該取模結果的工作線程。
一種更新狀態默克樹的裝置，該狀態默克樹用於儲存區塊鏈網路中帳戶的狀態，該裝置係部署在區塊鏈網路中任意節點中，包括：節點確定單元，配置成確定該狀態默克樹中由該帳戶的狀態變化導致需要更新的待更新節點；子樹提取單元，配置成根據該待更新節點，從該狀態默克樹中提取出一個第一子樹和M個第二子樹，該第一子樹包含該狀態默克樹的根節點，該M個第二子樹兩兩之間沒有交集，每個該第二子樹的根節點為待更新節點，且為該第一子樹中最底層節點的子節點，其中，M為大於1的整數；並行處理單元，配置成將該M個第二子樹分配給N個工作線程，使得該N個工作線程至少部分並行地處理該M個第二子樹，得到對應於該M個第二子樹之M個更新後的根雜湊，其中，N為大於1的整數；綜合更新單元，配置成至少基於從該N個工作線程得到之該M個更新後的根雜湊，從該第一子樹的一或多個葉節點到該狀態默克樹的該根節點更新該第一子樹，從而得到更新後的狀態默克樹；以及區塊驗證單元，配置成在得到更新後的狀態默克樹之後，將該更新後的狀態默克樹的根節點的雜湊值與待驗證區塊中記錄的狀態根的值進行比較，以驗證該待驗證區塊，其中，該交易集合為該待驗證區塊中包含的交易構成的集合。
如請求項10所述的裝置，還包括，帳戶狀態確定單元，配置成執行交易集合中的各條交易，確定該各條交易涉及的帳戶的狀態變化。
如請求項11所述的裝置，其中，該交易集合為從本地交易池中選定的多條交易構成的集合；該裝置還包括區塊產生單元，配置成在得到更新後的狀態默克樹之後，將該交易集合打包到待產生的第一區塊中，並將該更新後的狀態默克樹的根節點的雜湊值記錄到該第一區塊中。
如請求項10所述的裝置，其中，該節點確定單元配置成：在該狀態默克樹中，從狀態發生變化的各個帳戶所對應的各個葉節點向根節點回溯，將回溯路徑上經過的所有節點確定為該待更新節點。
如請求項10所述的裝置，其中，該子樹提取單元配置成：在該狀態默克樹中，提取從根節點到預定層數的節點，作為該第一子樹。
如請求項10所述的裝置，其中，該子樹提取單元配置成：在該狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第一預設閾值，則提取從根節點到目前層的節點作為該第一子樹。
如請求項14或15所述的裝置，其中，該子樹提取單元還配置成：獲取該第一子樹的最底層節點中的待更新節點，作為第一節點集合；獲取第一節點集合中各個節點的子節點中的待更新節點，作為第二節點集合；以及分別將第二節點集合中各節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為該M個第二子樹。
如請求項10所述的裝置，其中，該子樹提取單元配置成：在該狀態默克樹中，從根節點開始按照寬度優先逐層遍歷，如果目前層中待更新節點的數目大於或等於第二預設閾值，則提取從根節點到目前層的上一層的節點作為該第一子樹，並將目前層中各個待更新節點作為起始節點，獲取從各個起始節點直到葉節點的子樹作為該M個第二子樹。
如請求項10所述的裝置，其中，該並行處理單元配置成：分別對該M個第二子樹和該N個工作線程進行編號，使得各個第二子樹具有對應的第一編號，各個工作線程具有對應的第二編號；以及對於該M個第二子樹中任意的第二子樹，確定其對應的第一編號對N取模的結果，將其分配給第二編號為該取模結果的工作線程。
一種電腦可讀儲存媒體，其上儲存有電腦程式，當該電腦程式在電腦中執行時，令電腦執行如請求項1至9中任一項的所述的方法。
一種計算設備，包括記憶體和處理器，其特徵在於，該記憶體中儲存有可執行碼，該處理器執行該可執行碼時，實現如請求項1至9中任一項所述的方法。