2.6*　附：闲话Hash

2.6.1　此哈希非彼哈希

前面，我们将数据A的哈希值a视为数据A的指纹，即数字指纹a“唯一地”确定了数据A，就像指纹证据能唯一确定罪犯一样。

对于哈希，我们不陌生，例如，有5台服务器，我们希望交易在这5台服务器上均匀地分布，即负载均衡。解决方案：规定交易的某种属性x，如交易的序号、交易的账号、交易到达的时间等；规定服务器的某种属性y，如服务器编号0、1、2、3、4；构造一个哈希函数y=x（mod 5）；定义分配策略，如将交易x分配到服务器y上。

哈希函数y=x（mod 5），在方案中起到了映射作用，如图2.5所示，将7号交易和12号交易都分配到2号服务器上处理，体现了哈希的单向性。

显然，该哈希函数具有如下特性。

（1）单向：即由7能得到2，而从2不能断定是7；

（2）压缩：将成千上万的交易分配到5台服务器中，且均匀分布。

7和12都对应于2，我们说7和12产生了碰撞，负载均衡利用这种碰撞特性。只要有压缩就会产生碰撞，即使一丁点压缩。鸽笼原理是这样说的：n+1只鸽子飞向n只笼子，一定有一个笼子中有两只或两只以上的鸽子，即碰撞。这里说的是“一定”，可是当鸽子数小于笼子数时，就“不一定”了，但还是会以某种概率发生碰撞的，如40只鸽子飞向365只笼子的情况。

你可以做个测试：假定你小组有40人以上，猜测一下你小组成员是否会发生“生日碰撞”，即同一天过生日。小组不足40人？——把他女朋友算上。不想暴露生日？——那你不妨在纸上写上你的假生日。

利用碰撞进行负载均衡，但碰撞是指纹的死敌，试想若指纹有碰撞，那还能把它作为犯罪的证据吗？哈希函数的压缩特性说明哈希函数不具备防碰撞特性，但我们可以退一步，在一定的“应用范围”内，找具有“碰撞阻力”的哈希函数。这类哈希函数很神奇，虽然该哈希函数存在着碰撞，但如果在使用它的应用场景中碰不到它；故意找它难度大（至少在计算上是不可行的）。

既然是这样，那么在应用时，就可认为该类具有“碰撞阻力”的哈希函数是“无碰撞”的，其哈希值就可以作为“数字指纹”。大家熟知的MD5就是这样一个哈希函数。例如，MD5常用来做版本或文件的数字指纹，通过对下载的文件验证其数字指纹是否为指定的值，来验证版本或文件是否被篡改或版本是不是最新的。但遗憾的是，MD5强度不够，因为它是128位的。我国密码学家王小云找到了MD5产生碰撞的方法，打破了上述“故意找它难度大”的前提，直接导致了MD5逐渐被淘汰和弃用，被位数更多、强度更高的算法代替。

注意区分两类不同的哈希，本书后续提到的哈希，如无特殊说明均指“无碰撞哈希”。

2.6.2　碰撞，别发生

上节让大家做“生日碰撞”测试，不知大家感觉如何？反正一开始，我直觉上认为40人中撞生日的可能性很小，毕竟有365天。但事实上，40人中撞生日的可能性或者说概率可达89%，当人数达到100时，撞生日的可能性几乎是百分之百——99.9999%，只要人数达到23人，撞生日的可能性就超过50%了。

“撞生日”的反面是“不撞生日”，“撞生日”的概率等于1减“不撞生日”的概率，而“不撞生日”的概率易计算，假设有k个人，则他们不撞生日的概率为：

由此，我们可以得出一个结论：压缩函数一定会产生碰撞；即使减少“源”数量，发生碰撞的可能性还是很高的。那么该如何产生“碰撞阻力”呢？

2.6.3　碰撞，不会发生

我们回到上节的鸽笼例子上来，直观地理解一下产生“碰撞阻力”的方法，如图2.6所示。

首先，我们应扩大右边的目标集，即增加“笼子数”。

其次，我们应缩小左边的源集，即根据应用场景，使我们需要的图2.6粗线中的“有用子集”远小于右边的目标集。缩小方式有两个维度：一是空间，如我们的区块是有一定格式和编码要求的，这就排除了不合格的；二是时间，如一万年后的某交易与你现在的交易一毛钱关系没有，完全不用理会这种隔空发生的碰撞。

例如，一万只鸽子组成集合A1，其中有100只是有标记的鸽子集合A2，即应用的有用子集，鸽子飞向右边目标集中的一千只笼子，则可认为有标记的鸽子没有“碰撞”，也就是说，没有两只有标记的鸽子在同一只笼子中。

实际上，还是有两只有标记的鸽子飞进了同一只笼子，经查原来它们俩是夫妻，这就要重新修订飞的规则。

第三，从算法上构造办法，让鸽子的飞行相互独立，如一只一只地放飞，它不知道笼子中的情况。

有了上述三点，情形变为：

鸽子数 > > 笼子数 > > 有标记的鸽子数；分散的飞行算法。

“ > > ”表示远远大于，第一个“ > > ”会产生经常性的碰撞，如鸽笼原理，第二个“ > > ”会产生偶尔碰撞，如生日碰撞，再加上算法，产生“碰撞阻力”。

这样，鸽子就难以“碰撞”，符合抗碰撞性，即具有碰撞阻力。这就是对“避免碰撞”的简易理解。

更严格地讲，作为指纹的Hash函数应具有以下性质：

①压缩性：输入可以为任意长度的消息，而输出为固定长度的二进制串，如128bit或256bit；

②不可逆性：已知输入x，计算其Hash值h（x）容易，但已知Hash值h，要找到对应的x在计算上是不可行的；

③抗弱碰撞性：对任意的输入x，找到且满足h（x）=h（y）的y在计算上是不可行的；

④抗碰撞性：找到任意满足h（x）=h（y）的偶对（x,y）在计算上是不可行的。

回到区块链中的区块指纹，它选用的是Hash-256，是符合上述性质的256位的Hash函数。据说要破解它需要等到量子计算机之类的超强机器出现。

总结一下：基于鸽笼原理的碰撞一定存在，若应用中都是某种“特殊”鸽子，则碰撞不会发生，故意去碰撞也很难，因为算法具有抗碰撞性。

2.6.4　妙用Hash

有了上述“抗碰撞性”，我们可以认为数据A和它的Hash值a是一一对应的，它是区块链的理论基石之一。如图2.7所示，哈希值在区块链中有以下两个作用：

（1）作为指纹，用于防篡改；

（2）作为指针，用于查询。