Dagger Hashimoto

作者:链客区块链技术问答社区 时间:2019年9月26日

火币网注册

d8YTe!P:J;XVaz

链客,专为开发者而生,有问必答!.QUYI n

nH \4Vn2gB1Q3Z0此文章来自[区块链技术社区](https://www.liankexing.com),未经允许拒绝转载。

_'D%i,x6~DjNey0

v~H:O E0QQ$a0s7Xw O[.u0I

t#m\yBm2H r N3l0Ethash

8Qa%xX;ysN0 Lhguhv#U

前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DAG有向无环图的算法,这些都是本文要研究的Ethash的基础。Ethash是目前以太坊基于POW工作量证明的一个共识引擎(也叫挖矿算法)。它的前身是Dagger Hashimoto算法。a&J)u1V[2m

`)Ry*}i2a_0Dagger Hashimoto

E#{*Oha.NIH)u0e i0

@r+Hx6x/w3FY/Dj}0作为以太坊挖矿算法Ethash的前身,Dagger Hashimoto的目的是:G0k?(E4G7ig!P

#p,^L-ec1`/^8u8I0抵制矿机(ASIC,专门用于挖矿的芯片)I3L6|Xi0t9bG Y"G5f

F+k4h}.q2ua.ZB\)M

轻客户端验证6WoE;TQKu|+G T

$z2])~.b0l FJ%_v

全链数据存储!G zR8a~

r s x#r,w z4`.f[N0Dagger和Hashimoto其实是两个东西,

Dw Ij#x3d Sw*r;N0

Xl.~ a0rc@k2@0?&LI0Hashimoto算法

x$Y}6~ dV0

H@$Bmu'X ns0是这个人Thaddeus Dryja创造的。旨在通过IO限制来抵制矿机。在挖矿过程中,使内存读取限制条件,由于内存设备本身会比计算设备更加便宜以及普遍,在内存升级优化方面,全世界的大公司也都投入巨大,以使内存能够适应各种用户场景,所以有了随机访问内存的概念RAM,因此,现有的内存可能会比较接近最优的评估算法。Hashimoto算法使用区块链作为源数据,满足了上面的1和3的要求。

7O)?#u(hr`+C0

6f:U*Y;t#nTM0Dagger算法

kS`.r@0 { gLHN;t&a

是这个人Vitalik Buterin发明的。它利用了有向无环图DAG同时实现了Memory-Hard Function内存计算困难但易于验证Memory-easy verification的特性(我们知道这是哈希算法的重要特性之一)。它的理论依据是基于每个特定场合nonce只需要大型数据总量树的一小部分,并且针对每个特定场合nonce的子树的再计算是被禁止挖矿的。因此,需要存储树但也支持一个独立场合nonce的验证价值。Dagger算法注定要替代现存的仅内存计算困难的算法,例如Scrypt(莱特币采用的),它是计算困难同时验证亦困难的算法,当他们的内存计算困难度增加至真正安全的水平,验证的困难度也随之难上加难。然而,Dagger算法被证明是容易受到Sergio Lerner发明的共享内存硬件加速技术,随后在其他路径的研究方面,该算法被遗弃了。,S k%B1]0wK a~b'L`

7V*Ek;p u(Y"S

Memory-Hard Function

*Mt1a"{8pd'L0

q }p \{D0直接翻译过来是内存困难函数,这是为了地址矿机而诞生的一种思想。我们知道挖矿是靠我们的电脑,但是有些硬件厂商会制造专门用于挖矿的硬件设备,它们并不是一台完整的PC机,例如ASIC、GPU以及FPGAs(我们经常能听到GPU挖矿等)。所以这些作为矿机的设备是超越普通PC挖矿的存在,这是不符合我们区块链的去中心化精神的,所以我们要让挖矿设备平等。7i NkO:e$v#VJ [

)w9jk,X rSm0那么该如何让挖矿设备是平等的呢?

&JR"w'\1a%C3~ f5[0

:~ zR9O+iY(oU0上面谈到Dagger算法的时候其实提到了,这里换一种方式再来介绍一下,现在CPU都是多核的,如果从计算能力来讲,CPU有几核就可以模拟几台设备同时平行挖矿,自然效率就高些,但是这里采用的衡量对象是内存,一台电脑只有一个总内存。我们做过java多线程开发的朋友知道,无论机器性能有多高,但我们写的程序就是单线程的,那么这个程序运行在高配多核电脑和低配单核电脑的区别不大,只要他们的单核运算能力和内存大小一样即可。所以也是这个原理,通过Dagger算法,我们将挖矿流程锁定在以内存为衡量标准的硬件性能上,只要通过“塞一堆数据到内存中”的方式,让多核平行处理发挥不出来,降低硬件的运算优势,只与内存大小有关,这样无论是PC机还是ASIC、GPU以及FPGAs,都可达到平等挖矿的诉求,这也是ASIC-resistant原理,目前抵制矿机的主要手段。x!w X/k"LJy#\

*L1Z%bZxN |1R0两个问题的研究6cDv5m|!]

5R a:c{,` @LyL E9i

在Dagger以及Dagger Hashimoto算法中,有两个问题的研究是被搁置的,2FJ"p$Nwh,Y

M;y8z6E+c)_&y

基于区块链的工作量证明:一个POW函数包括了运行区块链上的合约。该方法被抛弃是因为这是一个长期的攻击缺陷,因为攻击者能够创建分叉,然后通过一个包含秘密的快速“trapdoor”井盖门的运行机制的合约在该分叉上殖民。

E&F]1VV0

W}c:A]Z\&|0随机环路:一个POW函数由这个人Vlad Zamfir开发,包含了每1000个场合nonces就生成一个新的程序的功能。本质上来讲,每次选择一个新的哈希函数,会比可重配置的FPGAs(可重编程的芯片,不必重新焊接电路板就可通过软件技术重新自定义硬件功能)更快。该方法被暂时搁置,是因为它很难看到有什么机制可以用来生成随机程序是足够全面,因此它的专业化收益是较低的。然而,我们并没有看到为什么这个概念无法让它生效的根本原因,所以暂时搁置。tTX$D i;wcs

)H]4Z$kb-a(n

Dagger Hashimoto算法.[D{)X5g+cW#I!f n

?!k VY"mr&tnH

(区别于Hashimoto)Dagger Hashimoto不是直接将区块链作为数据源,而是使用一个1GB的自定义生成的数据集cache。/O7}"ou5_`k

W5qMw]4\'iF;{L

