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

作者: 逆风_罗鹏 | 来源:发表于2019-06-09 19:04 被阅读0次

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

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

一般的POW算法思路

POW即工作量证明，也就是通过工作结果来证明你完成了相应的工作。
它的初衷希望所有人可参与，门槛低（验证容易），但是得到结果难（计算复杂）。在这一点上，只匹配部分特征的hash算法（不可逆）非常符合要求。

通过不断地更换随机数来得到哈希值，比较是否小于给定值（难度），符合的即为合适的结果。
随机数一般来自区块header结构里的nonce字段。
因为出块时间是一定的，但总体算力是不确定的，所以难度一般会根据时间来调整。

ethash算法的思路

ethash与pow类似，数据来源除了像比特币一样来自header结构和nonce，还有自己定的一套数据集dataset。
精简后的核心代码如下：

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 <= target，则计算到合适的nonce了（挖到矿了，矿工的努力终于没有白费哈哈）。而target则是2^256/难度，result的来源则是随机数nonce,区块头的hash值以及数据集dataset（另外，另一个返回值摘要digest存储在区块头，用来和验证得到的digest进行核对）。

说完了整体，下面将重点对dataset和header.Difficulty进行具体分析。

该dataset是ethash的主要部分，主要是为了抵抗ASIC矿机的。因为生成的dataset很大（初始就有1G），所以该算法的性能瓶颈不在于cpu运算速度，而在于内存读取速度。大内存是昂贵的，并且普通计算机现有内存也足够跑了，通过内存来限制，去除专用硬件的运算优势。

ethash是Dagger-Hashimoto算法的变种，由于ethash对原来算法的特征改变很大，所以不介绍算法的原理了。只结合现有的ethash源码，对生成dataset和使用dataset，分成Dagger和Hashimoto两部分讨论。

Dagger

Dagger是用来生成dataset的。

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

如图所示：

对于每一个区块，都能通过扫描区块头的方式计算出一个种子（ seed ），该种子只与当前区块有关。
使用种子能产生一个16MB 的伪随机缓存(cache)，轻客户端会存储缓存。
基于缓存再生成一个1GB的数据集(dataset)，数据集中的每一个元素都只依赖于缓存中的某几个元素，也就是说，只要有缓存，就可以快速地计算出数据集中指定位置的元素。挖矿者存储数据集，数据集随时间线性增长。

在代码中生成cache的部分

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

如图所示：

数字标记代表调用入口，其中3、4代表MakeCache和MakeDataset，是geth提供的命令，用于生成cache和dataset(生成dataset要先生成cache)。
重点是数字1和2代表的挖矿（ethash.mine）和验证(ethash.verifySeal)。mine走的是生成dataset的方式，后面再介绍。verifySeal如果是全量级验证则和mine一样。如果是轻量级验证，则不会生成完整的dataset，而是生成cache，最终的调用交给算法模块里的generateCache完成。

verifySeal 全量级验证部分

    if fulldag {
        dataset := ethash.dataset(number, true)
        if dataset.generated() {
            digest, result = hashimotoFull(dataset.dataset, ethash.SealHash(header).Bytes(), header.Nonce.Uint64())

            // Datasets are unmapped in a finalizer. Ensure that the dataset stays alive
            // until after the call to hashimotoFull so it's not unmapped while being used.
            runtime.KeepAlive(dataset)
        } else {
            // Dataset not yet generated, don't hang, use a cache instead
            fulldag = false
        }
    }

verifySeal 轻量级验证部分

    if !fulldag {
        cache := ethash.cache(number)

        size := datasetSize(number)
        if ethash.config.PowMode == ModeTest {
            size = 32 * 1024
        }
        digest, result = hashimotoLight(size, cache.cache, ethash.SealHash(header).Bytes(), header.Nonce.Uint64())

        // Caches are unmapped in a finalizer. Ensure that the cache stays alive
        // until after the call to hashimotoLight so it's not unmapped while being used.
        runtime.KeepAlive(cache)
    }

generateCache生成cache:大致思路是在给定种子数组seed[]的情况下，对固定容量的一块buffer(即cache)进行一系列操作，使得buffer的数值分布变得随机、无规律可循。

