基于門限環簽名的可刪除區塊鏈

任艷麗，徐丹婷，張新鵬，谷大武

（1. 上海大學通信與信息工程學院，上海 200444；2. 上海交通大學電子信息與電氣工程學院，上海 200240）

1 引言

區塊鏈技術[1]運用數據加密、時間戳、分布式共識和經濟激勵等手段，在節點不需要互相信任的分布式系統中實現去中心化的點對點交易，同時能按照時間順序將交易相關數據以數據區塊的形式存儲，其中，數據區塊以鏈條的方式組合成特定數據結構，并以密碼學原理保證數據不可篡改和不可偽造，形成去中心化的共享總賬。區塊鏈技術以其區別于中心化系統的核心優勢，引起了人們的廣泛關注，擁有廣泛的應用前景[2]。

共識機制是區塊鏈實現去中心化的核心內容，其中基于工作量的證明（PoW, proof of work）[1,3]和基于權益的證明（PoS, proof of stake）[4-5]是最為普遍的區塊鏈共識機制。但是，PoW會造成大量的電力能源損耗，且挖礦過程中產生的算力無法應用于別處，是一種純粹的算力損耗；而PoS挖礦成本低，容易受到攻擊，且挖礦收益與權益的相互促進，使系統日益趨于中心化。2017年，Park等[6]提出了基于空間證明的共識機制（PoSpace, proof of space），通過存儲空間的競爭來獲得記賬權，即競爭節點分別給出自身存儲空間大小的證明，驗證通過后空間大的節點生成新的區塊。同 PoW 和 PoS體制相比，PoSpace基于空間證明，不需要復雜的計算，大大降低了能源消耗，提高了共識效率，且節點的磁盤空間在證明結束后可得到釋放，用于下一次競爭，實現了資源的循環使用。

匿名性是區塊鏈交易中實現用戶隱私保護的基本要求，而環簽名對數據進行認證的同時可確保簽名者的匿名性，是區塊鏈研究中的重要工具。環簽名是Rivest等[7]在2001年提出的，允許某個成員代表一組用戶進行簽名，而不泄露簽名用戶的身份。隨后，Bresson等[8]提出了門限環簽名，即環中的部分成員只要達到規定的門限值，就可以代表環中所有用戶進行簽名，該方案提出了公平拆分的思想，并在隨機預言模型中可證安全。當簽名人數較少時，方案是高效的，但是當簽名人數較多時，方案效率較低。Toshiyuki等[9]針對簽名人數較多的情況，提出了高效的門限環簽名方案，但該方案存在安全問題，詳細分析請見本文第3節。Chung等[10]使用雙線性對映射，提出了基于身份的門限環簽名方案，但效率不高。以上方案都是基于傳統的密碼學困難問題，如陷門單向函數、離散對數問題等。2011年，Melchor等[11]基于編碼理論，提出了高效的門限環簽名方案。Zhang等[12]基于 MQ（multivariate quadratic）問題，提出了抗量子攻擊的門限環簽名方案。

隨著區塊鏈的發展，存儲所有區塊數據需要巨大的存儲空間，對于普通節點來說存儲代價很大。而在實際應用中，有的區塊數據已經過期或失效，比如已經宣布破產的銀行交易信息、已經廢除的法律文件等。這些數據永久存儲在區塊鏈中已經失去了價值，且占用大量空間，造成資源浪費。如果經大多數用戶同意后，可刪除這些失效的數據，而又不影響區塊鏈中其他數據的存儲和使用，有助于釋放節點的存儲空間，降低存儲代價，具有重要的應用價值。目前絕大多數區塊鏈結構是不允許刪除數據的，數據一旦寫入鏈中就不能更改，可能會造成過期數據占用大量存儲空間的問題。

在區塊鏈研究中，愛哲森公司基于變色龍散列，提出了可編輯區塊鏈技術[13]。只要知道變色龍散列的陷門，就可以找到已有數據的一個碰撞，從而實現對區塊鏈數據的編輯。但在該方法中，散列函數的陷門存儲在一個可信中心，因此對數據的編輯權過于中心化。Li等[14]使用秘密共享技術，將變色龍散列的陷門分成多份，并分配給各個網絡節點。當一半以上的網絡節點同意時，可恢復散列函數的陷門，找到已有數據的碰撞，對區塊鏈數據進行修改。以上2種方法均使用變色龍散列，而目前的區塊鏈結構大多使用抗碰撞的散列函數，因此上述方法的適用范圍非常有限?；诳古鲎驳纳⒘泻瘮?，本文提出了可刪除的區塊鏈方案，適用于大多數區塊鏈結構，具有廣闊的應用前景。

