Pre:

Go Blockchain Tutorial Part 2: Proof of Work 学习记录

共识机制:

我们常说区块链是一个分布式系统，系统中每个节点都有机会储存数据信息构造一个区块然后追加到区块链尾部。
这里就存在一个问题，

那就是当区块链系统中有多个节点都想将自己的区块追加到区块链时，我们该怎么办？

我们将这些等待添加的区块统称为候选区块，显然我们不能对候选区块全盘照收，否则区块链就不再是一条链而是不同分叉成区块树。

那么我们如何确定一种方法来从候选区块中选择一个加入到区块链中了？

这里就需要用到区块链的共识机制，后文将以比特币使用的最经典PoW共识机制进行讲解。

共识机制说的通俗明白一点就是要在相对公平的条件下让想要添加区块进区块链的节点内卷，通过竞争选择出一个大家公认的节点添加它的区块进入区块链。
整个共识机制被分为两部分，首先是竞争，然后是共识。

中本聪在比特币中设计了如下的一个Game来实现竞争：每个节点去寻找一个随机值（也就是nonce），将这个随机值作为候选区块的头部信息属性之一，要求候选区块对自身信息（注意这里是包含了nonce的）进行哈希后表示为数值要小于一个难度目标值（也就是Target），最先寻找到nonce的节点即为卷王，可以将自己的候选区块发布并添加到区块链尾部。
这个Game设计的非常巧妙

首先每个节点要寻找到的nonce只对自己候选区块有效，防止了其它节点同学抄答案
其次，nonce的寻找是完全随机的没有技巧，寻找到nonce的时间与目标难度值与节点本身计算性能有关，但不妨碍性能较差的节点也有机会获胜；
最后寻找nonce可能耗费大量时间与资源，但是验证卷王是否真的找到了nonce却非常却能够很快完成并几乎不需要耗费资源，这个寻找到的nonce可以说就是卷王真的是卷王的证据。

现在我们就来实现这个Game。
Find Nonce Game~

代码实现：

proofofwork.go

package blockchain

import (
	"bytes"
	"crypto/sha256"
	"fmt"
	"math"
	"math/big"
	"my-blockchain/constcoe"
	"my-blockchain/utils"
)

// 返回目标难度值的函数
func (b *Block) GetTarget() []byte {
	target := big.NewInt(1)
	// Lsh函数就是向左移位，移的越多目标难度值越大，
	// 哈希取值落在的空间就更多, 就越容易找到符合条件的nonce。
	target.Lsh(target, uint(256-constcoe.Difficulty))
	return target.Bytes()
}

// 每次我们输入一个nonce对应的区块的哈希值都会改变
func (b *Block) GetBase4Nonce(nonce int64) []byte {
	data := bytes.Join([][]byte{
		utils.ToHexInt(b.Timestamp),
		b.PrevHash,
		utils.ToHexInt(int64(nonce)),
		b.Target,
		b.Data,
	}, []byte{},
	)
	return data
}

func (b *Block) FindNonce() int64 {
	var intHash big.Int
	var intTarget big.Int
	var hash [32]byte
	var nonce int64
	nonce = 0
	intTarget.SetBytes(b.Target)

	for nonce < math.MaxInt64 {
		fmt.Printf("=======================\n")
		fmt.Println("Start Find the Right Nonce")
		fmt.Printf("nonce: %d\n", nonce)
		data := b.GetBase4Nonce(nonce)
		fmt.Printf("data: %x\n", data)
		hash = sha256.Sum256(data)
		fmt.Printf("hash: %x\n", hash)
		intHash.SetBytes(hash[:])
		fmt.Printf("intHash: %x\n", &intHash)
		fmt.Printf("intTarget: %x\n", &intTarget)
		// Cmp compares x and y and returns:
		//   -1 if x <  y
		//    0 if x == y
		//   +1 if x >  y
		if intHash.Cmp(&intTarget) == -1 {
			break
		} else {
			// 每次失败nonce就加1
			// 直到由当前nonce得到的区块哈希转化为数值 小于 目标难度值为止。
			nonce++
		}
	}
	return nonce
}

