以太坊源码分析 Ethash算法

Ethash是以太坊目前使用的共识算法,其前身是Dagger-Hashimoto算法,但是进行了很大的改动。

1. Dagger-Hashimoto

Dagger-Hashimoto算法想要达到以下几个目标:

  • 抵制ASIC矿机
  • 轻客户端验证
  • 全链数据存储

实际上Dagger-Hashimoto是由两种不同的算法Dagger和Hashimoto融合而成的:

Hashimoto

Hashimoto算法由Thaddeus Dryja发明,旨在通过“内存读取”瓶颈来抵制ASIC矿机。ASIC矿机可以通过设计专用电路来提升计算速度,但是很难提升“内存读取”速度,因为经历了这么多年的发展,内存访问已经经过了极致的优化。Hashimoto算法直接采用区块链数据,也就是区块中的交易作为输入源。

注:为了减小计算量,Dagger-Hashimoto中实际上只使用了低64位参与移位。

Dagger

Dagger算法由Vitalik Buterin发明,旨在通过DAG(有向无环图)来同时获得“memory-hard计算”和“memory-easy验证”这两个特性,其主要原理是针对每一个单独的nonce只需要访问数据集中的一小部分数据。Dagger曾经被认为可以替代一些memory-hard的算法(如Scrypt),但是后来被Sergio Lerner证明该算法易于遭受共享内存硬件加速的攻击,从而逐渐被废弃。

Dagger-Hashimoto vs. Hashimoto vs. Dagger

Dagger-Hashimoto和Hashimoto的主要区别是:Hashimoto直接使用区块链数据作为输入源,而Dagger-Hashimoto使用一个定制的1GB的dataset(数据集)作为输入源,该dataset每隔N个区块会被更新。dataset是通过Dagger算法生成的,轻客户端验证算法可以针对每一个nonce对其中一个子集完成高效计算。

Dagger-Hashimoto和Dagger的主要区别是:与Dagger不同,Dagger-Hashimoto用于查询区块的dataset是半持久化(semi-permanent)的,需要间隔很长一段时间才会更新。这样生成dataset的工作量比例接近于0,Sergio Lerner用于共享内存加速的参数就可以忽略不计了。

2. Ethash

Ethash算法主要分为以下几个步骤:

  • 根据区块信息生成一个seed
  • 根据seed计算出一个16MB的伪随机cache,由轻客户端存储
  • 根据cache计算出一个1GB的dataset,其中的每一个数据都是通过cache中的一小部分数据计算出来的。该dataset由完整客户端或者矿工存储,大小随时间线性增长
  • 矿工会从dataset中随机取出数据计算hash
  • 验证者会根据cache重新生成dataset中所需要的那部分数据,因此只需要存储cache就可以了

这里写图片描述

下面分别讨论这几个部分的实现。

2.1 生成seed

consensus/ethash/ethash.go:

func (d *dataset) generate(dir string, limit int, test bool) {
    ... ...
    seed := seedHash(d.epoch*epochLength + 1)
    ... ...
}

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

这里有个epoch(纪元)的概念:epochLength等于30000,也就是每30000个区块形成一个纪元,每个纪元更新一次数据集(就是前面提到的“半持久化”)。

seed初始值为0,每过一个纪元会取前一个seed的哈希值作为下一个纪元的seed。

2.2 生成cache

接下来就是用这个seed生成16MB的cache了。首先看一下cache大小的计算:

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) {
        size -= 2 * hashBytes
    }
    return size
}

前2048(maxEpoch)个纪元的cache大小是硬编码在代码里的,如果超过这个数量就需要自己计算了。cache的大小是线性增长的,size的值等于(2^24 + 2^17 * epoch - 64),用这个值除以64看结果是否是一个质数,如果不是,减去128再重新计算,直到找到最大的质数为止。

接下来分析cache数据的生成:

func generateCache(dest []uint32, epoch uint64, seed []byte) {
    ... ...
    // Create a hasher to reuse between invocations
    keccak512 := makeHasher(sha3.NewKeccak512())

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

看明白没?先用seed的哈希值生成第一个数(64字节),然后以新生成的数作为seed,生成下一个数,依次迭代,直至填充满整个cache。当然这只是第一步,后面还要跟之前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.3 生成dataset

dataset大小的计算和cache类似,量级不同:2^30 + 2^23 * epoch - 128,然后每次减256寻找最大质数。

生成数据是一个循环,每次生成64个字节,所以看generateDatasetItem()就可以了。代码分为下面几个部分:

  1. 用cache里的值进行初始化,计算一次哈希
    // 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)
  1. 转换成无符号整数
    // 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:])
    }

2)计算FNV哈希

    // 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:])
    }

4)整数转回字节数组,再计算一次哈希

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

这里用到了FNV哈希算法,这是一种不需要使用密钥的哈希算法,以它的三位发明者的名字命名:Glenn Fowler, Landon Curt Noll, Kiem-Phong Vo。这个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]
    }
}

从这里可以看出,dataset的每个值都是根据对应的cache中的值生成的,因此轻客户端无需存储dataset,只需要在验证的时候按需生成即可。

2.4 矿工挖矿

挖矿流程参见下图:这里写图片描述

具体代码参见consensus/ethash/algorithm.go中的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)
}

首先提供了一个lookup()函数,用于从dataset中查找数据。接着就是调用hashimoto()函数计算哈希了:首先根据hash和nonce生成一个seed,填充到mix数组中,然后用lookup()函数获取data,最后把mix和data送入fnvHash()函数中计算哈希值。具体代码这里就不分析了。

2.5 工作量验证

在节点收到新区块时,需要验证根据区块头的hash和nonce计算出来的FNV哈希值是否确实小于设定的难度值。入口位于core/blockchain.go的insertChain()方法:

func (bc *BlockChain) insertChain(chain types.Blocks) (int, []interface{}, []*types.Log, error) {
    ... ...
    for i, block := range chain {
        headers[i] = block.Header()
        seals[i] = true
    }
    abort, results := bc.engine.VerifyHeaders(bc, headers, seals)
    ... ...
}

继续跟踪consensus/ethash/consensus.go中的VerifyHeaders()方法,最终会调用verifyHeader():

func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *types.Header, uncle bool, seal bool) error {
    ... ...
    if seal {
        if err := ethash.VerifySeal(chain, header); err != nil {
            return err
        }
    }

    ... ...
}

这里会调用VerifySeal()方法验证区块头是否符合要求:

func (ethash *Ethash) VerifySeal(chain consensus.ChainReader, header *types.Header) error {
    ... ...
    digest, result := hashimotoLight(size, cache.cache, header.HashNoNonce().Bytes(), header.Nonce.Uint64())

    ... ...
    target := new(big.Int).Div(maxUint256, header.Difficulty)
    if new(big.Int).SetBytes(result).Cmp(target) > 0 {
        return errInvalidPoW
    }
    return nil
}

可以看到,这里调用hashimotoLight()函数计算FNV哈希值,然后跟目标难度比较,确认是否低于目标难度。这个hashimotoLight()就是为轻客户端节点计算FNV哈希值的,会根据需要通过cache生成少量dataset的值完成计算,有兴趣的同学可以再仔细研究一下具体细节。

3. 总结

Ethash是一种“memory-hard计算”和“memory-easy验证”的哈希算法,通过内存访问速度的瓶颈抵抗ASIC矿机,同时利用两级数据集实现挖矿和轻客户端验证的分离。

下一章:以太坊源码分析 控制台

本文分析以太坊控制台的工作原理和流程。当我们通过 geth console 或者 geth attach 与节点交互的时候,输入的命令是如何被处理的呢?命令行编辑器 Liner 等待用户输入命令JSRE 使用一个名为 ...