什么是PoST时空证明算法

从十年前到今天，比特币从一个白皮书的构想逐渐成为全球最大的点对点网络支付系统之一。随着比特币的发展，区块链技术也受到越来越多的关注。

其实，区块链本质上就是一个分布式的应用软件，而分布式系统首要问题就是解决一致性的问题，也就是要达成共识，所以说共识算法就是区块链的「灵魂」。从BFT到PoW再到PoS，共识算法逐渐被被发明、改进和应用。今天在区块链的核心领域——分布式存储领域，Lambda团队初步实现了该领域最为核心的算法，也就是PoST时空证明算法，并将该算法的核心类库部分在GitHub上进行开源，开源协议遵守GPL V3。

数据完整性验证机制

近些年，云计算得到广泛的普及和应用，其核心理念就是资源租用、应用托管和服务外包，其通过虚拟化技术将分布的计算节点组成一个共享的虚拟化池，为用户提供服务。但是当用户选择将大量应用和数据部署到云计算平台中时，云计算系统也相应地变为云存储系统，但高度集中的计算资源使云存储面临着严竣的安全挑战，这也是中心化服务先天具备的弱点。

此前我们在《腾讯云数据丢失事件思考：存储的未来在哪里？》一文中也提到，中心化的云存储在安全性、可靠性以及服务水平层面还存在很多问题亟待解决。企业数据放在云存储中，他们最关心的是数据是否完整无误，如果出现故障，是否可以实现数据的恢复，而且能够证明这些数据与原来数据完全一致。这就是去中心存储中经常提到的「数据完整性验证机制」。

数据完整性验证机制根据是否对数据文件采用了容错预处理分为数据持有性证明PDP机制（PDP，Provable Data Possession）和数据可恢复证明POR机制（POR，Proofs of Retrievability）。PDP机制能快速判断远程节点上数据是否损坏，更多的是注重效率，而POR机制不仅能识别数据是否已损坏， 且能恢复已损坏的数据。这两种机制有着不同的应用需求，PDP机制主要用于检测大数据文件的完整性，而POR机制则用于确保重要数据的完整性，以及数据丢失之后的可恢复性。

数据持有性证明PDP机制

首先我们可以看看PDP方案的一个应用场景：

（1）Alice要求Bob记忆一组信息；

（2）Alice本身并不会记下这组信息；

（3）Alice请Chris来确认Bob是否还记得这组信息；

（4）Chris并不了解这组信息的内容。

我们对这些角色进行代换：Alice即是用户，Bob即为存储旷工，Chris即为第三方审核者（以下简称TPA）。

验证流程如下：

（1）用户为待外包的每块数据生成一个Tag，这个tag经由用户进行签名；

（2）TPA随机对用户外包数据中一块发起Challenge，这个Challenge中包含有TPA生成的随机数；

（3）存储旷工根据被挑战的数据块内容、Tag信息、Challenge信息以及自己生成的一个随机计算得到一个Proof；

（4）TPA以challenge、proof及用户公钥为参数，通过映射函数e（u，v）双线性性质检验存储旷工是否持有数据。

PDP的核心公式为：

时空证明：Proof of Space Time

PoST，全称是Proof of Space TIme，是由FileCoin引入到区块链领域的概念，「时空」的定义是衡量并计算存储在网络中的数据存储时间及空间。 FileCoin和Lambda都是旨在提供去中心化的分布式存储，矿工通过存储及检索过程获得客户的付费，并通过时空证明算法获得出块奖励。由于整个网络是没有中心化节点的P2P网络，因此需要某种机制保证用户所存储数据的完整性和可恢复性，因此诞生了这个领域的一些相关算法。

时空证明PoST，它可以让验证者检查存储提供商是否在一段时间内存储了他/她的外包数据。这对提供商的直接要求是：

（1）生成顺序的存储证明来作为确定时间的一种方法。

（2）组成递归执行来生成简单的证明。

其实，PoST算法是对POR的一种改进，POR算法是由Juels等人在一篇名叫《Proofs of Retrievability For Large Files》的论文中最早进行阐述，其核心是将文件分片存储，并根据分片的标签信息定期进行挑战和证明。但通常学术界所定义的POR的运行依赖于中心化第三方节点，并且每次运行都要进行预处理，相对的SpaceTIme（PoST）是一定时期内产生一个POR序列来证明有用存储的保持时间。