这个数据集是基于区块数据每N个块就会更新。该数据集是使用Dagger算法生成,允许一个自己的高效计算,特定于每个轻客户端校验算法的场合nonce。3vV$tX%^ \Zn

\-O0x;C,{8_

(区别于Dagger)Dagger Hashimoto克服了Dagger的缺陷,它用于查询区块数据的数据集是半永久的,只有在偶然的间隔才会被更新(例如每周一次)。这意味着生成数据集将非常容易,所以Sergio Lerner的争议共享内存加速变得微不足道了。'n$V5{0uY9}"he L[J R

.ZM+u-k#^0~0挖矿补充 {f|,e x-zC

`#pF~5_qg w0前面我已经写了一盘关于挖矿的文章了,这一节是挖矿的补充内容。;{3Pr zfN-ac9k

^oA;E!vE z0以太坊将过渡到POS(proof-of-stake),代替传统的POW,挖矿将会被淘汰掉,所以现在不推荐再去做一名矿工(前期购买设备等成本较大,POS实现前未必能回本)。

8[0G(Tn2sWH Oe0

lah'Lh \0挖掘以太币=网络安全=验证估算

z|+XK ]`8}0 Hx Q"`5G6Y |1\

目前以太坊的POW算法是Ethash, e8a$J.b+@

6lZ3n i6lW.u!]'UN0Ethash算法包含找到一个nonce值输入到一个算法中,得到的结果是低于一个基于特定困难度的阀值。S(B|&B)W&?

C!B$C;]&T hbB5^'{0POW算法的关键点是除了暴力枚举,没有任何办法可以找到这个nonce值,但对于验证输出的结果是非常简单容易的。如果输出结果有一个均匀分布,我们就可以保证找到一个nonce值的平均所需时间取决于那个难度阀值,因此我们可以通过调整难度阀值来控制找到一个新块的时间,这就是控制出块速度的原理。Y@ \OCB5z

b6nU.c!R lvg

DAG

