以太坊源码分析之共识算法ethash

区块链是作为分布式系统构建的，由于不依赖于中央权威，分散的节点需要就交易是否有效达成一致，而达成一致的机制就是共识算法。

以太坊目前的算法是一种类 POW 算法：ethash。 除了像比特币一样需要消耗计算机资源进行计算外，还考虑了对专用矿机的抵抗力，增加了挖矿的公平性。

通用 POW 算法思路

POW即Proof of Work，就是通过工作的结果证明你已经完成了相应的工作。

其初衷是人人可参与以太坊公认共识端，门槛低（容易验证），但出结果难（计算复杂）。 在这一点上，只匹配部分特征的哈希算法（不可逆）就非常适合。

哈希值是通过不断改变随机数得到的，比较是否小于给定的值（难度），匹配的就是合适的结果。

随机数一般来自区块头结构中的nonce域。

因为出块时间是一定的，但是整体算力是不确定的，所以难度一般是根据时间来调整的。

ethash算法的思想

Ethash 类似于 pow。 数据来源不仅像比特币一样来自header structure和nonce，还有自己的一套数据集。

简化后的核心代码如下：

func (ethash *Ethash) mine(block *types.Block, id int, seed uint64, abort chan struct{}, found chan *types.Block) {
    var (
        header  = block.Header()
        hash    = ethash.SealHash(header).Bytes()
        target  = new(big.Int).Div(two256, header.Difficulty)
        number  = header.Number.Uint64()
        dataset = ethash.dataset(number, false)
    )
    var (
        attempts = int64(0)
        nonce    = seed
    )
    for {
            attempts++
            digest, result := hashimotoFull(dataset.dataset, hash, nonce)
            if new(big.Int).SetBytes(result).Cmp(target) <= 0 {
                // Correct nonce found, create a new header with it
                header = types.CopyHeader(header)
                header.Nonce = types.EncodeNonce(nonce)
                header.MixDigest = common.BytesToHash(digest)
                ...
            }
            ...
      }
      ...
}

    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()))
    }

miner方法中，hashimotoFull返回result，result seed-->cache-->dataset，生成一致的结果。

图片.png

从这个图中可以看出，无论是挖矿节点还是验证节点（全规模验证），生成数据集调用的方法是一样的，参数个数块高是一样的，所以数据集也是一样（参数async在这里不影响以太坊公认共识端，如果为true，数据集会在后台生成）。

桥本

Hashimoto 聚合数据集、块头哈希和随机数以生成最终值。

图片来自简书App

如图所示：

桥本全功能

func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    lookup := func(index uint32) []uint32 {
        offset := index * hashWords
        return dataset[offset : offset+hashWords]
    }
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}

hashtoLight 函数

func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    keccak512 := makeHasher(sha3.NewLegacyKeccak512())
    lookup := func(index uint32) []uint32 {
        rawData := generateDatasetItem(cache, index, keccak512)
        data := make([]uint32, len(rawData)/4)
        for i := 0; i < len(data); i++ {
            data[i] = binary.LittleEndian.Uint32(rawData[i*4:])
        }
        return data
    }
    return hashimoto(hash, nonce, size, lookup)
}

桥本函数：多次聚合header hash、nonce、dataset，得到最终的取值结果

func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
    // Calculate the number of theoretical rows (we use one buffer nonetheless)
    rows := uint32(size / mixBytes)
    // Combine header+nonce into a 64 byte seed
    seed := make([]byte, 40)
    copy(seed, hash)
    binary.LittleEndian.PutUint64(seed[32:], nonce)
    seed = crypto.Keccak512(seed)
    seedHead := binary.LittleEndian.Uint32(seed)
    // Start the mix with replicated seed
    mix := make([]uint32, mixBytes/4)
    for i := 0; i < len(mix); i++ {
        mix[i] = binary.LittleEndian.Uint32(seed[i*4:])
    }
    // Mix in random dataset nodes
    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)
    }
    // Compress mix
    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...))
}

consensus\ethash\algorithm.go中的generateCache、generateDataset、generateDatasetItem、hashimoto函数，这里只提供一个大概的思路，不去深究，因为涉及到一些密码算法，我自己看不懂代码。 另外，这部分细节对整体理解ethash算法影响不大。 以后还是分析密码算法比较好。

