ETHASH 挖矿算法

把最好的东西留到最后品尝,本书将以太坊的PoW(Proof of work)挖矿算法核心ETHASH算法作为最好的礼物留到最后讲解。掌握了ETHASH算法我们就有能力进行新的、独立的公链开发。这个知识也是最难消化的,需要读者有许多相应的数学知识背景。请让我们一步一步来对照着源代码讲解这部分知识。

ETHASH和比特币PoW的异同

ETHASH这个算法是消耗资源的PoW模式,同比特币共识算法一样,它需要消耗大量的计算资源得出最终的“结论”。但是这个结论的得出和执行交易的顺序无关。也就是说一般情况下并非需要调整“交易的排列组合”来影响最终的哈希计算值结果符合“阈值”的标准。这点和比特币是完全不一样的。在交易序列唯一确定后,以太坊共识算法通过调整8字节(64bit)的nonce值来让计算最终结果符合“阈值”的要求。

ETHASH的算法更加依赖于CPU+内存的双料资源组合,比特币的SHA256算法仅仅依赖于CPU的资源,两者在挖矿公平性上也是不同的,这点在后文会有讲解。

ETHASH的设计目标

在比特币诞生之后经历了很长一段时间,开源社区发现仅依赖于CPU的计算的算法造成挖矿成功率向算力高的一方倾斜,并诞生出了诸如矿机这种专门的设备用于挖矿。矿机并不是一台完整的计算机,而是利用如ASIC集成电路、GPU、FPGA等专用电路进行并发操作。获得更高的多挖矿效率。这个趋势渐渐将普通人的电脑淘汰出挖矿的队伍,让话语权集中于数个矿场主手中。有违背于区块链公链“人人参与,去中心化”的精神,对区块链的分布式安全也是严重的威胁。在后世的算法设计中,就将装备了“慢CPU”的设备也能参与进挖矿定为一个重要的设计目标。PoW挖矿算法更多地让整台计算机资源都充分被利用,例如GPU、内存等设备,将单纯提高CPU的优势抹平。

ETHASH并非一日铸成,前身经历了两次演进/组合,前身称之为Dagger-Hashimoto算法。Dagger与Hashimoto是两个不同的算法,它们共同组合起来形成了一套“Memory Hard Function”也就是对内存要求较高的计算/验证算法。它的核心点就是要找到一个8字节(64bit)的nonce值。而这个随机数的产生,没有比枚举更好的策略,这样对于每个挖矿者而言,找到随机数的概率是公平的。而这个随机数的找到的概率,取决于预先设置的挖矿难度。难度越高,找到随机数的概率越小,则同样的挖矿者需要更长时间来搜寻。这让以太坊有通过设置挖矿难度动态调整出块时间的可能。我们现在习惯的15秒出一个以太坊的块,就是动态难度调整和世界千万挖矿者算力博弈的最终动态平衡。

ETHASH的挖矿运行总流程

ETHASH改良了Dagger-Hashimoto,正确的说已经脱胎换骨,和原来的算法已经面目全非。它的总算法分为DAG的生成和DAG的使用(挖矿)两个部分。它有效地解决了单纯内存依赖的算法诸如Scrypt算法加密难与解密同样难的困境,也突破Dagger算法不抵抗内存共享硬件加速的困境,从全区块链数据的生成改为固定的1GB的数据的生成,支持了客户端预生成数据,保障挖矿难度的平滑过度。

总的工作量/工作量证明总体流程如下。

  • 计算一个种子(Seed),该种子的计算依赖于当本块及本块之前的所有块。
  • 从种子中计算得出一个缓存(Cache),该缓存仅仅由种子得出,是一个16MB大小的数据集。轻客户端应存储下该缓存用于日后验证。
  • 从缓存中生成一个1GB大小的数据集(DataSet),这个数据集通常称为DAG。完整客户端或者挖矿客户端需要保存该1GB大小的数据,该数据随时间线性增长。
  • 挖矿过程即为哈希过程。哈希的输入是取得1GB数据集的数个子部分,并将它们放在一起执行哈希。验证过程是可以在轻客户端通过Cache缓存生成被挖矿制定的数据碎片并执行哈希验证。故而轻客户端并不需要时刻保存1GB的DAG。
  • 每当30000个以太坊区块被发掘后,1GB的数据集将被更新一次,所以矿工的主要精力放在读取这个数据集上,而非产生数据集。为了平滑过度30000个时间点上的DAG产生带来的延迟,可以预先生成DAG数据。

