王昱博 馬春光

摘 ? 要：在區(qū)塊鏈系統(tǒng)中，空間量證明被認為是比工作量證明更綠色、更經(jīng)濟的選擇。與工作量證明不同，空間量證明將存儲作為投入的資源，以此有效地避免資源的集中化，提高不同礦工之間挖礦的公平性。文章將空間量證明作為主要論述對象，列舉了區(qū)塊鏈中現(xiàn)有的物理資源消耗型證明技術(shù)，對其中以存儲量作為消耗資源的證明技術(shù)進行展開，闡述了空間量證明的當前研究現(xiàn)狀，對將基于空間量證明的共識算法與區(qū)塊鏈結(jié)合的難點進行分析并總結(jié)現(xiàn)有的解決方法。

關(guān)鍵詞：區(qū)塊鏈;空間量證明;共識算法

中圖分類號： TP301.6 ? ? ? ? ?文獻標識碼：A

Abstract： In the blockchain system， proof of space is considered a greener and more economical choice than proof of work. Different from proof of work， the proof of space takes the storage as the consuming resource， so as to effectively avoid the concentration of resources and improve the fairness of mining among different miners. Summary takes proof of space as the main object， listing the existing proof technology of physical resource consumption in blockchain， detailedly discussing the proof technologies which take storage as consuming resource， generalizing current research status of proof of space， analyzing the difficulty of applying the consensus algorithm based on proof of space in blockchain and summarizing the current solution.

Key words： blockchain; proof of space; consensus algorithm

1 引言

比特幣[1]作為第一個以區(qū)塊鏈技術(shù)實現(xiàn)的應(yīng)用，一經(jīng)問世就吸引了眾多研究人員的目光，這一現(xiàn)象也使得區(qū)塊鏈相關(guān)的技術(shù)得到了飛速發(fā)展。盡管最初區(qū)塊鏈的應(yīng)用僅限于電子貨幣[2]，但隨著研究人員的不斷嘗試與創(chuàng)新，區(qū)塊鏈技術(shù)已經(jīng)開始逐漸融入各行各業(yè)，如醫(yī)療[3]、智能家居[4]、衛(wèi)星通信[5]等。共識算法作為區(qū)塊鏈的核心技術(shù)之一，其保證了區(qū)塊鏈系統(tǒng)的分布式一致性，對推動區(qū)塊鏈的發(fā)展有著重大作用，也自然而然的被廣大研究人員所關(guān)注。

區(qū)塊鏈是通過采用對等（Peer-to-Peer，P2P）網(wǎng)絡(luò)組織所有節(jié)點[6]，并采用激勵機制使得每個節(jié)點自愿參與系統(tǒng)維護的過程，而共識算法就是為了實現(xiàn)在這樣一個分布式系統(tǒng)中保證不同節(jié)點數(shù)據(jù)存儲的一致性。但因為P2P網(wǎng)絡(luò)中節(jié)點間無法相互約束，且激勵機制使得區(qū)塊鏈系統(tǒng)中有利可圖，這必然會出現(xiàn)一些節(jié)點希望通過不誠實行為，獲得比誠實節(jié)點更高的利益。為了防止?jié)撛诘牟徽\實行為的出現(xiàn)，系統(tǒng)必須通過恰當?shù)墓沧R算法使得不誠實的行為被大多數(shù)用戶所認可。

對于可自由進入的公鏈系統(tǒng)而言，缺乏身份驗證是一個主要的問題。敵手可能通過制造出許多虛假身份使得自己成為系統(tǒng)中的“大多數(shù)”，從而危及系統(tǒng)的安全性，這種攻擊被稱為“女巫攻擊（Witch Attack）”。共識算法要求每個參與的節(jié)點必須消耗一定資源來生成證明，從而證明自己的身份，由于每個節(jié)點擁有的資源有限，故能生成的證明也是有限的，通過這種方式來提高偽造身份（即，生成證明的過程）所需要的代價，從而一定程度上可以抵抗“女巫攻擊”。

投入資源一般分為物理資源和虛擬資源，其中虛擬資源是指現(xiàn)實不存在，而僅存在于區(qū)塊鏈系統(tǒng)中的資源，例如權(quán)益證明（Proof of Stake，PoStake）[8]中的幣齡（Coin Age）（即幣持有的天數(shù)X幣的數(shù)量）、授權(quán)股份證明[9]（Delegated Proof of Stake，DPoStake）中的股權(quán)（與持有資產(chǎn)的數(shù)量呈線性關(guān)系）等。而物理資源主要是指硬件資源，例如計算受限（Computation bound）工作量證明（Proof of work，PoW）中的計算能力、內(nèi)存依賴（Memory dependency）PoW的內(nèi)存相關(guān)資源。而內(nèi)存依賴型函數(shù)一般是被分為兩類—內(nèi)存受限函數(shù)（Memory Bound Functions，MBF）和內(nèi)存難解函數(shù)（Memory Hard Functions，MHF），其中MBF依賴于訪存時間，而MHF依賴于內(nèi)存的消耗?？臻g量證明（Proof of Space，PoSpace）使用的磁盤空間也屬于物理資源的一種，本文對四種物理資源進行介紹。

計算受限的PoW：計算受限算法是通過一段時間內(nèi)CPU計算操作有限來抵抗女巫攻擊。這種方法最早由Dwork和Naor[10]提出，用于阻止垃圾郵件泛濫。在發(fā)送電子郵件之前，驗證者必須執(zhí)行一些計算工作并生成一個可以有效驗證的證明，以使得發(fā)送大量垃圾郵件需要付出一些時間上的代價，使得任何人不能無節(jié)制的發(fā)送垃圾郵件。

內(nèi)存受限的PoW：基于平衡設(shè)備差異和堅持本地計算這兩個要求，Abadi等人[11]和Dwork等人[12，13]相繼提出了內(nèi)存受限函數(shù)。內(nèi)存受限函數(shù)主要是通過訪存時間來決定的，其復(fù)雜性度量是內(nèi)存訪問的次數(shù)，而不考慮實際使用的內(nèi)存容量。內(nèi)存受限的PoW的特點在于，它需要不斷地通過訪存和少量計算對內(nèi)存進行填充，此時訪存時間成為了影響挖礦速度最主要的因素。因此，為了消除系統(tǒng)中高速緩沖存儲器（Cache）對訪存時間的優(yōu)化，必須強制對內(nèi)存填充的數(shù)據(jù)塊至少大于Cache的容量。

內(nèi)存難解的PoW：內(nèi)存難解函數(shù)的主要思想是，對于給定的操作次數(shù)，設(shè)備需要盡可能多地消耗內(nèi)存。Percival[14]給出了內(nèi)存難解函數(shù)的概念并設(shè)計了滿足條件的Scrypt算法。由于Scrypt算法對內(nèi)存有一定的需求，故可以一定程度上抵抗ASIC帶來的不公平性，但現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）仍舊可以在以Scrypt算法為基礎(chǔ)的挖礦活動獲得很大的優(yōu)勢。

PoSpace：PoSpace[15，16]是以磁盤容量作為投入資源來獲取記賬權(quán)的資源消耗性證明。與基于MHF的PoW類似，PoSpace也需要投入大量的存儲空間來解決某個問題[18]。不同的是，PoSpace需要先在本地生成一個很大的隨機文件，然后讀出每次隨機挑戰(zhàn)所對應(yīng)的數(shù)據(jù)作為空間量證明，以證明自己確實投入了與隨機文件相同大小的空間量。此外，MHF運算一次只需要幾分鐘且用完之后就會丟棄，而PoSpace生成隨機文件往往需要幾個小時，且生成的隨機文件需要長期保存。