本文首先分析了文獻[9]中的門限環簽名方案，指出了該方案的安全問題，提出了改進方案，并在隨機預言模型中可證安全。隨后，使用改進的門限環簽名方案，基于空間證明的共識機制提出了可刪除的區塊鏈。當數據過期或失效時，經大多數用戶同意并簽名，對過期數據進行刪除，并保持區塊鏈的結構不變，不影響其他區塊的存儲和使用。所有人可對數據進行驗證，包括被刪除數據的相關信息。

2 基礎知識

2.1 門限環簽名

環簽名[7]主要包括以下算法。

setup算法：輸入安全參數λ，輸出n個環成員的公鑰PK1,…, P Kn和私鑰SK1,…,S Kn。

ring-sign算法：輸入消息m、n個環成員公鑰PK1,…, P Kn和簽名用戶私鑰SKS，輸出環簽名σ。

ring-verify算法：輸入環成員公鑰PK1,…,PKn和簽名(m,σ)，輸出“接收”或者“拒絕”。

安全的環簽名需要滿足正確性、不可偽造性以及匿名性，即合法環簽名可以驗證通過，非環成員不能偽造合法的環簽名，且任何人不能獲得環簽名用戶的真實身份。

在此基礎上，門限環簽名[8]包括以下算法。

setup算法：輸入安全參數λ，輸出n個環成員的公鑰PK1,…, P Kn和私鑰SK1,…,S Kn。

T-ring-sign算法：輸入消息m、n個環成員公鑰PK1,…, P Kn和n-t個簽名用戶私鑰SKi,1,… ,SKi,n-t，輸出環簽名σ。

T-ring-verify算法：輸入環成員公鑰PK1,…,PKn和簽名(m,σ)，輸出“接收”或者“拒絕”。

本文所提環簽名方案中用到了文獻[7]中提出的用戶拆分方法，下面做簡要介紹。

定義 1 公平拆分[7]。假設系統中n個用戶被拆分為t個子集π=(π1,… ,πt)，I= {i1, …,it}表示其中t個用戶編號的集合。對于集合I，如果對于所有的j∈[1,t]，均有就稱π是一個公平拆分，其中#(X)表示集合X中元素的個數。

如文獻[7]所述，為了確保環簽名中用戶的匿名性，對于任意包含t個用戶的集合，都要存在一個公平拆分，稱為完備拆分系統。具體定義如下。

定義 2 完備拆分系統[7]。令t＜n-t＜n，對于任意包含t個用戶編號的集合I，都存在一個公平拆分，這樣的系統稱為(n,t)-完備拆分系統。

2.2 環簽名安全模型

本節介紹門限環簽名方案的安全模型，即選擇消息攻擊下的強不可偽造性（SU-TRS-CMA, strong unforgeability against chosen message attack in a threshold ring signature scheme）。

定義3 SU-TRS-CMA。假設環中共有n個成員，其中n-t個成員可代表所有用戶簽名。通過以下游戲，本文定義TRS（threshold ring signature）方案在選擇消息攻擊下的強不可偽造性[8,15]。游戲包含2個參與者：挑戰者和敵手。具體包括以下步驟。

setup 挑戰者執行setup算法獲得所有環成員公鑰PK1,…, P Kn和私鑰SK1,…,S Kn，并發送公鑰給敵手。

階段1 敵手適應性地進行下列詢問。

散列詢問：敵手發送字符串給挑戰者，挑戰者選擇隨機數作為對應的散列值，并返還給敵手。

私鑰詢問：敵手發送用戶公鑰給挑戰者，挑戰者返回對應私鑰給敵手，敵手至多可詢問n-t-1個用戶的私鑰。

簽名詢問：敵手發送消息m給挑戰者。挑戰者隨機選擇n-t個環成員私鑰根據T-ring-sign算法生成簽名σ，并返回給敵手。

