3. 復(fù)制證明與時空證明

在Filecoin協(xié)議中，存儲供應(yīng)商必須讓客戶相信，他們的數(shù)據(jù)已經(jīng)被完好存儲。在實(shí)際操作中，存儲供應(yīng)商會生成存儲證明（Proofs-of-Storage，POS）給區(qū)塊鏈網(wǎng)絡(luò)（或客戶本身）進(jìn)行驗(yàn)證。

本節(jié)中，我們將展示和概括在Filecoin中所使用的復(fù)制證明（Proof-of-Replication，PoRep）和時空證明（Proof-of-Spacetime，PoSt）實(shí)現(xiàn)方案。

3.1 動機(jī)

存儲證明（POS）方案，例如可證明數(shù)據(jù)擁有（PDP）以及可恢復(fù)性證明（PoR）方案，它允許用戶（即審核人V）將數(shù)據(jù)外包給服務(wù)器（既證明人P）以檢查服務(wù)器是否依然存儲數(shù)據(jù)D。用戶可以用比下載數(shù)據(jù)還便捷的方式，來驗(yàn)證外包給服務(wù)器數(shù)據(jù)的完整性。服務(wù)器通過對一組區(qū)塊進(jìn)行隨機(jī)采樣和傳送少量數(shù)據(jù)，來生成概率性的擁有證明，以此作為給用戶的懷疑/響應(yīng)協(xié)議。

PDP和PoR方案只允許證明人在懷疑/響應(yīng)的時候擁有某些數(shù)據(jù)。在Filecoin中，我們需要更強(qiáng)大的保障，來阻止惡意礦工通過攻擊獲得不應(yīng)得的獎勵。常見的三種攻擊類型有：女巫攻擊（Sybil attack）、外包攻擊（outsourcing attacks）、生成攻擊（generation attacks）。

[[224242]]

3.2 復(fù)制證明

復(fù)制證明（PoRep）是一個新型的存儲證明，它允許服務(wù)器（證明人P)向用戶（審核人V）證明：數(shù)據(jù)D已被復(fù)制到它專有的物理存儲上了。我們的方案是一種交互式協(xié)議，證明人P:（a）承諾存儲數(shù)據(jù)D的n個不同的拷貝（獨(dú)立物理拷貝），然后（b）通過懷疑/響應(yīng)協(xié)議來使審核人V相信P確實(shí)已經(jīng)存儲了每個拷貝。我們目前已經(jīng)知道，PoRep在PDP和PoR方案中，阻止女巫攻擊、外包攻擊、生成攻擊的能力會有所提高。

注意，想要PoRep正式的定義，以及了解它的屬性和深入研究的，我們推薦參考[5]

【定義六】  PoRep方案允許有效的證明人P來說服審核人V：數(shù)據(jù)D的獨(dú)立物理副本R已被p存儲。PoRep協(xié)議是多項(xiàng)式時間算法的元組：

(Setup, Prove, Verify)

• Setup(1λ, D) → R, SP , SV, 其中SP和SV是為方案專門設(shè)定的P和V變量，λ是一個安全參數(shù)。PoRep.Setup用來生成副本R，以及給予P和V必要的信息來運(yùn)行PoRep.Prove 和 PoRep.Verify。一些方案可能會要求證明人或者第三方交互來運(yùn)算PoRep.Setup。
• Prove(SP, R, c) → πc，其中c是審核人V發(fā)出的隨機(jī)質(zhì)疑， πc是證明人產(chǎn)生的訪問R的證明，R是D的特定副本。PoRep.Prove由P運(yùn)行，為V生成πc。
• Verify(Sv, c, πc)→ {0, 1}，用來檢測證明是否正確。PoRep.Verify由V運(yùn)行，并使V相信P已經(jīng)存儲了R。

3.3 時空證明

存儲證明方案允許用戶檢查存儲提供商當(dāng)時是否存儲了外包數(shù)據(jù)。我們?nèi)绾问褂肞oS方案來證明在一段時間內(nèi)數(shù)據(jù)被存儲了？一個非常自然的答案是要求用戶重復(fù)（例如，每分鐘）對存儲提供商發(fā)送請求。然而這樣的交互所需要的通信復(fù)雜度會成為一些系統(tǒng)的瓶頸。像Filecoin這樣，存儲提供商會被要求提交證明到區(qū)塊鏈網(wǎng)絡(luò)。

