哈希研究所 | 区块链技术浅析（二）：哈希函数

哈希函数是指一种数学运算过程，它接受一个任意大小的输入值，经过一些运算后可以迅速给出一个确定的固定长度的输出值，这个输出值可以作为输入值的数字指纹.

正如双胞胎拥有独一无二的指纹一样，哈希函数被设计成具有相同的属性：即使输入值的微小差异也会导致哈希函数结果的巨大差异。 此外，哈希函数没有任何启发式算法，输入和输出之间的关系似乎是完全随机的。 比如给定一个输出结果，要求对应的输入值应该是，或者要求输出结果小于某个值。 值，问一个合格的输入值应该是多少，解决这些问题没有技巧和方法可循，只能通过不断的尝试，尝试的次数越多，就越有可能找到答案。

我们可以利用散列函数的这些性质来实现很多功能。 例如数据保护：数据的内容和数据的哈希值一起发送哈希算法与比特币，接收方对接收到的数据进行哈希运算，通过比较可以知道数据是否被篡改。 又如，网站在用户登录时，可以将用户密码的哈希值存储在数据库中，并与用户输入的密码哈希值进行比对，以验证身份。 好处是如果数据库泄露，黑客无法传递这些哈希值。 使用哈希值推导出用户密码相对安全。

值得注意的是，哈希函数的输入集合是无限的，而由于输出长度是固定的，所有可能的输出集合都是有限的。 根据鸽巢原理：将n+1个元素放入n个集合中，其中必有一个集合至少有两个元素。 因此，理论上两个不同的输入值具有相同的哈希值是可能的，但幸运的是，这种事情发生的概率很小，哈希函数也在不断完善中。 SHA1 函数曾被密码分析者发现。 为了找到有效的攻击方法，包括比特币在内的当前系统采用了更先进的SHA2系列算法。 比特币多年的良好运行，说明至少SHA256算法至今经受住了考验。 此外，连续多次使用散列函数是一个更安全的选择。

哈希函数在比特币中被用到很多地方，可以说起到了非常关键的作用。

1. 压缩验证交易信息

由于区块链要处理的交易信息量巨大，如果直接将每个区块中的所有数据按顺序存储，效率非常低且耗时，但可以通过哈希函数对信息进行压缩和验证. 使用默克尔树可以快速验证某笔交易是否属于某个区块。 其简化示意图如下。 对于打包成一个区块的所有交易，首先将其分成几个部分，如下图交易信息1所示。 交易信息2……并计算出对应的哈希值1、哈希值2……然后将两者结合起来进行哈希运算，最终得到默克尔树的根哈希值。 如果某个交易信息中记录的数据发生变化，最终计算出的Merkle根哈希值也会不同。

图 1 比特币中的 Merkle 树

那么为什么要使用这样的算法，而不是直接将所有的交易信息串成一个大块，计算它的哈希值呢？ 原因是这样的二叉树结构可以只允许少量的数据验证，同时如果交易数据信息有误，可以快速定位错误位置。

2. 用于证明工作量，形成共识

为什么说区块链不可篡改？ 先考虑一个简单的哈希链如下：每个包中包含前一个区块的哈希值和本区块的相关信息。 如果某个区块的信息被篡改，那么后续所有区块的哈希值都会发生变化，其他人也会注意到这一变化。 但这种设计的问题在于，任何人都可以修改某个区块上的信息，重新计算剩余链中的所有信息，并声称这是正确的链。

比特币设计的美妙之处在于，它使得这样一个过程的实施成本很高。 它采用工作量证明的共识机制。 大家通过比赛来证明自己完成了一定的工作量，谁先完成，谁就获得记账权。 工作量是指要求找到一个随机数，使得给定的字符串与它相加后计算出的哈希值小于某个值。 在比特币中，这个给定的字符串包含版本号、前一个区块的哈希值、存储在 Merkle 根哈希值中的交易信息、时间戳和难度值信息。

当矿工找到符合要求的随机数后，不仅“合法”宣告自己的记账权，还通过哈希函数完成交易信息的编码，并以不可篡改的方式存储。 如果有人试图更改交易信息，他一定非常幸运，能够在未来快速成功地为链条的每个区块找到正确的随机数，使他篡改信息后的链条成为当前最长的链条。 这种情况理论上是有可能的，但是在算力有限的情况下，概率比较小。

3 用于生成比特币钱包地址

在比特币交易中，大家能看到的信息如下哈希算法与比特币，左上角是交易号，绿色箭头连接的两个字母和数字的字符串是比特币地址，说明比特币在两个地址之间有转移。 而这个地址是钱包的公钥通过哈希函数转换生成的。 公钥是对由随机数组成的私钥进行非对称加密形成的。 公钥和比特币地址都需要在交易过程中公开发布，以便区块链系统验证支付交易的有效性。

图2 比特币转账示意图

哈希函数在这里发挥的作用相当巧妙：量子计算机可以很容易地从公钥中推导出私钥，但是量子计算机很难找到两个不同的输入值时具有相同的哈希值面对哈希算法，可以说中本聪的设计通过一些操作让比特币抵御量子计算机的威胁成为可能：比如每个比特币地址只被使用一次，每次支付都转移到别人的地址和你自己的更改地址中间。

从以上可以看出，中本聪通过巧妙的设计，很好地利用了哈希函数的特点，最终形成了一个运行良好的系统，涉及到多种学科交叉，也启示我们需要抽象在技​​术创新上，要从事物的本质出发，注意与其他领域的相互融合。 随着技术的进步，新的哈希函数也在不断被大家设计和测试。 哈希函数的发展可以说是“路高一尺，魔高十尺，永无止境”。

想复习哈希研究所往期文章的同学，链接在这里：

行业研究系列文章：

技术洞察系列文章：

深度思考系列文章：

哈希每周系列：