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

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

1 引言

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

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

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

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

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

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

2 基礎知識

2.1 門限環(huán)簽名

環(huán)簽名[7]主要包括以下算法。

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

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

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

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

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

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

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

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

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

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

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

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

2.2 環(huán)簽名安全模型

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

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

setup 挑戰(zhàn)者執(zhí)行setup算法獲得所有環(huán)成員公鑰PK1,…, P Kn和私鑰SK1,…,S Kn，并發(fā)送公鑰給敵手。

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

散列詢問：敵手發(fā)送字符串給挑戰(zhàn)者，挑戰(zhàn)者選擇隨機數(shù)作為對應的散列值，并返還給敵手。

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

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

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

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

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

2.3 基于空間證明的區(qū)塊鏈

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

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

圖1 有向無環(huán)結構圖

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

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

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

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

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

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

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

3 改進的門限環(huán)簽名方案

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

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

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

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

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

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

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

圖2 基于空間證明的區(qū)塊鏈結構

因此，消息m的最終簽名

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

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

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

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

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

3.2 改進的TRS方案

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

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

setup算法：同原方案。

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

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

因此，消息m的最終簽名

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

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

3.3 改進TRS方案安全性分析

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

1) 強不可偽造性

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

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

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

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

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

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

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

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

2) 匿名性

3) 效率分析

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

表1 不同方案的門限環(huán)簽名效率比較

4 可刪除的區(qū)塊鏈

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

4.1 數(shù)據(jù)刪除概述

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

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

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

4.2 區(qū)塊鏈結構

假設第i+1個區(qū)塊數(shù)據(jù)可以刪除，經(jīng)大多數(shù)用戶同意并生成門限環(huán)簽名，對數(shù)據(jù)進行刪除?？蓜h除的區(qū)塊鏈結構如圖3所示。

在第i+1個區(qū)塊中，包含3個子塊：證明子塊簽名子塊和門限環(huán)簽名子塊證明子塊和簽名子塊如第2.3節(jié)所述，這里只介紹門限環(huán)簽名子塊

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

圖3 可刪除的區(qū)塊鏈結構

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

4.3 數(shù)據(jù)刪除安全性分析

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

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

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

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

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

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

4.4 實驗仿真

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

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

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

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

圖4 系統(tǒng)有向圖

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

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

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

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

4.4.2 新區(qū)塊的生成

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

圖5 原始區(qū)塊33～35的數(shù)據(jù)

4.4.3 區(qū)塊的刪除

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

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

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

當區(qū)塊 34中的交易數(shù)據(jù)刪除后，區(qū)塊 33～35的數(shù)據(jù)如圖7所示。

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

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

圖6 求解程序運行

圖7 區(qū)塊34交易數(shù)據(jù)刪除后區(qū)塊33～35的數(shù)據(jù)

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

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

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

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

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

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

5 結束語

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