深入区块链共识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是否可以纳入其框架之下和一些思考的分享。
你可能感兴趣的文章
-
“姚班”团队在上海打造世界级区块链,姚期智给他们带来了什么?
-
“姚班”团队在上海打造世界级区块链,姚期智给他们带来了什么?
近日,习近平总书记给中国科学院院士、清华大学教授姚期智回信,向他致以诚挚问候并提出殷切希望。姚期智是“计算机诺奖”图灵奖得主,曾长期在美国高校任教,2004年全...
2024-10-16
黑客将以太坊区块链系统与谷歌系统相链接 可通过电子邮件发送以太坊
-
黑客将以太坊区块链系统与谷歌系统相链接 可通过电子邮件发送以太坊
站长之家(ChinaZ.com) 11月13日 消息:据trustnodes报道, 三名黑客提出了一个创新项目,将以太坊的区块链系统与谷歌系统连接起来,可以实现...
2024-10-16
新发票来了:官方发公告推行区块链发票这个咋用?
-
新发票来了:官方发公告推行区块链发票这个咋用?
1、通俗理解区块链发票1.流程:就餐—微信付款—微信“卡包”—申请开发票(填开票信息,跟“我的发票”链接)—申请报销—款到账(要是到微信钱包,将来可能还有手续费...
2024-10-14
别人都在发币,他们将区块链系统吞吐量提升了几万倍
-
别人都在发币,他们将区块链系统吞吐量提升了几万倍
区块链想满足大规模商用的需求,交易处理速度的提升是必要的前提条件。本文共计2304字,阅读时间4分钟。项目要点:1、博晨是一家区块链底层技术公司,已经完成两轮融...
2024-10-14
区块链工程技术人员需要什么报考条件?证书有什么用?
-
区块链工程技术人员需要什么报考条件?证书有什么用?
作为一个新兴发展的行业,国家政策红利之下,各行各业对不同种类的区块链人才有了更大的需求,选择成为一名区块链工程技术人员好就业,待遇也好,也有很多想要取得区块链工...
2024-10-10
区块链如何实现数据共享“可用不可见”?
-
区块链如何实现数据共享“可用不可见”?
我们在以前的文章中曾经提到,区块链的一大价值在于打破数据孤岛,让不同的企业、机构、组织之间可以共享数据,从而缩减流程,提升效率,增进合作。但是,对于这一点的细节...
2024-10-09
“风口”还是“虚火”? 来看这些五花八门的区块链应用
-
“风口”还是“虚火”? 来看这些五花八门的区块链应用
陈思进称,“区块链”领域存在泡沫,与20年前的“.COM”泡沫相似。他表示,那时,一个公司只要带上“.COM”的标识,其股价就会飙升。但是20多年过去了,在当年...
2024-10-09
民生中信银行上线国内信用证信息传输区块链系统,首日交易量达1亿人民币
-
民生中信银行上线国内信用证信息传输区块链系统,首日交易量达1亿人民币
近日,民生银行与中信银行合作打造的基于区块链的国内信用证信息传输系统一期(Blockchain based Letter of Credit System , ...
2024-10-02
一、区块链和分布式数据库的本质区别
-
一、区块链和分布式数据库的本质区别
此文是李宁先生的分享,讲解了什么是区块链?什么是分布式数据库?相信很多人容易混淆这两个概念。表面上看,区块链和分布式数据库在基础技术方面有很多相似的地方,但也仅...
2024-09-27
区块链国际标准在上海发布,原创技术为我国争得全球规则制定权
-
区块链国际标准在上海发布,原创技术为我国争得全球规则制定权
今天,IEEE(电气电子工程师学会)和上海树图区块链研究院联合发布了IEEE国际标准《区块链系统应用接口规范》(项目编号:IEEE P3217)。这项国际标准由...
2024-09-27