怎么证明建立了存储过程_【Filecoin源码仓库全解析】第七章:了解PoRep与PoSt并参与复制证明游戏
歡迎大家來到第七章,經(jīng)過前章《【Filecoin源碼倉庫全解析】第六章:如何單機部署多節(jié)點集群及礦池設(shè)計思路》的介紹,我們分享了如何在單機部署多節(jié)點集群的知識以及礦池設(shè)計的一些思路。
我們將在本章介紹目前Filecoin工程實現(xiàn)中所采用的復(fù)制證明(PoRep)方式與時空證明(PoSt)方式,以及如何參與協(xié)議實驗室發(fā)起的復(fù)制證明游戲(Replication-Game)。
一、Filecoin所設(shè)計的證明類型
Filecoin是一個利用區(qū)塊鏈技術(shù)來實現(xiàn)的去中心化存儲系統(tǒng),我們都知道,在一個區(qū)塊鏈系統(tǒng)中,需要保證每個節(jié)點公平有序地按照規(guī)則自行運轉(zhuǎn),能抵制惡意攻擊,確保整個體系的可信安全。
為此,Filecoin體系下也需要一個嚴(yán)謹(jǐn)?shù)淖C明手段來確保礦工不會在沒有存儲數(shù)據(jù)的情況下謊稱自己存儲了用戶的數(shù)據(jù),需要礦工憑借他們的存儲能力爭奪出塊資格。
Filecoin系統(tǒng)中的證明算法最初源于存儲證明(PoS)、數(shù)據(jù)持有性證(PDP)和可檢索證明(PoRet),后面逐漸迭代、增強約束條件,才完善為如今工程中所采用的復(fù)制證明(PoRep)與時空證明(PoSt),這里分別詳細(xì)介紹一下它們的含義:
- 存儲證明(Proof-of-Storage, PoS):為存儲空間提供的證明機制。
- 數(shù)據(jù)持有性證明(Provable Data Possession ,PDP):用戶發(fā)送數(shù)據(jù)給礦工進(jìn)行存儲,礦工證明數(shù)據(jù)已經(jīng)被自己存儲,用戶可以重復(fù)檢查礦工是否還在存儲自己的數(shù)據(jù)。
- 可檢索證明(Proof-of-Retrievability,PoRet):和PDP過程比較類似,證明礦工存儲的數(shù)據(jù)是可以用來查詢的。
- 復(fù)制證明(Proof-of-Replication,PoRep):存儲證明PoS的一個實際方案,用以證明數(shù)據(jù)被礦工獨立地保存,可以防止女巫攻擊,外源攻擊和生成攻擊。
- 空間證明(Proof-of-Space,PoSpace):存儲量的證明,PoSpace是PoW的一種,不同的是PoW使用的計算資源,而PoSpace使用的是存儲資源。
- 時空證明(Proof-of-Spacetime,PoSt):證明在一段時間內(nèi),礦工在自己的存儲設(shè)備上實際的存儲了特定的數(shù)據(jù)。
如下圖所示,這6種證明的定義并不是互斥獨立的,PoS包括PDP, PoRet, PoRep, PoSpace;而PoRep和PoSt是PoSpace的兩種實例,他們之間的定義相互有交叉:
復(fù)制證明和時空證明的實現(xiàn)方式?jīng)Q定了 Filecoin 礦機的配置。間接決定 Filecoin 系統(tǒng)的整體成本。Filecoin 提供了存儲和數(shù)據(jù)下載服務(wù)兩種服務(wù),系統(tǒng)成本最終決定用戶的使用成本。
如果復(fù)制證明和時空證明消耗的資源過多,那么會系統(tǒng)性的提升整個 Filecoin 成本,這會讓 Filecoin 系統(tǒng)的價值大打折扣。
目前所開源的第一版go-filecoin0.1.x系列所采用的是ZigZagDrg和StackedDrg的VDF方式來作為PoRep的實現(xiàn),官方對此認(rèn)為仍有改進(jìn)空間,協(xié)議實驗室也為此設(shè)立了RFPs基金,專門研究該課題,而復(fù)制游戲的誕生也是為了更好地讓社區(qū)愛好者提前參與測試和協(xié)助官方優(yōu)化這個部分。
二、復(fù)制證明PoRep
2.1 PoRep職能
PoRep算法的職能是用來證明一個存儲系統(tǒng)確實存儲了某一份數(shù)據(jù)的拷貝,而且每一份拷貝使用不同的物理存儲,并用來抵御去中心化系統(tǒng)中三種常見的攻擊:
2.2 PoRep本質(zhì)
PoRep本質(zhì)是一個加密時間長,解密時間短且證明與驗證過程高效的算法, 這個過程在學(xué)術(shù)圈,被稱為可驗證時延加密(Verifiable Time-Delay Encoding Function):
如上圖,我們假設(shè)這一加密算法的驗證時長是一倍,解密時間大約2-5倍,挑戰(zhàn)有效時間算作10倍,那么這一加密時間大約要1000倍才能在概率上達(dá)到99.9%的相對安全。
2.3 挑戰(zhàn)及證明模型
Filecoin證明機制的角色和過程可以抽象成如下,挑戰(zhàn)者、證明者、檢驗者。他們可以是礦工、用戶或者任何網(wǎng)絡(luò)內(nèi)其他角色。涉及的定義包括如下:
- 挑戰(zhàn)(challenge):系統(tǒng)對礦工發(fā)起提問,可能是一個問題或者一系列問題,礦工正確的答復(fù),則挑戰(zhàn)成功,否則失敗。
- 證明者(prover):一般只礦工。向系統(tǒng)提供證明了完成系統(tǒng)發(fā)起的挑戰(zhàn)。
- 檢驗者(verifier):向礦工發(fā)起挑戰(zhàn)(challenge)一方,來檢測是否礦工完成了數(shù)據(jù)存儲任務(wù)。
- 數(shù)據(jù)(data):用戶向礦工提交的需要存儲或者礦工已經(jīng)存儲的數(shù)據(jù)。
- 證明(proof):礦工完成挑戰(zhàn)(challenge)時候的回答。
如上圖,驗證過程可以表述為: 驗證者會按照一定的規(guī)則向礦工提起挑戰(zhàn),挑戰(zhàn)是隨機生成的,礦工不能提前獲知。礦工作為證明者相應(yīng)向檢驗者提交證明,證明的生成需要原始數(shù)據(jù)與隨機挑戰(zhàn)信息。證明生成后,證明者會交給驗證者,并由驗證者判定該證明是否有效,如果有效,則挑戰(zhàn)成功。
2.4 可驗證時延加密函數(shù)(VDF)
對于VDF,Filecoin最初受到了類似Cipher Block Chaining 分組塊加密鏈的啟發(fā),從而改進(jìn)和優(yōu)化屬于自己的VDF方式。
我們先看一下CBC的原理:大文件分塊成 d1-d4…
除了c1初始化向量比較特殊,后續(xù)所有文件塊編碼都需要做XOR運算和AES加密,例如c2由c1與d2共同生成,以此類推。這樣在編碼過程就無法并行,從而速度變慢。
再看右邊的過程,是對CBC算法的進(jìn)一步優(yōu)化,采用的深度魯棒鏈(Depth Robust Chaining),在分塊上使用了有向無環(huán)圖來做,進(jìn)一步壓縮了解碼驗證的復(fù)雜度,也提高了隨機性。
Filecoin目前工程上的實現(xiàn)是基于前面兩個算法的改進(jìn)版:ZigZagDRG算法 ,如下圖所示:
原始數(shù)據(jù)data首先依次分成一個個小數(shù)據(jù)(d1-d5),每個小數(shù)據(jù)將被計算出一個散列值(32個字節(jié)),小數(shù)據(jù)本身也將散列值作為加密種子來進(jìn)行編解碼。這些小數(shù)據(jù)的散列值按照DRG(Depth Robust Graph)建立連接關(guān)系。
數(shù)據(jù)塊的散列關(guān)系將構(gòu)成Merkle Tree結(jié)構(gòu)(類MySql數(shù)據(jù)庫的索引使用B+樹實現(xiàn))。
這樣是為了在進(jìn)行挑戰(zhàn)與檢驗的時候,無需針對所有數(shù)據(jù)塊解碼,即可以快速驗證,也更好地抵御了攻擊性。
例如:樹根即為副本的哈希,系統(tǒng)或者用戶隨機發(fā)起挑戰(zhàn),位置d5,礦工只需計算d5到根節(jié)點root的路徑,輸出一個證明給發(fā)起挑戰(zhàn)的驗證節(jié)點。
至于VDF中每個數(shù)據(jù)塊的單元加密,如下圖所示,應(yīng)用到了BLS12-381來進(jìn)行單元編碼與解碼:
(源碼路徑:https://github.com/filecoin-project/rust-fil-proofs/blob/41d7fe97b2d98e79eaf52959590a86c4d1749843/storage-proofs/src/vdf_sloth.rs)
BLS12-381是一種Zcash中所用的新型zk-SNARK 橢圓曲線的構(gòu)造加密算法,隸屬于Bellman庫,由Rust語言所實現(xiàn),它的特點是小巧易用,能快速驗證。Bellman的目標(biāo)是讓普通程序員更加簡單地使用zk-SNARKs。
散列函數(shù)由于需要適應(yīng)于SNARKS,目前沿用了Zcash中的Pedersen(Blake2、SHA256也在做實現(xiàn)和選擇):
整個PoRep的計算過程分為若干層 (目前在Filecoin中設(shè)置為4層,在復(fù)制游戲項目中設(shè)置為10層) ,每一層的DRG關(guān)系的箭頭方向是互斥的,上一層向右,下一層就向左,因此得名ZigZag(Z字型),數(shù)據(jù)解碼過程中,每一層之間互不依賴,即可并行執(zhí)行,相對于串行編碼要更為快速。
綜上,這樣就實現(xiàn)了PoRep的本質(zhì):編碼快,而解碼和驗證證明快的效果,從而防范各種攻擊。
三、時空證明PoSt
如圖所示,PoSt可以理解為礦工一定時間內(nèi)持續(xù)地生成復(fù)制證明和接受挑戰(zhàn)和驗證的過程,并通過這個過程,更新全網(wǎng)存儲算力。
挑戰(zhàn)者在PoRep循環(huán)重復(fù)執(zhí)行的i輪,輸入一個隨機挑戰(zhàn)參數(shù)c,之后,挑戰(zhàn)參數(shù)C會被鏈?zhǔn)竭f歸計算,即上一次的輸出作為下一次的輸入,直到T時間內(nèi),最后一次的結(jié)果作為PoSt的證明,接受反向驗證。
很明顯,不正當(dāng)?shù)牡V工如果沒有老老實實執(zhí)行PoSt,是無法反推出C的。
如下圖所示,目前,go-filecoin中所定義的閾值是:每隔20000個區(qū)塊(平均6天左右),存儲礦工必須提供一次PoSt(Proof of Space Time)的證明,表明仍存有用戶數(shù)據(jù)的證明。與此同時,存儲市場(上帝)會每隔100個區(qū)塊(平均50分鐘),去對PoSt發(fā)起證明驗證,以判斷是否需要下發(fā)懲罰。
(源碼路徑:https://github.com/filecoin-project/go-filecoin/blob/a45c0f1a70c2e8a61d6d5b4e01e641bedb344a06/actor/builtin/miner/miner.go)
四、Filecoin Proving Subsystem(FPS)
Filecoin Proving Subsystem(FPS)是Filecoin體系中所有證明算法的工程實現(xiàn),由于底層依賴Bellman庫的原因,完全由Rust編寫,源碼倉庫地址:https://github.com/filecoin-project/rust-fil-proofs
FPS在設(shè)計之時,十分注重解耦性:filecoin-proofs實現(xiàn)了為go-filecoin提供存儲證明的接口,并依賴其他兩個模塊:storage-proofs(存儲證明生成與驗證的模塊)和 sector-base (扇區(qū)控制模塊)。
這兩個模塊又依賴于storage-backend中間件實現(xiàn)存儲控制和消息轉(zhuǎn)發(fā)。
關(guān)于FPS的其他細(xì)節(jié)導(dǎo)讀,這里推薦李星前輩的一篇文章: - 星想法:Filecoin - PoRep和PoSt算法源代碼導(dǎo)讀
之后,可以配合官方的rust-fil-proofs源碼倉庫進(jìn)行閱讀和獲取最新的變動:
- github:rust-fil-proofs
關(guān)于PoRep和PoSt的推演論證過程,想深入了解的童靴可以對照這兩篇論文進(jìn)行剖析: - PoReps: Proofs of Space on Useful Data - Ben Fisch:Tight Proofs of Space and Replication
五、參與復(fù)制證明游戲
復(fù)制游戲是一項復(fù)制競賽,參與者挑戰(zhàn) Filecoin 官方提供的默認(rèn)的復(fù)制證明算法(前文提到的VDF),看是否能夠提供更優(yōu)(相對于默認(rèn)算法)的算法或執(zhí)行結(jié)果。
參與游戲的方法是:通過當(dāng)前 Filecoin 提供的復(fù)制算法(運行或重構(gòu)FPS),并將執(zhí)行結(jié)果發(fā)送到 Filecoin 服務(wù)器。
5.1 編譯游戲客戶端
如下準(zhǔn)備環(huán)境依賴,小編采用的是linux系統(tǒng),macOS環(huán)境類似,可使用brew包管理工具代替apt。
//安裝Rust curl https://sh.rustup.rs -sSf | sh重啟terminal//切換rust到nightly版 rustup install nightly//若想自行部署游戲服務(wù)端,需安裝PostgreSQL 數(shù)據(jù)庫 brew install postgresql@10apt-get install postgresql//安裝clang和libclang apt-get install clang//安裝pq庫 apt-get install libpq-dev//下載replication-game源碼 git clone https://github.com/filecoin-project/replication-game.gitcd replication-game//執(zhí)行編譯 cargo +nightly build --release --bin replication-game編譯完成后,可在bin/目錄下看到play可執(zhí)行文件:
5.2 啟動游戲
# 啟動指令: # bin/play NAME SIZE TYPE# E.g.# Zigzag 10MiB bin/play NAME 10240 zigzag# Zigzag 1GiB bin/play NAME 1048576 zigzag# DrgPoRep 10MiB bin/play NAME 10240 drgporep# DrgPoRep 1GiB bin/play NAME 1048576 drgporep- NAME: 你的游戲玩家名稱
- SIZE: 你打算要復(fù)制的文件的大小,單位是 KB
- TYPE: 你想要運行的算法名稱(目前可選值有: zigzag 和 drgporep)
Play腳本將自動從游戲服務(wù)器下載種子,復(fù)制數(shù)據(jù),生成證據(jù),然后將該證據(jù)發(fā)布到游戲服務(wù)器。
5.3 發(fā)送游戲結(jié)果至Rank服務(wù)器
Play腳本將通過curl提交游戲結(jié)果:
curl -X POST -H "Content-Type: application/json" -d @./proof.json https://replication-game.herokuapp.com/api/proof我們可以通過訪問Rank頁面:http://replication-game.herokuapp.com/,來查看排行。
小編的機型配置:
- Processor Name: Intel Core i5
- Processor Speed: 3.1 GHz
- Number of Processors: 1
- Total Number of Cores: 2
- L2 Cache (per Core): 256 KB
- L3 Cache: 4 MB
- Memory: 8 GB
Drg復(fù)制證明耗時2.1s/MiB:
ZigZag復(fù)制證明耗時11.2s/MiB:
我們的游戲結(jié)果將記錄在proof.json中,可以手動打開proof.json,分析一下證明的數(shù)據(jù)結(jié)構(gòu):
- prover:驗證人。
- seed:游戲種子,加密Key。
- proof_params:證明配置項。
- proof:證明數(shù)據(jù)塊關(guān)系。
- tau: 一棵或者多棵Merkle樹的樹根都稱為tau,每一層的輸入稱為d(data),每一層的VDE的結(jié)果稱為r(replica)。
- comm_d:每一層的輸入構(gòu)建的默克爾樹根為comm_d。
- comm_r:每一層的輸出構(gòu)建的默克爾樹根為comm_r。
- comm_r_star:每層comm_r的數(shù)據(jù)和replica id數(shù)據(jù)散列計算后的結(jié)果。
通過查閱Proof.json的數(shù)據(jù)結(jié)構(gòu),也可以幫助大家更好地理解2.4所述內(nèi)容。
5.4 如何提升Rank位置?
- 從硬件和軟件方面優(yōu)化:增加硬件配置,更快的 CPU 更大的內(nèi)存(RAM),或者使用其他的替換方案比如使用 FPGA, GPU, ASICs 等更擅長進(jìn)行深度計算的硬件。另外你可以優(yōu)化你操作系統(tǒng)的一些參數(shù)設(shè)置,比如 IO 參數(shù)等。
- 從算法方面優(yōu)化:你可以不使用 Filecoin 給你提供的默認(rèn)實現(xiàn)算法,自己設(shè)計一種新的能夠更快生成存儲證明的算法,比如打破順序假設(shè), 生成存儲更少數(shù)據(jù)的證明,打破 Pedersen 哈希等。
當(dāng)然,光追求Rank數(shù)據(jù)是無意義的,PoRep和PoSt的時延在Filecoin體系下,只是影響存儲效率的一個因子而已,對于礦工來說,需要追求的是綜合性價比。
參考文獻(xiàn)
- https://github.com/filecoin-project/replication-game
- https://z.cash/blog/bellman-zksnarks-in-rust/
往期系列文章回顧:
【Filecoin源碼倉庫全解析】第一章:搭建Filecoin測試節(jié)點 【Filecoin源碼倉庫全解析】第二章:如何創(chuàng)建賬戶錢包并獲取FIL Mock代幣 【Filecoin源碼倉庫全解析】第三章(上):存儲提供方(礦工)的配置操作
【Filecoin源碼倉庫全解析】第三章(下):存儲提供方(礦工)的配置操作
【Filecoin源碼倉庫全解析】第四章:存儲需求方(用戶)的配置操作
【Filecoin源碼倉庫全解析】第五章:檢索市場及檢索礦工
【Filecoin源碼倉庫全解析】第六章:如何單機部署多節(jié)點集群
聯(lián)系作者:
本人從業(yè)經(jīng)驗有限,不免有不足之處,歡迎指正和更多討論,可私信微信公眾號:jialesoho,或者加我微信:daijiale6239,如果覺得對您有幫助,可以幫點擊好看推廣和打賞支持噢,感激不盡!
(識別圖中二維碼,關(guān)注嘉樂SOHO微信公眾號)
總結(jié)
以上是生活随笔為你收集整理的怎么证明建立了存储过程_【Filecoin源码仓库全解析】第七章:了解PoRep与PoSt并参与复制证明游戏的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python大数据开发平台_python
- 下一篇: 酷狗音乐linux版_让父母也爱上音乐