Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

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

青丝暮雪780
68 0 0
Ethereum当前和Bitcoin一样,采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是,Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位,这个算法叫做Ethash。
$ p  }1 F+ ^  k6 }为什么要反ASIC* E9 ]* K: P2 P: Y. O- }- S6 ]
PoW的的核心是Hash运算,谁的Hash运算更快,谁就更有可能挖掘出新的区块,获得更多的经济利益。在Bitcoin的发展过程中,挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程,其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高,参与者久越来越少,这与区块链的去中心化构想背道而驰。
( y- S* [. r/ H9 V' S3 N* R因此,在共识算法设计时,为了减少ASIC矿机的优势(专用并行计算),Ethereum增加了对于内存的要求,即在进行挖矿的过程中,需要占用消耗大量的内存空间,而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了,即使配置,这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
* e$ u+ \2 j" x: ~" DDagger-Hashimoto
- g1 x3 y2 L0 D4 M) x! l  ]Ethash是从Dagger-Hashimoto算法改动而来的,而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法,它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
9 p! Q1 Z  L3 x- ]) L传统的PoW的本质是不断尝试不同的nonce,计算HASH
7 {1 k6 S; H/ xhash_output=HASH(prev_hash,merkleroot,nonce)
* k2 x  H9 P% }" ]如果计算结果满足$hash_output
& h8 K" _# n, L, y( \" ]8 P而对于Hashimoto,HASH运算仅仅是第一步,其算法如下:# g, S5 C* P  @! w& W. t, X
nonce: 64-bits.正在尝试的nonce值7 j) r; j6 d: r1 a
get_txid(T):历史区块上的交易T的hash
3 x- E; j# G% Xtotal_transactions: 历史上的所有交易的个数) V) g+ h" M5 L/ J( `  s* x/ q
hash_output_A = HASH(prev_hash,merkle_root,nonce)2 ]* `' Y0 k! o2 o5 B" `8 g) k
for i = 0 to 63 do
) B0 n: c5 u! d; r    shifted_A = hash_output_A >> i0 l+ F% R& F8 {8 y
    transaction = shifted_A mod total_transactions7 r4 |4 u/ v+ K1 g( o4 z' W
    txid = get_txit(transaction) - u9 `0 x) [/ }1 E9 r. D$ m" U6 J" p
可以看出,在进行了HASH运算后,还需要进行64轮的混淆(mix)运算,而混淆的源数据是区块链上的历史交易,矿工节点在运行此算法时,需要访问内存中的历史交易信息(这是内存消耗的来源),最终只有当 $final_output 6 I/ w+ P1 x; B' h' _2 h& V
Dagger-Hashimoto相比于Hashimoto,不同点在于混淆运算的数据源不是区块链上的历史交易,而是以特定算法生成的约1GB大小的数据集合(dataset),矿工节点在挖矿时,需要将这1GB数据全部载入内存。5 e- M# m) y* p* t6 v
Ethash算法概要
2 c3 u6 w# }$ _& A2 c矿工挖矿不再是仅仅将找到的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临时计算就行。0 ^6 q3 `+ E5 K  j# z
5 o0 L7 I- \* @3 B2 u9 M
Ethash源码解析, E) ], H  ]: |; C' Q/ i# U
dataset生成9 V2 t5 K$ w0 o; l) I
dataset通过generate()方法生成,首先是生成cache,再从cache生成dataset# ]: o& `8 _; u8 B/ q
挖矿(Seal)+ U( _( j) e! N' H# {% K  n: z* W
在挖矿与共识中提到了,共识算法通过实现Engine.Seal接口,来实现挖矿,Ethash算法也不例外。; d) z9 A$ P# e- J7 D' j
其顶层流程如下:
- U5 x" z# t" z  C, F
" c; a4 Z( A  b; Z, q% bSeal调用中,启动一个go routine来调用ethash.mine()进行实际的挖矿,参数中的block是待挖掘的区块(已经打包好了交易),而nonce是一个随机值,作为挖矿过程尝试nonce的初始值。mine()调用首先计算后续挖矿需要的一些变量。hash为区块头中除了nonce和mixdigest的Hash值,dataset为挖掘这个区块时需要的混淆数据集合(占用1GB内存),target是本区块最终Hash需要达到的目标,它与区块难度成反比对本次尝试的nonce进行hashmotoFull()函数计算最终result(最终Hash值)和digest,如果满足target要求,则结束挖矿,否则增加nonce,再调用hashmotoFull()
4 m& D9 @1 E8 E- ]; `

4 c# G* {- g7 G) ofunc hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {- @. G* m2 C1 h2 Q& z5 ]2 L2 U
    lookup := func(index uint32) []uint32 {
2 }9 y) l2 A2 E! R, P0 P        offset := index * hashWords
0 l- q( b3 i+ o9 F# j: K: z. F- O4 J        return dataset[offset : offset+hashWords]7 g, A% s* e4 P9 h  Y& u. t( x
    }& T, `7 A+ [! l
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
2 r1 ~& r3 e  S" i}" B( a4 l5 C; F2 y: P
hashmotoFull()是运算的核心,内部调用hashmoto(),第三个参数为dataset的大小(即1GB),第四个参数是一个lookup函数,它接收index参数,返回dataset中64字节的数据。3 }' C) [. p- e6 E1 e" \
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {& {4 |& \" L( Z
    // 将dataset划分为2维矩阵,每行mixBytes=128字节,共1073739904/128=8388593行
! S9 a$ I2 [( F% ~/ B1 y/ X    rows := uint32(size / mixBytes)0 U( _% l9 ~6 D  j
    ) v2 T. P5 T6 r( k
    // 将hash与待尝试的nonce组合成64字节的seed" ~0 p# F4 h1 I
    seed := make([]byte, 40). A7 j0 r+ T" F# b5 }' D
    copy(seed, hash)
- }: z. |) g& t  D2 C" }    binary.LittleEndian.PutUint64(seed[32:], nonce)0 d3 b& H! ]; H' S* u# ~
    seed = crypto.Keccak512(seed)
; N5 f/ X9 A1 D; A7 E8 S    seedHead := binary.LittleEndian.Uint32(seed)7 C5 G% P$ a( w8 ]
    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)$ I# X9 d' |  @) b
    mix := make([]uint32, mixBytes/4)7 V1 W! I$ K' U5 \/ l
    for i := 0; i
+ f- c1 E8 I7 f' |3 r* @. a* g/ S验证(Verify)
4 C& P8 I* A4 G% f验证时VerifySeal()调用hashimotoLight(),Light表明验证者不需要完整的dataset,它需要用到的dataset中的数据都是临时从cache中计算。1 A6 {+ R' U- p$ ]3 f
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
9 f8 P$ \$ D# R& O    keccak512 := makeHasher(sha3.NewKeccak512())* G, h) K9 q/ q1 K. g6 E
    //lookup函数和hashimotoFull中的不同,它调用generateDatasetItem从cache中临时计算$ |0 n2 G/ u# w& B3 k
    lookup := func(index uint32) []uint32 {
0 T3 A! O! Z+ f, ~  o        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte6 Q: Q% b4 v% ]# o4 T
        data := make([]uint32, len(rawData)/4) //  16 个 uint328 o- w( H1 g* U! j8 K
        for i := 0; i
/ _/ w" p! N0 S$ Z0 @4 `- b除了lookup函数不同,其余部分hashimotoFull完全一样0 @- `4 Y' K/ C
总结
$ \0 Q) w8 ?( Q. [5 CEthash相比与Bitcoin的挖矿算法,增加了对内存使用的要求,要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。$ Y) d3 R5 q  K6 e8 J8 X

4 W# U* R/ K3 q$ ?! r) x
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

青丝暮雪780 初中生
  • 粉丝

    0

  • 关注

    2

  • 主题

    11