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

以太坊中有两个共识算法的实现：clique 和 ethash。而 ethash 是目前以太坊主网（Homestead版本）的 POW 共识算法。

ethash 模块位于以太坊项目目录下的 consensus/ethash 目录下。

• algorithm.go 实现了 Dagger-Hashimoto 算法的所有功能，比如生成 cache 和 dataset、根据 Header 和 Nonce 计算挖矿哈希等。
• api.go 实现了供 RPC 使用的 api 方法。
• consensus.go 实现了以太坊共识接口的部分方法，包括 Verify 系列方法（VerifyHeader、VerifySeal等）、Prepare 和 Finalize、CalcDifficulty、Author、SealHash。
• ethash.go 实现了cache 结构体和 dataset 结构体及它们各自的方法、MakeCache/MakeDataset 函数、Ethash 对象的 New 函数，和 Ethash 的内部方法。
• sealer.go 实现了共识接口的 Seal 方法，和Ethash的内部方法 mine。这些方法实现了 ethash 的挖矿功能。

1. Ethash 设计原理

1.1 Ethash 设计目标

以太坊设计共识算法时，期望达到三个目的：

1. 抗ASIC性：为算法创建专用硬件的优势应尽可能小，让普通计算机用户也能使用CPU进行开采。
   • 通过内存限制来抵制（ASIC使用矿机内存昂贵）
   • 大量随机读取内存数据时计算速度就不仅仅受限于计算单元，更受限于内存的读出速度。
2. 轻客户端可验证性: 一个区块应能被轻客户端快速有效校验。
3. 矿工应该要求存储完整的区块链状态。

1.2 Dataset 数据集

ethash 要计算哈希，需要先有一块数据集 dataset。这块数据集较大，初始大小大约有1G，每隔 3 万个区块就会更新一次，且每次更新都会比之前变大8M左右。计算哈希的数据源就是从这块数据集中来的；而决定使用数据集中的哪些数据进行哈希计算的，才是 header 的数据和 Nonce 字段。这部分是由 Dagger 算法实现的。

1.3 Dagger 算法

Dagger 算法是用来生成数据集 Dataset 的，核心的部分就是 Dataset 的生成方式和组织结构。

可以把 Dataset 想成多个 item（dataItem）组成的数组，每个 item 是64字节的 byte 数组（一条哈希）。dataset 的初始大小约为1G，每隔3万个区块（一个epoch区间）就会更新一次，且每次更新都会比之前变大8M左右。

Dataset 的每个 item 是由一个缓存块（cache）生成的，缓存块也可以看做多个 item（cacheItem）组成，缓存块占用的内存要比 dataset 小得多，它的初始大小约为16M。同 dataset 类似，每隔 3 万个区块就会更新一次，且每次更新都会比之前变大128K左右。

生成一条 dataItem 的程是：从缓存块中“随机”（这里的“随机”不是真的随机数，而是指事前不能确定，但每次计算得到的都是一样的值）选择一个 cacheItem 进行计算，得的结果参与下次计算，这个过程会循环 256 次。

缓存块是由 seed 生成的，而 seed 的值与块的高度有关。所以生成 dataset 的过程如下图所示：

Dagger 还有一个关键的地方，就是确定性。即同一个 epoch 内，每次计算出来的 seed、cache、dataset 都是相同的。否则对于同一个区块，挖矿的人和验证的人使用不同的 dataset，就没法进行验证了。

1.4 Hashimoto 算法

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

它的作用就是使用区块 Header 的哈希和 Nonce 字段、利用 dataset 数据，生成一个最终的哈希值。

2. 源码解析

2.1 生成数据集 dataset

generate 函数位于 ethash.go 文件中，主要是为了生成 dataset，其中包扩以下内容：

• 生成 cache size
• 生成 dataset size
• 生成 seed 种子
• 生成 cache
• 生成 dataset
• 共识引擎核心函数

2.2 生成 cache size

cache size 主要某个特定块编号的ethash验证缓存的大小 ， epochLength 为 30000，如果 epoch 小于 2048，则从已知的 epoch 返回相应的 cache size，否则重新计算 epoch。

cache的大小是线性增长的，size的值等于(2²⁴ + 2¹⁷ * epoch - 64)，用这个值除以 64 看结果是否是一个质数，如果不是，减去 128 再重新计算，直到找到最大的质数为止。

csize := cacheSize(d.epoch*epochLength + 1)

func cacheSize(block uint64) uint64 {
    epoch := int(block / epochLength)
    if epoch < maxEpoch {
        return cacheSizes[epoch]
    }
    return calcCacheSize(epoch)
}