為了解決這個問題，我們介紹一個新的證明，時空證明（Proof-of-Spacetime），它可以讓審核人檢查存儲提供商是否在一段時間內(nèi)存儲了他的外包數(shù)據(jù)。這就對證明人產(chǎn)生了直觀的要求：（1）生成連續(xù)的存儲證明（在本文中是“復(fù)制證明”）來作為確定時間的一種方法。（2）遞歸執(zhí)行來生成簡單的證明。

【定義七】  （時空證明）Post方案可使有效的證明人P能夠說服一個審核人V相信P在一段時間內(nèi)存儲了數(shù)據(jù)D。PoSt是多項(xiàng)式時間算法的元組：

  (Setup, Prove, Verify)

• Setup(1λ, D) → R, SP , SV, 其中SP和SV是為方案專門設(shè)定的P和V變量，λ是一個安全參數(shù)。PoRep.Setup用來生成副本R，以及給予P和V必要的信息來運(yùn)行PoRep.Prove 和 PoRep.Verify。一些方案可能會要求證明人或者第三方交互來運(yùn)算PoRep.Setup。
• Prove(SP, R, c) → πc，其中c是審核人V發(fā)出的隨機(jī)質(zhì)疑， πc是證明人產(chǎn)生的訪問R的證明，R是D的特定副本。PoRep.Prove由P運(yùn)行，為V生成πc。
• Verify(Sv, c, πc)→ {0, 1}，用來檢測證明是否正確。PoRep.Verify由V運(yùn)行，并使V相信P已經(jīng)存儲了R。

3.4 PoRep和PoSt實(shí)際應(yīng)用

我們對PoRep和PoSt在現(xiàn)有系統(tǒng)上的應(yīng)用很感興趣，希望能構(gòu)建一個實(shí)用性系統(tǒng)，但不依賴任何的中心式第三方或者硬件。我們給出了一個PoRep架構(gòu)（見“密封的復(fù)制證明”[5]），它需要在Setup過程中執(zhí)行緩慢的順序計算密封來生成副本。PoRep和PoSt的協(xié)議草圖詳見圖4，Post證明步驟的底層機(jī)制的見圖3。

3.4.1 構(gòu)建加密區(qū)塊

防碰撞散列。我們使用一個防碰撞散列函數(shù)：CRH : {0, 1}* → {0, 1}O(λ)。以及另一個一個防碰撞散列函數(shù)MerkleCRH，它可以將字符串分割成多個部分，構(gòu)造二叉樹并將遞歸應(yīng)用到CRH，最后輸出根。

zk-SNARKs。我們對PoRep和PoSt的實(shí)現(xiàn)依賴于零知識的簡潔非交互式知識論（zero-knowledge Succinct Noninteractive ARguments of Knowledge，zk-SNARKs)[6,7,8]。因?yàn)閦k-SNARKs非常簡潔，證明短并且容易驗(yàn)證。形式上來說，就是讓L作為NP語言，并用C做為L的判決電路。中心式信任方執(zhí)行一次設(shè)置會產(chǎn)生兩個公共密鑰：證明密鑰pk和驗(yàn)證密鑰vk。證明密鑰pk可使任何（非信任的）的證明人都能生成證明π來證明x∈L，x是任一實(shí)例。非交互式證明π是零知識的，也是知識證明的。任何人都可以使用驗(yàn)證密鑰vk來驗(yàn)證π證明。尤其zk-SNARK的證明是可公開驗(yàn)證的：任何人都可以驗(yàn)證π，而不需要與生成π的證明者進(jìn)行交互。π證明具有恒定的大小，并且可以在| x |的線性時間內(nèi)得到及時驗(yàn)證。

zk-SNARKs是一個三項(xiàng)式時間算法：

(KeyGen, Prove, Verify)

• KeyGen(1λ,C)→(pk, vk)。輸入安全參數(shù)為λ，回路為C，pk和vk是KeyGen的概率樣本。這兩個密匙是公共參數(shù)，可用于證明/審核Lc上的成員。
• Prove(pk, x, w)→π。在輸入pk、輸入x并看到NP聲明w后，如果x∈LC，證明人Prove會輸出非交互式證明π。
• Verify(vk, x,π)→{0, 1}。當(dāng)輸入vk，x和證明 π，如果有x∈LC，審核人verifier輸出1。

