BTC 学习笔记连载(3)——Hash
我们说BTC是加密货币，
既然是加密货币，那自然跟密码学紧密相关。
但整个比特币用到的密码学也就2个：
哈希、签名
签名主要用到了公钥密码学，本篇先讲哈希。
什么是哈希？
不仅仅是BTC网络，哈希是整个加密世界的基础，要想对区块链有较深度的理解，必须先深入理解哈希。
哈希 (Hash) 就是我们平常说的哈希函数、散列函数、散列算法，能够将一个任意长度的输入值转换成一个固定长度的输出值。
散列函数通过其算法把消息、数据压缩成摘要，在将数据量变小的同时将输出数据统一，以方便作为任意输入数据的指纹。
哈希碰撞、不可逆、谜题友好性
能应用到BTC甚至作为整个Crypto世界的哈希函数我们称之为Crypto graphic hash function，这样的哈希函数具备3个重要的特性：
Collision resistance
这是哈希函数最重要的一条特性，即抗碰撞性。
什么是碰撞？
对于任意1个哈希函数 H(x) ，如果有2个不同的输入能得到相同的输出，即这2个输入发生了哈希碰撞，也可以这样表达：
X ≠ Y，H(X) = H(Y)
为什么会有碰撞？
其实不但有碰撞，而且碰撞是无穷多的。
很简单，我们知道SHA-256是一个固定256位二进制输出的哈希函数，也就是它的输出空间为2^256，虽然这已经是天文数字了，但它还是有限的。
一个有限的输出空间对应一个无穷的输入空间，必然发生碰撞。
哈希本质上就是一个多对一的模型，任何一个输出都对应无穷多的输入。
碰撞会带来什么隐患？
比如孙割的BTC钱包私钥（1个256位的二进制数），如果谁能通过它的公钥把它碰撞出来了，那将立刻获得私钥对应资产的控制权，直接一波自由。
但如果这种事情可以"被操作"了，那整个Crypto的世界基本就要推倒重来了，任何人的钱包还有安全性可言？
显然这不是你想碰撞就能碰撞的！
那哈希是如何抗碰撞呢？
这里的 Resistance 是指没有任何办法人为制造碰撞，比如你知道了孙割的钱包地址，要将其私钥定向“碰撞”出来没有任何办法，你只能不停地试，而你能试出来的概率比地球爆炸的几率还小N倍。
（私钥 - 公钥 - 地址 的转换算法后面文章会详细讲，这里理解Collision resistance就好了）这就是哈希函数的抗碰撞性，
这是Crypto世界的核心基础，
这一点如果被破坏，整个现有Crypto世界将被推翻！
不可逆
哈希的不可逆性也叫单向性，或Hiding。
即知道一个输入x，很容易得到它的输出 H(x) ，但拿到输出 H(x) 没法倒推出任何输入信息，也可以这样表达：
x — > H(x)
如何保障它的Hiding特性呢？
我们先看看怎样是不Hiding的：
比如酒吧里玩游戏，一个小姐姐让你猜她是几月的 (猜对今晚跟你回家)，为了规避作弊嫌疑先将答案哈希并公示出来。
这种场景就没有任何Hiding可言，你只需要将 1月—12月 逐一进行哈希运算，最多算12次就可以比对结果找到答案。
聪明的小朋友很快就能找到问题所在，要做到Hiding输入空间必须足够大，同时分布还要足够均匀。
也就是你不能通过任何技巧、任何信息、任何暗示去反推输入。
如果上面游戏小姐姐让你猜她最喜欢的一句诗，今晚你就只能自己回家了。
谜题友好性
符合Crypto应用要求哈希函数有2个最基本的特性：
- 只要输入不变输出是恒定不变的
- 输入有任何微小变化，输出会千差万别如图SHA-256函数的2个输出(已转换成16进制)：
‘’7f75b27d8174945991fd7ab054f66611cb7712b533bbcd77e20c3c2c0d6e226e‘’
‘’708e0993431d8156a95464bd870476b9d3809b6fa3e38abcb24ffcd842e6598a‘’
这是完全就不相干的两个值吧，其实输入就相差一个句号而以：
‘’我是中本聪‘’
‘’我是中本聪。‘’
这一点非常重要！
你没有任何办法根据输入规律推导输出结果！
这就是谜题友好性（Puzzle friendly），没有任何捷径可言，只能通过穷举对比结果，没有任何的经验优势、没有任何逻辑相关性，这是世界上最公平的事。
我后面会讲到的BTC 挖矿(Mining)过程，就是不停地尝试随机数Nonce进行哈希运算直到一个Nonce算出满足条件的结果，除此之外没有任何捷径。
只有满足这个条件，POW (Proof of work) 才能成立，才能证明你获得某个Block的记账权是因为做了足够多的工作量，才能让任何“每单位算力”切身感受到这是一个公平的游戏。
而一旦你找到这样一个Nonce获得记账权之后，其它节点是很容易验证的。
挖矿很难，验证很容易！
(这个我们后面专门出一篇讲BTC的挖矿)
是不是感觉这几个特点有点混淆，其实只要理解Hiding说的是不能通过输出反推输入，Puzzle friendly是指输入之间的不相干性，就容易理解了。
所有用到Crypto世界里的哈希函数都必须满足以上3个特性，包括后面我们会讲到的 Ethereum ，虽然有用到跟 BTC 不同的哈希，但本质上都要基于这几点才能run得通。
Rivest、MD系列、SHA家族、RIPEMD
市面上流行的哈希函数有很多，最经典的应该是MD系列了，我们平常接触得比较多的是MD5 (Message-Digest Algorithm 5)，MD5是由MD2、MD4发展而来的。
1989年MIT教授 Ronald Rivest 设计出MD2，这个算法首先会对信息数据补位，使信息的字节长度是16的倍数，然后以一个16位的检验和追加到末尾，并根据这个新产生的信息计算出散列值。
为了增强算法的安全性，Rivest在1990年又设计了MD4算法，MD4同样是先填补信息...然后经过多轮每个区块三个不同步骤的处理，生成长度为128位的摘要。
1991年 Den Boer 和 Bosselaers 发表了一篇文章指出 MD4 多伦迭代中第一步和第三步的漏洞，Dobbertin向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4的漏洞，这个漏洞将导致以不同内容进行输入得到相同的输出，毫无疑问MD4的生命就此结束。
但不得不讲 MD4 影响了后来一众主流哈希算法：MD5、SHA家族和RIPEMD。
在MD4的基础上Rivest 马不停蹄地就设计出了更加成熟的MD5算法，它在MD4的基础上增加了"安全-带子"（Safety-Belts）的概念，由四个和MD4设计有少许不同的步骤组成，输出也是128位，同样用了多轮的思想。
如图，一个MD5运算由类似的64次循环构成，分成4组16次。F 是一个非线性函数，一个函数运算一次。Mi 表示一个 32-bits 的输入数据，Ki 表示一个 32-bits 常数，用来完成每次不同的XOR, AND, OR , NOT 等计算。
1996年后MD5被证实存在弱点，可以被加以破解，2009年中科院的谢涛和冯登国仅用了2^20.96的算法复杂度就破解了MD5，该攻击在普通计算机上运行只需要数秒时间。 对于需要高度安全性的资料MD5正式退出历史舞台！
每当这个时候就会有更好的技术出现，该轮到SHA出场了：
SHA是Secure Hash Algorithm的缩写，我们称其为安全散列算法，是一个密码散列函数家族，由FIPS背书认证。
但坑爹的一点是SHA由美国国家安全局（NSA）设计，并由美国国家标准与技术研究院（NIST）发布，属于美国的政府标准，谁知道它有没有留点后门呢？
SHA主要有4个分类：
SHA-0：1993年发布后很快就被NSA撤回，基本没留下什么声音。
SHA-1：是MD5的主要后继者，在很多安全协议中广泛使用，但在2010年后其安全性在大多数场景中暴露无遗，2017年荷兰密码学研究小组CWI和Google正式宣布攻破了SHA-1。
SHA-2：包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256等，这些不同的算法标准除了生成摘要的长度、循环运行的次数等细微差异之外，基本是一致的。 最为我们熟知的应该是SHA-256、SHA-512，SHA-2目前还没暴露明显的漏洞，虽然算法跟SHA-1基本上仍然相似，至今尚未出现对SHA-2有效的攻击。
SHA-3：由于MD5被成功的破解，以及出现理论上破解SHA-0、SHA-1的方法，NIST需要一个与之前不同的哈希算法，2015年SHA-3正式发布。
RIPEMD是由鲁汶大学 Hans Dobbertin，Antoon Bosselaers 和 Bart Prenee组成的COSIC 研究小组发布于1996年，RIPEMD是以MD4为基础而设计的，其表现与更有名的SHA-1类似。
BTC里用到的是RIPEMD-160，是以原始版RIPEMD所改进的160位版本，是RIPEMD系列中最常见的版本，输出为160位二进制数、40位16进制数。
SHA-256的实现
为什么无论你输入的数据是大是小，都能得到等长的输出呢？
为什么你的输入改动一点点，输出就会翻天覆地改变呢？
BTC主要用到的哈希函数是SHA-256，我们从SHA-256来找找原因：
对于任意长度的输入，SHA-256都会产生一个256位的哈希输出摘要，相当于一个长度为32个字节的数组，通常有一个长度为64位的十六进制字符串来表示。
与MD4、MD5以及HSA-1等哈希函数的操作流程类似，在进行哈希计算之前首先要进行补位和信息分块：
对输入信息进行补位，使得最终的长度为512位的倍数
将补位后的信息分为512位为单位的快，M1、M2......Mn
如图，对这些信息块进行多轮运算，最终得到一个256位的输出：
逐个运算是以如下公式进行的：
其中C(x)就是SHA-256的压缩函数
H(i)为消息区块的哈希值，H(0)是一个固定初始哈希值(上图中红色圆圈代表的256位值)
+ 为是mod 2^32 加法，即2个数相加再对 2^32 取余
本质上它是一个通过将消息区块做为密钥，对中间哈希值进行加密的256位加密算法。
无论输入有多大，最终都会在一轮一轮的运算中生成一个256位的输出，输入多无非就是多算几轮的事情，输入非常小的时候也会补位到最少1个消息区块M1。
一般了解到这里就足够了，如果想更深入一点还可以自行查阅google，包括这里的H(0)是怎么定的、压缩函数是如何计算的、处理流程是怎样的等等。
防篡改、隐私保护、加盐
防篡改
H(m) = digest
如果对一条数据进行哈希后得到它的digest，那么这个digest就可以验证m是否被篡改。
BTC每个区块里的交易通过Merkle tree生成Root hash存放在Block header里，任何人都无法对区块里的交易进行篡改，其根本就是通过哈希函数来保障的。
防篡改的应用在web2也有很多场景，比如我们平常工作中也可以找到应用案例，比如你上传一份代码或机密文件是否有被篡改的痕迹，哈希是绝佳的工具。
隐私保护
古典密码学这篇我们提到过用于登录的密码，一个通行的口令、一个验证身份的凭证，这是我们使用最广泛的认证系统之一，防止未经授权的系统访问。
这些密码要怎么保存呢？
一般就会将其取哈希后存到数据库，当用户登时将其输入的密码做一次同样的哈希运算，跟数据库保存的哈希匹配一致即可通行。
这不但保护了用户的隐私还规避了不同站点之间的撞库风险，在大多数系统中密码是通过哈希加密存储的。
但是也有例外：
几年前Web2某某大厂被黑，爆出的数据库明文保存密码是否还记忆犹新？
……
其实我们工作中直到现在还在频繁使用MD5。
比如以前在腾讯做的营销、风控业务，我们经常需要用到机器学习建模，建模时需要客户提供正负样本，这个样本ID通常都是用户的手机号、设备ID，这可是不能乱传的。
为了保护用户隐私、保护这些手机号不被经手人员窃取，通常双方建模都是基于MD5的ID进行碰撞匹配的。
MD5虽然已经不在安全了，但在很多安全性要求并不那么高的场景依然是适用的，很多场景在一定的时间内一定的门槛保障下足够安全就行了。
digital commitment
也可以叫digital equivalent of a sealed envelop，也就是用于预测场景的。
预测者无需提前公布结果，而通过哈希将预测结果公示，待合适的时机公布自己的预测跟哈希匹配即可。
通常如果想进一步加强哈希结果的安全性，还可以进行加盐。
什么是加盐？
H( X || salt)
就是这里的salt，在输入X的基础上再拼接一个字符串，如过所处的场景输入空间并不是那么大或分布不是那么均匀，就可以通过加盐来提升安全性。
补充一点：
没有任何一个哈希函数是在数学上证明了 Collision resistance 的，也就是说上面提到的这么重要的性质从理论上是证不出来的，通常我们只能靠实践中的经验，世界上那么多密码学的专家谁都还没有找到碰撞的方法，所以我们认为SHA-256还是安全的，而MD5不是。
而安全性不是永恒的，加密和破解都是在对抗中互相发展的。
随着技术的突飞猛进，可能有一天SHA-256就不再安全了。
但一定会在BTC受到安全威胁之前硬分叉一个更安全的哈希算法。
所以拿住你的BTC，不用担心！
