最近无意中在知乎上看到一个问题:是否能够通过手算的方式来进行比特币挖矿? 这个问题看似荒谬,但其实早在前几年就有人提到过,并且确实有人对此进行了验证(来源:http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html ,回答中那篇Gizmodo的文章也是转载于此)。答案是:可以,但算力最多仅有0.67hash/天。事实上,挖矿的主要过程就是在进行一轮又一轮的SHA-256运算,因此通过手算的方式进行模拟,可以对SHA-256算法有一个比较深刻的理解,这才是我们想要达到的目的。

BTC的生成过程

“挖矿”这个词表面上来看似乎是在“挖”BTC,但从本质上来说,这个过程实际上是在创造一个获得了全网参与者认可的区块,作为奖励,系统将凭空生成固定数量的BTC,发放给这个有效区块的创建者(即矿工),我们来看一个标准的BTC区块结构:

挖矿的本质过程,是找到下面这个不等式的一个解:

SHA256(SHA256(versionprev_hashmerkle_rootntimenbitsX))<TARGETSHA256(SHA256(version \sim prev\_hash \sim merkle\_root \sim ntime \sim nbits \sim X))<TARGET

其中version、prev_hash、merkle_root、ntime、nbits就是上图中的版本号、前一区块Hash值、Merkle根、时间戳和当前比特币协议设定的计算复杂度,连接之后形成初始输入。TARGET则可以用来调整难度,越小则难度越大。

具体来说,求解过程如下:

  • 首先将系统中若干最近发生的交易记录打包成块(上图中的灰色部分);
  • 通过Merkle Tree算法生成Merkle Root Hash作为这组交易记录的摘要,连同上面不等式的其他参数形成固定80字节大小的区块头(上图中的浅黄色部分);
  • 然后,不停变换区块头中的Nonce值,每次变换后都对区块头做两次SHA256运算。如果小于目标值TARGET,则此时区块头的Hash值为若干个0开头,表明求解成功,最终暴力求解得到的Nonce即为上面不等式的解X。

一旦矿工找到了X,就可以向BTC网络广播这个新的区块,其他客户端会验证此区块是否合法。如果区块被接受,则系统将固定数量的BTC奖励发放至矿工的钱包中,并将此条记录置于该区块所有交易记录的顶端。例如这个区块就是一个已经获得认可的完整区块。

SHA-256哈希算法

上面已经说过,对不等式进行暴力求解的过程就是在不停地进行SHA-256哈希运算,在运算之前,需做以下准备工作:

  • 首先对输入的数据进行处理。假设数据长度为LL(二进制),首先在末尾添加“1”,然后填充k个0,使得(L+1+k)(L+1+k)与512求余得448。例如字符串"abc"从8位ASCII码转换为二进制后,一共有24位,那么一共需要填充448-(24+1)=423个0。最后将数据长度转换为64位二进制,并添加至末尾。如图所示:

​ 这样处理后的数据长度就刚好是512位的整倍数。

  • 假设处理后的数据长度为N512N*512,共M1M^1MNM^N 个块,每一块再以32位长度切分为16个子块,即第iiMM块切分为M0iM^i_0, M1iM^i_1M15iM^i_{15} ,子块均使用高位编址(Big Endian)
  • 将前8个子块标记为A、B、C、D、E、F、G、H,进行如下图所示的逻辑运算(来自Wikipedia):

即:Ch(E,F,G)Ch(E,F,G)Ma(A,B,C)Ma(A,B,C)0(A)\sum0(A)1(E)\sum{1}(E)

其中:

Ch(E,F,G)Ch(E,F,G) :即Choosing,对E、F、G每一位进行比较,如果此位上的E为1,则输出F,如果E为0,则输出G。例如Ch(0101,1001,0001)Ch(0101,1001,0001) ,第一位上的E为0,输出G(为0),第二位上的E为1,输出F(为0),以此类推,最终结果为00010001

Ma(A,B,C)Ma(A,B,C) :即Majority,对A、B、C的每一位进行比较,如果1的个数大于0的个数,则输出1,反之输出0。例如Ma(0110,1010,0010)Ma(0110,1010,0010) ,第一位上0的个数较多,第二位上0的个数较多,第三位上1的个数较多,第四位上0 的个数较多,则最后的结果为00100010

0(A)\sum{0}(A) 表示:将块A右移2位、13位、22位后,将三次的结果取异或;

1(E)\sum{1}(E) 表示:做上面类似的异或运算,只是右移位数变为6位、11位、25位;