r4Jm(Ie!u4{0

~DT3Nn xj0y0Ethash的POW是memory-hard,支持矿机抵御。这意味着POW计算需要选择一个固定的依赖于nonce值和块头的资源的子集。

{ L? e1CQ0 %R ygMd Qz'h9|

这个资源(大约1G大小)就是DAG!

,qv9aquhf&FbV ]O0

9i*irX/G'Q R:F2Yq0一世epoch

K(w Q5_+T0

|o`bx FL0每3万个块会花几个小时的时间生成一个有向无环图DAG。这个DAG被称为epoch,一世(为了好记,refer个秦二世)。DAG只取决于区块高度,它可以被预生成,如果没有预生成的话,客户端需要等待预生成流程结束以后才能继续出块操作。除非客户端真实的提前预缓存了DAG,否则在每个epoch的过渡期间,网络可能会经历一个巨大的区块延迟。

1c k P"a#Z+ie0 e j2v kU{

特例:当你从头启动一个结点时,挖矿工作只会在创建了现世DAG以后启动。.{y"_7OrL}

` `:`D^H.ky

挖矿奖励

D2fp[8` A)S{#?&M0

tVa)B0eb0有三部分:T)kH[d P;[6Py

|U8X6r!z0}y0静态区块创建奖励,精确发放3以太币作为奖励。

,S$tYKo0 Or!n+MaDH0~pu

当前区块包含的所有交易的gas钱,随着时间推移,gas会越来越便宜,获得的gas总和奖励会低于静态区块创建奖励。

Bm3O:G]S"?0Fd0

8bV-]$e%U?1dSx0叔块奖励,整块奖励的1/32。.ZN9z` j+rkmX0o"j

(h-[2jlGW

Ethash#xk{T4e}.\(}

-T6ln` X{r'C

Ethash算法路线图:

F"co:r uwV3C2R@f0 pb yv6B4@6`pv8c

存在一个种子seed,通过扫描块头为每个块计算出来那个点。

G:C hJ BN0

&or ` n6Q^k-|0Lk;T3e J0根据这个种子seed,可以计算一个16MB的伪随机缓存cache,轻客户端存储这个缓存。

s(n#@ m8Xtis4C0

GkbJwV^0从这个缓存cache中,我们能够生成一个1GB的数据集,该数据集中的每一项都取决于缓存中的一小部分。完整客户端和矿工存储了这个数据集,数据集随着时间线性增长。

.R-Vj oj!E%d"T$q0 k$V1c5|vt6}i0A

挖矿工作包含了抓取数据集的随机片以及运用哈希函数计算他们。校验工作能够在低内存的环境下完成,通过使用缓存再次生成所需的特性数据集的片段,所以你只需要存储缓存cache即可。9HYGLE'T t

q7Bx H'{dFyAvS

以上提到的大数据集是每3万个块更新一次,所以绝大多数的矿工的工作是读取该数据集而不是改变它。eQJ9M&I&I8j ^?Q'?

~h;A6dcn'yg0pkg ethash源码分析

HT"f JbKO4] nG0

$L3\)}iqnw-i0以上我们将所有的概念抽象梳理了一下,包括POW,挖矿,Ethash原理流程等,下面我们带着这些理论知识走进源代码中去分析具体的实现。正如我们的题目,本文主要分析的是ethash算法,因此整个源码范围仅限于go-ethereum/consensus/ethash包,该包实现了ethash pow的共识引擎。)yo6I%]$by`2B

p I Ij0LcZ'M[

入口 Q@ }-Z"klod

DSBq3K5Q3x0分析源码要有个入口,这个入口就是在《以太坊源码机制:挖矿》中挖下的坑“Seal方法”,原文留下了这个印子,在本文进行展开讨论。5xH/B*VX#p4^ b

|F1^'@H0{Q

在go-ethereum/consensus/consensus.go 接口中定义了如下的方法,正是对应上面的“Seal方法”,该接口方法的定义如下:

[8~n5[7n G5h+d`|0

VB#CQM'c}5n0Seal(chainChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error)//该方法通过输入一个包含本地矿工挖出的最高区块在主干上生成一个新块。:nws.}!s!YL,h*?

U^)Na O0参数有ChainReader,Block,stop结构体信号,返回一个主链上的新出的块实体。 Z"g K Ty$i

:S:X+V\R$j6R7F

ChainReader

3N{)b u,oz4E0 df6K |ye+B,t

//定义了一些方法,用于在区块头验证以及叔块验证期间,访问本地区块链。typeChainReaderinterface{'[[)N U z+w_

9pOi M yN-X0//获取区块链的链配置

]8P"L)b:PK0

\7y1_}$p/`0Config()*params.ChainConfig//从本地链获取当前块头

.NA v5N `;K0 %~8v+M&h$V*O

CurrentHeader()*types.Header//通过hash和number从主链中获取一个区块头-u/}8uG{-I

eB0[ J;R~7}0GetHeader(hashcommon.Hash,numberuint64)*types.Header//通过number从主链中获取一个区块头

*zuh B5dA*_0 jo%Z,d^L\ Jt*| g

GetHeaderByNumber(numberuint64)*types.Header//通过hash从主链中获取一个区块头3ek)C NB(A,W^

PD4sPW h'e#@!x2@0GetHeaderByHash(hashcommon.Hash)*types.Header//通过hash和number从主链中获取一个区块pP6a)D|

CS$F"DN:?

GetBlock(hashcommon.Hash,numberuint64)*types.Block}

J&a^#ZIj-y qo2m0 'V~n EDA{

总结,ChainReader定义了几个方法:从本地区块链获取配置、区块头,从主链中获取区块头、区块,参数条件包括hash和number,随意组合。

5u5S-MT'v?+Y;B&P0

xo B6^,W6N9M:MJ/z0BlockO-swj:m {[ w

k`:U6z"aS0//Block代表以太坊区块链中的一个完整的区块typeBlockstruct{

0yB1xj/F v1`"mj'W0

,J7iuo _"N/I`0header*Header//区块包括头

2LGHo#c0

@ TZb3^1a*w4N0uncles[]*Header//叔块

-hHgRC f v9| P$U0

o d ^/S8m7Q-l)y/t0transactionsTransactions//交易集合${v0]k}"e

#h"A)ui uv!p

//caches缓存

P#VJT|0 W9u cy Q

hashatomic.Value V]a htcL

9zYO8c%U1{F

sizeatomic.Value//Td用于core包存储所有的链上的难度ji-`4HU j D

RUv C(]B0td*big.Int//这些字段用于eth包来跟踪inter-peer内部端点区块的接替@8wv$ACVo

)n\$k)?2i!h

ReceivedAttime.Time

B(F7O _[+Fhj M0

&Z CP&MX$s0ReceivedFrominterface{}}a#t }P8~#k2{O r7hp4M

'y]N8_1y Ie(k

总结,Block除了我们熟知的区块中必有的区块头、叔块以及打包存储的交易信息,还有cache缓存的内容,以及每个块之于链的难度值,还有用于跟踪内部端点的字段。dI8P [ t+a8X e

3WO!`2S ~YR0stop

`[:rE"bEh0

+qF+^~ R)X-n#P(F0stop是一个空结构体作为信号源。,Ye\\#l

8p]2Bu7~b dl0关于空结构体的讨论,为什么go里面经常出现struct{}?0PuU8}bE6S d/egM

p2@2v H(|0go中除了struct{}类型以外,其他类型都是width,占有存储,而struct{}没有字段,没有方法,width为0,灵活性高,不占内存空间,这可能是让Gopher青睐的原因。h/BJDA[IT

3VNk;LqljM

sealer&QZ)r AB2_*i+i

DF$sdeEw^[3Qw

seal方法有两个实现,我们选择ethash,该方法存在于consensus/ethash/sealer.go文件中,第一个函数就是seal的实现,先来看该方法的声明部分:6TpA5z#s&N]@ P

:P-}.{+lz-Vu\0//尝试找到一个nonce值能够满足区块难度需求。func(ethash*Ethash)Seal(chainconsensus.ChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error){2~$k.R)R3c9oCY*y

~+^M.sc3[T

可以看出这个方法是属于Ethash的指针对象的,

&NErKhAp9x$z8}0W0 4[5}N!hE:C#C kF

typeEthashstruct{6]]lL.|;G2L T

C O M G e2\0//cache配置

N.WO:C-z*F0 }oh,lZ9dTc

cachedirstring//缓存位置

+jMR4t+T[0

}}*_:{P&gV0cachesinmemint//在内存中缓存的数量

3Y#P]7Fs\1u0w*]_0 aSBY(c

cachesondiskint//在硬盘中缓存的数量

zLm%O Z$|S2O$X3p0 *}HI Q{z\| C8t#U

//DAG挖矿数据集配置

j*Q+k W&o P*KeYZ0 w9R7`&MB3E"M

dagdirstring//DAG位置,存储全部挖矿数据集

Jw$[D W]R,h.H0 w-U [*nY nlk

dagsinmemint//在内存中DAG的数量/ul6R'E3\G-Q-{ om

b\&Lm3X/K2]

dagsondiskint//在硬盘中DAG的数量+Pc_ rw(M2k

R j w,d,s'CA m0L

//内存cache

:xq$A9xu9e xF#c0

x]|S%BtI,C#I0cachesmap[uint64]*cache//内存缓存,可反复使用避免再生太频繁 lex*I [|4R7u

wybx0\w:r&v&a3`0fcache*cache//为了下一世估算的预生产缓存

~m;i6cxu#i%V0 "i*j%[UXUp6D1`

//内存数据集

)~BB!ZL @N!D0

wsa$`W M0datasetsmap[uint64]*dataset//内存数据集,可反复使用避免再生太频繁

(J"Y?qL)t(y0

3nOAQ3]0fdataset*dataset//为了下一世估算的预生产数据集9C yb6h*f4B+B6`L

(s1Cd^:D!B

//挖矿相关字段

FFPkWyK,I0 &X]/TPN%Y3D;z

rand*rand.Rand//随机工具,用来为nonce做适当的种子

a.wf+S~ b.Y0

TEt)S@KM [(w0threadsint//如果在挖矿,代表挖矿的线程编号

!no~*t C_U0

Or R\$lI7o!K'Z!tX0updatechanstruct{}//更新挖矿中参数的通道

l2_7Wq2{N(c9\md0

6W+fc(G|A0hashratemetrics.Meter//测量跟踪平均哈希率F?,^D X

^HP9Pv%SIX0V7M

//以下字段是用于测试

df HxubY0

mQ'yt^0testerbool//是否使用一个小型测试数据集的标志位

cK,N)`whV*j0

4e-bk ?;]+Qx4{"eY0shared*Ethash//共享pow模式,无法再生缓存

pz(i(Cv+Z{O6S:L0

4Z.D*h-T Drx/Le0fakeModebool//Fake模式,是否取消POW检查的标志位+` WH a.w9T!cZA8`

?7IpCI8t B

fakeFullbool//是否取消所有共识规则的标志位{:|5N7x2ecR!@)_as

gn@9@\%x!?0d9i

fakeFailuint64//未通过POW检查的区块号(包含fake模式)

I5?L-c\?Na%_4a0 wtVfv

fakeDelaytime.Duration//验证工作返回消息前的休眠延迟时间

LtJ&^+i r5Z0 .pKzbQ Y&Q@

locksync.Mutex//为了内存中的缓存和挖矿字段,保证线程安全}

\6`#wj2~q)?2uw0 V/M3r)\&n!J

为了更好的读懂之后的代码,我们要对区块头的数据结构进行一个分析:

3g,feS@0

u;A$_ b*D0typeHeaderstruct{

i2iu3H"ji$QN+M0

#P#@ bQj0ParentHashcommon.Hash`json:"parentHash"gencodec:"required"`

6I7JU7l:| X5h0 "^zd3s$W"h0V4x._o

UncleHashcommon.Hash`json:"sha3Uncles"gencodec:"required"`d,Ta5|3H V2TQ7m1t

-cW ^*OVR1N~"O m

Coinbasecommon.Address`json:"miner"gencodec:"required"`

1T8h Q c\-g E0

%p+x@nu$V3w3q0Rootcommon.Hash`json:"stateRoot"gencodec:"required"`

H W'wIP(`5\A0

/f[8eYM&V2D\0TxHashcommon.Hash`json:"transactionsRoot"gencodec:"required"`*^5H6Ml~'w?

8u3~ b%| i

ReceiptHashcommon.Hash`json:"receiptsRoot"gencodec:"required"`Qv)cE*W2y

#?`Q[!e&[(D L

BloomBloom`json:"logsBloom"gencodec:"required"`

8`0J%D3Hr;f8A0 L8p;O/d K(R-k+P

Difficulty*big.Int`json:"difficulty"gencodec:"required"`

l x}y | Y;C3kl0

9]FTaoq4q7c0Number*big.Int`json:"number"gencodec:"required"`.{*bF%q!H c

FW*Vu0v"mb ?lJ0GasLimit*big.Int`json:"gasLimit"gencodec:"required"`&K{C$c};Y/`5l

,V.Nf{!g9Q'q

GasUsed*big.Int`json:"gasUsed"gencodec:"required"`g@*piO:R Zi

@hdqE6L@

Time*big.Int`json:"timestamp"gencodec:"required"`

iWg t/^:H/d,T0

"bc%Zyvf U0Extra[]byte`json:"extraData"gencodec:"required"`U2x+WrnAsbD#G

G3i'^J [2H$W0MixDigestcommon.Hash`json:"mixHash"gencodec:"required"`$AI&A/F.X@

*M5q Z5bZ,w*s0g

NonceBlockNonce`json:"nonce"gencodec:"required"`}

Wc5X)~6? q5f0 's bzg6z(w X

可以看到一个区块头包含了父块hash值,叔块hash值,Coinbase结点账户地址,状态根,交易hash,接受者hash,日志,难度值,块编号,最低支付gas,花费的gas,时间戳,额外数据,混合hash,nonce值(8个byte)。我们要对这些区块头的成员属性了然于胸,后面的源码内容才能更好的理解。下面我们继续Seal方法,下面展示完整代码:

!uVyk&H~ g%CD!v0 "H u4Y9ynB-ub

func(ethash*Ethash)Seal(chainconsensus.ChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error){c.M!Y \4`Q7zA

/ONR(va

//fake模式立即返回0nonce:H(?TG6CH

1`+^ UubFf9M0ifethash.fakeMode{

}^8G6gn'nR.Ha0 r1v@ J]

header:=block.Header()

4L\Gdd7QIT.\^|0

}*F3k&z pTy*\ b0header.Nonce,header.MixDigest=types.BlockNonce{},common.Hash{}%{?v'M"H|B'A#?8`

f:V I sZv

returnblock.WithSeal(header),nil}

1L'j-J8k*Cw3^(M?0

/B@s7P'|N\;M0//共享pow的话,则转到它的共享对象执行Seal操作

f;sz|(ZLO js0 t3ju*B_@?jL

ifethash.shared!=nil{

Z7c uk)[Y%Th0

X6Ed,sT{0returnethash.shared.Seal(chain,block,stop)h*`\ U}

0PEBf*Z7Z Kx7`

}ULOJ1i$P"Af

,bj~(n;v'S1s?];L

//创建一个runner以及它指挥的多重搜索线程

C6rz@Y'x6tT0

/OA"NtA I!z8rs;c0abort:=make(chanstruct{})

Sqc m4ME:a0

2JD Xuu'A-D0found:=make(chan*types.Block)of9}B T:W/eZ

RVAq)tM ^e0ethash.lock.Lock()//线程锁,保证内存的缓存(包含挖矿字段)安全 F lU}V

l jeE!?0threads:=ethash.threads//挖矿的线程sdoSJYE.C X

AE#C ep m0ifethash.rand==nil{//rand为空,则为ethash的字段rand赋值Tt+viIn2O&KM^

j z3Ff,L&[x.d Z0//获得种子0uv\+{4i|E

7nZ-rf6O4]

seed,err:=crand.Int(crand.Reader,big.NewInt(math.MaxInt64))F3Ta!G.L\

4I$VyzXdstCe+i

iferr!=nil{//执行失败,有报错SSqp$p!]`s0@

Q3C;QX IN2m ^8v

ethash.lock.Unlock()//先解锁

\$`zQd/A&N g0 -]]V#[ q&R{

returnnil,err//程序中止,直接返回空块和报错信息'wS2c,On6gw1j

6|:k;kEdgX.f

}

t&^ W0_1M*C!E+{0

7| wy xzo:dt0ethash.rand=rand.New(rand.NewSource(seed.Int64()))//执行成功,拿到合法种子seed,通过其获得rand对象,赋值。

#L.S7w/n(l:^5h O0

%Zq&\4VF s^q+u |1p0}

A:j;]Iu(m(z'Cu@0 I3qD6J:_5L

ethash.lock.Unlock()//解锁

{^a@#^7M0 :p`D9]?;^NS.o'?

ifthreads==0{//挖矿线程编号为0,则通过方法返回当前物理上可用CPU编号n Y+A w2Ww

tf)G"v(fa0threads=runtime.NumCPU()

"Qyf#S:P'~:pV~0

;|H4O8c^EQ8uz;c)Z0}V[zA~4L8Q

)wr+Lz7|1Ib#V0ifthreads<0{//非法结果9^lN5@ LM5P"s

,Dt8g/w)r0threads=0//置为0,允许在本地或远程没有额外逻辑的情况下,取消本地挖矿操作6g O+IQ(z'?9e:ypI8K

@5[9[](q

}

?Cj$I1|YPj6Q0

Kc0]1{*h W0varpendsync.WaitGroup//创建一个倒计时锁对象,go语法参照http://www.cnblogs.com/Evsward/p/goPipeline.html#sync.waitgroupZ.iW*A,gJ,vb

(h1M Q j0^de C]6^

fori:=0;i1U](zQ'K!V-m'U

"}Z AC yxU/A.n

pend.Add(1)nM,`9N}#nL e

~)Okjg U0^!PH e

gofunc(idint,nonceuint64){//核心代码通过闭包多线程技术来执行。

/D_ jjDh0 ._Mz*@gQ{

deferpend.Done()6u.c3x jl+R+f

\PlU4kb

ethash.mine(block,id,nonce,abort,found)//Seal核心工作

6xn&j,bC0 FG `Zsk@

}(i,uint64(ethash.rand.Int63()))//闭包第二个参数表达式uint64(ethash.rand.Int63())通过上面准备好的rand函数随机数结果作为nonce实参传入方法体

.Z6\bJ)Tqm4d~0 %}~ k3cUe5ne

}[Z3lL3gG

;|!P+Ic5{c1D7m7Kh0//直到seal操作被中止或者找到了一个nonce值,否则一直等$]/c}u R.U,|7g

Jq*enM!l8}1I6A+lh0varresult*types.Block//定义一个区块对象result,用于接收操作结果并作为返回值返回上一层+T PA+J&i/T

$g5o hN;|0select{//go语法参照http://www.cnblogs.com/Evsward/p/go.html#select OY+S\G5V

.C F$f`bR%V1|"?

case<-stop:(Eb@.y,W*o+i

ah5UOYd0A0//外部意外中止,停止所有挖矿线程

B}~'[{RY7i^0

JFn\(E5MMt0close(abort)%S-X `3bb(lDQ\

\R[3iJ}~D9j0caseresult=<-found:4?T0az0j2yE#[n

"v2T9U/K9LIt&W/d

//其中一个线程挖到正确块,中止其他所有线程i"Q7ipEP-gc

6jdHh_7y\$Q4?|

close(abort)

N8`&fp,J p0 -q*f"@ m'H }

case<-ethash.update:

[h5q!a@&C(He0 E,V7Bs? V C-Ty7D

//ethash对象发生改变,停止当前所有操作,重启当前方法%j3O+XL%_ X;r

(_I#W [T9Lq

close(abort)

,ica1X;Z6bZ3F-^0

$?9\(I\6y M0pend.Wait()Z|x&~*h H i5]1x

+Qb2` lsQ;SuRT)]

returnethash.Seal(chain,block,stop)

%f#Lr9S%dg-t+ql o2MU#e0 :L^1|%Cd W4V

}

R&OY[)iS0 ;M2lRC$A

//等待所有矿工停止或者返回一个区块

QV2x cB,n/f0 @r6VZ/_

pend.Wait()L Jym S-[h

X(LVLf.S

returnresult,nil}S[7QqR0W^

`-A6Q6jA \!s3D0以上Seal方法体,针对ethash的各种状态进行了校验和流程处理,以及对线程资源的控制,下面看Seal核心工作的内容(sealer.go文件只有两个函数,一个是Seal方法,另一个就是mine方法,可以看出Seal方法是对外的,而mine方法是内部方法,只能被当前ethash包域调用):mine方法

/}DEV.E#c {0

6a f|0d"g$El`k0//mine函数是真正的pow矿工,用来搜索一个nonce值,nonce值开始于seed值,seed值是能最终产生正确的可匹配可验证的区块难度func(ethash*Ethash)mine(block*types.Block,idint,seeduint64,abortchanstruct{},foundchan*types.Block){

'J:Q b^ Pp uU0

g:Al2o kr4X g8k0//从区块头中提取出一些数据,放在一个全局变量域中

([1T;`qXa a^U0 2}%hYr6{p e ^

var(O[jLmc

*H(YSZ[,_

header=block.Header()6|6Mgo,wq

Tx RocAK2DPm0HT"\

hash=header.HashNoNonce().Bytes()

3j[v o'ef,c5caM{0 $s'] a/m!c

target=new(big.Int).Div(maxUint256,header.Difficulty)//后面有大用,这是用来验证的target

9r!zh6P Sqd0

oknx _!aU5N0number=header.Number.Uint64()S`xV\!Z,e

*I [rI&t3q6zhWC(f

dataset=ethash.dataset(number)

C/gf {V6wR0

]3x)e ^Z2yo-K0)

,H Xv5N$EVW'm0

D1u5{D:G7e0@0v+yQ0//开始生成随机nonce值知道我们中止或者成功找到了一个合适的值

FW x};d'` U}0 5g~)j(I%i"N`2h?

var(

#G\Awc5mv(G0

b0i#anO_^q nV0attempts=int64(0)//初始化一个尝试次数的变量,下面会利用该变量耍一些花枪ss4AE$Np|

+e `+Yq5O0nonce=seed//初始化为seed值,后面每次尝试以后会累加3?MG7R.B{8sQ

ov9pea S

)

"B)cuV d|3Kw0

1n(i/HQ-{8Lz0logger:=log.New("miner",id)!? ] AU]i

$C ? b'FPk eJX0logger.Trace("Startedethashsearchfornewnonces","seed",seed) AO3@Z4m k

d1B7mMb!\&X3p3k]0for{

e:|xqh(B0 n;I5}%~)pd

select{

WK.y%u,V;p0

v[9v8b7f%@;i0case<-abort://中止命令#eN)p/M6s;f

ztU2y9A0H;S4Xn{Q

//挖矿中止,更新状态,中止当前操作,返回空(F] L9r?Ks/S

G2o~L"H k|1y

logger.Trace("Ethashnoncesearchaborted","attempts",nonce-seed)

.FsmehB0 ea*wPN#I

ethash.hashrate.Mark(attempts)L(N9s vx Q-c`cc{

zuM'H,e&p

return[#I#R f`

\/^ ]+K*H0default://默认执行@RV)HVP t A#b k

7t2Va:W \;Eo%~U7G

//我们没必要在每一次尝试nonce值的时候更新hash率,可以在尝试了2的X次方nonce值以后再更新即可

].SF0Z5jm0

h4t+o^d_0attempts++//通过次数attemp来控制{(URJ!NC"b_-};R

4N%X2Kd/VM

if(attempts%(1<<15))==0{//这里是定的2的15次方,位操作符请参考http://www.cnblogs.com/Evsward/p/go.html#%E5%B8%B8%E9%87%8F%L#R][ K&Quv;N(Y

.N*bW)T O7?I7Z8j0ethash.hashrate.Mark(attempts)//满足条件了以后,要更新ethash的hash率字段的状态值

WZ{p Vd3I0 W#^0qP v K-Ms

attempts=0//重置尝试次数#^!q)s fW3[;fGp*f

`#lu$Lc,X0}6A3q ^5W0f1vk5r

(}&ko a\j-P

//为这个nonce值计算pow值

#y1tb1M%MQr%R_0 fq1[(BM @Ss

digest,result:=hashimotoFull(dataset,hash,nonce)//调用的hashimotoFull函数在本包的算法库中,后面会介绍。JM)G d8k|1sDf$["l"O

o)V~nr'c/DuW0ifnew(big.Int).SetBytes(result).Cmp(target)<=0{//验证标准,后面介绍

e$Kl(j|X$v0 Y3F+]R-HX9_i

//找到正确nonce值,创建一个基于它的新的区块头 S Y!{;L$HEL&mc

9e I`x T!r

header=types.CopyHeader(header)

Z/\gK'M6g8c1q0 o,z n)u%S:pI.c

header.Nonce=types.EncodeNonce(nonce)//将输入的整型值转换为一个区块nonce值vxp;b.c8m]4L

$\Lk C$uc Q4u

header.MixDigest=common.BytesToHash(digest)//将字节数组转换为Hash对象【Hash是32位的根据任意输入数据的Keccak256哈希算法的返回值】:q Q8b9R4xF3H@

n,a}e kvg

//封装返回一个区块

k v+be![G[ R0 zm;uG[*f(s

select{

WG"Ap$I7d U0 n$M1a7[x,V

casefound<-block.WithSeal(header):

%MB;Kn*dX0~BE|.K0 'B!V"@ [HO C|

logger.Trace("Ethashnoncefoundandreported","attempts",nonce-seed,"nonce",nonce)

y7CI{I/}ab0

$sRmP;XXH.S0case<-abort:,R/~D3~T }0R1cQ

)lbCZw,jCD

logger.Trace("Ethashnoncefoundbutdiscarded","attempts",nonce-seed,"nonce",nonce)

xSmqk@Y0

6tK#FW/E!C0}

En.R!iD%T0

5ja C]O~;b^\0return

e[i#?,Dl:u0 a'V3z/yl8Da,v6]

}

*wq W M/m0 Dn7s.w9ay

nonce++//累加nonceY/^ b1Z(V-E"m p

7z&q x^R`[V}3c

}

!}8Df[ _&Ke0

'p8}!\Wo y$cD&GQ0}}

#LlNV,y"Z:I0

*u!AL8t(qj/D4O:P0mine方法主要就是对nonce的操作,以及对区块头的重建操作,注释中我们也留了一个坑就是对于nonce尝试的工作,这部分内容会转到算法库中来介绍。#uT q}1I)_K]X

JS h!B;V%@0m%{,n#R9X

algorithm(HP0nUoWW

E L;G/W/b-bX _

ethash包中包含几个algorithm开头的文件,这些文件的内容是pow核心算法,用来支持挖矿操作。首先我们继续上面留的坑继续研究。lO0Z}C h UI\?

,r5xH/V2R$o)}qH(h`0hashimotoFull函数EGU?,ET'e` `)k

&r?4|8T_}

该函数位于ethash/algorithm.go文件中,

t:B ?8K2Gb$c:f/YH:h0 &@-F'Ql:JU2wI T'`

//在传入的数据集中通过hash和nonce值计算加密值funchashimotoFull(dataset[]uint32,hash[]byte,nonceuint64)([]byte,[]byte){

3Mxu$X#e Sm0 3ts2g(c"N2@a+Jx

//本函数核心代码段:定义一个lookup函数,用于在数据集中查找数据

1BQo6|4G(C-[0 !|eHw'uz g

lookup:=func(indexuint32)[]uint32{

8}]{{!@0

`-n ltu0offset:=index*hashWords//hashWords是上面定义的常量值=16

%s"Y+h8['|-I#K:~+?^*u}0 oHU)unaf

returndataset[offset:offset+hashWords]

"P;j,Z2p#^J0 1]rtT0I\c

}w-{ a)i:p7UkblM

7c4p;f1|N0//hashimotoFull函数做的工作就是将原始数据集进行了读取分割,然后传给hashimoto函数。

/bt CO3s:pz'a S0

n9X9C:D US kE0returnhashimoto(hash,nonce,uint64(len(dataset))*4,lookup)}!h@S4R9S:Q

;l9BHM.]4d4m-p NF,{)o0hashimoto函数

Tv@_~7i n.Kw/?0

"Fr-H5^7[.{E8x6\0继续分析,上面的hashimotoFull函数返回的是hashimoto函数的返回值,hashimoto算法我们在上面概念部分已经介绍过了,读源码的朋友不理解的可以翻回上面仔细了解一番再回到这里继续研究。G?bh3I xz*C ?

"O2SB.Pu D2~0//该函数与hashimotoFull有着相同的愿景:在传入的数据集中通过hash和nonce值计算加密值funchashimoto(hash[]byte,nonceuint64,sizeuint64,lookupfunc(indexuint32)[]uint32)([]byte,[]byte){

6i_7fsp7i2IH:k0

(j8J!]#M&?(V.L;i0//计算数据集的理论的行数

*@:DN @C gk,V0v0 +iSC)j'{

rows:=uint32(size/mixBytes),hy t7BH~.t

[ W&gA'[ Yu%Za ^

//合并header+nonce到一个40字节的seed

Ui$d7w-jY b0

,R4k8C.Wo/b2x6i0seed:=make([]byte,40)//创建一个长度为40的字节数组,名字为seed

? TAv4s5D2qxZ9?0

}q/J0C+o:F0copy(seed,hash)//将区块头的hash(上面提到了Hash对象是32字节大小)拷贝到seed中。

4} a7Lk^%wu0 IvJl)zKe

binary.LittleEndian.PutUint64(seed[32:],nonce)//将nonce值填入seed的后(40-32=8)字节中去,(nonce本身就是uint64类型,是64位,对应8字节大小),正好把hash和nonce完整的填满了40字节的seed

(P{w9H7aWW9b0

C:L$Q:^5w-V0seed=crypto.Keccak512(seed)//seed经历一遍Keccak512加密[*UCU ? Fh

S/_*b?'AC

seedHead:=binary.LittleEndian.Uint32(seed)//从seed中获取区块头,代码后面详解

+SD&yf"T.\0 X+{%~?R,M\,n:r

//开始与重复seed的混合

q-^0V6doR0 &~x-\+I1{ q

mix:=make([]uint32,mixBytes/4)//mixBytes常量=128,mix的长度为32,元素为uint32,是32位,对应为4字节大小。所以mix总共大小为4*32=128字节大小

$tO$t2n2S0 ,D\e5Ho1A0P.LF

fori:=0;i!Rj3C*mz,^%x1?7N

!q aLb)X \ w \NY(T-@0mix[i]=binary.LittleEndian.Uint32(seed[i%16*4:])//共循环32次,前16和后16位的元素值相同?Qi#b;F0N

1B.mF(K3Yg br0}U{%B9?+H2t:I W%N2o

_9} `Du&Wa0//做一个temp,与mix结构相同,长度相同9Z_&t2Zo,o

DXG \*N~)P`0temp:=make([]uint32,len(mix))

#JC,ie)}$\ z(r@6~0 (\MI }:d'a8S8c

fori:=0;iJ+I,@{2d+lD2T!d \

x2[ZO u

parent:=fnv(uint32(i)^seedHead,mix[i%len(mix)])%rows//mix[i%len(mix)]是循环依次调用mix的元素值,fnv函数在本代码后面详解

*A _,}-A;QNz9m0

,fF W%a.R@ d`2Z0forj:=uint32(0);jN8m \u1g ?0 D n0vOM

copy(temp[j*hashWords:],lookup(2*parent+j))//通过用种子seed生成的mix数据进行FNV哈希操作以后的数值作为参数去查找源数据(太绕了)拷贝到temp中去。4N)h{f5cY,J a5dY

0``I ^ ]3{A0}

DcD O c*~-|+C V+f0 q+J+E9Pz

fnvHash(mix,temp)//将mix中所有元素都与temp中对应位置的元素进行FNVhash运算

J!]2s4?4Om8c/n&m0

_9E8QN-g0}

8Z;t0R,O#`q&L W0 C\p%\d9jF7d1`

//mix大混淆$G8}@EVIW;t8\

f_'Km)`i9Rl5@.H:~

fori:=0;iL1f C9CP+]l%v0 7D.G.mD1o1Q

mix[i/4]=fnv(fnv(fnv(mix[i],mix[i+1]),mix[i+2]),mix[i+3])RD'x3B3Y ~+@(V?

'swf+pj0}

H8K_h z9z(vD0 .^@F"CBn'H#r

//最后有效数据只在前8个位置,后面的数据经过上面的循环混淆以后没有价值了,所以将mix的长度减到8,保留前8位有效数据。

v r+u#_Wq@]0

o0MC t E@0mix=mix[:len(mix)/4]{eCf F5?"eC7E5t

S.d4_ EfFd~/m"e:E

digest:=make([]byte,common.HashLength)//common.HashLength=32,创建一个长度为32的字节数组digest K8SiEKn6|V s|U

8N$~y/zcx/~0fori,val:=rangemix{

7c }"D,[@S0 #t:d fT6[ S;G

binary.LittleEndian.PutUint32(digest[i*4:],val)//再把长度为8的mix分散到32位的digest中去。

jFO { YDs _S6S0 zg$]Y0I1AN O

}

&t f+_gPdt8?:o0

f i"Wp|I,_0returndigest,crypto.Keccak256(append(seed,digest...))}

3J)Do&t\eH0

-eoC!T v!F5J)~]f!H~0该函数除了被hashimotoFull函数调用以外,还会被hashimotoLight函数调用。顾名思义,hashimotoLight是相对于hashimotoFull的存在。hashimotoLight在后面有机会就介绍(看看能不能绕进我们的route吧)。1f?$mb}!nCMC

'`*af&g7?^ S,D m0下划线与位运算|&cJJO3S4h^

*eW5p ca I

以上代码中的seedHead := binary.LittleEndian.Uint32(seed),我们挑出来单练,跳转到内部方法为:

xK qa6`N0

\b ZSu5g0func(littleEndian)Uint32(b[]byte)uint32{#xS Exv ^

@+[*j`1H!W\

_=b[3]//boundscheckhinttocompiler;seegolang.org/issue/14808d oz/D&e"O{

:^)_ J"{_ I

returnuint32(b[0])|uint32(b[1])<<8|uint32(b[2])<<16|uint32(b[3])<<24}