func calcCacheSize(epoch int) uint64 {
    size := cacheInitBytes + cacheGrowthBytes*uint64(epoch) - hashBytes
    for !new(big.Int).SetUint64(size / hashBytes).ProbablyPrime(1) { // Always accurate for n < 2^64
        size -= 2 * hashBytes
    }
    return size
}

2.3 生成 dataset size

dataset Size 主要某个特定块编号的 ethash 验证缓存的大小 , 类似上面生成 cache size。

dsize := datasetSize(d.epoch*epochLength + 1)

func datasetSize(block uint64) uint64 {
epoch := int(block / epochLength)
    if epoch < maxEpoch {
        return datasetSizes[epoch]
    }
    return calcDatasetSize(epoch)
}

2.4 生成 seed 种子

seedHash 是用于生成验证缓存和挖掘数据集的种子。长度为 32。

seed := seedHash(d.epoch*epochLength + 1)

func seedHash(block uint64) []byte {
    seed := make([]byte, 32)
    if block < epochLength {
        return seed
    }
    keccak256 := makeHasher(sha3.NewLegacyKeccak256())
    for i := 0; i < int(block/epochLength); i++ {
        keccak256(seed, seed)
    }
    return seed
}

2.5 生成 cache

generateCache(cache, d.epoch, seed)

接下来分析generateCache的关键代码：

先了解一下hashBytes，在下面的计算中都是以此为单位，它的值为 64 ，相当于一个 keccak512 哈希的长度,下文以 item 称呼 [hashBytes]byte。

①：初始化 cache

此循环用来初始化cache：先将seed的哈希填入cache的第一个item,随后使用前一个item的哈希，填充后一个item。

for offset := uint64(hashBytes); offset < size; offset += hashBytes {
    keccak512(cache[offset:], cache[offset-hashBytes:offset])
    atomic.AddUint32(&progress, 1)
}

②：对 cache 中数据按规则做异或

为对于每一个item（srcOff），“随机”选一个item（xorOff）与其进行异或运算；将运算结果的哈希写入dstOff中。这个运算逻辑将进行cacheRounds次。

两个需要注意的地方：

• 一是 srcOff 是从尾部向头部变化的，而 dstOff 是从头部向尾部变化的。并且它俩是对应的，即当 srcOff 代表倒数第 x 个 item 时，dstOff 则代表正数第 x 个 item。
• 二是 xorOff 的选取。注意我们刚才的“随机”是打了引号的。xorOff 的值看似随机，因为在给出 seed 之前，你无法知道 xorOff 的值是多少；但一旦 seed 的值确定了，那么每一次 xorOff 的值都是确定的。而 seed 的值是由区块的高度决定的。这也是同一个 epoch 内总是能得到相同 cache 数据的原因。

for i := 0; i < cacheRounds; i++ {
    for j := 0; j < rows; j++ {
        var (
            srcOff = ((j - 1 + rows) % rows) * hashBytes
            dstOff = j * hashBytes
            xorOff = (binary.LittleEndian.Uint32(cache[dstOff:]) % uint32(rows)) * hashBytes
        )
        bitutil.XORBytes(temp, cache[srcOff:srcOff+hashBytes], cache[xorOff:xorOff+hashBytes])
        keccak512(cache[dstOff:], temp)

        atomic.AddUint32(&progress, 1)
    }
}

2.6 生成 dataset

dataset 大小的计算和 cache 类似，量级不同：2³⁰ + 2²³ * epoch - 128，然后每次减256寻找最大质数。

生成数据是一个循环，每次生成64个字节，主要的函数是 generateDatasetItem：

generateDatasetItem 的数据来源就是 cache 数据，而最终的 dataset 值会存储在 mix 变量中。整个过程也是由多个循环构成。

①：初始化 mix 变量

根据 cache 值对 mix 变量进行初始化。其中 hashWords 代表的是一个 hash 里有多少个 word 值：一个 hash 的长度为 hashBytes 即 64 字节，一个 word（uint32类型）的长度为 4 字节，因此 hashWords 值为 16。选取 cache 中的哪一项数据是由参数 index 和 i 变量决定的。

mix := make([]byte, hashBytes)
binary.LittleEndian.PutUint32(mix, cache[(index%rows)*hashWords]^index)
for i := 1; i < hashWords; i++ {
    binary.LittleEndian.PutUint32(mix[i*4:], cache[(index%rows)*hashWords+uint32(i)])
}
keccak512(mix, mix)

②：将 mix 转换成 []uint32 类型