挑戰階段 假設敵手能以不可忽略的概率ε偽造有效的門限環簽名，并將消息m*的環簽名σ*發送給挑戰者，且 (m*,σ*)沒有出現在簽名詢問階段。挑戰者可根據 (m*,σ*)，以不可忽略的概率ε′解決單向函數的求逆問題。

在上述游戲中，敵手的優勢定義為ε，即成功偽造門限環簽名的概率。如果對于任意t多項式時間的敵手，在經過q次詢問后，至多能以概率ε偽造有效的環簽名，則稱門限環簽名方案在選擇消息攻擊下是(t,q,ε)-強不可偽造的。

由以上安全模型，如果門限環簽名方案滿足強不可偽造性，則攻擊者即使得到消息m的簽名σ，也不能偽造m的其他有效簽名

2.3 基于空間證明的區塊鏈

PoSpace共識機制[6]基于“一定時間內需要一定空間構造一個結構圖”這一事實，展開空間競爭。首先，介紹空間證明過程。如圖1所示，設定有向無環結構圖為頂點集合，N為頂點個數，E為有向邊集合。圖中各頂點因為有向邊而存在一定的聯系，為進一步表示頂點之間的聯系，突出該圖的結構，為每個頂點設置與之相關聯的標簽值，具體為

其中，i為頂點序號，μ為可設定的隨機數，為鏈向當前頂點i的所有前向頂點，即其母頂點的標簽值。這樣，每個頂點與其母頂點便依靠標簽值聯系起來，形成了基于頂點標簽值的有向圖結構。

圖1 有向無環結構圖

從圖1可以看出，要實現對以上結構圖的存儲需要一定的空間，空間越大，越容易實現結構圖的存儲與恢復。而在空間不足時，只能多次利用僅有的空間存儲相關數據，反復存儲與刪除，以時間換取空間。因此當時間一定時，空間大小不同的礦工對同一結構圖的存儲效率便高低不齊，產生基于空間的競爭。PoSpace正是在這樣的模型下建立的。

PoSpace共識系統會生成如圖1所示的結構圖，每個礦工都可以依據自己的空間大小，最大程度并最優化地存儲該結構圖。系統會選擇存儲空間最大的礦工作為最終的記賬者。因此，基于空間證明的挖礦過程就是礦工證明自己擁有足夠大的空間，以便高效存儲結構圖的過程。礦工擁有的空間越大，挖礦成功的概率也越大。挖礦的具體實現過程可參考文獻[6]。

接下來，介紹基于空間證明的區塊鏈結構，如圖2所示。

由圖2可知，每個區塊i都分為3個子塊：證明子塊iφ（hashiφ）、簽名子塊iσ（signatureiσ）和交易子塊iτ（transactioniτ）。其中，證明子塊又稱散列子塊，是對相關內容做散列運算后的結果。

1) 散列子塊iφ包含：當前區塊序號i，記賬者對前一區塊的散列子塊φi-1的簽名φζ，記賬者在競爭記賬權時給出的承諾證明以及空間證明

2) 簽名子塊iσ包含：當前區塊序號i，記賬者對當前區塊的交易子塊iτ的簽名τζ，記賬者對前一區塊的簽名子塊σi-1的簽名

3) 交易子塊iτ包含：當前區塊序號i，交易信息列表ctx。即

3 改進的門限環簽名方案

3.1 IT-TRS方案及安全性分析

首先，回顧一下 IT-TRS（TOSHIYUKI I,KEISUKE T- threshold ring signature）方案[9]。

假設系統中有n個用戶，其中n-t個用戶可代表所有用戶生成環簽名，其余t個用戶不參與簽名。令表示非簽名用戶，而表示非簽名用戶編號的集合。假設通過拆分，所有用戶被拆分為t+1個互不相交的子群，則至少有一個子群中的用戶都參與了簽名，稱這個子群為合法子群。如文獻[8]所述，為了確保環簽名的不可偽造，需要采用(n,t+1)-完備拆分系統。

setup算法：令l表示安全參數，完備拆分系統，其中，表示一次公平拆分，記表示一組用戶編號的集合。令表示所有n個用戶。對于每一個i=1,2,…,n，gi表示匿名的單向陷門映射。對于任意i和j，j中元素的個數，Q表示的最大值。令如果對于所有的都是簽名者，稱是合法的。如文獻[8]所述，對于所有的整數n和t，且t≤n，(n,t+1)-完備拆分系統一定是存在的，每個用戶Pi基于單向陷門映射gi進行簽名。

