從十年前到今天，比特幣從一個(gè)白皮書(shū)的構(gòu)想逐漸成為全球最大的點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)支付系統(tǒng)之一。隨著比特幣的發(fā)展，區(qū)塊鏈技術(shù)也受到越來(lái)越多的關(guān)注。

其實(shí)，區(qū)塊鏈本質(zhì)上就是一個(gè)分布式的應(yīng)用軟件，而分布式系統(tǒng)首要問(wèn)題就是解決一致性的問(wèn)題，也就是要達(dá)成共識(shí)，所以說(shuō)共識(shí)算法就是區(qū)塊鏈的「靈魂」。從BFT到PoW再到PoS，共識(shí)算法逐漸被被發(fā)明、改進(jìn)和應(yīng)用。今天在區(qū)塊鏈的核心領(lǐng)域——分布式存儲(chǔ)領(lǐng)域，Lambda團(tuán)隊(duì)初步實(shí)現(xiàn)了該領(lǐng)域最為核心的算法，也就是PoST時(shí)空證明算法，并將該算法的核心類庫(kù)部分在GitHub上進(jìn)行開(kāi)源，開(kāi)源協(xié)議遵守GPL V3。

數(shù)據(jù)完整性驗(yàn)證機(jī)制

近些年，云計(jì)算得到廣泛的普及和應(yīng)用，其核心理念就是資源租用、應(yīng)用托管和服務(wù)外包，其通過(guò)虛擬化技術(shù)將分布的計(jì)算節(jié)點(diǎn)組成一個(gè)共享的虛擬化池，為用戶提供服務(wù)。但是當(dāng)用戶選擇將大量應(yīng)用和數(shù)據(jù)部署到云計(jì)算平臺(tái)中時(shí)，云計(jì)算系統(tǒng)也相應(yīng)地變?yōu)樵拼鎯?chǔ)系統(tǒng)，但高度集中的計(jì)算資源使云存儲(chǔ)面臨著嚴(yán)竣的安全挑戰(zhàn)，這也是中心化服務(wù)先天具備的弱點(diǎn)。

此前我們?cè)凇厄v訊云數(shù)據(jù)丟失事件思考：存儲(chǔ)的未來(lái)在哪里？》一文中也提到，中心化的云存儲(chǔ)在安全性、可靠性以及服務(wù)水平層面還存在很多問(wèn)題亟待解決。企業(yè)數(shù)據(jù)放在云存儲(chǔ)中，他們最關(guān)心的是數(shù)據(jù)是否完整無(wú)誤，如果出現(xiàn)故障，是否可以實(shí)現(xiàn)數(shù)據(jù)的恢復(fù)，而且能夠證明這些數(shù)據(jù)與原來(lái)數(shù)據(jù)完全一致。這就是去中心存儲(chǔ)中經(jīng)常提到的「數(shù)據(jù)完整性驗(yàn)證機(jī)制」。

數(shù)據(jù)完整性驗(yàn)證機(jī)制根據(jù)是否對(duì)數(shù)據(jù)文件采用了容錯(cuò)預(yù)處理分為數(shù)據(jù)持有性證明PDP機(jī)制（PDP，Provable Data Possession）和數(shù)據(jù)可恢復(fù)證明POR機(jī)制（POR，Proofs of Retrievability）。PDP機(jī)制能快速判斷遠(yuǎn)程節(jié)點(diǎn)上數(shù)據(jù)是否損壞，更多的是注重效率，而POR機(jī)制不僅能識(shí)別數(shù)據(jù)是否已損壞， 且能恢復(fù)已損壞的數(shù)據(jù)。這兩種機(jī)制有著不同的應(yīng)用需求，PDP機(jī)制主要用于檢測(cè)大數(shù)據(jù)文件的完整性，而POR機(jī)制則用于確保重要數(shù)據(jù)的完整性，以及數(shù)據(jù)丟失之后的可恢復(fù)性。

數(shù)據(jù)持有性證明PDP機(jī)制

首先我們可以看看PDP方案的一個(gè)應(yīng)用場(chǎng)景：

（1）Alice要求Bob記憶一組信息；

（2）Alice本身并不會(huì)記下這組信息；

（3）Alice請(qǐng)Chris來(lái)確認(rèn)Bob是否還記得這組信息；

（4）Chris并不了解這組信息的內(nèi)容。

我們對(duì)這些角色進(jìn)行代換：Alice即是用戶，Bob即為存儲(chǔ)曠工，Chris即為第三方審核者（以下簡(jiǎn)稱TPA）。

驗(yàn)證流程如下：

（1）用戶為待外包的每塊數(shù)據(jù)生成一個(gè)Tag，這個(gè)tag經(jīng)由用戶進(jìn)行簽名；

（2）TPA隨機(jī)對(duì)用戶外包數(shù)據(jù)中一塊發(fā)起Challenge，這個(gè)Challenge中包含有TPA生成的隨機(jī)數(shù)；

