哈希函数 · Elea Notes

下面从一个你能立刻感觉到的麻烦讲起，一步步走到它为什么必须长成那样。

先看一个麻烦：你怎么确认一本书没被人动过

我抄了一本一千页的书寄给你。路上要经过好几个人的手，其中可能有人改了一个字——把”不可以”改成”可以”，把某个数字的小数点挪了一位。

你收到之后，怎么确认它和我寄出时一字不差？

最直接的办法：你手上再放一本原书，逐字对。但这就绕回去了——你要是已经有原书，我为什么还要寄给你。这个循环是整件事的要害：验证不能依赖”已经拥有你想验证的东西”。

第二个办法：我另寄一张纸，写上”全书共 482,913 个字”。你数一遍，对得上就放心。这个办法的好处是那张纸很小，坏处是它太弱了：改字的人只要改字不改数，比如把”不可以”改成”可不以”，字数分毫不差，你完全看不出来。

朴素尝试为什么都不够

顺着”寄一张小纸条”的思路往下想，很自然会试这几招。它们全都会失败，而失败的方式恰好告诉我们真正的解法必须满足什么。

招数一：数字数。 上面说了，改字不改数就穿了。

招数二：把所有字的笔画数加起来。 比刚才强一点，但仍然很容易糊弄——把两个字互换位置，总和不变。任何”加起来”的办法都有这个通病：加法不在乎顺序。

招数三：每页取第一个字，拼成一张 1000 字的小抄。 这下顺序敏感了，但覆盖不到：每页除了第一个字之外的所有字，改了都发现不了。

招数四：把整本书压缩一下寄过去。 压缩确实能变小，可它必须可还原，所以信息一点没少——一千页的书压完还是几百页的量级，你还是得收下几乎同样多的东西。

四次失败凑出了三条硬要求。小纸条必须：

很小，且不管原文多大都一样小——否则不如直接寄原书；
牵一发动全身——改任何一个位置，纸条上的内容都得变；
不可还原——它小到根本装不下原文，所以注定丢掉了绝大部分信息。

第 3 条听起来像缺点，其实是第 1 条的必然结果：一千页压成一行，信息必须丢。而正是”丢得彻底”让这张纸条可以公开贴出来，不怕泄露书的内容。

满足这三条的东西就叫哈希函数，那张小纸条叫哈希值（或摘要、指纹）。

机制：亲手算一个小号的

真正的 SHA-256 有 64 轮运算，手算不现实。但它的骨架可以用小数字跑一遍，你会看到”牵一发动全身”是怎么造出来的。

规则：把每个字符的编号乘进一个累加器，每步都取余数（% 是取余数，也就是除完剩多少）。

h = 7                        起始值，随便定的
对每个字符 c：
    h = (h * 31 + c的编号) % 1000

拿 cat 和 cta 试（a=1, c=3, t=20）：

"cat":  h=7
        h = (7*31   + 3)  % 1000 = 220     ← c
        h = (220*31 + 1)  % 1000 = 821     ← a
        h = (821*31 + 20) % 1000 = 471     ← t   结果 471

"cta":  h=7
        h = (7*31   + 3)  % 1000 = 220     ← c
        h = (220*31 + 20) % 1000 = 840     ← t
        h = (840*31 + 1)  % 1000 = 41      ← a   结果 41

同样三个字母，只换了顺序，471 和 41 毫无关系。原因在于 h 每一步都被乘了 31 再折叠——前面的改动会被后面每一步反复放大，改动越早，扩散越猛。这就是招数二（加法）缺的那样东西：乘法和取余在乎顺序，加法不在乎。

再看”变小”是怎么发生的：% 1000 强行把结果压回三位数。不管你输入三个字母还是三百万个，出来永远是 0–999 之间的一个数。代价也一并暴露了——只有 1000 个可能的输出，而输入无穷多，所以必然有不同输入撞上同一个值。

这就是为什么真家伙用 256 位而不是三位数：可能的输出有 2^256 个，大约 10^77，比可观测宇宙的原子数还多。撞车在数学上依然必然存在，但没有人能找到一例。“安全”在这里的准确含义不是”不可能”，而是”没人算得过来”。

三条性质，以及它们各自对应哪次失败

现在回头看标准说法，每一条都对得上前面某次失败：

确定性：同样输入 → 同样输出。你我各算一遍必须一致，否则纸条没法当凭证。
雪崩效应：改一个比特，输出面目全非。这是招数二、三补不上的那个洞。
抗碰撞 / 单向：找不到两份不同数据得到同一指纹，也没法从指纹反推原文。这是第 3 条硬要求，也是纸条能公开的原因。

回头看：这台绞肉机把三件事变成了同一件事

比特币里有三处看起来毫不相干的机制，其实都是上面那张小纸条：

给一批交易盖指纹——区块里所有交易压成一个指纹（做法见 Merkle 树）。改任何一笔，指纹就变。这正是”确认书没被动过”的原题。
把区块串成链——每个区块记着前一个区块的指纹。改动历史里任一区块，它之后所有指纹全部失效。所谓”链”的强度，全部来自雪崩效应。
制造可验证的成本——工作量证明要求算出一个开头有若干个零的哈希。因为没法反推，只能一个个试；而别人验证只要算一次。难做、易验这个不对称，直接来自”单向”。

也就是说，你只要真的懂了那张小纸条，这三件事不是三个知识点，是一个知识点的三种用法。

边界与常见误解

哈希不是加密。 加密可逆（有钥匙能解回原文），哈希单向、永远解不回去。所以”密码用哈希存储”是对的，“密码被哈希加密”是外行话。

“没法反推”不等于”猜不出来”。 如果原文的可能性很少（比如六位数字的密码只有一百万种），攻击者可以把所有可能挨个算一遍来比对指纹。单向性保护的是不可逆，不是不可穷举——短密码该加盐、该用慢哈希，就是为了对付穷举。

指纹相同不能百分之百保证原文相同。 前面算过，输出有限而输入无限，碰撞必然存在。工程上把 SHA-256 的指纹当成身份，靠的是”找不到”，不是”不存在”。