什么是PoST時空證明算法

從十年前到今天，比特幣從一個白皮書的構想逐漸成為全球最大的點對點網絡支付系統(tǒng)之一。隨著比特幣的發(fā)展，區(qū)塊鏈技術也受到越來越多的關注。

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

數(shù)據(jù)完整性驗證機制

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

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

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

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

首先我們可以看看PDP方案的一個應用場景：

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

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

（3）Alice請Chris來確認Bob是否還記得這組信息；

（4）Chris并不了解這組信息的內容。

我們對這些角色進行代換：Alice即是用戶，Bob即為存儲曠工，Chris即為第三方審核者（以下簡稱TPA）。

驗證流程如下：

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

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

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

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

PDP的核心公式為：

時空證明：Proof of Space Time

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

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

（1）生成順序的存儲證明來作為確定時間的一種方法。

（2）組成遞歸執(zhí)行來生成簡單的證明。

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

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

關于 IPFS和 FileCoin

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

FileCoin關于時空證明PoST的定義為：

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

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

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

· PoSt.Verify（Sv， c， t，πc）→ {0，1}，用來檢測證明proof是否是正確。PoSt.Verify 由V運行和說服V 相信 P 在一段時間內已經存儲了R。

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

去中心化存儲項目需要解決的問題非常多，但是我們需要避免項目周期過長和設定過于龐大的目標。在軟件領域，有一本著名的書叫做《人月神話》，講述了一個著名的軟件項目失敗的過程。事實上，任何設計目標過于宏大的軟件都難逃失敗的命運，而正確的開發(fā)方式則應該是通過敏捷和迭代來進行完成。

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

Lambda的解決方案

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

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