区块链核心技术--密码学原理之哈希函数

上篇文章，我们简单介绍了下区块链，带到了几项区块链的核心技术，其中密码学中的哈希是重中之重，今天我们来挖挖哈希是个什么鬼。

01
什么是 Hash

Hash（哈希），又称“散列”。简单来讲就是个函数求解的过程，这个函数叫哈希函数。

哈希函数（Hash Function），也称为散列函数或杂凑函数。哈希函数是一个公开函数，可以将任意长度的消息M映射成为一个长度较短且长度固定的值H（M），称H（M）为哈希值、散列值（Hash Value）、杂凑值或者消息摘要（Message Digest）。它是一种单向密码体制，即一个从明文到密文的不可逆映射，只有加密过程，没有解密过程。

它的函数表达式为：h=H（m）

无论输入是什么数字格式、文件有多大，输出都是固定长度的比特串。以比特币使用的Sh256算法为例，无论输入是什么数据文件，输出就是256bit。

每个bit就是一位0或者1，256bit就是256个0或者1二进制数字串，用16进制数字表示的话，就是多少位呢？

16等于2的4次方，所以每一位16进制数字可以代表4位bit。那么，256位bit用16进制数字表示，当然是256除以4等于64位。

于是你通常看到的哈希值，就是这样的了：

00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8

。

02
特点+作用

1、Collision resistant-碰撞阻力：即不会出现输入 x≠y ，但是H(x)=H(y) 的情况.

如果一个函数有两个不同的输入，但都能产生相同的输出，这就叫碰撞。一个哈希函数具有碰撞阻力（或者叫有抗碰撞性），就是说该函数当有两个不同的输入时，没有人能够找到碰撞，我们就称该函数具有碰撞阻力。

请注意，我说的是没有人能够找到碰撞，我可没说不存在碰撞。实际上，哈希函数的碰撞是不可避免的，因为输入是任意长度的字符串，输出是固定长度的字符串，输入无限但输出有限，一定会产生碰撞。对一个256位输出大小的哈希函数，如果我选择2²⁵⁶+1个输入，产生了2²⁵⁶个输出，那么至少会产生一次碰撞。实际上，根据概率学中的生日悖论，我们只要随机选择2¹³⁰+1个输入值，至少会产生一次碰撞的概率是99.8%。那为什么哈希函数还可以用呢？就是因为，算出碰撞来是需要花很长很长时间的。比如对于一个256位输出的哈希函数来说，如果我们要进行2¹³⁰次哈希计算，如果一台电脑每秒能计算1万个哈希值，则我们需要花4*10¹⁹亿年。请注意，单位是“亿年”，宇宙自宇宙大爆炸以来到现在不才存在了138亿年吗？所以，从理论上，世界上没有一个哈希函数是具有防碰撞特性的，但有些函数是具有很大的碰撞阻力的。我们实践中所使用的加密哈希函数就是人们经过不懈地努力之后仍没有找到碰撞的函数。

比特币应用的SHA 256算法就是一个具有很强碰撞阻力的加密哈希函数。举两个例子：

是不是很神奇？给大家推荐一个网址：
http://tool.oschina.net/encrypt?type=2
这是一个SHA在线加密算法工具，有兴趣的朋友可以去试一下。

作用：防篡改
一个加密哈希函数如果具有碰撞阻力，对于两个不同的、任意大小的输入，会产生两个不同的、固定大小的输出，这个输出值就可以用来作为输入值的信息摘要（Message Digest）。举个例子，如果我在网络上存储了一个文件，过了一段时间，我想知道这个文件有没有被别人所篡改，我就可以在上传时用这个文件作为加密哈希函数的输入，然后得到一个输出，我记录下来这个哈希值。过一段时间，我下载网络上的这个文件，计算其哈希值，并与原来的哈希值进行对比。如果相同，说明该文件没有被篡改；如果不同，就说明该文件被篡改了。因此，加密哈希函数就为我们提供了一个记住之前所见的所有事物，并在今后确认该事物是否已经产生变化的有效方法。

2、Hiding-隐匿性：也就是说，对于一个给定的输出结果 H(x) ，想要逆推出输入 x ，在计算上是不可能的。如果想要得到 H(x) 的可能的原输入，不存在比穷举更好的方法。

作用：sealed envelope
举例: 有人说能预测股市，那有什么办法检验预测是否准确呢？我们有两种方法：
方法一：公开预测，然后第二天等收盘的时候大家再确认收盘的结果。但是这里有个问题，预测结果有可能会被该公开言论影响。
方法二：把预测结果放到一个信封里头，封存起来（sealed envelope），第二天再打开看。

在数字世界中我们怎么操作实现sealed envelope呢，把预测结果信息作为x，算出H（x），把H（x）公布出去即可，由于存在隐匿性，x将不被暴露。等结果公布后，然后我们拿着H（x）就能追溯x（预测信息），因为它还存在碰撞阻力的特性，这个信息没法篡改。说到这里是不是想起一个比特币中的应用--公钥生成比特币的地址。

其实比特币应用的哈希函数还有一个特性叫Puzzle Friendly-谜题友好，意思是说：哈希值的计算事先是不可预测，光是看输入，很难猜出结果，如果想要哈希值是落在某个范围内，那没有别的方法，只有暴力求解。例如说，你想得到前面K位都是0的哈希值，你没有其他办法，只能暴力求解。这里我们不做重点介绍。

补充知识点--哈希函数的暴力求解

如果知道哈希值H（X）真想找到输入值 X，只能从源头出发，一个数一个数去尝试，每个数都套到哈希函数里，然后看看输出的哈希值是不是等于H（X）。

就像如果你真想知道某个指纹是谁的指纹，你只能全世界一个个人找过去，去对比每一个手里的指纹和这个指纹，是不是完全相同，没有丝毫偏差。

哈希函数因为这三个特性成了利器，帮助在设计比特币的路上解决了多个难题，在比特币白皮书中，除了简介和结论的 10 个章节里，几乎每个章节都能看到哈希函数的使用。

用哈希函数的唯一性用来防止作假——数字签名
用哈希函数的唯一性来提升效率——默克尔树检索交易记录
用哈希函数的单向性用来保密——公钥生成比特币的地址

用哈希函数的暴力求解来设计比特币的工作量证明——当范围足够大的时候，拿着指纹去找指纹拥有人是不可能的事情，但如果把范围缩小呢，比如在一个只有几百万人的城市里找，难度就会小很多，这就是比特币的挖矿难度调整机制，想要难度高一点那就把范围扩大一点，想要难度低一点就把范围缩小一点。

1953 年哈希函数出现，1970 年哈希函数蓬勃发展，2001 年 SHA-256 出现，在 2008 年时，哈希函数成为了区块链技术里不可撼动的基石。

至此，虽然比特币白皮书中技术原理你只是懂了一个基础知识哈希函数，但这一点都不妨碍你理解了比特币白皮书里 50%想要表达的内容。

推荐阅读：
Blockchain 区块链基础知识[h1][/h1]（强烈推荐▲▲▲▲▲）