Proof of Work

目前，已经有了一个基本的区块链结构了。但是现在谁都可以向区块链中添加区块，因此需要一个机制来筛选谁来为区块链添加方块。这个机制就是 工作量证明（ Proof of Work, PoW) 。这个设计是 BTC 去中心化，抗攻击，安全的基础。
这里的工作证明是什么

工作就是大家常说的挖矿，而挖矿的本质就是通过计算寻找符合条件的 Nonce ， Nonce 是区块链的区块头（Block Header）中，Nonce 是一个 32位（4字节）的整数字段。 Block Header 中只有 Nonce 是可以不断调整的值，，直到满足网络的难度要求（即哈希值小于目标值）。

Proof of Work

区块链的一个关键点是，一个人必须完成一些困难的工作，才能讲数据存入数据库中。完成这个工作保证了区块链安全和一致。完成这个工作的人，也会获得相应的奖励。
在区块链中，是通过网络中的参与者（矿工）不断的工作来支撑起了整个网络。矿工不断地向区块链中加入新块，然后获得相应的奖励。在这种机制的作用下，新生成的区块能够被安全地加入到区块链中，它维护了整个区块链数据库的稳定性。值得注意的是，完成了这个工作的人必须要证明这一点，即他必须要证明他的确完成了这些工作。
这里努力工作的证明，就叫 工作量证明(PoW) 。工作需要大量计算，所以即使是高性能的计算机也不能很快速的完成。另外，技术的发展，这个工作的难度会越来越大，以保证每 10 分钟挖出 1 个区块的速度。

hashing

哈希计算是指获取一个数据哈希的过程。哈希是数据的唯一标识，类似于数据的身份证号码。对于同一段数据，同一个哈希函数，得到的哈希结果也是一样的，而不的数据在同一个哈希函数下，得到的哈希结果不同。
哈希的关键特征：

无法从一个哈希值恢复原始数据，也就是说，哈希不是加密，它无法解密。
对于特定的数据，只能有唯一的一个哈希，并且这个哈希也是唯一的。
即使只改变一个字符，哈希计算出来的结果也会完全不相同，没有规律。

在区块链中，哈希被用在保证块的一致性。将前一个块的数据通过哈希计算获取哈希，放在当前块的最前面，因此几乎不可能去修改区块链中前面的数据，如果一个人想要修改前面的某一个块，那么他必须要重新计算这个块以及后面所有块的哈希。

Hashcash

BTC 使用的是 Hashcash，这最初是一个用来防止垃圾邮件的算法。它分为一下的步骤：

取一些公开的数据（ Email 里通常是接收者的邮件地址；在 BTC 中，通常是区块的头部）。
添加一个计数器 counter ，这通常从0 开始。
获取 data 和 counter 的哈希。
检查一下哈希是否符合条件：
1. 如果符合条件，结束
2. 如果不符合条件，增加计数器，重复步骤 3-4

以邮箱为例，它就是要求发邮件的人在发送之前完成一定的计算任务，以此来做为 工作量证明 。例如发送前先将收件人的地址和 Nonce 等数据连接在一起，进行哈希计算，然后调整 Nonce ，使哈希满足前导零数量要求，接收方验证计算的合法性，这样可以增加攻击者的成本，减少滥用。这里的 Nonce 就是计数器， Nonce 是一个密码学术语。

因此，这是一个暴力算法：改变 Nonce 或者 counter ，哈希计算，检查，修改计数器，一直重复，直到达到目标。这就是为什么说计算成本高，因为本身哈希计算的成本就相对普通计算来说比较高，还需要不断的重复。

在原始的 Hashcash 上，它会要求哈希满足前导零数量 >= Bits / 4 （每 4 Bits 对应 1 个十六进制零）。

例如： Bits = 20 ，则要求知道有 5 个十六进制的前导零（20 / 4 =5）。

对于 BTC 来说，它的要求则是根据矿工的数量和算力动态调整的，以保证每十分钟生成一个区块。

Implementation

首先需要定义挖矿的难度：

const TargetBits = 24

