二、哈希算法和Merkle Tree

浅浅的花香味﹌ 2023-10-05 12:18 5阅读 0赞

章节系列目录：[点击跳转][Link 1]

#### 文章目录 ####

*  哈希算法
 *   *  哈希函数的定义
     *  可靠哈希函数需满足的要求
     *  哈希函数的主要作用
     *  哈希实际例子
 *  Merkle Tree默克尔树
 *   *  完整性校验的方法
     *  哈希列表 Hash List
     *  Merkle Tree 哈希树
     *  总结

## 哈希算法 ##

### 哈希函数的定义 ###

哈希函数：给一个任意大小的数据生成出一个固定长度的数据，作为它的映射。  
  你可以把哈希函数想象成“搅拌机”，一堆数据丢进去出来一段长度固定的16进制的数值就叫哈希值

### 可靠哈希函数需满足的要求 ###

一个可靠的哈希算法要满足如下三点

> 1.安全，给定数据 M 容易算出哈希值 X ，而给定 X 不能算出 M ，或者说哈希算法应该是一个单向算法。  
> 2.独一无二，两个不同的数据，要拥有不相同的哈希。  
> 3.长度固定，给定一种哈希算法，不管输入是多大的数据，输出长度都是固定的。

如果哈希的长度是固定的，也就是取值范围是有限的，而输入数据的取值范围是无限的，所以**总会找到两个不同的输入拥有相同的哈希**。所以哈希函数的安全性是相对的。如果出现了**两个不同输入有相同输出**的情况，就叫碰撞(`collision`) 。不同的哈希算法，哈希位数越多，基本意味着安全级别越高，或者说它的”抗碰撞性“越好。

> 消息A = 消息B 则 Hash(A) = Hash(B)  
> 逆否命题也成立：Hash(A) ≠ Hash(B) 则消息A ≠ 消息B  
> 而消息A ≠ 消息B **并不能推出** Hash(A) ≠ Hash(B)  
> 逆否命题：Hash(A) = Hash(B) **并不能推出** 消息A = 消息B  
>   
> 比如在网上都搜得到的汉字的哈希值有的就是一样的。  
> “柳柴"与"柴柕” hashCode=851553  
> “志捘"与"崇몈” hashCode=786017

> **注意：后续章节我们使用哈希算法验证两者一致性时，就当它是几乎没有碰撞或者几率很小的情况，请大家不要钻这个牛角尖。**

### 哈希函数的主要作用 ###

> 为了保证哈希的独一无二性，如果数据在存储或者传输过程中有任何改动或者损坏，哪怕只有1bit，它的哈希值就一定会变。

哈希函数的最常见的一个应用就是进行完整性校验（ `Integrity Check` ），也就是检验数据无损坏。

平时所看到的 `Digest` **摘要**，有时候叫 `Checksum` **校验值**，有时候叫 `Fingerprint` **指纹**，其实都是哈希的另一种说法。

### 哈希实际例子 ###

网站注册登录  
  当我们提交用户名密码的时候，用户名被会直接保存到网站的数据库中，但是密码却不是直接保存的，而是先把密码转换成哈希，保存到数据库中的其实是哈希。即使是公司后台管理人员也拿不到用户的密码。这样万一公司数据库泄露了，用户的密码依然是安全的。而当用户自己登录网站的时候，输入密码提交到服务器，服务器上进行相同的哈希运算，只要算出来的哈希值是一样的，就认为你输入的密码是正确的。

一般来说密码转换成哈希存储有几种处理方式，第一种是在需要哈希的字符串后面加盐，也就是一个无规则字符串。

......
    	// 盐值不能太简单，加盐也称为加签
    	public static final String SALT = "8qkhfjlrk!@Y%^i]ws"; 
    	......
        /**
         * 加盐取摘要，base64编码即可
         * @param strValue 你需要MD5处理的字符串
         * @return 处理后的字符串
         * @throws NoSuchAlgorithmException
         */
        public static String getMD5Str(String strValue) throws NoSuchAlgorithmException {
        
            MessageDigest md5 = MessageDigest.getInstance("MD5");
            return Base64.encodeBase64String(md5.digest((strValue + Constant.SALT).getBytes()));
        }

