比特币挖矿算法

比特币网络中，源源不断的收到交易，需要节点不断的打包这些交易，而网络中的所有节点都是对等的，如何判断谁可以打包这些交易，如何避免重复打包这些交易呢？

这个时候就需要用到工作量证明（PoW，Proof-of-Work）的方式决定记账权。

网络中的任何全节点，都可以试图创建区块，但区块只有在至少满足下列条件时创建的区块才会被其他节点认可和接受。

  • 区块中包含的交易都是合法的；
  • 区块哈希要小于等于一个目标值；

要满足第一个条件很简单，节点只要将每笔交易都验证一遍，丢弃掉不合法的交易即可。但要满足第二个条件就需要挖矿。

挖矿

比特币挖矿就是找到一个随机数（Nonce）参与哈希运算Hash（Block Header），使得最后得到的哈希值符合难度要求，用公式表示就是 Hash（Block Header）<= target。

比特币采用的哈希算法是 SHA-256 ，也就是说最后会产生256位的输出，一共2^256种可能的取值。

最后得到的哈希值小于target的意思是把哈希后得到的bytes转换成数字后小于target转换成的数字。

举个例子，直观的感受一下挖矿的难度：

下面这段字符是比特币第1000个区块的哈希，2009年1月产生：

00000000c937983704a73af28acdec37b049d214adbda81d7e2a3dd146f6ed09
可以看到前面有8个0，虽然哈希值的生成是随机的，但是生成前面有8个0的值对计算机穷举来说也并不算太难。

再看一下这段字符，是比特币第560000个区块的哈希，2019年1月产生：

0000000000000000002c7b276daf6efb2b6aa68e2ce3be67ef925b3264ae7122
可以看到前面有18个0，要生成满足这个条件的哈希对于普通电脑来说几乎是不可能完成的任务了。

简单来看挖矿难度的高低就是生成区块头的哈希值有多少0。

挖矿难度

在比特币系统中出块时间被设置为一个常数10分钟，但是挖出区块的速度并不是固定的，而是随着挖矿难度的变化在10分钟上下浮动， 挖矿难度越大，出块时间就越长，为了得到相对平均的出块时间，需要动态调整挖矿难度。

比特币每产生2016个区块调整一次挖矿难度，一个块10分钟，2016个块大概是两周的时间，而调整挖矿难度的这些逻辑都在代码中，当大多数诚实节点采用这个策略的时候整个网络就会自动遵循这个策略。

挖矿难度的计算公式如下：

diffculty = difficulty_1_target / target

此处的 difficulty_1_target 为一个常数，非常大的一个数字（ 2^(256-32)−1 ）。表示挖矿的初始难度，目标值越小，区块生成难度越大。

2^(256-32)−1 是比特币的初始难度，是前2016个块的难度。

这个难度被存储在比特币的区块头nBits字段中，当有恶意节点篡改这个策略时，挖矿产生的区块头的哈希值就会和诚实节点产生冲突，不会被接收，白白浪费了算力。

因为策略不同，也就是nBits不同，恶意节点产生的区块哈希无法被诚实节点验证。

调整出块时间

比特币系统中区块的生产速度是根据之前产生区块速度调整的，之前出块速度大于10分钟，则认为需要降低难度，则需要提高第一个公式中target的值，而target则通过如下公式计算；

target  =  current_target  *  ( actual time  /  excepted time )

current_target是当前系统中的难度值，target是调整后的难度值，actual time是实际产生区块的时间，excepted time是期望出块时间（2016块*10分钟），actual time有上下限，actual time最多8周，最小二分之一周。

挖矿算法

比特币中nBits标识了挖矿的难度，也就是说这个区块头进行SHA-256哈希算法后得到的bytes转换成数字后要小于这个难度，而SHA-256计算后的结果有256位，如果直接存储需要32个字节比较占用空间，所以采用了一种压缩算法。

压缩算法

nBits有4个字节32位，将SHA-256计算得到的值经过如下算法压缩到32位；

  1. 将数字转换为 256 进制。
  2. 如果第一位数字大于 127（0x7f），则前面添加 0。
  3. 压缩结果中的第一位存放该256进制数的位数。
  4. 后面三个数存放该256进制数的前三位，如果不足三位，从后补零。