在 BTC 中， TargetBits 是在 Blocker Header 中存储的，用来定义区块被挖出的难度。如果它的值是 10 ，则表示哈希的前 10 个前导数必须是 0 ，如果是24 ，则表示哈希的前 24 个前导数必须是 0 。这里没有算力的变化，也没有矿工，因此定义一个常量。
BTC 的动态调整规则的，它是根据最新生成的区块的时间减去上一个区块的时间，动态调整。

type ProofOfWork struct {
	Block  *blockchain.Block
	target *big.Int
}

func NewProofOfWork(b *blockchain.Block) *ProofOfWork {
	target := big.NewInt(1)
	target.Lsh(target, uint(256-TargetBits))

	pow := &ProofOfWork{b, target}

	return pow
}

这里创建了一个 ProofOfWork 的结构体用来指向块的指针和指向 target 。这里的 "target" 就是前面的目标，将区块的哈希转换成一个大整数，和它进行比较，如果哈希小于目标，则说明成功挖到矿了。
在 NewProofOfWork 中，初始化一个大整数，然后左移 256 - TargetBis 位，256 是哈希算法 SHA-h56 的哈希位数。 BTC 使用的也是 SHA-256 。Target 的十六进制数的表示是：

0x10000000000000000000000000000000000000000000000000000000000

它在内存中占 29 个字节。
字符 "I like donuts" 的 SHA-256 结果为:

f80867f6efd4484c23b0e7184e53fe4af6ab49b97f5293fcd50d5b2bfa73a4d0
0000010000000000000000000000000000000000000000000000000000000000

它的结果比 Target 要大，因此，这不是一个有效的 PoW 。而 "I like donutsca07ca" 的哈希结果是：

0000002f7c1fe31cb82acdc082cfec47620b7e4ab94f2bf9e096c436fc8cee06
0000010000000000000000000000000000000000000000000000000000000000

它的结果比 Target 要小，因此这是一个有效 PoW 。
可以把目标值看作是一个边界，只要小于这个边界，那就是有效的，只要大于这个边界，那就是无效的。

现在写一个准备哈希数据的函数：

func (pow *ProofOfWork) prepareData(nonce int) []byte {
	data := bytes.Join(
		[][]byte{
			pow.Block.PrevBlockHash,
			pow.Block.Data,
			IntToHex(pow.Block.Timestamp),
			IntToHex(int64(TargetBits)),
			IntToHex(int64(nonce)),
		},
		[]byte{},
	)

	return data
}

将这里的数据全部拼接起来，这里的 nonce 就是前面 Hashcash 说的计数器。

再然后就是最重要的 PoW 算法了：

func (pow *ProofOfWork) Run() (int, []byte) {
	var hashInt big.Int
	var hash [32]byte
	nonce := 0

	fmt.Printf("Mining the block containing \"%s\"\n", pow.Block.Data)

	for nonce < math.MaxInt64 {
		data := pow.prepareData(nonce)
		hash = sha256.Sum256(data)
		hashInt.SetBytes(hash[:])

		fmt.Printf("\r%x", hash)

		if hashInt.Cmp(pow.target) == -1 {
			fmt.Printf("\r%x", hash)
			break
		} else {
			nonce++
		}
	}
	fmt.Printf("\n\n")
	return nonce, hash[:]
}

首先定义一个变量 hashInt ，这是 hash 的整数表示形式， nonce 是计数器。然后做一个无限循环，限制大小为 big.MaxBase 以防止溢出。循环中，准备数据，然后计算哈希，将哈希转换为一个整数，最后和目标进行对比，知道小于目标值。

现在的哈希需要在里面加上 PoW ，因此前面的 SetHash 函数可以删除或者注释掉了， Block 结构体需要在里面加上 Nonce ，而 NewBlock 函数需要在里面加上 Pow ，因此需要修改

type Block struct {
	Timestamp     int64
	Data          []byte
	PrevBlockHash []byte
	Hash          []byte
	Nonce         int
}

func NewBlock(data string, prevBlockHash []byte) *Block {
	block := &Block{time.Now().Unix(), []byte(data), []byte(prevBlockHash), []byte{}, 0}
	// block.SetHash()
	pow := proofofwork.NewProofOfWork(block)
	nonce, hash := pow.Run()

	block.Hash = hash[:]
	block.Nonce = nonce

	return block
}