intMix := make([]uint32, hashWords)
for i := 0; i < len(intMix); i++ {
    intMix[i] = binary.LittleEndian.Uint32(mix[i*4:])
}

③：将 cache 数据聚合进 intmix

for i := uint32(0); i < datasetParents; i++ {
    parent := fnv(index^i, intMix[i%16]) % rows
    fnvHash(intMix, cache[parent*hashWords:])
}

FNV 哈希算法，是一种不需要使用密钥的哈希算法。

这个算法很简单：a乘以 FNV 质数0x01000193，然后再和b异或。

首先用这个算法算出一个索引值，利用这个索引从 cache 中选出一个值（data），然后对 mix 中的每个字节都计算一次 FNV，得到最终的哈希值。

func fnv(a, b uint32) uint32 {
    return a*0x01000193 ^ b
}
func fnvHash(mix []uint32, data []uint32) {
    for i := 0; i < len(mix); i++ {
        mix[i] = mix[i]*0x01000193 ^ data[i]
    }
}

④：将 intMix 恢复成 mix，并计算 mix 的哈希返回

for i, val := range intMix {
    binary.LittleEndian.PutUint32(mix[i*4:], val)
}
keccak512(mix, mix)
return mix

generateCache 和 generateDataset 是实现 Dagger 算法的核心函数，到此整个生成哈希数据集的的过程结束。

3. 共识引擎核心函数

代码位于 consensus.go。

①：Author

// 返回coinbase, coinbase是打包第一笔交易的矿工的地址
func (ethash *Ethash) Author(header *types.Header) (common.Address, error) {
    return header.Coinbase, nil
}

②：VerifyHeader

主要有两步检查，第一步检查header是否已知或者是未知的祖先，第二步是ethash的检查：

2.1 header.Extra 不能超过32字节

if uint64(len(header.Extra)) > params.MaximumExtraDataSize {  // 不超过32字节
    return fmt.Errorf("extra-data too long: %d > %d", len(header.Extra), params.MaximumExtraDataSize)
}

2.2 时间戳不能超过15秒，15秒以后的就被认定为未来的块

if !uncle {
    if header.Time > uint64(time.Now().Add(allowedFutureBlockTime).Unix()) {
        return consensus.ErrFutureBlock
    }
}

2.3 当前header的时间戳小于父块的

if header.Time <= parent.Time { 
// 当前header的时间小于等于父块的
    return errZeroBlockTime
}

2.4 根据时间戳和父块的难度来验证块的难度

expected := ethash.CalcDifficulty(chain, header.Time, parent)
if expected.Cmp(header.Difficulty) != 0 {
    return fmt.Errorf("invalid difficulty: have %v, want %v", header.Difficulty, expected)
}

2.5 验证gas limit小于2⁶³ -1

cap := uint64(0x7fffffffffffffff)
if header.GasLimit > cap {
    return fmt.Errorf("invalid gasLimit: have %v, max %v", header.GasLimit, cap)
}

2.6 确认gasUsed为<= gasLimit

if header.GasUsed > header.GasLimit {
    return fmt.Errorf("invalid gasUsed: have %d, gasLimit %d", header.GasUsed, header.GasLimit)
}

2.7 验证块号是父块加1

if diff := new(big.Int).Sub(header.Number, parent.Number); diff.Cmp(big.NewInt(1)) != 0 {
    return consensus.ErrInvalidNumber
}

2.8 检查给定的块是否满足pow难度要求

if seal {
    if err := ethash.VerifySeal(chain, header); err != nil {
        return err
    }
}

③：VerifyUncles

3.1 叔叔块最多两个

if len(block.Uncles()) > maxUncles {
    return errTooManyUncles
}

3.2 收集叔叔块和祖先块

number, parent := block.NumberU64()-1, block.ParentHash()
for i := 0; i < 7; i++ {
    ancestor := chain.GetBlock(parent, number)
    if ancestor == nil {
        break
    }
    ancestors[ancestor.Hash()] = ancestor.Header()
    for _, uncle := range ancestor.Uncles() {
        uncles.Add(uncle.Hash())
    }
    parent, number = ancestor.ParentHash(), number-1
}
ancestors[block.Hash()] = block.Header()
uncles.Add(block.Hash())

3.3 确保叔块只被奖励一次且叔块有个有效的祖先