比特幣是通過工作量證明來抵抗“女巫攻擊”，傳統(tǒng)基于哈希的PoW有一些缺點，最明顯的是不能有效地防止使用專用集成電路（Application Specific Integrated Circuit ，ASIC）。ASIC的哈希集成單元常常會使得在CPU上提供100倍加速的同時導(dǎo)致10000倍能源消耗，這使得裝備了ASIC的對手相對于使用普通設(shè)備的用戶具有巨大的優(yōu)勢，但與此同時也帶來了巨大的能源損耗問題[7]?？臻g量證明一直以來被視為是工作量證明的一種替代方案。由于PoSpace是以磁盤空間作為投入資源，這使得個人很難將大量的資源集中化，這將很好的解決專用設(shè)備所帶來的能源浪費和不公平性問題。

本文以空間量證明技術(shù)為核心，從不同的方面討論空間量證明相關(guān)研究及其發(fā)展。文章結(jié)構(gòu)安排為：首先，討論包含空間量證明技術(shù)在內(nèi)的存儲證明技術(shù)，羅列各類存儲技術(shù)發(fā)展中的重要成果，并展示這些成果對空間量證明技術(shù)的發(fā)展的促進作用;然后，對現(xiàn)有的空間量證明技術(shù)類型劃分，并闡述其安全性的發(fā)展;接著，分析將空間量證明技術(shù)與區(qū)塊鏈結(jié)合存在的難點，并總結(jié)現(xiàn)有的解決方案。最后對空間量證明技術(shù)的發(fā)展和研究趨勢進行總結(jié)。

2 存儲證明技術(shù)

空間量證明技術(shù)作為一種存儲證明技術(shù)，其發(fā)展與其他存儲證明技術(shù)之間有著密不可分的聯(lián)系。從這些技術(shù)中可以看到空間量證明技術(shù)的發(fā)展過程，以及未來的發(fā)展趨勢。本節(jié)致力于對安全擦除證明、可證明數(shù)據(jù)持有、可恢復(fù)證明、空間量證明和復(fù)制證明進行區(qū)分，將對一些基本成果進行論述。其各種技術(shù)之間的關(guān)系如圖1所示。

2.1安全擦除證明

對于某一個存儲量有限的設(shè)備，如果懷疑設(shè)備中可能存在惡意程序或希望刪除設(shè)備中的機密文件，研究人員可以通過安全擦除證明（Proof of Secure Erasure，PoSE）來實現(xiàn)。

PoSE是由驗證者V和證明者P參與的雙方協(xié)議，協(xié)議過程分為兩個階段：第一階段，V向P發(fā)送一個與P存儲器容量相等的隨機文件;第二階段，P保存V的隨機文件，并對文件進行適當計算，將結(jié)果返回給V，以證明自己確實保存了完整的隨機文件。

2010年，Perito等人[19]為了實現(xiàn)設(shè)備認證和代碼更新首次引入了PoSE的概念。Perito等人希望通過哈希函數(shù)對隨機文件進行處理，并要求使用隨機文件的最后k位作為密鑰。由于P在隨機文件的最后才能獲得密鑰并對隨機文件進行處理，這使得在隨機文件傳送完成之前，P需要前面的數(shù)據(jù)完整保存。

2011年，Dziembowski等人[20]通過基于箭頭圖的鋪石游戲（Pebbling Game），設(shè)計了新的原語“不可計算哈希函數(shù)（Uncomputable Hash Functions）”，并希望通過這種函數(shù)設(shè)計PoSE第二階段的計算過程。該方法極大的減小了通信的復(fù)雜度，但很大程度地增加了驗證者的驗證負擔。

2014年，Karvelas等人[21]分別通過基于超集中蝴蝶圖簇（Butter?y Superconcentrator Family of Graphs）[22]的鋪石游戲和函數(shù)求逆的方法，構(gòu)造了兩個新的PoSE方案。其中，與基于鋪石游戲的方案Dziembowski等人的方案思想相同，但在效率上得到了一定的改善。而在基于函數(shù)求逆的方案中，驗證者只需要一次正向計算來判斷證明者給出的值是否正確，從而完全消除了驗證者的驗證壓力。但相較于基于鋪石游戲的方案，基于函數(shù)求逆的方法并沒有很好的緊湊性。

2.2 可證明數(shù)據(jù)持有

為了解決分布式存儲中數(shù)據(jù)是否被惡意篡改或丟棄的問題，人們提出了可證數(shù)據(jù)持有（Provable Data Precession，PDP）概念，以實現(xiàn)遠程數(shù)據(jù)完整性檢查。對于遠程檢查數(shù)據(jù)完整性的實現(xiàn)方法，一種自然的想法是從分布式數(shù)據(jù)庫中下載數(shù)據(jù)，并在本地進行比對。但每次檢查都需要網(wǎng)絡(luò)將整個文件進行傳輸，增加了網(wǎng)絡(luò)負荷。因此，如何在不下載全部數(shù)據(jù)的情況下檢查遠程數(shù)據(jù)的完整性，成為了一個關(guān)鍵的問題。

2003年，Deswarte等人[23]通過引入Diffie-Hellman協(xié)議[24]設(shè)計實現(xiàn)了遠程完整性檢查。此外，他們還設(shè)計了一個可實現(xiàn)遠程完整性檢查的函數(shù)結(jié)構(gòu)。遺憾的是，Deswarte等人并沒有給出這樣一個具體方案。2006年，Gazzoni等人[25]通過引入RSA哈希同態(tài)函數(shù)，設(shè)計了Deswarte等人提出的函數(shù)結(jié)構(gòu)，并由此設(shè)計了證明數(shù)據(jù)持有協(xié)議。

2007年，Giuseppe等人[26]為這一類遠程數(shù)據(jù)完整性檢查技術(shù)命名為“可證明數(shù)據(jù)持有”，并給出了完整定義。他們的方案將大文件分塊并使用同態(tài)可驗證標簽技術(shù)對其進行標記，采取概率抽樣驗證方法避免對整個待驗證文件進行計算，在保證安全性的同時提高了協(xié)議交互的效率。

同樣在2007年，Juels等人[27]提出了“可恢復(fù)證明（Proof of retrievability，PoR）”方案，解決了遠程數(shù)據(jù)完整性檢查問題。他們將一些隨機數(shù)據(jù)填充到文件中，并對文件進行糾錯編碼。如果遠程數(shù)據(jù)被大范圍改動，則可以通過隨機數(shù)據(jù)的完整性檢測出來;而如果只是文件中少數(shù)位發(fā)生變化，則可以通過糾錯編碼進行糾正。

為了實現(xiàn)遠程動態(tài)數(shù)據(jù)完整性檢查，Chris等人[28]提出了動態(tài)可證明數(shù)據(jù)持有（Dynamic Provable Data Precession，DPDP）方案。該方案通過基于秩的認證跳躍表，在實現(xiàn)原本PDP方案的基礎(chǔ)上增加了遠程更新和更新驗證的過程，使得用戶可以遠程對數(shù)據(jù)進行增、刪、改操作，并可對更新后的結(jié)果進行遠程驗證。

2.3 空間量證明

空間量證明是證明者P與驗證者V之間的協(xié)議，協(xié)議要求P使V相信自己確實投入了一定量的磁盤資源。協(xié)議過程需要P根據(jù)V的要求構(gòu)造一個相當大的隨機文件，然后V再檢查該隨機文件的完整性以確保P確實生成并保存了該隨機文件。與PDP/PoR等問題中涉及的數(shù)據(jù)完整性檢查不同，驗證者并不知道完整的數(shù)據(jù)內(nèi)容，因而無法生成用于輔助驗證的數(shù)據(jù)。為解決具體設(shè)計中存在的問題，Giuseppe等人與Dziembowski等人分別獨立的構(gòu)造了不同的PoSpace方案。

