论文摘要

3. 关键概念的工作量证明

简单理解就是证明你做了一定工作量的证书。 工作量证明系统的主要特点是客户端需要做一些困难的工作才能得到一个结果，而验证者可以很容易地通过结果检查客户端是否做了相应的工作。 该方案的一个核心特征是不对称性：工作对请求者来说是适度的，对验证者来说很容易验证。

空间证明

依靠磁盘空间而不是计算能力作为采矿的主要资源创造了一种声称比 PoW 更环保和经济的替代方案。 这篇题为《超越赫尔曼的时间-记忆权衡的空间证明的应用》的论文概述了一种使用空间证明的能源密集度较低的采矿过程——比特币的能源密集型采矿模型受到了很多人的批评和许多人认为这是一种资源浪费。 由于能源需求减少和对现有硬件的依赖，这种方法旨在让任何拥有计算机的人都可以访问。 在空间证明系统下，矿工可以将未使用的磁盘空间分配给网络，成功挖掘区块的概率将与矿工分配的磁盘空间和网络总容量成正比。

比特币的工作量证明

工作量证明的算法大致可以描述为：多个服务器在一段时间内同时打包本期交易，打包完成后，结合区块头信息结合SHA256算法进行计算。 区块头和奖励交易 coinbase 中有一个可变的 nonce。 如果运算结果不满足难度要求，则调整nonce的值继续运算。 如果某个服务器首先计算出一个满足难度值的区块，它就可以广播这个区块。 其他服务器验证没有问题后，就可以加入到已有的区块链中，然后大家来争夺下一个区块。 这个过程也被称为挖矿。

比特币网络中的任何一个节点，如果要生成一个新的区块并将其写入区块链，就必须解决比特币网络的工作量证明难题。 本题的三个关键要素是工作量证明函数、区块和难度值。 工作量证明函数是这道题的计算方式，区块决定了这道题的输入数据，难度值决定了这道题需要的计算量。

堵塞

比特币区块由区块头和区块中包含的交易列表组成。 区块头大小为80字节，由4字节的版本号、32字节的上一个区块哈希值、32字节的Merkle Root Hash、4字节的时间扩展（当前时间）、4 bytes 以字节为单位的当前难度值和以 4 字节为单位的随机数。 块中包含的交易列表附加到块头。 第一笔交易是coinbase交易，是矿工获取奖励和手续费的特殊交易。

block的一般结构如图所示：

固定长度为 80 字节的块头是比特币工作量证明的输入字符串。 因此，为了让区块头能够反映出区块中包含的所有交易，在区块的构建过程中，需要通过Merkle Tree算法为要包含在区块中的交易列表生成一个Merkle Root Hash ，并将这个作为交易列表的摘要存储在区块头中。 Merkle Tree的算法图如下：

难度值

难度值（difficulty）是矿工挖矿时的一个重要参考指标。 它决定了矿工需要经过多少次哈希运算才能生成一个合法的区块。 大约每 10 分钟生成一个比特币块。 如果要在不同的网络算力条件下都保持这个速率产生新区块，就必须根据网络算力的变化来调整难度值。 简单地说，难度值设置为每 10 分钟出一个新区块的速率，与挖矿能力无关。

难度调整在每个完整节点内独立且自动发生。 每2016个区块，所有节点都会根据统一的公式自动调整难度。 这个公式是根据最近2016个区块花费的时间和预期时间（预期时间为20160分钟或两周，以每10分钟一个区块为准。根据实际时长与预期时长的比值, 做相应的调整（或做难或易），也就是说出块速度快于10分钟，难度就会增加，慢于10分钟，难度就会降低。

工作流程证明

我们可以大致总结比特币矿工为解决这个工作量证明难题所采取的步骤如下：

1.生成一个Coinbase交易并与所有其他交易组成交易列表打包进区块，通过Merkle Tree算法生成Merkle Root Hash

2. 将Merkle Root Hash等相关字段组装成区块头，将区块头的80字节数据（Block Header）作为工作量证明的输入

3、不断改变区块头中的随机数，也就是nonce的值，对每一个改变的区块头进行两次SHA256运算（即SHA256(SHA256(Block_Header))），并将结果值与目标进行比较对当前网络的值进行比较比特币3000论文，如果小于目标值，则问题成功解决，工作量证明完成。

计算分析

Hash值是由数字和大小写字母组成的字符串，每一种都有62种可能（可能是26个大写字母，26个小写字母，10个数字中的任意一个），假设任意一个字符出现的概率都相等，则首位为0的概率是1/62（不管其他位出现什么字符），理论上要进行62次Hash运算才能试首位为0，如果前两个2位为0比特币3000论文，就得尝试62次Hash运算的平方，如果从n个0开始，需要尝试62次运算的n次方。

4.POSW

Publicly verifiable proofs of sequential work---publicly verifiable proofs of sequential work

随机预言机（简称RO）。 在密码学中，随机预言机是一个预言机（简而言之，就像一个理论上的黑匣子），它为任何输入返回一个真正均匀的随机输出（见离散均匀分布），但对于相同的输入，预言机将返回完全相同的输出每次。 因为预言机实际上是一个黑盒子，中间有一个固定的算法，这个算法是相当复杂和保密的，所以相同的输入值经过这个算法运算后会输出相同的输出值，就像一个定函数在数学中，相同的值会被多次代入以得到相同的结果。 预言机的目的就是让你无法知道你的输入能得到什么样的结果。 如果你给了两个输入，而预言机同时给了两个输出，你将不知道这两个输出对应的结果。 哪个输入。

总结

该论文完成了连续工作的证明，该证明比 [MMV13] 中的原始结构更简单且参数化更好。 它还回答了 [MMV13] 论文中提出的三个问题。

1.规划求解的空间复杂度。 当我们构建时间戳和时间锁难题时，求解器会保留 n 个顶点图的哈希标签。 还有其他使用 O(N) 存储的解决方案吗？ 或者是否有任何内在原因需要 Ω(N) 存储？

论文中的改进方案是空间复杂度降低到O(logn)

2.深度鲁棒图的必要性。 我们构建的效率和安全性与深度文件图结构的参数密切相关：较低度的图给出更有效的解决方案，而具有更高鲁棒性的图（在某些顶点后剩余的最长路径长度的下限被移除) 给我们带来小的对抗优势的谜题。 一个有趣的悬而未决的问题是逆向是否也成立：具有更好参数的时间锁定谜题也意味着存在具有更好参数的深度稳健图？

深度稳健的地图也不是必需的。 仅底图就足以满足要求。

3. 基于RO模型的POSW可用于在抛硬币等协议中实现公平。

这个问题还在研究中。