阅读 213

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

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

以太坊目前的算法是类似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的。

如图所示:

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

如图所示:

  1. 数字标记代表调用入口,其中3、4代表MakeCache和MakeDataset,是geth提供的命令,用于生成cache和dataset(生成dataset要先生成cache)。
  2. 重点是数字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的部分

如图所示:

  • 调用入口与上图类似。
  • 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生成最终值。

如图所示:

  • 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矿机垄断,增强了去中心化能力。

参考资料

关注下面的标签,发现更多相似文章
评论