*本系列文章，是链博核心区块链研究小组输出的高质量区块链研究性文章，旨在研究和分享底层区块链技术的原理解析，新技术趋势，拒绝讨论任何token，行情和投资建议。
上篇文章中《深入区块链共识（一）：PoC概念及起源&BurstCoin沉浮史》中，我们简要介绍了基于存储的共识PoC(Proof-of-Capacity), 本篇文章中，我们将以Burst为例，进一步深入讲解PoC的数学基础以及完整的算法过程。
熟悉Bitcoin历史的朋友可能知道，PoW(Proof of Work)的概念和思想雏形并非由中本聪发明，而是早在2001年，就由Dwork and Naor[10]提出。
其核心思想在于，通过一种对CPU运算资源上“证明者(Prover)低效，验证者(Verifier)高效”的算法，达到证明者向验证者证明其对特定量的计算资源的投入的目的。
算法被运用于增加垃圾邮件发送者的发送开销，以此防止垃圾邮件。
同样的，对于存储资源来说，在分布式存储领域，文件拥有者与文件请求者之间，同样存在验证与被验证的关系。
[11],[12],[13]几篇论文都构建了一系列证明被验证者拥有某种存储资源的交互式算法。
PoC(Proof-of-Capacity)其背后的核心理念，便是在存储资源上，"证明者(Prover)低效，验证者(Verifier)高效"，以达到验证者可以花费很少的存储资源，在较少的计算时间内，验证证明者(Prover)拥有一定存储空间的目的。
Stefan Dziembowski[14]是第一个将存储量证明(proofs of storage, proofs ofretrievability或者proof of capacity等类似概念，思想都是基于存储证明)引入区块链系统的人，并完成了给出完整形式化证明的论文工作。
本篇我们将简单回顾其基于数学模型的系统设计，同时在下篇文章，我们以Burst为例，探讨其在实际系统中的工程实现。(值得注意的是，虽然paper的内容正是BurstCoin中的共识思想，但时间上Burst第一个release版本在这一篇paper的发表之前，其中的人物和Burst的渊源没有公开资料披露，我们亦不得而知)
在PoC共识中的最关键的一个问题，即证明者(Bob代指)如何向验证者(Alice代指)证明，其拥有某个特定文件大小的文件F始终存在于Bob的磁盘之中。
一个最简单直观的方式，我们可能会想到Alice在事先将F发送给Bob，其后Bob在需要证明时返回同样的文件F。
如下图所示，Alice接受到文件后，校验其是否与之前发送给Bob的文件一致。但这样做显然违背了"对存储资源，验证高效"的特性。
同时，在P2P网络中，利用有限的带宽发送PoC共识需要的大容量文件显然也是不现实的。
所以，我们需要设计一种对存储资源和网络资源来说都高效的算法，以达到"校验高效"的目的。
在PoC的范畴内，文件F的目的只是为证明Prover确实使用了一定量存储空间的工具，也即我们可以对文件F的内容做任何形式的要求(可以联想PoW中的CPU计算过程本身，并不与任何特定非区块链应用相关)。
在Stefan Dziembowski提出的PoC算法中，文件的内容是一种有向无环图(Directed Acyclic Graph,DAG)结构, 以V代表图中所有节点，定义W(V), 要求其满足一个特性W(V)=Hash(V, W(V')), 其中V'为V在图中的直接前驱节点。
如上图所示，图中简单解释了有向无环图结构，其每个节点的W值都是经过一次hash计算的长二进制串。
Prover需要将每个节点的W值存储，以供Verifier在验证阶段随机抽取检验。Prover与Verifier的交互流程如下：
- 初始阶段：
- Verifier与Prover协商复杂有向无环图G，同时Prover计算所有W(V)，并存储计算结果(此步骤需要的计算时间与存储空间，和图的节点数目成正比。)
- Prover 将所有W(V)的值组成默克尔树(Merkle Tree)，同时将树根节点的值Φ发送给Verifier
- 验证阶段：
- Verfier随机抽取节点V，要求Prover给出其W(V)的值，同时揭示其在Merkle Tree中的路径
- Prover提取其存储中的特定W(V)，同时揭示其在Merkle Tree中的路径
- Verfier验证其W(V)的合法性，同时验证其是否存在以Φ为根的Merkle树中
在初始阶段，类似PoW算法中利用hash达到证明CPU的使用量，PoC在初始阶段要求诚实的Prover存储每个按照图结构计算出的节点hash值。
由于在实际应用中，图节点数远远比上图要多, 同时图的连接关系也比上图更加复杂，考虑到最有可能的Prover作弊的情况是，Prover在初始阶段不使用大量的存储将Hash运算后的结果存储在磁盘上，而是在验证阶段重新使用CPU资源进行Hash的运算。
这样的以“时间换空间”的作弊行为显然是行不通的，因为在有限的验证时间内，投入巨大的运算资源重新计算每个节点的Hash值，既是不经济的，更是不现实的。
论文中选取 Random Bipartite Graphs 与 Superconcentrator Graphs 两类特定类型的DAG，两类图形的数学特性保证了节点间的连接关系的高度复杂性。
通过建立的 Pebble Game 模型，证明一个不诚实的Prover如果不存储与图节点相同数量的Hash值时，在常数有限时间内，不可能正确的通过验证者的验证[14]。
上述两阶段交互既是论文中提到的PoC算法的核心。
细心的读者可能会注意到在初始阶段的b与验证阶段的b,c两个步骤中，涉及到关于Merkle Tree的计算和验证，此处的核心思想在于利用Merkle Tree的性质，简化验证者的验证复杂度，从而达到对验证者来说"验证高效"的目的。
如上图所示，Prover将每个节点的W值作为merkle树的叶子节点，计算出merkle树的树根，作为参数之一，在初始节点发送给Verifier。
在验证阶段，Verifier只需要验证某个节点的W值是否存在在第一步初始阶段发送的Merkle树中即可。
其算法流程与区块链系统中常见的轻钱包验证交易完全相同，使验证工作的复杂度大大降低。
综上所述，我们解读了PoC领域的第一篇Paper的工作，主要集中在其理念，算法的构建。
具体的模型细节和证明细节有兴趣的读者可以参考Stefan Dziembowski[14]论文获取更多。
BurstCoin则是在工程角度实际运行的PoC完备系统。两者在理念上是完全一致的，但Burst在实现细节上却与该论文提出的模型和交互不完全相同。
下一篇文章我们将重点介绍BurstCoin的PoC共识过程，同时在末尾结合StefanDziembowski的模型讨论Burst是否可以纳入其框架之下和一些思考的分享。
链博科技区块链系列文章，致力于分享区块链领域的底层技术知识，努力提供原创，有深度的技术内容。
从技术角度探索区块链创新的同时，链博科技也从产业结合角度深入思考，推进区块链落地项目的建设，为企业提供专业、易用、全栈的区块链链改服务。
欢迎关注我们的往期文章，也欢迎在文章评论区留下你们的观点和想法。
参考源
- [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, LeaKissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession atuntrusted 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: theoryand implementation. In CCSW, pages 43–54, 2009
- [13.] Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secureerasure. In Security and Cryptography for Networks - 9th InternationalConference, SCN 2014, Amalfi, Italy, September 3-5, 2014. Proceedings, pages520–537, 2014]
- [14.] Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs ofspace. Lecture Notes in Computer Science (Including Subseries Lecture Notesin Artificial Intelligence and Lecture Notes in Bioinformatics), 9216(616160),585–605.
- [15]Bitcoin White Paper