第二种是需要`MD5`处理的字符串，将每个字符加上盐值，而这个盐值，对于每个用户来说都不一样，比如帐号`zhangsan`的`salt`为`123`，而`lisi`的`salt`为`456`，盐值最好三位数以上，这样彩虹表也难以破解([密码破解的利器——彩虹表（rainbow table）][rainbow table])，即便碰巧破解出盐值，也会让人吐血的发现每个用户盐值`salt`都不一样。我个人喜欢第二种方式。

........
    		// 加盐后MD5摘要，进行比对
            // 对前台输入的密码加盐混淆后生成MD5，与保存在数据库中的MD5密码进行比对
            String md5 = MD5Utils.md5Digest(password, user.getSalt());
            if (!md5.equals(user.getPassword())) {
        
                throw new BussinessException("L002", "密码错误");
            } else {
        
            	// 验证通过，登录成功后的逻辑
    		}
            ........
       /**
         * 对源数据加盐混淆后生成MD5摘要
         * @param source 源数据
         * @param salt 盐值
         * @return 摘要
         */
        public static String md5Digest(String source, Integer salt) {
        
            char[] ca = source.toCharArray();// 字符数组
            // 对每个字符混淆处理
            for (int i = 0; i < ca.length; ++i) {
        
                ca[i] = (char) (ca[i] + salt); // 每个账户的salt都不同
            }
            String target = new String(ca);
            // 对混淆后的字符进行MD5处理
            String md5 = DigestUtils.md5Hex(target);
            return md5;
        }

