Dagger Hashimoto

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

D(U*|`Z0W

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

8}*\{ ?$LA#F0

{ ]$U?s(D0此文章来自[区块链技术社区](https://www.liankexing.com),未经允许拒绝转载。

`aV\8fcAA0

Xz A)Y!p7bD.U7K0

e,v-R%Q"{N0S*Qu'o0

X8X4O,A,S ee@#a,l0Ethash

0o?"bq-g-{'~3pd^,^0

&W*pu~8E@)Gm"F0前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DAG有向无环图的算法,这些都是本文要研究的Ethash的基础。Ethash是目前以太坊基于POW工作量证明的一个共识引擎(也叫挖矿算法)。它的前身是Dagger Hashimoto算法。V5Q(IZ,w;S-s

$Fi;Nu?t0Dagger Hashimoto

2h%{@&G%]O] v0 &Jd*h|*rdN2M

作为以太坊挖矿算法Ethash的前身,Dagger Hashimoto的目的是:j On;G+P/x

NTD u"QraW0抵制矿机(ASIC,专门用于挖矿的芯片)

Cc#sg:Lg)n@0

M*d8B8e9M6U-X0轻客户端验证%o#iA o F3y%a$[&g

_i,Dq3t0全链数据存储E'`~7er

/O'G1AXww0Dagger和Hashimoto其实是两个东西,PX G#T"} O

sf,fY~ LGd

Hashimoto算法

%u2Hjr%G$_:D_ MQ s|0

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

k8e W` AB3qP+s+[ R

Dagger算法

4V {nG,]S n/p)H0

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

x!S n/wv:| H"r+y0 $u2Y,c+?6u(^*@

Memory-Hard Function

9UB*G0cN8S5C0 #O"T VF P

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

W%K5n-ll*JJoe#gZ J0 6|8} _f5Dtw

那么该如何让挖矿设备是平等的呢?

.M[S\Rv$kE0

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

p-O5Xp2Mi.`,|0 6p}:l9| `V]"p J

两个问题的研究P+Kk8Ul4{-E;q

o6?;r)W0z!{i6g,VD0在Dagger以及Dagger Hashimoto算法中,有两个问题的研究是被搁置的,8y1\(U Gb9x

xB:Y){;hRePO~

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

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

Q"{;IO G,P9X*K0

J8n ?%m$iL0OP0Dagger Hashimoto算法

HM!Yk[H0 {r4W3[#s+P

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

kZH0ng!D4m3v0

f%~1sK*H G0这个数据集是基于区块数据每N个块就会更新。该数据集是使用Dagger算法生成,允许一个自己的高效计算,特定于每个轻客户端校验算法的场合nonce。

}1Ep"@8a(EXUf,SY L4j0

^| k*sv\ H5?}0(区别于Dagger)Dagger Hashimoto克服了Dagger的缺陷,它用于查询区块数据的数据集是半永久的,只有在偶然的间隔才会被更新(例如每周一次)。这意味着生成数据集将非常容易,所以Sergio Lerner的争议共享内存加速变得微不足道了。J'm$m _m^r d

_I(`s q4B6o

挖矿补充_Y#x V%phd#a