'm'W|Q?*|"\t0

fF,AMa~e0go语法补充:下划线变量代表Go语言“垃圾桶”的意思,这个垃圾桶并不是说销毁一个对象,而是针对go语言报错机制来处理的,所以b[3]这一行可以是b[3]未使用防止go报“xxx未使用”的错误,同时观察后面的官方注释,也是为了在真正使用b[3]数据前进行边界检查,如果b[3]为空,则会提前报错,不会引发程序问题。%^#Q1vML`$pa*U

#K(p6X8t,H|S

位运算,我们在《掌握一门语言GO》中对左移和右移进行了介绍,这里针对或|和与&进行介绍。位运算都是将原数据转换为二进制进行运算,或|就是0和1或得1,例如1和2或得3,因为1的二进制表达为01,2的二进制表达为10,01和10或运算以后就是11,等于3。同理,与&运算就是,0和1与得0,所以1和2的与运算结果为0,因为与&运算是只有都为1才能得1。r!T|i XD)A

g)k5XH3C X0q0FNV hash 算法-^Y \`W|5{ _*y

I^E!B"QW {n

FNV是由三位创建者的名字得来的,我们知道hash算法最重要的目标就是要平均分布(高度分散),避免碰撞,最好相近的源数据加密后完全不同,哪怕他们只有一个字母不一样,FNV hash算法就是这样的一种算法。

0GF1~,g4L"?3P l0 ouP WDnRTI5[

funcfnv(a,buint32)uint32{

Py!H\Eu K0 o0eDWh@ I!@S

returna*0x01000193^b}funcfnvHash(mix[]uint32,data[]uint32){

qca1YQ m;t%dP0 lL f^4{&uq e`