對于每個子群πij，定義單向陷門映射為

T-ring-sign算法：假設系統中至多有t個用戶不參與簽名。由于所有用戶被分為t+1個互不相交的子群，則每次拆分都存在一個合法子群，記為設簽名消息為m，H為輸出長度為Qlbit的hash函數。對每個，簽名者執行以下步驟。

步驟 2 對于k=j+1,…,t+1,1,2,…,j-1，隨機選擇其中

圖2 基于空間證明的區塊鏈結構

因此，消息m的最終簽名

T-ring-verify算法：對于簽名iσ，驗證者計算

通過分析，上述方案中的門限環簽名不滿足強不可偽造性。假設合法子群 πij按照上述算法生成消

息m的簽名σ，則非合法子群 πij+1可與合法子群中的某個用戶相勾結，生成消息m的另外一個合法簽名。不妨設非合法子群與合法子群中的用戶相勾結，攻擊過程如下。

把以上過程重復p次，生成最終的簽名

由驗證算法可知，上述簽名可以通過驗證。攻擊成功的原因在于隨機數的改變只影響的值，而對沒有影響，因此攻擊者只要知道的某個陷門，就可以偽造簽名通過驗證。

3.2 改進的TRS方案

針對上述攻擊方法，本文提出了改進的 TRS（I-TRS, improved threshold ring signature）方案，滿足門限環簽名的強不可偽造性及用戶的匿名性。

假設系統中有n個用戶，其中n-t個用戶可代表所有用戶生成環簽名，其余t個用戶不參與簽名。改進方案中的數學符號與原方案相同。

setup算法：同原方案。

T-ring-sign算法：假設系統中至多有t個用戶不參與簽名。由于所有用戶被分為t+1個互不相交的子群，則每次拆分都存在一個合法子群，記為設簽名消息為m，H為輸出長度為Qlbit的 hash函數。對每個 πi,i= 1 ,2,… ,p，簽名者執行以下步驟。

步驟 2 對于k=j+1,…,t+1,1,2,…,j-1，隨機選擇

因此，消息m的最終簽名

T-ring-verify算法：對于簽名iσ，驗證者計算

改進方案解決了原方案存在的問題，是一個安全的環簽名方案。

3.3 改進TRS方案安全性分析

本節對改進TRS方案進行分析，包括簽名的強不可偽造性及簽名者的匿名性。

1) 強不可偽造性

在隨機預言模型中，假設敵手最多可勾結(n-t-1)個非簽名者，在經過qH次散列詢問后，能以概率ε偽造(n-t,n)門限環簽名，則對于陷門單向映射知某個輸出y0，可構造算法以概率找到輸入x0，使

證明 本文需要在選擇消息攻擊下證明門限環簽名的強不可偽造性（SU-TRS-CMA）。游戲包括2個參與者：挑戰者和敵手。假設敵手在經過詢問后可偽造有效的門限環簽名，則挑戰者已知陷門單向映射的輸出y0，可構造算法找到對應輸入具體步驟如下。

setup 挑戰者為所有用戶生成公私鑰對，并將所有用戶公鑰PK1,… ,PKn發送給敵手。

階段1 敵手適應性地進行下列詢問。

散列詢問：敵手發送字符串給挑戰者，挑戰者隨機選擇Qlbit的隨機數v，并設定某2個字符串的散列值分別為v和v⊕y0，其余字符串選擇Qlbit的隨機數作為散列值，并返還給敵手。

私鑰詢問：敵手發送用戶公鑰給挑戰者，挑戰者返回對應私鑰給敵手。敵手至多可詢問(n-t-1)個用戶的私鑰。

簽名詢問：敵手發送消息m給挑戰者。挑戰者隨機選擇(n-t)個環成員私鑰根據T-ring-sign算法生成簽名σ，并返回給敵手。

挑戰階段 假設敵手能以概率ε偽造消息m*的環簽名且沒有出現在簽名詢問階段。

2) 匿名性

3) 效率分析

假設系統中有n個用戶，其中n-t個用戶可代表所有用戶生成環簽名。當t很小，即簽名人數很多時，所提改進方案是效率最高的，如表 1所示。為了公平起見，本文只比較傳統的門限環簽名方案。

表1 不同方案的門限環簽名效率比較

