*本系列文章卷拘，是鏈博核心區(qū)塊鏈研究小組輸出的高質(zhì)量區(qū)塊鏈研究性文章仰禽，旨在研究和分享底層區(qū)塊鏈技術(shù)的原理解析氮墨，新技術(shù)趨勢(shì)，拒絕討論任何token吐葵，行情和投資建議规揪。
上篇文章中《深入?yún)^(qū)塊鏈共識(shí)（一）：PoC概念及起源&BurstCoin沉浮史》中，我們簡(jiǎn)要介紹了基于存儲(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 of retrievability或者proof of capacity等類似概念，思想都是基于存儲(chǔ)證明)引入?yún)^(qū)塊鏈系統(tǒng)的人对省，并完成了給出完整形式化證明的論文工作蝗拿。
本篇我們將簡(jiǎn)單回顧其基于數(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è)最簡(jiǎn)單直觀的方式辛慰，我們可能會(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)。
如上圖所示掘鄙，圖中簡(jiǎ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ì)银酗，簡(jiǎn)化驗(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é)合Stefan Dziembowski的模型討論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, Lea Kissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession at untrusted 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: theory and implementation. In CCSW, pages 43–54, 2009
[13.] Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secure erasure. In Security and Cryptography for Networks - 9th International Conference, SCN 2014, Amalfi, Italy, September 3-5, 2014. Proceedings, pages 520–537, 2014]
[14.] Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs of space. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9216(616160), 585–605.
[15]Bitcoin White Paper
