[發明專利]一種基于區塊鏈的并發交易處理方法及其應用

在審

• 申請號: 202210810789.1
• 申請日: 2022-07-11
• 公開（公告）號: CN115018648A
• 公開（公告）日: 2022-09-06
• 發明（設計）人: 李京;陳聰;王盛姣;熊航;王碩
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06Q40/04
• 分類號: G06Q40/04;G06F16/27;G06F16/23
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于區塊鏈的并發交易處理方法，其特征是應用于由區塊鏈、狀態數據庫S所組成的交易環境中，所述區塊鏈的區塊中存儲有用戶進行商品交易所產生的交易信息，所述狀態數據庫S中記錄有所有數據對象的最新值；所述并發交易處理方法是按如下步驟進行：

步驟1：更新維護狀態數據庫S為最新值；

步驟1.1、定義狀態數據庫S＝{s₁,s₂,...,s_i,...,s_I}，其中，s_i表示第i個數據對象a_i的狀態信息，I為狀態信息的總條數；令第i個數據對象a_i的狀態信息s_i是一個三元組其中，表示第i個數據對象a_i的鍵，表示第i個數據對象a_i的當前最新的版本號，表示第i個數據對象a_i的當前值；

步驟1.2、構建待上鏈區塊的交易信息集合，記為TX＝{tx₁,tx₂,...,tx_p,...,tx_P}，其中，tx_p表示第p條交易信息，P為交易信息的總條數；所述第p條交易信息tx_p包含的操作數據，記為其中，d_q,p表示第p條交易信息tx_p中的第q個操作，Q_p表示第p條交易信息tx_p包含的最大操作數；令所述第p條交易信息tx_p中的第q個操作數據d_q,p包含三元組其中，key_q,p表示第q個操作數據d_q,p訪問數據對象的鍵，表示第q個操作數據d_q,p讀取數據對象的版本號，表示第q個操作數據d_q,p寫入數據對象的值；

步驟1.3、遍歷交易信息集合TX，并對第p條交易信息tx_p構建對應的交易讀集其中，是第p條交易tx_p讀取的第j個鍵版本對信息，key_j,p,分別表示第p條交易tx_p讀取的第j個數據對象的鍵和版本號，J是第p條交易tx_p讀取操作的總數；

步驟1.4、遍歷交易讀集RS_p中的鍵版本對信息，對第j個鍵版本對信息如果狀態數據庫S中不存在鍵為key_j,p的數據對象或者存在鍵為key_j,p的數據對象對應的版本號小于則更新S中對應條目為其中，表示鍵為key_j,p，版本號為的數據對象的值；

步驟2：區塊數據預處理；

步驟2.1、遍歷交易信息集合TX，對第p條交易信息tx_p，構建對應的交易寫集其中，是第p條交易tx_p寫入的第k個鍵值對信息，key_k,p,分別表示第p條交易tx_p寫入的第k個數據對象的鍵和值，K是第p條交易tx_p寫入操作的總數；

步驟2.2、如果第p條交易信息tx_p的交易寫集WS_p為空，則表示第p條交易信息tx_p為讀交易，并將第p條交易信息tx_p在區塊中的位置前移到第一位；否則，表示第p條交易信息tx_p為寫交易，并保持不動；

步驟2.3、遍歷交易信息集合TX，如果第p條交易信息tx_p的交易讀集RS_p中存在一個鍵版本對滿足小于狀態數據庫S中鍵為key_l,p的數據對象對應的版本號，則將相應交易標記出來，且被標記的交易不參與步驟3和步驟4；

步驟3：求解最大可合并交易序列集；

步驟3.1、遍歷交易信息集合TX，對第p條交易信息tx_p，構建對應的值增量集ΔV_p＝{＜key_1,p,Δval_1,p＞,＜key_2,p,Δval_2,p＞,...,＜key_e,p,Δval_e,p＞,...,＜key_E,p,Δval_E,p＞}，其中，＜key_e,p,Δval_e,p＞是第p條交易tx_p涉及的第e個數據對象的鍵和增值，E是第p條交易tx_p涉及的數據對象總數；

步驟3.2、判定交易是否語義合法：

對第p條交易信息tx_p，遍歷ΔV_p，并根據式(1)計算鍵為key_e,p的數據對象a_e的新值val_e,p：

式(1)中，是鍵為key_e,p的數據對象a_e在狀態數據庫S中記錄的值，如果第p條交易信息tx_p涉及的所有數據對象的新值都大于等于0，則判定第p條交易信息tx_p的語義合法，否則標記第p條交易信息tx_p的語義不合法；

步驟3.3、定義一個數組arr，對第p條交易信息tx_p，令arr[p]表示以tx_p作為最后一條交易信息的最長合法交易序列的長度，初始化arr[p]為0；

步驟3.4、定義最大可合并交易序列集為B；

步驟3.5、記執行第p條交易tx_p后得到的狀態數據庫為S_p；記除tx_p外任意一條交易為tx_g；記執行第g條交易tx_g后得到的狀態數據庫為S_g；如果基于狀態數據庫S_p執行交易tx_g是合法的，則記是安全的；

步驟3.6、基于狀態數據庫S和交易信息集TX，利用式(2)更新數組arr中的元素arr[p]，從而更新數組arr中的所有元素：

式(2)中，max(·)表示取最大值，∧表示且；

步驟3.6、找到數組arr中的最大值以及其對應的索引t，即arr[t]為數組arr中的最大值，令arr[t]對應的交易序列為最長合法交易子序列L＝(tx′₁,tx′₂,...tx′_i,...,tx′_t)，i∈[1,t]，其中，tx′_i表示交易序列L包含的任意一個交易，交易序列L包含的交易數|L|≤t，且在交易信息集合TX中能找到一個交易tx_k，使得tx′_t＝tx_k，k∈[1,t]；

步驟3.8、將最長合法交易子序列L添加到最大可合并交易序列集B中，并執行L中交易后得到的狀態數據庫記為S′，并由除L中的交易以外的所有交易構成余下的交易信息集TX′；

步驟3.9、基于狀態數據庫S′和余下的交易信息集TX′重復步驟3.6～3.8，直至最大可合并交易序列集B不再更新為止，從而得到更新后的最大可合并交易序列集B′；

步驟4：合并交易；

步驟4.1、根據狀態數據庫S和更新后的最大可合并交易序列集B′，得到新的狀態數據庫S_B；

步驟4.2、建立一個空的讀集RS′和一個空的寫集WS′；

步驟4.3、遍歷交易信息集TX，將TX中的任意一個交易訪問的任意一個數據對象b_h的鍵及其在狀態數據庫S中的版本號構成的二元組添加到讀集RS′中；

步驟4.4、遍歷交易信息集TX，將TX中的任意一個交易訪問的任意一個數據對象b_h的鍵及其在狀態數據庫S_B中的值構成的二元組添加到寫集WS′中；

步驟4.5、由讀集RS′，寫集WS′與最大可合并交易序列集B′中的交易序列構成處理完成的合并交易。