func (b *Block) ValidatePow() bool {
	var intHash big.Int
	var intTarget big.Int
	var hash [32]byte
	intTarget.SetBytes(b.Target)
	data := b.GetBase4Nonce(b.Nonce) // 由当前nonce得到的区块哈希
	hash = sha256.Sum256(data)
	intHash.SetBytes(hash[:])
	if intHash.Cmp(&intTarget) == -1 { // 区块哈希转化为数值小于目标难度值
		return true
	}
	return false
}

测试不同难度值:

尝试将全局变量Difficulty改大来增加难度值，然后观察一下各个区块的nonce、timestamp的变化。

Difficulty = 12

符合条件 intHash < intTarget：

Start Find the Right Nonce
nonce: 3483
hash:      000dc411eb3f27a11d820658c7a465357aaa92ff662448b8cd0ae561829877ac
intHash:   dc411eb3f27a11d820658c7a465357aaa92ff662448b8cd0ae561829877ac
intTarget: 10000000000000000000000000000000000000000000000000000000000000

不符条件 intHash > intTarget：

Start Find the Right Nonce
nonce: 3482
hash:      86916242d284f85cd3355af5b81a704f6e52b9fb69271ab5d5ff78fab894ce66
intHash:   86916242d284f85cd3355af5b81a704f6e52b9fb69271ab5d5ff78fab894ce66
intTarget: 10000000000000000000000000000000000000000000000000000000000000

Difficulty = 15

符合条件 intHash < intTarget：

Start Find the Right Nonce
nonce: 33547
hash:      00017e89620ddef6de217ed066611b7aad51668c15f1df021cb51d4a2b9832d0
intHash:   17e89620ddef6de217ed066611b7aad51668c15f1df021cb51d4a2b9832d0
intTarget: 2000000000000000000000000000000000000000000000000000000000000

不符条件 intHash > intTarget：

Start Find the Right Nonce
nonce: 33546
hash:      4fd58060f8f54d4b9e98bab58f449b26f7297bc278ae946fce9ec0a15e4aa0cb
intHash:   4fd58060f8f54d4b9e98bab58f449b26f7297bc278ae946fce9ec0a15e4aa0cb
intTarget: 2000000000000000000000000000000000000000000000000000000000000

统计结果如下：难度值越高，intTarget长度越短，找出符合条件的nonce的尝试次数越多。

难度值	Hash ByteLength	intTarget值	intTarget ByteLength	尝试次数
12	64	10000000000000000000000000000000000000000000000000000000000000	62	3483
15	64	2000000000000000000000000000000000000000000000000000000000000	61	33547
30	64	400000000000000000000000000000000000000000000000000000000	57	未测

参考一：简化的工作量证明算法

参考一下《MasteringBitcoin》里的简化的工作量证明算法。

挖矿的目标是找到一个随机数的值nonce，使区块头的哈希值小于难度目标target。
在找到合适的随机值前，挖矿节点可能需要尝试数十亿，或数万亿次。

简单地说，挖矿是重复散列区块头的过程，不断更改参数，直到生成的哈希值与特定目标相匹配。
散列函数的结果不能预先确定，也不能创建产生特定哈希值的模式。
散列函数的这种特性意味着产生匹配特定目标的散列结果的唯一方法是反复尝试，随机修改输入，直到偶然出现所需的结果。

#!/usr/bin/env python
# Proof-of-Work 算法示例

import hashlib
import time

try:
    long        # Python 2
    xrange
except NameError:
    long = int  # Python 3
    xrange = range

max_nonce = 2 ** 32  # 40亿


def proof_of_work(header, difficulty_bits):
    # 计算难度目标
    target = 2 ** (256 - difficulty_bits)

    for nonce in xrange(max_nonce):
        hash_result = hashlib.sha256(str(header) + str(nonce)).hexdigest()

        # 检查是否是目标值以下的有效结果
        if long(hash_result, 16) < target:
            print("Success with nonce %d" % nonce)
            print("Hash is %s" % hash_result)
            return (hash_result, nonce)

    print("Failed after %d (max_nonce) tries" % nonce)
    return nonce


