以太坊源码分析—Ethash共识算法
青丝暮雪780
发表于 2023-1-3 17:15:57
99
0
0
为什么要反ASIC
PoW的的核心是Hash运算,谁的Hash运算更快,谁就更有可能挖掘出新的区块,获得更多的经济利益。在Bitcoin的发展过程中,挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程,其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高,参与者久越来越少,这与区块链的去中心化构想背道而驰。
因此,在共识算法设计时,为了减少ASIC矿机的优势(专用并行计算),Ethereum增加了对于内存的要求,即在进行挖矿的过程中,需要占用消耗大量的内存空间,而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了,即使配置,这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)5 X! d2 a9 n7 Y/ g: v
Dagger-Hashimoto. Q& r7 { N- z- [+ U9 ^4 |# Y
Ethash是从Dagger-Hashimoto算法改动而来的,而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法,它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
传统的PoW的本质是不断尝试不同的nonce,计算HASH
hash_output=HASH(prev_hash,merkleroot,nonce)
如果计算结果满足$hash_output
而对于Hashimoto,HASH运算仅仅是第一步,其算法如下:6 }2 K$ J1 |4 [% [
nonce: 64-bits.正在尝试的nonce值
get_txid(T):历史区块上的交易T的hash K- k5 L- m- k, x
total_transactions: 历史上的所有交易的个数
hash_output_A = HASH(prev_hash,merkle_root,nonce)
for i = 0 to 63 do 8 K- n5 s7 z' M8 F8 @& {
shifted_A = hash_output_A >> i1 P0 z4 c: M# y0 |; J
transaction = shifted_A mod total_transactions
txid = get_txit(transaction) 4 j8 R. V9 b6 ?% U0 F. g6 O
可以看出,在进行了HASH运算后,还需要进行64轮的混淆(mix)运算,而混淆的源数据是区块链上的历史交易,矿工节点在运行此算法时,需要访问内存中的历史交易信息(这是内存消耗的来源),最终只有当 $final_output $ H+ q& P- J5 z3 j
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临时计算就行。+ N! N5 U9 f: E5 T* m2 N
Ethash源码解析
dataset生成# O. Z- Q" ~5 \3 B" e
dataset通过generate()方法生成,首先是生成cache,再从cache生成dataset
挖矿(Seal)# A' X- m& C; m! f" x
在挖矿与共识中提到了,共识算法通过实现Engine.Seal接口,来实现挖矿,Ethash算法也不例外。; l* U0 {" Q" p
其顶层流程如下:
7 k' o! g/ n5 d5 S; ~
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()! M$ c4 {$ B/ {5 \
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {5 F2 q8 { r4 r# [
lookup := func(index uint32) []uint32 {
offset := index * hashWords
return dataset[offset : offset+hashWords]) \7 I+ [* z" U8 h% e
}
return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)$ t3 W+ H# W$ A$ Y( `4 a
}
hashmotoFull()是运算的核心,内部调用hashmoto(),第三个参数为dataset的大小(即1GB),第四个参数是一个lookup函数,它接收index参数,返回dataset中64字节的数据。: A; _$ X8 g4 a5 g
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {$ Q2 J; D" e: v
// 将dataset划分为2维矩阵,每行mixBytes=128字节,共1073739904/128=8388593行; c/ ~9 ?- `/ s! G/ i3 F
rows := uint32(size / mixBytes)1 B. I1 |9 e* Q, o' ^
// 将hash与待尝试的nonce组合成64字节的seed: W$ }* V$ I! l' W# ~
seed := make([]byte, 40)( ^5 B( U8 j) B& y5 w
copy(seed, hash)& ^) y+ b6 [5 p/ P' W C
binary.LittleEndian.PutUint64(seed[32:], nonce)2 }) j, E0 ^/ l" {8 J$ g% ^: c+ a
seed = crypto.Keccak512(seed)
seedHead := binary.LittleEndian.Uint32(seed)7 Q2 R* ]8 w) f' j
// 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
mix := make([]uint32, mixBytes/4)
for i := 0; i 3 p% U8 ?/ G5 w) r% ?
验证(Verify): X* _5 v; \4 \. I- V
验证时VerifySeal()调用hashimotoLight(),Light表明验证者不需要完整的dataset,它需要用到的dataset中的数据都是临时从cache中计算。8 m+ t- x8 o) n+ A6 }
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
keccak512 := makeHasher(sha3.NewKeccak512())9 e, ^ z) t' x- G2 T' b
//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# p5 H2 }* v: X' F
for i := 0; i
除了lookup函数不同,其余部分hashimotoFull完全一样, G* I+ v4 v1 ]. S
总结
Ethash相比与Bitcoin的挖矿算法,增加了对内存使用的要求,要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。
. Q) S/ z6 t; z9 d1 Y6 ^6 n
成为第一个吐槽的人