区块链之哈希算法（完整篇）

读过我之前的文章或者对比特币比较了解的同学应该都清楚像比特币这些数字货币必然离不开密码学。而比特币中用到的密码学主要是哈希算法和数字签名。今天就给大家普及一下哈希算法。

哈希算法是基于密码学中的哈希函数。哈希函数主要有下面几个特征：

输入可以是任何长度和大小的字符串。
输出是固定长度的。在比特币中输出固定为256位。
它能在一定的时间内输出结果。时间复杂度为O(N).

哈希函数之所以可以用于加密，主要是它具有三个特性：

碰撞阻力
隐秘性
谜题友好

碰撞阻力密码学中的碰撞是指对于两个不同的输入，产生相同的输出。而哈希函数中的碰撞阻力就是指如果想找到两个不同的输入，产生相同的输出，是有一定的难度的。但并不是不可以，你可以试想对于哈希函数，输入是无限时，输出是有限长度的，所以必然会存在多个不同的输入产生相同的输出。但要想找到两个不同的输入产生相同的输出是要花费很大的精力和时间。

举个例子，考虑对应于一个256位输出大小的哈希函数，选择2^256 +1个不同数值，计算每个数的哈希值，并检查是否有两个相等的输出。因为我们这里选择的输入多于输出，因此在应用哈希函数时，一些数对必将产生碰撞。但对于一个256位输出的哈希函数来说，最坏的情况是你需要进行2^256 +1次哈希函数计算，平均次数为2^128 次，这简直是一个天文数字——如果一台电脑每秒计算10000个哈希值，计算2^128 个哈希值，需要花10^27 多年时间！所以说哈希函数的碰撞阻力是很大的，十分适合于加密。

哈希函数（算法）具有隐秘性，其实它并不“隐秘”，它并不难理解。简单地说，就是如果我们仅仅知道H(x)=H(y)，要想反推其中的x和y，我们是需要花巨大的力气。专业的定义是：

隐秘性哈希函数H具有隐秘性，如果：当其输入r选自一个高阶最小熵（highmin-entroy）的概率分布，在给定H（r‖x）条件下来确定x是不可行的。

学过信息论的同学应该清楚什么叫熵，在这里我就不再展开了。所谓的最小熵可以简单地理解为最小值。举个具体的例子，如果r是从长度为256位的字符串中随意选出的，那么任意特定字符串被选中的概率为1/2^256 ，这是一个小到几乎可以忽略的取值。

想必学到这里，大家应该清楚哈希函数（算法）的隐秘性，最后我还总结一下，哈希函数的隐秘性就是尽管必然存在两个或多个不同输入，使得哈希函数的输出值一样，但要想通过计算找出这些不同的输入是十分的困难的。

最后，哈希函数还具有谜题友好性。

下面先给出传统的定义：

谜题友好如果对于任意n位输出值y，假定k选自高阶最小熵分布，如果无法找到一个可行的方法，在比2^n 小很多时间内找到x，保证H(k‖x)=y成立，那么我们称哈希函数H为谜题友好。

这里同样涉及到信息论中熵的概念，但我并不打算展开讲，因为我认为对于这些概念只要在大体上理解就行，但感兴趣的同学也可以自行百度。其实，所谓的谜题友好，通俗地说就是如果有一个人想找到y值所对应的输入，假定在输入集合中，有一部分是非常随机的，那么他将非常难以求得y值对应的输入。

细心的同学应该都发现了，其实隐秘性和谜题友好都在强调一件事情，知道哈希函数的输出值，来反求其输入值，是十分地困难。隐秘性是从概率的角度强调，能够反求出输入值的概率非常小，谜题友好是从时间的角度强调在很小的时间内是非常难求出其输入值。但它们都有同一个目的，就是反求出其输入值难度是非常地大。

最后，如果一个哈希函数具备谜题友好特性，这就意味着对于这个谜题没有一个解决策略，比只是随机地尝试x取值会更好。到这里应该就清楚为什么平时比特币挖矿的很多方法就是简单的遍历了吧，因为整体时间角度考虑，根本就没有一个比随机地尝试求x的所需的时间更快。

今天先分享到此，知识虽不多，但正所谓骐骥一跃，不能十步；驽马十驾，功在不舍。每天与你分享一个区块链小知识，希望你有所收获。

参考：网络文章、知乎、《区块链：技术驱动金融》、《区块链：从数字货币到信用社会》、《区块链：重塑经济与世界》、《区块链革命：比特币底层技术如何改变货币、商业和世界》、《区块链社会：解码区块链全球应用与投资案例》、《区块链：定义未来金融与经济新格局》

往期精彩文章
我是如何自学区块链的？
区块链学习指南
区块链之谈谈中本聪
区块链之谈谈《一种点对点的电子现金系统》1
区块链之谈谈《一种点对点电子现金系统》2
区块链之谈谈《一种点对点电子现金系统》3
区块链之发展历史
区块链之应用场景
区块链之比特币的前世今生