Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

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

青丝暮雪780
161 0 0
Ethereum当前和Bitcoin一样,采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是,Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位,这个算法叫做Ethash。( p% |5 a' t+ O2 ~
为什么要反ASIC; v/ `& z8 F) @
PoW的的核心是Hash运算,谁的Hash运算更快,谁就更有可能挖掘出新的区块,获得更多的经济利益。在Bitcoin的发展过程中,挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程,其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高,参与者久越来越少,这与区块链的去中心化构想背道而驰。
, G: D0 ?/ j/ h! ?% I因此,在共识算法设计时,为了减少ASIC矿机的优势(专用并行计算),Ethereum增加了对于内存的要求,即在进行挖矿的过程中,需要占用消耗大量的内存空间,而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了,即使配置,这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
$ c/ @0 _+ M" M  K' ]  g9 m4 M7 VDagger-Hashimoto
8 s& o1 Z0 |. n3 I: C' t  uEthash是从Dagger-Hashimoto算法改动而来的,而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法,它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。0 a5 A3 S* }' d+ C# X
传统的PoW的本质是不断尝试不同的nonce,计算HASH7 T& s' g0 {8 y' y$ _
hash_output=HASH(prev_hash,merkleroot,nonce), r) Z/ W+ e6 d4 f7 J2 n5 u2 q
如果计算结果满足$hash_output
0 X2 n' \) l- C/ c8 |. ?! ~+ _而对于Hashimoto,HASH运算仅仅是第一步,其算法如下:6 u- _5 b, Y+ [" w* f9 z
nonce: 64-bits.正在尝试的nonce值  B/ o* \; Y+ F
get_txid(T):历史区块上的交易T的hash
, ^. B2 S; H' `9 W) P- g% itotal_transactions: 历史上的所有交易的个数( R; m: j; p) h: S* o  m3 |: z, M
hash_output_A = HASH(prev_hash,merkle_root,nonce)
3 t, s# T5 D7 t" `- ?+ F# qfor i = 0 to 63 do
- H. D3 e: l! r3 I( j0 n( L" U3 y( @    shifted_A = hash_output_A >> i7 C; Y- D- X3 x7 @  a; K# s( a- h( m
    transaction = shifted_A mod total_transactions" t% r" w9 M+ Q' [7 L% Q
    txid = get_txit(transaction)
( @1 D: y# A1 U: `6 g, G可以看出,在进行了HASH运算后,还需要进行64轮的混淆(mix)运算,而混淆的源数据是区块链上的历史交易,矿工节点在运行此算法时,需要访问内存中的历史交易信息(这是内存消耗的来源),最终只有当 $final_output
! p4 y# o% B# X$ v6 zDagger-Hashimoto相比于Hashimoto,不同点在于混淆运算的数据源不是区块链上的历史交易,而是以特定算法生成的约1GB大小的数据集合(dataset),矿工节点在挖矿时,需要将这1GB数据全部载入内存。1 d3 D8 f$ M: p: u( x0 U
Ethash算法概要" w) n4 B8 a6 N4 O
矿工挖矿不再是仅仅将找到的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临时计算就行。/ K+ @: v( p6 W
$ Z* B  \; E3 D7 L5 m4 |$ H. U
Ethash源码解析" d9 c2 g; l3 D) `' k- {8 Q
dataset生成  \7 w1 V+ a6 R+ |  ~
dataset通过generate()方法生成,首先是生成cache,再从cache生成dataset0 M; y6 J7 P- v8 O& p, ^
挖矿(Seal)
6 G3 O! Q9 x. R在挖矿与共识中提到了,共识算法通过实现Engine.Seal接口,来实现挖矿,Ethash算法也不例外。. y% |" Y+ ^/ w5 J' ^$ k$ C
其顶层流程如下:
8 e4 r! t1 n( q5 v$ }. O
7 a+ [+ n6 p2 S7 z, mSeal调用中,启动一个go routine来调用ethash.mine()进行实际的挖矿,参数中的block是待挖掘的区块(已经打包好了交易),而nonce是一个随机值,作为挖矿过程尝试nonce的初始值。mine()调用首先计算后续挖矿需要的一些变量。hash为区块头中除了nonce和mixdigest的Hash值,dataset为挖掘这个区块时需要的混淆数据集合(占用1GB内存),target是本区块最终Hash需要达到的目标,它与区块难度成反比对本次尝试的nonce进行hashmotoFull()函数计算最终result(最终Hash值)和digest,如果满足target要求,则结束挖矿,否则增加nonce,再调用hashmotoFull()6 i, ^  r. G1 A
' x: V7 N2 ]/ V8 C, R, R) e7 B8 P
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {$ o/ K: ^, t& o  p
    lookup := func(index uint32) []uint32 {
( v4 J8 y5 t& n' v( ^9 m        offset := index * hashWords4 L8 @! h6 N1 R, l
        return dataset[offset : offset+hashWords]" O& O; j; [$ J2 C# V$ G$ s
    }6 g0 v4 m% }2 k( x8 P" D, R
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
8 f  l0 ?2 U5 Y+ [}# a. C1 A6 `% U8 n* a
hashmotoFull()是运算的核心,内部调用hashmoto(),第三个参数为dataset的大小(即1GB),第四个参数是一个lookup函数,它接收index参数,返回dataset中64字节的数据。
" j6 p1 g$ b( o6 ^- }! N, y# Pfunc hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {: Q6 n8 M/ e1 v: o+ T
    // 将dataset划分为2维矩阵,每行mixBytes=128字节,共1073739904/128=8388593行" U$ p" p, L2 ^# U
    rows := uint32(size / mixBytes)
* \# \" b2 p1 A7 X    / r3 b. n( s- A* G
    // 将hash与待尝试的nonce组合成64字节的seed
9 A- n: P3 @% p    seed := make([]byte, 40)
6 J1 X' e' d9 z0 V) v% ]. g    copy(seed, hash)' f' W! s  F, A( f' B3 c
    binary.LittleEndian.PutUint64(seed[32:], nonce)6 {+ [2 p2 w4 z/ {+ h' z  u9 t
    seed = crypto.Keccak512(seed)
4 ~( i3 Z9 }" l2 t3 t- x    seedHead := binary.LittleEndian.Uint32(seed)
: K4 X( e$ y: b3 ?8 C# t5 S& {    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)4 y3 {' h7 {! _- E) _, p! E" `4 M
    mix := make([]uint32, mixBytes/4)* V" m( K9 I2 \' ~/ H, c$ M
    for i := 0; i
0 T7 A: B5 e- M+ g# u验证(Verify)$ C( r( T; Y7 F( y
验证时VerifySeal()调用hashimotoLight(),Light表明验证者不需要完整的dataset,它需要用到的dataset中的数据都是临时从cache中计算。: ?# P8 \; x5 S$ A+ p6 T, A8 I$ Y  O
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
" `, N% f2 N3 Q& A7 [/ Y  A    keccak512 := makeHasher(sha3.NewKeccak512())
" v" k2 h. b, }. f1 }    //lookup函数和hashimotoFull中的不同,它调用generateDatasetItem从cache中临时计算
( o. O, b- Q! I, F' s0 K9 i    lookup := func(index uint32) []uint32 {; K2 a% ?4 P2 h, _/ \! k8 Z( E
        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte: e5 h6 Y% S1 B; Y% ]9 t1 Z
        data := make([]uint32, len(rawData)/4) //  16 个 uint32
( ?5 ^9 I" o3 E! e2 R        for i := 0; i 9 O4 {' G" B( _0 _0 S) y
除了lookup函数不同,其余部分hashimotoFull完全一样
. H5 B6 l$ v% C1 y9 ~. ]- B总结% J+ B9 v. C# k5 d9 m" W
Ethash相比与Bitcoin的挖矿算法,增加了对内存使用的要求,要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。6 J0 Z7 \" c+ Z) \: u! Z3 K

5 |% C* ?8 e& D0 @' M
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

青丝暮雪780 初中生
  • 粉丝

    0

  • 关注

    2

  • 主题

    11