2014年，Giuseppe等人[16]基于鋪石游戲和隨機神諭假設(shè)，實現(xiàn)了單段PoSpace協(xié)議，其中協(xié)議包含兩輪交互。該方案與Dziembowski等人提出的PoSE的方案[20]類似（事實上，Giuseppe等人的PoSpace方案也僅實現(xiàn)了PoSE的功能），不同的是：（1）Giuseppe等人利用鋪石圖自身結(jié)構(gòu)的性質(zhì)和Merkle樹，大大降低了驗證者的計算復(fù)雜度;（2）用堆式超集中蝶形圖（Stack of Butter?y Superconcentrators）結(jié)合基本下限證明[29]，提高了方案的緊湊性。Giuseppe等人指出PoSpace有潛力作為PoW的替代方案，但遺憾的是，他們的方案每次執(zhí)行都需要大量的時間構(gòu)造隨機文件，效率低下明顯的限制了其應(yīng)用。

2015年，基于同樣的思想，Dziembowski等人[15]設(shè)計了兩段PoSpace協(xié)議。該PoSpace協(xié)議具體可分為初始化階段和執(zhí)行階段。初始化階段與Giuseppe等人的單段PoSpace協(xié)議基本相同，需要完成隨機文件和Merkle樹的計算并檢查文件的一致性。而在執(zhí)行過程中，V同樣需要生成隨機挑戰(zhàn)并發(fā)送給P，P根據(jù)挑戰(zhàn)對應(yīng)的標簽返回對應(yīng)的Merkle路徑作為空間量證明。兩段的PoSpace一定程度上更好的迎合了區(qū)塊鏈系統(tǒng)的要求，但是兩段協(xié)議使得方案的緊湊性明顯下降。

基于對PoSpace中時空權(quán)衡問題的研究，2016年Ren等人[30]提出一種堆式二分擴展圖作為鋪石游戲中構(gòu)造隨機文件的結(jié)構(gòu)。他們的方案表明，可以通過加節(jié)點之間的邊數(shù)提高緊湊性，但這增加了圖的復(fù)雜程度，降低了實用性。

2017年， Abusalah等人[31]舍棄了鋪石游戲，而選擇隨機函數(shù)求逆作為PoSpace協(xié)議的底層問題，并基于Hellman的時空權(quán)衡攻擊[32，33]做出了詳細的討論。基于隨機函數(shù)求逆的PoSpace由于沒有隨機文件承諾過程且證明尺寸較小等特點，被認為比基于鋪石游戲的PoSpace更適用于區(qū)塊鏈系統(tǒng)中，但該方案在緊湊性上有很大的不足。

2.4 復(fù)制證明

假設(shè)驗證者（用戶）V希望將兩段相同的數(shù)據(jù)D，D'存儲至證明者（遠程服務(wù)器）P中，則P可能僅存儲D，每次進行數(shù)據(jù)完整性檢查時快速生成D'，并根據(jù)PDP/PoR協(xié)議正確響應(yīng)V的挑戰(zhàn)。該問題主要是由于PDP/PoR方案無法解決遠程數(shù)據(jù)備份存儲問題，以及PDP/PoR方案沒有公開可驗證的性質(zhì)。

2017年，Benet等人[34]提出了復(fù)制證明（Proof of Replicability，PoRep）作為解決方案。PoRep的主要思想是，通過編碼生成與源數(shù)據(jù)內(nèi)容不同但大小相同的副本并存儲，并通過遠程完整性檢查來確保P確實存儲了數(shù)據(jù)及其副本。同時，PoRep使用了PoSpace的兩段結(jié)構(gòu)解決可公開驗證的問題。此外，他們的方案使用緩慢的偽隨機置換（Pseudo-random permutation）函數(shù)計算副本，使得P不能快速通過原數(shù)據(jù)得到副本。

2018年，Alwen、Blocki和Pietrzak[36]研究出了一種具有更強性質(zhì)的深度健壯圖（Depth Robust Graphs，DRG）。同年，Pietrzak[35]提出使用該圖的構(gòu)造實現(xiàn)PoRep中的編碼過程。這種編碼本質(zhì)上是利用鋪石游戲構(gòu)造出隨機文件，再通過這些隨機文件對存儲文件進行編碼。如此設(shè)計的編碼過程確實減緩了計算副本的過程，但對副本進行恢復(fù)時也需要同樣的過程，這使得效率十分低下。

同樣在2018年，F(xiàn)isch將深度健壯圖與可驗證延遲編碼（Verifiable Delay Encode，VDE）相結(jié)合，構(gòu)造了新的PoRep方案[37]。該方案使用了Bucket抽樣算法[40]構(gòu)造深度健壯圖，使其具有很強的實用性。不同于Pietrzak的方案中僅保留部分節(jié)點標簽，F(xiàn)isch將整個圖進行保存，再配合VDE快速解碼的特性，明顯提高了將副本恢復(fù)為原數(shù)據(jù)的效率。

2019年，F(xiàn)isch基于PoRep方案的緊湊性考慮，基于對深度健壯圖和堆式擴展二分圖的研究[39]，設(shè)計了堆式深度健壯圖并將其應(yīng)用于PoRep協(xié)議設(shè)計中。其思想類似Ren等人[30]的分層結(jié)構(gòu)，不同的是，每層中的節(jié)點形成一個深度健壯圖。隨著圖的層數(shù)不斷增加，理論上該方案的緊湊性可以也會無限提高，且深度健壯圖自身的特性使得方案可以有效抵抗并行攻擊。

3 空間量證明分類

針對當前對于空間量證明技術(shù)的研究，研究人員可以將其視為證明者P和驗證者V之間的一個兩段協(xié)議。為了討論空間量證明協(xié)議的不同模型，本文介紹了Dziembowski等人給出的協(xié)議交互形式。整個空間量證明協(xié)議可以被劃分為初始化和執(zhí)行兩個階段，但由于不同的PoSpace方案之間使用的構(gòu)造技術(shù)不同，從而使得每個階段的交互目的存在一些差異。當前對PoSpace協(xié)議的研究主要可以分為兩類：基于鋪石游戲的PoSpace協(xié)議，基于函數(shù)求逆的PoSpace協(xié)議。

3.1 基于鋪石游戲的PoSpace協(xié)議

3.1.1 鋪石游戲與標簽問題

鋪石游戲是一種基于有向無環(huán)圖（DAG）的分析時空復(fù)雜的技術(shù)。在鋪石游戲中，鋪石者需要用到黑色石頭和白色石頭，游戲要求鋪石者根據(jù)鋪石規(guī)則將石頭放在DAG的頂點上。將有向無環(huán)圖中的所有匯點（即沒有后繼的頂點）記為挑戰(zhàn)集C，鋪石者需要通過拓撲排序用石頭鋪滿挑戰(zhàn)集，方可獲得游戲勝利。對于白色石頭而言，有三條鋪石規(guī)則。

（1）對于某一頂點，如果其所有前驅(qū)頂點上都有石頭（白色或黑色），則可以將石頭放在該頂點。

（2）對于某一頂點，如果它是源點（即沒有前驅(qū)的節(jié)點），則可以將石頭放在該頂點。

（3）每次鋪石者只能將一塊白色石頭放在圖上，但可以移除任意多個圖上的白色石頭。