ETHASH算法源代码解读

我们之前探讨的算法都是纸上谈兵。接下去我们将分段用Go语言源码 方式来查看一下究竟ETHASH的挖矿和验证过程是如何进行的。探讨挖矿过程就如同探索爱丽丝仙境中的兔子洞,必须层层向下探索,它的最终解答的问题是:如何才能用ETHASH算法找到一个合法的nonce,进而形成一个块?

整个打包块的过程源于sealer(封装)函数,它需要负责封装一个合法的块,这个块的获得将是一个mine(挖矿)过程,我们来查看一下它们的函数签名。

/consensus/ethash/sealer.go
func (ethash *Ethash) Seal(chain consensus.ChainReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error {

Seal函数总目标是找到一个nonce,让其符合块难度设定,这样块就能成为合法的块而被其他节点所接受。接受多个参数输入,并返回一个Ethash的指针。输入参数中包含了ChainReader,可料想到对于区块链前置的数据是有扫描的;Block可见最终也会修改块的部分数据,例如头部数据。我们来查看一下Ethash数据结构是怎样的:

/consensus/ethash/ethash.go
type Ethash struct {
    config Config

    caches   *lru // LRU类型的Cache缓存避免大量反复查询
    datasets *lru // LRU类型的 DataSet数据集,防止反复生成

    // 挖矿相关
    rand     *rand.Rand    // 产生nonce的随机数
    threads  int           // 挖矿需要的线程数量
    update   chan struct{}
    hashrate metrics.Meter // 跟踪当下hash rate挖矿效率的参数

    // 远程打包者所关注的参数
    workCh       chan *sealTask   // 通知渠道,通知远程打包者打包数据
fetchWorkCh  chan *sealWork   // 获取渠道, 远程打包者获取元数据
submitWorkCh chan *mineResult // 提交渠道,远程打包者提交打包结果
    fetchRateCh  chan chan uint64 // 获取渠道,获取远程打包者提交挖矿效率参数值
    submitRateCh chan *hashrate   // 提交渠道,远程大包着提交挖矿效率参数值

    // 用于测试的钩子
    shared    *Ethash
    fakeFail  uint64
    fakeDelay time.Duration
    lock      sync.Mutex
    closeOnce sync.Once
    exitCh    chan chan error
}

我们看到了熟悉的三个元素,caches、datasets、rand,这三个参数在之前的算法粗略讲解里面已经提到,是ETHASH的所使用到参数的基石,我们看下这个具体的封装区块的过程。

/consensus/ethash/sealer.go
// Seal函数主要功能是触发miner函数进行挖矿操作
func (ethash *Ethash) Seal(chain consensus.ChainReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error {
    // 为了简洁,我们删去了测试代码
// 为了简洁,我们删去了共享挖矿的代码

    // 取消挖矿信号量
    abort := make(chan struct{})

    ethash.lock.Lock()
    threads := ethash.threads
    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()))
    }
    ethash.lock.Unlock()
    if threads == 0 {
        threads = runtime.NumCPU()// 决定多少并发挖矿线程
    }
    if threads < 0 {
        threads = 0 // 取消本地挖矿功能
    }
    // 将挖矿过程推送给远程挖矿者
    if ethash.workCh != nil {
        ethash.workCh <- &sealTask{block: block, results: results}
    }
    var (
        pend   sync.WaitGroup
        locals = make(chan *types.Block)
    )
    for i := 0; i < threads; i++ {
        pend.Add(1)
        go func(id int, nonce uint64) { // 最重要的函数,etash.mine为挖矿函数
            defer pend.Done()
            ethash.mine(block, id, nonce, abort, locals)
        }(i, uint64(ethash.rand.Int63()))
    }
    // 开启多线程,直到挖矿成功或者取消挖矿
    go func() {
        var result *types.Block
        select {
        case <-stop:
            // 外部取消信号捕捉,直接关闭挖矿线程
            close(abort)
        case result = <-locals:
            // 某一线程找到了合法块,通知其他挖矿线程关闭
            select {
            case results <- result:
            default:
                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 {
                log.Error("Failed to restart sealing after update", "err", err)
            }
        }
        // Wait for all miners to terminate and return the block
        pend.Wait()
    }()
    return nil
}

我们看到上文中大部分代码都在处理多线程关系,还有挖矿的开启和停止,用到了Go语言的核心功能–多线程并发。挖矿的代码就一行,是一个调用,调用了ethash.mine(block, id, nonce) 这个子函数进行真的苦力活PoW算法,下面我们查看一下这个具体挖矿的实现代码。

/consensus/ethash/sealer.go
// 通过PoW挖矿行为找到最终符合条件的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)
    )
    // 开启反复试算nonce值,直到算出,或者取消。
    var (
        attempts = int64(0)
        nonce    = seed
    )
    logger := log.New("miner", id)
    logger.Trace("Started ethash search for new nonces", "seed", seed)