if __name__ == '__main__':
    nonce = 0
    hash_result = ''

    # 难度从0到31位
    for difficulty_bits in xrange(32):
        difficulty = 2 ** difficulty_bits
        print("Difficulty: %ld (%d bits)" % (difficulty, difficulty_bits))
        print("Starting search...")

        # 当前时间
        start_time = time.time()

        # 创建一个包含前一个块的散列的新块
        # 我们伪造一个交易块 —— 只是一个字符串。
        new_block = 'test block with transactions' + hash_result

        # 为新块找到一个有效的nonce
        (hash_result, nonce) = proof_of_work(new_block, difficulty_bits)

        # 记录需要多长时间才能找到结果
        end_time = time.time()

        elapsed_time = end_time - start_time
        print("Elapsed Time: %.4f seconds" % elapsed_time)

        if elapsed_time > 0:

            # 估计每秒的散列计算次数
            hash_power = float(long(nonce) / elapsed_time)
            print("Hashing Power: %ld hashes per second" % hash_power)

nonce自增,会不断去计算出符合条件的hash值，类似暴力破解

hash_result is 1f3fe9dcf01e80b10e2adb650ac8fa0d843566b67f1109e9db6017bbde6d6651
hash_result is 5fdceb40e2c82558588a67c55f2c074f68a5e5d9d18db20aef6adc930f4220ce
hash_result is c59e7922f6e6701898c4392fa1ac5bc351bb0c16dae0d8793beab5bac9de688c
hash_result is a7717e95f3d912771573ca305aabaa983081642edb1f55fc55d30eae1e2edfac
hash_result is efafc1b283dc674b288c7afcfa58cb36927e067f7bc23f5c4de361531ecd55ee
hash_result is b7663a2c3e43f68478670fb7e60fec7330c6c457f648b03bf4bb451f21a4e8db
hash_result is 014bbc2e4bc516ab57543a053f0e320021410e6f2e1791ca01bebd914f3bfecf
hash_result is 6dd4ab421f060e6f4b968964e7d2ea85825c2138e73719f574a7edc00b705078
hash_result is 7cadff34a0d0fc0a5fd0e12eaed399be025d90eae75968bc67c19b6e70a34697

长度的判断条件则是将hash值前面的0去掉。换言之，难度目标影响了符合条件的hash值的前置零的个数。

# 检查是否是目标值以下的有效结果
if long(hash_result, 16) < target:
# 示例:     00000006dc70d218bafb37c31f3166e49b1b0d28f3fea500431ecb22e954c99e 
#           =》
#          6dc70d218bafb37c31f3166e49b1b0d28f3fea500431ecb22e954c99e

# 输出结果
============================
Difficulty: 2097152 (21 bits)
Starting search...
Success with nonce 687438
Hash is   000003a6eeee97491a9183e4c57458172edb6f9466377bf44afbd74e410f6eef
target is 55213970774324510299478046898216203619608871777363092441300193790394368
Elapsed Time: 1.3613 seconds
Hashing Power: 504976 hashes per second
============================
Difficulty: 4194304 (22 bits)
Starting search...
Success with nonce 1759164
Hash is   0000008bb8f0e731f0496b8e530da984e85fb3cd2bd81882fe8ba3610b6cefc3
target is 27606985387162255149739023449108101809804435888681546220650096895197184
Elapsed Time: 3.5224 seconds
Hashing Power: 499417 hashes per second

...

============================
Difficulty: 268435456 (28 bits)
Starting search...
Success with nonce 139905000
Hash is   0000000e4da88b53f70b2c5fc142500f0633e6407a4793462c54e6e704a687f3
target is 431359146674410236714672241392314090778194310760649159697657763987456
Elapsed Time: 289.7721 seconds
Hashing Power: 482810 hashes per second