func generateCache(dest []uint32, epoch uint64, seed []byte) {
    log.Info("luopeng2 generateCache")
    // Print some debug logs to allow analysis on low end devices
    logger := log.New("epoch", epoch)

    start := time.Now()
    defer func() {
        elapsed := time.Since(start)

        logFn := logger.Debug
        if elapsed > 3*time.Second {
            logFn = logger.Info
        }
        logFn("Generated ethash verification cache", "elapsed", common.PrettyDuration(elapsed))
    }()
    // Convert our destination slice to a byte buffer
    header := *(*reflect.SliceHeader)(unsafe.Pointer(&dest))
    header.Len *= 4
    header.Cap *= 4
    cache := *(*[]byte)(unsafe.Pointer(&header))

    // Calculate the number of theoretical rows (we'll store in one buffer nonetheless)
    size := uint64(len(cache))
    rows := int(size) / hashBytes

    // Start a monitoring goroutine to report progress on low end devices
    var progress uint32

    done := make(chan struct{})
    defer close(done)

    go func() {
        for {
            select {
            case <-done:
                return
            case <-time.After(3 * time.Second):
                logger.Info("Generating ethash verification cache", "percentage", atomic.LoadUint32(&progress)*100/uint32(rows)/4, "elapsed", common.PrettyDuration(time.Since(start)))
            }
        }
    }()
    // Create a hasher to reuse between invocations
    keccak512 := makeHasher(sha3.NewLegacyKeccak512())

    // Sequentially produce the initial dataset
    keccak512(cache, seed)
    for offset := uint64(hashBytes); offset < size; offset += hashBytes {
        keccak512(cache[offset:], cache[offset-hashBytes:offset])
        atomic.AddUint32(&progress, 1)
    }
    // Use a low-round version of randmemohash
    temp := make([]byte, hashBytes)

    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)
        }
    }
    // Swap the byte order on big endian systems and return
    if !isLittleEndian() {
        swap(cache)
    }
}

在代码中生成dataset的部分

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

如图所示：

调用入口与上图类似。
mine生成dataset，经过一系列的调用到算法模块里的generateDataset，由它负责生成整个数据集，而Dataset细分成DatasetItem，具体的item则交给generateDatasetItem完成。verifySeal如果是全量级验证也一样。
verifySeal如果是轻量级则比较特殊，它用到的时候才生成指定的数据集。它会在算法模块里的hashimotoLight(后面再介绍）里用之前生成的cache调用generateDataItem生成指定的DatasetItem参与计算。

mine中得到dataset的代码

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

generateDataset函数生成整个dataset:大致思路是将数据分成多段，使用多个goroutine调用generateDatasetItem生成所有的。

func generateDataset(dest []uint32, epoch uint64, cache []uint32) {
    // Print some debug logs to allow analysis on low end devices
    logger := log.New("epoch", epoch)

    start := time.Now()
    defer func() {
        elapsed := time.Since(start)

        logFn := logger.Debug
        if elapsed > 3*time.Second {
            logFn = logger.Info
        }
        logFn("Generated ethash verification cache", "elapsed", common.PrettyDuration(elapsed))
    }()

    // Figure out whether the bytes need to be swapped for the machine
    swapped := !isLittleEndian()

    // Convert our destination slice to a byte buffer
    header := *(*reflect.SliceHeader)(unsafe.Pointer(&dest))
    header.Len *= 4
    header.Cap *= 4
    dataset := *(*[]byte)(unsafe.Pointer(&header))

    // Generate the dataset on many goroutines since it takes a while
    threads := runtime.NumCPU()
    size := uint64(len(dataset))

    var pend sync.WaitGroup
    pend.Add(threads)

    var progress uint32
    for i := 0; i < threads; i++ {
        go func(id int) {
            defer pend.Done()

            // Create a hasher to reuse between invocations
            keccak512 := makeHasher(sha3.NewLegacyKeccak512())

            // Calculate the data segment this thread should generate
            batch := uint32((size + hashBytes*uint64(threads) - 1) / (hashBytes * uint64(threads)))
            first := uint32(id) * batch
            limit := first + batch
            if limit > uint32(size/hashBytes) {
                limit = uint32(size / hashBytes)
            }
            // Calculate the dataset segment
            percent := uint32(size / hashBytes / 100)
            for index := first; index < limit; index++ {
                item := generateDatasetItem(cache, index, keccak512)
                if swapped {
                    swap(item)
                }
                copy(dataset[index*hashBytes:], item)

                if status := atomic.AddUint32(&progress, 1); status%percent == 0 {
                    logger.Info("Generating DAG in progress", "percentage", uint64(status*100)/(size/hashBytes), "elapsed", common.PrettyDuration(time.Since(start)))
                }
            }
        }(i)
    }
    // Wait for all the generators to finish and return
    pend.Wait()
}

generateDataItem函数得到指定的dataset：大致思路是计算出cache数据的索引，通过fnv聚合算法将cache数据混入，最后得到dataItem。

func generateDatasetItem(cache []uint32, index uint32, keccak512 hasher) []byte {
    //log.Info("luopeng1 generateDatasetItem")
    // Calculate the number of theoretical rows (we use one buffer nonetheless)
    rows := uint32(len(cache) / hashWords)

    // Initialize the mix
    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)

    // Convert the mix to uint32s to avoid constant bit shifting
    intMix := make([]uint32, hashWords)
    for i := 0; i < len(intMix); i++ {
        intMix[i] = binary.LittleEndian.Uint32(mix[i*4:])
    }
    // fnv it with a lot of random cache nodes based on index
    for i := uint32(0); i < datasetParents; i++ {
        parent := fnv(index^i, intMix[i%16]) % rows
        fnvHash(intMix, cache[parent*hashWords:])
    }
    // Flatten the uint32 mix into a binary one and return
    for i, val := range intMix {
        binary.LittleEndian.PutUint32(mix[i*4:], val)
    }
    keccak512(mix, mix)
    return mix
}

