以太坊之六挖矿算法
正在学习区块链，如果我哪里有错误希望大家指出，如果有任何想法也欢迎留言。这些笔记本身是在typora上写的，如果有显示不正确的敬请谅解。笔记本身也是给我自己写的，所以如果有侵权的请通知我，我立即删除。
6.挖矿算法 6.1 scrypt算法PoW本身是为了能让记账权能够随机分给各个节点而产生的，但是现在有人用了专用的ASIC芯片，而且迭代速度非常快，把挖矿当做一种职业已经普及开了，这已经违背了PoW的初衷。中本聪用比特币是当作一种去中心化的加密货币，可以理解为电子黄金的投资或者保值类产品。所以需要使用一种ASIC resistance的算法，即抵抗ASIC。如果降低了对计算速度的要求，就要提升对内存的要求，即memory hard mining puzzle。莱特币使用的是scrypt算法。
有一个数组x，先用一个伪随机数seed求完哈希后放入x[0]中，再求x[i+1]=HASH(x[i])，直至把整个数组填满了，这个数组是个待查的表。实际使用的时候先找到A，通过对A求哈希能够找到B，再通过B的哈希找到C，直至最后找到结果。如果不用这个表，B那个数值是多少就要从数组头开始求，C的时候再通过数组头找，效率就会很低，这样就由时间的问题转换到了空间问题。
这个开头的数必须是伪随机数，肖老师说要么后续没法查了。
有的矿工只存储奇数位置的值，偶数位置的用奇数的算一步就行了。
scrypt算法的缺点也是空间，轻节点在验证的时候也需要维护这个数组。如果是电脑维护1G的数组还是挺简单的，但是如果是手机开销可就大了。不过莱特币本身是没有轻全节点的区分。
6.2 以太坊挖矿算法ethash原理以太坊中有两个数组，一个是cache一个是dataset（也叫DAG），初始时cache有16M，dataset有1G。轻节点仅维护cache，全节点两个都维护。两个数组每3万个区块增大一次，增大原来的1/128，也就是变为原来的一又一百二十八分之一，因为内存技术也是在逐渐增大中。
使用的时候先用一个伪随机的种子seed按照顺序生成这个数组，第0个数时seed的哈希值，第1个数是第0个数的哈希值，依此类推。生成cache的过程较为繁琐，遍历每个dataset的位置，用一种方法找到cache中对应的下标（这个方法是用dataset的下标对cache的元素个数取余再进行异或，我也不知道为什么异或，下面有写），当然也就找到了对应的哈希值，假设是A。接着用A找到B，再找到C，连续执行256次，就得到了dataset中的这个元素。
这个dataset怎么用呢？用一种特别的方法遍历这个dataset（这个方法我就不写了，代码有），遍历的同时生成哈希，最终遍历完整个dataset后得到的哈希就是结果，是要挖矿的时候验证target啊，还是其它节点验证结果啊，就都可以了。
下面这个函数用于根据seed生成cache的伪代码。每隔3万个区块会重新生成新的seed（新seed是对原来的seed求哈希值），并根据新的seed生成新的cache。cache的初始大小为16M，每隔3万个区块重新生成时增大初始大小的1/128，即128K。每个节点的哈希值是前一个节点哈希的结果，cache_size就是cache数组的大小，seed就是伪随机数种子。
def mkcache(cache_size, seed):
o = [hash(seed)]
for i in range(1, cache_size):
o.append(hash(o[-1]))
return o
下面这个函数用于根据cache遍历full_size生成dataset。full_size自然是dataset的数组大小，cache就是cache数组。这个dataset叫做DAG，初始大小是1G，也是每隔3万个块更新，同时增大初始大小的1/128，即8M。
def calc_dataset(full_size, cache):
return [calc_dataset_item(cache,i) for i in range(full_size)]
下面这个函数用于遍历dataset的每一位来生成dataset，cache就是整个cache数组。（这句话是我抄的）先通过cache中的第i%cache_size个元素生成初始的mix，因为两个不同的dataset元素可能对应同一个cache中的元素，为了保证每个初始的mix都不同，注意到i也参与到了哈希计算中。get_int_from_item()函数的作用是当前的哈希值求出下一个要读取的位置。make_item()用刚刚的cache索引和哈希值求出下一个哈希值。cache中的数据做256次哈希，返回结果，这个结果可以存到dataset里。
def calc_dataset_item(cache, i):
cache_size = cache.size
mix = hash(cache[i % cache_size] ^ i)
for j in rage(256):
cache_index = get_int_from_item(mix)
mix = make_item(mix, cache[cache_index % cache_size])
return hash(mix)
下面第一个是全节点，第二个是轻节点的，返回哈希值。全节点和轻节点的区别就是轻节点是不存储dataset的，每个数值是现求的。轻节点是用来验证nonce是否有效，全节点是用来挨个尝试nonce。header是当前要生成的区块的块头，nonce是尝试的数字，full_size是dataset的大小，这个值3万个区块改一次，增加1G的1/128即8M。以太坊和比特币一样挖矿只用块头的信息，因为这样能够实现轻节点仅用块头就可以验证。我在看代码的时候有点问题，for循环中mix的值被不停的修改，return的只能是最后一个结果，那执行两次make_item()还有什么意义？第5行的mix也是第6行的参数，总之就是用一种既定的方式遍历dataset，直至求出最终哈希的结果。
def hashimoto_full(header, nonce, full_size, dataset)
mix = hash(header, nonce)
for i in range(64):
dataset_index = get_int_from_item(mix) % full_size
mix = make_item(mix, dataset[dataset_index])
mix = make_item(mix, dataset[dataset_index + 1])
return hash(mix)
def hashimoto_light(header, nonce, full_size, cache)
mix = hash(header, nonce)
for i in range(64):
dataset_index = get_int_from_item(mix) % full_size
mix = make_item(mix, calc_dataset_item(cache,dataset[dataset_index]))
mix = make_item(mix, calc_dataset_item(cache,dataset[dataset_index + 1]))
return hash(mix)
下面的函数用于挖矿，寻找满足target的节点。具体内容不用说了。
def mine(full_size, dataset, header, target):
nonce = random.randint(0,2**64)
while hashimoto_full(header, nonce, full_size, dataset) > target
nonce = (nonce + 1) % 2**64
return nonce
6.4 ASIC resistance
以太坊为了实现ASIC resistance，打算把PoW转换为PoS，即工作量转换为权益证明，不过它们一直没实现，实现的时间点一直在后推。因为ASIC芯片的研发周期大约1年，以太坊就不停的吓唬矿机生产商：我们要做权益证明了哈，搞的矿机生产商不敢大幅度生产。事实证明很有效，以太坊中ASIC芯片确实不多，没有比特币那么泛滥，可能也跟ethash有关。
到底要不要设计抵抗ASIC芯片的算法呢？抵抗后，就越能让通用设备参加挖矿。以太坊和莱特币是这么做的。持正方态度的是因为参加挖矿的设备越普通，参加挖矿的人越多，挖矿的结果越民主，区块链越安全。反方觉得ASIC芯片使挖矿的成本大幅度提高，首先ASIC芯片的研发周期大约1年，能让该芯片占有统治地位的时间也很短，而且专为某一种币挖矿而设计的ASIC芯片还不能用于另一种币。如果有人需要发动攻击需要购买大量的ASIC矿机，攻击后很可能会导致币的价格大幅下跌，这就是完全费力不讨好的事。如果让很多通用设备能够参与挖矿，像亚马逊和阿里云那种云计算超级强的公司，它们在全球服务器的数量可能已经够攻击币了。虽然这些钱可能对那些公司来说不算什么，但是如果他们觉得以太坊的某些记录或者什么数据威胁到了他们，他们完全可以集中算力干掉以太坊，服务器再继续出租，大大降低了51%的成本。
作者：蓝莓侠
