*本系列文章，是链博核心区块链研究小组输出的高质量区块链研究性文章，旨在研究和分享底层区块链技术的原理解析，新技术趋势，拒绝讨论任何token，行情和投资建议。
上一篇文章《深入区块链共识(三)》中，我们以BurstCoin为例，详细介绍了工程中的PoC共识算法的实现，主要集中在Plot文件内容的生成，与出块的详细交互和计算流程。
本篇文章，我们将提取几个PoC共识过程的核心问题，同时对比Stefan Dziembowski的模型，讨论其与Burst的异同和场景，结合对PoC基本文件结构和挖矿流程的介绍，可以帮我们更好的理解PoC算法。
基于deadline的出块过程中，如何解决分布式节点中的时间同步问题
image
区块链系统作为分布式系统的一种特殊类型，继承了分布式系统的特性与问题。熟悉分布式系统的读者可能了解，在设计分布式系统时，一个重要的分布式系统特性一定要纳入考虑，即lack of global clock，也即是分布式系统中不存在唯一的全局时钟。
在BurstCoin系统中，不同的矿工对不同的节点广播具有不同deadline的区块，而不同的节点对于当前时钟又有着不同的理解，那节点如何确定当前的block是否可以满足广播条件？收到网络中同步的区块，又如何验证其deadline是合法的呢？
要解决因为时钟不同，步调不一致而导致的 out of sync 的问题，在分布式系统中，一般需要设法形成一个逻辑上的「时钟」，让大家都认可这个「时钟」而不是自己的时钟。
这个逻辑时钟的第一个实现是 Lamport timestamps。虽然Lamport timestamps 学术价值大于实际价值，并没有被系统实际使用，然而在它之上演进出的 Vector clock 广泛被 AWS S3，DynamoDB，Riak 等系统采用，用于确保同一个 object 的因果关系。
image
Vector clock 的算法严重依赖于节点间的信任，所以它只适用于一个可信赖的分布式环境。而作为运行在节点间互相并不信任的 P2P 网络上的区块链系统，无法确保这一点。那么，类似 Bitcoin 这样的分布式系统，是怎么决定时间（因果）的呢？中本聪在 Bitcoin 的设计中，巧妙地应用了 PoW 的产物，block 来作为系统的逻辑时间（引用BitCoin白皮书）：
The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post.[2][3][4][5] The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.
Each block contains a Unix time timestamp. In addition to serving as a source of variation for the block hash, they also make it more difficult for an adversary to manipulate the block chain. A timestamp is accepted as valid if it is greater than the median timestamp of previous 11 blocks, and less than the network-adjusted time + 2 hours. "Network-adjusted time" is the median of the timestamps returned by all nodes connected to you. As a result block timestamps are not exactly accurate, and they do not need to be. Block times are accurate only to within an hour or two. Whenever a node connects to another node, it gets a UTC timestamp from it, and stores its offset from node-local UTC. The network-adjusted time is then the node-local UTC plus the median offset from all connected nodes. Network time is never adjusted more than 70 minutes from local system time, however. Bitcoin uses an unsigned integer for the timestamp, so the year 2038 problem is delayed for another 68 years.
BurstCoin也一定程度继承了BitCoin的核心思想，timestamp作为一种逻辑上的先后时序存在，而非真正精确的时间。
一般其与真正的UTC时间之间允许有1-2小时误差。同时，BurstCoin的特殊性在于，区块是否成功上链与其计算得出的deadline直接相关。故我们在BurstCoin源码中可以找到如下的校验过程：
image
此过程对比了当前区块deadline的值，与当前区块timestamp和其前驱timestamp的差值。其中的timestamp，即为相对于块高为0的第一个区块的时间偏移量，允许一定程度的误差。在误差允许的范围内，并不需要全局时钟的存在，区块链系统形成了关于“时序”的共识。
Deadline合法性的校验
开始阅读BurstCoin源码时，笔者曾疑惑，在区块数据库中并无完整当前出块所使用的Scoop，同时也不涉及Merkle的操作，如何校验一个区块的deadline的合法性？
还记得在系列第二篇文章中我们讨论了Stefan Dziembowski提出的PoC系统中，使用了Merkle Tree来简化校验过程，在BurstCoin中也并无关于Merkle树的相关计算。
透彻的阅读BurstCoin源码后，笔者发现，PoC共识中基于存储内容计算出的共识参数deadline的校验，BurstCoin中采用了更巧妙的计算方式，下面我们展开说明:
image
- 在节点收到P2P网络中的历史区块，抑或是收到矿工广播的铸造区块时，首先要对区块进行preVerify操作，此处在调用者提交的参数中，scoopData总是空值，因为在burstCoin所使用的数据存储中，block的字段没有存储scoopData。那又是如何完成验证？
image
- 答案就在calculateHit这一方法之中，BurstCoin将其节点的一部分功能方法放到了burstKit的单独jar包中，找到其计算calculateHit方法后，我们发现，其调用了MiningPlot的初始化方法。
- 在MiningPlot方法中，我们可以看到，通过nonce Id，accountId两个参数，回忆Nonce文件的生成算法，我们可以得知，通过nonce Id 与 accountId，可以完全确定的生成两个Nonce文件。所以，在BurstCoin中，矿工并不需要向节点发送大小为256KB的Nonce文件，只需要在参与出块时，将区块内容与这两个参数发送给钱包节点，由钱包即可计算出整个Nonce值，同时由全网每个节点收到每个区块后都会通过计算此Nonce来计算其deadline。
image
理解了BurstCoin中Deadline的合法性校验过程，让我们与Stefan Dziembowski的协议过程对比。在BurstCoin中，由于不存在Merkle树的计算，所以BurstCoin的存储文件F初始化是完全非交互式的。
矿工只需要遵循协议，用特定的图结构生成Nonce文件即可。（在Burst中，也即Nonce文件的算法方法批量生成Nonce即可。其实Nonce文件计算的过程与Stefan Dziembowski的图模型是可以完全契合的，其中每一个Hash就是Nonce图结构中的w值，在BurstCoin中使用的图结构于Stefan Dziembowski并不完全相同，但其同样有复杂的前驱后继及连接关系，理论的证明Burst并未给出，但总体证明思路是类似的。有兴趣的读者这里可以探究。）
这点无疑是非常重要的优化，由于在分布式系统中，复杂的交互往往带来协议的复杂性，同时由于网络中大量存在的节点，交互的复杂往往会因为P2P网络中存在的网络延时和网络波动变得难以实现。
Stefan Dziembowski虽然在验证阶段使用了Merkle的结构让验证变得极其高效，但是在真实的庞大网络体量的分布式系统中，交互的步骤越少，协议越简单，往往意味着可靠性更高。
在此点上，BurstCoin选择了在验证阶段节点需要额外的8192次Hash计算，以带来初始阶段的完全非交互式文件初始化，和验证阶段更小的网络数据传输量(只需要像节点发送包括nonce Id，accountId的几个固定参数)，无疑是更加适合区块链系统本身的选择。
反观Stefan Dziembowski中提出的相对复杂的初始化流程，更加适合网络情况相对间的联盟链系统和有权限的区块链系统，和一些网络情况较为良好的点对点系统。
BurstCoin如何处理分叉
在PoW共识的区块链系统中中，处理分叉的逻辑非常简单明确，所有诚实的节点都应该认为当前网络中的最长链，即是主链。但事情到了PoC共识中并没有这么显而易见。相比Bitcoin区块时间十分钟，大部分时间都用在矿工对于消耗大量CPU时间对当前区块nonce的计算上。
BurstCoin由于挖矿本身行为并不需要密集的CPU运算时间，矿工往往可以在30秒内完成磁盘的遍历，计算得出的deadline才是真正完成对区块时间的控制，所以主链的判断并不能只依据于最长链。
Bitcoin共识中链的长度体现了当前链上投入的CPU运算量，而在Burst中，体现硬盘空间占用量的指标是累积多少有效的deadline。在一个区块的块高加一的所有竞争者中，产出deadline越小的区块的矿工，概率上使用了更多的存储空间，因而获得铸块权。
类似的，如果考虑分叉的场景，Burst如何判断那一条链为主链？诚实的矿工又如何选择两条分叉的子链呢？
image
在真实的Burstcoin系统中，引入了CumulativeDifficulty的概念。
其计算公式如下：
image
同时，baseTarget对于每个区块都需要重新计算：
image
在BurstCoin中，所有诚实节点都应当认为当前CumulativeDifficulty最大的一条链为PoC共识的主链。
其实这一结论理解起来并不复杂。
观察baseTarget的计算过程我们可知，当前区块的deadline会影响下一个区块的挖矿难度，也即当前deadline越小，下一个区块的baseTarget越小，同时CumulativeDifficulty由于当前区块所附加的难度就越大，从而由CumulativeDifficulty这一指标反映了各条子链的所有区块的难度之和。
类似PoW思想，链的长度本质上代表该链上面的投入的计算资源的数量多少。而在PoC中，通过CumulativeDifficulty这一指标直观的反映了当前链上使用存储资源的数量多少。
通过这三个问题的详细讨论，结合源码分析，相信读者可以对PoC共识的内容，思想和算法细节由透彻详尽的理解。
PoC系列文章截至本章就告一段落，后续，我们将讨论更多关于区块链领域的技术话题，对于特定领域感兴趣的朋友，也欢迎评论说明。
image
链博科技区块链系列文章，致力于分享区块链领域的底层技术知识，努力提供原创，有深度的技术内容。
从技术角度探索区块链创新的同时，链博科技也从产业结合角度深入思考，推进区块链落地项目的建设，为企业提供专业、易用、全栈的区块链链改服务。
欢迎关注我们的往期文章，也欢迎在文章评论区留下你们的观点和想法。
参考源
- [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, Lea Kissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession at untrusted 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: theory and implementation. In CCSW, pages 43–54, 2009
- [13.] Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secure erasure. In Security and Cryptography for Networks - 9th International Conference, SCN 2014, Amalfi, Italy, September 3-5, 2014. Proceedings, pages 520–537, 2014]
- [14.] Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs of space. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9216(616160), 585–605.
- [15]Bitcoin White Paper
网友评论