1.1 密码学哈希函数

我们需要理解的第一个密码学的基础知识是密码学哈希函数，哈希函数是一个数学函数，具有以下三个特性：

● 其输入可为任意大小的字符串。

● 它产生固定大小的输出。为使本章讨论更具体，我们假设输出值大小为256位，但是，我们的讨论适用于任意规模的输出，只要其足够大。

● 它能进行有效计算，简单来说就是对于特定的输入字符串，在合理时间内，我们可以算出哈希函数的输出。更准确地说，对应n位的字符串，其哈希值计算的复杂度为O（n）。

这些特性定义了一般哈希函数，以这个函数为基础，我们可以创建数据结构，例如哈希表。我们将只专注于加密的哈希函数，要使哈希函数达到密码安全，我们要求其具有以下三个附加特性：（1）碰撞阻力（collision-resistance）；（2）隐秘性（hiding）；（3）谜题友好（puzzle-friendliness）。

我们会仔细研究这些特性，并会逐步阐释我们为什么需要这样的函数。学习过密码学的读者可能会注意到，我们这里对于哈希函数的论述与一般的密码学课程会有所不同，特别是关于谜题友好。在一般密码学中，谜题友好并非加密的哈希函数的一般要求，却对加密数字货币这一特性非常有用。

特性1：碰撞阻力

加密的哈希函数的第一个特性是它要具有碰撞阻力。这里的碰撞指对于两个不同的输入，产生相同的输出。如果对于哈希函数H(·)，没有人能够找到碰撞，我们则称该函数具有碰撞阻力（见图1.1）。即：

注意，我们说没人能找到碰撞，并不表示不存在碰撞。事实上，通过简单的计数论证（counting argument），我们可以证明碰撞的确存在。哈希函数的输入空间包含所有长度的任意字符串，但输出空间则只包含特定固定长度的字符串。因为输入空间比输出空间大（输入空间是无限的，而输出空间是有限的），一定会有输入字符串映射到相同的输出字符串。实际上，根据鸽巢原理（Pigeonhole Principle），我们可以得出，必然会有大量可能的输入被映射到任意特定输出（见图1.2）。

而更糟糕的是，对于加密的哈希函数，我们虽然说应该找不到碰撞，但有些方法是能保证找到碰撞的。考虑以下对应于一个256位输出大小的哈希函数，选择2256+1个不同数值，计算每个数的哈希值，并检查是否有两个相等的输出。因为我们这里选择的输入多于输出，因此在应用哈希函数时，一些数对必将产生碰撞。

使用上述方法一定能找到碰撞。但如果我们随机性地选择输入，并计算哈希值，我们在检验第2256+1个输入之前便很可能找到碰撞。实际上，如果我们随机选择2130+1个输入值，找到至少两个等同哈希值的概率为99.8%。仅仅通过检验可能输出数量的平方根次数，便大体能找到碰撞，这一事实在概率学中被称为是生日悖论（birthday paradox）。

这个碰撞检测算法对每个哈希函数都有效，但是它的问题是其计算需要花很长很长时间才能完成。对于一个256位输出的哈希函数来说，最坏的情况是你需要进行2256+1次哈希函数计算，平均次数为2128次，这简直是一个天文数字——如果一台电脑每秒计算10 000个哈希值，计算2128个哈希值，需要花1027多年时间！换个角度，我们可以说，如果人类制造的每台电脑在整个宇宙起源时便开始计算，到目前为止，它们找到碰撞的概率仍然无穷小，比下两秒钟地球将被大陨石摧毁的概率还要小得多。

因此，为了寻找一个任意的哈希函数的碰撞，我们只是有了一个一般，但并不实用的算法。一个更艰涩的问题是：有没有其他的方法，可以用于对于某一特定哈希函数找到碰撞？也就是说，虽然一般的碰撞测试算法不适用，但仍可能有其他的算法，可以有效地找到某个哈希函数的碰撞。