建議有興趣的讀者閱讀[6，7，8]，那里有對zk-SNARK系統(tǒng)的概念和實(shí)現(xiàn)更詳細(xì)的介紹。通常來說系統(tǒng)會要求KeyGen是由中心式可信任參與方來運(yùn)行的。新型可擴(kuò)展計算的完整性和隱私性（SCIP）系統(tǒng)[9]展示了一個很有前景的、可以避免這個步驟的發(fā)展方向，才有了上面的信任假設(shè)。

3.4.2 密封操作

密封操作的作用是：（1）通過要求證明人存儲公鑰下數(shù)據(jù)D的偽隨機(jī)序列，強(qiáng)制副本成為成為相互獨(dú)立的拷貝，這樣提交n個副本后就會產(chǎn)生n個獨(dú)立的磁盤空間（并占用副本大小n倍的儲存空間）。（2）在運(yùn)行PoRep.Setup的時候強(qiáng)制生成副本，實(shí)質(zhì)上會比預(yù)估的質(zhì)疑響應(yīng)花費(fèi)更多的時間。有關(guān)密封操作的更正式定義，請參見[5]。上述的操作可以用SealτAES?256實(shí)現(xiàn)，SealτAES?256中的τ需要比常規(guī)的“質(zhì)疑-證明-審核”序列多花費(fèi)10-100倍的時間。所以對τ的選擇非常重要的，因?yàn)檫\(yùn)行SealτBC可能比證明人隨機(jī)訪問R要花費(fèi)更多時間。

3.4.3 PoRep構(gòu)建實(shí)踐

本節(jié)將描述PoRep協(xié)議的組成，并在圖4展示簡化的協(xié)議草圖。我們略過了具體實(shí)現(xiàn)方法和優(yōu)化細(xì)節(jié)。

創(chuàng)建副本。Setup算法通過密封操作，和正確生成副本的證明，來實(shí)現(xiàn)副本的生成。證明人生成副本，并將輸出（不包括R）發(fā)送給審核人。

證明存儲。Prove算法生成副本存儲的證明。證明人收到來自審核人的隨機(jī)質(zhì)疑c。該審核人在樹根為rt的Merkle樹R中確定葉子節(jié)點(diǎn)Rc。證明人生成關(guān)于Rc，和其延伸到葉子Rc的Merkle路徑的知識證明。

審核證明?？紤]到副本的Merkle樹根，和原始數(shù)據(jù)的散列，Verify算法會審核存儲證明的有效性。證明是公開可驗(yàn)證的：分布式系統(tǒng)的節(jié)點(diǎn)保持了賬本和客戶對特定數(shù)據(jù)的關(guān)注，這樣就能驗(yàn)證這些證明。

3.4.4 PoSt構(gòu)建實(shí)踐

本節(jié)將描述Post協(xié)議架構(gòu)，并在圖4中給出一個簡單協(xié)議草圖。本節(jié)忽略實(shí)現(xiàn)過程和優(yōu)化細(xì)節(jié)。Setup和Verify算法和前文的PoRep架構(gòu)相同，所以這里只描述Prove。

證明時空。Prove算法為副本生成時空證明。證明人接收來自于審核人的隨機(jī)質(zhì)疑，并順序生成復(fù)制證明，證明輸出后，經(jīng)過特定次數(shù)的迭代t，可作為其他的輸入（見圖3）。

Figure 3: Illustration of the underlying mechanism of PoSt.Prove showing the iterative proof to demonstrate storage over time.

3.5 在Filecoin中的應(yīng)用

Filecoin協(xié)議采用時空證明來審核礦工提供的存儲。因?yàn)闆]有指定的審核人，并且我們希望網(wǎng)絡(luò)中的任何成員都有審核權(quán)，所以為了在Filecoin中使用PoSt，我們把方案改為了非交互式的。我們的審核人在公開的代幣模型中運(yùn)行，所以我們可以從區(qū)塊鏈中隨機(jī)地發(fā)出質(zhì)疑。