比特币（三）：区块链中的哈希算法
1. Hash算法图
Hash算法，特别是SHA256算法，用于区块Hash值（即挖矿过程）。 比特币系统本身就是加密算法的衍生物。
2. SHA256算法流程
这篇文章主要简单介绍一下SHA256算法的过程，下篇文章会简单讲一下它的理论基础。
1.输入信息x
SHA256 要求数据包长度不能超过 2^64bit。
2.填充
因为采用了块加密方式，每组的长度为512bit，原始信息x不一定是512的倍数，也就是说可能不能准确划分为每组为512bit的情况。 这时候就需要更换了。
先在x后面加一个1，然后再加0比特币 算法，直到总长度（x和补数）模512为448
3.化妆长度
为什么不在第二步直接把总长度填成512的倍数呢，因为后面还要加上64位来记录原始信息x的位数。 (64 + 448) % 512 = 0。可见，只有64位表示原始信息x的位数，所以x的最大长度为2^64。
4.计算Hash值
消息被加成512的倍数，总长度变成512 * N。计算哈希值的基本思路是：先将处理后的消息分成N个512bit的数据块：M[1]比特币 算法， M[2], ..., M[N]，然后逐个处理：哈希初始值H[0]通过第一个数据块M[1]得到H[1]，H[1]得到H [2]通过第二个数据块M[2]，...，依次处理，最终得到H[N]。 每个hash值，比如H[0]，由8个32bits组成，32bits又叫words，也就是说每个hash值由8个words组成。 最后将H[N]的8个字连成一个256bit（8 * 32 bit）的最终值。 至于为什么可以这样，我们会在下一篇文章中介绍，先来看一下过程。
1）哈希初始值H[0]
SHA256算法中使用的哈希初始值H[0]（共8个32bits）为：
H[0][0] = 0x6A09E667
H[0][1] = 0xBB67AE85
H[0][2] = 0x3C6EF372
H[0][3] = 0xA54FF53A
H[0][4] = 0x510E527F
H[0][5] = 0x9B05688C
H[0][6] = 0x1F83D9AB
H[0][7] = 0x5BE0CD19
0x表示十六进制，十六进制中的一位表示4bit。
注：这些初值取自自然数中前8个质数2、3、5、7、11等的平方根小数部分的前32位。
2）周期计算
# M的下标从1开始，M即为M[1], ..., M[N]
for i in range(1, N + 1):
# 第一步，先根据16个32bit的原始消息，生成64个32bit
W = [0] * 64
for t in range(0, 64):
if t < 16:
W[t] = M[i][t]
else:
W[t] = SSIG1(W[t - 2]) + W[t-7] + SSIG0(W[t-15]) + W[t-16]
# 第二步，将上次的hash值，也就是8个32bit，赋值到8个临时变量，用这8个临时变量计算
# 原本的hash值在本轮结束的时候仍然需要使用
a = H[i - 1][0]
b = H[i - 1][1]
c = H[i - 1][2]
d = H[i - 1][3]
e = H[i - 1][4]
f = H[i - 1][5]
g = H[i - 1][6]
h = H[i - 1][7]
# 第三步，执行散列计算，内循环是64轮，使用了上面的64个W，以及提前定义好的64个K
for t in range(0, 64):
t1 = h + BSIG1(e) + CH(e, f, g) + K[t] + W[t]
t2 = BSIG0(a) + MAJ(a,b,c)
h = g
g = f
f = e
e = d + t1
d = c
c = b
b = a
a = t1 + t2
# 第四步，将本轮经过64个内循环新计算的临时值和上次的hash值求和，作为本轮最终的hash值
H[i][0] = a + H[i - 1][0]
H[i][1] = b + H[i - 1][1]
H[i][2] = c + H[i - 1][2]
H[i][3] = d + H[i - 1][3]
H[i][4] = e + H[i - 1][4]
H[i][5] = f + H[i - 1][5]
H[i][6] = g + H[i - 1][6]
H[i][7] = h + H[i - 1][7]
# 最终H[N]的8个32bit返回，即为该消息的SHA256结果
3）函数和常量说明
(1) 64个常量K为：
K = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 ]
注：这些常量的值是从自然数中前64个质数的立方根的小数部分的前32位得到的。
（2）用到的函数有：
# 本段代码没有使用python语法
CH(x, y, z) = (x AND y) XOR ((NOT x) AND z)
MAJ(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
BSIG0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x)
BSIG1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x)
SSIG0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x)
SSIG1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x)
其中，除了AND或NOT之外，XOR是异或，ROTR^n是循环右移n位，SHR^n是n位右移。
三、总结
以上就是SHA256的计算过程。