（3）存儲(chǔ)曠工根據(jù)被挑戰(zhàn)的數(shù)據(jù)塊內(nèi)容、Tag信息、Challenge信息以及自己生成的一個(gè)隨機(jī)計(jì)算得到一個(gè)Proof；

（4）TPA以challenge、proof及用戶公鑰為參數(shù)，通過(guò)映射函數(shù)e（u，v）雙線性性質(zhì)檢驗(yàn)存儲(chǔ)曠工是否持有數(shù)據(jù)。

PDP的核心公式為：

時(shí)空證明：Proof of Space Time

PoST，全稱是Proof of Space Time，是由FileCoin引入到區(qū)塊鏈領(lǐng)域的概念，「時(shí)空」的定義是衡量并計(jì)算存儲(chǔ)在網(wǎng)絡(luò)中的數(shù)據(jù)存儲(chǔ)時(shí)間及空間。 FileCoin和Lambda都是旨在提供去中心化的分布式存儲(chǔ)，礦工通過(guò)存儲(chǔ)及檢索過(guò)程獲得客戶的付費(fèi)，并通過(guò)時(shí)空證明算法獲得出塊獎(jiǎng)勵(lì)。由于整個(gè)網(wǎng)絡(luò)是沒(méi)有中心化節(jié)點(diǎn)的P2P網(wǎng)絡(luò)，因此需要某種機(jī)制保證用戶所存儲(chǔ)數(shù)據(jù)的完整性和可恢復(fù)性，因此誕生了這個(gè)領(lǐng)域的一些相關(guān)算法。

時(shí)空證明PoST，它可以讓驗(yàn)證者檢查存儲(chǔ)提供商是否在一段時(shí)間內(nèi)存儲(chǔ)了他/她的外包數(shù)據(jù)。這對(duì)提供商的直接要求是：

（1）生成順序的存儲(chǔ)證明來(lái)作為確定時(shí)間的一種方法。

（2）組成遞歸執(zhí)行來(lái)生成簡(jiǎn)單的證明。

其實(shí)，PoST算法是對(duì)POR的一種改進(jìn)，POR算法是由Juels等人在一篇名叫《Proofs of Retrievability For Large Files》的論文中最早進(jìn)行闡述，其核心是將文件分片存儲(chǔ)，并根據(jù)分片的標(biāo)簽信息定期進(jìn)行挑戰(zhàn)和證明。但通常學(xué)術(shù)界所定義的POR的運(yùn)行依賴于中心化第三方節(jié)點(diǎn)，并且每次運(yùn)行都要進(jìn)行預(yù)處理，相對(duì)的SpaceTime（PoST）是一定時(shí)期內(nèi)產(chǎn)生一個(gè)POR序列來(lái)證明有用存儲(chǔ)的保持時(shí)間。

如下圖所示，PoST與PoR的主要區(qū)別在于重復(fù)挑戰(zhàn)的執(zhí)行，而不重新運(yùn)行初始化階段，這就大大提高了執(zhí)行效率。

關(guān)于 IPFS和 FileCoin

現(xiàn)在，區(qū)塊鏈領(lǐng)域的很多人混淆了IPFS和FileCoin項(xiàng)目，以為IPFS項(xiàng)目已經(jīng)解決了存儲(chǔ)數(shù)據(jù)的完整性問(wèn)題，這是一個(gè)誤區(qū)。這些人錯(cuò)誤的認(rèn)為，IPFS對(duì)數(shù)據(jù)進(jìn)行哈希之后，是可以保證數(shù)據(jù)的不可篡改的，這是一個(gè)錯(cuò)誤的認(rèn)識(shí)，對(duì)于任意IPFS網(wǎng)絡(luò)的節(jié)點(diǎn)來(lái)說(shuō)，它們僅僅會(huì)存儲(chǔ)自己感興趣的數(shù)據(jù)，而不是用戶指定的數(shù)據(jù)。因此，需要一個(gè)激勵(lì)和檢查層來(lái)確保用戶指定數(shù)據(jù)的存儲(chǔ)和不被篡改。做一個(gè)簡(jiǎn)單的比較，IPFS是類似于開(kāi)源的Ceph軟件，F(xiàn)ileCoin和Lambda則更類似于AWS的S3。沒(méi)有數(shù)字貨幣激勵(lì)的單純存儲(chǔ)系統(tǒng)，是不可能解決數(shù)據(jù)的持有性問(wèn)題的。

FileCoin關(guān)于時(shí)空證明PoST的定義為：

· 時(shí)空證明PoST方案使得有效的證明人P 能夠說(shuō)服一個(gè)驗(yàn)證者V 相信 P 在一段時(shí)間內(nèi)已經(jīng)存儲(chǔ)了一些數(shù)據(jù) D。PoSt其特征是多項(xiàng)式時(shí)間算法的元組： （Setup， Prove， Verify）。