困难

func CalcDifficulty(config *params.ChainConfig, time uint64, parent *types.Header) *big.Int {
    next := new(big.Int).Add(parent.Number, big1)
    switch {
    case config.IsConstantinople(next):
        return calcDifficultyConstantinople(time, parent)
    case config.IsByzantium(next):
        return calcDifficultyByzantium(time, parent)
    case config.IsHomestead(next):
        return calcDifficultyHomestead(time, parent)
    default:
        return calcDifficultyFrontier(time, parent)
    }
}

以太坊的难度分多个阶段调整，根据区块高度的阶段使用该阶段的计算公式。 由于目前处于君士坦丁堡阶段，因此仅描述代码。

计算君士坦丁堡难度的函数是makeDifficultyCalculator。 由于评论里已经有对应的公式，代码就不贴了。 梳理如下：

step = parent_diff // 2048

direction = max((2 if len(parent.uncles) else 1) - ((timestamp - parent.timestamp) // 9), -99)

periodCount = (block.number - (5000000-1)) if (block.number >= (5000000-1)) else 0

diff = parent_diff + step *direction+ 2^(periodCount - 2)

diffculty计算分为两部分： 1.动态线性调整：parent_diff + step *direction

这部分难度值是在父块的基础上微调的。 调整单位为step，根据当前块与父块的时间间隔，是否有叔块得到一个单位调整范围方向。 step *direction 为调整值。

也就是说，时间间隔太小，方向为正，难度会增加一点，间隔太小，难度会降低一点。 为了防止一直产生叔块，会延长时间，增加难度。 如果出现意外情况或程序出现漏洞，难度大大降低，并有最低门槛（-99）。

值得注意的是，parent_diff + step *direction 除了方向有最小阈值外，还有一个最小难度。

        // minimum difficulty can ever be (before exponential factor)
        if x.Cmp(params.MinimumDifficulty) < 0 {
            x.Set(params.MinimumDifficulty)
        }

MinimumDifficulty      = big.NewInt(131072) // The minimum that the difficulty may ever be.

2. 指数增长：2^(periodCount - 2)

指数增长部分在以太坊中被称为难度炸弹（也称为冰河时代）。 由于以太坊的共识算法会从pow过渡到pos，设计难度炸弹会使挖矿难度越来越大，以至于无法出块。 这样矿工就有了期待，和平过渡到pos。

目前在君士坦丁堡阶段，periodCount减去数字5,000,000是为了防止指数部分增长过快，即延迟难度炸弹生效。

关于header.difficulty的具体难度分析，这篇文章分析的很好。

试验结果

我本地私链当前区块高度为2278，配置的君士坦丁堡起始高度为5，即进入君士坦丁堡阶段。

刚开始程序挖矿的时候，因为没有其他节点挖矿，最后一个出块时间和当前出块时间的间隔相差很大，方向设置为-99。 但是区块高度不超过5000000，索引部分结果为0，父难度为689054，最终难度为655790。

图片.png

一段时间后，方向基本徘徊在-1、0、1之间，平均挖矿间隔只有十几秒。

图片.png

INFO [06-09|17:49:46.059] luopeng2                                 block_timestamp - parent_timestamp=25
INFO [06-09|17:49:53.529] luopeng2                                 block_timestamp - parent_timestamp=7
INFO [06-09|17:51:19.667] luopeng2                                 block_timestamp - parent_timestamp=18
INFO [06-09|17:51:23.387] luopeng2                                 block_timestamp - parent_timestamp=4
INFO [06-09|18:46:02.608] luopeng2                                 block_timestamp - parent_timestamp=31
INFO [06-09|18:46:18.575] luopeng2                                 block_timestamp - parent_timestamp=1

目前以太坊网络状态正常，算力稳定，ethgasstation

网站上查到的时间间隔和我当地的情况差不多

图片.png

总结

综上所述，ethash的基本思想类似于比特币的pow，就是比较随机nonce得到的值和难度。 如果条件满足则挖矿成功，否则继续尝试。 与比特币竞争CPU算力不同，ethash通过生成庞大的数据集和限制内存来增强去中心化，防止ASIC矿机强势算力的垄断。

参考