精华内容
下载资源
问答
  • 以太坊改算法
    2021-07-16 21:38:31

    共识算法

    目前以太坊中有两个公式算法的实现,分别为clique和ethash。其中clique是PoA共识的实现,ethash是PoW共识的实现,其相应的代码位于go-ethereum/consensus目录下。

    PoW (ethash)

    PoW定义

    PoW与PoA不同之处在于,PoW是一个人人都可能有出块权的共识机制,而PoA通过“选举专家”来确认出块权。PoW可以被概括为如下:

    PoW用来对人人可以参与的区块链项目的出块权进行确权。确权的方式是通过计算满足一定的条件。这个计算必须是复杂的、耗时的;而条件的验证最好是非常简单能快速完成的。
    

    基础的Pow实现思路如下:

    • 使用哈希算法作为计算复杂、验证简单的保证;

    • 验证方式为将计算得到的哈希值作为一个数值,比较其是否小于某一阈值;

    • 根据前一个块的出块时间长短,阈值可以动态调整,以保证计算复杂度;

    • 哈希算法的数据源为新块的Header的哈希(保留Nonce字段可以随意更改)。

    ethash实现方案

    算法设计要求

    以太坊中的共识算法ethash的实现思路与上述大题一致,只是哈希算法使用的数据源有较大区别。

    同时,以下为官方提供的ethash共识算法的设计准则:
    在这里插入图片描述

    1. 首先,它要求算法是IO饱和的,也就是说,算法执行过程中需要占用几乎所有的内存读写带宽(需要内存不断读写,且达到饱和),从而避免了如ASIC这样的专用挖矿设备的影响(这种设备应该是针对某种哈希计算做优化,但是设备中内存很小之类的);
    2. GPU友好型,指可以利用GPU进行挖矿;
    3. 轻量级客户端可以快速验证挖矿的结果;
    4. 但是,轻量级客户端的挖矿速度很慢。

    验证方式

    首先,在Geth中以太坊区块链区块头部的定义如下:
    在这里插入图片描述
    其中,Difficulty字段表示当前的“出块难度”,ethash计算得到的哈希值作为整数,必须小于 2 256 / D i f f i c u l t y 2^{256}/Difficulty 2256/Difficulty,这个哈希才能被认为是有效的。

    另外,注意到以太坊在区块头部中还含有一个MixDigest字段,这是由于ethash算法中额外的验证所产生的。因此,ethash在计算hash时会得到两个值,除了用来与Difficulty比较的哈希值外,另外一个用来与MixDigest进行比较。同时,若想通过验证,那么这个哈希值必须与MixDigest字段一致。

    综上,ethash的验证方式可以总结为:

    • 首先,进行哈希计算得到两个哈希值,分别为digest和result;

    • result作为一个整数值,必须小于 2 256 / D i f f i c u l t y 2^{256}/Difficulty 2256/Difficulty

    • mix必须与区块头部的字段MixDigest相同。

    后续将会介绍这两个哈希值digest和result是怎么被计算出来的。

    难度调整

    ethash实现了对出块难度要求的动态调整,以粗略保证出块的时间间隔的稳定。以太坊的发布分成了四个阶段:FrontierHomesteadMetropolisSerenity。各个阶段对应的难度计算公式有些不同。

    同时,在Metropolis阶段中出现过两个版本的硬分叉,分别为拜占庭(Byzantium)分叉以及君士坦丁堡(Constantinople)分叉。

    由于以太坊设计一开始的计划是把PoW共识当作一个过渡,最终的以太坊将使用PoS作为共识,而弃用PoW。如果这个转变过程处理地不好,必然会损害一部分矿工的利益。因此,在最初的阶段Frontier中,以太坊的设计者在难度计算公式中加入了指数变化的部分(这个设计称为“难度炸弹”),目的是使得矿工对难度变化有一个预期,不会投入过多的资源再购买挖矿硬件上,以使得从PoW转向PoS能够平稳过渡。但是,由于以太坊的共识计划的转型迟迟没有完成,而此时的挖矿难度的增加已经使得很难或几乎不可能出块,这个时期称为“冰川时代”,因此,以太坊官方先后发起了两次硬分叉,其目的主要是为了延迟挖矿难度的上升趋势(可能降低挖矿难度),以等待共识机制的转型,这两次分叉称为“延迟难度炸弹”。

    此外,后续的“缪尔冰川”升级也是为了“延迟难度炸弹”(在Serenity版本发布前夕,陆续经历了“伊斯坦布尔” 升级、“缪尔冰川” 升级以及“柏林” 升级,但由于Serenity版本发行过程中遇到的各种问题,因此一直在不断被推迟,Serenity版本的发行意味着以太坊从1.0版本向2.0的转型)。

    哈希数据源

    对于前面介绍的基础的PoW,我们使用的是区块头部作为哈希计算的数据源。由于以太坊希望ethash能够抵制ASIC矿机,因此ethash除了使用区块头部信息之外,还需要一个更大的数据集作为数据源来计算哈希。

    那么以太坊是如何地址ASIC矿机的呢?简单来说,是通过内存限制来抵制的。原因如下,一是因为ASIC矿机中使用大内存比较昂贵;二是因为大量随机读取内存数据时计算速度就不仅仅受限于计算单元,更受限于内存的读出速度。由于在ethash中,计算哈希首先就要维护一个初始大小为1G的数据集(除此之外还有一个缓存数据集),同时这个数据集的大小还会随着区块链的长度增长而不断增大(这是为了应对硬件的不断发展),具体的数据集大小变化公式已经在黄皮书中给出:
    在这里插入图片描述
    计算哈希的数据源就是从这块数据集中来的;而决定使用数据集中的哪些数据进行哈希计算的,才是区块头部数据和Nonce字段。此外,ethash中使用的这种方法可以看作是“Dagger-Hashimoto”算法的变种。

    为了表述方便,后续我们将使用dataset来表示这个数据集。

    Dagger

    Dagger算法定义了dataset的生成方式和组织方式。

    我们可以认为dataset是由多个dataitem组成的巨大数据,而每一个dataitem是一个64字节的byte数组(可以理解为一条哈希)。每一个dataitem又是由缓存数据集(cache)生成的,同样地,cache也可以认为是由多个cacheitem组成的,每个cacheitem也是一条哈希,但是cache占用的空间比dataset小得多。

    生成一个dataitem的步骤大致如下:从cache中选择一个cacheitem进行计算,得到的结果参与下次计算,这个过程会循环进行256次(相当于对某一个cacheitem进行256次计算后得到的结果)。cache则是由seed生成,seed的值与块的高度有关。根据黄皮书中的定义,seed的计算方式如下:
    在这里插入图片描述
    综上,dataset的生成大致过程如下图所示:
    在这里插入图片描述
    Dagger还有一个关键的地方,就是确定性。即同一个epoch(以太坊中规定每30000个区块为一个epoch)内,每次计算出来的seed、cache、dataset都是相同的(具体的计算方式见黄皮书)。否则对于同一个区块,挖矿的人和验证的人使用不同的dataset,就没法进行验证。在以太坊中的文档中,称这个巨大的dataset为DAG。

    dataset作为哈希计算的数据源,在保证挖矿必须用到大量内存的同时,也使得验证变得简单,其原因如下:

    1. 挖矿是一个反复尝试的过程,如果矿工不维护这个dataset,那么就需要在每次尝试时计算需要用到的dataitem,这种重新计算的过程相比于直接从维护的dataset中获取相应的dataitem来说是相当耗时的。因此,如果不占用内存来维护这个dataset,那么挖矿就必然消耗大量的计算成本,从而逼迫矿工放弃这种做法。
    2. 如果某个节点只是单纯地需要验证收到的区块,那么它只需要保存cache,之后在验证过程中如果缺少对应的dataitem,那么就通过cache生成相应的dataitem。由于验证的过程只进行一次,因此它的开销可以忽略不计。

    Hashimoto

    Hashimoto算法则是利用区块头部数据和Nonce字段以及生成的dataset数据集,生成一个最终的哈希值。其大致步骤如下:

    1. 首先利用区块头部(不含Nonce和MixDigest)哈希与Nonce值生成一个初始哈希;

    2. 经过计算得到需要获取dataset数据集中的dataitem的索引;

    3. 获取dataitem后将其聚合到mix变量中;

    4. 最终返回mix值以及计算结果result(mix值在验证时与区块头部的MixDigest比较,result与区块头部Difficulty比较如果满足条件则表明成功挖出一个有效的区块)。

    ethash源码解析

    ethash模块实现的源码位于go-ethereum/consensus/ethash目录下,此目录下的文件及其相应的代码功能如下:

    • algorithm.go
      此文件实现了Dagger-Hashimoto算法的所有功能,包括dataset、cache的生成以及计算挖矿哈希等

    • api.go
      此文件实现了供RPC使用的api方法

    • consensus.go
      此文件实现了以太坊共识接口的部分代码

    • ethash.go
      此文件实现了cache结构体和dataset结构体及它们各自的方法

    • sealer.go
      此文件实现了共识接口的Seal方法以及ethash的挖矿功能

    ethash模块下的几个重要函数分别为MakeCache()函数、MakeDataset()函数、Ethash.Seal()和Ethash.VerifySeal()函数。它们的作用分别为产生缓存集、产生哈希运算数据集、挖矿打包区块以及验证被打包的区块,这些函数最终都会都会调用到generateCache()或者generateDataset()这两个函数来产生相应的数据,这些函数的调用流程如下图所示:
    在这里插入图片描述

    generateCache()以及generateDataset()这两个函数也是生成cache数据和dataset数据的真正实现。在后续的内容中,我们会具体分析这两个函数的实现方式。

    数据保存

    注意到,cache数据和dataset数据不仅仅存储在内存中,它们也可以被保存在用户的磁盘上。如果每次都需要重新生成这些数据集,这将会花费一些不必要的计算时间,因此将数据保存在磁盘中,并在下次需要用到的时候直接从磁盘中读取,可以很好的节约这些时间开销。在ethash.go中就定义了cache结构体以及dataset结构体,从而方便将cache数据和dataset数据的初始化以及磁盘文件的保存,它们的定义如下:

    type cache struct {
    	epoch uint64    // Epoch for which this cache is relevant
    	dump  *os.File  // File descriptor of the memory mapped cache
    	mmap  mmap.MMap // Memory map itself to unmap before releasing
    	cache []uint32  // The actual cache data content (may be memory mapped)
    	once  sync.Once // Ensures the cache is generated only once
    }
    type dataset struct {
    	epoch   uint64    // Epoch for which this cache is relevant
    	dump    *os.File  // File descriptor of the memory mapped cache
    	mmap    mmap.MMap // Memory map itself to unmap before releasing
    	dataset []uint32  // The actual cache data content
    	once    sync.Once // Ensures the cache is generated only once
    	done    uint32    // Atomic flag to determine generation status
    }
    

    其中dumpmmap字段就是负责磁盘数据读写操作的。另外,once字段用来保证数据的初始化只进行一次。后续我们提到cache和dataset仅仅指的是里面存储的字节数据而不是这个结构体。

    数据生成

    前面我们提到过generateCache()以及generateDataset()这两个函数才是负责真正生成cache数据和dataset数据的,它们位于algorithm.go文件中。

    首先对于generateCache()函数,其主要代码(省略部分不重要的代码)如下:

    func generateCache(dest []uint32, epoch uint64, seed []byte) {
    	...
    	// Convert our destination slice to a byte buffer
    	var cache []byte
    	...
    
    	// Calculate the number of theoretical rows (we'll store in one buffer nonetheless)
    	size := uint64(len(cache))
    	rows := int(size) / hashBytes
    
    	...
        
    	// 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])
    		...
    	}
    	// 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)
    
    			...
    		}
    	}
        
        ...
    }
    

    从上面的代码中可以看出,每个cache可以被分成多个cacheitem,同时每个cacheitem的大小为hashBytes(64字节)。cache数据的生成过程如下:

    1. 首先,利用seed进行KEC512计算保存在第零个cacheitem中(代码17行);
    2. 从第一个cacheitem开始,后一个cacheitem为前一个cacheitem的KEC512哈希值,依次计算(代码18—21行);
    3. 循环cacheRounds次,每次循环变量所有的cacheitem,并根据黄皮书中给出的公式更新相应的cacheitem(代码25—37行)。

    对于generateDataset()函数,精简后的代码如下:

    func generateDataset(dest []uint32, epoch uint64, cache []uint32) {
    	...
    	// Convert our destination slice to a byte buffer
    	var dataset []byte
    	...
    
    	// 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 uint64
    	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 := (size + hashBytes*uint64(threads) - 1) / (hashBytes * uint64(threads))
    			first := uint64(id) * batch
    			limit := first + batch
    			if limit > size/hashBytes {
    				limit = size / hashBytes
    			}
    			// Calculate the dataset segment
    			for index := first; index < limit; index++ {
    				item := generateDatasetItem(cache, uint32(index), keccak512)
    				...
    				copy(dataset[index*hashBytes:], item)
    				...
    			}
    		}(i)
    	}
    	// Wait for all the generators to finish and return
    	pend.Wait()
    }
    

    generateDataset()函数主要是根据CPU线程数分配任务到多个go线程中,每个go线程负责生成制定索引index区间内的所有dataitem,最后将这些所有的dataitem合并起来就是我们需要的dataset数据集,因此我们重点分析31行处调用generateDatasetItem()函数的代码,其作用为生成指定索引的dataitem,其主要代码内容如下:

    func generateDatasetItem(cache []uint32, index uint32, keccak512 hasher) []byte {
    	// 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
    }
    

    注意到,代码第3行处的rows的计算方式,因为cache中的数据项是以uint32形式存储的,因此这行代码的计算结果为cache数据中cacheitem的项数。代码中出现的cache[(index%rows)*hashWords]的访问方式,就是为了确保对cache的访问是以cacheitem为单位进行的。因此,dataitem生成的过程如下:

    1. 获取cache中的第index个cacheitem与index做异或运算的结果,再进行KEC512哈希运算(代码8—12行);

    2. 接着循环执行相应的计算datasetParents次(具体计算公式见黄皮书),同时每次计算的结果会作为下一次计算的输入(代码20—23行);

    3. 循环结束后将结果再次进行KEC512哈希运算并输出(代码28行);

    工作量证明函数

    以太坊的工作量证明函数为hashimoto(),它会在hashimotoLight()和hashimotoFull()中被调用,这两个函数主要区别在于前者使用cache数据,并在调用过程中生成需要用到的dataset数据来提供工作量证明,而后者直接使用dataset数据提供工作量证明,因此前者一般用来验证区块而后者则在挖矿过程中被调用。hashimoto()函数的主要代码如下:

    // hashimoto aggregates data from the full dataset in order to produce our final
    // value for a particular header hash and nonce.
    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...))
    }
    

    该函数最终返回两个输出,在挖矿过程中,如果挖矿成功,第一个输出会作为MixDigest放入区块头部,在验证过程中,它将会被用来与区块头部的MixDigest字段比较来验证区块的正确性,第二个输出则会与区块头部的Difficulty字段进行比较来判断是否满足工作量证明。其工作流程如下:

    1. 首先对区块头部哈希(不包含Nonce和MixDigest字段)与nonce进行拼接,之后计算KEC512哈希得到seed(代码7—12行);
    2. 接着用得到的seed初始化mix数据,这里做的相当于将seed与自身拼接一次得到mix(代码15—19行);
    3. 接着循环loopAccesses次,每次计算索引parent,再根据索引调用lookup函数获取相应的dataset数据,获取的数据放入temp中,再将mix与temp进行FNV函数计算,更新mix(代码21—29行);
    4. 然后循环对mix执行compress操作(代码31—35行,具体公式见黄皮书);
    5. 最后,对mix的格式进行修改放入digest中作为第一个输出,seed与digest进行拼接作为第二个输出(代码37—41行)。

    该函数会在hashimotoLight()和hashimotoFull()中被调用,它们调用的具体形式如下:

    // hashimotoLight aggregates data from the full dataset (using only a small
    // in-memory cache) in order to produce our final value for a particular header
    // hash and nonce.
    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)
    }
    
    // hashimotoFull aggregates data from the full dataset (using the full in-memory
    // dataset) in order to produce our final value for a particular header hash and
    // nonce.
    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函数的形式不同,第一个函数每次都需要根据cache和index生成相应的datasetitem,而第二个函数则只需要获取记录在内存中对应index的datasetitem。

    挖矿

    矿工在进行挖矿时会依次调用Engine接口的Prepare()、Finalize()以及Seal()函数,它们的作用分别为计算和填充区块头部的Difficulty值、计算区块中交易执行结束后的状态并放入区块头部的Root字段,以及进行挖矿操作。前两个函数的实现比较简单(在ethash中它们的实现位于ethash/consenus.go文件),相应的代码如下:

    // Prepare implements consensus.Engine, initializing the difficulty field of a
    // header to conform to the ethash protocol. The changes are done inline.
    func (ethash *Ethash) Prepare(chain consensus.ChainHeaderReader, header *types.Header) error {
    	parent := chain.GetHeader(header.ParentHash, header.Number.Uint64()-1)
    	if parent == nil {
    		return consensus.ErrUnknownAncestor
    	}
    	header.Difficulty = ethash.CalcDifficulty(chain, header.Time, parent)
    	return nil
    }
    
    // Finalize implements consensus.Engine, accumulating the block and uncle rewards,
    // setting the final state on the header
    func (ethash *Ethash) Finalize(chain consensus.ChainHeaderReader, header *types.Header, state *state.StateDB, txs []*types.Transaction, uncles []*types.Header) {
    	// Accumulate any block and uncle rewards and commit the final state root
    	accumulateRewards(chain.Config(), state, header, uncles)
    	header.Root = state.IntermediateRoot(chain.Config().IsEIP158(header.Number))
    }
    

    对于Seal()函数(在ethash中它的实现位于ethash/sealer.go文件),其主要代码内容如下:

    // Seal implements consensus.Engine, attempting to find a nonce that satisfies
    // the block's difficulty requirements.
    func (ethash *Ethash) Seal(chain consensus.ChainHeaderReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error {
    	...
        
    	threads := ethash.threads
    	...
        
    	if threads == 0 {
    		threads = runtime.NumCPU()
    	}
    	if threads < 0 {
    		threads = 0 // Allows disabling local mining without extra logic around local/remote
    	}
    	// Push new work to remote sealer
    	if ethash.remote != nil {
    		ethash.remote.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) {
    			defer pend.Done()
    			ethash.mine(block, id, nonce, abort, locals)
    		}(i, uint64(ethash.rand.Int63()))
    	}
    	// Wait until sealing is terminated or a nonce is found
    	go func() {
    		...
    		pend.Wait()
    	}()
    	return nil
    }
    

    其中,在代码第23—29行,它创建了多个线程同时进行挖矿,并且等待挖矿的结果,而挖矿的主要工作则是调用Ethash.mine()函数实现的,该函数的主要内容如下:

    // mine is the actual proof-of-work miner that searches for a nonce starting from
    // seed that results in correct final block difficulty.
    func (ethash *Ethash) mine(block *types.Block, id int, seed uint64, abort chan struct{}, found chan *types.Block) {
    	// Extract some data from the header
    	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)
    	)
    	// Start generating random nonces until we abort or find a good one
    	var (
    		attempts = int64(0)
    		nonce    = seed
    	)
    	...
    search:
    	for {
    		select {
    		case <-abort:
                ...
    			break search
    
    		default:
    			attempts++
    			...
                
    			// Compute the PoW value of this nonce
    			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)
    
    				// Seal and return a block (if still needed)
    				select {
    				case found <- block.WithSeal(header):
    					...
    				case <-abort:
    					...
    				}
    				break search
    			}
    			nonce++
    		}
    	}
    	...
    }
    

    Seal()函数在调用mine()函数是,首先传入一个随机生成的nonce初始值,接着利用这个初始值以及区块头部(不含Nonce和MixDigest)的哈希在一个循环中调用hashimotoFull()函数分别得到结果存入digest和result,接着将result与区块头部的Difficulty进行比较,观察是否满足工作量证明。如果满足,说明挖矿成功,则将digest以及此时的nonce分别写入区块头部的MixDigest和Nonce字段;否则修改nonce的值为nonce+1,并继续循环。

    多节点远程挖矿

    当我们分析Seal()函数时,我们可以注意到函数中的几行代码,其内容如下:

    func (ethash *Ethash) Seal(chain consensus.ChainHeaderReader, block *types.Block, results chan<- *types.Block, stop <-chan struct{}) error {
    	...
    	// Push new work to remote sealer
    	if ethash.remote != nil {
    		ethash.remote.workCh <- &sealTask{block: block, results: results}
    	}
    	...
    }
    
    

    由注释可以看出,这段代码的主要功能是将当前工作提交到一个远程节点进行挖矿。那么远程节点是如何接受这个信息的呢?我们可以观察到,在利用ethash/ethash.go文件中的New函数对Ethash对象进行初始化时,会调用startRemoteSealer()函数,startRemoteSealer()函数又会开启一个线程,去接受相应的工作信息,其主要代码如下:

    func New(config Config, notify []string, noverify bool) *Ethash {
    	...
    	ethash.remote = startRemoteSealer(ethash, notify, noverify)
    	...
    }
    
    func startRemoteSealer(ethash *Ethash, urls []string, noverify bool) *remoteSealer {
    	...
    	go s.loop()
    	...
    }
    
    func (s *remoteSealer) loop() {
    	...
    
    	for {
    		select {
    		case work := <-s.workCh:
    			// Update current work with new received block.
    			// Note same work can be past twice, happens when changing CPU threads.
    			s.results = work.results
    			s.makeWork(work.block)
    			s.notifyWork()
    		...
    		}
    	}
    }
    

    在接收到通道中传递过来的信息之后,会分别调用makeWork()和notifyWork()两个函数,用来包装需要传递的信息以及传递包装后的信息,主要代码如下:

    func (s *remoteSealer) makeWork(block *types.Block) {
    	hash := s.ethash.SealHash(block.Header())
    	s.currentWork[0] = hash.Hex()
    	s.currentWork[1] = common.BytesToHash(SeedHash(block.NumberU64())).Hex()
    	s.currentWork[2] = common.BytesToHash(new(big.Int).Div(two256, block.Difficulty()).Bytes()).Hex()
    	s.currentWork[3] = hexutil.EncodeBig(block.Number())
    
    	// Trace the seal work fetched by remote sealer.
    	s.currentBlock = block
    	s.works[hash] = block
    }
    
    func (s *remoteSealer) notifyWork() {
    	work := s.currentWork
    	blob, _ := json.Marshal(work)
    	s.reqWG.Add(len(s.notifyURLs))
    	for _, url := range s.notifyURLs {
    		go s.sendNotification(s.notifyCtx, url, blob, work)
    	}
    }
    
    func (s *remoteSealer) sendNotification(ctx context.Context, url string, json []byte, work [4]string) {
    	...
    
    	req, err := http.NewRequest("POST", url, bytes.NewReader(json))
    	...
    	ctx, cancel := context.WithTimeout(ctx, remoteSealerTimeout)
    	...
    }
    

    另外,远程节点可以调用api接口中的GetWork()和SubmitWork()来获取远程节点传递过来的信息以及提交挖矿的结果。

    其实这就是一个简单的支持矿池挖矿的基础功能。这里不得不提一下stratum协议,这是一个支持矿池挖矿的完整的协议,但以太坊并不支持这个协议,而是仅仅提供了简单的eth_getWork和eth_submitWork接口。

    PoA (clique)

    PoA,全称Proof of Authority,中文译为权威证明。PoA的基本思想应该也是来源于现实世界:在现实世界里,对很多事情我们往往“诉诸权威”,即我们相信专家。PoA的思想与此类似:授权一定数量的“专家”,由这些人相互合作打包区块并对区块链进行维护,其它人则无权打包区块,并且普通人相信成为专家的人会努力维护区块链的正常秩序。

    PoA牺牲了一部分去中心化的特性,换来了一种可控性。与此同时,它在设计时也存在两个必须要解决的问题,这里我们将实现区块打包维护的专家称为签名者,那么问题可以表述为:

    • 问题一:如何实现签名者的引进和踢出
      PoA的第一个问题是需要解决签名者更换的问题。在PoA中,签名者必须保证多数情况下在线出块。然而随着项目的不断运行,不可能所有签名者都一直有资源、有意愿继续工作;另外偶尔签名者也会作恶,必须及时将作恶的人踢出。(在PoW中任何人随时都可以加入区块链网络并尝试出块,也可以随时退出网络)
    • 问题2:如何控制出块时机
      首先要明确的是,出块时机由两方面决定:一是出块时间;二是由谁出块。在PoA中,签名者之间是合作关系,共同协商出块时机。(在PoW中所有人竞争出块权,算力越高的人越有可能竞争得到出块权)

    clique设计思路

    首先,在介绍clique算法之前,需要对算法中用到的几个名字进行解释:

    • CHECKPOINT:一个特殊的块,它的高度为EPOCH_LENGTH的整数倍,该块中不包含投票信息只包含当前所有的签名者列表;
    • EPOCH_LENGTH:两个CHECKPOINT之间相隔的区块数量(以太坊中这个值为30000,也就是说每隔30000个区块会产生一个CHECKPOINT),生成CHECKPOINT时会清除当前所有未生效的投票信息;
    • SIGNER_COUNT:当前时刻签名者(有权进行签名)的数量;
    • SIGNER_LIMIT:以太坊中这个值为SIGNER_COUNT/2+1,也就是说当一个签名者对某个区块进行签名之后,至少需要间隔SIGNER_LIMIT个区块才能再次进行签名,同时它也是投票生效的票数阈值;
    • BLOCK_PERIOD:出块时间的最小间隔,两个相邻区块产生的时间差必须不小于这个值;
    • DIFF_INTURN:此状态代表“按道理当前应该轮到我出块”(它被记录在区块头部的Difficulty字段);
    • DIFF_NOTURN:此状态代表“按道理当前还没轮到我出块”(它被记录在区块头部的Difficulty字段);

    clique算法与ethash算法的区块头部数据结构形式相同,但某些字段记录的内容有所不同,具体如下表所示:

    字段PoWPoA
    Coinbase挖矿奖励者地址普通块中表示被投票人地址;CHECKPOINT块这个字段为全零
    Nonce满足工作量证明的随机数普通块中投票结果(表明对被投票人进行添加或者删除);CHECKPOINT块这个字段为全零
    MixDigest混合摘要这个字段为全零
    UncleHash叔块摘要这个字段为全零
    Difficulty挖矿难度1或2,分别代码状态DIFF_NOTURN和DIFF_INTURN
    Extra额外数据普通块中为32字节空前缀+65字节当前区块出块者对区块头部的签名;CHECKPOINT块这个字节为32字节空前缀+所有签名者地址列表+65字节当前区块出块者对区块头部的签名

    接下来我们来观察一下clique算法是如何解决上述两个问题的。

    • 问题一:如何实现签名者的引进和踢出
      1. 只有当前签名者列表中的签名者可以进行投票,投票信息保存在区块头部,具体见上表。一个区块只能保存一个投票信息,并且只能在自己生成的区块上保存。
      2. 每一轮(每EPOCH_LENGTH个区块为一轮)投票结束后,所有的投票信息都将会被清空。
      3. 如果某个被投票人累计的票数超过SIGNER_LIMIT,那么投票结果立即生效。如果生效的是添加票(被投票人不在签名者列表中),则将被投票人加入到签名者列表中;如果是删除票(被投票人在签名者料表中),则将被投票人从签名者列表中移除,同时移除被投票人已经投出去的票。注意到,如果投的是添加票,那么当前被投票人一定不在签名者列表中;反之,如果投的是删除票,那么当前被投票人一定在签名者列表中(不存在将当前已经在签名者列表中的人引入签名者列表或者将当前不在签名者列表中的人移出签名者列表这种情况)。另外,删除票生效后可能会导致原本不通过的投票,在被投票人被移除后成立(因为将被投票人从签名者列表中移除,就可能导致SIGNER_LIMIT减少,那么就可能存在某个被投票人累计的票数超过SIGNER_LIMIT),clique算法不处理这种情况,而是放到下次统计时再进行判断。
      4. 对于无效的投票,即被投票人已经在签名者列表中却被投了添加票或者被投票人不在签名者列表中却被投了删除票。无效投票不会被惩罚,但是包含无效投票的区块是不会被打包的,即使被打包传播到区块链网络中,也不会被其他节点承认。
      5. 发起一个投票后,客户端不会被立即清除投票信息,而是在之后每次出块时都会选一个继续投票。因为区块链中的有效区块有重新调整的可能性,所以不能认为投票生效了之后就会一直生效。(这个部分不太明白,有人能解释一下吗)
      6. 在同一轮内,一个签名者给同一个账号地址重复投票时,会先将上次的投票信息清除,然后再统计本次的投票信息(如果在统计本次投票信息时发现本次投票是无效的,那么清楚的信息也不会恢复)。
      7. 每个CHECKPOINT不进行投票,而只是包含当前签名者列表信息。对于其它区块,可以用来携带投票信息。
    • 问题2:如何控制出块时机
      出块时机由两方面决定:一是出块时间;二是由谁出块。
      • 出块时间
        1. 只有出块间隔大于BLOCK_PERIOD的区块才是有效的。
      • 由谁出块
        1. 出块者必须在签名者列表中并且在SIGNER_LIMIT内没有出过块(SIGNER_LIMIT保证了同一个签名者不能连续出块,如果同一个签名者一直向其他签名者上传自己的区块,首先这个区块是无法通过验证的,同时其他签名者也有权投票将他从签名者列表中移除)。
        2. 如果签名者是DIFF_INTURN状态,则拥有较高出块权(立即出块);否则,如果签名者是DIFF_NOTURN状态,则拥有较低出块权(延迟一段时间)。该签名者处于什么状态是由当前区块高度,当前签名者列表共同决定的。

    clique源码解析

    投票信息记录

    Snapshot对象是clique中比较重要的一个对象,它的作用是统计某一轮中的投票信息以及当前的签名者列表,在后续不管是区块打包还是区块验证都会反复用到这个数据结构中的相关信息。同时它以checkpointInterval=1024为周期,每隔一个周期(1024个区块)都会在磁盘上对该数据结构进行保存,并且在需要用到相应的Snapshot时,如果磁盘中存在,也可以直接从磁盘中读取。相关代码位于go-ethereum/consensus/clique/snapshot.go文件。Snapshot对象的定义如下:

    // Snapshot is the state of the authorization voting at a given point in time.
    type Snapshot struct {
    	config   *params.CliqueConfig // Consensus engine parameters to fine tune behavior
    	sigcache *lru.ARCCache        // Cache of recent block signatures to speed up ecrecover
    
    	Number  uint64                      `json:"number"`  // Block number where the snapshot was created
    	Hash    common.Hash                 `json:"hash"`    // Block hash where the snapshot was created
    	Signers map[common.Address]struct{} `json:"signers"` // Set of authorized signers at this moment
    	Recents map[uint64]common.Address   `json:"recents"` // Set of recent signers for spam protections
    	Votes   []*Vote                     `json:"votes"`   // List of votes cast in chronological order
    	Tally   map[common.Address]Tally    `json:"tally"`   // Current vote tally to avoid recalculating
    }
    

    其中,Signers字段表示签名者列表,Recents表示最近某个区块的签名者地址,Votes是所有投票信息的集合,Tally表示投给某个被投人所有票的总和。Vote和Tally对象的具体定义如下

    // Vote represents a single vote that an authorized signer made to modify the
    // list of authorizations.
    type Vote struct {
    	Signer    common.Address `json:"signer"`    // Authorized signer that cast this vote
    	Block     uint64         `json:"block"`     // Block number the vote was cast in (expire old votes)
    	Address   common.Address `json:"address"`   // Account being voted on to change its authorization
    	Authorize bool           `json:"authorize"` // Whether to authorize or deauthorize the voted account
    }
    
    // Tally is a simple vote tally to keep the current score of votes. Votes that
    // go against the proposal aren't counted since it's equivalent to not voting.
    type Tally struct {
    	Authorize bool `json:"authorize"` // Whether the vote is about authorizing or kicking someone
    	Votes     int  `json:"votes"`     // Number of votes until now wanting to pass the proposal
    }
    

    从代码中我们可以看出,Vote代表的是一次投票的详细信息,其中字段Signer表示投票者,Address表示被投票者,Block表示此投票所在的区块以及Authorize表示投的是添加票还是删除票;Tally表示对被投票者的投票结果统计,其中Authorize表示投的是添加票还是删除票,Votes表示相应的票数总和。

    对于Snapshot对象,其中的一个重要函数为apply()函数,它接收一个区块头部切片作为输入,并统计这些区块头部所有的投票信息,最终更新当前Snapshot对象并输出。其精简后的代码如下所示:

    // apply creates a new authorization snapshot by applying the given headers to
    // the original one.
    func (s *Snapshot) apply(headers []*types.Header) (*Snapshot, error) {
    	// Allow passing in no headers for cleaner code
    	...
    	// Sanity check that the headers can be applied
    	...(保证区块头部数据是有序的)
    	// Iterate through the headers and create a new snapshot
    	snap := s.copy()
    	...
    	for i, header := range headers {
    		// Remove any votes on checkpoint blocks
    		number := header.Number.Uint64()
    		if number%s.config.Epoch == 0 {
    			snap.Votes = nil
    			snap.Tally = make(map[common.Address]Tally)
    		}
    		// Delete the oldest signer from the recent list to allow it signing again
    		if limit := uint64(len(snap.Signers)/2 + 1); number >= limit {
    			delete(snap.Recents, number-limit)
    		}
    		// Resolve the authorization key and check against signers
    		signer, err := ecrecover(header, s.sigcache)
    		if err != nil {
    			return nil, err
    		}
    		if _, ok := snap.Signers[signer]; !ok {
    			return nil, errUnauthorizedSigner
    		}
    		for _, recent := range snap.Recents {
    			if recent == signer {
    				return nil, errRecentlySigned
    			}
    		}
    		snap.Recents[number] = signer
    
    		// Header authorized, discard any previous votes from the signer
    		for i, vote := range snap.Votes {
    			if vote.Signer == signer && vote.Address == header.Coinbase {
    				// Uncast the vote from the cached tally
    				snap.uncast(vote.Address, vote.Authorize)
    
    				// Uncast the vote from the chronological list
    				snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
    				break // only one vote allowed
    			}
    		}
    		// Tally up the new vote from the signer
    		var authorize bool
    		switch {
    		case bytes.Equal(header.Nonce[:], nonceAuthVote):
    			authorize = true
    		case bytes.Equal(header.Nonce[:], nonceDropVote):
    			authorize = false
    		default:
    			return nil, errInvalidVote
    		}
    		if snap.cast(header.Coinbase, authorize) {
    			snap.Votes = append(snap.Votes, &Vote{
    				Signer:    signer,
    				Block:     number,
    				Address:   header.Coinbase,
    				Authorize: authorize,
    			})
    		}
    		// If the vote passed, update the list of signers
    		if tally := snap.Tally[header.Coinbase]; tally.Votes > len(snap.Signers)/2 {
    			if tally.Authorize {
    				snap.Signers[header.Coinbase] = struct{}{}
    			} else {
    				delete(snap.Signers, header.Coinbase)
    
    				// Signer list shrunk, delete any leftover recent caches
    				if limit := uint64(len(snap.Signers)/2 + 1); number >= limit {
    					delete(snap.Recents, number-limit)
    				}
    				// Discard any previous votes the deauthorized signer cast
    				for i := 0; i < len(snap.Votes); i++ {
    					if snap.Votes[i].Signer == header.Coinbase {
    						// Uncast the vote from the cached tally
    						snap.uncast(snap.Votes[i].Address, snap.Votes[i].Authorize)
    
    						// Uncast the vote from the chronological list
    						snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
    
    						i--
    					}
    				}
    			}
    			// Discard any previous votes around the just changed account
    			for i := 0; i < len(snap.Votes); i++ {
    				if snap.Votes[i].Address == header.Coinbase {
    					snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
    					i--
    				}
    			}
    			delete(snap.Tally, header.Coinbase)
    		}
    		// If we're taking too much time (ecrecover), notify the user once a while
    		...
    	}
    	...
    	snap.Number += uint64(len(headers))
    	snap.Hash = headers[len(headers)-1].Hash()
    
    	return snap, nil
    }
    

    函数执行的大体流程如下:

    1. 首先对传入区块头部切片数据的有效性进行检查,主要需要保证传入数据是有序的;
    2. 接着,遍历每个区块头部数据,如果当前块为CHECKPOINT,则清除所有的投票信息;
    3. 然后,从Recents字段中清除最早的记录,并获取当前区块的签名者地址(利用ecrecover()函数从区块头部恢复签名者地址,同时检查正确性),添加到Recents字段中,这个字段是为了保证在一段时间内已经签名过的签名者不能再次签署交易;
    4. 如果某一个签名者对一个人进行重复投票,则先清除之前的投票信息;
    5. 检查当前区块头部中的投票信息是否正确,如果正确则进行投票,投票过程在cast()函数中实现,它会首先检查投票的有效性,如果检查通过,则根据投票内容同时修改Votes以及Tally字段;
    6. 本轮投票结束后,如果被投票人累计的票数超过SIGNER_LIMIT,则需要对被投票人进行引入或者移出。
    7. 如果被投票人被引入,则更改Signers字段;如果被投票人被移出,则先修改Signers字段,再对被投票人投出的票进行撤回。最后对当前投给被投票人的票的信息也进行删除。同时,在被投票人被移出时,可能会导致SIGNER_LIMIT的变化,因此可能需要再次更新Recents字段。
      这里需要注意其中调用的两个函数,cast()和uncast(),它们的定义分别如下:
    // cast adds a new vote into the tally.
    func (s *Snapshot) cast(address common.Address, authorize bool) bool {
    	// Ensure the vote is meaningful
    	if !s.validVote(address, authorize) {
    		return false
    	}
    	// Cast the vote into an existing or new tally
    	if old, ok := s.Tally[address]; ok {
    		old.Votes++
    		s.Tally[address] = old
    	} else {
    		s.Tally[address] = Tally{Authorize: authorize, Votes: 1}
    	}
    	return true
    }
    
    // uncast removes a previously cast vote from the tally.
    func (s *Snapshot) uncast(address common.Address, authorize bool) bool {
    	// If there's no tally, it's a dangling vote, just drop
    	tally, ok := s.Tally[address]
    	if !ok {
    		return false
    	}
    	// Ensure we only revert counted votes
    	if tally.Authorize != authorize {
    		return false
    	}
    	// Otherwise revert the vote
    	if tally.Votes > 1 {
    		tally.Votes--
    		s.Tally[address] = tally
    	} else {
    		delete(s.Tally, address)
    	}
    	return true
    }
    

    其中,cast()函数还调用了validVote()函数,validVote()函数的作用是用来验证区块的有效性(添加不在签名者列表中的节点或者移除已经在签名者列表中的节点为有效票)。cast()和uncast()函数的作用是根据当前的投票来跟性Tally字段。

    共识部分(验证及打包区块)

    共识部分的相关代码位于go-ethereum/consensus/clique/clique.go文件。在介绍clique算法如何验证及打包区块之前,我们首先要介绍如下的数据结构:

    // Clique is the proof-of-authority consensus engine proposed to support the
    // Ethereum testnet following the Ropsten attacks.
    type Clique struct {
    	config *params.CliqueConfig // Consensus engine configuration parameters
    	db     ethdb.Database       // Database to store and retrieve snapshot checkpoints
    
    	recents    *lru.ARCCache // Snapshots for recent block to speed up reorgs
    	signatures *lru.ARCCache // Signatures of recent blocks to speed up mining
    
    	proposals map[common.Address]bool // Current list of proposals we are pushing
    
    	signer common.Address // Ethereum address of the signing key
    	signFn SignerFn       // Signer function to authorize hashes with
    	lock   sync.RWMutex   // Protects the signer fields
    
    	// The fields below are for testing only
    	fakeDiff bool // Skip difficulty verifications
    }
    

    这些字段的含义在注释中都有介绍,这里额外说明一下。其中,db字段是为了从本地磁盘中读取Snapshot或者向本地磁盘存储Snapshot需要用到的,recents字段是最近用到的区块的snapshot缓存,signatures字段是最近用到的区块的签名者地址缓存。在获取某个区块对应的snapshot或者签名者地址时,会首先查找缓存,如果有则直接从缓存中获取,否则才计算对应的内容。最后proposals字段为当前节点的所有投票内容,用户可以通过RPC接口添加自己期望的投票,于是,当轮到自己出块的回合,将会产生相应的区块,在将自己期望的投票放入到区块并广播到网络中。

    此外,我们需要观察理解其中的ecrecover()函数及snapshot()函数,它们的作用分别是获取一个区块的签名者或者snapshot。

    首先对于ecrecover()函数,其定义如下:

    // ecrecover extracts the Ethereum account address from a signed header.
    func ecrecover(header *types.Header, sigcache *lru.ARCCache) (common.Address, error) {
    	// If the signature's already cached, return that
    	hash := header.Hash()
    	if address, known := sigcache.Get(hash); known {
    		return address.(common.Address), nil
    	}
    	// Retrieve the signature from the header extra-data
    	if len(header.Extra) < extraSeal {
    		return common.Address{}, errMissingSignature
    	}
    	signature := header.Extra[len(header.Extra)-extraSeal:]
    
    	// Recover the public key and the Ethereum address
    	pubkey, err := crypto.Ecrecover(SealHash(header).Bytes(), signature)
    	if err != nil {
    		return common.Address{}, err
    	}
    	var signer common.Address
    	copy(signer[:], crypto.Keccak256(pubkey[1:])[12:])
    
    	sigcache.Add(hash, signer)
    	return signer, nil
    }
    

    它的执行步骤如下:

    1. 获取区块头部对应的哈希
    2. 根据哈希,首先在缓存(这个缓存就是Clique结构体中的signatures字段)中查找,若找到,则返回当前区块签名者的地址。
    3. 若没有找到,则提取区块头部中的Extra字段中的签名信息。
    4. 通过签名信息,恢复签名者的公钥,再通过公钥获取签名者的地址。

    对于snapshot()函数,它的主要代码如下:

    // snapshot retrieves the authorization snapshot at a given point in time.
    func (c *Clique) snapshot(chain consensus.ChainHeaderReader, number uint64, hash common.Hash, parents []*types.Header) (*Snapshot, error) {
    	// Search for a snapshot in memory or on disk for checkpoints
    	var (
    		headers []*types.Header
    		snap    *Snapshot
    	)
    	for snap == nil {
    		// If an in-memory snapshot was found, use that
    		if s, ok := c.recents.Get(hash); ok {
    			snap = s.(*Snapshot)
    			break
    		}
    		// If an on-disk checkpoint snapshot can be found, use that
    		if number%checkpointInterval == 0 {
    			if s, err := loadSnapshot(c.config, c.signatures, c.db, hash); err == nil {
    				...
    				snap = s
    				break
    			}
    		}
    		// If we're at the genesis, snapshot the initial state. Alternatively if we're
    		// at a checkpoint block without a parent (light client CHT), or we have piled
    		// up more headers than allowed to be reorged (chain reinit from a freezer),
    		// consider the checkpoint trusted and snapshot it.
    		if number == 0 || (number%c.config.Epoch == 0 && (len(headers) > params.FullImmutabilityThreshold || chain.GetHeaderByNumber(number-1) == nil)) {
    			checkpoint := chain.GetHeaderByNumber(number)
    			if checkpoint != nil {
    				hash := checkpoint.Hash()
    
    				signers := make([]common.Address, (len(checkpoint.Extra)-extraVanity-extraSeal)/common.AddressLength)
    				for i := 0; i < len(signers); i++ {
    					copy(signers[i][:], checkpoint.Extra[extraVanity+i*common.AddressLength:])
    				}
    				snap = newSnapshot(c.config, c.signatures, number, hash, signers)
    				if err := snap.store(c.db); err != nil {
    					return nil, err
    				}
    				...
    				break
    			}
    		}
    		// No snapshot for this header, gather the header and move backward
    		var header *types.Header
    		if len(parents) > 0 {
    			// If we have explicit parents, pick from there (enforced)
    			header = parents[len(parents)-1]
    			if header.Hash() != hash || header.Number.Uint64() != number {
    				return nil, consensus.ErrUnknownAncestor
    			}
    			parents = parents[:len(parents)-1]
    		} else {
    			// No explicit parents (or no more left), reach out to the database
    			header = chain.GetHeader(hash, number)
    			if header == nil {
    				return nil, consensus.ErrUnknownAncestor
    			}
    		}
    		headers = append(headers, header)
    		number, hash = number-1, header.ParentHash
    	}
    	// Previous snapshot found, apply any pending headers on top of it
    	for i := 0; i < len(headers)/2; i++ {
    		headers[i], headers[len(headers)-1-i] = headers[len(headers)-1-i], headers[i]
    	}
    	snap, err := snap.apply(headers)
    	if err != nil {
    		return nil, err
    	}
    	c.recents.Add(snap.Hash, snap)
    
    	// If we've generated a new checkpoint snapshot, save to disk
    	if snap.Number%checkpointInterval == 0 && len(headers) > 0 {
    		if err = snap.store(c.db); err != nil {
    			return nil, err
    		}
    		...
    	}
    	return snap, err
    }
    

    该函数的执行流程如下:

    1. 根据区块号,区块哈希以及该区块的父母区块的头部信息,在循环中构建snapshot对象,此时有四种情况
      • 情况一,Clique的字段recents中已经存储该区块对应的snapshot对象,则直接从中获取并返回
      • 情况二,该区块正好处于checkpointInterval的周期上(前面提到过,算法会每隔checkpointInterval将snapshot记录在磁盘上),并且磁盘中保存有相应的snapshot,则从磁盘中读取并返回
      • 情况三,该区块为CHECKPOINT,那么只需要从区块的Extra字段中获取当前的签名者列表,便能直接构建snapshot
      • 情况四,如果上述情况都不成立,只能查找该区块前一个区块的snapshot是否存在。
    2. 循环结束后,我们知道,如果获取的snapshot是由第四种情况构建的。那么,它就不是当前区块的snapshot,于是就需要利用它后续的所有区块头部信息,对获取的snapshot进行更新,直到更新到当前区块为止,于是便获得了当前区块的snapshot。
    3. 最后,需要将获取的snapshot保存在缓存中,以便下次使用,同时,也根据条件判断,来确定是否将snapshot保存在磁盘中。

    验证区块

    对区块的验证是为了达成共识,只有通过验证的区块才能被节点接收,也只有这样的区块才能在网络中传播,验证区块的主要函数为VerifySeal(),其主要代码如下:

    // VerifySeal implements consensus.Engine, checking whether the signature contained
    // in the header satisfies the consensus protocol requirements.
    func (c *Clique) VerifySeal(chain consensus.ChainHeaderReader, header *types.Header) error {
    	return c.verifySeal(chain, header, nil)
    }
    
    // verifySeal checks whether the signature contained in the header satisfies the
    // consensus protocol requirements. The method accepts an optional list of parent
    // headers that aren't yet part of the local blockchain to generate the snapshots
    // from.
    func (c *Clique) verifySeal(chain consensus.ChainHeaderReader, header *types.Header, parents []*types.Header) error {
    	// Verifying the genesis block is not supported
    	number := header.Number.Uint64()
    	if number == 0 {
    		return errUnknownBlock
    	}
    	// Retrieve the snapshot needed to verify this header and cache it
    	snap, err := c.snapshot(chain, number-1, header.ParentHash, parents)
    	if err != nil {
    		return err
    	}
    
    	// Resolve the authorization key and check against signers
    	signer, err := ecrecover(header, c.signatures)
    	if err != nil {
    		return err
    	}
    	if _, ok := snap.Signers[signer]; !ok {
    		return errUnauthorizedSigner
    	}
    	for seen, recent := range snap.Recents {
    		if recent == signer {
    			// Signer is among recents, only fail if the current block doesn't shift it out
    			if limit := uint64(len(snap.Signers)/2 + 1); seen > number-limit {
    				return errRecentlySigned
    			}
    		}
    	}
    	// Ensure that the difficulty corresponds to the turn-ness of the signer
    	if !c.fakeDiff {
    		inturn := snap.inturn(header.Number.Uint64(), signer)
    		if inturn && header.Difficulty.Cmp(diffInTurn) != 0 {
    			return errWrongDifficulty
    		}
    		if !inturn && header.Difficulty.Cmp(diffNoTurn) != 0 {
    			return errWrongDifficulty
    		}
    	}
    	return nil
    }
    

    对区块验证的主要内容如下:

    1. 该区块的签名者处于当前的签名者列表中;
    2. 该区块的签名者最近(SIGNER_LIMIT之内)未进行过签名;
    3. 该区块的Difficulty字段没有造假。

    对于一个区块还有其他的一些验证,其实现在函数VerifyHeader()中,包括对区块的时间戳验证,Nonce、Extra等字段的构造规范验证等等,这里就不过多介绍。

    打包区块

    当轮到某个签名者出块时,该签名者调用Seal()函数打包一个区块,并发送到网络中。这个函数虽然代码比较长,但实现的主要功能比较简单,这里就不给出函数对应的源码。但它实现的主要功能包括如下几点:

    1. 验证当前节点是否在签名者列表当中(是否有权签署区块)
    2. 验证当前节点最近是否已经签署过区块
    3. 如果已经签署过区块,则会等待一段时间,这个等待时间有具体的计算公式
    4. 如果此时可以签名,则利用当前账户对区块头部信息进行签名并放入Extra字段中。

    在调用Seal()函数之前,需要调用Prepare()函数,这个函数的主要代码如下:

    // Prepare implements consensus.Engine, preparing all the consensus fields of the
    // header for running the transactions on top.
    func (c *Clique) Prepare(chain consensus.ChainHeaderReader, header *types.Header) error {
    	// If the block isn't a checkpoint, cast a random vote (good enough for now)
    	header.Coinbase = common.Address{}
    	header.Nonce = types.BlockNonce{}
    
    	number := header.Number.Uint64()
    	// Assemble the voting snapshot to check which votes make sense
    	snap, err := c.snapshot(chain, number-1, header.ParentHash, nil)
    	if err != nil {
    		return err
    	}
    	if number%c.config.Epoch != 0 {
    		c.lock.RLock()
    
    		// Gather all the proposals that make sense voting on
    		addresses := make([]common.Address, 0, len(c.proposals))
    		for address, authorize := range c.proposals {
    			if snap.validVote(address, authorize) {
    				addresses = append(addresses, address)
    			}
    		}
    		// If there's pending proposals, cast a vote on them
    		if len(addresses) > 0 {
    			header.Coinbase = addresses[rand.Intn(len(addresses))]
    			if c.proposals[header.Coinbase] {
    				copy(header.Nonce[:], nonceAuthVote)
    			} else {
    				copy(header.Nonce[:], nonceDropVote)
    			}
    		}
    		c.lock.RUnlock()
    	}
    	// Set the correct difficulty
    	header.Difficulty = calcDifficulty(snap, c.signer)
    
    	// Ensure the extra data has all its components
    	if len(header.Extra) < extraVanity {
    		header.Extra = append(header.Extra, bytes.Repeat([]byte{0x00}, extraVanity-len(header.Extra))...)
    	}
    	header.Extra = header.Extra[:extraVanity]
    
    	if number%c.config.Epoch == 0 {
    		for _, signer := range snap.signers() {
    			header.Extra = append(header.Extra, signer[:]...)
    		}
    	}
    	header.Extra = append(header.Extra, make([]byte, extraSeal)...)
    
    	// Mix digest is reserved for now, set to empty
    	header.MixDigest = common.Hash{}
    
    	// Ensure the timestamp has the correct delay
    	parent := chain.GetHeader(header.ParentHash, number-1)
    	if parent == nil {
    		return consensus.ErrUnknownAncestor
    	}
    	header.Time = parent.Time + c.config.Period
    	if header.Time < uint64(time.Now().Unix()) {
    		header.Time = uint64(time.Now().Unix())
    	}
    	return nil
    }
    

    它的主要作用便是对将要签名区块头部中的各个字段进行构造(除了签名是在Seal()函数中完成的),其中,被投票人的地址是从Clique结构体的proposals字段中随机获取一个。

    其他共识

    还有一些共识机制,在以太坊中尚未给出具体实现,但都是应用比较广泛地共识算法。下面归纳了一些常用的共识算法:

    • POW,工作量证明
    • POS,权益证明
    • DPOS,授权POS
    • POA,权威证明
    • PBFT,实用拜占庭容错算法
    • DBFT,授权拜占庭容错算法

    具体说明可以看这里

    参考

    [1] 以太坊源码解析:共识算法之clique
    [2] 以太坊源码解析:共识算法之ethash(理论介绍篇)
    [3] 以太坊源码解析:共识算法之ethash(源码篇)

    更多相关内容
  • 以太坊挖矿算法和难度调整(四)

    千次阅读 2022-01-09 18:57:31
    以太坊挖矿算法及其难度调整.,

    以太坊 挖矿算法

    对于基于工作量证明的系统来说,挖矿是保障区块链安全的重要手段,有时候说Block chain is secured by mining,比特币里面的挖矿算法总的来说是比较成功的,经受了时间的检验,到目前为止,没有人发现,也没有什么大的漏洞。

    bug bounty:bounty(赏金)

    美国电影有一个叫bounty hunter(赏金猎人),专门去抓那些政府悬赏捉拿的逃犯

    bug bounty:有的公司悬赏来找软件中的漏洞,如果能找到软件中的安全漏洞就可以得到一笔赏金。

    比特币的挖矿算法是一个天然的bug bounty,如果你能找到里面的漏洞,或者是某一个挖矿的捷径就能取得很大的利益。但是到目前为止还没有人发现有什么捷径可走,所以比特币的挖矿算法总的来说是比较成功的,是经受住时间检验的,但是比特币的挖矿算法也有一些值得改进得地方,其中有一个保守争议得问题就是挖矿设备得专业化,有普通的计算机挖不倒矿,只能用专门的设备,专用的ASIC芯片来挖矿,那么很多人认为这种去中心化的做法和去中心化的理念是背道而驰的,也跟比特币的设计初衷相违背的,中本聪最早的一篇论文,提出One cpu,one vote,理想状况下,应该让普通老百姓也能参与挖矿过程,就用家里的桌面机,笔记本电脑,甚至手机来挖矿,这样也更安全,因为算力分散之后,有恶意的攻击者想要聚集到51%的算力发动攻击,这个难度就会大得多。所以比特币之后出现的加密货币包括以太坊设计mining puzzle的时候,一个目标就是要做到ASIC resistance,那么怎么才能设计出对ASIC芯片不友好的mining puzzle呢?

    一个常用的做法就是增加mining puzzle对内存访问的需求,也就是所谓的memory hard mining puzzle,ASIC芯片相对于普通计算机而言,主要优势是算力强,但是在内存访问的性能上没有那么大的优势,同样的价格买一个ASIC矿机和买一个普通的计算机,这个ASIC矿机的计算能力是普通计算机的几千倍,但是内存访问方面的性能差距远远没有这么大,所以能设计出一个对内存要求很高的puzzle,就能起到遏制芯片的作用。

    • 怎么设计呢?

    一个早期的例子是莱特币LiteCoin,曾经是市值仅次于比特币的第二大加密货币,他用的Puzzle是基于Scrypt,这个是对内存要求很高的哈希函数,以前用于计算机安全领域,跟密码相关,那么他的具体设计思想是说,开一个很大的数组,然后按照顺序填充一些伪随机数,比如说有一个种子节点,seed的值通过一些运算,算出一个数来,填在第一个位置,然后后面每个位置都是前一个位置的值取哈希得到的,伪随机数是说取哈希值后的值你也不知道,看上去就是乱七八糟的数一样,就好像随机数,但我们不可能真的用随机数,真的用随机数没法验证。填充完之后,里面的数值是有前后依赖关系的,是从第一个数依次算出来的,然后需要求解这个puzzle的时候,按照伪随机数的顺序从数组当中读取一些数,每次读取的位置跟前一个数相关,比如说要解puzzle了,一开始读取A这个位置的数,把A位置的值读取出来之后,根据他的取值进行一些运算,算出下次要读取的位置,比如说是B这个位置,然后把B这个位置的数读出来,再进行一些运算得到下一个读取的位置,比如说C这个位置,这个也是一种伪随机数的顺序,因为经过哈希运算之后得到下一个读取的位置。
    image-20210813211553593

    这样做的好处:
    如果这个数组开的足够大的时候,挖矿的矿工就是memory hard,因为如果不保存数组,那么挖矿的计算复杂度会大幅度上升,比如说,在读取数组里面这些数的时候,你没有保存数组,那要怎么办,比如说求解puzzle的时候,一开始在A这个位置,如果没有数组的话,还得从第一个数,依次算出这个值,然后要读取第二个位置的数,这些没有存起来,再算一遍算到B位置的值,下面是C,也一样,要算到C位置的值,这个计算复杂度会大幅度上升。

    所以要想高效地挖矿,这个内存区域是需要保存的,有的矿工可能保存一部分内存区的内容,比如说,这个数组当中只保留奇数位置地元素,偶数位置地元素就不存了,这样数组可以少一半,那用到偶数位置的数怎么办呢,要根据另外一半去算一下,计算复杂度会提高一点,但是内存量可以减小一半,管它叫做time-memory trade off。

    这个设计的核心思想是不能像比特币那样主要进行哈希运算,比特币其实也不是取一次哈希,他是取两次哈希,但这个不够,要增加他的运算过程中对内存访问的需求,要设计一个对ASIC芯片不友好的,对普通计算机能参与的。设计的任务更像是普通计算机干的事情,而不是像一个挖矿专用的ASIC芯片干的事情,普通计算机内存很大,就要利用这个特性,设计puzzle对资源的需求,特别像是普通计算机对资源的配备比例。

    这个puzzle好的地方:对于矿工挖矿的时候是memory hard。

    坏的地方:对轻节点来说也是memory hard。

    前面讲过设计puzzle的一个原则:difficult to solve,but easy to verify,这个问题就在于验证这个puzzle需要的内存区域跟求解这个puzzle需要的区域几乎是一样大的,轻节点验证的时候也得保存这个数组,要不然他的计算复杂度也是大幅度提高,对于scrypt早期计算机的安全领域,这个密码方面的话他不是一个问题,他没有轻节点验证这个问题,但对于我们这个来说是不行的,这样造成一个结果就是莱特币在真正使用的时候,这个内存区域不敢设置的太大,比如说你设一个1G的数组,这对于计算机来说是不大的,但是如果是一个手机上的app,1G的内存可能就太大了,因为这个原因,实际莱特币在使用的时候,这个数组只有128Ks,这个是非常小的,连1M都不到,就是为了照顾轻节点,那么最后的效果怎么样呢

    当初莱特币在发行的时候,目标不仅仅是ASIC resistance,还是GPU resistance,就是挖矿最好连GPU都不要用,都用普通的CPU挖矿就行了,结果后来就出现GPU挖矿的,再后来就出现用ASIC芯片挖矿的,实践证明莱特币要求的128k内存不足以对ASIC芯片的生产和设计带来实际上的障碍,所以从这一点来说,莱特币的设计目标没有达到,但是他早期宣传的设计目标对于解决能启动问题是很有帮助的,任何一个加密货币,都存在能启动问题,包括比特币,一开始的时候,没有人知道这个加密货币,你就发行一个货币,也没有人理你,那怎么办呢,没有人参与,这是一个问题,而且对于基于工作量证明的加密货币来说,挖矿人太少是不安全的,因为发动恶意攻击难度太低,比特币早期也是不安全的,一开始只有中本聪一个人在用,后来变成少数几个人在挖矿,那个时候,如果想对比特币发动恶意攻击是很容易的,那么比特币是怎么解决这个能启动的问题呢,现在谁也说不清楚了,但总的来说是一个循坏迭代的过程,中本聪宣传的多了,对比特币感兴趣的人就多了,然后参与挖矿人就多了,变得更安全,价值也提高了,然后对比特币感兴趣的人就更多了,挖矿的人也更多了,然后比特币变得更安全了,价值就更进一步提高了,形成一个良性循坏。莱特币虽然没有达到当初的设计目标,但是他早期的宣传,更民主,让更多人参与的理念对于聚集人气来说是很重要的,所以莱特币一直到现在也是一个比较主流的加密货币,除了这个mining puzzle之外,莱特币跟比特币的另一个区别是来特比的出块速度是比特币的4倍,他的出块间隔是两分半,而不是十分钟,除此之外,这两种加密货币基本上是一样的。

    以太坊也是用一种memory hard mining puzzle,但是在设计上,跟莱特币有很大的不同

    以太坊用的是两个数据集,一大一小,小的是16M cache,大的数据集是一个1G dataset,DAG,这1G的数据集是从16M的cache生成出来的,为什么要设计成一大一小的两个数据集呢,就是为了便于验证,轻节点只要保存16M cache就行了,只有需要挖矿的矿工才需要保存1G的dataset。

    基本思想:
    小的数据集的生成方式跟前面讲的数组的生成方式是比较类似的,首先从一个种子节点seed,进行一些运算,算出数组的第一个元素,然后依次取哈希,第一个元素取哈希得到第二个元素,第二个元素取哈希得到第三个元素,这样从前往后,把这个数组从前往后,填充一些伪随机数得到一个cache,下面和莱特币就不一样了,莱特币是直接从数组当中按照伪随机数的顺序读取一些数,然后进行运算,以太坊是要先生成一个更大的数组,这里没有按比例画,就这个大数组应该比下面的小数组要大得多,下图看就大了一点,因为黑板画不下了,就意思意思,而且小的cache和大的dataset都是定期增长的,每隔一段时间,大小要增大,因为计算机的内存容量也是定期增长的,比如说这个大的dataset涨到了2.5G,就已经不是一个G了,那大的dataset是怎么生成的呢,他的每个元素小的cache里按照伪随机数的顺序读取一些元素,方法和刚才讲的莱特币里面求解puzzle的过程是类似的,比如说,第一次读取A位置的元素,读取完之后,对当前的哈希值进行一些更新迭代,算出下一个要读取的位置,比如说B这个位置,然后把B位置的数再进行一些哈希值的更新,算出C这个位置,那么从这个cache里面这么来回读,一共读256次,读256个数,最后算出来一个数放在大的dataset的第一个元素,然后第二个元素也是一样的,dataset的每个元素都是从这个cache里面按照伪随机数的顺序,不断进行迭代更新,最后得到一个值存在里面,然后求解puzzle的时候,用的是大数据集中的数,这个cache是不用的,按照伪随机数的顺序在大的数据集中读取128个数,就是一开始的时候根据区块的块头,包括里面的nonce值算出一个初始的哈希,根据这个哈希,映射到大数据集里面的某个位置,把这个数读取出来,然后进行一些运算,算出下一个要读取的位置,比如说又在大数据集里面的另一个位置,又把这个数读取出来,这里有一个区别:他每次读取的时候除了计算出这个元素的位置之外,还要把相邻元素也要读取出来,这个例子当中每次读取的时候是读取两个相邻元素,这样循环64次,每次读两个元素,所以一共是符合难度要求128个数,最后算出一个哈希值来,跟挖矿难度的目标域值比较是不是符合难度要求,如果不是,把block header 里面的nonce替换一下,换另外一个nonce,因为换了nonce之后,第一次算的那个哈希值就变了,然后重复这个过程,根据这个哈希值找到数组中的元素,读取两个相邻的元素,反复循环64次,再得到一个哈希值,然后再去比较。
    image-20210813211608230

    上面讲的比较抽象,下面是写的一个伪代码,没有直接用以太坊中的源代码,这个伪代码省略了源代码中的一些实现的细节,更有利于理解。


    ethash算法伪代码

    第一步首先生成16M cache,cache中每个元素都是64个字节的哈希值,生成的方法与莱特币类似,第一个元素是种子的哈希,就是这个seed的哈希,后面每个元素是前一个的哈希,这个哈希的内容每隔3万个区块会变化一次,这个seed每隔3万个区块会发生变化,然后重新生成cache中的内容,同时cache的容量要增加原始大小的1/128,也就是16M的1/128=128K。
    image-20210813211618636

    第二步是从这个cache生成1G的大数据集,这个函数的功能是通过cache来生成dataset中的第i个元素,基本思想是按照伪随机数的顺序读取cache中的256个数,每次读取的位置是由上一个位置的数值经过计算得到的,这里用的两个函数get_int_from_item和make_item,是自己定义的,源代码中是没有的,把源代码中一些相关的内容总结成了这两个函数,可以避免源代码中不是很重要的细节,这个get_int_from_item函数就是用当前算出来的哈希值求出下一个要读取的位置,然后make_item函数用cache中这个位置的数和当前的哈希值计算出下一个哈希值,这样迭代256轮,最后得到一个64字节的哈希值,作为大数据集中的第i个元素。

    image-20210813211633339

    这个calc_dataset是生成整个1G数据集的过程,就是不断调用前的函数来依次生成大数据集中的每个元素

    image-20210813211643556

    这一页的两个函数,分别是矿工用来挖矿的函数,和轻节点用来验证的函数,先看一下上面这个函数,这个矿工用来挖矿的函数,他有四个参数,header是当前要生成的区块的块头,以太坊和比特币一样,挖矿只用到块头的信息,这样设计的原因,是轻节点只下载块头,就可以验证这个区块是否符合挖矿的难度要求,第二个参数nonce就是当前尝试的nonce值,以太坊就像比特币一样,挖矿的时候,也是要尝试大量的nonce才能找到一个符合要求的,第三个参数full_size是大数据集中元素的个数,元素的个数每3万个区块会增加一次,增加原始大小的1/128也就是1G的1/128=8M,最后参数dataset就是前面生成的大数据集,挖矿的过程是这样的,首先根据块头的信息,和当前Nonce算出一个初始哈希值,然后要经过64轮的循环,每一轮循环读取大数据集中两个相邻的数,读取的位置是由当前哈希值计算出来的,然后再根据这个位置上的数值来更新当前的哈希值,这跟前面生成大数据集的方法是类似的,循环64次,最后返回一个哈希值,跟挖矿难度目标域值相比较。

    这里提个小问题,每次读取大数据集中两个相邻位置的哈希值,这两个哈希值有什么联系吗?

    其实是没有联系的,他们虽然位置相邻,但是生成的过程是独立的,每个都是由前面那个16M的cache中的256个数生成的,而且256个数的位置是按照伪随机数的顺序产生的,这个是构造大数据集的一个特点,每个元素独立生成,这才给轻节点的验证提供了方便,所以每次读取的相邻两个位置的哈希值是没有什么联系的。

    下面这个函数是轻节点用来验证的函数,也是有四个参数,但是含义跟上面那个矿工用的函数有所不同,轻节点不挖矿,当他收到某个矿工发的区块的时候,这里用来验证的函数的第一个参数header是这个区块的块头,第二参数是包含在这个块头里的Nonce,是发布这个区块的矿工选好的,轻节点的任务是验证这个nonce是否符合要求,验证用的是16M的cache,也就是最后的参数cache,注意,第三个参数full_size仍然是大数据集的元素个数,跟上面那个挖矿的那个full_size含义是一样的,并不是cache中的元素个数,验证的过程也是64轮循环,看上去与挖矿的过程类似,只有一个地方有区别,比较这一页的上下两个函数,有什么区别?

    每次需要从大数据集中读取元素的时候,因为轻节点没有保留大数据集,所以要从cache中重新生成其他地方的代码逻辑是一样的,每次从当前的哈希值算出要读取的元素的位置,这个位置是指在在大数据集中的位置,但是轻节点并没有这个大数据集,所以要从cache中生成大数据集中这个位置的元素,我们前面说过大数据集中每个元素都可以独立生成出来。
    image-20210813223417890

    最后这个函数,是矿工挖矿的主循环,其实是不断尝试nonce的过程,这里的target就是挖矿的难度目标,跟比特币类似,也是可以动态调整的,nonce的可能取值是从0-2的64次方,对每个nonce用前面讲的那个函数算出一个哈希值,看看是不是小于难度目标,如果不行的话,就再试下一个nonce。

    image-20210813223432497

    最后这一页是前面讲过的所有函数的一个汇总,同时解释了为什么轻节点可以只保存cache,而矿工要保存整个大数据集。其实轻节点做一次验证的计算量也不算少,同样要经过64轮循环,每次循环用到大数据集中的两个数,所以是128个数,每个数是从cache里的256个数计算得到的,跟比特币相比,以太坊中验证一个nonce的计算量要大很多,但是仍然在可以接受的范围内,相比之下,如果矿工每次都这么折腾的话,代价就太大了,因为要尝试的nonce就太多了。

    image-20210813223449656


    那以太坊设计的这个puzzle实际效果怎么样呢?

    到目前为止,以太坊挖矿主要还是以GPU为主,用ASIC矿机的很少,所以从这一点来说,他比莱特币来说要成功,起到了ASIC resistance的作用,这个跟以太坊的挖矿算法需要的大内存是很有关系的,这个挖矿算法就是ethash,这个起的很有意思,前三个字母eth是以太坊的代码,后面这个hash,h用了两遍,矿工挖矿需要1G的内存,跟莱特币的128K比,差了有八千多倍,即使是16M的cache跟128K比,也要大了一百多倍,所以这个差距是很大的,而且还是按照这两个数据集的最初的大小算的,因为定期会增长嘛,如果按照现在这个2.5G差距就更大了,以太坊没有出现ASIC矿机还有另外一个原因,以太坊从很早就计划要从工作量证明转移到权益证明,所谓的PoW->PoS(Proof of Stake),所谓的权益证明,就是按照所占的权益进行投票来形成共识,就不用挖矿了,权益证明是不挖矿,就类似于股份公司按照股票多少来进行投票,这个对于ASIC矿机的厂商来说是个威胁,因为ASIC芯片的研发周期是很长的,一款芯片从设计研发流片到最后生产出来,一年的周期就已经算是很快的了,而且研发的成本也很高,将来以太坊转入权益证明之后,就不挖矿,那些投入的研发费用就白费了,其实到目前为止,以太坊是基于工作量证明,以太坊很早就说要转入权益证明,但是转移的时间点一再往后推迟,到现在也没转过来,但是他不停的宣称要这么做,所以要想达到ASIC resistance一个简单的办法就是不断地吓唬大家:大家注意哦,下面要搞权益证明就不挖矿了,所以你就不要设计ASIC矿机了,你设计出来到时候也没用了,因为要设计一年嘛,一年以后,我们就不挖矿了。

    等过了一年,不行,还是得继续挖矿,那怎么办呢,再吓唬一次:我们真的再挖一年,然后就再也不挖了,所以你还是不要再设计了。

    从历史看,以太坊成为一个主流的加密货币,其实就是最近两年的事情(2018),以前市值很小的时候,没有人会去设计ASIC芯片,因为划不来啊,无利可图,等到市值上来之后呢,你这么吓唬他几次,就能起到ASIC resistance的作用,这也是另外一方面的原因。

    关于以太坊的挖矿还有一个要说明的

    以太坊中采用了预挖矿,叫pre-mining,所谓预挖矿并不是说真的去挖矿,而是说,在当初发行货币的时候,预留一部分货币给以太坊的开发者,有点像创业公司会留一部分股票给创始人和早期员工一样,将来这个加密货币成功了的话,这些预留的币就变得是很值钱了。

    像以太坊的早期开发者,现在就都很有钱,比北大教授要有钱多了,跟这个比特币相比呢,比特币就没有采用pre-mining的模式,所有的比特币都是挖出来的,只不过早期的时候,挖矿的难度,要容易的多,与pre-mining相关的一个概念叫pre-sale(就是把pre-mining预留的那些币通过出售的方法来换取一些资产用于加密货币的开发工作),有点类似于众筹,如果你看好这个加密货币的未来,可以在pre-sale的时候买入,将来这个加密货币成功之后呢,同样可以赚很大一笔钱

    下面看一下以太坊上的一些统计数据

    下面这个图显示了以太坊中货币供应量的分布情况,总共有大约一亿个以太币,每个以太币的市场价格是五百多美元,这里的数据是以前的,现在以太币的价格没有了解,整个以太坊的市值大概是五百多亿美元,下面这个图显示了这一亿的来源,绝大部分是通过pre-mining方法产生的,这个蓝色部分Genesis是指创世纪块中就已经包含了这些以太币,上线以后,再挖出来的以太币中Block Rewrad占了绝大多数,Uncle Reward就是前面讲的叔父区块得到的奖励只占很少一部分。有没有觉得毁三观,挖矿挖的再努力,关键还是不能输在起跑线上。
    image-20210813223510176

    下图显示的是最大的以太坊矿池所占的算力比重,可以看出挖矿集中化的程度也是很高的,尤其是最大的几个矿池所占的比例很高,与比特币的情况类似

    image-20210813223520824

    下图显示的是以太币的价格随时间变化的情况,可以看到在以太坊早期的那几年价格基本没怎么涨,真正的大涨是2017年,这一年的价格涨得非常猛,直到2018年初达到了顶峰,然后开始走下坡路,这个图显示的是以太坊的市值,叫Market Capitalization,这个跟价格的走势基本上是符合的

    image-20210813223534420

    下图显示的是以太坊HashRate的变化情况,HashRate是指系统中所有的矿工加在一起,每秒钟计算的哈希次数,可以看到HashRate从总体来说是处于上升趋势的,而且也是从2017年开始大幅度上升的,2018年以太币的价格下跌了不少,HashRate总体上趋于平稳,并没有出现明显的下降,不同的货币入宫采用的mining puzzle不一样的话,那么它们的HashRate是不可比的,比特币和以太坊的HashRate就不能直接比较,因为以太坊中尝试一个nonce的工作量要比比特币大得多。
    image-20210813223546195

    这篇文章讲的是挖矿的算法设计要尽可能让通用的设备也能参加,参加的人越多,挖矿的过程越民主,那么区块链就越安全,这也是为什么莱特币,以太坊要设计memory hard mining puzzle,但是也有一些人有不同的观点,认为让通用设备参加反而是不安全的,像比特币那样只能用专门的ASIC芯片挖矿才是更安全的,假设要对比特币系统发动攻击,需要投入大量资金买入ASIC矿机,才能聚集到发动攻击所需要的算力,而这些矿机除了挖矿之外,干不了别的任何事情,而且是为某一个加密货币设计的加密芯片,只能挖这一种加密货币,像比特币的ASIC芯片去挖莱特币就不行,所以呢,发动这个攻击的成本是很高的,早期需要投入大量的硬件资源,而且一旦攻击成功比特币系统的安全性被证明存在安全问题,大家对比特币的信心会大幅度下跌,然后比特币的价格也会跳水,这样早期投入的硬件成本就收不回来了,因为比特币本身就不值钱了,你买的那些比特币的矿机当然也不值钱了。相反如果让通用设别参与挖矿的话,发动攻击的成本就大幅度下降。所以有些人认为让通用设备参与挖矿是不安全的,让ASIC矿机一统天下才是安全的

    挖矿难度调整

    比特币是每隔2016个区块会调整一下挖矿难度,目的是维持出块时间在十分钟左右,以太坊是每个区块都有可能调整挖矿难度,调整的方法也比较复杂也改过好几个版本,网上的一些资料,像论坛,博客对这些介绍也有很多不一致的地方包括以太坊的黄皮书和实际代码也有一些出入,我们遵循以代码为准的原则,从以太坊的代码当中找到了这部分的内容,把他们总结了一个ppt。

    image-20210813224338610

    这是难度调整的公式,这里的H是指当前这个区块,Hi是这个区块的序号,D(H)是这个区块当前的难度,那么这个难度调整的公式有两部分,这个max括号里的是第一部分,管它叫基础部分,目的是为了维持出块时间大概在十五秒左右,后面跟的是第二部分,也称为难度炸弹,主要是为了向权益证明过渡,将来的以太坊想把共识机制从工作量证明逐步转入权益证明。

    第一部分调整的方法是在父区块的难度基础上,加上一些自调整的部分,这个P(H)就是红框里的父区块的难度

    所谓的父区块就是当前区块链的最后一个区块,对于我们正在挖的这个区块来说,他是这个区块的父区块。

    第一部分的难度调整有一个下限,就是这里的D0,131072,这一部分无论你去怎么调整,最小不能低于这个难度,这是为了保证挖矿有一个最低的难度。

    image-20210813224411745

    后面的红框里的就是难度炸弹部分

    image-20210813224423303

    先看一下第一部分,这个x是调整的力度,是父区块的难度除以2048,所以调整难度时,无论上调下调,都是按照这个力度的整数倍进行调整的,按照父区块的难度的1/2048作为调整的一个单位。

    image-20210813224433619

    下面那个奇怪的符号是y-后面的一项,奇怪符号的取值跟两个因素有关,一个是出块时间,另外一个是有没有叔父区块,就是父区块有没有叔父区块,那么为什么要跟叔父区块相关呢?
    因为如果是当前区块的最后一个区块,它包含有一个叔父区块的话,这个时候,系统中的货币总供应量是增加的,因为叔父区块要得到出块奖励,那么包含叔父区块的这个父区块也有得到一定的奖励,所以这两个合在一起就会使货币的总供应量增加,那么他为了维持系统中的总供应量的稳定,一种平衡,所以挖这个区块的难度就要提高一个单元,
    image-20210813224448052

    后面这个-99是说难度调整系数部分有一个下限,Max前面这部分有可能是正的,有可能是负的,如果是负的话,那么难度要往下调,最多一次性只能调整99个单元,每个单位是父区块难度的1/2048,所以一次性下调难度最多是99/2048,

    image-20210813224457860

    仔细看一下这个公式,这个y就是我们说的取决于有没有叔父区块,有叔父区块的话,y=2,没有叔父区块的话,y=1,那么不论是哪种情况,都是常数,所以都是常数减去后面这一项,但如果后面这一项比前面这个常数大的话,减出来是个负数,说明这个难度是要下调的。相反,如果后面那一项比前面那一项要小的话,减出来就是个正数,说明难度要上调。
    image-20210813224510962

    看几个具体的例子,这个Hs是当前区块的时间戳

    image-20210813224521461

    P(H)是父区块的时间戳,这两项相减,就是当前区块的出块间隔,这个出块间隔除以9,然后向下取整

    image-20210813224531182

    为什么要这么设计?

    比如说,我们当前这个区块的出块时间是在18s之间,这个时候,后面往下取整的那一部分算出来是0对吧,那么y-0=y,假设没有叔父区块,那么y是等于1的,那么这整个就是等于是1,说明这种情况下,难度要上调一个单位,这个也是可以的,因为我们希望保证稳定的出块时间是在15秒,现在的出块时间变成了18s,说明出块速度有点太快了,把难度上调一个单位维持下平衡。相反如果出块时间是在917s之间,后面是1,前面也是1,1-1=0,说明这个时候出块时间是符合要求的,希望是15s,他是917s之间,这个时候可以不用调,光考虑基础部分,不考虑难度炸弹的话,就是基本上可以不用调。最后一项,如果出块时间是在18~26s之间,那么后面那项算出来是2,变成了1-2=-1,说明难度要下调一个单位,如果出块时间更长呢,比26s更长,那么下调的幅度也会更大

    image-20210813224603500

    但是不要忘了,上面那个公式里max的第二项有一个-99,如果单次的出块时间非常非常长,你可能前面算出来是个负的很厉害的数,但是你一次性下调也不能超过99个单位,这是为了防止一些系统中出现的异常情况,像一些黑天鹅事件,正常情况下,不能出现这个幅度的下调,前面又讲完了第一部分,基础部分。

    image-20210813224618129

    下面讲难度炸弹,他的初衷是这样的,以太坊的共识机制要从工作量证明逐步转入权益证明,而权益证明是不挖矿的,这就带来一个问题,那些已经在挖矿设备上投入大量资金的矿工会不会联合起来抵制这个转换。比如说,我已经花了好多钱买这个矿机,现在被告知要搞权益证明了,那我这些挖矿设备都没用了,那我肯定有意见,所以以太坊就担心大家不愿意转入权益证明,本来从工作量证明转入权益证明就是要经过硬分叉来实现,相当于你改了这个共识协议了,如果因为这些挖矿设备有些人不原意转过来,造成社区的分裂,可能出现的情况是,以太坊可能出现两条平行的链,那怎么办呢,为了避免这种情况,所以以太坊在设计这个难度调整公式的时候就加了一个难度炸弹,看一下难度炸弹设计的特点

    当初设计这个难度炸弹的时候,没有第二行,没有减去三百万这一行,第一行直接用的就是Hi,当前区块的序号,没有Hi一撇这一项。

    当前的区块号除以10万,向下取整,然后作为2的指数,也就是说,难度炸弹这部分的取值,是从指数形式增长的,那么指数函数的特点是什么,早期的时候,以太坊刚刚上线不久的时候,区块号都比较小,所以难度炸弹这部分算出来的值是很小的,基本上可以忽略不计,那么难度调整主要还是由刚才讲完的第一部分,基础部分来决定的,或者是由系统中的出块时间来决定的,然而随着时间的推移,区块号变得越来越大,这个时候难度炸弹的威力开始显现出来,我们知道指数函数增长到后期,速度是非常恐怖的,所以当初设计的思想是等到这个难度炸弹的威力开始发挥出来的时候,也正是从以太坊需要从工作量证明转入权益证明的时候,那个时候因为挖矿变得越来越难了,所以大家也就原意转入权益证明了,因为如果不转的话,要挖出矿来,就太费劲了,这是当初设计以太坊时候的如意算盘,但实际情况,基于权益证明的共识机制实际设计出来有很多问题要解决,远远没有当初想象的那么顺利,这样造成的结果就是,转入权益证明的时间点被一再的推迟,然后出现的情况就是挖矿已经变得越来越难了,因为难度炸弹的威力已经显现出来了,但是大家还是得继续挖,因为没有别的方法可以达成共识。

    原来是担心大家不愿意转,现在变成了想转也没法转,因为权益证明的共识机制还没有开发出来,这个情况到2017年四五月份中旬的时候就已经很明显了,就出块时间已经逐渐开始增长了,原来是说要稳定在15秒,那个时候就不断的变成了从15秒不断地增加,从十五秒,十六秒,十七秒,最后增加到三十秒左右,而且如果不采取措施,还会继续增长上去,那怎么办呢

    以太坊最后在一个EIP当中,决定计算难度炸弹地时候,要把区块号,回退三百万个区块来计算,就这个公式中,把真实的区块号减去三百万,算出Hi一撇,这个可以看成是假的区块号,然后算难度炸弹的时候是用这个假的区块号算的。这个给权益证明的上限争取了一些时间。

    image-20210813224632142

    那么这样做的结果怎么样呢

    y轴是难度炸弹的取值,x轴是区块号,是以10万为单位,可以看到早期的时候,区块号比较小的时候,这个难度炸弹的作用是很不明显的,基本可以忽略不计,难度调整基本上是根据系统中的出块时间进行调整的,然后,这个图的前半部分是按照原来那个公式算的,就是在没有决定回调之间的原始公式算的,直接用正常的区块号算,大概是370万个区块左右,这个难度炸弹的威力开始指数上升,到上面这个尖峰,这个尖峰的位置就是以太坊决定回调这个难度炸弹的时候,减了三百万个区块,所以他一下就掉下来了,这个难度炸弹的取值一下就掉下来了,后面看上去好像是个平的直线,其实也是在增长,只不过是因为那个尖峰的位置太高了,所以看上去好像是直线,前面这个部分其实也是在增长,也是因为这个尖峰太高了,所以看不出来

    image-20210813224644811

    以太坊的发展被分成了四个阶段,Frontier,Homestead,Metropolis,Serenity,其中Metropolis又分为两个阶段,Byzantium和Constantinople,我们处于Byzantium阶段,难度炸弹的回调就是在Byzantium阶段进行的

    image-20210813224655092

    EIP:Ethereum Improvement Proposal,BIP:BitCoin Improvement Proposal

    在难度回调的同时,把出块奖励从五个以太币降到了三个以太币,因为如果不这么调的话,对于回调之前的矿工是不公平的,他这个回调是突然进行的,昨天挖矿的时候挖的很辛苦,得到的是五个以太币,结果今天一夜之间难度降低了,你挖矿也是得了五个以太币,那对我来说就不公平,而且从系统当中获益的总供应量来说要维护总供应量的稳定,现在变得是挖矿要容易了,所以就相应的把出块奖励减少一些,这里说明一点,比特币当中每隔一段时间出块奖励减半的做法在以太坊中是没有的,像这个把五个以太币降低三个就是一次性的,并不是说以后定期都这么做。

    image-20210813224705817

    下面看一下具体的代码实现

    这个是Byzantium阶段,挖矿难度调整的代码,输入时父区块的时间戳和父区块的难度,计算出当前挖的这个区块的难度,这里面的注释给出了难度计算公式,也是分成两部分,括号里面是第一部分是难度调整的基础部分,后面加上2的periodCount-2次方,这就是难度炸弹,基础部分是在parent_diff的基础上加上后面那一项,后面那一项就是前面这个难度调整的力度,parent_diff/2048乘以后面的系数,后面max的前面那一串就是前面ppt公式的那个y,如果有叔父区块是2,没有的话是1,减去后面这个就是出块间隔除以9向下取整,后面这个-99也是难度调整的下限。

    下面这几行代码,这个BigTime就是当前区块的时间戳,bigParentTime就是父区块的时间戳

    image-20210813224719207

    这一页的代码主要是计算基础部分的难度调整,第一行就是把当前时间戳减去父区块的时间戳算出出块时间,然后第二行除以9向下取整。

    下面这个if.else就是判断一下是不是有叔父区块,有的话,是用2减去前面这个数x,没有的话用1减去前面这个数x,然后接下来跟负的99相比,往下调有一个节限,不能比-99还要小,接下来算的是难度调整的力度,父区块的难度除以这个DifficultyBoundDivisor实际上就是2048,然后跟前面算出的系数相乘,加到父区块的难度上面去,基础部分的难度调整有一个下限,难度再小也不能小于那个D0,这个MinimumDifficulty就是那个D0,131072

    image-20210813224733827

    下一页就是难度炸弹的计算,fakeBlockNumber假的区块号就是前面讲的Hi一撇。下面这个if的判断跟2999999相比,比她大的话,就要减掉2999999,为什么不减3000000,前面的公式不是减三百万吗,其实是因为,这里判断的是父区块的序号,而我当前挖的这个区块,比父区块要多一个,所以按照父区块的序号算的话,就正好差一个

    image-20210813224748259

    下面看一下以太坊中实际统计情况

    这个就是以太坊中的难度统计

    显示的是以太坊中挖矿难度的变化曲线,可以看到在以太坊早期,挖矿难度的变化是不明显的,增长的是比较慢的,当时以太坊市值很小,谁也没有想到以太坊未来会成为一个主流的加密货币,从2017年开始,挖矿难度的增长就比较明显了,尤其是难度炸弹这一部分

    image-20210813224801321

    看到这一部分的曲线,看上去像是指数形状,到尖峰的位置就是以太坊决定回滚难度炸弹,回滚三百万个区块,所以挖矿难度一下就掉下来了,就好像从悬崖中掉下来了,之后又震荡一会,之后又逐步上升,2018年以太坊的挖矿难度已经恢复到了以前的水平,而且还略有些增加,从图上看出,目前以太坊的挖矿难度基本上是区域稳定的

    image-20210813224820584

    这个图显示的是出块时间,不考虑个别波动,总体来说,出块时间稳定在十五秒上下有了很长时间,说明以太坊在早期的时候,挖矿难度额调整主要是以稳定出块时间为主的,达到这个预期的效果,同样是在2017年中旬5,6月份的时候,出块时间出现了大幅度增长,就是这个难度炸弹的效应

    image-20210813224830674

    到这个地方,可以看到出块时间达到了 三十秒左右,然后是难度炸弹的回调,一下子断崖似的下降,又恢复到了十五秒,而且一直维持到现在,这个图跟前一个图对比,前一个图显示的是难度炸弹回调之后总的挖矿难度逐渐又恢复到了原来的水平,这个是因为挖矿变容易之后,有更多的矿工加入,竞争更激烈了,而我们这个图显示呢,从出块角度来讲并没有收到影响,出块时间一直到现在还算是维持的比较好的15秒左右

    image-20210813224842546

    最后这个图显示的之前看过的两个区块,讲GHOST协议的时候看过的两个区块

    image-20210813224851390

    主要看这两行

    Difficulty就是当前区块的难度,Total Difficulty是把当前这个区块所在的这条链上的所有区块的难度加在一起,也就是这条链的总难度,所以之前讲的最长合法链对于以太坊来说,其实应该叫做最难合法链,就是总难度最大额合法链,每个区块的难度,反应的是挖出这个区块所需要的工作量,而总难度最大,就是挖出这条链上的所有区块需要的总工作量最大,一般来说,靠后的区块,他挖出来需要的工作量也是比较大的

    image-20210813224902561

    展开全文
  • 以太坊是一个平台,它上面提供各种模块让用户来搭建应用,如果将搭建应用比作造房子,那么以太坊就提供了墙面、屋顶、地板等模块,用户只需像搭积木一样把房子搭起来,因此在以太坊上建立应用的成本和速度都大大改善...
  • 以太坊解析之二——POA共识过程 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 文章目录以太坊解析之二——POA共识过程前言一、工作流程详细...

    以太坊解析之二——POA共识过程

    原始版本创建于2021-05-27



    前言

    简单解释一下这个共识:
    1、依靠预设好的授权节点(signers),负责产生block
    2、由已授权的signer选举(投票超过50%)加入新的signer


    一、工作流程

    1、启动挖矿后, 该组signers开始对生成的block进行 签名并广播,签名结果 保存在区块头的Extra字段中

    2、Extra中更新当前高度已授权的 所有signers的地址 ,因为有新加入或踢出的signer

    3、每一高度都有一个signer处于IN-TURN状态, 其他signer处于OUT-OF-TURN状态,
    ——IN-TURN的signer签名的block会 立即广播 (打包节点-打包signer)、(普通signer),
    ——OUT-OF-TURN的signer签名的block会 延时 一点随机时间后再广播, 保证IN-TURN的签名block有更高的优先级上链

    另外一个关键在于,假定打包节点(IN-TURN signer)作恶,POA限制了同一个signer只能在一定数量的连续区块中负责打包一次

    也就是坏人只能在最近的x个区块中负责打包(处于IN-TURN状态)一次(x为signer的总数)

    同时由于难度的设定,坏人(IN-TURN状态)发出一个坏区块(有恶意交易,完美的区块——这个坏人在IN-TURN签名过的)的速度要比其他人(OUT-OF-TURN状态)发出一个好区块(没有恶意交易,不完美——需要当前IN-TURN签名的区块)的速度要慢

    详细解析

    POA的共识:请看图——理想共识过程
    1、每个signer都可以miner.start(),但是他们挖矿的难度有些不同(IN-TURN难度为2,其他人为1)
    2、出块后会广播出去,经过N-1个参与者校验并签名后(N不确定,取决于什么时候能碰到IN-TURN的signer)
    3、第N个参与者校验者(也就是IN-TURN的signer)会签名,并校验是否“满足共识”确定完成区块的生成流程后上链
    4、那么“满足共识”的条件就是:当前收到的区块签名包含了第一张所述的IN-TURN的signer的签名,此时肯定满足共识。
    (而这个区块也肯定是由IN-TURN的signer签名的,发出的,所以它确实是第一个打包成完美块的那个节点)
    在这里插入图片描述

    二、详细过程

    1.启动

    POA共识的启动过程——在backend.go:470 进行初始化:
    在这里插入图片描述
    接下来一路到worker.go:992:commit():
    在这里插入图片描述

    需要注意,其实POA共识一直到最后的广播区块之前都与POW都一样,不同的是Seal过程和收区块验证的过程
    Seal现在过程如下:
    在这里插入图片描述

    请看Clique.go中的Seal函数:644行,即为签名
    在这里插入图片描述

    接下来就是广播后的同步过程
    也就是将这个没有IN-TURN的signer签名的不完美区块发出去,让IN-TURN的signer签名

    2.同步

    接下来看一下同步过程,关键从fetcher.go:162:newLightFetcher开始(在这之前是同步节点的命令启动)
    并关注166行:engine.VerifyHeader(chain, header, ulc == nil)
    从这一行开始,就要使用POA共识引擎对区块进行验证了

    直接进入consensus/clique/clique.go:217及246,关注VerifyHeader函数

    在这里插入图片描述
    在这里插入图片描述

    接下来就是对区块头和Seal好的区块中的签名者进行验证,也就是307->366
    在这里插入图片描述
    来看看VerifySeal:
    在这里插入图片描述在这里插入图片描述
    这就是关键的共识验证过程了,只需要知道这个函数最后会返回一个结果即可
    (如果不满足共识要求就会返回error或继续广播)

    3.总结

    关键的共识验证过程:
    说白了,如果签名中没有指定的IN-TURN signer,这个区块就是不完美的,没有满足共识要求的,否则就没问题

    4.一些其他问题

    1、如果我签名好的区块转了一圈一个签名者也没有碰到,又转回来了怎么办

    在Seal函数中
    在这里插入图片描述
    一些参考(尤其是后三个):
    http://chanye.18183.com/201807/1124156.html
    https://segmentfault.com/a/1190000014544347
    https://www.jianshu.com/p/071bdc6297ed
    https://www.jianshu.com/p/058698a30c82
    https://www.jianshu.com/p/9e3c21fb6cc2

    三、如果我想修改POA共识机制,把它改成质押(矿机)应该怎么做?

    要解决四个问题:

    怎么设计惩罚机制(前提:已知作恶节点和coinbase)
    质押机制怎么和POA绑定——块包含着质押的信息
    激励机制如何设计,出块应该怎么奖励
    POA代码如何修改

    在四个问题解决之前:需要看一下当前POA的节点投票是如何决定添加或删除signer的?

    1、节点环境:signer在不断挖矿(miner.start()),并可于任何时间调用propose进行投票,并存放在proposals[address]=bool(添加或删除)中(api.go:107)
    2、在生成新区块时,先为该区块初始化一个header(clique.go:506:prepare()),并从本地保存的proposals中随机选取一个投票信息放入header的coinbase(投谁)和nonce(添加还是删除)中(clique.go:527)(!!注意这里,也就是说添加/删除一个signer就相当于只有一个提案,如果你发起了好多投票让这个人或那个人添加或删除signer的话,每次区块是从这些好多票中随机选一个上区块)
    在3发生前,看一下snapshot(下图):

    3、同时创建一个新的snapshot,snapshot的组成是从上一个时间点的snapshot(可能距离好几个区块)到当前这个新区块的所有header的数据组成(!!但是很明显,如果数据很多存不下怎么办?POA设置了一个Epoch,每次创建新快照时,如果之前那个snapshot的header数量达到了Epoch,那么snapshot中的Votes和Tally清零(Epoch默认值:30000)snapshot.go:185:apply())

    4、将每一个header中有效的提名写入新snapshot的snap.Votes和snap.Tally集合

    5、判断是否大于snap.Signers的二分之一,大于则应用这次投票结果(添加或删除)snapshot.go:apply():261
    在这里插入图片描述

    具体流程如下:

    在这里插入图片描述

    1.如何设计惩罚机制

    可能的惩罚前提:
    1、(由第三方或其它signer)发现某个IN-TURN-signer出块了恶意区块时,进行惩罚
    2、(由第三方或其它signer)发现某个OUT-OF-TURN-signer打包了恶意区块时,进行惩罚
    3、(由第三方或其它signer)发现某个signer验证通过了某个恶意区块时,进行惩罚
    4、(由第三方或其它signer)发现某个非signer节点进行攻击等恶意交易时,进行惩罚
    5、signers共同认为某个signer作恶时,进行惩罚
    6、signers共同投票踢出某个signer时,进行惩罚

    惩罚的方式:
    1、signer作恶:signers共同决定踢出一个signer,并扣除质押(超过二分之一投票)
    2、普通节点作恶:signer共同对惩罚进行投票,并扣除账户金额,禁止后续交易(超过二分之一投票)
    惩罚的过程:
    对应上面1-5的惩罚前提:即signer已经对某个作恶情况完全明确,不需投票
    1、明确被惩罚者,明确惩罚方式,由一个指定signer节点通过发起特殊tx的形式来进行惩罚
    2、其它signer收到tx后,识别出这是一个惩罚tx,并解析出惩罚对应信息后对本地节点数据库进行修改
    对应上面6的惩罚前提:即需要投票踢出,才能进行惩罚
    1、这种惩罚过程是:当原始POA共识的投票过程满足后,就对本地节点数据库进行修改

    2.如何设计激励机制

    每当最后的IN-TURN出块广播时,其它的signer节点收到后便会修改本地节点数据库让这个IN-TURN节点获取奖励,参考POW的奖励方法即可,具体代码后面会有解释

    3.质押机制怎么和POA绑定——块包含着质押的信息

    质押的信息应保存在本地节点数据库中,并保存在Account数据中,Account数据结构左图如下:
    可以改为第二张图所示:

    在这里插入图片描述
    在这里插入图片描述

    进入质押过程:
    1、新的质押者使用拥有的货币,自定义一个量主动提出质押要求,以交易的方式发布到网络中

    2、其它signer收到tx,如果通过了节点要求(如最低质押金额要求,地址黑白名单),这个signer会自动发起一个添加signer的proposal(包含了质押者地址,以及自己是否同意添加signer(通过节点要求就是同意,否则就是不同意)),并与投票过程一样,随自己打包的块进行传播,同时将tx转发,让其它节点继续收tx,投票。

    3、其它signer收到tx后,同样的方法发出proposal,并转发tx

    4、最终,当这些proposal达成了超过 二分之一(可为其它值)同意质押的信息后,与添加signer的情况相同,增加一个signer

    5、而发出的tx最终会被IN-TURN signer打包上链,从而更改质押数据

    其它的考虑:
    在上面的2和3需要注意的一点是,由于原始的投票进块是随机的,也就是clique.go中的prepare用的是rand(int),所以投票出结果的速度和tx上链的速度不定:

    情况A:质押投票可能会滞后于tx上链从而修改质押账户的速度
    也就是会存在这样一种状态:“质押币账户已经加钱了,我的余额已经减钱了,但是我依然不是signer”
    针对这个问题,如果存在大量的proposal等待上链,则需要再代码中优先处理质押相关的proposal

    情况B:质押投票可能会快于tx上链从而修改质押账户的速度 也就是会存在这样一种状态:“我的质押币账户还没加钱,但我已经成为signer了”
    针对这个问题,如果这个signer作恶其实不用担心,我们可以后面进行惩罚 如果出现恶意的质押退出,使自己没有质押的时候保持signer身份,实际上这样我们依然可以用惩罚来解决

    当然,为了避免上述问题,我们尽量让tx上链和质押账户修改保持同步,也就是说,在prepare函数中,优先让质押信息进块

    退出质押过程:
    1、新的质押者使用拥有的质押货币,自定义一个量主动提出退出质押要求,以交易的方式发布到网络中

    2、其它signer收到tx,如果通过了节点要求(如最低质押金额要求,地址黑白名单),这个signer会自动发起一个删除signer的proposal(包含了质押者地址,以及自己是否同意删除signer(通过节点要求就是同意,否则就是不同意)),并与投票过程一样,随自己打包的块进行传播,同时将tx转发,让其它节点继续收tx,投票。

    3、其它signer收到tx后,同样的方法发出proposal,并转发tx

    4、最终,当这些proposal达成了超过 二分之一(可为其它值)退出质押的信息后,与进入质押的情况类似,删除一个signer

    5、而发出的tx最终会被IN-TURN signer打包上链,从而更改质押数据

    下面讲解如何让投票速度与tx上链速度尽量同步,也就是如何让质押投票进块的速度更快:

    解决方案很直接,就是在prepare过程中,优先选择那些质押的proposal,那么如何保存?
    当前,用于保存proposal是一个proposals的map:proposals
    map[common.Address]bool(可以查看下一页的clique的struct)

    我们将这个map修改,增加一个保存proposal类型的地方,这个类型仅仅是用于本地识别proposal是单纯的投票进出signer,还是因质押的投票进入signer

    这样在prepare中就从那些质押的proposal中优先选择即可

    4.代码如何修改

    一、数据结构
    · 增加区块头结构
    1、address VoteAddress(替代coinbase,标识着投关于谁的票)
    2、bool VoteBool(替代nonce,标识着添加还是删除)

    · 修改区块头结构(已存在,不需修改只做标记说明)
    1、address Coinbase(恢复在POW当中的作用,用于发放奖励)
    2、Nonce(恢复在POW当中的作用,用于标识不同的交易)

    · 修改账户结构(core/state/state_object.go:101)
    1、*big.Int Pledge(质押货币数量)

    · 依照账户结构修改本地节点数据库,增加Pledge字段

    ·对应15页下半部分关于增加质押投票速度的解决方案:
    1、增加clique类型,增加一个proposal类型(质押投票或是普通投票)

    · 增加配置文件
    1、关于质押的配置文件数据(质押的标准,质押黑名单)


    · 一些前提——Account的增加、减少、设置操作: 原有的POW奖励代码:consensus/ethash/consensus.go:641:accumulateRewards()-> accumulateRewards调用奖励核心代码:core/state/statedb.go:386:AddBalance()-> AddBalance关键执行代码:core/state/state_object.go:440,448:SetBalance()

    二、功能修改——基本数据操作修改
    · 在验证区块是否为完美区块后,在clique.go:VerifyHeader给予奖励,使用上述的accumulateRewards()
    · 在core/state/state_object.go中增加质押货币的增加、减少、设置操作(相当于账户余额的锁仓),对应操作节点数据库,具体的实现可以参考“· 一些前提”中关于余额的操作

    三、功能修改——投票功能修正
    · 区块头在clique.go中prepare函数随机选取proposal时信息的保存位置从区块头的coinbase-nonce改为区块头的voteaddress-votebool

    四、功能修改——质押tx的接收过程
    · 当tx收到了一个用来修改质押账户的tx后要识别出来(可以直接从tx中识别,对应数据库修改之后,可以对tx的转账类型识别)修改位置需要参考修改质押账户的位置
    · 对于质押信息生成质押结果的判别,要依赖一下配置文件,看看是否有黑名单,是否超过了质押下限,另可以开放api交给节点使用者自定义本节点能够接收的质押下线和黑名单
    · 识别出来后,保存到proposal中时,除了保存地址、是否同意质押之外,增加保存proposal的类别(普通投票/质押投票)修改位置:clique/api.go内,的propose函数修改,新增类型的保存
    · 在proposal进区块即clique/clique.go中的prepare函数中新增优先质押投票的识别,优先选择质押投票进块

    关键的难点:对于节点数据库k-v的修改,并需要让持久化层和控制层的匹配

    具体的代码参考 cmd/geth/dbcmd.go core/state/statedb.go core/state/database.go
    core/state/state_object.go

    另,为了减少开发难度,节点数据库中pledge质押账户的的修改可以不用走状态,仅仅让balance(上一张的setbalance函数)走状态也可

    看一下Transaction从创建-广播发出-接收-再广播发出是如何进行的
    先来看从创建到广播发出:

    在这里插入图片描述

    展开全文
  • 哈希校验区块完整性,保证不可篡改特性,用到了hash算法以太坊中具体用到sha2 sha3的hash算法) 对区块链通讯报文进行加密,防止传输过程泄密;在北京银行网贷资金存管项目中,我司方案用加密保证私密性和可监管...

    区块链技术的基础是计算机密码学,可以说***“没有计算机密码学,就没有区块链技术”***,区块链在如下方面用到了计算机密码学:

    • 验证签名,保证交易发起的真实性,用到了ECDSA

    • 哈希校验区块完整性,保证不可篡改特性,用到了hash算法(以太坊中具体用到sha2 sha3的hash算法)

    • 对区块链通讯报文进行加密,防止传输过程泄密;在北京银行网贷资金存管项目中,我司方案用加密保证私密性和可监管性

    区块链应用国密算法的重要性

    为了保障商用密码的安全性,国家商用密码管理办公室制定了一系列密码标准,包括SM1(SCB2)、SM2、SM3、SM4、SM7、SM9、祖冲之密码算法(ZUC)那等等。

    其中:

    • SM1、SM4、SM7、祖冲之密码(ZUC)是对称算法

    • SM2、SM9是非对称算法

    • SM3是哈希算法

    目前,这些算法已广泛应用于国家各个领域中,其中金融领域比如PBOC3.0中国密是国家标准。在国内区块链应用采用国密算法作为标准是必然的。

    国密算法对应表

    前面所述区块链功能及所采用的密码学算法,国密中都有对应的部分,见如下表格

    在这里插入图片描述

    完全用国密去建立起一套区块链框架,理论上是有可能的,且所用到的国密算法主要是SM2,SM3,SM4


    国密替代方案

    完全用国密建立起一套区块链框架,虽然理论上是有可能的,但是实际实现时需要考虑兼容性问题,我们知道以太坊的账户就是基于ECDSA椭圆曲线算法生成的,私钥是32位,公钥是65位,公钥压缩成地址后是20位。国密的对应算法是SM2,虽然同样属于椭圆曲线算法体系,但是曲线参数的不同,造成其并不兼容以太坊账户。

    • 用现有以太坊账户签名的交易,用SM2无法验证签名

    • 以太坊账户和SM2生成的账户无法进行有效的密钥交换

    因此国密替换的重点放在了用SM4算法替换AES算法。

    SM4算法介绍:SM4分组密码算法是我国自主设计的分组对称密码算法,用于实现数据的加密/解密运算,以保证数据和信息的机密性。要保证一个对称密码算法的安全性的基本条件是其具备足够的密钥长度,SM4算法与AES算法具有相同的密钥长度分组长度128比特,因此在安全性上高于3DES算法。

    回头看我们为北京银行网贷资金存管项目所做的加密流程:
    在这里插入图片描述

    其中设计加密算法的如下:

    • 对业务明文加密是用对称算法进行的,此处可以用国密SM4,现在是DES

    • 对交易密钥本身的加密,也是采用对称算法的,此处可以用国密SM4,现在是AES

    • 对交易密钥加密的密钥是通过ECDSA椭圆曲线算法生成的,此处不替换,但是由于做了缓存,这种运算只有程序初始化的时候用到

    也就是说如果前2种情况采用国密,就相当于覆盖了99%的加密需求


    替换国密后性能对比测试

    使用国密算法后,性能问题要重点考虑,因为:

    • 之前公开报道中,国内某家公司用SM2代替ECDSA后,性能显著下降,需要在架构上考虑剥离加密,采用GPU加速等方式来对冲性能影响

    • 我们之前对北京银行网贷资金存管项目的测试中发现加密速度对项目性能有较大影响,而且CPU占用率较高

    考虑到如上情况,所以设计了一个实验

    • 环境为工作笔记本,4C8G,其中CPU是i5-5200U,2.2Ghz

    • 明文长度是16字节,密钥长度16字节,密文长度16字节

    • 基于Junit,每个循环经历一次加密,一次解密,且解密结果和原文进行核对,如果对不上中断退出

    • 每次测试,发起100万个加密解密请求

    • 同样地,加密过程中所用的哈希算法也替换成国密(比如密钥交换后得到的大数用hash变为32位以便后续运算),同样是每次测试发出100万个哈希请求,比对原有算法和国密的速度

    对称加密测试结果对比表格:(红色为最长耗时,蓝色为最短耗时)

    在这里插入图片描述
    测试期间CPU占用情况比对:(前者AES,后者SM4)
    在这里插入图片描述

    SM4算法调用的代码:
    在这里插入图片描述

    SM3哈希算法调用的代码:
    在这里插入图片描述

    哈希算法测试结果对比表格:

    在这里插入图片描述


    测试情况说明:

    1. Java中加密算法的实现,可以由不同的第三方去实现;本次测试所用3种,分布是JDK自带的标准实现,著名第三方提供商SpongyCastle包中提供的AES和SM4算法。

    2. JDK自带的AES实现,速度比较慢,经过代码分析,该实现代码较为简单,没有为了提升速度将一些中间过程中可能用到的变量全部以静态方式预存;相反地SpongyCastle AES算法,采用**“以空间换时间”**的方法,定义了大量的空间用于对称加密过程中的比特变化,大大提升了速度。

    3. SongyCastle SM4实现上和SpongyCastle AES算法较为相似,也采用了类似“以空间换时间”的方法,速度较快。同样地,哈希算法使用以太坊Util类中自带的哈希算法,和采用国密SM3哈希算法,速度也差不多,甚至国密还快点。预计区块链换用国密SM3和SM4后,速度不会因此下降。

    4. 目前单单计算加密解密的TPS,可以达到十万次每秒的水平级别,而我们区块链的TPS还在千次每秒的水平级别,目前加密解密还不成为瓶颈

    展开全文
  • 基于以太坊实现EOS的dpos共识算法,实现go版本EOS的dpos公链
  • 以太坊共识算法研究

    千次阅读 2018-06-10 11:52:41
    在两种共识算法的实现中,Ethash是产品环境下以太坊真正使用的共识算法,Clique主要针对以太坊的测试网络运作,两种共识算法的差异,主要体现在Seal()的实现上。 Ethash共识算法 Ethash算法又被称为Proof-of-Work...
  • 以太坊交易和签名

    千次阅读 2022-04-25 16:33:10
    以太坊交易 以太坊交易是什么 ? 交易(Transaction)是指由一个外部账户转移一定资产给某个账户, 或者发出一个消息指令到某个智能合约。 在以太坊网络中,交易执行属于一个事务。具有原子性、一致性、隔离性、...
  • 以太坊目前所使用的共识算法介绍

    万次阅读 2019-05-08 12:53:30
    如果别人问你“以太坊目前所使用的共识算法”是什么?如果你此时去浏览器搜索发现有些文章说是PoS,又有些说是PoW。 完整且正确的说法应该是这样的,这其实也是PoW共识机制与以太坊的关系。首先以太坊的源码是分有...
  • 一直以来,以太坊由多元化的全球性社区贡献者来协同进行维护和改善,社区成员耕耘于以太坊的方方面面,从核心协议到应用程序。 这个网站,就像以太坊的其他部分一样,是由一群人共同构建的,并将持续构建下去。 本...
  • 以太坊的官方共识算法是ethash算法,这在前文已经有了详细的分析: 它是基于POW的共识机制的,矿工需要通过计算nonce值,会消耗大量算力来匹配target值。 如果在联盟链或者私链的方案里,继续使用ethash就会浪费算力...
  • 死磕以太坊源码分析之Ethash共识算法 代码分支:https://github.com/ethereum/go-ethereum/tree/v1.9.9 文章合集:https://github.com/blockchainGuide 引言 目前以太坊中有两个共识算法的实现:clique和ethash。而...
  • Ethash的C / C ++实现–以太坊工作量证明算法 目录 安装 使用CMake从源代码构建。 mkdir build cd build cmake .. cmake --build . 用法 有关导出的功能和文档的列表,请参见 。 测试向量 最佳化 本节描述了与有关...
  • ①本人想要把以太坊的链层为dag的形式,使他能够并行加入块,请问是在以太坊代码中哪个文件下修改 ②想要修改共识机制该在哪个文件下修改,想把其他共识运用在以太坊
  • 以太坊的共识机制

    万次阅读 2018-08-13 14:50:49
    在开始之前,我们补充一点基础知识。   第一个概念是哈希。简单理解,哈希是一个函数。...几乎任何加密货币都会用到哈希算法以太坊采用的哈希算法是ethash算法。   第二个补充知识是,以太坊的区块结构。...
  • 以太坊白皮书(更新于2021年2月9日版本) 这篇介绍性论文最初由以太坊创始人Vitalik Buterin于2013年发表,该项目于2015年启动。值得注意的是,以太坊和许多社区驱动的开源软件项目一样,从一开始就在不断发展。 ...
  • 最近,以太坊又一次出现大拥堵,美图基于以太坊框架实现了 DPoS 算法并且对代码进行了开源(链接见文末),希望借助此方案能让以太坊发展有更多的选择的可能。图:最近一周以太坊交易又出现大范围拥堵有些人对于以太坊...
  • 一、以太坊简介 以太坊(Ethereum)项目的最初目标是打造一个运行智能合约的平台(Platform for Smart Contract),支持图灵完备的应用,按照智能合约的约定逻辑自动执行,理想情况下将不存在故障停机、审查、欺诈以及...
  • 以太坊官方发文提醒硬分叉注意事项:分叉时间预计在1月16日,区块高度在7080000。并强调,此次硬分叉就像Office软件升级一样,会出现一些兼容类的问题,节点需要全部更新升级。  此次更新是无争议的硬分叉更新,...
  • 以太坊技术要点 ethereum/wiki ethereumbook 密钥、地址、钱包账户 参考:keys-addresses 加密算法:Keccak256、ECDSA、RIPEMD-160、PBKDF2PBKDF2(Password-Based Key Derivation Function,基于密码的密钥推导函数2...
  • 以太坊的状态树 Merkle Patricia Tree

    千次阅读 2022-02-01 15:27:41
    以太坊的MPT [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QxxPxO5m-1643700433445)(https://github.com/hrt014pocky/pocky/blob/main/pictures/worldstatetrie.png?raw=true ...
  • Polygon 架构 Polygon 是一个区块链应用平台,提供POS共识和Plasma的侧链, 从架构上,它有一个通用的验证层,与各种不同的执行环境...以太坊是Polygon支持的第一个基链,但Polygon打算根据社区建议和共识,提供对其他
  • 哈希/ *版权所有-Open Eth Mine以太坊矿业 有或没有源和二进制形式的重新分发和使用修改,只要满足以下条件满足: 重新分发源代码必须保留上述版权请注意,此条件列表和以下免责声明。 以二进制形式重新分发必须复制...
  • NodeTable类负责以太坊的节点发现,NodeTable采用kademlia(KAD)算法进行节点发现 NodeTable维护一个网络节点列表,此列表为当前可用节点,供上层使用 由于NodeID经过sha3生成出的Hash为256位。列表有256-1=255...
  • 我们将可忽略概率Pn定义为获得256位SHA3冲突(以太坊的Hash算法)的概率:1/2 ^ 128。 为了遵守以太坊的安全要求,我们需要选择最小链长N(在我们每个块都验证之前),最大K验证批量大小如(1 / K)^(N / K)。 对...
  • 以太坊源码阅读1——准备环境

    千次阅读 2022-03-10 20:14:37
    以太坊源码阅读1——准备环境 基本环境 win10家庭版 IntelliJ IDEA 2021.3.2(GOLAND等也行) 环境准备 由于ethereum是用go写的,需要准备一下go的环境 下载go插件 准备go的SDK IDE有时候会请求帮忙下载,...
  • 以太坊中,交易所需的 gas 费计算方式是: TransactionFee = GasPrice × GasLimit 其中 Gas Limit 代表你愿意为这笔交易支付的最大 gas 量,这通常取决于交易的复杂程度。Gas Price 指的是 Gas 的价格,即你...
  • 以太坊的初始阶段,持续时间为2015年7月30日至2016年3月 “家园”(Homestead)-Block #1,150,000 以太坊的第二阶段,于2016年3月推出 “大都会”(Metropolis)Block#437000 以太坊的第三个阶段,于2017年10月推出的...
  • Fabric、FISCO BCOS、以太坊对比一、以太坊1.1 什么是工作量证明(POW)1.2 这是如何运作的?1.3 工作量证明的问题1.4 股权证明二、Fabric2.1 产生背景2.2 共识机制2.3 数据隔离2.4 智能合约2.5 权限管控2.6 存储2.7...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,198
精华内容 2,079
关键字:

以太坊改算法