search:
    for {  // 死循环开始
        select {
        case <-abort:
            // 如果我们取消了,停止
            logger.Trace("Ethash nonce search aborted", "attempts", nonce-seed)
            ethash.hashrate.Mark(attempts)
            break search

        default:
            // 记录尝试次数
            attempts++
            if (attempts % (1 << 15)) == 0 {
                ethash.hashrate.Mark(attempts)
                attempts = 0
            }
            // 重要! 试算PoW算式下的nonce值
digest, result := hashimotoFull(dataset.dataset, hash, nonce)
// 重要! 成功找到nonce值的判定标准!
            if new(big.Int).SetBytes(result).Cmp(target) <= 0 {
                // 更新header,试算结束!
                header = types.CopyHeader(header)
                header.Nonce = types.EncodeNonce(nonce)
                header.MixDigest = common.BytesToHash(digest)

                // 成功找到块打包结束
                select {
                case found <- block.WithSeal(header):
                    logger.Trace("Ethash nonce found and reported", "attempts", nonce-seed, "nonce", nonce)
                case <-abort:
                    logger.Trace("Ethash nonce found but discarded", "attempts", nonce-seed, "nonce", nonce)
                }
                break search
            }
            nonce++
        }
    }

    runtime.KeepAlive(dataset)
}

在上方的代码中,总逻辑是一个死循环,循环内部反复试算nonce值直到符合难度规定,那么判断的条件就是一个依据,如下面这行代码所示。

if new(big.Int).SetBytes(result).Cmp(target) <= 0 {

这句话至关重要,如果试算出来的结果result小于target,则试算成功。那么又是如何试算的呢?我们仔细看可以看到这么一个试算函数。

digest, result := hashimotoFull(dataset.dataset, hash, nonce)
/consensus/ethash/algorithm.go
func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    lookup := func(index uint32) []uint32 {
        offset := index * hashWords
        return dataset[offset : offset+hashWords]
}
// 将具体的hashimoto算法触发,获得最终的结果
    return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
}

上文可以看到hashimotoFull函数将计算的过程完全代理给了hashimoto函数,本身并没有过多的数据计算和操作,我们再深入到最深的兔子洞—hashitmoto()函数来看一下。

// 针对某个header和nonce,hashimoto函数采撷DataSet中部分数据来进行哈希
func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
    // 计算理论上用的到的“行”
    rows := uint32(size / mixBytes)

    // 组合header+nonce 形成 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)

    // 用seed开始“混合”操作
    mix := make([]uint32, mixBytes/4)
    for i := 0; i < len(mix); i++ {
        mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])
    }
    // 混合入数据集DataSet中的数据
    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)
    }
    // 压缩混合
    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...))
}

至此我们已经清晰地分析了整个试算nonce值的过程,整个过程犹如爱丽丝漫游仙境,需要层层向下探索兔子洞,按照“Seal -> mine -> hashimotoFull -> hashimoto”的顺序一层层往下解读源代码,找到试算nonce的过程,一旦找到合法的nonce立即停止多线程的mine挖矿过程,返回最终结果给Seal函数,形成合法的区块头。