4 可刪除的區塊鏈

本節基于改進的門限環簽名方案，提出可刪除的區塊鏈結構，并做仿真實驗進行模擬實現。當區塊鏈數據過期時，只有絕大多數用戶同意，并生成有效的門限環簽名才能進行刪除，否則不能進行刪除。除刪除操作外，不能對區塊數據做其他更改。在刪除區塊數據時，不能影響其他區塊數據的使用和驗證。

4.1 數據刪除概述

假設某個區塊i+1的交易數據因為數據過期、廢棄等原因，不再具有鏈上存儲以供溯源的意義。繼續存儲該區塊的交易數據無疑是對存儲資源的浪費。在此情況下，網絡中的相關節點向網絡廣播“刪除區塊i+1交易數據”的請求信息，具體表示為：DelTx={number, reason}，其中，number=i+1為請求刪除的交易數據所在的區塊號，reason即為請求刪除的原因。其余所有合法節點在接收到DelTx后，會對該刪除操作的合理性進行考證，比如該區塊交易數據是否真的來自一個已經宣布倒閉的銀行等等?？甲C過后，合法節點需廣播自己關于DelTx的意見，記為 ReDelTx。ReDelTx=1，表示節點同意刪除請求；ReDelTx=0，表示不同意刪除請求。最終，每個節點均可統計整個網絡對該刪除信息的反饋，如果“同意”信息超過設定門限（本文設為全網節點的 75%），便認為該刪除請求合法，然后生成一條專屬的刪除消息m，其具體格式將在第 4.2節中介紹。

接下來，對該刪除消息持“同意”意見的節點將進行交易數據的刪除工作，并成為環簽名系統中的簽名節點，按照第3節中提出的改進門限環簽名方案，代表整個系統生成消息m的門限環簽名，作為對刪除消息m合法性的承諾。同時還將生成的環簽名存儲于交易數據原本所在的位置，并在全網進行廣播，以供所有節點對該刪除操作的合法性進行驗證。

所提方案是在公鏈模式下，基于PoSpace共識機制提出的區塊鏈數據刪除方案。在目前使用PoSpace共識機制的區塊鏈中，鏈上交易數據都是公開的，可供全網節點公開驗證，不能實現交易數據的隱私性。因此，方案面向的區塊數據都是公開可驗證的，刪除交易數據時對數據進行公開考證是合理的，刪除操作不會增加數據的隱私泄露風險。如果用戶對隱私性要求較高，可將數據存儲在能實現隱私保護的區塊鏈中，如 Zerocash[16]、Monero[17]等。

4.2 區塊鏈結構

假設第i+1個區塊數據可以刪除，經大多數用戶同意并生成門限環簽名，對數據進行刪除。可刪除的區塊鏈結構如圖3所示。

在第i+1個區塊中，包含3個子塊：證明子塊簽名子塊和門限環簽名子塊證明子塊和簽名子塊如第2.3節所述，這里只介紹門限環簽名子塊

區塊數據刪除后，由簽名節點廣播至全網。其余用戶首先驗證門限環簽名是否正確，然后將中對被刪除交易子塊τi+1的簽名τζ與簽名子塊σi+1的簽名τζ進行比較，若一致則接受刪除行為，否則不接受。

圖3 可刪除的區塊鏈結構

對比交易數據刪除前后的區塊信息可知，除交易數據被替換成相應環簽名外，當前區塊及其前后區塊中的其余信息都未發生任何變化，區塊鏈的結構未發生變動。可見，所提區塊鏈方案可以成功刪除區塊中廢棄的交易數據，釋放大量存儲空間，且不影響其他區塊數據的使用和驗證。

4.3 數據刪除安全性分析

本文通過閾值設定，在全網75%節點同意時，才可生成刪除消息m，并由同意刪除的節點生成m的門限環簽名，承諾數據刪除的合法性。門限環簽名本身具有的正確性、匿名性和強不可偽造性保證了該承諾的安全有效，并可供任意節點隨時進行驗證。其中，閾值比例75%的設定是綜合考慮“門限環簽名效率”“節省存儲空間”“刪除操作是否代表大多數節點的意見”這3點，并通過實驗測試得出的。一方面，閾值越高，越能代表系統中更多節點的意見，讓刪除操作更加安全。但另一方面，閾值過高將導致刪除區塊耗時太長，影響刪除操作的效率，降低數據刪除的應用價值。因此權衡兩者，將閾值比例設定為75%，可在保障安全性的前提下也保證方案效率。