[https://www.cmd5.com/][https_www.cmd5.com]  
网站介绍如下：  
  针对`md5`、`sha1`等全球通用公开的加密算法进行反向查询，通过穷举字符组合的方式，创建了明文密文对应查询数据库，创建的记录约90万亿条，占用硬盘超过`500TB`，查询成功率95%以上，很多复杂密文只有这个网站才可查询。  
  综上，`MD5`并不安全，所以我们还需要采取加盐的策略，在明文的基础上随机的添加特别难以破解的值。加盐又称为加签，都是加盐签名的意思。

**加盐和不加盐对比如下：**  
比如

public static void main(String[] args) {
        
            // 为了混淆力度更大，建议盐值是3位的整数
            System.out.println(MD5Utils.md5Digest("test", 0)); // 这里不加盐值
        }

打印结果：`098f6bcd4621d373cade4e832627b4f6`  
查询该网站数据库可以得出你的字符串就是`"test"`

![20210422164929175.png][]

但是你加盐之后，比如改为197

public static void main(String[] args) {
        
            // 为了混淆力度更大，建议盐值是3位的整数
            System.out.println(MD5Utils.md5Digest("test", 197)); // 这里不加盐值
        }

打印结果：`89e89f369e07634fbb2286efffb9492b`  
![20210422165357767.png][]

你就会发现， 他根本破解不出来，或者不容易破解出来，至少这个数据库未收录。

## Merkle Tree默克尔树 ##

`Merkle Tree`也叫哈希树，`Merkle Tree` 就是用来做完整性校验的，所谓的完整性校验，就是检查一下数据有没有损坏或者被恶意篡改。`Merkle Tree` 的最大的应用场合就是在点对点网络上，`Git` 版本控制系统，`IPFS` 协议以及比特币以太坊等等项目

### 完整性校验的方法 ###

要实现完整性校验，最简单的方法就是对要校验的整个的数据文件做个哈希运算，把得到的哈希值公布在网上，这样我们把数据下载到手之后，再次运算一下哈希值，如果运算结果相等，就表示我们下载过程中文件没有任何的损坏。如下图

![20200913115956780.png][]

这种简单的采用哈希的方式做数据运算，**比较适合数据本身不做分割且是放在一台服务器上的情况**。如果去某个公司网站上去下载他们的一个软件，就会看到公司网站上公布了这个下载包的哈希值，有了这个哈希值，我们就可以放心的去下载这个软件，下载完做一下完整性校验，就知道这个软件没有损坏。甚至可以放心从其他的不可信网站上去下载这个软件包，因为有了校验机制，也一样可以保证这个包是跟官方的包一模一样的。

### 哈希列表 Hash List ###

在点对点网络上，数据往往都是拆分成很多小碎片去下载的，而且其中很多平台可以认为是不稳定或者是不可信的，很有可能因为网络问题导致下载中断，难不成要从头开始重新下载？这时需要有更加巧妙的做法。最简单的方式就是哈希列表（`Hash List`）

实际点对点网络在传输数据的时候，其实都是把比较大的一个文件切成一个个小的数据块。**如果有一个小块数据在传输过程中损坏了, 那我只要重新下载这一个数据块就行了, 不用重新下载整个文件**。当然这就要求对每个数据块计算哈希值，所有这些小数据块的哈希值都是兄弟关系，这样大家就组成了一个哈希列表。BT 下载的时候，在下载真正的数据之前，会先下载一个哈希列表的，这个就是所谓的**种子文件**。有了各个小块数据的 `hash` 之后，文件就可以从任意的机器上下载了，不用管那些机器是否是安全可信的。

**这时有一个问题就出现了，那么多的哈希，我们怎么保证它们本身都是正确地呢？**

![20200912125856997.png][]   我们需要一个根哈希，把每个小块的哈希值拼到一起，然后对整个这个长长的字符串再做一次哈希运算，最终的结果就是哈希列表的根哈希。于是，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友手里拿到一个正确的根哈希，就可以用它来校验哈希列表中的每一个哈希都是正确的，进而可以保证下载的每一个数据块的正确性了。

`Hash List` 也就是哈希列表形式，就非常适合在点对点网络上存储的大型数据了。

### Merkle Tree 哈希树 ###

`Merkle Tree` 本身也算是一个哈希列表，只不过是在这个基础上又引入了树形结构，从而获得了更高的灵活性。  
  我们把数据分成小的数据块，然后**对每个小的数据块进行哈希**。但是往上走并不是直接去运算根哈希，而是**把相邻的两个哈希合并成一个字符串，再对这个字符串的哈希**，得到一个子哈希，如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 `Merkle Root` 。根哈希有时候也叫主哈希 `Master Hash` ，也有人叫它顶哈希 `Top Hash` 。

![20200912121055232.png][]   相对于 Hash List，Merkle Tree 的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这给很多使用场合就带来了哈希列表所不能比拟的灵活和高性能。 ![20200912131213674.png][]

Merkle Tree 是涉及到了数据结构中的3个概念：哈希、哈希列表、树。

### 总结 ###

单个哈希不能担当大文件在分布式点对点网络上的校验工作，于是我们有了哈希列表的概念。 Merkle Tree 可以认为是哈希列表的一个变体，让哈希列表变得更加灵活高效，因为每次校验都可以单纯拿出树的一个分支来操作。

文章资料参考自nervos网站，中间代码举例为原创

关注、留言，我们一起学习。  
  
\----------------------Talk is cheap, show me the code-----------------------

[Link 1]: https://blog.csdn.net/qq_34115899/category_10508177.html
[rainbow table]: https://www.jianshu.com/p/732d9d960411
[https_www.cmd5.com]: https://www.cmd5.com/
[20210422164929175.png]: https://img-blog.csdnimg.cn/20210422164929175.png
[20210422165357767.png]: https://img-blog.csdnimg.cn/20210422165357767.png
[20200913115956780.png]: https://img-blog.csdnimg.cn/20200913115956780.png
[20200912125856997.png]: https://img-blog.csdnimg.cn/20200912125856997.png
[20200912121055232.png]: https://img-blog.csdnimg.cn/20200912121055232.png
[20200912131213674.png]: https://img-blog.csdnimg.cn/20200912131213674.png