以下面的哈希函数为例：

H(x)=x mod 2256

这个函数接受任何长度的输入，产生一个固定大小输出（256位），且能进行有效计算，因此符合我们对哈希函数的要求。但是对于这个函数，我们确实具备一个有效的能够寻找碰撞的方法。注意，这个函数仅返回输入的最后256位，因此，数值3和3+2256就构成了碰撞。这个简单的例子表明，虽然我们的一般碰撞测试方法在实践中不可行，但至少对于某些哈希函数，存在有效的测试碰撞的方法。

但对于某些哈希函数，我们无法确认识别碰撞的有效方法是否存在，我们只是怀疑这些函数具有防碰撞特性，但是我们已经证明，世界上没有哈希函数具有防碰撞特性。我们实践中依赖的加密的哈希函数仅仅是人们经过不懈努力之后暂未成功找到碰撞的函数。因此，我们选择相信那些加密的哈希函数具有哈希阻力（在某些情况下，如之前的MD5哈希函数，在多年的努力之后最终找到了碰撞，导致该函数在实践中被逐渐淘汰，最终被弃用）。

应用：信息摘要

现在我们知道什么是碰撞阻力了，我们自然会问：碰撞阻力有什么用途？以下就是一个应用：哈希函数H具有碰撞阻力，x和y是两个不同的输入，那么可以假设它们的哈希函数H(x)和H(y)也不同——如果已知x和y不同，但哈希值相同，那么H具有碰撞阻力的假设就不成立了。

这个论证使我们可以将哈希输出作为信息摘要（message digest）。以SecureBox为例，SecureBox是一个允许用户上传文件，并保证文件被完整下载的线上文件存储系统。假设爱丽丝上传了很大的文件，并希望能够在之后下载时确认她下载的文件与她上传的文件相同。一种方法是将整个文件进行本地存储，并直接将其与下载文件对比。如果这样可行，那么将文件上传便显得毫无意义，倘若爱丽丝需要使用本地文件副本以保证其完整性，她可以直接使用本地副本。

无碰撞哈希函数为这个问题提供了简单有效的解决方法，爱丽丝只需要记住原文件的哈希值，从SecureBox下载文件后，她可以计算下载文件的哈希值，并与原文件哈希值进行对比。如果哈希值相同，那么爱丽丝可以说该文件就是她上传的那一个，但是如果不同，她则可以确定文件被破坏了。记录哈希值可以帮助爱丽丝检测文件在传输过程中，或在SecureBox服务器上是否产生了意外损坏，或者检测文件是否受到服务器的蓄意修改。保证主体不受其他实体的恶意行为侵害，这正是密码学的核心。

这里的哈希函数对于一个信息生成固定长度的摘要，或生成了简明总结，这为我们提供了一种记住之前所见事物，并在今后认出这些事物的有效方法。虽然整个文件可能非常大，存储规模达数G，但其哈希值的长度固定。例如，哈希函数为256位。这样做，极大地降低了存储要求。在本章后面及整本书中，我们都会看到哈希作为信息摘要的应用。

特性2：隐秘性

我们希望哈希函数拥有的第二个特性是其隐秘性。隐秘性保证，如果我们仅仅知道哈希函数的输出y=H(x)，我们没有可行的办法算出输入值x。问题是，上述的表示形式不一定是正确的。考虑以下简单的例子：我们做一个抛硬币的实验，如果抛硬币结果为正面，我们会宣布字符串哈希为“正面”；如果结果为反面，我们会宣布字符串哈希为“反面”。

然后我们问我们的对手，在他没有见到抛硬币，而只见到哈希函数的输出的前提下说出哈希函数的输入字符串（很快我们就知道为什么要玩这个游戏了）。为了回答问题，对手会简单计算“正面”字符串的哈希值及“反面”字符串的哈希值，然后对手便可以知道他得到的是哪一个。这样，只需要几步，对手就能反解出输入值。

