2 工作量证明

引言

在上一章节中,我们利用非常简单的数据结构构建了blockchain数据库。Block之间存在链式关系:每个block都保存上一个block的链接。但是,我们的blockchain实现存在一个严重的问题:添加block操作过于简单。而区块链和比特币系统的主旨是让新增block成为一个高成本的操作。接下来,我们将修改这个问题。

POW

天道酬勤是blockchain的核心思想之一,即要想将block放到blockchain中,是需要付出一定努力的。这确保blockchain的安全性和一致性。与此同时,也会受到相应的奖赏(整个过程称作挖矿)。
这种机制与现实生活有异曲同工之妙:努力工作挣钱从而维持生计。在blockchain中,参与者(矿工)努力工作(挖矿)添加block进而获取奖励,从而维持整个blockchain网络。挖矿使block安全地加入blockchain,维持了整个blockchain的稳定。值得注意的是,挖矿是需要某种方式来证明的。
上述机制被称作“工作量证明”(即PoW)。PoW需要大量算力,即使是高性能计算机也不能非常快速地完成计算。此外,PoW随着时间的推移,难度也相应增加。
此外,PoW算法必须满足一个要求:工作量难度很高,但证明很容易。由于往往是其他人进行验证工作量,因此“快速证明”十分重要。

Hash 哈希

本节我们来讨论下hash,如果你熟悉hash,可以跳过此节。
hash是对于某个特定数据获得其hash值得过程。对于某个数据其hash值实唯一的。hash函数以随意长度数据作为输入,输出特定长度的hash值。对于hash来说,需要具备以下特性:
  • 从hash值中无法恢复出原始数据。然而,hash并不是加密;
  • 对于某个特定数据,hash值是唯一的;
  • 输入数据即使改变一个字节,其hash值也会大不相同
Hash函数被广泛的用于数据一致性检查。例如,软件开发者提供软件包的同时,也会附带一个校验码。下载软件包后,可以使用hash函数计算出该软件包的hash值,并与软件开发者提供的校验码进行对比验证。
在blockchain中,hash用于保证block一致性。block的hash计算依赖于上一block的hash值。若想修改blockchain中的一个block,就需要把其后所有block全部重新计算一遍,这将消耗大量的算力(目前看是天文数字),这是得修改block变得非常非常困难,几乎不可实现。

Hashcash算法

比特币使用Hashcash算法进行工作量证明,该算法一开始用于反垃圾邮件。该算法分为以下步骤:
  • 获取某种公开数据data(在反垃圾邮件场景下,使用收件人地址;在比特币中,使用block头信息)
  • 使用一个计数器counter,初始化为0
  • 计算data+counter的hash值
  • 检查hash值是否满足某种要求
    • 满足,结束
    • 不满足,counter加1,然后重复3-4步骤
这是个暴力型算法:改变counter值,计算得到新hash值,判断该值是否满足要求,不满足,再改变counter值,再计算,再检查…如此反复尝试直到得到满足要求为止,要求很高的算力。
来我们看看hash要满足什么要求,hashcash最初实现中,hash值要满足“头20个bit全部为0”的要求。比特币设计中,hash值要求是动态变化的,随着时间和矿工的增多,算力要求也越来越多。
为了展示算法,使用上面示例中的数据(“I like donuts”),不停的计算该数据+counter的hash值,直到找到一个满足要求(“前3个字节为0”)的hash值为止,如下图所示:
“I like donutsca07ca”中的ca07ca是十六机制格式的值,即counter从0递增到13240266时计算得到满足要求的hash值。

实现

OK,纸上谈兵到此为止,接下来实现该机制。首先,让我们来定义挖矿的难度:
  • const targetBits = 24
比特币中,“target bits”在block头信息中,表示该block被挖到的难度。我们并不实现难度自调整算法,而是定义一个全局的难度。
“target bits”只要小于256(因为我们要使用sha256算法计算hash值)即可,我们设置为24。这意味着,当hash值的前24位均为0即满足要求。当“target bits”过大时,满足要求将非常困难,因为符合条件的数据总数量变得非常小,因此需要更长时间计算才有可能得到满足要求的hash值。“target bits”的值越大难度越高,值越小难度越低。
256 位 转成16进度就是 256/4=64个16进制, 相当于长度是64位. 1的16进制是
000000000000...(63个0)1,  1 << 232 相当于 000001000(后面58=232/4个0), 即:
  • 0000010000000000000000000000000000000000000000000000000000000000
代码:
  • type ProofOfWork struct {
  •     block  *Block
  •     target *big.Int
  • }
  • func NewProofOfWork(b *Block) *ProofOfWork {
  •     target := big.NewInt(1)
  •     // Lsh sets z = x << n and returns z.
  •     // func (z *Int) Lsh(x *Int, n uint) *Int {
  •     // 相当于 target << (256-24) target左移了 232 位
  •     target.Lsh(target, uint(256-targetBits))

  •     pow := &ProofOfWork{b, target}

  •     return pow
  • }