基于鋪石游戲的時空復(fù)雜度分析，將放置一塊白色石頭作為一次關(guān)鍵計算，將某一時間圖上石頭的個數(shù)記作當前消耗的空間量，鋪石者總希望通過最少的計算和空間量完成游戲。與白色石頭不同的是，黑色石頭可以任意被放在圖上。毫無疑問，可以用個黑色石頭鋪滿挑戰(zhàn)集，如此一來鋪石者不需要計算步驟便可以獲得游戲勝利。而鋪石游戲中的時空權(quán)衡問題需要研究的是，是否存在使用個黑色石頭的策略，使得通過T次鋪石和同時最多個白色石頭來獲得游戲勝利。如果的值遠小于且T的值又不太大，則這將是個很好的時空權(quán)衡策略，來實現(xiàn)用少量的時間換取空間。

在PoSpace協(xié)議中，鋪石游戲是通過圖標簽問題來實現(xiàn)的。取圖為DAG，其中為圖中邊的集合，為頂點的集合且。在圖標簽問題中，每一個頂點都對應(yīng)與一個標簽值，通過存儲來模擬在頂點上鋪石，通過刪除來模擬將上的石頭移除。此外，引入隨機神諭來計算圖上頂點的標簽值，計算為：

其中，是表示鋪石者身份的標識符，是前驅(qū)節(jié)點的索引。由公式（1）可知，對于非源點頂點，必須要計算其所有前驅(qū)的標簽值，才能獲得自己的標簽值。由此，實現(xiàn)了模擬DAG中的拓撲序列。

3.1.2 基于鋪石游戲的PoSpace協(xié)議結(jié)構(gòu)

基于鋪石游戲的PoSpace協(xié)議生成隨機文件的過程，實際上是一個計算DAG頂點標簽的過程，其隨機文件的內(nèi)容由DAG中頂點標簽構(gòu)成。在初始化階段，證明者P會根據(jù)系統(tǒng)參數(shù)抽取一個DAG圖，并將公鑰作為自己的標識符，根據(jù)拓撲順序計算并保存圖G上對應(yīng)挑戰(zhàn)集頂點的標簽。為了證明隨機文件的完整性，證明者P將所有存儲的挑戰(zhàn)集頂點的標簽值作為葉子結(jié)點，構(gòu)建完整的Merkle樹，并將Merkle樹的根節(jié)點作為隨機文件的承諾值發(fā)送給驗證者V。隨后V會通過一個“挑戰(zhàn)-響應(yīng)”過程，完成對隨機文件完整性的檢查。

在初始化的“挑戰(zhàn)-響應(yīng)”過程中，V隨機抽取圖上若干個頂點，將其作為挑戰(zhàn)發(fā)送給證明者P。P的響應(yīng)內(nèi)容分為兩部分：1）挑戰(zhàn)節(jié)點的前驅(qū)節(jié)點的標簽值（用于驗證隨機文件生成的正確性）;2）挑戰(zhàn)節(jié)點及其前驅(qū)節(jié)點對應(yīng)的Merkle路徑（用于驗證與承諾的一致性）。由于驗證需要用到挑戰(zhàn)節(jié)點前驅(qū)的標簽值，而證明者P僅存儲挑戰(zhàn)集中的頂點標簽，這意味此次驗證過程需要重復(fù)一遍隨機文件構(gòu)造過程。

根據(jù)兩段空間量協(xié)議的設(shè)計思想，執(zhí)行階段是一個需要反復(fù)運行的過程，因此執(zhí)行階段要比初始化階段簡單得多。執(zhí)行階段也是一個“挑戰(zhàn)-響應(yīng)”的過程，不同的是，V只能從挑戰(zhàn)集中隨機抽取頂點作為挑戰(zhàn)，而P的響應(yīng)也只是挑戰(zhàn)節(jié)點對應(yīng)的Merkle路徑。具體協(xié)議為：

（1）初始化階段

1）V和P分別獲取相關(guān)參數(shù)和各自的公私鑰對。

2）P根據(jù)系統(tǒng)參數(shù)、自己的公私鑰、投入空間量N等生成自己的隨機文件F。

3）構(gòu)建F對應(yīng)的Merkle樹，并將樹根作為F的承諾值發(fā)送給V。

4）V從整個DAG圖中任意選取幾個頂點，并將其作為挑戰(zhàn)發(fā)送給P。

5）P重新執(zhí)行生成文件F的操縱，并將挑戰(zhàn)頂點及其前驅(qū)點的標簽和Merkle路徑作為響應(yīng)，發(fā)送給V。

6）V驗證響應(yīng)的正確性。

（2）執(zhí)行階段

1）V從頂點挑戰(zhàn)集C中隨機選取幾個頂點，并將其作為挑戰(zhàn)發(fā)送給P。

2）P將挑戰(zhàn)頂點對應(yīng)的Merkle路徑作為響應(yīng)發(fā)送給V。

3）V驗證響應(yīng)的正確性。

3.1.3 基于鋪石游戲的PoSpace安全性研究

基于鋪石游戲的PoSpace協(xié)議的安全性很大程度依賴于DAG圖的構(gòu)造。由于鋪石游戲本身存在時空權(quán)衡的現(xiàn)象，如何加強DAG中前驅(qū)節(jié)點與挑戰(zhàn)集的依賴性，從而使得無法通過一定量的計算實現(xiàn)更少的空間存儲，成為基于鋪石游戲的PoSpace協(xié)議安全性研究的關(guān)鍵問題。

“空間差距（Space Gap）”是一種衡量不同方案間時空權(quán)衡能力的參數(shù)，其本質(zhì)上是一個比值（N-N'）/N，其中N表示誠實證明者需要投入的空間量， 為敵手通過現(xiàn)有手段可獲得的最小空間（也稱為可證明的下界）。

Dziembowski等人[15]提出了兩種圖的結(jié)構(gòu)來構(gòu)造PoSpace協(xié)議，第一種基于Paul、Tarjan和Celoni[22]的圖簇，第二種基于二分圖、超集中圖和Erdos、Graham、Szemeredi[41]的混合構(gòu)造圖。但是，Dziembowski的方案的空間差距至少為，如此大的空間差距使得協(xié)議的安全性無法得到保障。

2016年，Ren等人[30]提出一種堆式二分圖來改善PoSpace協(xié)議的空間差距。堆式二分圖可分為k層，各層分別為且每層包含n個節(jié)點。每層中每個節(jié)點恒定以d為出度，將邊連接到下一層的節(jié)點上，使得每層之間形成一個隨機二分圖。堆式二分圖確實大幅度的提高了空間差距，但理論上仍然存在的差距，且需要將無限增加d的取值作為代價。這極大程度的限制了方案的實用性。

Fisch[39]將堆式二分圖的想法與深度健壯圖結(jié)合起來，將其稱為堆式深度健壯圖，并將其用于PoRep協(xié)議中。隨著構(gòu)造堆式深度健壯圖的迭代次數(shù)不斷增加，理論上方案的空間差距將無限減少，這將允許對初始化階段效率和安全性進行權(quán)衡。此外，堆式深度健壯圖還可以有效地抵抗并行攻擊。

3.2 基于函數(shù)求逆的PoSpace協(xié)議

3.2.1 基于函數(shù)求逆的PoSpace協(xié)議結(jié)構(gòu)