[B@$TB({7W(px

前面我已经写了一盘关于挖矿的文章了,这一节是挖矿的补充内容。 HHK z'S V$](p,dtm

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

d0bKl^ |I3p;\0 'u2B B/Vi3nA ]!a

挖掘以太币=网络安全=验证估算(^8?.gX Fu2lp"L

K){0B3Gg0目前以太坊的POW算法是Ethash,d-d+p0[G}-D(~(L%~

R)|t5@q u#F~

Ethash算法包含找到一个nonce值输入到一个算法中,得到的结果是低于一个基于特定困难度的阀值。"[g?1mVle(Z g

@ MR/{g;O(Y m.vwz0POW算法的关键点是除了暴力枚举,没有任何办法可以找到这个nonce值,但对于验证输出的结果是非常简单容易的。如果输出结果有一个均匀分布,我们就可以保证找到一个nonce值的平均所需时间取决于那个难度阀值,因此我们可以通过调整难度阀值来控制找到一个新块的时间,这就是控制出块速度的原理。"|9M-|2X}IcaV

@$e3ObL+DY+\0DAG

-w Y%yOe0

L.CB5{2n}uy.H0Ethash的POW是memory-hard,支持矿机抵御。这意味着POW计算需要选择一个固定的依赖于nonce值和块头的资源的子集。IGqG ~wY

3V.w6db7oYd v0这个资源(大约1G大小)就是DAG!

h {#e\)e0 G-K+m;n n

一世epoch

6E%}!SK2hK{u8Mk0 $P a%k |S9]"X8M

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

8f9@QrL#^1v U

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

'ko&t(@-}B2RwC0

;@gC-~E m,|T;R0K6V&`#e0挖矿奖励

} c,m]:| c;}c0 ;Bk~#B(UQaqy

有三部分:3yo i!|*w/IgZ/`

n8a8yDK A%Q@Z9U

静态区块创建奖励,精确发放3以太币作为奖励。

n g(Z7n7j(C@.E#Q0 U7G+R3O}gp F9uk

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

I/f0Qs-c4o9^LB0 :De*z]2qGa

叔块奖励,整块奖励的1/32。_'VR(t7rgg

jK/WSL$}R7Nc0Ethash7hkj@pl t

0q?(T*T8H/m

Ethash算法路线图:U U L*]$j G1L$r zT

:ZS*q h z*W|

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

;w!fl ?DWF0 P K1w7f+D Xjg a

根据这个种子seed,可以计算一个16MB的伪随机缓存cache,轻客户端存储这个缓存。

Rg(iF"j.C uB0

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

"\c{.t Mb0

| t$EyE#Q G0挖矿工作包含了抓取数据集的随机片以及运用哈希函数计算他们。校验工作能够在低内存的环境下完成,通过使用缓存再次生成所需的特性数据集的片段,所以你只需要存储缓存cache即可。.j0V1~nCg;P}hm+@

Y6H!E9?O

以上提到的大数据集是每3万个块更新一次,所以绝大多数的矿工的工作是读取该数据集而不是改变它。lp\Qowtq

$HE)f&Z;W??c0pkg ethash源码分析

eMb5Bg z0

$A1c)S)L"[{[ Ja0以上我们将所有的概念抽象梳理了一下,包括POW,挖矿,Ethash原理流程等,下面我们带着这些理论知识走进源代码中去分析具体的实现。正如我们的题目,本文主要分析的是ethash算法,因此整个源码范围仅限于go-ethereum/consensus/ethash包,该包实现了ethash pow的共识引擎。nG t^8w"d

] w V%{d`T

入口

"H'|;`sh_4C1~_Z0 .PUi#L0I#R v mi

分析源码要有个入口,这个入口就是在《以太坊源码机制:挖矿》中挖下的坑“Seal方法”,原文留下了这个印子,在本文进行展开讨论。w cHZ'hIG2H6A7@%f

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

'pi`,rB0

Cdg;c!Q"j0Seal(chainChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error)//该方法通过输入一个包含本地矿工挖出的最高区块在主干上生成一个新块。

8P h@ ByII GT0

$`!kC+z.|+Y Q9lT2?%V0参数有ChainReader,Block,stop结构体信号,返回一个主链上的新出的块实体。

P\%uk,^m0 #E.~6?8S~/Zp

ChainReaderF z+W5T,^K!}

|'t0x\ w:PlF {

//定义了一些方法,用于在区块头验证以及叔块验证期间,访问本地区块链。typeChainReaderinterface{

JN hPKl0

Y"L(uV^J$j\vC-z u0//获取区块链的链配置.jK6QT"F6n&o:d

7Hwp$q d0h0Config()*params.ChainConfig//从本地链获取当前块头

6SsRAtc0

DP7Z8Y7_m0CurrentHeader()*types.Header//通过hash和number从主链中获取一个区块头

i|3oV+c1a#I/Y0 TN4iU@P$]^3e

GetHeader(hashcommon.Hash,numberuint64)*types.Header//通过number从主链中获取一个区块头QjHQ?

e Z[d3QD0GetHeaderByNumber(numberuint64)*types.Header//通过hash从主链中获取一个区块头/U;|ww~UYU

-M(e5D9Ri5SP%x(T0GetHeaderByHash(hashcommon.Hash)*types.Header//通过hash和number从主链中获取一个区块7D6Y)p2I*M @V q

7ZZVn+W1R^o

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

!cs?1I l"H N0 b xq%E Y7G l-a)aY/Z9_ y

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

J{Jvr8@g0 u T JX3O,F{

Block(Ewh&b-L+CD4Y6K$[0[s%z

/A%O9S;W[o'Bxl0//Block代表以太坊区块链中的一个完整的区块typeBlockstruct{MQ&hj+z.y6?%m,\9r

%S t ZJ+{)j-D3z&h

header*Header//区块包括头{8q0? HB

Ha;UK*n kEp9n0uncles[]*Header//叔块

} n$Pc#W(g-g'[0

/X|U]s{S8a$_%i0transactionsTransactions//交易集合8wGS7U[|7_P2v

"p X m:m{8t B0//caches缓存

3`t^tZd0 jmB0Wb%N|

hashatomic.ValueC$z!{n fx d/f

M2?&p(w$@-E:[1l]8ax&{

sizeatomic.Value//Td用于core包存储所有的链上的难度

!mD TWaiW;M0 VA)u.S9S

td*big.Int//这些字段用于eth包来跟踪inter-peer内部端点区块的接替E:`&} Y(s'`

,? o;@ QS x

ReceivedAttime.Time6B+lb;E_~H~}

\+[2@J/y~

ReceivedFrominterface{}}Kw*doys*O(p v3]

{c!t \`%s-HQ0总结,Block除了我们熟知的区块中必有的区块头、叔块以及打包存储的交易信息,还有cache缓存的内容,以及每个块之于链的难度值,还有用于跟踪内部端点的字段。Fi2e$Z1y"s

,^&O!D:?uu*Z`0stop

Q} C3P.\0 9Fk#b9gkuP(Z2Z

stop是一个空结构体作为信号源。

y*Y/~%X%G#B0l0 1e/GC)zo U%lN~

关于空结构体的讨论,为什么go里面经常出现struct{}?

lR/@&y?q@0 -M4an&o^&kwdD

go中除了struct{}类型以外,其他类型都是width,占有存储,而struct{}没有字段,没有方法,width为0,灵活性高,不占内存空间,这可能是让Gopher青睐的原因。:G&E wxI:rJv

+E^#U e!V:P4?0sealer

bIkyWf0A;Q)Z\7w0

nH5ZA.E6qs0seal方法有两个实现,我们选择ethash,该方法存在于consensus/ethash/sealer.go文件中,第一个函数就是seal的实现,先来看该方法的声明部分:

e"v!d.Q7Mj1^`4m0 4[#W$K.aVh-k!m-t;w

//尝试找到一个nonce值能够满足区块难度需求。func(ethash*Ethash)Seal(chainconsensus.ChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error){

4o S)~[b3l&b0

j/S`Q(d5L1^+F0P$x;y0e0可以看出这个方法是属于Ethash的指针对象的,

3r8rCQ6f0

j%K3A&M A*L8F0typeEthashstruct{ R%Lo:R^%@-O)n*U

7gQ(a5N3~(CW(oG0//cache配置

\4p8S:J'i+aJ0 Cm%mlz!Z5b~

cachedirstring//缓存位置

qh(F1Y&D%l8ChF0

1Ez1e%fj)K&U)p1y8^0cachesinmemint//在内存中缓存的数量

!q$Z Rng5_0

.?\7C(R8h0cachesondiskint//在硬盘中缓存的数量.}/t4Z \;|%j+f

'_iEJgP*X V

//DAG挖矿数据集配置O^)[OlR s]-cj

] HOt0O&CO0dagdirstring//DAG位置,存储全部挖矿数据集t:X@1g,g

Hj*a1w FNoqP0dagsinmemint//在内存中DAG的数量

2wHTc.ag0 e]#W+J,f~F

dagsondiskint//在硬盘中DAG的数量{IZ7s[1~0{`O

B+Cp&gw_-M3S6ls0//内存cache

#k$v*[ [(oen0

~l.aKF0cachesmap[uint64]*cache//内存缓存,可反复使用避免再生太频繁

`7] ub`3V*fn NS0

5K5q0w2W6Bmba0fcache*cache//为了下一世估算的预生产缓存TPs%R X:Hg@A

`5|T9zH9}'aq

//内存数据集

K7a(|Tzy'J0

A%@As~Nq-nQ0datasetsmap[uint64]*dataset//内存数据集,可反复使用避免再生太频繁Zfv^wE

0l6_[9x!Fa r~K0fdataset*dataset//为了下一世估算的预生产数据集?#vG0{H(gbnZ7cg

3t0HQ(P6F+b\0//挖矿相关字段k5_S~1JNy9gv

\ V:P1|7i0rand*rand.Rand//随机工具,用来为nonce做适当的种子

.t|+a T5Z.L a5~0 \&Y;^-} v N~!f+r(GLJ

threadsint//如果在挖矿,代表挖矿的线程编号)})X])[ G^C

H;^$M NL S0updatechanstruct{}//更新挖矿中参数的通道

i? EMK0 0s9k,a1rF5NKtZdf

hashratemetrics.Meter//测量跟踪平均哈希率0F.vA }m

K%s-o7N4m{\7kOc0//以下字段是用于测试

!hD/O6bg]A }n)f3q0

!JT5jF UV0testerbool//是否使用一个小型测试数据集的标志位

$H Y~9O6A0

6k f%z `F P @9Ji(D0shared*Ethash//共享pow模式,无法再生缓存

%F1T.?"{ X1A8DIF0 |bT9\ [QfK^

fakeModebool//Fake模式,是否取消POW检查的标志位

t;}1t1a#` S[0

v{!XB/n:X`m0fakeFullbool//是否取消所有共识规则的标志位 s:@R(~ O

)rj'rP"N5Y

fakeFailuint64//未通过POW检查的区块号(包含fake模式)|7jZ~d I

oS-iY$I.ak

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

hp8Z} N*VV Q%n m

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

ou{]Y+bu/\W&d0为了更好的读懂之后的代码,我们要对区块头的数据结构进行一个分析:"s bq F U*`N2{O1LU

O-Z_0C2i8o;Z*u w^U

typeHeaderstruct{*^0?s*?'C"[y

Y TZjV*m+t \0I0ParentHashcommon.Hash`json:"parentHash"gencodec:"required"`

2C1n G1j"Zt.L AW0

1jG ufb@0UncleHashcommon.Hash`json:"sha3Uncles"gencodec:"required"`^+B,[/_-D Xi*@(E

.an4d&O8h1f'E3\0Coinbasecommon.Address`json:"miner"gencodec:"required"`

6n%x h[X*\r0 w'Y;|f}V-WD?` ~

Rootcommon.Hash`json:"stateRoot"gencodec:"required"`

+qos9N-q8N$a h0 o d-`@o S5@K

TxHashcommon.Hash`json:"transactionsRoot"gencodec:"required"`9s}pTU/R

3WV4E5REbEX%m

ReceiptHashcommon.Hash`json:"receiptsRoot"gencodec:"required"`

4V j S5Q.s'F\J0 gfz0?;{BYw

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

-W5k]B\6P0

b7MW5tR.])` IP6];z0Difficulty*big.Int`json:"difficulty"gencodec:"required"`

h M9|B(zPU#a0

0d0v6fQ!w0Number*big.Int`json:"number"gencodec:"required"`

,Thq YaJn3r0 r9OP6Fqu8m

GasLimit*big.Int`json:"gasLimit"gencodec:"required"`

b mb4Hm0

q{"iy5|)?M5kz0GasUsed*big.Int`json:"gasUsed"gencodec:"required"`

,U'YR9g/I'B6y0

,CgbD o4Q0Time*big.Int`json:"timestamp"gencodec:"required"`

Z U4DK0||0 4m*ox|_{(Sf&W

Extra[]byte`json:"extraData"gencodec:"required"`0\;w^8XR ~'?

4\&p5yf mRh)C,X E

MixDigestcommon.Hash`json:"mixHash"gencodec:"required"`?+a#Bm6d

/P7P[S9Wp

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

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

`,TLhi8`EwCf0func(ethash*Ethash)Seal(chainconsensus.ChainReader,block*types.Block,stop<-chanstruct{})(*types.Block,error){n0f2jNz(s

J"fM"g(Ne0u,za!@

//fake模式立即返回0nonce^y,oKN!o,iA\9L"M

r hpz4k\5x,`x1`0ifethash.fakeMode{H9^,e8? y/w

C U"}:l S

header:=block.Header()

Y.i*gHd|-Cii%h0 1~:I5X/h$kW7F

header.Nonce,header.MixDigest=types.BlockNonce{},common.Hash{}yJ+p0^ rcA

6oqSZ&Y9D)^"B Sv

returnblock.WithSeal(header),nil},^)k8d0[g$z

;qC#|G5b({(r0//共享pow的话,则转到它的共享对象执行Seal操作

)wKj3[w;mY0 &h K7}^a.I&u M

ifethash.shared!=nil{

$w)M/o?&ao0

9Y X7HoZB@zk6B0returnethash.shared.Seal(chain,block,stop)!y+~'S1syQ{1S

h)Evz3J%~6?fN0}

7M#`aXU"x0

B unv+c:]t0//创建一个runner以及它指挥的多重搜索线程6a0GL8]k

&^oo:D6qz

abort:=make(chanstruct{})

@Q|Jd/j0 jD MxDM

found:=make(chan*types.Block)-HyA n}+iB

8A"W(p6Ln(o(v0ethash.lock.Lock()//线程锁,保证内存的缓存(包含挖矿字段)安全

EH Drp0 6x4`I)Y6SX

threads:=ethash.threads//挖矿的线程s

X2U5CWcY$t[0 N~s'y he-B.Uy

ifethash.rand==nil{//rand为空,则为ethash的字段rand赋值9g ] U)i~L?Z*g

B C8CV4X,Y;Y%l6B

//获得种子

Q3r m7^*Lg]3z0

'hA}trH(TCAr0seed,err:=crand.Int(crand.Reader,big.NewInt(math.MaxInt64))OwMU7p~

7X.N1L3e%?-Z+G ?0iferr!=nil{//执行失败,有报错qb/x:tlS'ly*E[ SU

K/{"A(x8`c-P

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

P _'^Gx(R-R9Q0V2}0

M{yjP @%}.W+e%o0returnnil,err//程序中止,直接返回空块和报错信息

gV Q~]:HSh3u9rM0

sw+U3GUv8p0}

xu1B.wHt2q&x0

{+Q_Z-yo_0ethash.rand=rand.New(rand.NewSource(seed.Int64()))//执行成功,拿到合法种子seed,通过其获得rand对象,赋值。

Zqp-j [dc0 |9@w5V6h M

}?'US$aryng

Cvf!C&V\ T4e;q_0ethash.lock.Unlock()//解锁&P%Tv]zk

*QLU3Xi{4k

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

0}S \(e` b3P0

:m g}#F(~0threads=runtime.NumCPU()

;uK7je$u\ c&D[0

-QN^)j0y `W+q[0}

,V\S7em o0G0

9A;JU7?$_ ?_F0ifthreads<0{//非法结果TSE g+Dj

T1DA8z"D F!u e0threads=0//置为0,允许在本地或远程没有额外逻辑的情况下,取消本地挖矿操作3M#j7B:] eM

Bkr)Z7Z1qh5h

}

*kdc4l@"x Sf0

:h7T)?9H @ p)|J/E*z0varpendsync.WaitGroup//创建一个倒计时锁对象,go语法参照http://www.cnblogs.com/Evsward/p/goPipeline.html#sync.waitgroupG3x1D3L!c;S+c {w%ff

9w/t{ I,x"s![ \l

fori:=0;i q s/otX2XS0

%P:N;qq^OJF0pend.Add(1)C~_-Jd3uy)srH

S1@MAjE0gofunc(idint,nonceuint64){//核心代码通过闭包多线程技术来执行。3^X@ s|Fn&n

5f KU.~R)qu

deferpend.Done()

)SGP/} z0 %uT U"O A![~ R

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

#wi p&MUC;q

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

%w#nX;K{C,_0UQ0 U\C,^%g`-k1Wb'd8M)f

}HxpE"e a

|[ e:X!TWs

//直到seal操作被中止或者找到了一个nonce值,否则一直等

&I2@ @+Ur7Co0

m2tT v"TU0varresult*types.Block//定义一个区块对象result,用于接收操作结果并作为返回值返回上一层lMv5nq/Y&tz i9D0Q1\

BF$v m[&y

select{//go语法参照http://www.cnblogs.com/Evsward/p/go.html#select

5D2_.F_&J;j0

Xz] {:h M0case<-stop:

'F1A7j0feU0F0 ,HP$pw"m U7{

//外部意外中止,停止所有挖矿线程sX3H3E(FX4RMH

,X7g k};??/I:?0close(abort)

%@x1r:}~ut(F0 mT1C@R TQ

caseresult=<-found:F0Iv EM&L p LK

'?4c`#\)E {;g#\0//其中一个线程挖到正确块,中止其他所有线程1E!d_W~+b @;o:l#fN

"yK5sr#I Srh&jkX0close(abort)s|;ix*WqL'a%K

M:n_v1S m.g E2iP1S

case<-ethash.update:

%k fN/_sa8w X"L0

u"^9i EF\0//ethash对象发生改变,停止当前所有操作,重启当前方法&uRc.eo@(_

*~t%@vW~8~ ZvQ'^0close(abort)wE|)PTE

_~ AsEW-y4f

pend.Wait()

}[9mhf_S-x-c%N0 `wW"f.X.f7X

returnethash.Seal(chain,block,stop)Y;Xe7H r(S*{/O

9Uas pC.I-SDh$b

}I Y"uj Bo/?Zh&E

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

yYI"k2A/g3c0 -^$b.cp:dt,]A

pend.Wait()d#bpd Kn

|.X nt BH"P0returnresult,nil}

AM sYRJm0 sE*kl2T&Gi

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

O VC i4|7Jh^H^(c

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

bvU:`%G w gF

//从区块头中提取出一些数据,放在一个全局变量域中l}Ymz,F1D

b7u~RT(x_;}

var(

&Wi.J J Zf#M.N9N0

+Y}sGm/u0header=block.Header()

(p5f"AU N ]0

tC}(x4Td6@)z9ae0hash=header.HashNoNonce().Bytes()

%h.h8H!YP-|v oQ`9pJ0

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

fX0qq$?0

i$~-S~C,i`0number=header.Number.Uint64()?*Hot~/{*ps2U

:Gy+oZz3Q:R%l)vZ|0dataset=ethash.dataset(number)/y/S o_U;B2z!Za

P:o0lD9q_[_*a

)0D1X^/eC^

vw:fw J U'b)g0//开始生成随机nonce值知道我们中止或者成功找到了一个合适的值6e~?'_9{

d.G3@ g&V#^-oq0var((n|@~:D

&yA.t| U

attempts=int64(0)//初始化一个尝试次数的变量,下面会利用该变量耍一些花枪

cD+Wpn#HgX0 3h X2[["C2`!}6Y+k

nonce=seed//初始化为seed值,后面每次尝试以后会累加z1@ILfS_u

"EH&o/H%UpB}0)

+j5[P Gkh$h0 QH9["z)H1d Q

logger:=log.New("miner",id)

a_zLR D0

R(V%p8ln;L {0logger.Trace("Startedethashsearchfornewnonces","seed",seed)

(j m Z,I} e0 9E%a/w1Y7[nK

for{ D$h z M%ZN2iqx

7pIx;l$^4E-^ C&gv0select{4o&x o [EY Y

!GM\ G%Ha_k.k7{

case<-abort://中止命令

n:?d/]zk0

+g]u4KW1U8?0//挖矿中止,更新状态,中止当前操作,返回空K5J(Iet6S

Y,[Hq\|

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

;n#X;[xo B JLfE"l0 ?*`0Pu~` _'O

ethash.hashrate.Mark(attempts)]"|{L9q.N~I

"E q,XXY0return

]nJ2D7]e8fYCR0 EX&v:pY@_e-c

default://默认执行

Z#u O4\xrQ#zH5E*z0 +vL:w1b;?

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

uI_|F N SZp0attempts++//通过次数attemp来控制;nDYh-z9n

h8C~6B.|0if(attempts%(1<<15))==0{//这里是定的2的15次方,位操作符请参考http://www.cnblogs.com/Evsward/p/go.html#%E5%B8%B8%E9%87%8FlM Y J lb P^L!h

F NZ5b?vP0ethash.hashrate.Mark(attempts)//满足条件了以后,要更新ethash的hash率字段的状态值xQ5OI/TYZ

?+e!Es-k'l|0attempts=0//重置尝试次数

(z8f7x^g,w q6K\['k0 BA@h%u2z

}

rv,Hg w0

&O1B~.y \7f6F0//为这个nonce值计算pow值 eP])B#B6^ l

ug&X:vHqF"m3aw

digest,result:=hashimotoFull(dataset,hash,nonce)//调用的hashimotoFull函数在本包的算法库中,后面会介绍。

ZQaS2f(C,Zw.c0

y*hdd)V$C8s%g0ifnew(big.Int).SetBytes(result).Cmp(target)<=0{//验证标准,后面介绍2{kZ9h w9n@

4q*V$ZI*p)as _

//找到正确nonce值,创建一个基于它的新的区块头Z2K*@9As@&H6bX"W

yl#bhv5L~

header=types.CopyHeader(header)

MY&|c$ks0

9p&j+Z5E#@]z;Wk:V"U;LW8Z6V0header.Nonce=types.EncodeNonce(nonce)//将输入的整型值转换为一个区块nonce值`8O m9Jt,g z?r

x-MdRtg"~

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

s T H:_,f)|}[0

`R.WN%X0//封装返回一个区块

G4zx$s1TX N)|?0 .d-a-{;w;BF

select{8q$l~Q_3{

#s7nsh)bK

casefound<-block.WithSeal(header):;co6Q2gP$Q1S

s ~s._6j&xl/ku0|0logger.Trace("Ethashnoncefoundandreported","attempts",nonce-seed,"nonce",nonce) z,v oTUJ l6hb7W6f

W'i$~i!St0case<-abort:

@~,zH Vlu7g`0

c2b*O&~1H S7_+a-{0logger.Trace("Ethashnoncefoundbutdiscarded","attempts",nonce-seed,"nonce",nonce) |gXs.e sTY&N,d

mDK)^/`Dc0}/~9U)C4t'GEj s'^T~

OJ6g`_V)K6PV0return

s5M{:m3MTN0

aPC {!lV/D0}+s5{ }jV?zp

&_d9[ M?J4x5^P0nonce++//累加nonce

z9~@dc&Y&I _'z0

,[-v6P;I`*ro0})Q7p1E6?%HY8Oq

`p(V*_,AA0}}

1g1BoT2YAw0 %U6D%Ej0Ix-U

mine方法主要就是对nonce的操作,以及对区块头的重建操作,注释中我们也留了一个坑就是对于nonce尝试的工作,这部分内容会转到算法库中来介绍。

4VN3wq l0

S'fyBWz0algorithm

+ILu5MW!J [0 )n2s1B6a(P[

ethash包中包含几个algorithm开头的文件,这些文件的内容是pow核心算法,用来支持挖矿操作。首先我们继续上面留的坑继续研究。wk|;_E7t+P }

X@C5I&{5L

hashimotoFull函数 WI'RV&}`g

!UGg`/O

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

#M ]+| E0~)IT0 -p+p-T kY1IYD2q

//在传入的数据集中通过hash和nonce值计算加密值funchashimotoFull(dataset[]uint32,hash[]byte,nonceuint64)([]byte,[]byte){'k%f-?fM S!k)[

M,DT6IyD0//本函数核心代码段:定义一个lookup函数,用于在数据集中查找数据/RR:h2Fl["J

cs+p,OC fj'ih0lookup:=func(indexuint32)[]uint32{7Du,V:N sJK5\*`

Uvj9g7Z2rmq-l

offset:=index*hashWords//hashWords是上面定义的常量值=16$]3P D_0ke+Z L8Qj8N

*rQWUB2U3T1v

returndataset[offset:offset+hashWords]:X'u%qeG

? ^)x&J+](j0}

'x Rhb\"q-Qq0 7c'm6}iMY

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

kR)s}-BC4I.o;e/A0

z,^RU-m'B~,b0returnhashimoto(hash,nonce,uint64(len(dataset))*4,lookup)}1[$D+^(T8SX})bFh]2w

p cmt%G'k9oI0hashimoto函数

2]1Rl6EE^0

)](}-^B9hA0继续分析,上面的hashimotoFull函数返回的是hashimoto函数的返回值,hashimoto算法我们在上面概念部分已经介绍过了,读源码的朋友不理解的可以翻回上面仔细了解一番再回到这里继续研究。

mLVgtlDg0

X7M'u,Y#bz7K |0//该函数与hashimotoFull有着相同的愿景:在传入的数据集中通过hash和nonce值计算加密值funchashimoto(hash[]byte,nonceuint64,sizeuint64,lookupfunc(indexuint32)[]uint32)([]byte,[]byte){z0]n U4o

e)^)G@ sP

//计算数据集的理论的行数7zM!\)q2\r~

%~;}c nA |W/d[V

rows:=uint32(size/mixBytes)

!wH O6q+s5qy0 Cu0v @n8Ou

//合并header+nonce到一个40字节的seed&oh'n I&pkzeDwB/D@

Z0T#R,s:sbPi

seed:=make([]byte,40)//创建一个长度为40的字节数组,名字为seed+| xfctuJ

X-QFGZ t

copy(seed,hash)//将区块头的hash(上面提到了Hash对象是32字节大小)拷贝到seed中。

|t!N| e~C;z}Y0 4z }n:X0o#C5T

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

W1]4{NV1H4`4Fy0

5@2rz4GT C]+E O }0seed=crypto.Keccak512(seed)//seed经历一遍Keccak512加密`kC!S:N)_#p

9~xK[h)C3ek0seedHead:=binary.LittleEndian.Uint32(seed)//从seed中获取区块头,代码后面详解

6OS!B2e1xEJC0 8[A K+HLfrP

//开始与重复seed的混合

c B._q:yT-T0 -r)D5P,by0E;~pM

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

(pj,Kq.\%f.b#E0 9?tIc7Fj _S'Wa6z

fori:=0;i%m wR ZM? e*@3l

W| ~WA0mix[i]=binary.LittleEndian.Uint32(seed[i%16*4:])//共循环32次,前16和后16位的元素值相同

}pN Or_/g[:F0 _N8l Ub

}

2l^KFX{4Jf;lf0 j'{o!W*w

//做一个temp,与mix结构相同,长度相同

]h2V;K O/t0

.O w-r/VN0Lp&G0temp:=make([]uint32,len(mix))

Jy^GBz1z0

^$[GkUoM0fori:=0;i M(?|7?4T

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

2R k*a\/j EE"P

forj:=uint32(0);j$X6v1{aP

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

"P0f z| B]Dz0 "|[h s1hB"uD

}:] x\"j:eyV8T

LZ6FRA9K;[/sHO

fnvHash(mix,temp)//将mix中所有元素都与temp中对应位置的元素进行FNVhash运算*TT.E3J6n.f6] M,x l)C

c&O8a/QHv)])o

}j5U|3PVI

6B vOT4U~&B1o0//mix大混淆

K+d*_8m7}(d~%H0

B"eO Vg:w0fori:=0;i+FB*B/n!ta0 :bCQ y.lS'P

mix[i/4]=fnv(fnv(fnv(mix[i],mix[i+1]),mix[i+2]),mix[i+3])

?4{ {6`~(LW'b3i'Qr0 X"[SN[b sBC:L Z

}c6{_#H}N@

Bh*R9u1N H:Fq0A0//最后有效数据只在前8个位置,后面的数据经过上面的循环混淆以后没有价值了,所以将mix的长度减到8,保留前8位有效数据。,U'i2C6e P7x0T

LR5\;^!XM

mix=mix[:len(mix)/4]om [x/fR.i f v

)|\5t8RV!@7N |)A0digest:=make([]byte,common.HashLength)//common.HashLength=32,创建一个长度为32的字节数组digest5X S0E\-nh6l

||Ow0f(e2W0fori,val:=rangemix{[X|:T*^-YV#|1T,e v

aV(zeK9Q#Q0binary.LittleEndian.PutUint32(digest[i*4:],val)//再把长度为8的mix分散到32位的digest中去。X+Am,]:s'd`:_

6UT"{n!f#D_Kx:J

}

_ SpM ?Y0 'rK/C I z6D+S(h

returndigest,crypto.Keccak256(append(seed,digest...))}CC}FFehT

sRq(EUh&?

该函数除了被hashimotoFull函数调用以外,还会被hashimotoLight函数调用。顾名思义,hashimotoLight是相对于hashimotoFull的存在。hashimotoLight在后面有机会就介绍(看看能不能绕进我们的route吧)。F3B9XA%a%B^&y

iD#HD!y7d|D e

下划线与位运算|

m-CQq AdhY0

NC%rdj v0以上代码中的seedHead := binary.LittleEndian.Uint32(seed),我们挑出来单练,跳转到内部方法为:$AyP!k,By ZY&{

bT j4fIHI)] P#Al I6^

func(littleEndian)Uint32(b[]byte)uint32{

4z+p#]8MR9w0 5nEA/rH;t@f

_=b[3]//boundscheckhinttocompiler;seegolang.org/issue/14808Z-{B6I1m7j*d O

MQ J%u7^|{0returnuint32(b[0])|uint32(b[1])<<8|uint32(b[2])<<16|uint32(b[3])<<24}

9ckh3kaDj;Pp0 #Iy8Z.iW-y }+E

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

5b;Kj{"f\O

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

7v6f tGw7M V

FNV hash 算法

.| n2_ ~.w Xi x5l'kC0

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

#J%k\4F ^&P-N0

%~/^(b;z(v.?bO0funcfnv(a,buint32)uint32{

^-x(F j&^ XQ0

*A$W.^!\tA0returna*0x01000193^b}funcfnvHash(mix[]uint32,data[]uint32){

#^6Ftq+hZ\;i0

S%f&u?.A jjN E0fori:=0;i+u%[:q-t4{BY"s!}

0I4eC`U{0mix[i]=mix[i]*0x01000193^data[i]

z j9R!M6oUs7M0

8z9wA0PXW5x0}}4i/z(Z;zw+m

-B`Vzd-O] T V00x0100193是FNV hash算法的一个hash质数(Prime number,又叫素数,只能被1和其本身整除),哈希算法会基于一个常数来做散列操作。0x01000193是FNV针对32 bit数据的散列质数。 E2@Y-W i`;cL

n$U e0aVs)N

验证方式R].};`:McT t^

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

\(C"_D7^j0

'j:]*d:} qwY ] p0new(big.Int).SetBytes(result).Cmp(target)<=0 [Y0M+o1U+ERW b

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

CE`-cF/z+b:_0那么target是什么?f_#E;J}p4Ud8Y%p@

x0VObXbw0target被定义在mine方法体中靠前的变量声明部分,

1}4Lz8V)s~ Ex'A0

8[+TH2_G0target=new(big.Int).Div(maxUint256,header.Difficulty)

(U7{ fhm9DN.A0 3})_Kt.o%E)`

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

4t%zva)v&GK)L0 WokC'N

总结

es?6Tg'x v G bi0

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

1~ x'z/O^&p0

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

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

火币网注册