DAY 18- 杂凑函数 SHA-256

「SHA SHA， SHA SHA SHA SHA」

SHA-256是SHA-2家族里输出位元为256的杂凑函数，
也是比特币区块链所使用的杂凑函数。
我们来看他怎麽运作的。

SHA-256

1.填充 PADDING

第一件事情是补足位数，也就是除了原先有的讯息，
我们要把讯息後面加上1後再加上一堆0，
直到总长度是512位元的倍数减掉64位元。
而被减掉的那64位元，用来写上原讯息的位元长度。

2. 初始值 INITIAL VALUES

设定初始值，初始值是2, 3, 5, 7, 11, 13, 17, 19开根号後的小数点後前32位元。

h0 = 0x6a09e667
h1 = 0xbb67ae85
h2 = 0x3c6ef372
h3 = 0xa54ff53a
h4 = 0x510e527f
h5 = 0x9b05688c
h6 = 0x1f83d9ab
h7 = 0x5be0cd19

还要储存64个回合常数，
分别是前64个质数开三次方根後，小数点後前32位元的值，计做 K[0] 到 K[63]。

3. 扩散

每512位元为一个区块。
将填充後的讯息每32位元分成一堆，称为word
每个区块会有16个word。
在这16个word後面，我们要再加上48个word。

这48个word的生成方式如下：
for i from 16-63

• s0 = (W[i-15] rightrotate 7) XOR (W[i-15] rightrotate 18) XOR (W[i-15] rightshift 3)
• s1 = (W[i- 2] rightrotate 17) XOR (W[i- 2] rightrotate 19) XOR (W[i- 2] rightshift 10)
• W[i] = W[i-16] + s0 + W[i-7] + s1

进行完以上步骤後，我们会有64个word，其中16个是原始的，48个是加上去的。

4. 压缩

先初始化向量(a, b, c, d, e, f, g, h)等於当前的杂凑值(h0, h1, h2, h3, h4, h5, h6, h7)

for i from 0 - 63

• S1 = (e rightrotate 6) XOR (e rightrotate 11) XOR (e rightrotate 25)
• choose = (e and f) XOR ((not e) and g)
• t1 = h + S1 + choose + K[i] + W[i]
• S0 = (a rightrotate 2) XOR (a rightrotate 13) XOR (a rightrotate 22)
• maj = (a and b) XOR (a and c) XOR (b and c)
• t2 = S0 + maj
• h = g
• g = f
• f = e
• e = d + t1
• d = c
• c = b
• b = a
• a = t1 + t2

接着将将结果加上原本的h，之後进行下一个区块

h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e
h5 = h5 + f
h6 = h6 + g
h7 = h7 + h

如此重复一直计算直到每个区块都结束。
就会得到一个最终的 h0-h7。
只要把h0-h7放在一块（concatenate），就是最终结果。

以上就是 SHA-256 的演算法内容，是不是超级复杂的。
我个人觉得他有点像 AES 的那种位元调换来调换去的那种感觉，
不过复杂了许多。

所以可以想到的是电脑跑的速度有多快了，
每一次矿工在进行运算时，
都要跑遍以上的所有步骤，然後运算过超级多次之後才有可能冒出一个符合条件的，
而且还有高机率被别人抢走。

看完详细的介绍，再来看维基百科的图，大概就能理解了（吧？）。

图片来源：
https://medium.com/biffures/part-5-hashing-with-sha-256-4c2afc191c40
https://zh.wikipedia.org/wiki/SHA-2