对手能够猜出字符串，这是因为x只有两个可能，他可以很轻易地将两个可能对应的哈希值计算出来。为了能够实现隐秘性，我们需要x的取值来自一个非常广泛的集合，也就是说，仅仅通过尝试几个特定的x，就能找到输出值的方式将不会发生了。

现在的问题是：在类似抛硬币的“正面”、“反面”实验中，如果我们想要的反解的输入值并非来自分散的集合，我们是否还能得到隐秘性？幸运的是，对于这个问题答案是肯定的！我们甚至能够通过与另一个较为分散的输入进行结合，而将一个并不分散的输入进行隐秘。现在我们可以更精确地表示隐秘的含义了（双竖线‖为连接符号，代表把一系列事件、事情等联系起来）。

在信息论中，最小熵是用于测试结果可预测性的手段，而高阶最小熵这个概念比较直观描述了分布（如随机变量）的分散程度。具体来说，在从这样分布中取样时，我们将无法判定取样的倾向。举个具体的例子，如果r是从长度为256位的字符串中随意选出的，那么任意特定字符串被选中的概率为1/2256，这是一个小到几乎可以忽略的取值。

应用：承诺

现在来看一下隐秘性的应用。具体来说，我们把想做的事情称为承诺（commitment）。这里承诺是一个数字化过程，可以类比为以下动作：首先选定一个数字，将数字装进信封，然后将该信封放到一个人人都看得到的桌子上。这样做以后，可以说你就信封里的数字做出了承诺，在打开信封前，虽然你已经做出了承诺，对其他人来说它还是秘密。在之后，你可以打开信封，来展示承诺的数值。

为了使用承诺方案，我们首先需要产生一个临时随机数。然后将这个临时随机数与承诺信息msg一起代入承诺函数，计算承诺函数输出值com，然后公布该输出。这个过程就如同将封好的信封放到一个人人能看到的桌上那样。之后，如果我们希望展示之前的承诺值，我们首先公布用于产生承诺的临时随机数，并公布信息msg。此时任何人都可以验证这时公布的msg是否为之前承诺，这个阶段就如同打开信封。

以上两个安全特性决定了这一算法就如同密封及打开信封。第一，如果仅仅知道com，即承诺函数的输出，就如同只看信封并不能得到信息内容；第二就是约束性，这就保证了你一旦承诺信封内的内容，就不能再改变主意。也就是说，我们无法找到两个不同的信息，当你在承诺一个信息后，而又声称你承诺了另一个信息。

我们如何在承诺协议中保证隐秘性和约束性这两个性质成立呢？在讨论这一点之前，我们需要讨论如何执行承诺方案。我们可以通过使用加密的哈希函数来达到目的，考虑如下承诺协议实施方案：

commit(msg, nonce):=H(nonce‖msg)

其中，nonce为长度为256位的临时随机数。

为承诺一段消息，我们首先生成一个256位的临时随机数，然后将这个临时随机数与信息链接，并返回这个链接值的哈希值，来作为承诺输出。为了便于验证，我们还要设定其他人来计算一下临时随机数与信息链接之后的哈希值，比对一下计算结果是否与承诺输出相同。

再来看一下我们的承诺方案要求的两个特性，如果我们将承诺和验证换成H(nonce‖msg)，那么这些特性就变成：

● 隐秘性：已知H(nonce‖msg)，没有可行方法找到msg。

● 约束性：没有可行方法找到两对(msg, nonce)和(msg’, nonce’)，msg≠msg’，而H(nonce‖msg)==H(nonce’‖msg’)。

承诺的隐秘特性正是我们要求哈希函数要具备的隐秘性，如果将一个解密钥匙选定为256位的随机值，那么由隐秘性得出，如果解密钥匙与信息链接，那么仅仅从哈希函数的输出中恢复信息就是不可行的。约束性隐含在哈希函数的碰撞阻力特性中，如果哈希函数具有碰撞阻力，那么我们将不能找到不同的msg及msg'值，而H(nonce‖msg)=H(nonce'‖msg')，如果这种情况发生，将构成碰撞。

