基于空間量證明的共識算法綜述

王昱博 馬春光

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

關鍵詞：區塊鏈;空間量證明;共識算法

中圖分類號： 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]作為第一個以區塊鏈技術實現的應用，一經問世就吸引了眾多研究人員的目光，這一現象也使得區塊鏈相關的技術得到了飛速發展。盡管最初區塊鏈的應用僅限于電子貨幣[2]，但隨著研究人員的不斷嘗試與創新，區塊鏈技術已經開始逐漸融入各行各業，如醫療[3]、智能家居[4]、衛星通信[5]等。共識算法作為區塊鏈的核心技術之一，其保證了區塊鏈系統的分布式一致性，對推動區塊鏈的發展有著重大作用，也自然而然的被廣大研究人員所關注。

區塊鏈是通過采用對等（Peer-to-Peer，P2P）網絡組織所有節點[6]，并采用激勵機制使得每個節點自愿參與系統維護的過程，而共識算法就是為了實現在這樣一個分布式系統中保證不同節點數據存儲的一致性。但因為P2P網絡中節點間無法相互約束，且激勵機制使得區塊鏈系統中有利可圖，這必然會出現一些節點希望通過不誠實行為，獲得比誠實節點更高的利益。為了防止潛在的不誠實行為的出現，系統必須通過恰當的共識算法使得不誠實的行為被大多數用戶所認可。

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

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

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

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

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

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

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

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

2 存儲證明技術

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

2.1安全擦除證明

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

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

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

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

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

2.2 可證明數據持有

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

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

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

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

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

2.3 空間量證明

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

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

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

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

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

2.4 復制證明

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

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

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

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

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

3 空間量證明分類

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

3.1 基于鋪石游戲的PoSpace協議

3.1.1 鋪石游戲與標簽問題

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

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

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

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

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

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

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

3.1.2 基于鋪石游戲的PoSpace協議結構

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

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

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

（1）初始化階段

1）V和P分別獲取相關參數和各自的公私鑰對。

2）P根據系統參數、自己的公私鑰、投入空間量N等生成自己的隨機文件F。

3）構建F對應的Merkle樹，并將樹根作為F的承諾值發送給V。

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

5）P重新執行生成文件F的操縱，并將挑戰頂點及其前驅點的標簽和Merkle路徑作為響應，發送給V。

6）V驗證響應的正確性。

（2）執行階段

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

2）P將挑戰頂點對應的Merkle路徑作為響應發送給V。

3）V驗證響應的正確性。

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

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

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

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

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

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

3.2 基于函數求逆的PoSpace協議

3.2.1 基于函數求逆的PoSpace協議結構

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

（1）初始化階段

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

2）P根據系統參數、自己的公私鑰、投入空間量N等生成自己的函數表F。

（2）執行階段

1）V選擇隨機數人r（mod N），并將其作為挑戰發送給P。

2）P通過查找函數表F，找出對應的原像作為響應。

3）V驗證響應的正確性。

3.2.2 基于函數求逆的PoSpace安全性研究

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

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

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

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

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

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

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

3.3 兩種方案對比

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

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

雖然基于鋪石游戲的PoSpace方案在緊湊性方面很有優勢，但在具體實現上，區塊鏈似乎對基于函數求逆的PoSpace方案更友好。

4 空間量共識與區塊鏈

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

4.1 空間量共識在區塊鏈中的挑戰

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

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

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

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

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

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

4.2 Spacemint

2018年，Park等人提出了一個基于PoSpace的區塊鏈協議—Spacemint[17]。協議給出一個判斷記賬權和最佳鏈的具體方案，并基于對利益無關問題的分析給出了相應的解決方案。

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

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

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

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

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

4.3 Chia

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

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

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

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

4.4 Spacemesh

Spacemesh是一個將用戶投入的空間資源和投入時長綜合考慮的共識協議，當前也作為電子貨幣系統的底層協議。該項目開創性的使用網狀結構代替常見的鏈狀結構，為區塊鏈研究提供了許多開創性的思路。

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

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

4.5 Filecoin

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

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

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

5 結束語

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

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

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

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

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

參考文獻

[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] 袁勇，倪曉春，曾帥，等.區塊鏈共識算法的發展現狀與展望[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.