机器之心编辑部
哈希算法到底是什么？它又是如何运行的？Greg Walker 用视频给出了一个可视化的解答，并在 GitHub 上进行了共享，详细先容了 SHA-256 函数的事情事理。
项目链接：https://github.com/in3rsha/sha256-animation
（图片来自网络侵删）Greg Walker 喜好构建一些教诲性网站，大略易懂地讲解一些科普类算法。
他在这个阐明 SHA-256 的视频中，不仅先容了哈希打算，还涉及比特币挖矿、根本运算、函数、常量等知识。
什么是哈希函数？
哈希便是将不同的输入映射成独一无二的、固定长度的值（又称 "哈希值"），是最常见的软件运算之一。很多网络做事会利用哈希函数，产生一个 token，标识用户的身份和权限。
那它是如何运行的呢？哈希函数可以把给定的数据转换成固定长度的无规律数值。此处为方便读者理解，我们借用《我的第一本算法书》里的比喻：将哈希函数想象成搅拌机。
图源：《我的第一本算法书》
将数据 “abc” 放入搅拌机里，经由哈希函数打算后，会输出固定长度且无规律的数值，而这个无规律数值便是“哈希值”，绝大多数情形用十六进制来表示。
哈希函数有一系列特色，如上图所示，输出的哈希值与输入数据的大小、长度等没有任何关系。
若输入相同，输出的哈希值也必定相同。
如输入不同，输出的哈希值也一定不同，哪怕是只有细微差异。
在输入数据完备不同的情形下，输出的哈希值有可能是相同的，这种少数分外情形称为“哈希冲突”。
同时，哈希值是不可逆的，也便是说，通过哈希值不可能反向推算出原来的数据。
在本项目中，Greg Walker 也通过视频先容了以上几大特色。
SHA-256
SHA 包括 SHA-0、SHA-1、SHA-2 和 SHA-3 系列，SHA-256 是 SHA-2 系列的函数之一。其择要长度为 256 bits，即 32 个字节，故称 SHA-256。SHA-256 常涌现于比特币领域。
那么 SHA-256 到底是什么样的呢？Greg Walker 供应了动画展示。
动画展示 SHA-256，你也能做到
只需对须要进行 hash 处理的数据运行 sha256.rb 脚本即可。
# simpleruby sha256.rb abc
# hash binary or hex data by using `0b` or `0x` prefixesruby sha256.rb 0b01100001ruby sha256.rb 0xaabbccdd
# speed up or step through the animation (optional)ruby sha256.rb abc normal # defaultruby sha256.rb abc fastruby sha256.rb abc enter
输入二进制字符串作为参数，从而运行 SHA-256 中的各个函数：
ruby shr.rb 11111111111111110000000000000000 22ruby rotr.rb 11111111111111110000000000000000 22ruby sigma0.rb 11111111111111110000000000000000ruby sigma1.rb 11111111111111110000000000000000ruby usigma0.rb 11111111111111110000000000000000ruby usigma1.rb 11111111111111110000000000000000ruby ch.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111ruby maj.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111
你也可以利用 hash256.rb 来进行 double-SHA256，该脚本默认接管十六进制数据，如交易数据等。
ruby hash256.rb 0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a29ab5f49ffff001d1dac2b7c # genesis block header
SHA-256 的事情事理
根本运算
这里只对 SHA-256 的根本运算进行大略先容。
SHA-256 uses four basic bitwise operations on words.
SHA-256 对 words 利用 4 种 bitwise 根本运算。
右移 (shr.rb)
SHRn(x) = x >> n
将 bits 向右移动多个位置，同时从右侧移出的 bits 丢失。
向右旋转 (rotr.rb)
将 bits 向右移动多个位置，然后将移动后的 bits 放在左侧，也称为「循环右移」。
Exclusive Or (xor.rb)
x ^ y ^ z
XOR 的输入为两个 bit，如果个中只有一个为 1，则输出 1。在合并多个 bit 时通过多次 XOR 运算进行，同时得到多个 bit 的“平衡表示”（balanced representation）。
加法 (add.rb)
(v + w + x + y + z) % 232
这是非常标准的整数加法运算，唯一的不同是，此处采取结果模数为 2^32，从而将结果限定为 32 位数字。
函数
将上述运算组合起来，就可以创建函数。
前四个函数利用希腊符号 Sigma 命名（小写σ和大写Σ）。
σ0 (sigma0.rb)
σ0(x) = ROTR7(x) ^ ROTR18(x) ^ SHR3(x)
σ1 (sigma1.rb)
σ1(x) = ROTR17(x) ^ ROTR19(x) ^ SHR10(x)
Σ0 (usigma0.rb)
Σ0(x) = ROTR2(x) ^ ROTR13(x) ^ ROTR22(x)
Σ1 (usigma1.rb)
Σ1(x) = ROTR6(x) ^ ROTR11(x) ^ ROTR25(x)
末了两个函数 “Choice” 和“Majority”可接管三个不同的输入，如下所示：
Choice (ch.rb)
该函数基于 x 位在 y 位和 z 位之间做出选择。如果 x = 1，则选择 y 位；如果 x = 0，则选择 z 位。
Ch(x, y, z) = (x & y) ^ (~x & z)
Majority (maj.rb)
该函数返回的是三个 bits 中的多数。
Maj(x, y, z) = (x & y) ^ (x & z) ^ (y & z)
压缩
该教程中还先容了很多有趣的根本知识，这里不再赘述。我们重点来看哈希函数的压缩函数，这也是其核心功能。
对付调度中的每个词，我们都利用 “状态寄存器” 中确当前值来打算两个新的临时词（设为 T_1 和 T_2）。
Temporary Word 1 (t1.rb)
T1 = Σ1(e) + Ch(e, f, g) + h + Kt + Wt
此临时词将调度中的下一个单词与列表中的下一个常量并在一起运行。
Temporary Word 2 (t2.rb)
T2 = Σ0(a) + Maj(a, b, c)
通过将状态寄存器中第一个值Σ_0 进行旋转，与前三个寄存器中的 Majority 的值相加来打算这个临时词。
压缩 (compression.rb)
在打算了两个临时词之后，将状态寄存器中的值移至下一个位置，并更新寄存器：
状态寄存器中的第一个值变为 T_1 + T_2，同时状态寄存器中的第五个值已添加了 T_1。
这即是一轮压缩，对付信息调度中的每个词该过程都会重复一次。
在压缩了全体调度之后，我们将得到的哈希值添加到初始哈希值中，由此得出块的终极哈希值。
但如果还有其他块要处理，则将当前哈希值不才一次压缩中用作初始哈希值。如下图所示：