因此，如果哈希函数H具有碰撞阻力及隐秘性，从安全特性上来讲，这个承诺方案将有效。

特性3：谜题友好

哈希函数需要的第三个安全特性为谜题友好特性。这一特性较为复杂，我们首先解释该特性的技术要求，然后通过举例来阐释该特性的意义。

直觉上，谜题友好可以这样解释，如果有一个人想找到y值所对应的输入，假定在输入集合中，有一部分是非常随机的，那么他将非常难以求得y值对应的输入。

应用：搜索谜题

现在，让我们试想一个应用以阐释谜题友好特性的意义。在这个应用中，我们将建立一个搜索谜题，该谜题是一个需要对庞大空间进行搜索，才能找到解决办法的数学问题。该搜索谜题没有捷径，也就是说除了搜索庞大的空间来进行求解，别无他法。

H(id‖x)∈Y

这个直觉是：如果H有一个n位输出，那么它的可能取值有2n个。解决这个谜题要求找到一个位于集合Y（通常比所有输出值集合小很多）内的输出值，Y的大小决定了谜题的难度。如果Y是所有n位字符串的集合，这个谜题就毫无意义。然而，如果Y只有一个元素，那么这个谜题难度最大，谜题ID取自高阶最小熵分布，这个事实保证了求解无捷径。反过来，如果该ID的确定性很高，那么有人可能会作弊，比如通过使用该ID，事先对谜题进行求解。

如果一个哈希函数具备谜题友好特性，这就意味着对于这个谜题没有一个解决策略，比只是随机地尝试x取值会更好。因此，如果我们要把谜题做成很难解决是可以的，只要我们能用适合的随机方式生成谜题ID。当我们讨论比特币采矿（是一种搜索谜题）时会采用这一思路。

安全哈希算法

我们讨论了哈希函数的三个特性及其相应的应用。现在，让我们讨论本书中将会大量用到的一个哈希函数，安全哈希算法（Secure Hash Algorithm 256，简称SHA-256）。哈希函数有很多，但SHA-256是一个主要被比特币世界采用，并且效果还很不错的哈希函数。

回想一下，我们要求哈希函数可以用于任意长度输入。幸运的是，只要我们能建立一个用于固定长度输入的哈希函数，然后通过一般方法，就可以将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数，我们称这个转换过程为MD（Merkle-Damgard）变换，SHA-256是采用这种变换方法的常用哈希函数之一。在通用术语中，这种基础型，可用于固定长度，具备碰撞阻力的哈希函数被称为是压缩函数（compression function）。经过验证，如果基本压缩函数具有碰撞阻力的特性，那么经过转换而生成的哈希函数也具有碰撞阻力。

MD变换很简单。比如压缩函数代入长度为m的输入值，并产生长度短一些为n的输出值。哈希函数的输入（可为任意大小）被分为长度为m-n的区块。MD变换运作过程如下：将每个区块与之前区块的输出一起代入压缩函数，注意，输入长度则变为(m-n)+n=m，也刚好就是压缩函数的输入长度。对于第一个区块而言，之前没有的区块，我们需要选取一个初始向量（见图1.3）。每次调用哈希函数，这个数字都会被再一次使用，而在实践中，你可以直接在标准文档中找到它。最后一个区块的输出也就是你返回的结果。

SHA-256函数利用了这样的一个压缩函数，这个压缩函数把一个768位的输入压缩成一个256位的输出，每一个区块的大小是512位。我们可以通过图1.3来理解SHA-256的工作过程。

截至目前，我们已经讨论了哈希函数、密码学上使用具备特性的哈希函数、这些特性的应用，以及在比特币世界中使用的一类特殊的哈希函数。在下面的章节中，我们将讨论通过哈希函数来构建比特币网络中的更为复杂的数据结构。