概 要
存儲證明是 Filecoin 網(wǎng)絡(luò)成立的基礎(chǔ)，F(xiàn)ilecoin的存儲證明包括：PoRep（復(fù)制證明）和 PoSt（時空證明）
PoRep = PoS + PoR
算法的設(shè)計目標(biāo)是，復(fù)制證明必須在足夠長的時間內(nèi)才能完成绵咱，而時空證明要足夠快蝎毡，從而達(dá)到防止作弊的目的
證明算法具體實現(xiàn)在 rust-fil-proofs 項目中袖扛，F(xiàn)ilecoin實現(xiàn)通過CGo調(diào)用 Rust 相關(guān)函數(shù)
1. 為什么需要存儲證明
信息產(chǎn)業(yè)發(fā)展至今傲诵，存儲已經(jīng)成為一個最為基礎(chǔ)的產(chǎn)業(yè)耽装。整個存儲市場處于高速發(fā)展之中龙考，基本上是每兩年存儲容量就翻一番蟆肆。然而，作為信息的承載體晦款，存儲市場起步晚于網(wǎng)絡(luò)市場勉盅，因此蓝晒，其發(fā)展也較晚，當(dāng)通用網(wǎng)絡(luò)協(xié)議和實現(xiàn)都已經(jīng)標(biāo)準(zhǔn)化的今天，存儲市場卻完全被巨頭把控解藻。在存儲越來越重要的今天界牡，通用的統(tǒng)一的存儲網(wǎng)絡(luò)呼聲也就越來越高镇防。
Filecoin就是致力于建立這樣一個通用的人人可以參與的存儲網(wǎng)絡(luò)活玲，在這個網(wǎng)絡(luò)之中，沒有寡頭控制袜匿，也無需巨頭背書更啄。一個基本的目標(biāo)就是，網(wǎng)絡(luò)（代碼）本身就可以形成一個良性的生態(tài)居灯，獎優(yōu)罰劣祭务，形成一個高質(zhì)量的網(wǎng)絡(luò)。其首要任務(wù)就是防攻擊（防欺騙）怪嫌。在Filecoin的白皮書中提到了三種攻擊方式：女巫攻擊待牵、生成攻擊和外包攻擊。對這些攻擊的定義這里不展開喇勋，需要提到的是缨该，所謂的防攻擊，也就是要讓欺騙者現(xiàn)行川背，讓誠實者獲得利益贰拿。
從存儲的角度來理解蛤袒，很簡單，這個網(wǎng)絡(luò)需要防止存儲提供者作假膨更，也就是要保證：1）不能虛報存儲空間妙真；2）不能虛報存儲的數(shù)據(jù)或存儲份數(shù)；3）不能虛報存儲相應(yīng)數(shù)據(jù)的時間周期荚守。如果網(wǎng)絡(luò)（代碼）本身能夠防止這些欺騙珍德，那么，就不需要一個企業(yè)或機(jī)構(gòu)來背書或仲裁矗漾。網(wǎng)絡(luò)的生態(tài)形成了锈候。
2. Filecoin 相關(guān)的存儲證明
具體在Filecoin的實現(xiàn)之中，大致可以劃分為兩個部分：PoRep（Proof of Replication敞贡，復(fù)制證明）和 PoSt（Proof of Spacetime泵琳，時空證明）。還有數(shù)據(jù)片段證明和可檢索證明誊役。
Proof of Replication: 復(fù)制證明获列，證明數(shù)據(jù)的的一個單獨(dú)的拷貝已經(jīng)在一個特定的扇區(qū)內(nèi)創(chuàng)建成功。復(fù)制證明由封踊坠浮（****Seal****）操作完成击孩，封印操作創(chuàng)建一份數(shù)據(jù)的拷貝，并產(chǎn)生相應(yīng)的復(fù)制證明
Proof of Space-Time：時空證明鹏漆， 證明一定數(shù)量的已封印的扇區(qū)在一定的時間范圍內(nèi)存在于指定的存儲空間之中 — 而不是證明者臨時生成的數(shù)據(jù)（這被視為攻擊）
Piece Inclusion Proof：數(shù)據(jù)片段包含證明溯壶，證明一個給定的數(shù)據(jù)片段存在于一個已封印的扇區(qū)之中
Proof of Retrievability：可檢索證明，一種默克樹證明甫男，用來表明一個給定的葉節(jié)點(diǎn)存在于一個已封印的扇區(qū)內(nèi)
Filecoin的時空證明是與復(fù)制證明算法緊密相關(guān)的。從實現(xiàn)的角度而言验烧，實際上是一起實現(xiàn)的板驳。協(xié)議實驗室在前人研究的基礎(chǔ)上進(jìn)行了創(chuàng)新，組合了兩種（圖）算法碍拆，實現(xiàn)了更嚴(yán)格的證明和更高效的驗證若治，這種算法就叫做** Zigzag，目前最高效感混，最嚴(yán)格的存儲證明算法**端幼。
Zigzag: 當(dāng)前最高效，最嚴(yán)格的存儲證明算法
是兩種（圖）算法的組合 - 實現(xiàn)了更嚴(yán)格的證明和更高效的解封
- Depth Robust Graph
- Expander Graph
僅使用其中任何一種弧满，都不能達(dá)到此目的
3. 存儲證明和驗證流程
要做好存儲證明婆跑，整個過程分為幾個主要階段，包括：初始化（僅執(zhí)行一次）庭呜，數(shù)據(jù)預(yù)處理（對每一片數(shù)據(jù)進(jìn)行）滑进，生成復(fù)制數(shù)據(jù)（對每片數(shù)據(jù)進(jìn)行）犀忱，復(fù)制證明（每個節(jié)點(diǎn)周期性進(jìn)行），數(shù)據(jù)還原（當(dāng)有檢索的時候進(jìn)行）扶关，挑戰(zhàn)隨機(jī)數(shù)生成（需要驗證時進(jìn)行）阴汇，復(fù)制證明，復(fù)制驗證节槐。
理論上講搀庶，就是對應(yīng)以下7個步驟：
- PoRep.Setup(λ,T) → pp ：初始化階段，每個節(jié)點(diǎn)執(zhí)行铜异，產(chǎn)生公共參數(shù)pp（每個節(jié)點(diǎn)一樣）哥倔，security parameter λ, time parameter T (挑戰(zhàn)響應(yīng)時間)
- PoRep.Preproc(sk, D) → D ? , τD ：預(yù)處理過程，節(jié)點(diǎn)自己完成熙掺。sk, 秘鑰未斑，D要處理的數(shù)據(jù)；產(chǎn)生币绩，處理后的數(shù)據(jù)D ? 和數(shù)據(jù)標(biāo)識τD ：數(shù)據(jù)標(biāo)識需要發(fā)送給驗證方蜡秽，也即網(wǎng)絡(luò)。
- PoRep.Replicate(id, τD , D ? ) → R, aux ：產(chǎn)生復(fù)制數(shù)據(jù)缆镣。id為復(fù)制數(shù)據(jù)序號芽突，在節(jié)點(diǎn)上執(zhí)行，產(chǎn)生復(fù)制數(shù)據(jù)R董瞻，aux是附加信息寞蚌，在做證明和驗證的時候要用到
- PoRep.Extract(pp, id, R) → D ? ：從復(fù)制數(shù)據(jù)還原成原數(shù)據(jù)（預(yù)處理過的原數(shù)據(jù)）
- PoRep.Prove(R, aux, id, r) → π ：復(fù)制證明，輸入分別為钠糊，復(fù)制數(shù)據(jù)及其附加信息挟秤，序號，加上挑戰(zhàn)信息（一個由驗證者產(chǎn)生的隨機(jī)數(shù)）抄伍，生成證明 π
- PoRep.Poll(aux) → r ：產(chǎn)生挑戰(zhàn)信息艘刚，輸入：復(fù)制數(shù)據(jù)的附加信息。
- PoRep.Verify(id, τD, r, aux, π) → {0,1} ：驗證證明是否有效截珍，輸入包括：復(fù)制數(shù)據(jù)序號攀甚，原數(shù)據(jù)標(biāo)識，挑戰(zhàn)隨機(jī)數(shù)岗喉，復(fù)制附加信息秋度，驗證信息。所有這些都需要傳送給網(wǎng)絡(luò)進(jìn)行驗證钱床。驗證只有通過或不通過兩種狀態(tài)荚斯。
注意：這里似乎并沒有提到時空證明，其實，時空證明包含著復(fù)制證明和驗證之中鲸拥。這是因為系統(tǒng)周期性地發(fā)送挑戰(zhàn)信息給每個節(jié)點(diǎn)拐格，而每個節(jié)點(diǎn)都需要證明在一定的期間之內(nèi)能夠完成數(shù)據(jù)存儲的驗證，通過持續(xù)的證明和驗證刑赶，就完成了時空證明捏浊。
4. 如何防攻擊
要真正做到存儲提供者不能欺騙，設(shè)計出證明和驗證算法并不特別難撞叨。真正難的是金踪，在一個去中心化的世界里這個算法也有效。這里先不說任意人驗證和數(shù)據(jù)擁有者驗證難度上的天壤之別牵敷。單說胡岔，在去中心化的世界里，其實沒有絕對的防止欺騙或攻擊的手段枷餐。
以大家都熟知的比特幣為例靶瘸，為防止雙花（對網(wǎng)絡(luò)的攻擊），PoW提高了其難度毛肋，但不能抵御51%攻擊怨咪。也就是說，機(jī)制的設(shè)計是讓攻擊者付出極高的成本润匙，太不劃算而不去做诗眨。
Filecoin的存儲證明也是一樣，沒有絕對的安全孕讳，所設(shè)計的算法只是提高欺騙（攻擊）的成本匠楚。那Filecoin存儲證明的一個基本原則就是：讓欺騙者付出比誠實者高得多的成本，那還不如做一個誠實節(jié)點(diǎn)厂财，賺更多的錢芋簿。根據(jù)前文所述，欺騙者的一個主要手段就是在沒有存儲數(shù)據(jù)的情況謊報存儲而獲取利益璃饱。存儲證明不能避免這種情況發(fā)生与斤。但是整個協(xié)議的設(shè)計是：上節(jié)的7個步驟中的第3步（生成復(fù)制數(shù)據(jù)）比較復(fù)雜，需要較長的時間和運(yùn)算帜平，而第5步要求很快。那么當(dāng)一個存儲提供方梅鹦，在沒有保存第3步產(chǎn)生的數(shù)據(jù)的情況下裆甩，要證明自己（第5步），就必須臨時做第3步齐唆，者需要消耗大量的計算嗤栓，需要非常高的系統(tǒng)配置才來得及，否則就會超時被判存儲證明失敗。去大大提高系統(tǒng)的配置茉帅，還不如加一點(diǎn)存儲老老實實做簡單得多叨叙。
5. Filecoin 存儲證明的實現(xiàn)
Filecoin 所有證明的真正實現(xiàn)擂错，都是在 rust-fil-proofs 項目中用 rust 語言編寫的。采用 rust 的一個重要原因是 rust 具有與 c/c++ 相當(dāng)?shù)母咝杂８颍瑫r其語言設(shè)計又大大提高了安全性钮呀，在內(nèi)存分配和管理方面強(qiáng)大得多。
rust-fil-proofs 代碼請參見：https://github.com/filecoin-project/rust-fil-proofs. 其與Filecoin證明相關(guān)的 API 定義在 filecoin-proofs/src/api/ 目錄之下昨凡。其中：
驗證相關(guān)的接口爽醋，就定義在 filecoin-proofs/src/api/ 目錄中；而與復(fù)制證明相關(guān)的接口便脊，則定義在 filecoin-proofs/src/api/sector_builder/helper/ 目錄中蚂四，這些接口包括：
- add_piece: 往一個sector 里面填充內(nèi)容
- seal: 封印，即通過密碼運(yùn)算產(chǎn)生一個可證明的復(fù)制哪痰，當(dāng)產(chǎn)生之后遂赠，原數(shù)據(jù)可刪除
- retrieve_piece: 獲取用戶數(shù)據(jù)，包括unseal
rust-fil-proofs 是一個獨(dú)立的項目妒御，F(xiàn)ilecoin 的Go語言實現(xiàn)（目前唯一的一種實現(xiàn)）通過 CGo 來調(diào)用 rust-fil-proofs函數(shù)解愤。其中接口定義在 https://github.com/filecoin-project/go-filecoin/blob/master/proofs/sectorbuilder/interface.go;
更多信息，參見rust-fil-proofs Readme文件乎莉，以下列出了與Filecoin API相關(guān)部分送讲。
Sector Base API:
…/rust-fil-proofs/target/doc/sector_base/api/index.htmlFilecoin Proofs API:
…/rust-fil-proofs/target/doc/filecoin_proofs/api/index.htmlfilecoin-proofs 扇區(qū)構(gòu)建相關(guān)API的Go語言實現(xiàn)
-- 相關(guān)的接口結(jié)構(gòu)定義filecoin-proofs 驗證相關(guān) API的 Go語言實現(xiàn)
-- 相關(guān)的接口結(jié)果定義
參考
Tight Proofs of Space and Replication , Ben Fisch
https://github.com/filecoin-project/specs/blob/master/proofs.md
https://github.com/filecoin-project/go-filecoin/blob/master/proofs/interface.go