· PoSt.Setup（1λ，D）-》Sp，Sv，其中SP 和 SV 是P 和V 的特點(diǎn)方案的設(shè)置變量，λ 是一個(gè)安全參數(shù)。PoSt.Setup用來(lái)給予 P 和V 必要的信息來(lái)運(yùn)行PoSt.Prove和 PoSt.Prove。一些方案可能要求證明人或者是有互動(dòng)的第三方去運(yùn)算PoSt.Setup。

· PoSt.Prove（Sp ， D， c， t） → πc，其中c 是驗(yàn)證人V 發(fā)出的隨機(jī)驗(yàn)證， πc 是證明人在一段時(shí)間內(nèi)可以訪問(wèn)數(shù)據(jù)D 的的證明。PoSt.Prove由P（證明人）為V（驗(yàn)證者）運(yùn)行生成 πc。

· PoSt.Verify（Sv， c， t，πc）→ {0，1}，用來(lái)檢測(cè)證明proof是否是正確。PoSt.Verify 由V運(yùn)行和說(shuō)服V 相信 P 在一段時(shí)間內(nèi)已經(jīng)存儲(chǔ)了R。

從邏輯上來(lái)講，數(shù)據(jù)的持有性證明是一種由兩個(gè)角色和四個(gè)步驟完成的游戲。第一個(gè)角色是Challenger，第二個(gè)角色是完成Proof的人，Challenger的第一步把文件和一些謎題生成之后，放到Server上；第二步生成某個(gè)Challenger的信息，需要的某些數(shù)據(jù)；第三步存儲(chǔ)節(jié)點(diǎn)完成了某個(gè)Proof，發(fā)回給Challenger；第四步就是Challenger用自己原來(lái)遺留的一些信息，生成一個(gè)Verify，用Verify跟Proof去驗(yàn)證這東西是不是對(duì)的；這就是用兩個(gè)角色、四個(gè)步驟完成驗(yàn)證。

去中心化存儲(chǔ)項(xiàng)目需要解決的問(wèn)題非常多，但是我們需要避免項(xiàng)目周期過(guò)長(zhǎng)和設(shè)定過(guò)于龐大的目標(biāo)。在軟件領(lǐng)域，有一本著名的書(shū)叫做《人月神話》，講述了一個(gè)著名的軟件項(xiàng)目失敗的過(guò)程。事實(shí)上，任何設(shè)計(jì)目標(biāo)過(guò)于宏大的軟件都難逃失敗的命運(yùn)，而正確的開(kāi)發(fā)方式則應(yīng)該是通過(guò)敏捷和迭代來(lái)進(jìn)行完成。

FileCoin作為一個(gè)歷史悠久的項(xiàng)目，其白皮書(shū)所采用的技術(shù)方案多次更改，核心共識(shí)算法PoST v1從最早的類PoW共識(shí)，到2017完全推翻V1的設(shè)計(jì)，改用類似于Algorand的VRF算法，到加入Poreps的VDE實(shí)現(xiàn)，到引入新的VDF算法，并且檢索市場(chǎng)、小額支付等問(wèn)題也尚未有完善的設(shè)計(jì)方案，F(xiàn)ileCoin涉獵了太多的技術(shù)及學(xué)術(shù)難題，使得開(kāi)發(fā)周期變得非常不可控。

Lambda的解決方案

而Lambda的思路是，盡可能通過(guò)原型系統(tǒng)去迭代實(shí)現(xiàn)一個(gè)基于區(qū)塊鏈的PDP和POR系統(tǒng)，并實(shí)現(xiàn)PoST的所有優(yōu)點(diǎn)，比如連續(xù)挑戰(zhàn)和鏈上隨機(jī)挑戰(zhàn)。Lambda認(rèn)為，在非BlockChain情況下，在另外一種和POR不一樣驗(yàn)證算法中，可以構(gòu)造一個(gè)PDP算法，假設(shè)一個(gè)可信第三方，通過(guò)一定的概率，對(duì)于數(shù)據(jù)的持有性進(jìn)行驗(yàn)證，并且把驗(yàn)證結(jié)果以顯式不可篡改的方式來(lái)存儲(chǔ)。那么這個(gè)可信的第三方的審計(jì)，也就是所謂的TPA，一定可以把驗(yàn)證結(jié)果通過(guò)上鏈來(lái)實(shí)現(xiàn)不可篡改，并且一個(gè)單點(diǎn)可信的驗(yàn)證過(guò)程，也一定可以通過(guò)一組半可信Validator節(jié)點(diǎn)共識(shí)來(lái)完成。

而對(duì)于Validator節(jié)點(diǎn)和角色的使用，是Lambda不同于FileCoin的主要特點(diǎn)，也因此讓Lambda項(xiàng)目的開(kāi)發(fā)難度得以降低。今天，Lambda開(kāi)放的使用Validator節(jié)點(diǎn)的PoST實(shí)現(xiàn)，給分布式存儲(chǔ)和區(qū)塊鏈存儲(chǔ)領(lǐng)域提供了新的思路和研究方向。