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

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

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

3.1 動(dòng)機(jī)

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

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

[[224242]]

3.2 復(fù)制證明

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

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

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

(Setup, Prove, Verify)

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

3.3 時(shí)空證明

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

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

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

  (Setup, Prove, Verify)

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

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

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

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

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

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

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

(KeyGen, Prove, Verify)

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

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

3.4.2 密封操作

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

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

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

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

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

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

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

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

證明時(shí)空。Prove算法為副本生成時(shí)空證明。證明人接收來(lái)自于審核人的隨機(jī)質(zhì)疑，并順序生成復(fù)制證明，證明輸出后，經(jīng)過(guò)特定次數(shù)的迭代t，可作為其他的輸入（見(jiàn)圖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é)議采用時(shí)空證明來(lái)審核礦工提供的存儲(chǔ)。因?yàn)闆](méi)有指定的審核人，并且我們希望網(wǎng)絡(luò)中的任何成員都有審核權(quán)，所以為了在Filecoin中使用PoSt，我們把方案改為了非交互式的。我們的審核人在公開(kāi)的代幣模型中運(yùn)行，所以我們可以從區(qū)塊鏈中隨機(jī)地發(fā)出質(zhì)疑。