基于函數(shù)求逆的PoSpace協(xié)議中存儲的隨機文件本質(zhì)上是一個函數(shù)表，方案會事先設(shè)計一個反向求解困難的函數(shù)，要求證明者P通過窮舉的方法正向計算出函數(shù)像與原像之間的對應(yīng)關(guān)系并記錄在函數(shù)表中。在初始化階段，證明者P根據(jù)系統(tǒng)參數(shù)和自己的公鑰計算函數(shù)表，其中函數(shù)域由P投入的空間量決定。在執(zhí)行階段，驗證者V在函數(shù)域中抽取一個隨機數(shù)作為挑戰(zhàn)，P根據(jù)挑戰(zhàn)值在函數(shù)表中找出相應(yīng)的原像作為響應(yīng)。具體協(xié)議過程為二個階段。

（1）初始化階段

1）V和P分別獲取相關(guān)參數(shù)和各自的公私鑰對，及函數(shù)像與原像的域。

2）P根據(jù)系統(tǒng)參數(shù)、自己的公私鑰、投入空間量N等生成自己的函數(shù)表F。

（2）執(zhí)行階段

1）V選擇隨機數(shù)人r（mod N），并將其作為挑戰(zhàn)發(fā)送給P。

2）P通過查找函數(shù)表F，找出對應(yīng)的原像作為響應(yīng)。

3）V驗證響應(yīng)的正確性。

3.2.2 基于函數(shù)求逆的PoSpace安全性研究

當前，只有Abusalah[31]提出了一個基于函數(shù)求逆的PoSpace協(xié)議，且基于Hellman的時空權(quán)衡攻擊給出了安全性分析。Hellman的時空權(quán)衡攻擊描述了這樣一個過程：

（1）對于一個正向求解容易但反向求解困難的置換（為了避免發(fā)生碰撞，方案要求函數(shù)f是一個置換），取一個隨機數(shù)x令，考慮序列其中;

（2）取N的一個因子T，證明者會存儲所有的得到新的函數(shù)表，此時函數(shù)表的大小是原大小的1/T;

（3）對于一個隨機挑戰(zhàn)c，證明者對c遞歸的進行f置換，直到與某個發(fā)生碰撞;

（4）找到并遞歸的進行f置換，直到找到一個a使得，則將a作為對挑戰(zhàn)c。

從上面的過程可以看出，一個正向求解容易的置換似乎總是可以通過上述過程，通過T次計算將存儲量降低為原來的1/T，將敵手使用的空間大小記為S，則滿足（表示忽略所有亞線性因子）。但實際上，正向求解容易似乎并不是基于函數(shù)求逆的PoSpace協(xié)議所必須的性質(zhì)。

Abusalah設(shè)計了一個隨機函數(shù)，其由函數(shù)和置換組成。將該隨機函數(shù)定義為，其中（表示為編碼取反）。該方案可以實現(xiàn)的安全性，而且可以通過對這種結(jié)構(gòu)嵌套構(gòu)造，實現(xiàn)的安全性。但是，這種方法構(gòu)造的PoSpace協(xié)議的空間差距為，使得方案缺乏緊湊性。

3.3 兩種方案對比

就當前研究進展而言，基于鋪石游戲PoSpace方案的緊湊性遠優(yōu)于基于函數(shù)求逆PoSpace方案。從協(xié)議的交互過程上看，基于鋪石游戲的PoSpace方案在初始化過程中比基于函數(shù)求逆的PoSpace方案多一個“挑戰(zhàn)-響應(yīng)”階段，用于實現(xiàn)隨機文件的完整性檢查。這使得將PoSpace與區(qū)塊鏈進行結(jié)合的時候，基于鋪石游戲的PoSpace方案還需要有一個注冊過程，用于提交承諾空間、隨機文件的Merkle承諾等信息。而且在執(zhí)行完整性檢查的期間，提供證明的一方必須完整的執(zhí)行一遍隨機文件生成過程，這似乎對于無許可的公鏈而言有些不友好。此外，驗證者在每次驗證證明正確性，還需要獲取提交承諾空間、隨機文件的Merkle承諾等信息，這使得每次驗證還需要回溯以前的塊，而這些區(qū)塊很可能極為久遠。

通過分析執(zhí)行階段很容易發(fā)現(xiàn)，基于鋪石游戲的PoSpace方案證明長度的規(guī)模比基于函數(shù)求逆的PoSpace方案要大很多。對于每一個標簽的位置，基于鋪石游戲的PoSpace方案的證明是一個Merkle路徑，使得證明規(guī)模為O（logN）（N為投入的空間量）。但對于基于函數(shù)求逆的PoSpace方案而言，證明是一個函數(shù)原像，長度規(guī)模為O（1）。

雖然基于鋪石游戲的PoSpace方案在緊湊性方面很有優(yōu)勢，但在具體實現(xiàn)上，區(qū)塊鏈似乎對基于函數(shù)求逆的PoSpace方案更友好。

4 空間量共識與區(qū)塊鏈

專用硬件的出現(xiàn)使得比特幣系統(tǒng)中計算資源越來越集中，其產(chǎn)生的不公平性和能源浪費等問題也日趨嚴重。不同于比特幣中將計算能力作為投入資源，以磁盤容量作為投入資源的PoSpace被視為一種解決這些問題的替代方案。然而將基于PoSpace的共識算法與區(qū)塊鏈系統(tǒng)結(jié)合的過程中仍然面臨著一些挑戰(zhàn)。

4.1 空間量共識在區(qū)塊鏈中的挑戰(zhàn)

PoSpace與區(qū)塊鏈系統(tǒng)結(jié)合的過程中挑戰(zhàn)主要有兩方面，“利益無關(guān)（nothing at stake）問題”和“競爭記賬權(quán)問題”。與比特幣中PoW不同，PoSpace的證明是從礦工存儲文件中讀取的某個隨機數(shù)，這使得所有誠實礦工都可以在第一時間拿出合法的證明，因此什么樣的證明可以在基于PoSpace的共識算法中獲得記賬權(quán)是一個關(guān)鍵的問題。

利益無關(guān)問題[42]是指生成區(qū)塊所需證明的代價很低而產(chǎn)生的一系列安全性威脅。由于PoSpace生成證明的過程非常簡單（僅從已保存的隨機文件中讀?。@使得當使用PoSpace替代PoW時很容易面臨與PoStake一樣的利益無關(guān)問題，而其中比較突出的攻擊手段包括區(qū)塊打磨攻擊（Grinding attack）和長程攻擊（Long-range attack）。

打磨攻擊也可以分為兩種情況。在第一種情況中，礦工通過調(diào)整區(qū)塊中的可變內(nèi)容使得下一個挑戰(zhàn)更有利于自己。區(qū)塊鏈系統(tǒng)中，所有礦工都會從上一個區(qū)塊中獲得隨機挑戰(zhàn)（通常是區(qū)塊頭的哈希值），此時研究人員將獲取記賬權(quán)的過程抽象成一個函數(shù) ，記賬權(quán)由f（x）值最高的礦工獲得，其中x是礦工給出的空間量證明。礦工從自己的隨機文件中讀取相應(yīng)的證明x并計算f（x）的值，如果礦工認為自己很大概率會在記賬權(quán)競爭過程中獲勝，則構(gòu)造對應(yīng)的區(qū)塊頭并反復(fù)調(diào)整區(qū)塊頭的內(nèi)容，使得下一個由自己生成的證明x'也極有可能獲勝。反復(fù)調(diào)整區(qū)塊頭內(nèi)容的過程就是打磨過程，顯然區(qū)塊中有很多內(nèi)容是允許打磨的，如時間戳和事務(wù)數(shù)量等。

