哈希函数
哈希函数在密码学中是非常重要的，这篇文章里面主要谈论的哈希函数也是在密码学中的哈希函数。 首先我们看一下一般的哈希函数的定义。一般的哈希函数是一个数学函数，其需要满足三个特点： - 输入可以是任意长度的字符串。 - 输出是固定长度的。 - 函数的计算时间比较短，从算法的角度上来说，时间复杂度为O(n) 对于密码学中的哈希函数有需要额外的三个特性要求： - 无碰撞性(collision-resistance) - 隐藏性（hiding） - 制作谜题的友好性 （puzzle-friendliness）
无碰撞性
碰撞的定义指的是，两个不同的输入经过哈希函数以后的输出是一样的。因此可以引出无碰撞性的定义。 如果一个哈希函数H是无碰撞行的，那么不可能找出两个值x和y，\(x \neq y\)使得H(x)=H(y). 但实际上碰撞是难以避免的，通常需要表示的y的空间是远大于x的。比如说对于字符串计算哈希值。如果哈希值的输出是256位的。那么这个哈希值最多可以表示的字符串的数目是\(2^{256}+1\)个。显然，这个值是远远小于字符串的组合数量的。26个字符可以有无数种组合。 无碰撞性的一个典型的应用就是无碰撞性。比如说，Alice在云盘里面上传了一个文件。等到再把文件下载下来的时候，想知道文件是否和原来的一样。可以将原来的文件用哈希函数计算得到一个哈希值。等到下载文件的时候，再用哈希函数算出来一个哈希值，看看和原来的哈希值是否一样的。如果是一样的话，那么这个文件和原来上传的文件是完全一样的。
隐藏性（hiding）
Hiding的定义是如果我们知道一个哈希函数的输出是y。我们无法得知这个哈希函数的输入x是什么。 从数学上来说就是，如果一个哈希函数H具有隐藏性，那么当一个秘密的值r是从一个高最小熵(high min-entropy)的系统中取出的，我们知道H(r||x)时，我们无法知道什么是x。其中||表示的是关联。 隐藏性的一个应用是承诺（commitments，来自”Princeton Bitcoin textbook”）。我们将一个随机的256bit的nonce和我们的message连接在一起，使用哈希函数计算得到一个哈希值。当我们想要验证的时候，给出nonce和mesage就知道，就可以证明这个nonce和message是原来的nonce和message。 这种承诺对于双方都有意义。这个过程就像是寄一封信。写信的人就是做出承诺的人。他写了一封信，放在一个信封里面贴上封条，就相当于做出了承诺。写信人的如果不想的话，看信的人无法知道这封信的内容。当写信的人写完信后想要修改信的内容也不可能，使得他无法抵赖。
制作谜题的友好性（Puzzle-friendly）
制作谜题的友好性是为了像比特币这样的数字货币中的共识机制而设计的。比特币的共识机制是PoW（Proof of work）。在比特币中，每个挖矿节点对于打包的交易和一个数字作哈希计算，希望得到一种目标的哈希值。这种哈希值的特点是前部指定的几位全部为0。这个数字被称为nonce。如果这个哈希函数具有制作谜题的友好性的话，那么在这个寻找nonce的过程中，最好的方法应该是从0开始尝试这个nonce，然后不断的累加。也就是从0开始遍历nonce，知道\(2^{256}\)。 从数学上来定义这个特点就是，如果一个哈希函数是制作谜题友好的，那么对于每一个可能的n-bit的输出值y来，如果k是从一个高 最小熵的分布中选出的话，那么不可能在一个远小于\(2^n\)的时间内找到一个x，使得\(H(k||x)=y\)。 对于是这个谜题我们可以这么定义我们有一个哈希函数H，有一个目标集合Y。在这个谜题中，我们想要找到一个值id，是的\(H(id||x)\)落在Y区间内。 这个特性的典型应用就是在比特币的PoW中。