以太坊源码分析 Ethash共识算法 Ethereum 和 Bitcoin 都是采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与 Bitcoin 不同的是,Ethereum 采用的共识算法可以抵御 ASIC 矿机对挖矿工作的垄断地位,这个算法叫做 Ethash。 ASIC(Application Specific Integrated Circuit)即专用集成电路,是指应特定用户要求和特定电子系统的需要而设计、制造的集成电路。ASIC 矿机针对 HASH 算法进行了专门的设计。 1. 为什么要反ASIC PoW 的的核心是 Hash 运算,谁的 Hash 运算更快,谁就更有可能挖掘出新的区块,获得更多的经济利益。在 Bitcoin 的发展过程中,挖矿设备经历了 CPU=>GPU=>ASIC 的进化过程,其中的动机就是为了更快地进行 Hash 运算。随着矿机门槛地提高,参与者久越来越少,这与区块链的去中心化构想背道而驰。 因此,在共识算法设计时,为了减少 ASIC 矿机的优势(专用并行计算),Ethereum 增加了对于内存的要求,即在进行挖矿的过程中,需要占用消耗大量的内存空间,而这是 ASIC 矿机不具备的(配置符合运算那能力的内存太贵了,即使配置,这也就等同于大量 CPU 了)。即将挖矿算法从 CPU 密集型(CPU bound)转化为 IO 密集型(I/O bound)。 2. 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: 正在尝试的 nonce 64-bits值 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 = get_txit(transaction) << i end for 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 数据全部载入内存。 3. Ethash算法概要
4. Ethash源码解析4.1 dataset生成 dataset 通过 generate() 方法生成,首先是生成 cache,再从 cache 生成 dataset。 4.2 挖矿(Seal)在挖矿与共识中提到了,共识算法通过实现 Engine.Seal 接口,来实现挖矿。Ethash算法也不例外,顶层流程如下:
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 = 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, 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...)) } 4.3 验证(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 = binary.LittleEndian.Uint32(rawData[i*4:]) } return data } return hashimoto(hash, nonce, size, lookup) } 除了 lookup 函数不同,其余部分 hashimotoFull 完全一样。 5. 总结 Ethash 相比与 Bitcoin 的挖矿算法,增加了对内存使用的要求,要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗 ASIC 矿机的目的。 |
2. 盗版,破解有损他人权益和违法作为,请各位站长支持正版!