第二種情況是在比特幣中，每個礦工的計算能力有限，這使得礦工必須在多個分叉中選擇一條鏈擴展。理性的礦工會要求自己選擇擴展的鏈與大多數(shù)礦工的選擇相一致，如此一來，另一條鏈將逐漸被系統(tǒng)遺忘。由于在基于PoSpace的共識算法中生成證明的過程非常容易，理性的礦工會選擇同時對多個分叉鏈進行擴展，以避免自己選擇的鏈被遺忘所帶來的財產(chǎn)損失。而這樣的結(jié)果將導(dǎo)致分叉永遠存在，且多個分叉會以同樣的速度延伸，從而導(dǎo)致系統(tǒng)永遠無法達成共識。

長程攻擊是指礦工對很早之前的區(qū)塊發(fā)起分叉攻擊，并構(gòu)造一條鏈來代替主鏈。在比特幣系統(tǒng)中，礦工根據(jù)鏈的長度來判斷主鏈，當個人算力無法超過50%時，礦工用永遠無法通過長程攻擊構(gòu)造一條鏈來取代主鏈。但在基于PoSpace的共識算法中，任意礦工都可以生成一條足夠長的鏈，這使得比特幣中的方法行不通。方便起見，這里將礦工判斷主鏈的過程也抽象成一個函數(shù)F（·），顯然F（·）的值應(yīng)該是與鏈上每一個區(qū)塊f（·）值相關(guān)。但礦工似乎總可以通過第一種打磨攻擊構(gòu)造一條鏈，且鏈上的每個區(qū)塊的f（·）值都很高，這極大程度的威脅了共識算法的安全性。

由于利益無關(guān)問題是由產(chǎn)生證明的過程太容易所造成的，因此增加證明產(chǎn)生的難度成為了解決該問題的主要方式。為了使礦工在一段時間內(nèi)（一個挖礦周期中）只能產(chǎn)生有限的證明數(shù)量，許多方案往往會將時間作為一個參考量融入到證明中，因此提出了時空量證明（Proof of SpaceTime，PoST）。當前，已經(jīng)有許多基于PoSpace協(xié)議的區(qū)塊鏈系統(tǒng)，如Spacemesh、Filecoin和Chia。他們都無一例外的提出了PoST的概念，但它們實現(xiàn)的方式都不相同，甚至在概念上也存在很大的差異。當然，也有非PoST解決方案，如Spacemint協(xié)議，它們同樣給基于PoSpace的區(qū)塊鏈系統(tǒng)提出了許多有意義的方案。對于不同系統(tǒng)解決問題的方案如表1所示。

4.2 Spacemint

2018年，Park等人提出了一個基于PoSpace的區(qū)塊鏈協(xié)議—Spacemint[17]。協(xié)議給出一個判斷記賬權(quán)和最佳鏈的具體方案，并基于對利益無關(guān)問題的分析給出了相應(yīng)的解決方案。

在判斷記賬權(quán)和最佳鏈的方案中，Spacemint引入了“質(zhì)量”的概念。在競爭記賬權(quán)的過程中，驗證方會比較不同區(qū)塊的質(zhì)量大小，并將質(zhì)量最大的區(qū)塊作為候選區(qū)塊記在區(qū)塊鏈上。而方案中的鏈質(zhì)量是由鏈上所有區(qū)塊的質(zhì)量按一定權(quán)重乘在一起的結(jié)果。

為了抵抗第一種打磨攻擊，Spacemint對區(qū)塊的結(jié)構(gòu)進行分割。整個區(qū)塊被分割成哈希部分、簽名部分和事務(wù)部分，不同部分之間通過簽名相互關(guān)聯(lián)。該結(jié)構(gòu)將原本區(qū)塊頭中允許打磨的內(nèi)容從哈希部分移到前面部分中，并將哈希部分的哈希值作為下一個區(qū)塊的隨機挑戰(zhàn)，以此來抵抗塊打磨攻擊。出于對第二種打磨攻擊的考慮，Spacemint引入懲罰機制，并設(shè)計適當激勵措施使所有礦工對系統(tǒng)進行監(jiān)督，并舉報惡意行為。

至于長程攻擊，Spacemint提出讓一個區(qū)塊的哈希部分作為此后多個區(qū)塊的挑戰(zhàn)來源。例如，區(qū)塊i的哈希部分的哈希值c，將為其后的次記賬權(quán)競爭生成隨機挑戰(zhàn)，如此一來，礦工就不能通過調(diào)整區(qū)塊內(nèi)容來獲得更有利于自己的挑戰(zhàn)。

此外，Spacemint中調(diào)整了基于鋪石游戲PoSpace的交互過程。原本基于鋪石游戲PoSpace的交互過程中，初始化階段需要完成隨機文件生成和文件完整性證明兩個過程。在Spacemint的初始化階段中，礦工僅完成隨機文件生成然后就開始執(zhí)行階段，而文件完整性證明則在成功獲得記賬權(quán)后隨完整區(qū)塊一起提交給區(qū)塊鏈。這樣做的優(yōu)點是多次檢查文件完整性，提高了系統(tǒng)的安全性。但缺點是每一次文件完整性證明生成的過程相當于重新生成隨機文件的過程，這種效率對于實際的系統(tǒng)而言是不可能接受的。

Spacemint確實為基于PoSpace系統(tǒng)設(shè)計提出了許多有用的建議，但仍然有一些問題解決的不夠優(yōu)雅（如，抵御第二種打磨攻擊采用的懲罰機制），這使得該協(xié)議離實際部署仍有一定差距。

4.3 Chia

Chia是由Cohen和Pietrzak[43]提出的一種基于函數(shù)求逆PoSpace的共識方案，目前作為Alpha電子貨幣的底層協(xié)議，該項目一定程度上借鑒了Spacemint的處理方法，但在許多問題的處理上比Spacemint更加實用。

Chia在解決競爭記賬權(quán)的問題時引入了PoST的概念。在Chia網(wǎng)絡(luò)中除了有礦工負責打包區(qū)塊之外，還有時主需要確認礦工生成的空間量證明。時主確認證明時采用的技術(shù)是VDF[44]，不同于Fisch方案中數(shù)據(jù)編碼的作用，此處是利用了VDF計算過程緩慢的性質(zhì)，使得確認一個合法的證明需要消耗一些時間資源。在競爭記賬權(quán)的過程中，礦工產(chǎn)生空間證明后需要交由時主確認，而后才能被記入?yún)^(qū)塊鏈中。Chia借用了Spacemint中區(qū)塊質(zhì)量的概念，要求時主確認證明的速度與證明的質(zhì)量有關(guān)，這使得質(zhì)量越優(yōu)的區(qū)塊越容易被確認，從而獲得記賬權(quán)。

在對抗第一種打磨攻擊的方法上，Chia除了采用Spacemint的區(qū)塊分割方式之外，還要求哈希部分的密碼原語均具有唯一性，以防止礦工對簽名、證明值或VDF輸出進行打磨。對于第二種打磨攻擊，Chia采取的方案是允許礦工對分叉的多條鏈進行延伸。對于時主而言，每個競爭周期他們只會確認k個證明（由于網(wǎng)絡(luò)延時的原因，可能存在每個周期確認證明數(shù)量多于k的情況）。k的值設(shè)置的越大，越能保證系統(tǒng)的安全性，但隨著k的增加，每個周期礦工的負擔也在增加，Chia的開發(fā)團隊認為k=3是一個較為合理的權(quán)衡。

另外，由于VDF是一個計算緩慢的技術(shù)，其似乎天然具有抵抗長程攻擊的優(yōu)勢。這使得在Chia中，礦工幾乎不可能以很快的速度產(chǎn)生一條當前鏈的替代鏈。

