Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

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

青丝暮雪780
69 0 0
Ethereum当前和Bitcoin一样,采用基于工作量证明(Proof of Work,PoW)的共识算法来产生新的区块。与Bitcoin不同的是,Ethereum采用的共识算法可以抵御ASIC矿机对挖矿工作的垄断地位,这个算法叫做Ethash。* O8 s: ?- z( V
为什么要反ASIC, J0 L; @7 R6 R" Z: p. |. i+ {
PoW的的核心是Hash运算,谁的Hash运算更快,谁就更有可能挖掘出新的区块,获得更多的经济利益。在Bitcoin的发展过程中,挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程,其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高,参与者久越来越少,这与区块链的去中心化构想背道而驰。0 T# d/ F8 A$ ~- z1 z, Y: z
因此,在共识算法设计时,为了减少ASIC矿机的优势(专用并行计算),Ethereum增加了对于内存的要求,即在进行挖矿的过程中,需要占用消耗大量的内存空间,而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了,即使配置,这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)
3 i) E8 L6 d- {$ c9 E* m! M' kDagger-Hashimoto! }( [, @" K* ?% H, d3 y- m
Ethash是从Dagger-Hashimoto算法改动而来的,而Dagger-Hashimoto的原型是Thaddeus Dryja提出的Hashimoto算法,它在传统Bitcoin的工作量证明的基础上增加了消耗内存的步骤。
5 F; b! W  d/ k' e传统的PoW的本质是不断尝试不同的nonce,计算HASH
" p7 b/ G" s* ^5 z& J' q  Khash_output=HASH(prev_hash,merkleroot,nonce)& _8 d# P- m: v7 x  P; T
如果计算结果满足$hash_output! E2 V2 i3 _, d& a6 @, O& g) |2 ]
而对于Hashimoto,HASH运算仅仅是第一步,其算法如下:% p& x, x# W# H$ r$ S
nonce: 64-bits.正在尝试的nonce值
- c( H4 o* x$ w7 ?  D7 @) xget_txid(T):历史区块上的交易T的hash
6 @9 @7 n' n# c' i4 \total_transactions: 历史上的所有交易的个数
, {6 a6 |3 E+ u: \3 _hash_output_A = HASH(prev_hash,merkle_root,nonce)( ?( D3 J+ J* [6 p
for i = 0 to 63 do 4 F  d. N: U( n4 ?
    shifted_A = hash_output_A >> i
, A0 k: b8 o( e9 x    transaction = shifted_A mod total_transactions1 A6 I0 s6 q4 ?. g9 q2 X" J! z
    txid = get_txit(transaction) ! |+ h: k9 a9 R: n
可以看出,在进行了HASH运算后,还需要进行64轮的混淆(mix)运算,而混淆的源数据是区块链上的历史交易,矿工节点在运行此算法时,需要访问内存中的历史交易信息(这是内存消耗的来源),最终只有当 $final_output
: S9 @9 o3 B7 h4 m4 V% N* F9 MDagger-Hashimoto相比于Hashimoto,不同点在于混淆运算的数据源不是区块链上的历史交易,而是以特定算法生成的约1GB大小的数据集合(dataset),矿工节点在挖矿时,需要将这1GB数据全部载入内存。
8 e. [1 D+ `2 T7 r) `; T* m; Z9 kEthash算法概要
0 ~4 Z8 h2 l: K6 o+ e/ P# 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临时计算就行。. o# T- m- Y, P5 u9 V! Q5 ]( l
# D, S; t4 \" X3 n# p
Ethash源码解析
2 H' {4 s! ?7 [7 q" ^6 Z) {1 ydataset生成: h. ~! v, c" {+ O
dataset通过generate()方法生成,首先是生成cache,再从cache生成dataset$ W% }' i  C' J& N  A. {
挖矿(Seal)
/ r2 Q9 d, [  F% H" u' c* v6 _在挖矿与共识中提到了,共识算法通过实现Engine.Seal接口,来实现挖矿,Ethash算法也不例外。6 L; L( k2 q2 Y. Z
其顶层流程如下:
- A& K* u7 V; @9 b8 e, N0 h4 B6 Z: p; c
% N3 ]2 ~2 j4 X7 ^( ^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()
/ g+ Z1 M* F& X; a
# e  A9 C7 S! `- t6 t# X: m% d; q
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
% u& S; F( d3 o1 e/ E    lookup := func(index uint32) []uint32 {! U6 o7 T- [, c2 k' B; U
        offset := index * hashWords0 s1 W  @. W# |8 X5 \
        return dataset[offset : offset+hashWords]
7 |# p2 l1 {5 j& v    }8 Y: f2 G% `8 A, b; C9 W
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)+ \2 V- i( ]+ `! r' ?) Q
}; i" j: s; c1 B& f
hashmotoFull()是运算的核心,内部调用hashmoto(),第三个参数为dataset的大小(即1GB),第四个参数是一个lookup函数,它接收index参数,返回dataset中64字节的数据。
* e7 B) z$ U0 Y# g* @" D: |func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {8 M" t  y8 i* f, W. D0 |1 t/ X
    // 将dataset划分为2维矩阵,每行mixBytes=128字节,共1073739904/128=8388593行8 C1 _3 R$ s; e4 o' @" |/ U- K
    rows := uint32(size / mixBytes)0 v& Q* h' c7 F& J
    ( K& X+ n5 x0 X$ q
    // 将hash与待尝试的nonce组合成64字节的seed' l1 Q/ l1 X  p. E% _2 h0 l
    seed := make([]byte, 40)" G9 w* b7 d3 O& g4 ~( M! B4 X
    copy(seed, hash)  o$ Z  P0 _& U* m$ V) P
    binary.LittleEndian.PutUint64(seed[32:], nonce)
8 w7 x) ]- w7 I5 J8 ?/ t    seed = crypto.Keccak512(seed)
* z9 z8 C. _8 a% ]  D    seedHead := binary.LittleEndian.Uint32(seed)+ R$ e$ o) z& h. ?3 C: v
    // 将64字节的seed转化为32个uint32的mix数组(前后16个uint32内容相同)
( B/ x; U; S" |7 ?- M    mix := make([]uint32, mixBytes/4)
" a$ H5 s) z  N  ?5 `( J7 T! M9 [    for i := 0; i ' O. u! O: E/ S) ?
验证(Verify)
/ m4 p6 ~! L7 W2 _验证时VerifySeal()调用hashimotoLight(),Light表明验证者不需要完整的dataset,它需要用到的dataset中的数据都是临时从cache中计算。
  o* L8 e/ {3 n0 Ffunc hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {2 E& z2 O+ |2 Y- s( G  C
    keccak512 := makeHasher(sha3.NewKeccak512())
- }' W# P. N8 C$ b# L( T) P    //lookup函数和hashimotoFull中的不同,它调用generateDatasetItem从cache中临时计算
7 `$ c, A# {! {  b, Q6 |    lookup := func(index uint32) []uint32 {
& d# d# ~  w/ p        rawData := generateDatasetItem(cache, index, keccak512) //  return 64 byte5 D2 q7 D% n* r% A. E3 |
        data := make([]uint32, len(rawData)/4) //  16 个 uint322 l/ {. B4 U( f( u' z  N/ k; v! s! r
        for i := 0; i
8 B! A8 C( n2 y1 e0 Z1 j除了lookup函数不同,其余部分hashimotoFull完全一样4 n5 ^3 \7 x7 h$ t3 m, K
总结9 G3 n% X2 P* B: h- ]# S6 P" H
Ethash相比与Bitcoin的挖矿算法,增加了对内存使用的要求,要求矿工提供在挖矿过程中使用了大量内存的工作量证明,最终达到抵抗ASIC矿机的目的。
7 c* F* e) T- ~; V
% e7 d( Q0 I0 e) S& r5 G$ r
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

青丝暮雪780 初中生
  • 粉丝

    0

  • 关注

    2

  • 主题

    11