seed、cache和dataset的关系

前面或多或少说到了，不过为了脉络更清晰，着重梳理一下。
dataset是最终参与hashimoto的数据集，所以要得到dataset必须得到cache。所以不管是通过generateDataset函数得到dataset（全部的），还是generateDatasetItem函数datasetItem（指定部分），它都来源于cache，而cache则来源于seed。
但由于seed是来源于指定的block并且加工处理规则是固定的,所以其他节点依然可以根据block-->seed-->cache-->dataset，生成一致的结果。

image.png

从此图便可以看出，不管是挖矿的节点还是验证的节点（全量级验证），生成dataset调用的方法是相同的，参数number区块高度相同，那么dataset也相同（参数async在此处不影响，为true则会在后台生成dataset）。

Hashimoto

Hashimoto聚合数据集、区块头 hash和nonce生成最终值。

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

如图所示：

mine和走全量级的verifySeal会调到算法模块里的hashimotoFull，由于已经得到dataset了，它将从dataset里面取指定的dataset，最终调用hashimoto。
而轻量级验证的verifySeal会调到算法模块里的hashimotoLight,与full不同的是，它从参数cache里调用generateDatasetItem得到指定的dataset，最终调用hashimoto。

hashimotoFull函数

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

hashimoto函数：将header hash、nonce、dataset多次哈希聚合得到最终值result

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%16*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算法没有太大影响，日后研究密码学算法再分析这里好了。

Difficulty

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,根据现在的块与父块的时间间隔，以及是否存在叔块得到一个单位调整幅度direction。step *direction即为调整值。
也就是说如果时间间隔太小，direction为正，难度会增加一点，间隔太小，难度会减少一点。为了防止老是出叔块，会将时间拉长一点，难度增加。若出现意外情况或程序有漏洞导致难度大大降低，最低也有一个阀值（-99）。
值得注意的是，除了direction有最低阀值，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减去数字5000000，是为了防止指数部分增长过快，也就是延迟难度炸弹生效。

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

测试结果

我本地私有链当前区块高度是2278，配置的君士坦丁堡起始高度是5，即已进入君士坦丁堡阶段。
刚启动程序挖矿时，因为没有其他节点挖矿，所以上一区块时间与当前区块时间间隔相差很大，direction被设置成-99。而区块高度未超过5000000，指数部分的结果为0，父难度是689054，则最终难度是655790。

image.png

而一段时间后，direction基本上是在-1、0、1之间徘徊，挖矿的时间间隔平均也就十几秒。

image.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
网站上查到的时间间隔也与自己本地情况差不多

image.png

总结

综述，ethash基本思路和比特币的pow类似，都是不断随机nonce得到的值与难度进行比较，满足条件则挖矿成功，否则继续尝试。与比特币比拼cpu算力不同的是，ethash通过生成一个巨大的数据集，通过限制内存来防止具备强大算力的ASIC矿机垄断，增强了去中心化能力。

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

一般的POW算法思路

ethash算法的思路

Dagger

在代码中生成cache的部分

在代码中生成dataset的部分

seed、cache和dataset的关系

Hashimoto

Difficulty

diffculty计算分为两部分：

1. 动态线性调整：parent_diff + step *direction

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

测试结果

总结

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读