4.4 Spacemesh

Spacemesh是一個將用戶投入的空間資源和投入時長綜合考慮的共識協(xié)議，當前也作為電子貨幣系統(tǒng)的底層協(xié)議。該項目開創(chuàng)性的使用網(wǎng)狀結(jié)構(gòu)代替常見的鏈狀結(jié)構(gòu)，為區(qū)塊鏈研究提供了許多開創(chuàng)性的思路。

與Chia中增加證明生成難度的目的不同，Spacemesh中提到的PoST[45，46]概念強調(diào)礦工或投入一定量空間，或消耗一定量的計算能力。與PoSpace不同的是，PoST允許礦工對存儲的數(shù)據(jù)進行時空權(quán)衡，但根據(jù)其理性存儲證明保證了一個理性礦工必然選擇存儲完整數(shù)據(jù)作為資源投入（即，存儲完整數(shù)據(jù)的代價最小）。此外，PoST并不使用類似于鋪石游戲的空間難解函數(shù)，而是通過不可壓縮工作量證明（Incompressible Proofs of Work，IPoW）計算隨機文件。IPoW強調(diào)的不可壓縮性使得礦工無法通過少量存儲節(jié)省計算時間，即每一塊數(shù)據(jù)的丟失都必須通過完整的計算重新獲得，提高了刪除部分文件的代價。為了證明礦工投入資源用掉的時間，Spacemesh引入了消逝時間證明（Proof of Elapsed Time，PoET），該技術(shù)可以證明從礦工得到初始挑戰(zhàn)到現(xiàn)在所用的時間。最終，將PoET和PoST組合并結(jié)合Fiat-Shamir技術(shù)，從而實現(xiàn)了非交互時空證明（Non-Interactive Proofs of Space-Time），該證明可確保礦工確實在一定時間內(nèi)投入了一定量的空間。

對于競爭記賬權(quán)問題，協(xié)議要求每個礦工進入系統(tǒng)時都需要對自己的身份進行注冊，系統(tǒng)會將所有的注冊身份匯成一張身份表存儲在注冊節(jié)點上。在每層競爭記賬權(quán)的過程中，每個礦工先通過一個統(tǒng)一的隨機函數(shù)計算出身份表上的一個子集，然后在這些礦工生成的區(qū)塊中選出超過閾值的區(qū)塊記錄在區(qū)塊鏈上。這一思想類似于Chia中，對每個周期確認證明數(shù)量k的控制，因此同樣具有防止第二種打磨攻擊的作用。此外，方案結(jié)合拜占庭算法提出了“龜兔共識（tortoise and hares consensus）”協(xié)議[48]，由此確保誠實者的資源都集中在同一條鏈上，從而有效地抵抗長程攻擊。

4.5 Filecoin

Filecoin[48]是一個基于PoRep協(xié)議[34]設(shè)計的文件存儲與檢索系統(tǒng)。系統(tǒng)中包含用戶、存儲礦工和檢索礦工三種角色，其中用戶需要使用系統(tǒng)存儲或獲取數(shù)據(jù)，存儲礦工通過幫助用戶存儲數(shù)據(jù)來獲得服務(wù)費，而檢索礦工通過幫助用戶獲取數(shù)據(jù)來獲得服務(wù)費。但只有存儲礦工才能產(chǎn)生新的區(qū)塊，檢索礦工需要根據(jù)請求尋找存儲對應(yīng)資源的存儲礦工，并要求其提供數(shù)據(jù)服務(wù)。

Filecoin在競爭記賬權(quán)階段采用了“期望共識（Expected Consensus）”的方法，該方法要求在每個周期中，區(qū)塊鏈系統(tǒng)會選取小部分人獲得記賬權(quán)，人數(shù)的期望為1。但在某個階段中，選取的人數(shù)可能為0或2。如果為0則由系統(tǒng)添加一個空塊;如果為2則會類似于比特幣，較少人選擇的鏈將會被人遺忘。對于礦工而言，它們需要在每個競爭周期檢查自己是否被選中，檢查方法類似CoA[49]、Snow White[50]或Algorand[51]。

Filecoin中也存在PoST的概念，其通過反復(fù)讀取隨機文件來增加礦工產(chǎn)生證明的復(fù)雜程度。Filecoin中的PoST本質(zhì)上是一個證據(jù)鏈，礦工根據(jù)區(qū)塊鏈系統(tǒng)中給出的挑戰(zhàn)計算第一個證明，再根據(jù)第一個證明的哈希值計算的二個證明，依次計算出完整的證據(jù)鏈。證據(jù)鏈的串行計算對長程攻擊和第二種打磨攻擊都能起到一定的抵御作用。

5 結(jié)束語

空間量證明作為工作量證明的一種替代方案，其節(jié)省能源和公平的特性吸引了許多研究學者的青睞。本文對一些存儲證明技術(shù)進行介紹，并對空間量證明的研究進行詳細的梳理與分析。此外，文章希望給專注于共識算法的研究人員一個新視角，并對后續(xù)的研究起到啟發(fā)和借鑒作用。

綜合現(xiàn)有的對空間量證明的研究來看，大致可以分為三個方向，分別為功能研究、緊湊性研究和工程研究。

在功能研究上，一個重要的成果就是PoRep協(xié)議。該協(xié)議使得礦工在貢獻磁盤空間時，不再存儲一些無意義的隨機文件，而是有意義且可恢復(fù)的文件。一個簡單的想法是，基于該技術(shù)開發(fā)的區(qū)塊鏈系統(tǒng)不再把存儲區(qū)塊作為一種負擔，而將其作為自己獲取獎勵的資源。此外，可以結(jié)合DPDP技術(shù)，在保證遠程數(shù)據(jù)存儲安全性的同時增加動態(tài)性，使得區(qū)塊鏈系統(tǒng)不只提供存儲服務(wù)，還可以動態(tài)產(chǎn)生或刪除一些用戶數(shù)據(jù)。

在緊湊性研究上，基于鋪石游戲的PoSpace方案已經(jīng)取得了一些理論成就，但將具有完美緊湊性的PoSpace投入應(yīng)用還有些距離。另一方面，由于區(qū)塊鏈對基于函數(shù)求逆的PoSpace方案更友好，因此提高基于函數(shù)求逆PoSpace的緊湊性將非常有意義。

在工程研究上，協(xié)議的安全和效率是永恒的話題。雖然基于PoSpace的區(qū)塊鏈系統(tǒng)已經(jīng)開始部署，但單從理論上難以判斷其成功與否。對各類區(qū)塊鏈系統(tǒng)需要不斷發(fā)掘可能出現(xiàn)的惡意行為，并研究對抗策略。通過不斷嘗試引入新的密碼技術(shù)，完善人們對系統(tǒng)的需求。

參考文獻

[1] Nakamoto S. Bitcoin： A peer-to-peer electronic cash system[J]. 2008.

[2] Underwood S. Blockchain beyond bitcoin[J]. Communications of the ACM， 2016， 59（11）： 15-17.

[3] Mettler M. Blockchain technology in healthcare： The revolution starts here[C]//2016 IEEE 18th International Conference on e-Health Networking， Applications and Services （Healthcom）. IEEE， 2016： 1-3.

[4] Dorri A， Kanhere S S， Jurdak R， et al. Blockchain for IoT security and privacy： The case study of a smart home[C]//2017 IEEE international conference on pervasive computing and communications workshops （PerCom workshops）. IEEE， 2017： 618-623.

[5] Mital R， de La Beaujardiere J， Mital R， et al. Blockchain application within a multi-sensor satellite architecture[J]. 2018.

