作者：七哥
来源：登链社区
编者注：原标题为《也许是国内第一篇把以太坊工作量证明从算法层讲清楚的》
对于没有把数学学会的同学来说，如果希望从算法层了解以太坊的工作量证明是非常困难的。一本黄皮书会难倒一大批吃瓜群众。因此，本文将试图使用图文和尽量简单的数学来解释以太坊挖矿工作量证明，包括以太坊是如何对抗ASIC1、如何动态调整挖矿难度、如何校验挖矿正确性的。
认识工作量证明PoW
工作量证明是一种对应服务与资源滥用、或是拒绝服务攻击的经济对策。一般是要求用户进行一些耗时适当的复杂运算，并且答案能被服务方快速验算，以此耗用的时间、设备与能源做为担保成本，以确保服务与资源是被真正的需求所使用。
摘自维基百科
这种经济性应对政策概念，是在1993年提，直到1999年才使用Proof-of-Work一词。
ProofofWork，直接翻译过来是工作量证明。这个词的中文直接听起来有点不知所云。实际上如果我跟你说结婚证明，离职证明，那你是不是首先想到的是一张上面印着一些东西的纸呢？别人看到这张纸就知道你的确结婚了，或者你的确从某单位离职了。工作量证明从语法上也是一个逻辑，也可以理解成一张纸，通过这张纸就可以证明你的确完成了一定量的工作。这就是工作量证明的字面意思。
那工作量证明有什么特点呢？我们抛开计算机，用现实世界的例子来说明。例如我上课不认真，老师罚我把《桃花源记》抄写十遍，我用了两个小时的劳动，最后给老师的就是一张纸，而老师要确认我的确付出了大量劳动，其实只需要看一眼就可以了。这个例子道出了POW机制的一大特点，那就是生成需要花费大量劳动，但是验证只需一瞬间。另外一个工作量证明的例子可以是，老师给我出一道题，我给老师的运算结果，或者说就是最后的那个数字，就是我的工作量证明。回到计算机情形下，纸当然是不存在的，所以所谓的工作量证明就是花费了很多劳动而得到的一个数了。
声音 | 国家金融与发展实验室特聘研究员：要加强区块链技术应用的顶层规划和制度安排:据证券日报报道，国家金融与发展实验室特聘研究员董希淼对《证券日报》记者表示，目前区块链技术在公共服务、社会治理以及供应链管理等多个方面已发挥作用。由于区块链技术具有开放透明、难以篡改、开放互联、易于追溯、算法信任等优势，在数字金融、公共服务以及社会治理等都有广阔的应用前景。从应用方向看，区块链技术应发挥其在教育、就业、养老、精准脱贫、医疗健康、商品防伪、食品安全、公益、社会救助等领域的积极作用，赋能实体经济，惠及民生领域；从应用形式看，联盟链或将成为未来区块链应用的主要形式，应逐步解决链上链下数据协同等问题，重点加强对联盟链的研究和开发。同时，要加强区块链技术应用的顶层规划和制度安排，加速底层平台、业务应用等相关标准体系建设，以此更好地参与国际竞争，杜绝借机神化、炒作区块链。[2020/2/10]
再说说POW最早的用途。人们在使用电子邮件的时候会收到垃圾邮件的骚扰。如果没有成本，那么发送一百万封邮件的确是很轻松的事情了。所以，聪明的人就会想，如果让每一封邮件发送时候，都有一个微小的成本，那么垃圾邮件就会被很大程度的遏制了。而POW就是为了服务这个目的产生的。基本过程就是邮件接收方会先广播一道题出去，邮件发送方发邮件的时候必须附带上这道题的答案，这样邮件才会被接受，否则就会被认为是垃圾邮件。
摘自：https://zhuanlan.zhihu.com/p/42694998
挖矿
挖矿就是在求解一道数学方程。方程的多个可能的解被称为解的空间。挖矿就是从中寻找一个解。不同于几何方程，这个挖矿方程有如下特点：
1.没有比穷举法更有效的求解方法；
2.解在空间中均匀分布，每一次穷举查找到解的概率基本一致；
3.解的空间足够大，保证一定能够找到解；
假设挖矿方程是：n=random(1,10)，求n<D。
动态 | 境内已超500项区块链信息服务备案:据新京报消息，第二批境内区块链信息服务备案清单中共涉及309个境内区块链信息服务名称及备案编号，其中大部分为银行、金融服务机构或信息科技类公司，其中也涉及工商银行等上市公司。在第一批通过境内区块链信息服务备案的公司，易见股份曾经暴涨。根据国家网信办公告，自2019年2月15日《区块链信息服务管理规定》正式实施以来，国家互联网信息办公室依法依规组织开展备案审核工作，于今年3月30日发布第一批共197个境内区块链信息服务名称及备案编号。以此计算，第一批、第二批通过备案的区块链信息服务，已超过500项。注：10月27日晚间，上市公司京蓝科技发布公告表示，下属公司好农易电子商务有限公司自主研发、具有自主知识产权的“区块链农业生产溯源系统”通过国家网信办备案。[2019/10/27]
当D为10时，我们只需要运算一次就可以找到任意的n都满足n<10，可当D=5，则平均需要两次运算才能找到n<5，随着D的减小，需要运算的次数就会增大。
这里的D就是通常说的挖矿难度，通过调整解空间中的符合要求的解的数量来控制求解所需要尝试的次数，间接的控制产生一个区块所需要的时间。使得可以调控和稳定区块间隔时间。
当挖矿的人很多，单位时间内尝试次数增多时，求解的速度也就更快，区块挖出用时更短。此时则增大挖矿难度，增大平均尝试次数，使得挖矿耗时上升。反之依然。
以太坊新区块挖矿流程
通过父区块可计算新区块的挖矿难度，再求解挖矿方程。
挖矿工作量证明通过一个密码学安全的nonce来证明“为了获得挖矿方程解n，已经付出了一定量的计算”。工作量证明函数可以用PoW表示：
其中
1.是新的区块头，但nonce和mixHash均为空值；2.是区块difficulty值。；3.是区块mixHash值；挖矿方程算法返还的第一个参数值；4.是区块nonce值;挖矿方程算法返还的第二个参数值；5.d是一个计算mixHash所需要的大型数据集dataset；6.PoW是工作量证明函数，可以得到两个值，其中第一个是mixHash，第二个是密码学依赖于H和d的伪随机数。
声音 | Facebook区块链部门成员：最大的担忧是Libra得不到公平的机会:据LongHash 7月5日消息， Facebook区块链部门的Christina Smedley负责Calibra的品牌推广，而Calibra是Faceboo的子公司，将推出Libra的数字钱包。针对LongHash的提问“那么你现在所担心的是什么呢？”， Smedley表示，我加入这个团队是因为我相信这个使命。我从第一天开始就加入了Facebook的Libra团队，因为我发自内心地认为是时候这样做了。现在，你可以在10秒内发送一幅图片，而且不需要付任何手续费，我认为这个事实同样应该适用于货币。这是唯一没有真正进化的东西。因此我最大的担忧就是它得不到公平的机会，我担心它在还没有覆盖到我们真正的服务目标之前就已经被人们拒绝了。这就是我最近难以入眠的原因。 针对提问“你认为人们最主要的误解是什么？” Smedley表示，我认为应该是他们认为Libra是一种中心化的 Facebook币，但事实并非如此。[2019/7/5]
这个基础算法就是挖矿方程Ethash。通过可以信任的挖矿方程求解，来确保区块链的安全性。同时，挖出新块还伴有区块奖励，所以工作量证明不仅提供安全保障，还是一个利益分配机制。
下面是挖矿工作量证明的计算过程：
大致流程如下：
1.根据父区块头和新区块头计算出；2.在PoW开始时选择一个随机数作为Nonce的初始化值；3.将Nonce和作为挖矿方程Ethash的入参；4.执行Ethash将得到两个返回值：mixHash和result；5.判断result是否高于。如果是则nonce加1，继续穷举查找；否则，如果是则说明求解成功。返回mixHash和Nonce;6.两个值记录到区块头中，完成挖矿。
区块难度difficulty
以太坊的挖矿难度记录在区块头difficulty上，那么在它是如何动态调整的呢？
调整算法在以太坊主网有多次修改，即使以太坊黄皮书中的定义也和实际实现代码也不一致，这里我以程序实现代码来讲解区块难度调整算法。
声音 | 索尼中国：索尼国际教育将开展区块链技术实测:索尼中国今日发微博表示，索尼国际教育、富士通与修曼日本语学校合作，开展区块链技术实测，用于课程记录和成绩单管理。留学预申请人参加指定日语课程学习的数据将以证书形式、不可伪造地存储在区块链中，教育机构据此评估学生能力并提供有效指导。[2019/3/1]
其中有：
是创世区块的难度值。难度值参数被用来影响出块时间的动态平衡。使用了变量而非直接使用两个区块间的时间间隔，是用于保持算法的粗颗粒度，防止当区块时间间隔为1秒时只有稍微高难度情况。也可以确保该情况下容易导致到软分叉。
-99的上限只是用来防止客户端安全错误或者其他黑天鹅问题导致两个区块间在时间上相距太远，难度值也不会下降得太多。在数学理论是两个区块的时间间隔不会超过24秒。
难度增量∈会越来越快地使难度值缓慢增长，从而增加区块时间差别，为以太坊2.0的权益证明切换增加了时间压力。这个效果就是所谓的“难度炸弹”或“冰河时期”。
以太坊的设想是最终从PoW过度到PoS，为了给过度施加时间压力，所以在区块难度中预埋了一个难度炸弹∈，他是以2的指数级增长的。如果听过“棋牌摆米”的数学故事，就应该清楚指数级增长是非常恐怖的。
最终，在拜占庭版本中，伴随EIP-649，通过伪造一个区块号来延迟冰河时期的来临。这是通过用实际区块号减去300万来获得的。换句话说，就是减少∈和区块间的时间间隔，来为权益证明的开发争取更多的时间并防止网络被“冻结”。
在君士坦丁堡版本升级中，以太坊开发者在视频会议中表示，如果直接执行难度炸弹，那么难保以太坊能顺利切换到PoS就有大量矿工离开，这很有可能极大的影响以太坊的安全性。因此，伴随EIP-1234，再一次修改到500万来延迟冰河时期。
这个挖矿难度调整机制保证了区块时间的动态平衡；如果最近的两个区块间隔较短，则会导致难度值增加，因此需要额外的计算量，大概率会延长下个区块的出块时间。相反，如果最近的两个区块间隔过长，难度值和下一个区块的预期出块时间也会变短。
赵长鹏会见百慕大总理 称该国在拥抱区块链上走在前列:百慕大总理David Burt发推特称，很开心邀请到币安CEO赵长鹏和何一与该国内阁会面，分享、探讨了百慕大在包括数字货币在内的数字资产世界的探索。赵长鹏回复表示，百慕大在拥抱区块链上走得前列。此前马耳他总理曾“隔空喊话”邀请币安落户该国，随后币安和捷克Changelly交易所在马耳他达成合作。[2018/4/28]
挖矿方程Ethash
区块链鼻祖比特币，是PoW共识，已经稳定运行10年。但在2011年开始，因为比特币有利可图，市场上出现了专业矿机专门针对哈希算法、散热、耗能进行优化，这脱离了比特币网络节点运行在成千上万的普通计算机中并公平参与挖矿的初衷。这容易造成节点中心化，面临51%攻击风险。因此，以太坊需要预防和改进PoW。因此在以太坊设计共识算法时，期望达到两个目的：
1.抗ASIC1性：为算法创建专用硬件的优势应尽可能小，理想情况是即使开发出专有的集成电路，加速能力也足够小。以便普通计算机上的用户仍然可以获得微不足道的利润。2.轻客户端可验证性:一个区块应能被轻客户端快速有效校验。
在以太坊早期起草的共识算法是Dagger-Hashimoto，由Buterin和Dryja提出。但被证明很容易受到SergioLerner共享内存硬件加速的影响。所以最终抛弃了Dagger-Hashimoto，改变研究方向。在对Dagger-Hashimoto进行大量修改，终于形成了明显不同于Dagger-Hashimoto的新算法：Ethash。Ethash就是以太坊1.0的挖矿方程。
介绍
这个算法的大致流程如下：
1.通过扫描区块头直到某点，来为每个区块计算得到一个种子Seed。2.根据种子可以计算一个初始大小为16MB的伪随机缓存cache。轻客户端保存这个cache,用于辅助校验区块和生成数据集。3.根据cache，可以生成一个初始大小为1GB的DAG数据集。数据集中的每个条目(64字节)仅依赖于cache中的一小部分条目。数据集会随时间线性增长，每30000个区块间隔更新一次。数据集仅仅存储在完整客户端和矿工节点，但大多数时间矿工的工作是读取这个数据集，而不是改变它。4.挖矿则是在数据集中选取随机的部分并将他们一起哈希。可以根据cache仅生成验证所需的部分，这样就可以使用少量内存完整验证，所以对于验证来讲，仅需要保存cache即可。
这里cache选择16MB缓存是因为较小的高速缓存允许使用光评估方法,太容易用于ASIC。16MB缓存仍然需要非常高的缓存读取带宽，而较小的高速缓存可以更容易地被优化。较大的缓存会导致算法太难而使得轻客户端无法进行区块校验。
选择初始大小为1GB的DAG数据集是为了要求内存级别超过大多数专用内存和缓存的大小，但普通计算机能够也还能使用它。数据集选择30000个块更新一次，是因为间隔太大使得更容易创建被设计为非常不频繁地更新并且仅经常读取的内存。而间隔太短，会增加进入壁垒，因为弱机器需要花费大量时间在更新数据集的固定成本上。
同时，缓存和数据集大小随时间线性增长，且为了降低循环行为时的偶然规律性风险，数据大小是一个不超过上限的素数。每年约以0.73倍的速度增长，这个增长速率大致同摩尔定律持平。这仍有越过摩尔定律的风险，将导致挖矿需要非常大量的内存，使得普通的GPU不再能用于挖矿。因为可通过使用缓存重新生成所需数据集的特定部分，少量内存进行PoW验证，因此你只需要存储缓存，而不需要存储数据集。
缓存和数据集大小
缓存c和数据集d的大小依赖用区块的窗口周期Eepoch。
每过一个窗口周期后，数据集固定增长8MB(223字节)，缓存固定增长128kb。为了降低循环行为时的偶然规律性风险，数据大小必须是一个素数。计算缓存大小公式：
计算数据大小公式：
其中，求素数公式如下：
这个素数计算是从不高于上限值中向下依次递减2*64字节递归查找，直到x/64是一个素数。
生成种子哈希值
种子seed实际是一个哈希值，每个窗口周期更新一次。它是经过多次叠加Keccak256计算得到的。
第一个窗口周期内的种子哈希值s是一个空的32字节数组，而后续每个周期中的种子哈希值，则对上一个周期的种子哈希值再次进行Keccak256哈希得到。
生成缓存cache
缓存cache生成过程中，是将cache切割成64字节长的若干行数组操作的。
先将种子哈希值的Keccak512结果作为初始化值写入第一行中；随后，每行的数据用上行数据的Keccak512哈希值填充；最后，执行了3次RandMemoHash算法。该生成算法的目的是为了证明这一刻确实使用了指定量的内存进行计算。
RandMemoHash算法可以理解为将若干行进行首尾连接的环链，其中n为行数。
每次RandMemoHash计算是依次对每行进行重新填充。先求第i行的前后两行值得或运算结果，再对结果进行Keccak512哈希后填充到第i行中。
最后，如果操作系统是Big-Endian(非little-endian)的字节序，那么意味着低位字节排放在内存的高端，高位字节排放在内存的低端。此时，将缓存内容进行倒排，以便调整内存存放顺序。最终使得缓存数据在内存中排序顺序和机器字节顺序一致。
生成数据集
利用缓存cache来生成数据集，首先将缓存切割成n个16bytes大小的单元。在生成过程中时将数据集切割为若干个64bytes大小的数据项，可对每项数据mix并发生成。最终将所有数据项拼接成数据集。
1.在生成index行的数据时，先从缓存中获取第index%n个单元的值u;
2.数据项mix长度64bytes，分割为4bytes的16个uint32。第一个uint32等于u^index，其他第i个uint32等于u+i;
3.用数据项mix的Keccak512哈希值覆盖mix；
4.对mix进行FNV哈希。在FNV哈希时，是要从缓存中获取256个父项进行运算。
1）确定第p个父项位置:FNV(index^p，mix)%n；2）再将FNV(mix,cache)的值填充到mix中；其中，FNV(x,y)=x*0x01000193^y；这里的256次计算，相当于mix的16个uint32循环执行了16次。
5.再一次用数据项mix的Keccak512哈希值覆盖mix；
6.如果机器字节序是Big-Endian的，则还需要交换高低位；
7.最后将mix填充到数据集中，即dataset=mix;
注意，在FNV哈希计算中，初始大小1GB数据集累积需要约42亿次次计算。即使并发计算，也需要一定的时间才能完成一次数据集生成。这也就是为什么在启动一个geth挖矿节点时，刚开始时会看到一段“GeneratingDAGinprogress”的日志，直到生成数据集完成后，才可以开始挖矿。
Ethash挖矿方程求解
准备好数据集dataset就可以用于工作量证明计算。依赖nonce、h、dataset可计算出的一个伪随机数N，工作量证明就是校验N是否符合难度要求。工作量计算由挖矿方程Ethash定义。
上图是Ethash的计算流程图。说明如下：
1.首先将传入的新区块头哈希值和随机数nonce拼接后进行KEC512哈希，得到64字节的种子seed；2.然后初始化一个128字节长的mix，初始化时分割成32个4字节的单元；使用128字节的顺序访问，以便每次Ethash计算都始终从RAM提取整页，从而最小化页表缓存未命中情况。理论上，ASIC是可以避免的；3.mix数组的每个元素值来自于seed;mix=s;是seed的第0、4、8...60位的值；4.紧接着完成64次循环内存随机读写。每次循环需要从dataset中取指定位置p和p+1上的两个16字节拼接成32字节的m；然后，使用fnv(mix,m)去覆盖mix;其中，i是循环索引、s是种子seed的前32字节、rows是表示数据集dataset可分成rows个128字节。5.然后压缩mix。压缩是将mix以每16字节分别压缩得到8个压缩项。每16字节又是4小份的fnv叠加哈希值fnv(fnv(fnv(m,m),m),m);6.拼接这8个压缩项就得到mix的哈希值mixHash;7.最后将seed和mixHash进行KEC256哈希得到伪随机数N；8.最终，返回这两个参数：mixHash和N；
本文链接：https://www.8btc.com/media/589432
转载请注明文章出处
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。