*本系列文章镇辉，是鏈博核心區(qū)塊鏈研究小組輸出的高質(zhì)量區(qū)塊鏈研究性文章雕沿，旨在研究和分享底層區(qū)塊鏈技術(shù)的原理解析，新技術(shù)趨勢妖碉，拒絕討論任何token涌庭，行情和投資建議。
上篇文章中《深入?yún)^(qū)塊鏈共識(shí)（一）：PoC概念及起源&BurstCoin沉浮史》中欧宜，我們簡要介紹了基于存儲(chǔ)的共識(shí)PoC(Proof-of-Capacity), 本篇文章中坐榆，我們將以Burst為例，進(jìn)一步深入講解PoC的數(shù)學(xué)基礎(chǔ)以及完整的算法過程冗茸。
熟悉Bitcoin歷史的朋友可能知道席镀，PoW(Proof of Work)的概念和思想雛形并非由中本聰發(fā)明，而是早在2001年夏漱，就由Dwork and Naor[10]提出豪诲。
其核心思想在于，通過一種對(duì)CPU運(yùn)算資源上“證明者(Prover)低效挂绰，驗(yàn)證者(Verifier)高效”的算法屎篱，達(dá)到證明者向驗(yàn)證者證明其對(duì)特定量的計(jì)算資源的投入的目的。
算法被運(yùn)用于增加垃圾郵件發(fā)送者的發(fā)送開銷葵蒂，以此防止垃圾郵件交播。
同樣的，對(duì)于存儲(chǔ)資源來說践付，在分布式存儲(chǔ)領(lǐng)域秦士，文件擁有者與文件請(qǐng)求者之間，同樣存在驗(yàn)證與被驗(yàn)證的關(guān)系永高。
[11],[12],[13]幾篇論文都構(gòu)建了一系列證明被驗(yàn)證者擁有某種存儲(chǔ)資源的交互式算法隧土。
PoC(Proof-of-Capacity)其背后的核心理念，便是在存儲(chǔ)資源上乏梁，"證明者(Prover)低效次洼，驗(yàn)證者(Verifier)高效"，以達(dá)到驗(yàn)證者可以花費(fèi)很少的存儲(chǔ)資源遇骑，在較少的計(jì)算時(shí)間內(nèi)卖毁，驗(yàn)證證明者(Prover)擁有一定存儲(chǔ)空間的目的。
Stefan Dziembowski[14]是第一個(gè)將存儲(chǔ)量證明(proofs of storage, proofs ofretrievability或者proof of capacity等類似概念，思想都是基于存儲(chǔ)證明)引入?yún)^(qū)塊鏈系統(tǒng)的人亥啦，并完成了給出完整形式化證明的論文工作炭剪。
本篇我們將簡單回顧其基于數(shù)學(xué)模型的系統(tǒng)設(shè)計(jì)，同時(shí)在下篇文章翔脱，我們以Burst為例奴拦，探討其在實(shí)際系統(tǒng)中的工程實(shí)現(xiàn)。(值得注意的是届吁，雖然paper的內(nèi)容正是BurstCoin中的共識(shí)思想错妖，但時(shí)間上Burst第一個(gè)release版本在這一篇paper的發(fā)表之前，其中的人物和Burst的淵源沒有公開資料披露疚沐，我們亦不得而知)
在PoC共識(shí)中的最關(guān)鍵的一個(gè)問題暂氯，即證明者(Bob代指)如何向驗(yàn)證者(Alice代指)證明，其擁有某個(gè)特定文件大小的文件F始終存在于Bob的磁盤之中亮蛔。
一個(gè)最簡單直觀的方式痴施，我們可能會(huì)想到Alice在事先將F發(fā)送給Bob，其后Bob在需要證明時(shí)返回同樣的文件F究流。
如下圖所示辣吃，Alice接受到文件后，校驗(yàn)其是否與之前發(fā)送給Bob的文件一致芬探。但這樣做顯然違背了"對(duì)存儲(chǔ)資源神得，驗(yàn)證高效"的特性。
同時(shí)偷仿，在P2P網(wǎng)絡(luò)中循头，利用有限的帶寬發(fā)送PoC共識(shí)需要的大容量文件顯然也是不現(xiàn)實(shí)的。
所以炎疆，我們需要設(shè)計(jì)一種對(duì)存儲(chǔ)資源和網(wǎng)絡(luò)資源來說都高效的算法，以達(dá)到"校驗(yàn)高效"的目的国裳。
在PoC的范疇內(nèi)形入，文件F的目的只是為證明Prover確實(shí)使用了一定量存儲(chǔ)空間的工具，也即我們可以對(duì)文件F的內(nèi)容做任何形式的要求(可以聯(lián)想PoW中的CPU計(jì)算過程本身缝左，并不與任何特定非區(qū)塊鏈應(yīng)用相關(guān))亿遂。
在Stefan Dziembowski提出的PoC算法中，文件的內(nèi)容是一種有向無環(huán)圖(Directed Acyclic Graph,DAG)結(jié)構(gòu), 以V代表圖中所有節(jié)點(diǎn)渺杉，定義W(V), 要求其滿足一個(gè)特性W(V)=Hash(V, W(V')), 其中V'為V在圖中的直接前驅(qū)節(jié)點(diǎn)蛇数。
如上圖所示，圖中簡單解釋了有向無環(huán)圖結(jié)構(gòu)是越，其每個(gè)節(jié)點(diǎn)的W值都是經(jīng)過一次hash計(jì)算的長二進(jìn)制串耳舅。
Prover需要將每個(gè)節(jié)點(diǎn)的W值存儲(chǔ)，以供Verifier在驗(yàn)證階段隨機(jī)抽取檢驗(yàn)。Prover與Verifier的交互流程如下：
- 初始階段：
- Verifier與Prover協(xié)商復(fù)雜有向無環(huán)圖G浦徊，同時(shí)Prover計(jì)算所有W(V)馏予，并存儲(chǔ)計(jì)算結(jié)果(此步驟需要的計(jì)算時(shí)間與存儲(chǔ)空間，和圖的節(jié)點(diǎn)數(shù)目成正比盔性。)
- Prover 將所有W(V)的值組成默克爾樹(Merkle Tree)霞丧，同時(shí)將樹根節(jié)點(diǎn)的值Φ發(fā)送給Verifier
- 驗(yàn)證階段：
- Verfier隨機(jī)抽取節(jié)點(diǎn)V，要求Prover給出其W(V)的值冕香，同時(shí)揭示其在Merkle Tree中的路徑
- Prover提取其存儲(chǔ)中的特定W(V)蛹尝，同時(shí)揭示其在Merkle Tree中的路徑
- Verfier驗(yàn)證其W(V)的合法性，同時(shí)驗(yàn)證其是否存在以Φ為根的Merkle樹中
在初始階段悉尾，類似PoW算法中利用hash達(dá)到證明CPU的使用量突那，PoC在初始階段要求誠實(shí)的Prover存儲(chǔ)每個(gè)按照?qǐng)D結(jié)構(gòu)計(jì)算出的節(jié)點(diǎn)hash值。
由于在實(shí)際應(yīng)用中焕襟，圖節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)比上圖要多, 同時(shí)圖的連接關(guān)系也比上圖更加復(fù)雜陨收，考慮到最有可能的Prover作弊的情況是，Prover在初始階段不使用大量的存儲(chǔ)將Hash運(yùn)算后的結(jié)果存儲(chǔ)在磁盤上鸵赖，而是在驗(yàn)證階段重新使用CPU資源進(jìn)行Hash的運(yùn)算务漩。
這樣的以“時(shí)間換空間”的作弊行為顯然是行不通的，因?yàn)樵谟邢薜尿?yàn)證時(shí)間內(nèi)它褪，投入巨大的運(yùn)算資源重新計(jì)算每個(gè)節(jié)點(diǎn)的Hash值饵骨，既是不經(jīng)濟(jì)的，更是不現(xiàn)實(shí)的茫打。
論文中選取 Random Bipartite Graphs 與 Superconcentrator Graphs 兩類特定類型的DAG居触，兩類圖形的數(shù)學(xué)特性保證了節(jié)點(diǎn)間的連接關(guān)系的高度復(fù)雜性。
通過建立的 Pebble Game 模型老赤，證明一個(gè)不誠實(shí)的Prover如果不存儲(chǔ)與圖節(jié)點(diǎn)相同數(shù)量的Hash值時(shí)轮洋，在常數(shù)有限時(shí)間內(nèi)，不可能正確的通過驗(yàn)證者的驗(yàn)證[14]抬旺。
上述兩階段交互既是論文中提到的PoC算法的核心弊予。
細(xì)心的讀者可能會(huì)注意到在初始階段的b與驗(yàn)證階段的b,c兩個(gè)步驟中，涉及到關(guān)于Merkle Tree的計(jì)算和驗(yàn)證开财，此處的核心思想在于利用Merkle Tree的性質(zhì)汉柒，簡化驗(yàn)證者的驗(yàn)證復(fù)雜度，從而達(dá)到對(duì)驗(yàn)證者來說"驗(yàn)證高效"的目的责鳍。
如上圖所示碾褂，Prover將每個(gè)節(jié)點(diǎn)的W值作為merkle樹的葉子節(jié)點(diǎn)，計(jì)算出merkle樹的樹根历葛，作為參數(shù)之一正塌，在初始節(jié)點(diǎn)發(fā)送給Verifier。
在驗(yàn)證階段，Verifier只需要驗(yàn)證某個(gè)節(jié)點(diǎn)的W值是否存在在第一步初始階段發(fā)送的Merkle樹中即可传货。
其算法流程與區(qū)塊鏈系統(tǒng)中常見的輕錢包驗(yàn)證交易完全相同屎鳍，使驗(yàn)證工作的復(fù)雜度大大降低。
綜上所述问裕，我們解讀了PoC領(lǐng)域的第一篇Paper的工作逮壁，主要集中在其理念，算法的構(gòu)建粮宛。
具體的模型細(xì)節(jié)和證明細(xì)節(jié)有興趣的讀者可以參考Stefan Dziembowski[14]論文獲取更多窥淆。
BurstCoin則是在工程角度實(shí)際運(yùn)行的PoC完備系統(tǒng)。兩者在理念上是完全一致的巍杈，但Burst在實(shí)現(xiàn)細(xì)節(jié)上卻與該論文提出的模型和交互不完全相同忧饭。
下一篇文章我們將重點(diǎn)介紹BurstCoin的PoC共識(shí)過程，同時(shí)在末尾結(jié)合StefanDziembowski的模型討論Burst是否可以納入其框架之下和一些思考的分享筷畦。
鏈博科技區(qū)塊鏈系列文章词裤，致力于分享區(qū)塊鏈領(lǐng)域的底層技術(shù)知識(shí)，努力提供原創(chuàng)鳖宾，有深度的技術(shù)內(nèi)容吼砂。
從技術(shù)角度探索區(qū)塊鏈創(chuàng)新的同時(shí)，鏈博科技也從產(chǎn)業(yè)結(jié)合角度深入思考鼎文，推進(jìn)區(qū)塊鏈落地項(xiàng)目的建設(shè)渔肩，為企業(yè)提供專業(yè)、易用拇惋、全棧的區(qū)塊鏈鏈改服務(wù)周偎。
歡迎關(guān)注我們的往期文章，也歡迎在文章評(píng)論區(qū)留下你們的觀點(diǎn)和想法撑帖。
參考源
- [1.]Spacemint:A Cryptocurrency Based on Proofs of Space
- [2.]BHD whitepaper
- [3.]BurstCoin Introduction Serious
- [4.]Proof of Space
- [5.]Burstcoinist
- [6.]Proof of Space from Stacked Expanders
- [7.]The Burst Dymaxion
- [8.]burstforum
- [9.]mining tutorials
- [10.] Cynthia DworkMoni Naor,Pricing via Processing or Combatting Junk Mail
- [11.] Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, LeaKissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession atuntrusted stores. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F.Syverson, editors, ACM CCS 07, pages 598–609. ACM Press, October 2007
- [12.] Kevin D. Bowers, Ari Juels, and Alina Oprea. Proofs of retrievability: theoryand implementation. In CCSW, pages 43–54, 2009
- [13.] Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secureerasure. In Security and Cryptography for Networks - 9th InternationalConference, SCN 2014, Amalfi, Italy, September 3-5, 2014. Proceedings, pages520–537, 2014]
- [14.] Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs ofspace. Lecture Notes in Computer Science (Including Subseries Lecture Notesin Artificial Intelligence and Lecture Notes in Bioinformatics), 9216(616160),585–605.
- [15]Bitcoin White Paper