[6] 袁勇，倪曉春，曾帥，等.區(qū)塊鏈共識算法的發(fā)展現(xiàn)狀與展望[J].自動化學報， 2018， 44（11）： 2011-2022.

[7] De Vries A. Bitcoin's growing energy problem[J]. Joule， 2018， 2（5）： 801-805.

[8] King S， Nadal S. Ppcoin： Peer-to-peer crypto-currency with proof-of-stake[J]. self-published paper， August， 2012， 19.

[9] Larimer D. Delegated proof-of-stake （dpos）[J]. Bitshare whitepaper， 2014.

[10] Dwork C， Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer， Berlin， Heidelberg， 1992： 139-147.

[11] Abadi M， Burrows M， Manasse M， et al. Moderately hard， memory-bound functions[J]. ACM Transactions on Internet Technology （TOIT）， 2005， 5（2）： 299-327.

[12] Dwork C， Goldberg A， Naor M. On memory-bound functions for fighting spam[C]//Annual International Cryptology Conference. Springer， Berlin， Heidelberg， 2003： 426-444.

[13] Dwork C， Naor M， Wee H. Pebbling and proofs of work[C]//Annual International Cryptology Conference. Springer， Berlin， Heidelberg， 2005： 37-54.

[14] Percival C. Stronger key derivation via sequential memory-hard functions[J]. 2009.

[15] Dziembowski S， Faust S， Kolmogorov V， et al. Proofs of space[C]//Annual Cryptology Conference. Springer， Berlin， Heidelberg， 2015： 585-605.

[16] Ateniese G， Bonacina I， Faonio A， et al. Proofs of space： When space is of the essence[C]//International Conference on Security and Cryptography for Networks. Springer， Cham， 2014： 538-557.

[17] Park S， Kwon A， Fuchsbauer G， et al. Spacemint： A cryptocurrency based on proofs of space[C]//International Conference on Financial Cryptography and Data Security. Springer， Berlin， Heidelberg， 2018： 480-499.

[18] Alwen J， Chen B， Kamath C， et al. On the complexity of scrypt and proofs of space in the parallel random oracle model[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Berlin， Heidelberg， 2016： 358-387.

[19] Perito D， Tsudik G. Secure code update for embedded devices via proofs of secure erasure[C]//European Symposium on Research in Computer Security. Springer， Berlin， Heidelberg， 2010： 643-662.

[20] Dziembowski S， Kazana T， Wichs D. One-time computable self-erasing functions[C]//Theory of Cryptography Conference. Springer， Berlin， Heidelberg， 2011： 125-143.

[21] Karvelas N P， Kiayias A. Efficient proofs of secure erasure[C]//International Conference on Security and Cryptography for Networks. Springer， Cham， 2014： 520-537.

[22] Paul W J， Tarjan R E， Celoni J R. Space bounds for a game on graphs[J]. Mathematical systems theory， 1976， 10（1）： 239-251.

[23] Deswarte Y， Quisquater J J， Sa?dane A. Remote integrity checking[C]//Working Conference on Integrity and Internal Control in Information Systems. Springer， Boston， MA， 2003： 1-11.

[24] Diffie W， Hellman M. New directions in cryptography[J]. IEEE transactions on Information Theory， 1976， 22（6）： 644-654.

[25] Gazzoni Filho D L， Barreto P S L M. Demonstrating data possession and uncheatable data transfer[J]. IACR Cryptology ePrint Archive， 2006， 2006： 150.

[26] Ateniese G， Burns R， Curtmola R， et al. Provable data possession at untrusted stores[C]//Proceedings of the 14th ACM conference on Computer and communications security. 2007： 598-609.

[27] Juels A， Kaliski Jr B S. PORs： Proofs of retrievability for large files[C]//Proceedings of the 14th ACM conference on Computer and communications security. 2007： 584-597.

[28] Erway C C， Küp?ü A， Papamanthou C， et al. Dynamic provable data possession[J]. ACM Transactions on Information and System Security （TISSEC）， 2015， 17（4）： 1-29.

[29] Tompa M. Time-space tradeoffs for computing functions， using connectivity properties of their circuits[J]. Journal of Computer and System Sciences， 1980， 20（2）： 118-132.

[30] Ren L， Devadas S. Proof of space from stacked expanders[C]//Theory of Cryptography Conference. Springer， Berlin， Heidelberg， 2016： 262-285.

[31] Abusalah H， Alwen J， Cohen B， et al. Beyond Hellmans time-memory trade-offs with applications to proofs of space[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer， Cham， 2017： 357-379.

[32] Hellman M. A cryptanalytic time-memory trade-off[J]. IEEE transactions on Information Theory， 1980， 26（4）： 401-406.

[33] Fiat A， Naor M. Rigorous time/space tradeoffs for inverting functions[C]//Proceedings of the twenty-third annual ACM symposium on Theory of computing. 1991： 534-541.

[34] Benet J， Dalrymple D， Greco N. Proof of replication[J]. Protocol Labs， July， 2017， 27： 20.

[35] Pietrzak K. Proofs of catalytic space[C]//10th Innovations in Theoretical Computer Science Conference （ITCS 2019）. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik， 2018.

[36] Alwen J， Blocki J， Pietrzak K. Sustained space complexity[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Cham， 2018： 99-130.

[37] Fisch B. PoReps： Proofs of Space on Useful Data[J]. IACR Cryptology ePrint Archive， 2018， 2018： 678.

[38] Boneh D， Bonneau J， Bünz B， et al. Verifiable delay functions[C]//Annual international cryptology conference. Springer， Cham， 2018： 757-788.

[39] Fisch B. Tight proofs of space and replication[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Cham， 2019： 324-348.

[40] Alwen J， Blocki J， Harsha B. Practical graphs for optimal side-channel resistant memory-hard functions[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017： 1001-1017.

[41] Erdoes P， Graham R L， Szemeredi E. On sparse graphs with dense long paths[M]. Stanford University. Computer Science Department， 1975.

[42] Martinez J. Understanding proof of stake： the nothing at stake theory[J]. 2018.

[43] Cohen B， Pietrzak K. The Chia Network Blockchain[J]. 2019.

[44] Pietrzak K. Simple verifiable delay functions[C]//10th innovations in theoretical computer science conference （itcs 2019）. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik， 2018.

[45] Moran T， Orlov I. Rational proofs of space-time[J]. Cryptol. ePrint Arch.， Tech. Rep， 2016， 35.

[46] Moran T， Orlov I. Simple proofs of space-time and rational proofs of storage[C]//Annual International Cryptology Conference. Springer， Cham， 2019： 381-409.

[47] Bentov I， Hubácek P， Moran T， et al. Tortoise and Hares Consensus： the Meshcash Framework for Incentive-Compatible， Scalable Cryptocurrencies[J]. IACR Cryptology ePrint Archive， 2017， 2017： 300.

[48] Benet J， Greco N. Filecoin： A decentralized storage network[J]. Protoc. Labs， 2018.

[49] Bentov I， Lee C， Mizrahi A， et al. Proof of activity： Extending bitcoin's proof of work via proof of stake [extended abstract] y[J]. ACM SIGMETRICS Performance Evaluation Review， 2014， 42（3）： 34-37.

[50] Bentov I， Pass R， Shi E. Snow White： Provably Secure Proofs of Stake[J]. IACR Cryptology ePrint Archive， 2016， 2016（919）.

[51] Micali S. Algorand： the efficient and democratic ledger （2016）[J]. arXiv preprint arXiv：1607.01341， 2017.