深入区块链共识:PoC论文解读与模型建立
摘要: 本系列文章,是链博核心区块链研究小组输出的高质量区块链研究性文章,旨在研究和分享底层区块链技术的原理解析,新技术趋势,拒绝讨论任何token,行情和投资建议。
此前,我们简要介绍了基于存储的共识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是否可以纳入其框架之下和一些思考的分享。
链博科技区块链系列文章,致力于分享区块链领域的底层技术知识,努力提供原创,有深度的技术内容。
从技术角度探索区块链创新的同时,链博科技也从产业结合角度深入思考,推进区块链落地项目的建设,为企业提供专业、易用、全栈的区块链链改服务。
你可能感兴趣的文章
-
给区块链大佬泼盆冷水:先吃螃蟹者,不一定是英雄,也可能是烈士
-
给区块链大佬泼盆冷水:先吃螃蟹者,不一定是英雄,也可能是烈士
朱啸虎冷眼旁观区块链昨天朱啸虎与陈伟星(快的打车创始人)的互怼,想必大家都有目共睹了,有人觉得朱啸虎理性,有人觉得陈伟星更有前瞻性。不过区块链的火热,也引发了许...
2024-10-18
连获2个“全市第一”苏州高铁新城区块链又到高光时刻
-
连获2个“全市第一”苏州高铁新城区块链又到高光时刻
11月6日,2020(第八届)江苏互联网大会可信区块链高峰论坛上,正式公布了江苏省50大区块链典型应用案例。在这份极具含金量的省级名单中,苏州高铁新城14项相关...
2024-10-18
解读:腾讯区块链方案白皮书(三)
-
解读:腾讯区块链方案白皮书(三)
“我们很清楚,孤木难成林。只有赋予开放分享的基因,生态才可能长成一片森林。”这是马化腾2016年在至伙伴公开信中曾经提到,显然,区块链已经成为腾讯开放基因中的重...
2024-10-18
手机挖矿app有哪些这三种目前比较火
-
手机挖矿app有哪些这三种目前比较火
手机挖矿应成为现在很流行的一种赚钱方式了,那么手机挖矿app哪个好?那个app靠谱?有哪些手机挖矿app呢?下面一起了解一下吧!什么是手机挖矿手机挖矿其实本质还...
2024-10-18
以太币是什么?新人必看教学
-
以太币是什么?新人必看教学
以太币是什么
2024-10-18
虚拟货币投资详解,哪些币种值得入手?!
-
虚拟货币投资详解,哪些币种值得入手?!
3、定投定期定额买虚拟货币是一种比较适合新手投资的方式,定投指每隔一段时间,以固定的金额买入同一种加密资产或者组合
2024-10-18
野路子能出奇迹?快来看区块链十大主流代币
-
野路子能出奇迹?快来看区块链十大主流代币
比特币(BTC)数字货币鼻祖,最具价值的虚拟货币。因勒索病毒点名只收比特币而进入大众视野,2017年比特币自身价格的暴涨更是吸引了大批投资者进入数字货币市场。由...
2024-10-17
一文看 懂国内区块链产业,到底哪块最赚钱?
-
一文看 懂国内区块链产业,到底哪块最赚钱?
区块链火了。无论它是徐小平、陈伟星等人眼中的“风口”,还是巴菲特、朱啸虎等人口中的“泡沫”、“骗局”。当你为没加入“3点钟”社群而深深焦虑的时候,不如平心静气地...
2024-10-17
央行数字货币五大好处曝光以人的价值为基础,用区块链定义
-
央行数字货币五大好处曝光以人的价值为基础,用区块链定义
2月28日,国际货币基金副总裁张涛在伦敦经济学院发表了演讲,探讨了最近的国际热门话题,即“中央银行数字货币(简称:CBDC)”。演讲中,张涛简单阐述了CBDC的...
2024-10-17
详解印度区块链,你不可错过的二三事
-
详解印度区块链,你不可错过的二三事
区块链在印度发展可谓一波三折,但数字货币的快速升值也引起了印度媒体的关注,主流媒体对加密货币进行了密集报道,大多数文章对比特币和加密币持支持的态度,会给出“投资...
2024-10-17