for _, uncle := range block.Uncles() {
    // Make sure every uncle is rewarded only once
    hash := uncle.Hash()
    if uncles.Contains(hash) {
        return errDuplicateUncle
    }
    uncles.Add(hash)

    // Make sure the uncle has a valid ancestry
    if ancestors[hash] != nil {
        return errUncleIsAncestor
    }
    if ancestors[uncle.ParentHash] == nil || uncle.ParentHash == block.ParentHash() {
        return errDanglingUncle
    }
    if err := ethash.verifyHeader(chain, uncle, ancestors[uncle.ParentHash], true, true); err != nil {
        return err
    }
}

④：Prepare

初始化header的Difficulty字段

parent := chain.GetHeader(header.ParentHash, header.Number.Uint64()-1)
if parent == nil {
    return consensus.ErrUnknownAncestor
}
header.Difficulty = ethash.CalcDifficulty(chain, header.Time, parent)
return nil

⑤：Finalize会执行交易后的所有状态修改（例如，区块奖励），但不会组装该区块。

5.1 累积任何块和叔块的奖励

accumulateRewards(chain.Config(), state, header, uncles)

5.2 计算状态树的根哈希并提交到header

header.Root = state.IntermediateRoot(chain.Config().IsEIP158(header.Number))

⑥：FinalizeAndAssemble 运行任何交易后状态修改（例如，块奖励），并组装最终块。

func (ethash *Ethash) FinalizeAndAssemble(chain consensus.ChainReader, header *types.Header, state *state.StateDB, txs []*types.Transaction, uncles []*types.Header, receipts []*types.Receipt) (*types.Block, error) {
    accumulateRewards(chain.Config(), state, header, uncles)
    header.Root = state.IntermediateRoot(chain.Config().IsEIP158(header.Number))
    return types.NewBlock(header, txs, uncles, receipts), nil
}

很明显就是比 Finalize 多了 types.NewBlock。

⑦：SealHash 返回在 seal 之前块的哈希（会跟 seal 之后的块哈希不同）

func (ethash *Ethash) SealHash(header *types.Header) (hash common.Hash) {
    hasher := sha3.NewLegacyKeccak256()

    rlp.Encode(hasher, []interface{}{
        header.ParentHash,
        header.UncleHash,
        header.Coinbase,
        header.Root,
        header.TxHash,
        header.ReceiptHash,
        header.Bloom,
        header.Difficulty,
        header.Number,
        header.GasLimit,
        header.GasUsed,
        header.Time,
        header.Extra,
    })
    hasher.Sum(hash[:0])
    return hash
}

⑧：Seal 给定的输入块生成一个新的密封请求（挖矿），并将结果推送到给定的通道中。

注意，该方法将立即返回并将异步发送结果。 根据共识算法，可能还会返回多个结果。这部分会在下面的挖矿中具体分析，这里跳过。

4. 挖矿细节

挖矿的核心接口定义：