fori:=0;i.WJrT'O:q!BV0 r!AUn/Lt"h5n1I

mix[i]=mix[i]*0x01000193^data[i]

r@6~s M/rl ~0

C7?N {4_u-x;lH0}}

1o/@,A|.r F0

1QNTSNB'O00x0100193是FNV hash算法的一个hash质数(Prime number,又叫素数,只能被1和其本身整除),哈希算法会基于一个常数来做散列操作。0x01000193是FNV针对32 bit数据的散列质数。5@7XWD5r ZK^_8?V

'A/X4y"EKD)k

验证方式+gm&uS V Mk

X3Y,Xa ?s?9b Fi

我们一直提,pow是难于计算,上面这么长篇章深刻体现了这一点,但是pow是易于验证的,所以本节讨论的是ethash的pow的验证方式,这个验证方式也很容易找到,就是上面mine方法中我在注释里留下的坑:

8}kGx!_C D0

2dRy*i#N0new(big.Int).SetBytes(result).Cmp(target)<=0r^Zx7['y3c

4T#Zm"G+Mf EC

我们的核心计算nonce对应的加密值digest方法hashimoto算法返回了一个digest和一个result两个值,而由这行代码可知,与验证方式相关的就是result的值。result在hashimoto算法中最终还经过了crypto.Keccak256(append(seed, digest...)的Keccak256加密,参数列表中也看到了digest值。得到result值以后,就要执行上面这行代码的表达式了。这行表达式很简单,主要含义就是将result值和target值进行比较,如果小于等于0,即为通过。

rUav8{)l0 3_J o:Vyb8^Ul

那么target是什么?

y;fIQhxKg,n0

B.a'eyp7i` i0target被定义在mine方法体中靠前的变量声明部分,

n'N)FlJ:q0

1M$r3X.i{u"w5Wz0target=new(big.Int).Div(maxUint256,header.Difficulty)2w0}q _v/W9de;\

j0gQgmp9y'U

可以看出,target的定义是根据区块头中的难度值运算而得出的。所以,这就验证了我们最早在概念部分中提到的,我们可以通过调整Difficulty值,来控制pow运算难度,生成正确nonce的难度,达到pow工作量可控的目标。

Z'rY0c@[RZKh0 ii)I$T5uB9o1[

总结

La4Np7jd0 Yle*X(`

代码读到这里,已经完成了一个闭环,结合前面的《挖矿》,我们已经走通了以太坊pow的全部流程,整个流程我没有丝毫懈怠,从入口深入到内核,我们把源码扒了底掉(实际上,目前为止的流程中,以太坊的pow并未真正使用到如我所想的DAG)。到目前为止,我们对pow,以及以太坊ethash的实现有了深刻的理解与认识,相信如果让我们去实现一套pow,也是完全有能力的。大家在阅读本文时有任何疑问均可留言给我,我一定会及时回复。

0W,@6U3r9]s;F F1Y0

来源:金色财经(区块链技术) https://www.jinse.com/

以上信息版权归原作者所有,不代表本站立场和任何投资暗示。

火币网注册