北京大学肖臻老师《区块链技术与应用》公开课笔记(十九)：ETH挖矿算法
在之前的BTC篇中，介绍了比特币系统中使用的挖矿算法。挖矿这一过程，虽然并没有创造什么实际价值，但挖矿本身维持了比特币系统的稳定，Block chain is secured by mining。总体来说，比特币系统中的挖矿算法较为成功，并未发现大的漏洞。
当然，比特币系统的挖矿算法也存在一定问题，其中最为突出的就是导致了挖矿设备的专业化，普通计算机用户难以参与进去，导致了挖矿中心化的局面产生，而这与“去中心化”这一理念相违背(初衷是one cpu,one vote)。因此，在比特币之后包括以太坊在内的许多加密货币针对该缺陷进行改进，希望做到ASIC Resistance(抗拒ASIC专用矿机)。由于ASIC芯片相对普通计算机来说，算力强但访问内存性能差距不大，因此常用的方法为Memory Hard Mining Puzzle，即增加对内存访问的需求，早期的一个例子就是莱特币
LiteCoin(莱特币)
莱特币曾一度成为市值仅次于比特币的第二大货币。其基本设计大体上和比特币一致，但针对挖矿赛诺菲进行了修改。
莱特币的puzzle基于Scrypt。Scrypt为一个对内存性能要求较高的哈希函数，之前多用于计算机安全密码学领域。
莱特币挖矿算法基本思想
- 首先设置一个很大的数组，按照顺序填写伪随机数
seed为种子节点，通过seed进行一些运算获得一个值填到数组的第一个位置，之后的元素都是前一个元素取hash得到的。所以数组中的元素是有前后依赖关系的。
为什么叫伪随机？
因为hash函数的运算结果并不能提前预料，所以看上去就像是一系列的随机数，但不是真的随机，因为真随机没法验证，所以叫伪随机数
- 在需要求解Puzzle的时候，按照伪随机顺序，从数组中读取一些数，每次读取位置与前一个数相关。例如：第一次，从A位置读取其中数据，根据A中数据计算获得下一次读取位置B；第二次,从B位置读取其中数据，根据B中数据计算获得下一次读取位置C；
分析
如果这个数组设置的足够大，大到计算n次hash值所需时间远远大于从内存中取一个数的时间，那么挖矿的矿工必须事先存储这个数组，否则每次不仅计算位置，还要根据Seed计算整个数组数据，才能查询到对应位置的数据，时间复杂度大幅度上升。
当然，矿工可以选择只保存一部分数据，例如：只保存奇数位置数据，偶数位置需要时再根据前一个奇数位置数据计算即可，从而对内存空间大小减少了一半(时间换空间，time-memory trade off)。
核心思想：puzzle不能只涉及运算，还要增加其对内存的访问，从而实现对ASIC芯片不友好。
这个idea有问题吗？看似蛮不错的，使得ASIC矿机挖矿变得不友好，但是对轻节点也是memory hard。我们设计puzzle的原则是difficult to solve,but easy to verify，求解和验证所需的内存区域是一样大的，之前Scrypt用于计算机安全领域是没有这个问题的，因为不存在轻节点验证的问题，但切换到挖矿环境来，就暴露出了这个问题。比如我们在手机app(轻节点)上想要验证该puzzle，是很困难的，需要存储该数组(系统中绝大多数节点为轻节点)。
因此，莱特币真正应用来说，数组大小不敢设置太大。例如：对于计算机而言，1G毫无压力，而对于手机APP来说，1G占据空间就过大了。所以，实际中，莱特币系统设计的数组大小仅仅128K大小。起初莱特币发行时，不仅希望能够抗拒ASIC，还希望能抗拒GPU。但实际中，后来慢慢出现了GPU挖矿，再后来，ASIC芯片挖矿也出现了。实际应用中，莱特币的设计并未起到预期作用，也就是说，128K对于ASIC Resistance来说过小了。
莱特币的这一设计是好事还是坏事？
从其并未起到预期作用来看，当然是一件坏事，但换个角度来思考，早期通过宣传这一设计目标，有效吸引了大批矿工参与，解决了莱特币“能启动”问题，因此目前莱特币仍然是一个较为主流的加密货币。
此外，莱特币和比特币另一区别为出块时间，莱特币为2.5min，为比特币的1/4。除了这些不同外，这两种货币基本一样。
以太坊
以太坊的理念与莱特币相同，都是Memory Hard Mining Puzzle，但具体设计上与莱特币不同
以太坊挖矿算法基本思想
以太坊中，设计了两个数据集，一大一小。小的为16MB的cache，大的数据集为1G的dataset(DAG)。其关系为，1G的数据集是通过16MB数据集生成而来的，并且两个数据集都要定期变大(每3W个区块增大1/128)
为何要设计一大一小两个数据集？
为了便于进行验证，轻节点保存16MB的Cache进行验证即可，而矿工为了挖矿更快，减少重复计算则需要存储1GB大小的大数据集。
cache
16MB的小Cache数据生成方式与莱特币中生成方式类似，通过Seed进行一些运算获得第一个数，之后每个数字都是通过前一个位置的值取哈希获得的
DAG
DAG中每个元素都是从小数组中生成的，每个位置以某个cache的元素为初始值，经过一系列运算得到DAG中某位置的值。如A作为DAG的i位置的对应cache的初始值，第一次读取A位置数据，对当前哈希值更新迭代算出下一次读取位置B，再进行哈希值更新迭代计算出C位置元素。如此来回迭代读取256次，最终算出一个数作为DAG中第i位置元素的值，如此类推，DAG中每个元素生成方式都依次类推。
分析
轻节点只保存小的cache，因为DAG中所有的元素都是由cache中某个元素经过运算得到的，验证时通过计算得到DAG的值即可。但对于挖矿来说，如果这样则大部分算力都花费在了通过Cache计算DAG上面，因此，其必须保存大的数组DAG以便于更快挖矿。
以太坊挖矿过程：
根据区块block header和其中的nonce值计算一个初始哈希，根据其映射到DAG的某个初始位置A，读取A位置的数及其相邻的后一个位置A’上的数,根据该两个数进行运算，算得下一个位置B，读取B和B’位置上的数，依次类推，迭代读取64次，共读取128个数。
最后一次迭代得到的数，计算出一个哈希值与挖矿难度目标阈值比较，若不符合就重新更换nonce，重复以上操作直到最终计算哈希值符合难度要求或当前区块已经被挖出。
伪代码理解以太坊挖矿算法
生成cache数组
第一个元素是种子的hash，剩下的元素是前一个元素的hash
生成DAG
挖矿算法与验证算法
矿工的挖矿算法hashimoto_full与轻节点验证算法hashimoto_light
以太坊和比特币一样，挖矿只用到区块的块头，这样轻节点只需要有块头就可以验证区块是否符合要求。
并且算法中每次迭代取的DAG中两个相邻位置的值，这两个位置的值是没有关联的，实际上DAG中所有元素的值都是独立生成，没有关联。
总结
目前以太坊挖矿以GPU为主，可见其设计较为成功，这与以太坊设计的挖矿算法(Ethash)所需要的大内存具有很大关系。
1G的大数组与128k相比，差距8000多倍，即使是16MB与128K相比，也大了一百多倍，可见对内存需求的差距很大(况且两个数组大小是会不断增长的)。
当然，以太坊实现ASIC Resistance除了挖矿算法设计之外，还存在另外一个原因，即其预期从工作量证明(POW)转向权益证明(POS)
权益证明(POS: Proof of State)
权益证明：按照所占权益投票进行共识达成，类似于股份制有限共识按照股份多少投票，权益证明不需要挖矿。
而这对于ASIC矿机厂商来说，就好比一把悬在头上的达摩克利斯之剑。因为ASIC芯片研发周期很长，成本很高，如果以太坊转入权益证明，这些投入的研发费用将全部白费(ASIC矿机只能用于挖特定的加密货币)
但实际上，以太坊目前仍然是POW挖矿共识机制(2022年启动了权益证明)。在设计之初，以太坊开发者就设想要从POW转向POS，并为了防止有矿工不愿意转埋下了一颗“难度炸弹”。但截至目前，以太坊仍然基于POW共识机制
预挖矿(Pre-Mining)
以太坊中采用的预挖矿的机制。这里“预挖矿”并不挖矿，而是在开发以太坊时，给开发者预留了一部分货币。以太坊的早期开发者，目前就很有钱了。
而比特币并未采用这一模式，所有比特币都是通过挖矿产生的。但早期挖矿难度容易，所有中本聪本人本来就有很多币。和Pre-Mining对应，还有Pre-Sale，Pre-Sale指的是将预留的货币出售掉用于后续开发，类似于拉风投或众筹。目前，各类加密货币很多，存在一部分货币就在采用Pre-Sale来获取资金，如果此时买入，后续如果该货币取得成功，同样可以获得很大收益，但真正成功的货币只占少数，这就是其风险性。
以太坊统计数据
以太坊中以太币供应量(2018年)
最大的25个矿池挖矿算力比重(2018年)
可见集中化现象依旧很严重
以太币价格变化情况(至2018年)
以太币市值变化情况(至2018年)
以太币Hash Rate变化情况(至2018年)
其他观点
本篇中挖矿算法设计一直趋向于让大众参与，这一才是公平的。且由于参与人员的分散，算力分散，也进一步使得系统更安全。
但同样一件事物，从不同观点看就有不同的看法。也有人认为让普通计算机参与挖矿是不安全的，像比特币那样，让中心化矿池参与挖矿才是安全的。为什么呢？
因为要攻击系统，需要购入大量只能进行特定货币挖矿的矿机通过算力进行强行51%攻击，而攻击成功后，必然导致该币种的价值跳水，攻击者投入的硬件成本将会全部打水漂。而如果让通用计算机也参与挖矿，发动攻击成本便大幅度降低，目前的大型互联网公司，将其服务器聚集起来进行攻击即可，而攻击完成后这些服务器仍然可以转而运行日常业务。因此，也有人认为，在挖矿上面，ASIC矿机“一统天下”才是最安全的方式。