Seal(chain ChainReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error

进入到seal函数：

①：如果运行错误的POW，直接返回空的nonce和MixDigest，同时块也是空块

if ethash.config.PowMode == ModeFake || ethash.config.PowMode == ModeFullFake {
    header := block.Header()
    header.Nonce, header.MixDigest = types.BlockNonce{}, common.Hash{}
    select {
    case results <- block.WithSeal(header):
    default:
        ethash.config.Log.Warn("Sealing result is not read by miner", "mode", "fake", "sealhash", ethash.SealHash(block.Header()))
    }
    return nil
}

②：共享pow的话，则转到它的共享对象执行Seal操作

if ethash.shared != nil {
    return ethash.shared.Seal(chain, block, results, stop)
}

③：获取种子源，并根据其生成ethash需要的种子

if ethash.rand == nil {
    // 获得种子
    seed, err := crand.Int(crand.Reader, big.NewInt(math.MaxInt64))
    if err != nil {
        ethash.lock.Unlock()
        return err
    }
    ethash.rand = rand.New(rand.NewSource(seed.Int64())) // 给rand赋值
}

④：挖矿的核心工作交给mine

for i := 0; i < threads; i++ {
    pend.Add(1)
    go func(id int, nonce uint64) {
        defer pend.Done()
        ethash.mine(block, id, nonce, abort, locals) // 真正执行挖矿的动作
    }(i, uint64(ethash.rand.Int63()))
}

⑤：处理挖矿的结果

• 外部意外中止，停止所有挖矿线程
• 其中一个线程挖到正确块，中止其他所有线程
• ethash对象发生改变，停止当前所有操作，重启当前方法

go func() {
    var result *types.Block
    select {
    case <-stop:
        close(abort)
    case result = <-locals:
        select {
        case results <- result: //其中一个线程挖到正确块，中止其他所有线程
        default:
            ethash.config.Log.Warn("Sealing result is not read by miner", "mode", "local", "sealhash", ethash.SealHash(block.Header()))
        }
        close(abort)
    case <-ethash.update:
        close(abort)
        if err := ethash.Seal(chain, block, results, stop); err != nil {
            ethash.config.Log.Error("Failed to restart sealing after update", "err", err)
        }
    }

由上可以知道 seal 的核心工作是由 mine 函数完成的，重点介绍一下。

mine 函数其实也比较简单，它是真正的 pow 矿工，用来搜索一个 nonce 值，nonce 值开始于 seed 值，seed 值是能最终产生正确的可匹配可验证的区块难度。

①：从区块头中提取相关数据，放在全局变量域中

var (
    header  = block.Header()
    hash    = ethash.SealHash(header).Bytes()
    target  = new(big.Int).Div(two256, header.Difficulty) // 这是用来验证的target
    number  = header.Number.Uint64()
    dataset = ethash.dataset(number, false)
)

②：开始产生随机 nonce，直到我们中止或找到一个好的 nonce

var (
    attempts = int64(0)
    nonce    = seed
)

③： 聚集完整的 dataset 数据，为特定的 header 和 nonce 产生最终哈希值

func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    //定义一个lookup函数，用于在数据集中查找数据
    lookup := func(index uint32) []uint32 {
        offset := index * hashWords //hashWords是上面定义的常量值= 16
        return dataset[offset : offset+hashWords]
    }
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}

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

接下来重点分析 hashimoto 函数：

3.1 根据 seed 获取区块头

rows := uint32(size / mixBytes) ①
seed := make([]byte, 40) ②
copy(seed, hash) ③
binary.LittleEndian.PutUint64(seed[32:], nonce)④
seed = crypto.Keccak512(seed)⑤
seedHead := binary.LittleEndian.Uint32(seed)⑥

• 计算数据集的行数
• 合并header+nonce到一个 40 字节的seed
• 将区块头的hash拷贝到seed中
• 将nonce值填入seed的后（40-32=8）字节中去，（nonce本身就是uint64类型，是 64 位，对应 8 字节大小），正好把hash和nonce完整的填满了 40 字节的 seed
• Keccak512加密seed
• 从seed中获取区块头

3.2 从复制的种子开始混合

• mixBytes常量= 128，mix的长度为 32，元素为uint32，是 32位，对应为 4 字节大小。所以mix总共大小为 4*32=128 字节大小

mix := make([]uint32, mixBytes/4)
for i := 0; i < len(mix); i++ {
    mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])
}

3.3 混合随机数据集节点

//与mix结构相同，长度相同
temp := make([]uint32, len(mix))
for i := 0; i < loopAccesses; i++ {
    parent := fnv(uint32(i)^seedHead, mix[i%len(mix)]) % rows
    for j := uint32(0); j < mixBytes/hashBytes; j++ {
        copy(temp[j*hashWords:], lookup(2*parent+j))
    }
    fnvHash(mix, temp)
}

3.4 压缩混合

for i := 0; i < len(mix); i += 4 {
    mix[i/4] = fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])
}
mix = mix[:len(mix)/4]

digest := make([]byte, common.HashLength)
for i, val := range mix {
    binary.LittleEndian.PutUint32(digest[i*4:], val)
}
return digest, crypto.Keccak256(append(seed, digest...))

最终返回的是digest和digest与seed的哈希；而digest其实就是mix的[]byte形式。在前面Ethash.mine的代码中我们已经看到使用第二个返回值与target变量进行比较，以确定这是否是一个有效的哈希值。

5. 验证 pow

挖矿信息的验证有两部分：

•  验证Header.Difficulty是否正确
•  验证Header.MixDigest和Header.Nonce是否正确

①：验证 Header.Difficulty 的代码主要在 Ethash.verifyHeader 中

func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *types.Header, uncle bool, seal bool) error {
  ......
  expected := ethash.CalcDifficulty(chain, header.Time.Uint64(), parent)

  if expected.Cmp(header.Difficulty) != 0 {
    return fmt.Errorf("invalid difficulty: have %v, want %v", header.Difficulty, expected)
  }
}

通过区块高度和时间差作为参数来计算Difficulty值，然后与待验证的区块的Header.Difficulty字段进行比较，如果相等则认为是正确的。

②：MixDigest 和 Nonce 的验证主要是在 Header.verifySeal 中

验证的方式:使用Header.Nonce和头部哈希通过hashimoto重新计算一遍MixDigest和result哈希值,并且验证的节点是不需要dataset数据的。