同時，由第4.2節的分析可知，整個交易數據的刪除過程并不會破環原有區塊鏈的結構。區塊數據刪除后，門限環簽名被存儲于原有數據所在位置。當前區塊的證明子塊和簽名子塊信息并未發生改變，因此該區塊仍然與前后區塊保持合法的鏈接關系。交易數據刪除后，區塊中簽名子塊關于交易數據的簽名與門限環簽名中包含的交易數據簽名是一致的，其他網絡節點將通過驗證該一致性以確定區塊鏈接的合法性。

綜上，可刪除的區塊鏈具有以下特點。

1) 只有大多數用戶同意才能對數據進行刪除，避免惡意刪除。由門限環簽名的強不可偽造性可知，當區塊數據過期或失效時，只有超過門限個數的用戶才能生成有效的環簽名，否則不能生成簽名并通過驗證。因此，本文可以設定合適的門限值，確保絕大多數用戶同意才能刪除區塊數據，避免惡意用戶的刪除。

2) 除刪除操作外，不能對區塊數據做其他更改，例如插入數據、刪除部分數據等。在基于空間證明的區塊鏈中，每個區塊中都包括證明子塊和簽名子塊，證明子塊可以認證記賬者的身份，簽名子塊是記賬者對交易數據的認證。如果惡意用戶更改區塊數據，例如插入數據、刪除部分數據等，則需要重新生成簽名子塊，但是記賬者的簽名是不能偽造的，因此數據不會更改成功。

3) 第i+1個區塊數據的刪除并不影響其余區塊的鏈接。原因如下：交易數據的刪除只是把原有區塊中的交易子塊τi+1變成了門限環簽名子塊并不改變證明子塊φi+1和簽名子塊σi+1，因此它們與前后區塊的鏈接關系不受影響。

4.4 實驗仿真

本節分別對區塊的生成和刪除進行了仿真實現。挖礦節點使用的實驗設備配置為2.4 GHz Intel i5 處理器，4 GB內存，并在Visual Studio Ultimate開發環境下，使用C++語言編程實現。在生成區塊鏈時，散列函數和記賬節點簽名分別使用 SHA（secure hash algorithm）-256和DSA（digital signature algorithm）-512實現。在刪除區塊鏈時，使用第3節提出的門限環簽名，其中的單向陷門函數使用RSA-1024實現。

4.4.1 基于空間證明的記賬權競爭

如第2.3節所述，在PoSpace共識機制下，礦工們基于空間證明對記賬權展開競爭，首先模擬空間競爭過程。

假設系統生成如圖4所示的有向圖，共包含20個頂點。

圖4 系統有向圖

設有5位礦工，分別記為A、B、C、D、E，每位礦工都可根據自己的公鑰，計算該有向圖中每個頂點的標簽值（使用SHA-256實現），生成結構固定但頂點標簽值與身份一一對應的專屬有向圖。由于空間限制，部分礦工無法一次性存儲全部頂點，只能完成對部分頂點的存儲，其他非存儲頂點則需要依據有向圖結構和已存儲的頂點計算得到。當系統隨機要求礦工返回相關頂點標簽值時，本地空間大、存儲頂點多的礦工總是擁有較大的優勢，以最快的速度響應系統，從而贏得記賬權，這樣便形成了基于空間的記賬權競爭。其中，5位礦工的公鑰及其對圖4有向圖的存儲情況如下。

每個礦工都作為一個空間證明者P向系統扮演的驗證者V證明自己擁有足夠的空間存儲全圖，V多次發布驗證頂點標號集合，記為向P發起挑戰，要求P返回Ch中每個標號對應的頂點標簽值及其母頂點標簽值，以驗證P是否有足夠大的空間存儲全圖，P返回相應數值響應V發起的挑戰。表2記錄了上述5位礦工在不同挑戰Ch下的空間證明時間。

表2 5名礦工空間證明時間比較

由表2可知，在不同的挑戰Ch下，P的空間越大，對V的挑戰的響應就越快，越容易獲得記賬權，這便是基于空間證明的PoSpace共識機制下區塊記賬權競爭的基本過程。

4.4.2 新區塊的生成

