哈希研究院区块链技术洞察之哈希函数

原创
2225 天前
12914


哈希函数是指一类数学运算过程,它接受任意大小的输入值,经过一番运算后可以很快给出一个确定的固定长度的输出值,这个输出值可以作为这个输入值的数字指纹。

正如对于双胞胎而言,他们各自的指纹也是独一无二的,哈希函数的设计使得它也具有同样的特性:即使是非常微小的输入值差别,哈希函数的运算结果也会有非常巨大的差异。除此以外,哈希函数没有任何启发式算法,输入和输出的关系看起来是完全随机的,例如给一个确定的输出结果,要求对应的输入值应该是多少,或者是要求输出结果小于某个值,问一个符合条件的输入值应该是多少,这些问题的求解没有什么技巧和方法可循,只能通过不断地进行尝试,尝试的次数越多,越有可能找到答案。

我们可以利用哈希函数的这些特性实现很多功能。

例如数据保护:将数据的内容和数据的哈希值一起发送,接收者对接收到的数据进行哈希运算,对比即可知道数据是否被篡改。再比如,网站在进行用户登录时,可以在数据库里存储用户密码的哈希值,与用户输入的密码的哈希值进行比对来验证身份,好处是如果数据库泄露,黑客也不能通过这些哈希值来反推出用户的密码,相对来说比较安全。

值得注意的是,哈希函数的输入集合是无限的,而由于输出长度固定,输出的所有可能集合是有限的,根据鸽笼原理:n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。所以两个不同的输入值有相同的哈希值理论上是一定存在的,但是好在这样的事情发生的概率非常小,而且哈希函数也在不断改进,SHA1函数就曾经被密码分析人员发现了有效的攻击方法,目前比特币在内的系统采用了更先进的SHA2系列算法,比特币多年的良好运行表明至少到目前为止SHA256算法经受了检验。此外,连续多次使用哈希函数也是一种更加安全的选择。

哈希函数在比特币中有多处运用,可以说扮演了非常关键的角色。

1. 对交易信息进行压缩和验证

由于区块链要处理的交易信息内容庞大,将每个块内的所有数据直接以序列的方式存储将会非常低效且耗时,但是利用哈希函数可以对信息进行压缩和验证。使用Merkle树可以很快验证某笔交易是否属于某个区块,它的简化示意图如下,对于打包到一个区块的所有交易,首先将它们划分为几个部分,如下图中的交易信息1、交易信息2……并计算出对应的哈希值1、哈希值2… …之后两两结合进行哈希运算,最终得到这个Merkle树的根哈希值。如果某一笔交易信息记录的数据有变化,那么最终算出来的Merkle根哈希值也会不一样。


图1  比特币中的Merkle树

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

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

为什么都说区块链是不可篡改的呢?首先考虑一个如下的简单的哈希链:每次打包时包含上一个区块的哈希值和这个区块的相关信息,如果某一个块的信息被篡改了,往后所有块的哈希值都会有变化,其他人也会注意到这个变化。但是这样设计的问题在于任何人都可以修改某一个区块上的信息,重新计算剩余链条的所有信息,并且声称这才是正确的链。

比特币设计的精妙之处在于,它使得要实现这样的过程需要付出昂贵的成本。它采用工作量证明的共识机制,大家争相证明自己完成了一定的工作量,最先完成的获得记账权。而工作量指的就是要求找到一个随机数,使得它加上一个给定的字符串后计算得到的哈希值小于某个值。在比特币中,这个给定的字符串包含了版本号、上一个区块的哈希值、以Merkle根哈希值存放的交易信息,时间戳、难度值的信息。矿工找到符合要求的随机数,既“合法”宣告了自己的记账权,也通过哈希函数完成了对交易信息的编码,并以一种不可篡改的方式存储。如果有人试图想更改交易信息,他必须运气特别好,能够快速且成功地找到往后链条的每个区块的正确的随机数,使得他篡改信息后的链条成为当前最长的链条,这样的情况理论上的确可能发生,但是在算力有限的情况下,概率比较小。

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

在比特币的交易中,大家都能看到的信息如下图,左上角是交易号码,绿色箭头连接的两个字母和数字组成的字符串是比特币地址,表明比特币在两个地址之间有了转移。而这个地址的生成是由钱包的公钥经过哈希函数转换而成的。其中公钥是由随机数字构成的私钥通过非对称加密形成的。交易时公钥和比特币地址都需要公开发布,来使区块链系统验证付款交易的有效性。

 

图2  比特币转账示意图

在这里哈希函数扮演的角色相当巧妙:量子计算机可以很容易从公钥反推出私钥,但是量子计算机在面对哈希算法时则难以找出拥有同一个哈希值的两个不同输入值,可以说中本聪的这个设计使得通过一些操作可以让比特币有可能抵御量子计算机的威胁:比如每个比特币地址都只用一次,每次付款转账到别人的地址和自己的找零地址中。

由上可见,中本聪通过巧妙的设计很好地利用了哈希函数的特性,并最终形成了一个良好运转的系统,这当中牵扯到了多种交叉学科,也启示我们在技术创新时需要抽象出一件事物的本质,注意与其他领域相互融合。随着技术的进步,新的哈希函数也在不断地被设计出来,并接受着大家的检验,哈希函数的发展可以说是“道高一尺,魔高一丈,愈进愈阻,永无止息”。