北大-区块链技术与应用19-ETH挖矿算法

Block chain is secured by mining（挖矿保障了区块链的安全性），比特币的挖矿算法是一个天然的 bug bounty（悬赏找bug），如果能找到漏洞或挖矿的捷径（shortcut）就能获取很大的利益

很多人认为，挖矿设备的专业化 和比特币的去中心化理念是相违背的（one cpu, one vote），普通人能够参与挖矿有利于分散算力，预防 51% attack。所以后续的加密货币设计 mining puzzle 的一个理念是 ASIC resistance

设计 ASIC resistance 的 mining puzzle 的常用做法是：增加 puzzle 对内存访问的需求，即 memory hard mining puzzle，因为 ASIC 芯片计算能力强，但是在内存访问的性能上没有很大的优势

一、LiteCoin & Scrypt

一个早期的例子是 LiteCoin（莱特币），曾经是市值仅次于比特币的加密货币，其 mining puzzle 基于 scrypt

Scrypt 是一个对内存要求很高的哈希函数，设计思想是：开设一个很大的数组，按照顺序填充一些伪随机数；具体过程是：按照一个 seed 的值，运算出一个数填在第一个位置，后面每个位置都是前一个位置取哈希得到的；其特点是里面的取值是有前后依赖关系的；求解 puzzle 时，按照伪随机的顺序从数组中读取一些数（通过对当前数运算得到下一个读取顺序，模拟随机）；好处是：如果数组开得足够大，对于矿工来说就是 memory hard 的，有的矿工可能保存一部分内存区域的内容，比如只保留奇数位置的数，需要读取到偶数再算，这也叫做 time-memory trade off（时间换空间）

其坏处是：对于轻节点验证来说也是 memory hard，不符合 difficult to solve, but easy to verify。所以其实际使用过程中，数组只有 128k，不足以对 ASIC 芯片造成遏制，但该理念对其冷启动有很大帮助（需要冷启动是因为，参与挖矿的人太少很容易遭受恶意攻击），所以莱特币现在仍然是主流货币

莱特币的出块时间是两分半，速度是比特币的四倍，其他部分和比特币基本相同

二、以太坊 memory hard

以太坊的挖矿算法叫做 ethash，矿工挖矿需要 1G 的内存，和莱特币的 128k 比，大了 8000 多倍，光是 cashe 就大了 100 多倍；更别说现在内存要求还在增长

以太坊使用一大一小两个数据集：16M 的 cache 和 1G 的dataset，轻节点只要保存 cache，矿工才需要保存 1G 的大数据集

1、具体算法

算法太复杂了，没完全搞明白，具体算法的伪代码可参考课程视频（28分）：

https://www.bilibili.com/video/BV1Vt411X7JF?spm_id_from=333.788.player.switch&vd_source=69ac93649ea21c4726fe85f272b6d968&p=19

cache 的生成方式和 scrypt 类似，但是不同于莱特币从数组中按照伪随机的顺序读取并进行运算，以太坊是需要先生成一个更大的数组（dataset 要大得多），而且 cache 和 dataset 是定期增长的，因为计算机的内存容量也在增长

dataset 中的每个元素都是从 cache 中按照伪随机的顺序读取一些元素（和莱特币类似），一共读 256 次，用这 256 个数算出一个数，作为 dataset 的第一个元素，后续元素也一样

求解 puzzle 时只使用 dataset 中的数，按照伪随机的顺序，从大数据集中读取 128 个数：一开始根据区块的块头、包括其中的 nonce 值，算出一个初始的哈希，然后根据该哈希映射到这个大数据集中的某个位置，将其中的数读取出来（同时将其相邻的元素读取出来），然后进行一些运算算出下一个位置，总共进行 64 次循环，共读取 128 个数。最后算出一个哈希值，和挖矿难度的目标域值比较，看是否符合要求，如果不符合，更换 nonce 之后再重新计算

2、矿工保存 dataset 的原因

由于矿工需要验证非常多的 nonce，如果每次都从 16M 的 cache 中重新生成，挖矿的效率就太低了，并且其中有大量的重复计算（因为随机选取的 dataset 的元素中有很多是重复的，可能是之前尝试别的 nonce 时用过的）。所以矿工采取空间换时间的策略，保存整个 dataset

3、轻节点只保存 cache 的原因

轻节点由于只验证一个 nonce，验证时直接生成要用到的 dataset 中的元素即可

和比特币相比，以太坊中验证一个 nonce 的计算量要大很多，但也在可接受范围内

目前以太坊挖矿还是以 GPU 为主，所以起到了 ASIC resistance

三、以太坊 POS

以太坊没有出现 ASIC 矿机的另一个原因是，以太坊2.0（或以太坊合并）已经于 2022年 从 POW 转向 POS（Power of Stake，权益证明），即按照所占的权益进行投票从而形成共识，而不是挖矿，类似于股份制公司按照股份多少来投票

这对于 ASIC 厂商是很大的威胁，因为其研发周期很长（1年都算快的），并且研发成本也很高，如果后续不挖矿了，那么所有投入都白费了

四、预挖矿

以太坊采用了 pre-mining（预挖矿），在当初发行货币的时候，预留一部分货币给以太坊的开发者，类似创业公司留一部分股票给创始人和早期员工；而比特币没有采用 pre-mining 的模式，都是挖矿挖出来的

Pre-sale（预售） 就是把 pre-mining 中预留的币，通过出售的方法来换取一些资产，用于加密货币的开发工作

但有一些人认为，让通用计算设备参与挖矿反而是不安全的，用 ASIC 芯片挖矿才是最安全的，因为购买矿机需要大量的资金，并且只能用于一种加密货币，成本较高