共识算法 – POW 及实现思路

2018年9月16日 作者 jacky

 

POW 理论

比特币区块

比特币区块由区块头和该区块所包含的交易列表组成。区块头大小为80字节,其构成包括:

4字节:版本号
32字节:上一个区块的哈希值
32字节:交易列表的Merkle根哈希值
4字节:当前时间戳
4字节:当前难度值
4字节:随机数Nonce值

此80字节长度的区块头,即为比特币Pow算法的输入字符串。
交易列表附加在区块头之后,其中第一笔交易为矿工获得奖励和手续费的特殊交易。

比特币Pow算法原理

Pow的过程,即为不断调整Nonce值,对区块头做双重SHA256哈希运算,使得结果满足给定数量前导0的哈希值的过程。
其中前导0的个数,取决于挖矿难度,前导0的个数越多,挖矿难度越大。

具体如下:

1、生成铸币交易,并与其它所有准备打包进区块的交易组成交易列表,生成Merkle根哈希值。
2、将Merkle根哈希值,与区块头其它字段组成区块头,80字节长度的区块头作为Pow算法的输入。
3、不断变更区块头中的随机数Nonce,对变更后的区块头做双重SHA256哈希运算,与当前难度的目标值做比对,如果小于目标难度,即Pow完成。

Pow完成的区块向全网广播,其他节点将验证其是否符合规则,如果验证有效,其他节点将接收此区块,并附加在已有区块链之后。之后将进入下一轮挖矿。

比特币挖矿难度计算

每创建2016个块后将计算新的难度,此后的2016个块使用新的难度。计算步骤如下:

1、找到前2016个块的第一个块,计算生成这2016个块花费的时间。
即最后一个块的时间与第一个块的时间差。时间差不小于3.5天,不大于56天。
2、计算前2016个块的难度总和,即单个块的难度x总时间。
3、计算新的难度,即2016个块的难度总和/14天的秒数,得到每秒的难度值。
4、要求新的难度,难度不低于参数定义的最小难度。

以太坊区块

以太坊区块由Header和Body两部分组成。

其中Header部分成员如下:
ParentHash,父区块哈希
UncleHash,叔区块哈希,具体为Body中Uncles数组的RLP哈希值。RLP哈希,即某类型对象RLP编码后做SHA3哈希运算。
Coinbase,矿工地址。
Root,StateDB中state Trie根节点RLP哈希值。
TxHash,Block中tx Trie根节点RLP哈希值。
ReceiptHash,Block中Receipt Trie根节点的RLP哈希值。
Difficulty,区块难度,即当前挖矿难度。
Number,区块序号,即父区块Number+1。
GasLimit,区块内所有Gas消耗的理论上限,创建时指定,由父区块GasUsed和GasLimit计算得出。
GasUsed,区块内所有Transaction执行时消耗的Gas总和。
Time,当前时间戳。
Nonce,随机数Nonce值。

有关叔区块:
叔区块,即孤立的块。以太坊成块速度较快,导致产生孤块。
以太坊会给发现孤块的矿工以回报,激励矿工在新块中引用孤块,引用孤块使主链更重。在以太坊中,主链是指最重的链。

有关state Trie、tx Trie和Receipt Trie:
state Trie,所有账户对象可以逐个插入一个Merkle-PatricaTrie(MPT)结构中,形成state Trie。
tx Trie:Block中Transactions中所有tx对象,逐个插入MPT结构中,形成tx Trie。
Receipt Trie:Block中所有Transaction执行后生成Receipt数组,所有Receipt逐个插入MPT结构中,形成Receipt Trie。

Body成员如下:
Transactions,交易列表。
Uncles,引用的叔区块列表。

以太坊Pow算法原理

以太坊Pow算法可以表示为如下公式:
RAND(h, n) <= M / d

其中RAND()表示一个概念函数,代表一系列的复杂运算。
其中h和n为输入,即区块Header的哈希、以及Header中的Nonce。
M表示一个极大的数,此处使用2256-1。
d,为区块难度,即Header中的Difficulty。

因此在h和n确定的情况下,d越大,挖矿难度越大,即为Difficulty本义。
即不断变更Nonce,使RAND(h, n)满足RAND(h, n) <= M / d,即完成Pow。

以太坊挖矿难度计算

以太坊每次挖矿均需计算当前区块难度。
按版本不同有三种计算难度的规则,分别为:calcDifficultyByzantium(Byzantium版)、calcDifficultyHomestead(Homestead版)、calcDifficultyFrontier(Frontier版)。此处以calcDifficultyHomestead为例。

计算难度时输入有:
parent_timestamp:父区块时间戳
parent_diff:父区块难度
block_timestamp:当前区块时间戳
block_number:当前区块的序号

当前区块难度计算公式,即:


block_diff = parent_diff
+ (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)
+ 2^((block_number // 100000) - 2)

其中//为整数除法运算符,a//b,即先计算a/b,然后取不大于a/b的最大整数。

调整难度的目的,即为使挖矿时间保持在10-19s期间内,如果低于10s增大挖矿难度,如果大于19s将减小难度。另外,计算出的当前区块难度不应低于以太坊创世区块难度,即131072。

POW核心思想的代码实现

代码实现