这一系列文章是链家博客核心区块链研究小组输出的高质量区块链研究文章。它旨在研究和分享区块链底层技术的原理分析和新技术趋势，拒绝讨论任何令牌，市场和投资建议。之前，我们简要介绍了基于存储的PoC(容量验证)。本文将以Burst为例，进一步阐述PoC的数学基础和完整的算法流程。
熟悉比特币历史的朋友可能知道，PoW(工作证明)的概念和思想原型并不是中本聪发明的，而是早在2001年由Dwork和Naor[10]提出的。
其核心思想是，证明者可以通过一种在CPU计算资源上“证明者低效，验证者高效”的算法，向验证者证明自己在特定量计算资源上的投入。
该算法用于增加垃圾邮件发送者的发送成本以阻止垃圾邮件。
同样，对于存储资源，在分布式存储领域，也存在文件所有者和文件请求者之间的验证与被验证的关系。
[11]，[12]，[13]几篇论文构造了一系列交互算法来证明被验证者拥有某种存储资源。
PoC(Proof-of-Capacity)背后的核心思想是证明者效率低，验证者在存储资源上效率高，这样验证者可以花费更少的存储资源，在更少的计算时间内验证证明者有一定的存储空间。
Stefan Dziembowski[14]是第一个将存储证明(存储证明、可检索证明或容量证明及其他类似概念，均基于存储证明)引入区块链系统的人，并完成了给出完整形式证明的论文工作。
在本文中，我们将简单回顾其基于数学模型的系统设计，在下一篇文章中，我们将以Burst为例，讨论其在实际系统中的工程实现。(值得注意的是，虽然论文的内容只是BurstCoin中的共识思想，但在这篇论文发表之前，时间上Burst的第一个发布版本，并没有关于人物和Burst起源的公开信息，我们也不得而知。)
PoC共识中的一个关键问题是证明者(Bob的代理)如何向验证者(Alice的代理)证明Bob的磁盘中始终存在某个文件大小的文件F。
用最简单直观的方式，我们可能会认为，Alice事先把F发给Bob，然后Bob在需要证明的时候返回同样的文件F。
如下图所示，Alice收到文件后，检查是否与之前发送给Bob的文件一致。但这显然违背了‘存储资源的高效验证’的特性。
同时，在P2P网络中，使用有限的带宽来发送PoC共识所要求的大容量文件显然是不现实的。
因此，我们需要设计一种对存储资源和网络资源都高效的算法，从而达到‘高效验证’的目的。
在PoC的范围内，文件F的目的只是证明证明者确实使用了一定的存储空间，也就是我们可以对文件F的内容提出任何形式的要求(它可以与PoW中的CPU计算过程本身相关联，与任何具体的非区块链应用无关)。
在Stefan Dziembowski提出的PoC算法中，文件的内容是一种有向无环图(DAG)结构。V表示图中的所有节点，定义了W(V)，要求满足特征W(V)=Hash(V，W(V’)，其中V’是图中V的直接前任节点。
如上图所示，简单说明了有向无环图的结构，每个节点的W值经过一次哈希计算后就是一个长二进制串。
证明者需要存储每个节点的W值，这个值可以在验证阶段由验证者随机选取。证明者和验证者之间的交互过程如下：
初始阶段：验证者与证明者协商复杂有向无环图G，而证明者计算所有W(V)并存储计算结果(这一步所需的计算时间与存储空间和图的节点数成正比。)证明者将W(V)的所有值形成一棵Merkle树，并将根节点的值发送给验证者。验证阶段：Verfier随机抽取节点V，要求证明者给出其值W(V)，并揭示其在Merkle树中的路径。证明者在其存储中提取特定的W(V)。同时，揭示其在Merkle树中的路径验证器以验证其W(V)的合法性，并验证其是否存在于根为的Merkle树中。在初始阶段，类似于PoW算法，使用hash来证明CPU使用率。PoC要求诚实证明者在初始阶段存储根据图结构计算的每个节点的哈希值。
在实际应用中，图中的节点数量远远多于上图，图的连接关系也比上图复杂。考虑到最有可能出现的证明者作弊的情况，证明者在初始阶段并没有使用大量的存储来将哈希运算的结果存储在磁盘上，而是在验证阶段复用CPU资源来执行哈希运算。
这种“用时间换空间”的作弊行为显然是不可行的，因为在有限的验证时间内投入巨大的计算资源重新计算每个节点的哈希值是不经济的，也是不现实的。
本文选择随机二部图和超中心图作为两种特殊类型的Dag。这两类图的数学特性保证了节点间连接关系的高度复杂性。
通过建立的Pebble博弈模型，证明了如果一个不诚实的证明者没有存储与图节点相同数量的Hash值，则不可能在恒定的有限时间内正确通过验证者的验证[14]。
上述两阶段交互是本文提到的PoC算法的核心。
细心的读者可能会注意到，Merkle树的计算和验证涉及到初始阶段的B和验证阶段的B和C两个步骤。这里的核心思想是利用Merkle树的性质来简化验证者的验证复杂度，从而达到验证者‘高效验证’的目的。
如上图所示，证明者将每个节点的W值作为merkle树的叶节点，计算merkle树的根，作为参数之一发送给初始节点的验证者。
在验证阶段，验证者只需要验证一个节点的W值是否存在于第一步初始阶段发送的Merkle树中。
算法流程与区块链系统中常见的轻钱包验证交易完全相同，大大降低了验证的复杂度。
综上所述，我们解读PoC领域的第一篇论文工作，主要围绕其思想和算法的构建。
具体的模型细节和证明细节，感兴趣的读者可以参考Stefan Dziembowski[14]了解更多信息。
BurstCoin是一个完整的PoC系统，实际上是从工程的角度运行的。两者在概念上是相同的，但是Burst在实现细节上不同于本文提出的模型和交互。
在下一篇文章中，我们将重点介绍BurstCoin的PoC共识过程，并在最后讨论Burst能否纳入其框架，并分享一些StefanDziembowski模型的思考。
博科技区块链系列文章，致力于分享区块链领域底层技术知识，力求提供原创、深入的技术内容。
链博科技在技术层面探索区块链创新的同时，也从产业整合的角度进行深度思考，推动区块链落地项目建设，为企业提供专业、易用、全栈的区块链改革服务。
欢迎关注我们之前的文章，也欢迎在文章评论区留下你的看法和想法。
–
基准源
[1.]Spacemint:一种基于空间证据的加密货币BHD白皮书[3。]爆裂硬币介绍严重[4。]空间的证明[5。爆发主义者.]堆叠扩展器的空间证明[7。爆裂的Dymaxion[8 .]突发论坛.]采矿教程[10。辛西娅德沃克莫尼瑙尔，《通过处理或打击垃圾邮件定价》[11。朱塞佩阿坦尼斯、兰德尔c伯恩斯、礼萨科特莫拉、约瑟夫海岭、李基斯纳、扎卡里新泽西州彼得森和道恩宋。托管商店中可证明的数据占有。彭宁萨布丽娜德卡皮塔尼迪维梅尔卡蒂和保罗塞弗森，编辑，美国计算机学会CCS 07，第598-609页。美国计算机学会出版社，2007年10月[12。凯文d鲍尔斯、阿里朱尔斯和艾莉娜奥普瑞。可检索性的证明：理论与实现。在CCSW，第43-54页，2009年[13。尼古拉卡尔韦拉斯和阿盖洛斯基亚斯。安全措施的有效证明。《网络安全与加密——第九届国际会议，SCN 2014，意大利阿马尔菲，2014年9月3-5日》。会议录，第520-537页，2014][14。Dziembowski，s .Faust，s .Kolmogorov，v .Pietrzak，K. (2015).空间的证明。计算机科学讲义（包括人工智能的子系列讲义和生物信息学的讲义),9216(616160),585605。[15]比特币白皮书（作者：链博科技，内容来自链得得内容开放平台\”得得号\”;本文仅代表作者观点，不代表链得得官方立场)
