共计 4560 个字符，预计需要花费 12 分钟才能阅读完成。
Ethereum 当前和 Bitcoin 一样，采用基于工作量证明 (Proof of Work,PoW) 的共识算法来产生新的区块。与 Bitcoin 不同的是，Ethereum 采用的共识算法可以抵御 ASIC 矿机对挖矿工作的垄断地位，这个算法叫做 Ethash。
为什么要反 ASIC
PoW 的的核心是 Hash 运算，谁的 Hash 运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在 Bitcoin 的发展过程中，挖矿设备经历了 (CPU=>GPU=>ASIC) 的进化过程，其中的动机就是为了更快地进行 Hash 运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。因此，在共识算法设计时，为了减少 ASIC 矿机的优势 (专用并行计算)，Ethereum 增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是 ASIC 矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量 CPU 了)。即将挖矿算法从 CPU 密集型(CPU bound) 转化为 IO 密集型(I/O bound)
Dagger-Hashimoto
Ethash 是从 Dagger-Hashimoto 算法改动而来的，而 Dagger-Hashimoto 的原型是 Thaddeus Dryja 提出的 Hashimoto 算法，它在传统 Bitcoin 的工作量证明的基础上增加了消耗内存的步骤。
传统的 PoW 的本质是不断尝试不同的 nonce，计算 HASH$$hash\_output=HASH(prev\_hash,merkle_root,nonce)$$ 如果计算结果满足 $hash\_output<target$，则说明计算的 nonce 是有效的
而对于 Hashimoto，HASH 运算仅仅是第一步，其算法如下:
nonce: 64-bits. 正在尝试的 nonce 值
get_txid(T): 历史区块上的交易 T 的 hash
total_transactions: 历史上的所有交易的个数
hash_output_A = HASH(prev_hash,merkle_root,nonce)
for i = 0 to 63 do
shifted_A = hash_output_A >> i
transaction = shifted_A mod total_transactions
txid[i] = get_txit(transaction) << i
end of
txid_mix = txid[0]^txid[1]…txid[63]
final_output = txid_mix ^（nonce<<192)
可以看出，在进行了 HASH 运算后，还需要进行 64 轮的混淆 (mix) 运算，而混淆的源数据是区块链上的历史交易，矿工节点在运行此算法时，需要访问内存中的历史交易信息(这是内存消耗的来源)，最终只有当 $final\_output < target$ 时，才算是找到了有效的 nonce
Dagger-Hashimoto 相比于 Hashimoto，不同点在于混淆运算的数据源不是区块链上的历史交易，而是以特定算法生成的约 1GB 大小的数据集合(dataset)，矿工节点在挖矿时，需要将这 1GB 数据全部载入内存。
Ethash 算法概要
矿工挖矿不再是仅仅将找到的 nonce 填入区块头，还需要填入一项 MixDigest，这是在挖矿过程中计算出来的，它可以作为矿工的确在进行消耗内存挖矿工作量的证明。验证者在验证区块时也会用到这一项。
先计算出约 16MB 大小的 cache，约 1GB 的 dataset 由这约 16MB 的 cache 按特定算法生成，dataset 中每一项数据都由 cache 中的 256 项数据参与生成，cache 中的这 256 项数据可以看做是 dataset 中数据的 parent。只所以是约，是因为其真正的大小是比 16MB 和 1GB 稍微小一点(为了好描述，以下将省略约)
cache 和 dataset 的内容并非不变，它每隔一个 epoch(30000 个区块)就需要重新计算
cache 和 dataset 的大小并非一成不变，16MB 和 1GB 只是初始值，这个大小在每年会增大 73%, 这是为了抵消掉摩尔定律下硬件性能的提升，即使硬件性能提升了，那么最终计算所代表的工作量不会变化很多。结合上一条，那么其实每经过 30000 个区块，cache 和 dataset 就会增大一点，并且重新计算
全节点 (比如矿工) 会存储整个 cache 和 dataset，而轻客户端只需要存储 cache。挖矿 (seal) 时需要 dataset 在内存中便于随时存取，而验证 (verify) 时，只需要有 cache 就行，需要的 dataset 临时计算就行。
Ethash 源码解析
dataset 生成
dataset 通过 generate()方法生成，首先是生成 cache，再从 cache 生成 dataset
挖矿(Seal)
在挖矿与共识中提到了，共识算法通过实现 Engine.Seal 接口，来实现挖矿,Ethash 算法也不例外。其顶层流程如下:
Seal 调用中，启动一个 go routine 来调用 ethash.mine()进行实际的挖矿，参数中的 block 是待挖掘的区块(已经打包好了交易)，而 nonce 是一个随机值，作为挖矿过程尝试 nonce 的初始值。
mine()调用首先计算后续挖矿需要的一些变量。hash 为区块头中除了 nonce 和 mixdigest 的 Hash 值，dataset 为挖掘这个区块时需要的混淆数据集合(占用 1GB 内存),target 是本区块最终 Hash 需要达到的目标，它与区块难度成反比
对本次尝试的 nonce 进行 hashmotoFull()函数计算最终 result(最终 Hash 值)和 digest，如果满足 target 要求，则结束挖矿，否则增加 nonce，再调用 hashmotoFull()
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
lookup := func(index uint32) []uint32 {
offset := index * hashWords
return dataset[offset : offset+hashWords]
}
return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}
hashmotoFull()是运算的核心，内部调用 hashmoto()，第三个参数为 dataset 的大小（即 1GB）, 第四个参数是一个 lookup 函数，它接收 index 参数，返回 dataset 中 64 字节的数据。
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
// 将 dataset 划分为 2 维矩阵，每行 mixBytes=128 字节，共 1073739904/128=8388593 行
rows := uint32(size / mixBytes)
// 将 hash 与待尝试的 nonce 组合成 64 字节的 seed
seed := make([]byte, 40)
copy(seed, hash)
binary.LittleEndian.PutUint64(seed[32:], nonce)
seed = crypto.Keccak512(seed)
seedHead := binary.LittleEndian.Uint32(seed)
// 将 64 字节的 seed 转化为 32 个 uint32 的 mix 数组(前后 16 个 uint32 内容相同)
mix := make([]uint32, mixBytes/4)
for i := 0; i < len(mix); i++ {
mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])
}
temp := make([]uint32, len(mix))
// 进行总共 loopAccesses=64 轮的混淆计算，每次计算会去 dataset 里查询数据
for i := 0; i < loopAccesses; i++ {
parent := fnv(uint32(i)^seedHead, mix[i%len(mix)]) % rows
for j := uint32(0); j < mixBytes/hashBytes; j++ {
copy(temp[j*hashWords:], lookup(2*parent+j))
}
fnvHash(mix, temp)
}
// 压缩 mix：将 32 个 uint32 的 mix 压缩成 8 个 uint32
for i := 0; i < len(mix); i += 4 {
mix[i/4] = fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])
}
mix = mix[:len(mix)/4]
// 用 8 个 uint32 的 mix 填充 32 字节的 digest
digest := make([]byte, common.HashLength)
for i, val := range mix {
binary.LittleEndian.PutUint32(digest[i*4:], val)
}
// 对 seed+digest 计算 hash，得到最终的 hash 值
return digest, crypto.Keccak256(append(seed, digest…))
}
验证(Verify)
验证时 VerifySeal()调用 hashimotoLight()，Light 表明验证者不需要完整的 dataset，它需要用到的 dataset 中的数据都是临时从 cache 中计算。
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
keccak512 := makeHasher(sha3.NewKeccak512())
//lookup 函数和 hashimotoFull 中的不同，它调用 generateDatasetItem 从 cache 中临时计算
lookup := func(index uint32) []uint32 {
rawData := generateDatasetItem(cache, index, keccak512) // return 64 byte
data := make([]uint32, len(rawData)/4) // 16 个 uint32
for i := 0; i < len(data); i++ {
data[i] = binary.LittleEndian.Uint32(rawData[i*4:])
}
return data
}
return hashimoto(hash, nonce, size, lookup)
}
除了 lookup 函数不同，其余部分 hashimotoFull 完全一样
总结
Ethash 相比与 Bitcoin 的挖矿算法，增加了对内存使用的要求，要求矿工提供在挖矿过程中使用了大量内存的工作量证明, 最终达到抵抗 ASIC 矿机的目的。
参考资料
1 Ethash-Design-Rationale2 what-actually-is-a-dag3 why-dagger-hashimoto-for-ethereum