當節點獲得記賬權后，依次生成新區塊的證明子塊（hash子塊）、簽名子塊和交易子塊。原始區塊33～35的數據如圖5所示，本文以區塊35為例進行說明。

圖5 原始區塊33～35的數據

4.4.3 區塊的刪除

假設當前區塊鏈中，編號33～35的區塊信息如圖5所示。其中，區塊34中的交易數據已過期，為了節約存儲空間，區塊鏈中的各個節點于 2018年7月3日達成共識，對該區塊執行刪除操作。首先，由區塊 34刪除時間“20180703”、刪除原因“overdue”和記賬者對區塊 34中交易數據的簽名“57B55F59A500212FDEBC6F92BC8B14F46444BF DE”，生成刪除行為對應的消息m= “3420180703 overdue57B55F59A500212FDEBC6F92BC8B14F46 444BFDE”，并按照第3.2節中的改進算法，對消息m生成門限環簽名，記錄在原始交易子塊中。

假設系統中總用戶數n=8，環簽名門限值為6，則非簽名用戶數t=2。設簽名用戶集合記為非簽名用戶集合記為設某次拆分方法為：

將上述過程重復p次，得到最終的門限環簽名其中，

當區塊 34中的交易數據刪除后，區塊 33～35的數據如圖7所示。

刪除操作完成并廣播后，網絡中所有節點均能對門限環簽名進行驗證，并將消息m中記賬者對區塊 34中交易數據的簽名與簽名子塊中的簽名進行對比驗證，如果驗證通過，則認可數據刪除行為的合法性。

最后，本文對生成和刪除區塊的效率進行了分析。如第4.3節所述，本文需要選定合適的閾值，以權衡“門限環簽名效率”“節省用戶存儲空間”以及“刪除操作是否代表大多數節點的意見”這3點，使其在保障安全性的前提下也保證方案效率，其中，效率分析包括計算時間與存儲空間比較，即刪除操作用時越短，環簽名所占空間越小，方案效率越高。在以下實驗中，本文選取不同閾值，從“刪除區塊時間”和“刪除后節省空間占比”這2個方面進行了比較。

圖6 求解程序運行

圖7 區塊34交易數據刪除后區塊33～35的數據

如第3.1節所述，對于所有的整數n和t，且t＜n，(n,t+1)-完備拆分系統一定是存在的。同時，為了使刪除操作代表系統多數節點意見以保證安全，簽名節點應在半數以上。以上實驗中n=8，因此t={1,2,3}，合法閾值集合n-t={5,6,7}。表3和表4分別比較了不同閾值下區塊刪除的平均時間和刪除前后的存儲空間及節省空間占比。

表3 不同閾值下區塊刪除的平均時間比較

表4 不同閾值下交易刪除前后的存儲空間及節省空間占比

由表3可知，區塊刪除的平均時間隨著閾值的增大而增加，三者之間兩兩相差大約0.5 s，約占區塊生成平均時間的對計算效率影響明顯。由表4可知，當閾值為6和7時，交易刪除后節省空間的效果顯著，均大于80%；而閾值為5時，交易刪除后節省空間大約60%。因此，當閾值為7時，雖然刪除后節省空間的效果最優，但刪除區塊耗時較長；當閾值為5時，雖然刪除區塊耗時較短，但節省空間效果不太理想，且參與刪除的節點相對較少，降低了方案的安全性。綜合考慮區塊刪除的安全性和效率，本文選擇閾值為6，即占比是同時保證方案安全性和效率的最佳閾值。

如表5所示，當閾值比例為75%時，生成一個區塊平均耗時0.965 s，刪除交易數據并生成門限環簽名平均耗時3.028 s。

表5 5個區塊在閾值比例為75%時的生成區塊和刪除區塊耗時

5 結束語

本文首先提出了改進的門限環簽名方案，在隨機預言模型中可證安全，同時滿足簽名的強不可偽造性與簽名者的匿名性。然后，基于空間證明的區塊鏈結構，使用門限環簽名方案提出了可刪除的區塊鏈。當某個區塊數據過期失去存儲價值時，經大多數節點同意后可有效刪除該區塊，大大節省了用戶的存儲空間，并保持區塊鏈的總體結構不變。實驗結果表明，所提區塊鏈方案生成和刪除區塊的效率都很高，且不影響其他區塊的存儲和使用。