举个例子，将十进制1000压缩;

1. 1000转换256进制数，1000 = 3 * 256 + 232 = 3*256^(2-1) + 232*256^(1-1)
2. 3小于127，不需要补0，跳过
3. 从第一部看到1000转换成256位数有2位，压缩结果第一位应该存放2
4. 因为只有两位，所以最后一位补0，得到存放的值为 [2, 3, 232, 0]十进制，转换十六进制 [0x02, 0x03, 0xe8, 0x00] 合并存储到nbits为 0x0203e800

难度计算

在第一个公式中difficulty_1_target的值为 2^(256-32)-1,转换成256进制为；

FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

第一位大于0x7f，前面补0，变为

00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

其长度等于 28+1=29 (0x1d)，且长度超过三位，无需补零，则压缩结果为：0x1d00FFFF，因为压缩存储容量只有才4个字节，前两字节已经被长度和添加的 00 所占用，只剩下2个字节来存储数字，这样后面的26个 FF 值被丢弃。

T=0x00FFFF * 256^(0x1b-3) = 0x00000000FFFF0000000000000000000000000000000000000000000000000000

比特币中的difficulty就是0x1d00FFFF，如果区块中的nBits为0x1d00FFFF则说明这个区块挖矿难度为最小挖矿难度1.

实际上专业的矿池程序会保留被截断的FF：

00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

我们算一下比特币101799号区块的挖矿难度，通过区块链浏览器可以看到101799号区块的nBits为0x1b0404cb

D = 0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF / 0x00000000000404CB000000000000000000000000000000000000000000000000 = 16307.669773817162 (pdiFF)

pdiFF也被称为矿池难度。

算力

为了找到符合条件的值在挖矿的时候需要不断的调整区块头中Nonce的值，但是又会有一个问题，在比特币中Nonce的值是32位的，如果挖矿难度太大，就算穷尽Nonce的所有可能还是不能算出符合条件的值。

铸币交易

在一个区块产生的时候，会有一个铸币交易（coinbase），也就是矿工为自己铸币，产生新的比特币。

铸币交易没有UTXO输入，只有输出指向自己的比特币地址，当挖矿成功，这个区块被网络接收的时候，新产生的币就转移到这个矿工地址了。

看一下铸币交易包含的字段；

  • transaction hash：“交易哈希”字段32个字节全部填充0（因为其没有UTXO输入）；
  • ouput index：“交易输出索引”字段全部填充0xFF(十进制的255)；
  • coinbase data：coinbase数据长度最小2字节，最大100字节。除了开始的几个字节外，矿工可以任意使用coinbase的其他部分，随意填充任何数据。以创世块为例，中本聪在coinbase中填入了这样的数据“The Times 03/Jan/ 2009 -Chancellor on brink of second bailout for banks“； - coinbase data size：coinbase数据大小；
  • sequence number：现在未使用，设置为0xffffffff

可以看到铸币交易的coinbase data字段是我们可以控制的，当Nonce不能满足挖矿难度的时候，我们可以通过调整coinbase data字段，从而影响区块头的默克尔树根的值，提供更多的可能来满足挖矿难度的要求。

算力单位

通过上面的流程，进行一次可能的挖矿尝试被称为H。

1 H/s = 每秒可执行一次哈希运算。

1 KH/s = 每秒1,000哈希（一千次）。

1 MH/s = 每秒1,000,000次哈希（百万次）。

1 GH/s = 每秒1,000,000,000次哈希（十亿次）。

1 TH/s = 每秒1,000,000,000,000次哈希（万亿次）。

1 PH/s = 每秒1,000,000,000,000,000次哈希。

1 EH/s = 每秒1,000,000,000,000,000,000次哈希。

挖矿收益

矿机挖矿的时候就会出现很长的时间找不到符合条件的哈希值，如果找不到哈希值不能打包区块就没有收益，显然对矿工十分不友好，但是如果挖到就像中彩票一样获得非常丰厚的回报。

矿池

