# BTC 学习笔记连载(3)——Hash By [Crypto 吊车尾](https://paragraph.com/@imsongoku) · 2022-09-04 --- 欢迎交流：[twitter.com/songoku\_web3](http://twitter.com/songoku_web3) 我们说BTC是加密货币， 既然是加密货币，那自然跟密码学紧密相关。 但整个比特币用到的密码学也就2个： **哈希、签名** 签名主要用到了公钥密码学，本篇先讲哈希。 **什么是哈希？** 不仅仅是BTC网络，哈希是整个加密世界的基础，要想对区块链有较深度的理解，必须先深入理解哈希。 哈希 (Hash) 就是我们平常说的哈希函数、散列函数、散列算法，能够将一个任意长度的输入值转换成一个固定长度的输出值。 散列函数通过其算法把消息、数据压缩成摘要，在将数据量变小的同时将输出数据统一，以方便作为任意输入数据的指纹。 哈希碰撞、不可逆、谜题友好性 -------------- 能应用到BTC甚至作为整个Crypto世界的哈希函数我们称之为Crypto graphic hash function，这样的哈希函数具备3个重要的特性： 1. **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世界将被推翻！ 2. **不可逆** 哈希的不可逆性也叫单向性，或Hiding。 即知道一个输入x，很容易得到它的输出 H(x) ，但拿到输出 H(x) 没法倒推出任何输入信息，也可以这样表达： **x — > H(x)** 如何保障它的Hiding特性呢？ 我们先看看怎样是不Hiding的： 比如酒吧里玩游戏，一个小姐姐让你猜她是几月的 (猜对今晚跟你回家)，为了规避作弊嫌疑先将答案哈希并公示出来。 这种场景就没有任何Hiding可言，你只需要将 1月—12月 逐一进行哈希运算，最多算12次就可以比对结果找到答案。 聪明的小朋友很快就能找到问题所在，要做到Hiding输入空间必须足够大，同时分布还要足够均匀。 也就是你不能通过任何技巧、任何信息、任何暗示去反推输入。 如果上面游戏小姐姐让你猜她最喜欢的一句诗，今晚你就只能自己回家了。 3. **谜题友好性** 符合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位，同样用了多轮的思想。 ![](https://storage.googleapis.com/papyrus_images/af4a84620eadd9864774a90063c3c5c5efd60f5e863a62c4fd70a24687d4dee5.png) 如图，一个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位的输出： ![](https://storage.googleapis.com/papyrus_images/2c8a9b0151aa5cce295d6c06246004fcf4607910a9d07dd1cbef74d5367d3cce.jpg) 逐个运算是以如下公式进行的： ![](https://storage.googleapis.com/papyrus_images/65afd140da8908d0b6d6b7829f2a5841fbe765b27a4f1dc8efdcf5dbbe9d6589.png) * 其中C(x)就是SHA-256的压缩函数 * H(i)为消息区块的哈希值，H(0)是一个固定初始哈希值(上图中红色圆圈代表的256位值) * \+ 为是mod 2^32 加法，即2个数相加再对 2^32 取余 本质上它是一个通过将消息区块做为密钥，对中间哈希值进行加密的256位加密算法。 无论输入有多大，最终都会在一轮一轮的运算中生成一个256位的输出，输入多无非就是多算几轮的事情，输入非常小的时候也会补位到最少1个消息区块M1。 一般了解到这里就足够了，如果想更深入一点还可以自行查阅google，包括这里的H(0)是怎么定的、压缩函数是如何计算的、处理流程是怎样的等等。 **防篡改、隐私保护、加盐** 1. **防篡改** **H(m) = digest** 如果对一条数据进行哈希后得到它的digest，那么这个digest就可以验证m是否被篡改。 BTC每个区块里的交易通过Merkle tree生成Root hash存放在Block header里，任何人都无法对区块里的交易进行篡改，其根本就是通过哈希函数来保障的。 防篡改的应用在web2也有很多场景，比如我们平常工作中也可以找到应用案例，比如你上传一份代码或机密文件是否有被篡改的痕迹，哈希是绝佳的工具。 2. **隐私保护** [古典密码学这篇](https://mirror.xyz/imsongoku.eth/ogK67tcc8uDwsV_d5xq_DFuFQlX3cV7YuF-j9TdHbHY)我们提到过用于登录的密码，一个通行的口令、一个验证身份的凭证，这是我们使用最广泛的认证系统之一，防止未经授权的系统访问。 这些密码要怎么保存呢？ 一般就会将其取哈希后存到数据库，当用户登时将其输入的密码做一次同样的哈希运算，跟数据库保存的哈希匹配一致即可通行。 这不但保护了用户的隐私还规避了不同站点之间的撞库风险，在大多数系统中密码是通过哈希加密存储的。 但是也有例外： 几年前Web2某某大厂被黑，爆出的数据库明文保存密码是否还记忆犹新？ …… 其实我们工作中直到现在还在频繁使用MD5。 比如以前在腾讯做的营销、风控业务，我们经常需要用到机器学习建模，建模时需要客户提供正负样本，这个样本ID通常都是用户的手机号、设备ID，这可是不能乱传的。 为了保护用户隐私、保护这些手机号不被经手人员窃取，通常双方建模都是基于MD5的ID进行碰撞匹配的。 MD5虽然已经不在安全了，但在很多安全性要求并不那么高的场景依然是适用的，很多场景在一定的时间内一定的门槛保障下足够安全就行了。 3. **digital commitment** 也可以叫digital equivalent of a sealed envelop，也就是用于预测场景的。 预测者无需提前公布结果，而通过哈希将预测结果公示，待合适的时机公布自己的预测跟哈希匹配即可。 通常如果想进一步加强哈希结果的安全性，还可以进行加盐。 什么是加盐？ H( X || salt) 就是这里的salt，在输入X的基础上再拼接一个字符串，如过所处的场景输入空间并不是那么大或分布不是那么均匀，就可以通过加盐来提升安全性。 **_补充一点：_** 没有任何一个哈希函数是在数学上证明了 Collision resistance 的，也就是说上面提到的这么重要的性质从理论上是证不出来的，通常我们只能靠实践中的经验，世界上那么多密码学的专家谁都还没有找到碰撞的方法，所以我们认为SHA-256还是安全的，而MD5不是。 而安全性不是永恒的，加密和破解都是在对抗中互相发展的。 随着技术的突飞猛进，可能有一天SHA-256就不再安全了。 但一定会在BTC受到安全威胁之前硬分叉一个更安全的哈希算法。 所以拿住你的BTC，不用担心！ --- *Originally published on [Crypto 吊车尾](https://paragraph.com/@imsongoku/btc-3-hash)*