ProofOfWork结构包括一个block指针和一个target指针。“target”表示困难度,其类型为big.Int,之所以使用big结构是为了方便和hash值做比较检查是否满足要求。
NewProofOfWork方法中,将target初始化为1,然后将其左移(256-target),其值为:
  • 0x10000000000000000000000000000000000000000000000000000000000
该值在内存中占用29字节,接下来将其与之前示例中的hash值进行比较:
  • 0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
  • 0000010000000000000000000000000000000000000000000000000000000000
  • 0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca
上面有3个hash值,第1行是“I like donuts”计算得到hash值,第2行是目标值(1 << 232),第3行是基于“I like donutsca07ca”计算得到的hash值。
  • 第1行值大于目标值,不满足要求;
  • 第3行值小于目标值,满足要求,结束证明。
总结一下,hash值满足要求的规则:
  • 当hash值大于目标值,表示不满足要求;
  • 当hash值小于等于目标值,表示满足要求。
prepareData方法将block各个字段和nonce(counter值)作为输入,计算得到hash值作为输出:
  • 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
  • }
准备工作一切完毕,接下来实现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 < maxNonce {
  •         data := pow.prepareData(nonce)
  •         hash = sha256.Sum256(data)
  •         fmt.Printf("\r%x", hash)
  •         hashInt.SetBytes(hash[:])
  •         /*
  •         // Cmp compares x and y and returns:
  •         //
  •         //   -1 if x <  y
  •         //    0 if x == y
  •         //   +1 if x >  y
  •         //
  •         func (x *Int) Cmp(y *Int) (r int)
  •         */
  •         // 计算出的hash与目标hash比较 == -1 表示 hashInt < target
  •         if hashInt.Cmp(pow.target) == -1 {
  •             break
  •         } else {
  •             nonce++
  •         }
  •     }
  •     fmt.Print("\n\n")

  •     return nonce, hash[:]
  • }
最初,初始化变量:hashInt是hash值得整数形式;nonce是一个递增计数器,初始化为0。接下来,开始进行循环计算, nonce和maxNonce(设置为math.MaxInt64)进行比较,直到找到符合要求的hash值为止。
循环中进行如下操作:
  • 准备数据
  • 使用SHA-256算法计算hash值
  • 将hash值转换为整数
  • 整型hash值与目标值作比较
接下来,删除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
  • }
大功告成!让我们运行看看效果吧:
  • Mining the block containing "Genesis Block"
  • 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1

  • Mining the block containing "Send 1 BTC to Ivan"
  • 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804

  • Mining the block containing "Send 2 more BTC to Ivan"
  • 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe

  • Prev. hash:
  • Data: Genesis Block
  • Hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1

  • Prev. hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1
  • Data: Send 1 BTC to Ivan
  • Hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804

  • Prev. hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804
  • Data: Send 2 more BTC to Ivan
  • Hash: 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe
可以看到,所有block的hash值前3个字节均为0,同时生成block时需要花费一定时间。
目前还有一件事需要做,就是对工作量进行验证:
  • 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数据。
再运行一次,一切OK:
  • func main() {
  •     ...

  •     for _, block := range bc.blocks {
  •         ...
  •         pow := NewProofOfWork(block)
  •         fmt.Printf("PoW: %s\n", strconv.FormatBool(pow.Validate()))
  •         fmt.Println()
  •     }
  • }
输出:
  • ...

  • Prev. hash:
  • Data: Genesis Block
  • Hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
  • PoW: true

  • Prev. hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038
  • Data: Send 1 BTC to Ivan
  • Hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
  • PoW: true

  • Prev. hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b
  • Data: Send 2 more BTC to Ivan
  • Hash: 000000e42afddf57a3daa11b43b2e0923f23e894f96d1f24bfd9b8d2d494c57a
  • PoW: true
提示: 大家在本地运行的时候可以将24调小点, 比如20, 不然生成一个还是比较费时间的.

总结

我们的blockchain日趋成熟:现在添加block需要一定工作量,挖矿成为可能。但是仍然缺少一些关键特性:blockchain是非持久化的,没有钱包、地址、交易,缺乏一致性机制。所有这些特性将在后续章节实现。现在让我恩先尽情享受挖矿的乐趣吧!

本文来自 gitbooks zhangli1的书一章, 他翻译自Ivan Kuznetsov的系列文章《Building Blockchain in Go》,原文地址: https://jeiwan.cc . 程序代码都在 https://github.com/Jeiwan/blockchain_go中.

我在阅读和实践中, 为本文做了一些注解以便更好的理解.

有任何问题欢迎在下方评论讨论.

立即登录, 发表评论.
没有帐号? 立即注册