为了避免单个矿工挖矿收益的不稳定性，就出现了矿池，矿池集合了大量的矿工，平均挖矿的收益，避免了挖矿收益的不稳定性。 矿池组织大量的矿工挖矿面临很重要的一个问题就是如何把高难度计算哈希的任务拆解成相对简单的任务，发送给单个矿工，回顾之前挖矿难度的计算，可以简单的认为前面0的多少表明了挖矿的难易。 0越多，挖矿难度越高，为了降低挖矿难度我们就要增加挖矿哈希0的数量，举个例子

假设挖矿目标值  0x000abc，只要满足这个值就可以打包区块获得挖矿收益；
降低挖矿难度为 0x001abc，发送给矿工，矿工只要计算区块头满足这个相对低一点的难度就可以得到一个分片（shared），但是单个矿工挖到这个简单难度的块是无法发布到整个网络中的，但是矿池可以把这个分片记录下来，作为以后给这个矿工奖励的凭证。
0x001abc是0x000abc的子集，只要子集足够多总有一个会满足目标值。
当有一个矿工挖出一个满足目标值之后就可以获得挖矿收益，而挖矿就可以根据矿工分片多少来获得收益。

矿工收益 = 挖矿收益 / 挖到的分片数量

但是现在还有一个问题没有解决，单个矿工挖到目标值以后如果私吞收益，私自广播区块怎么办？

矿池有集中托管式的，也有分布式的。

  • 集中托管式矿池，矿工可以把挖矿的机器托管给矿池，由矿池统一操作维护，只需要支付一些电费管理费即可，这样就避免了私自广播。
  • 分布式矿池，矿工将机器自行管理，通过矿池协议从网络连接矿池即可，这样就会出现私自广播的可能。

回顾一下铸币交易coinbase，可以看到有output字段，UTXO模型中币的来源都是上一个交易的output，所以可以把铸币交易的output字段设置为矿池的地址，然后随机生成一些coinbase data的填充后生成区块头的默克尔树，最后发由矿工去尝试目标值。

通过这样的方式，即使矿工找到满足条件的哈希值，铸币交易的地址也是矿池的地址，私自广播区块没有任何收益，如果调整铸币交易的地址，这样又回到了独立挖矿的场景。

全网算力

如果要获知全网算力，可以通过出块时间，挖矿难度大致反推出全网算力。

区块确认

当一个区块产生之后，它不是立即可信的，网络上的节点总是相信最长的区块链，当一条交易记录被打包进一个区块之后，就有了一个确认，而这个区块所在的链后面被再加入一个区块，就是第二个确认，如此下去，一个交易有了6个确认，我们就认为这个交易已经确定了，会被永远记录在区块链中。 为什么是6个确认呢？因为每一个确认就是一个挖矿过程，需要大量的工作量证明，因此，这6个区块被同一个矿工创建的可能性微乎其微（可以说是不可能），因此矿工伪造交易也基本不可能。

由于比特币的区块平均产生时间是10分钟，所以一个交易要1小时左右才能保证成功（最快），不过也不是所有的系统都这样认为，有些网站在接受比特币支付时，认为4个确认就可以给客户发货了，区块确认越多则越难被逆转。

区块广播

在区块链中，为了尽快收到其他节点的信息，节点间并不是直接传递区块信息的。 节点向附近节点发送一个Inv消息，Inv消息中包含已经被发送者（sender）接收并验证过的“交易记录的哈希”、以及“区块哈希”。接收者（receiver）收到Inv消息后，如果他还尚未从其他节点收到过相同的信息，他会发送一个getdata消息给发送者，要求得到交易记录及区块哈希包含的具体信息。此时，区块和交易记录的信息才会进行整体传递。 其中Inv消息结构如下；

type MsgInv struct {
    InvList []*InvVect
}

type InvVect struct {
    Type InvType // Type of data
    Hash chainhash.Hash // Hash of the data
}

PoW，全称Proof of Work，即工作量证明，又称挖矿。大部分公有链或虚拟货币，如比特币、以太坊，均基于PoW算法，来实现其共识机制。即根据挖矿贡献的有效工作，来决定货币的分配。  比特币区块 ...