另外还需要有常量WtW_tKtK_t 参与运算,其中WkW_k 的取值与每一轮有关(1-16轮总是等于该轮中的MtiM^i_t ,16轮后需进行移位及迭代,具体参见官方文档:SECURE HASH STANDARD,第19页),KtK_t 则为常量(前64个质数的立方根小数前32位,16进制表示)。

然后开始运算,第t轮的具体过程为:

  • 计算Wt+Kt+Ht+Ch(Et,Ft,Gt)+1(Et)W_t{+}K_t{+}H_t{+}Ch(E_t, F_t, G_t)+\sum1(E_t) ,得到中间值T1T_1
  • 计算0(At)+Ma(At,Bt,Ct)+T1\sum0(A_t)+Ma(A_t, B_t, C_t)+T_1 ,得到下一轮的At+1A_{t+1}
  • 计算Dt+T1D_t+T_1,得到下一轮的 Et+1E_{t+1}
  • 此轮的AtA_tBtB_tCtC_t 为下一轮的Bt+1B_{t+1}Ct+1C_{t+1}Dt+1D_{t+1}
  • 此轮的EtE_tFtF_tGtG_t 为下一轮的Ft+1F_{t+1}Gt+1G_{t+1}Ht+1H_{t+1}

特别地,对于第1轮,初始A、B、C、D、E、F、G、H为固定常量,规定为前8个质数的平方根小数前32位,16进制表示。

最后,每一次SHA-256运算需做64轮循环,共2次SHA-256运算,即128轮循环。以下将展示1轮循环的具体过程。

开始挖矿

为了展示清晰,用表格对相应过程进行说明。

准备工作

取前8个质数的平方根、前64个质数的立方根,并将小数部分前32位转换为16进制,得到初始A、B、C、D、E、F、G、H,以及常量K:

准备输入。对于第1轮,输入的前32位(或8位16进制)必定为区块版本号,即02000000

开始计算

将初始值填入A、B、C、D、E、F、G、H中(红字),除D和H外均转换为二进制,同时在这一步就可以得到下一轮的B、C、D、F、H、G(绿色标注):

对E、F、G进行Choose运算Ch(E,F,G)Ch(E, F, G) ,每一位上的选择均用黑框标注出,同时将结果转化为16进制:

将E右移6位、11位、25位,做异或运算,得到1(E)\sum1(E) ,同样将结果转换为16进制:

对A、B、C做Ma(A,B,C)Ma(A, B, C) 运算:

将A右移2位、13位、22位后做0(A)\sum0(A) 运算:

计算中间值T1T_1 ,即W1+Kt+H+Ch(E,F,G)+1(Et)W_1+K_t+H+Ch(E, F, G)+\sum1(E_t) ,此时W1W_1 等于M11M^1_1 ,即版本号02000000

T1=02000000+428A2F98+5BE0CD19+1F85C98C+3587272B=F577ED68T_1=02000000+428A2F98+5BE0CD19+1F85C98C+3587272B=F577ED68

用以下式子计算下一轮的A:

newA=0(A)+Ma(A,B,C)+T1=CE20B47E+3A6FE667+F577ED68=FE08884Dnew A=\sum0(A)+Ma(A, B ,C)+T_1=CE20B47E+3A6FE667+F577ED68=FE08884D

用以下式子计算下一轮的E:

newE=D+T1=A54FF53A+F577ED68=9AC7E2A2new E=D+T_1=A54FF53A+F577ED68=9AC7E2A2

将以上全部结果综合之后得到第一轮的计算过程表:

第1轮计算完毕。

后续计算

按照以上过程重复进行64轮后,将最终得到的A、B、C、D、E、F、G、H分别与8个初始值再进行一次相加,拼接8个结果即可得到第一轮的SHA-256哈希计算结果:

再进行一次SHA-256运算后,即完成第一次暴力求解。

结论

通过以上过程我们可以知道,SHA-256其实就是在做大量的二进制位移和相加运算,因此其算法可以轻易而举地由集成电路并行实现,这也是为什么现在BTC的开采都使用ASIC矿机了。与之相反的是,后来推出的Litecoin等一部分山寨币采用的则是Scrypt哈希算法,这种算法需要更多的内存,并行计算的难度也更高,因此很难直接在集成电路上实现。

文章开头提到的博客原文中,作者采用的是纸笔手算的方法,做一轮完整而正确的运算大概是16分钟(包括计算和检查等等),所以做128轮计算需要大概1.49天,也就是0.67hash/天的计算效率,在ASIC矿机面前基本等于零速度,而且就算求解出了不等式,别人早就解出来了,你的区块也不会被系统承认,所以这种方法肯定是不实际的,大家也不用去尝试了,不过用来了解SHA-256的算法细节倒是一个不错的选择(笑)。