以太坊源码分析—Ethash共识算法

43次阅读

共计 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

正文完
 0