从输出结果来看，难度越大，target越短，符合条件的hash值的前置零的个数需要得越多

Difficulty	正确hash的前置0个数	耗费时间
21	5	1.3613 seconds
22	6	3.5224 seconds
28	7	289.7721 seconds

继续看书中的例子：

[...]

Difficulty: 67108864 (26 bits)
Starting search...
Success with nonce 84561291
Hash is 0000001f0ea21e676b6dde5ad429b9d131a9f2b000802ab2f169cbca22b1e21a
Elapsed Time: 665.0949 seconds
Hashing Power: 127141 hashes per second

可以看出，随着难度位一位一位地增加，查找正确结果的时间会加倍增长。
如果考虑整个256bit数字空间，每次要求多一个0，就把哈希查找空间缩减了一半。
在什么的输出中，为寻找一个随机数使得哈希值开头的26位值为0，一共尝试了8千多万次。
即使笔记本电脑每秒可以达120,000多次哈希计算，找到结果依然需要10分钟。

在写这本书的时候，比特币网络要寻找区块头信息哈希值小于

1	0000000000000000029AB9000000000000000000000000000000000000000000

可以看出，这个难度目标开头的0多了很多。这意味着可接受的哈希值范围大幅缩减，因而找到正确的哈希值更加困难。
网络平均每秒要花费超过1.8个zeta次哈希（千亿个哈希）才能发现下一个区块。
这似乎是一项不可能完成的任务，但幸运的是，网络每秒有3exa次哈希（EH/sec）的处理能力，平均10分钟左右就能找到一个区块。

参考二:

何谓工作量证明:

网路上的节点可以简单地透过工作量证明，快速验证彼此是否拥有记帐权。就像是我们求学时期所发的毕业证书，大学四年熬夜苦读、凿壁偷光就是为了获得那张毕业证书，求职时，面试官透过那张毕业证书，快速验证你大学的成果。
上述例子中，你的毕业证书就是你的「工作量证明」。

以比特币为例介绍PoW:

每10~15分钟比特币网路上全体矿工会互相竞争，运用大量的运算能力去解一道复杂的数学题的答案，这个答案是一个随机数，可以想像题目大概长这样：

1	Hash｛（前一个区块的Hash 值）,（当前区块的交易资讯）,（随机数）｝＝当前区块的Hash 值

矿工必须找出一串数字，代入上述公式，让当前区块的Hash 值开头为18 个0 ，例如：

1	0000000000000000001583447dd74c13c09280a9218827244089adadaba8c8c9

解答的过程没有轨迹可循，矿工只能不断代入随机数，透过暴力的解法找出答案。

挖矿难度:

最先解开的人就能获得下一个区块的记帐权并获得比特币作为奖励。
比特币固定10~15 分钟出块一次，但是如果节点越来越多、全网算力增加，会缩短算出答案的时间。
因此，比特币协议每2016 个区块会调整一次挖矿难度，大约两个礼拜调整一次。
挖矿难度提高时，就必须找出有更多个0 的当前区块Hash 值，例如从原先的18 个0 增加到19 个0，难度降低时则相反。

算力低的矿机没机会得到记帐权？

必须强调的是，挖矿的过程其实像是掷一颗20 面的骰子，谁先骰到< 2 的数字谁就能获得计帐权.
换句话说，矿机的硬体运算能力再强大，也只能提高获得计帐权的机率（骰骰子手速比较快），算力差的矿工不代表没有机会。

很多人都认为，如果以后超级电脑普及，工作量证明不就没用了吗？
其实工作量证明数学题的难度相当高，因此取得记帐权的机会就像抽奖一样，即便某人拥有超级电脑，也只能够提高机率。
这就像在湖里丢一枚硬币，让一万个人去找这枚硬币，就算你是奥运游泳选手，也未必能第一个找到这枚硬币，只能提高找到的机率。

Trash Bin

StudyRecord-GoBlockchain_Tutorial_Part2_ProofOfWork