英文源地址

简介

在上一篇文章中, 我们构建了一个非常简单的数据结构, 这是区块链数据库的本质.并且我们可以通过它们之间的链式关系来添加区块: 每个区块都链接到前一个区块.哎, 我们的区块链实现有一个重大缺陷: 向链中添加区块既容易又便捷. 区块链和比特币的关键之一是增加新的区块是一项艰难的任务. 今天我们将修复这个缺陷.

工作量证明

区块链的一个关键思想是, 人们必须执行一些艰难的任务才能将数据放入其中.正是这项艰难的任务使区块链变得安全和一致.此外, 这种艰难的工作也会得到奖励(这就是人们miner获得比特币的方式).
这种机制于现实生活中的机制非常类似: 人们必须努力工作以获得奖励并维持他们的生活.在区块链中, 网络中的一些参与者(miner)通过工作来维持网络, 向其添加新的区块, 并获得他们的工作奖励. 由于他们的工作, 一个区块以一种安全的方式被合并到区块链中, 从而维护了整个区块链数据库的稳定性.值得注意的是,完成工作的人必须证明这一点.
这整个’努力工作并证明’的机制成为工作量证明. 这很难, 因为它需要大量的计算能力: 即使是高性能的计算机也无法快速完成. 此外,这项工作的难度会不断增加, 以保持每小时6个区块的新区块产量.在比特币中, 这种工作的目标是为一个区块找到一个哈希值, 满足一些要求. 这个哈希值可以作为证明. 因此, 寻找证明才是真正的工作.
最后要注意的是, 工作量证明算法必须满足一个要求: 做工作很难, 但是验证工作证明很容易. 证明通常交给其他人, 所以对他们来说, 不应该花太多时间来验证它.

哈希函数

在这一小节, 我们将讨论哈希(散列)函数.如果你熟悉这个概念, 可以跳过这一部分.
散列函数是为指定数据获取散列的过程. 哈希值是计算数据的唯一表示.哈希函数是一种接受任意大小的数据作为输入并生成固定大小的哈希值的函数.下面是哈希函数的一些关键特性:

不能从散列值恢复原始数据. 因此, 哈希操作不是加密操作
同样的数据只会有一个哈希值, 并且哈希值是唯一的
即使更改输入数据中的一个字节也会导致完全不同的哈希值

散列函数被广泛用于检查数据一致性.一些软件提供商除了发布软件包之外还会发布校验和.下载文件后, 您可以将其提供给散列函数, 并将生成的散列值于软件开发人员提供的散列值进行比较.
在区块链中, 哈希操作被用来保证区块的一致性.哈希算法的输入数据包含前一个区块的哈希值, 因此不可能(或至少相当困难)修改链中的区块: 必须重新计算其哈希值和之后所有块的哈希值.

Hashcash

比特币使用的是Hashcash, 这是一种工作量证明算法, 最初是为了防止垃圾邮件而开发的. 它可以分为以下几个步骤:

以一些公开的数据(如果是电子邮件, 则是收件人的电子邮箱地址; 就比特币而言, 他就是区块头部信息)
给它添加一个计数器. 计数器从0开始计数.
获取数据+计数器组合的哈希值
检查哈希值是否满足一定的要求:
1.如果满足, 就完成了
2.如果不满足, 增加计数器并重复3,4步骤

因此, 这是一个蛮力算法:你改变计数器, 计算一个新的哈希值, 检查它, 增加计数器, 计算一个哈希值, 等等.这就是为什么它在计算机上代价很高的原因.
现在让我们仔细看看散列值必须满足的条件.在最初Hashcash实现中, 这个要求听起来像是’哈希的前20位必须为零’. 在比特币中, 这一要求是随着时间调整的, 因为根据设计, 尽管计算能力随着时间的推移而增加, 越来越多的miner加入网络, 但必须每10分钟生成一个区块.
为了演示这个算法, 我从签名的例子中(‘i like donuts’)中获取数据, 并找到一个以3个零字节开头的哈希值. 在这里插入图片描述
ca07ca是计数器的十六进制值, 在十进制中对应的是13240266.

实现

好了, 我们讲完了理论, 开始写代码吧!首先, 让我们来定义miner的难度:

const targetBits = 24

在比特币中. '目标位’是存储区块开采难度的区块头.我们现在不会实现目标调整算法, 所以我们可以将难度定义为一个全局常数.
24是一个任意的数字, 我们的目标是在内存中占用少于256位的target数值.我们希望差值足够明显, 但又不会太大, 因为差值越大, 就越难找到合适的哈希值.

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

func NewProofOfWork(b *Block) *ProofOfWork {
	target := big.NewInt(1)
	target.Lsh(target, uint(256-trgetBits))
	
	pow := &ProofOfWork{b, target}
	return pow
}

在这里创建一个ProofOfWork结构, 它保存一个指向区块的指针和一个指向目标的指针.'target’是前一段描述的需求的另一个名称. 我们使用一个大整数, 因为我们将哈希值与target目标值进行比较: 我们将哈希值转换为一个大整数, 并检查它是否小于目标值.
在NewProofOfWork函数中, 初始化一个big.Int, 赋值为1并左移(256-targetBits)位.256是SHA-256哈希值的长度, 以bit为单位, 我们要使用的是SHA-256散列算法.target的十六进制表示为