如下图所示，PoST与PoR的主要区别在于重复挑战的执行，而不重新运行初始化阶段，这就大大提高了执行效率。

关于 IPFS和 FileCoin

现在，区块链领域的很多人混淆了IPFS和FileCoin项目，以为IPFS项目已经解决了存储数据的完整性问题，这是一个误区。这些人错误的认为，IPFS对数据进行哈希之后，是可以保证数据的不可篡改的，这是一个错误的认识，对于任意IPFS网络的节点来说，它们仅仅会存储自己感兴趣的数据，而不是用户指定的数据。因此，需要一个激励和检查层来确保用户指定数据的存储和不被篡改。做一个简单的比较，IPFS是类似于开源的Ceph软件，FileCoin和Lambda则更类似于AWS的S3。没有数字货币激励的单纯存储系统，是不可能解决数据的持有性问题的。

FileCoin关于时空证明PoST的定义为：

· 时空证明PoST方案使得有效的证明人P 能够说服一个验证者V 相信 P 在一段时间内已经存储了一些数据 D。PoSt其特征是多项式时间算法的元组： （Setup， Prove， Verify）。

· PoSt.Setup（1λ，D）-》Sp，Sv，其中SP 和 SV 是P 和V 的特点方案的设置变量，λ 是一个安全参数。PoSt.Setup用来给予 P 和V 必要的信息来运行PoSt.Prove和 PoSt.Prove。一些方案可能要求证明人或者是有互动的第三方去运算PoSt.Setup。

· PoSt.Prove（Sp ， D， c， t） → πc，其中c 是验证人V 发出的随机验证， πc 是证明人在一段时间内可以访问数据D 的的证明。PoSt.Prove由P（证明人）为V（验证者）运行生成 πc。

· PoSt.Verify（Sv， c， t，πc）→ {0，1}，用来检测证明proof是否是正确。PoSt.Verify 由V运行和说服V 相信 P 在一段时间内已经存储了R。

从逻辑上来讲，数据的持有性证明是一种由两个角色和四个步骤完成的游戏。第一个角色是Challenger，第二个角色是完成Proof的人，Challenger的第一步把文件和一些谜题生成之后，放到Server上；第二步生成某个Challenger的信息，需要的某些数据；第三步存储节点完成了某个Proof，发回给Challenger；第四步就是Challenger用自己原来遗留的一些信息，生成一个Verify，用Verify跟Proof去验证这东西是不是对的；这就是用两个角色、四个步骤完成验证。

去中心化存储项目需要解决的问题非常多，但是我们需要避免项目周期过长和设定过于庞大的目标。在软件领域，有一本著名的书叫做《人月神话》，讲述了一个著名的软件项目失败的过程。事实上，任何设计目标过于宏大的软件都难逃失败的命运，而正确的开发方式则应该是通过敏捷和迭代来进行完成。

FileCoin作为一个历史悠久的项目，其白皮书所采用的技术方案多次更改，核心共识算法PoST v1从最早的类PoW共识，到2017完全推翻V1的设计，改用类似于Algorand的VRF算法，到加入Poreps的VDE实现，到引入新的VDF算法，并且检索市场、小额支付等问题也尚未有完善的设计方案，FileCoin涉猎了太多的技术及学术难题，使得开发周期变得非常不可控。

Lambda的解决方案

而Lambda的思路是，尽可能通过原型系统去迭代实现一个基于区块链的PDP和POR系统，并实现PoST的所有优点，比如连续挑战和链上随机挑战。Lambda认为，在非BlockChain情况下，在另外一种和POR不一样验证算法中，可以构造一个PDP算法，假设一个可信第三方，通过一定的概率，对于数据的持有性进行验证，并且把验证结果以显式不可篡改的方式来存储。那么这个可信的第三方的审计，也就是所谓的TPA，一定可以把验证结果通过上链来实现不可篡改，并且一个单点可信的验证过程，也一定可以通过一组半可信Validator节点共识来完成。

而对于Validator节点和角色的使用，是Lambda不同于FileCoin的主要特点，也因此让Lambda项目的开发难度得以降低。今天，Lambda开放的使用Validator节点的PoST实现，给分布式存储和区块链存储领域提供了新的思路和研究方向。