这里 nonce 被保存在 Block 中， nonce 可以用来证明你的工作量。

重新运行项目：

Mining the block containing "Genesis Block"
00000001fe0390daad62fd570077bfffa7bca5838252c1821d5cc850c6330946

Mining the block containing "Send 1"
00000039b5f5483dbe087f4674c58431a0ad66083d68c090e499d62047eb5565

Mining the block containing "Send 2"
00000015f0d30557d087551c072acda4905c6dd9977f2fd7082e43fbd5feece0

Mining the block containing "Send 3"
000000c986a66a6e859c96928f0d55d46489abf5c394f4362e6a4b92bdac65e3

Prev. hash: 
Data: Genesis Block
Hash: 00000001fe0390daad62fd570077bfffa7bca5838252c1821d5cc850c6330946

Prev. hash: 00000001fe0390daad62fd570077bfffa7bca5838252c1821d5cc850c6330946
Data: Send 1
Hash: 00000039b5f5483dbe087f4674c58431a0ad66083d68c090e499d62047eb5565

Prev. hash: 00000039b5f5483dbe087f4674c58431a0ad66083d68c090e499d62047eb5565
Data: Send 2
Hash: 00000015f0d30557d087551c072acda4905c6dd9977f2fd7082e43fbd5feece0

Prev. hash: 00000015f0d30557d087551c072acda4905c6dd9977f2fd7082e43fbd5feece0
Data: Send 3
Hash: 000000c986a66a6e859c96928f0d55d46489abf5c394f4362e6a4b92bdac65e3

现在，哈希的开头有许多 0 。

最后就是需要验证工作了。

func (pow *ProofOfWork) Validate() bool {
	var hashInt big.Int

	data := pow.prepareData(pow.Block.Nonce)
	hash := sha256.Sum256(data)
	hashInt.SetBytes(hash[:])

	isValid := hashInt.Cmp(pow.target) == -1

	return isValid
}

在 main 函数中添加验证的方法。

func main() {

	...

	for _, block := range bc.Blocks {

		...
		
		pow := blockchain.NewProofOfWork(block)
		fmt.Printf("PoW: %s\n", pow.Validate())
		
		...
	}
}

最后加了个一个计时器，挖三个区块就用了快五十分钟:(

Mining the block containing "Genesis Block"
00000078b9de817a51773255985ee8f0013c3a653280f12d4f60c4309fb0d74d

Mining the block containing "Send 1"
0000006cf3226aa8ab3fbe2771f2b2a5c49e13a7e0ffae3014c540bf47d2ed5f

Mining the block containing "Send 2"
0000001553ed175a610ad68a538084651baa2ca4e5b8e408708ce3ea49e9064f

Mining the block containing "Send 3"
0000009418fca42d1fe3489204d8ce374f98c0cdab898a489ef883077eeb5a2b

Prev. hash: 
Data: Genesis Block
Hash: 00000078b9de817a51773255985ee8f0013c3a653280f12d4f60c4309fb0d74d
PoW: true

Prev. hash: 00000078b9de817a51773255985ee8f0013c3a653280f12d4f60c4309fb0d74d
Data: Send 1
Hash: 0000006cf3226aa8ab3fbe2771f2b2a5c49e13a7e0ffae3014c540bf47d2ed5f
PoW: true

Prev. hash: 0000006cf3226aa8ab3fbe2771f2b2a5c49e13a7e0ffae3014c540bf47d2ed5f
Data: Send 2
Hash: 0000001553ed175a610ad68a538084651baa2ca4e5b8e408708ce3ea49e9064f
PoW: true

Prev. hash: 0000001553ed175a610ad68a538084651baa2ca4e5b8e408708ce3ea49e9064f
Data: Send 3
Hash: 0000009418fca42d1fe3489204d8ce374f98c0cdab898a489ef883077eeb5a2b
PoW: true

Time-consuming 46m4.7701423s

这里显示的也是 true ，说明 PoW 被验证了。

Proof of Work ​

Proof of Work ​

hashing ​

Hashcash ​

Implementation ​

Proof of Work

Proof of Work

hashing

Hashcash

Implementation