0x10000000000000000000000000000000000000000000000000000000000

它占用了内存29个字节.下面是它与前面例子中的哈希值的视觉对比

0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
0000010000000000000000000000000000000000000000000000000000000000
0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca

第一个哈希值(根据’I like donuts’计算)比目标值大, 因此它不是有效的工作量证明. 第二个哈希值('根据’I like donutsca07ca’计算)比目标值小, 因此它是一个有效的证明.
你可以将目标值视为范围上的上边界: 如果一个数字(哈希值)低于该边界, 则它是有效的, 反之亦然.降低边界将导致更少的有效数字, 因此寻找有效数字所需的工作会更加困难.
现在,我们需要对数据进行哈希值求解, 让我们准备一下:

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合并. nonce是上面Hashcash算法描述中的计数器, 这是一个密码学术语.
好了, 所有的准备工作都完成了, 让我们来实现PoW算法的核心:

func (pow *ProofOfWork) Run() (int, []byte) {
	var hashInt big.Int
	var hash [32]byte
	nonce := 0
	maxNonce := math.MaxInt64
	fmt.Printf("Mining the block containing \"%s\"\n", pow.block.Data)
	for nonce < maxNonce {
		data := pow.prepareData(nonce)
		hash = sha256.Sum256(data)
		fmt.Printf("\r%x", hash)
		hashInt.SetBytes(hash[:])
		
		if hashInt.Cmp(pow.target) == -1 {
			break
		} else {
			nonce++
		}
	}
	fmt.Print("\n\n")
	return nonce, hash[:]
}

首先, 初始化变量: hashInt是hash值的整数形式.nonce是计数器值.接下来, 我们运行一个’无限’的循环:它受maxNonce的限制, 它等于math.MaxInt64; 这样做是为了避免nonce可能的溢出.尽管我们的PoW实现的难度太低, 计数器不会溢出, 但最好还是有个检查, 以防万一.
在循环中,我们:

准备数据
用SHA-256算法计算hash值
将哈希值转换为大整数
将该整数值与目标值进行比较

和之前解释的一样简单. 现在我们可以删除Block的SetHash方法并修改NewBlock函数:

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

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

在这里我们看到nonce被保存为Block的属性.这是必要的. 因为需要nonce来验证证明. Block结构现在是这样的:

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

好了!让我们运行程序看看是否一切正常:

Prev. hash:
Data: Genesis Block
Hash: 0000005d42343f4f2aef73a27ed617c7b61768b87fdf9705b588db99477c4fb9

Prev. hash: 0000005d42343f4f2aef73a27ed617c7b61768b87fdf9705b588db99477c4fb9
Data: Send 1 BTC to Ivan
Hash: 000000fbcdefd2389096e73d2c3af7ad11d6c17d59756dd848bfaddfe3c3ac1b

Prev. hash: 000000fbcdefd2389096e73d2c3af7ad11d6c17d59756dd848bfaddfe3c3ac1b
Data: Send 2 more BTC to Ivan
Hash: 000000d01d9fa49f97f5abd759d1ae59cee4f36044117754a9347f7414ec4980

耶!你可以看到, 现在每个散列都以三个零字节开始, 并且需要一些时间来获得这些散列值.
还有一件事要做: 让我们使得验证工作量证明成为可能.

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
}

这就是我们需要保存nonce的原因.
让我们再检查一次, 确保一切正常.

func main() {
	bc := NewBlockchain()

	bc.AddBlock("Send 1 BTC to Ivan")
	bc.AddBlock("Send 2 more BTC to Ivan")

	for _, block := range bc.blocks {
		fmt.Printf("Prev. hash: %x\n", block.PrevBlockHash)
		fmt.Printf("Data: %s\n", block.Data)
		fmt.Printf("Hash: %x\n", block.Hash)
		fmt.Println()

		pow := NewProofOfWork(block)
		fmt.Printf("Pow: %s\n", strconv.FormatBool(pow.Validate()))
		fmt.Println()
	}
}

输出结果

Prev. hash:
Data: Genesis Block
Hash: 00000074c46066dc882a455694f6457f18ce4552153c58d4c7c94c97b420c405

Pow: true

Prev. hash: 00000074c46066dc882a455694f6457f18ce4552153c58d4c7c94c97b420c405
Data: Send 1 BTC to Ivan
Hash: 000000bb4739f0563ef910e16afd8b6f1fe3d1837e355b22714c388b2b73506e

Pow: true

Prev. hash: 000000bb4739f0563ef910e16afd8b6f1fe3d1837e355b22714c388b2b73506e
Data: Send 2 more BTC to Ivan
Hash: 000000d7ae7d8736aa04542d09c58fc6bbc6437a21e4ad23bafe4d6ef140c8d2

Pow: true

总结

我们的区块链离实际框架又近了一步: 添加区块现在需要经过艰难的工作, 因此miner是可行的. 但它仍然缺乏一些关键性功能: 区块链数据库没有持久化存储, 没有钱包, 地址, 事务, 也没有共识机制.我们将在之后的文章中实现所有这些功能, 现在, 祝您miner愉快!

links:
https://github.com/Jeiwan/blockchain_go/tree/part_2
https://en.bitcoin.it/wiki/Block_hashing_algorithm
https://en.bitcoin.it/wiki/Proof_of_work
https://en.bitcoin.it/wiki/Hashcash