数据结构：GitHub 和比特币中的哈希函数

哈希函数不仅在生成哈希表等数据结构中起着重要作用，实际上它在密码学中也起着关键作用。 密码学的概念听起来离我们很远，但实际上它已经应用在我们身边的各种软件中。 那么这一讲，我们就来看看哈希函数在GitHub中是如何应用的，以及链表和哈希函数在比特币中是如何应用的。

加密散列函数

如果一个哈希函数可以安全地应用在密码学中，我们就称它为密码哈希函数（Cryptographic Hash Function）。 “数字文摘”一词您应该很熟悉。 它也是将任意长度的信息通过加密的哈希函数转换成的固定长度的哈希值。

数字摘要通常用于验证一段数据或一个文件的完整性（Integrity），而验证数据文件的完整性利用了散列函数的一个特点：“两个相同的对象作为输入的哈希函数，它们将始终获得相同的哈希值”。 并且当数据文件中的任何内容被修改时，哈希函数生成的哈希值都会不同，因此我们可以确定数据文件是被修改的文件。 在很多地方，我们也会把这样的哈希值称为校验和（Checksum）。 当然，我们不能忘记哈希函数的另一个特点：“将两个不同的对象作为哈希函数的输入，它们不一定会得到不同的哈希值”。

常见的密码哈希函数算法有MD（Message Digest）算法和SHA（Secure Hash Algorithm）算法。

MD算法可以通过输入产生一个128位的哈希值，保证信息传输的完整性； 在SHA算法中，比较常见的有SHA-1、SHA-256算法等，也可以通过input输入。 生成 160 位或 256 位哈希值。 与MD算法一样，它们用于保证信息传输的完整性。 对这些算法感兴趣的同学可以自行阅读MD和SHA的百科资料。

这些加密的哈希函数算法，它们所做的并不是为每个数据文件生成唯一的哈希值，而是通过这些加密的哈希函数算法，将不同数据文件生成的哈希值哈希冲突的概率很小，小到这几乎是不可能的。 这样，我们就可以有把握地说，当两个数据文件通过加密哈希函数生成的哈希值一致时，这两个数据文件就是同一个数据文件。

但如果有一天，我们可以人为地修改数据文件，让两个不同的文件在经过加密哈希函数后可以生成相同的哈希值，那么使用这些加密哈希函数进行验证的应用程序就可能被屏蔽。 被别有用心的黑客攻击。 2017年，SHA-1加密算法正式宣布破解。 这是什么意思？ 这意味着使用 SHA-1 加密算法来验证数据完整性的应用程序可能会受到人为创建哈希冲突的攻击。

使用 SHA-1 加密算法进行数据完整性验证的一个著名应用程序是 Git。 简单的说，Git使用SHA-1算法对每个文件对象进行哈希值运算，因此每个提交的文件都会有自己的哈希值。 在Git中查找一个文件对象，其实就是通过hash值来查找。

当我们提交代码并运行“git commit”命令时，Git会对所有这些文件进行一次SHA-1运算，再加上一些元数据（Metadata），得到一个新的哈希值。 它包括上次提交期间生成的哈希值。 包含上次commit生成的hash值主要是为了防止中间有人恶意修改一些commit，让后面的所有commit都能发现自己保存的上次commit的hash值被修改了的hash值过去的commit不一致，就是说中间的commit被篡改了。

现在我们知道Git其实是通过SHA-1算法生成的哈希值来找到一个文件对象的，所以如果恶意程序可以为两个不同的文件创建相同的哈希值，即生成一个哈希值。 希望碰撞比特币使用的哈希函数是，所以 Git 无法确定哪个文件是“真实的”。

知名的代码软件托管平台GitHub其实也面临同样的问题。 当然，根据2017年公布的实验结果，如果真的需要人为制造SHA-1哈希碰撞攻击，现阶段的成本是非常昂贵的，比如需要单核CPU 6500年计算时间，或者需要110年的单核GPU计算时间，所以单纯依靠暴力枚举是行不通的。

根据 Github.com 的报告，一些针对 Github.com 的碰撞攻击实际上使用了一些特殊的技术来减少这些计算次数，并且在这些攻击中会有固定的“字节模式”遵循。 所以GitHub.com会对每一个上传的文件进行一次SHA-1碰撞检测，而且他们使用的检测工具也是开源的（检测工具源代码）。

Linux 和 Git 之父 Linus 也对 SHA-1 被攻破发表了自己的一些看法。 下面我还附上了一封他亲自回复的邮件。 如果您有兴趣，可以自行查看这封邮件的内容。

比特币是区块链技术中比较知名的应用。 同时，比特币也与链表和哈希函数这两种数据结构有着千丝万缕的联系。 比特币是由一个叫“中本聪”的人提出的。 它是一种诞生于2009年的虚拟加密货币，其本质思想是建立一个基于区块链的去中心化记录。 账户系统。 我们平时使用的记账系统，无论是使用实体银行卡还是使用移动支付，其交易信息都会记录在一个统一的数据库中。 在去中心化的记账系统中，交易信息会被加密，直接存储在用户的地方。

比特币将所有交易记录存储在称为块的数据结构中。 我们可以把这里的块看成是链表数据结构中的一个节点。 当用户需要打包新的交易记录时比特币使用的哈希函数是，可以自己创建一个新的区块，放在整个区块链的末尾，相当于在一个链表的末尾插入一个新的节点。 区块链中的第一个区块，即链表的头节点，称为创世区块。

不同于使用内存地址寻找下一个节点的链表数据结构，区块链使用哈希值寻找节点。 在比特币中，它使用加密哈希函数 SHA-256，它为每个块计算一个 256 位的哈希值。 在每一个新区块中，都会保存前一个区块计算出的哈希值。 通过这个哈希值，我们可以找出这个新区块的前一个区块是哪个区块。 所有的区块都可以利用这种机制寻找前一个区块，从而遍历整个区块链，直到找到创世区块。

当然，并不是每个人都“有资格”创建新区块。 就像上一讲的区块链“挖矿”原理一样，只有用户“挖矿”成功，才有资格打包交易信息，创建新的区块。 典型的比特币区块链如下图所示：