区块链的那些事—安全守卫者“哈希函数”的详细分析

image.png

首发在先知社区，原文稿件地址：https://xz.aliyun.com/t/2922

工程领域从来没有黑科技，而密码学不仅仅是工程。

一、何为哈希？

密码哈希是一类数学函数，可以在有限合理的时间内将任意长度的消息压缩为固定长度的二进制串，其输出值为成为哈希值或者散列值。哈希在密码学中扮演着十分重要的角色，用于实现数据完整性验证以及认证工作。公式表示为：h=H(m)

函数说明： 
m：任意长度消息（不同算法实现，长度限制不同，有的哈希函数（SHA-3）不限制消息长度，有的限制（SHA-2），但即使有限制其长度也非常大，可以认为是任意长度消息） 
H：哈希函数 
h：固定长度的哈希值

将哈希函数用于工程项目是有其原因的。

• 哈希函数定义——密码哈希函数是一类数学函数，可以在有限合理的时间内，将任意长度的消息压缩为固定长度的二进制串，其输出值称为哈希值，也称散列值。

• 碰撞定义——是指两个不同的消息在同一哈希函数作用下，具有相同的哈希值。

• 哈希函数的安全性——是指在现有的计算资源（包括时间、空间、资金等）下，找到一个碰撞是不可行的。

• 抗强碰撞性——找任意一对不同的消息M1 、M2，使H(M1)=H(M2)在计算上是不可行的。

• 雪崩效应——当一个输入位发生变化时，输出位将有一半会发生变化。

以上的性质中，我们应该重点关注他的抗碰撞性这个特点，因为之后的相关内容均与其有关。

下面，我们就来解释下为什么哈希函数有以上特性（我们以经典的MD5算法来说明）。

image.png

首先对明文进行补位处理。
    （1）将512位的明文分组划分为16个子明文分组，每个子明文分组为32位。
    （2）申请4个32位的链接变量，记为A、B、C、D。
    （3）子明文分组与链接变量进行第1轮运算。
    （4）子明文分组与链接变量进行第2轮运算。
    （5）子明文分组与链接变量进行第3轮运算。
    （6）子明文分组与链接变量进行第4轮运算。
    （7）链接变量与初始链接变量进行求和运算。
    （8）链接变量作为下一个明文分组的输入重复进行以上操作。
    （9）最后，4个链接变量里面的数据就是MD5摘要。
输出128位固定长度的摘要。

因为哈希函数均为多轮处理，所以他的混淆扩散性很好。由于轮数很多以及强大的密码学设计，所以当原文中有一点点内容有所改变都会引起结果的巨大变化。除此之外，由于结果共有128位，所以哈希值的可能性共有2^128这么多，所以重复性也是非常低的（结果空间很大）。其安全性是指在现有的计算资源（时间、空间、资金等）下，找到一个碰撞是不可行的。

详细的MD5分析过程见：

hash算法原理之md5过程

MD5哈希算法学习

二、区块链中的哈希算法

区块链通过哈希算法对一个交易区块中的交易信息进行加密，并把信息压缩成由一串数字和字母组成的散列字符串。区块链的哈希值能够唯一而准确地标识一个区块，区块链中任意节点通过简单的哈希计算都可以获得这个区块的哈希值，计算出的哈希值没有变化也就意味着区块中的信息没有被篡改。

对于区块链来说，哈希函数在其项目中有以下优点：

• collision-free 即冲突概率小:
  x != y => hash(x) != hash(y)

• 能够隐藏原始信息：
  例如区块链中各个节点之间对交易的验证只需要验证交易的信息熵，而不需要对原始信息进行比对，节点间不需要传输交易的原始数据只传输交易的哈希即可，常见算法有SHA系列和MD5等算法

在比特币系统中使用了两个密码学哈希函数，一个是SHA256，另一个是PIPEMD160.后者用于生成比特币地址，而前者的用处更为丰富。

1 PIPEMD160算法

RIPEMD (RACE原始完整性校验讯息摘要)是一种加密哈希函数，由 鲁汶大学 Hans Dobbertin,Antoon Bosselaers 和 Bart Prenee组成的COSIC 研究小组发布于1996年。 RIPEMD是以MD4为基础原则所设计的 ，而且其表现与更有名的SHA-1类似.

此算法主要用于比特币的地址方面。在我之前的文章中对此也有所提及区块链安全的那些事—匿名性以及隐私性。对于地址的生成，具体的步骤如下：

• 1 随机选取一个32字节的数作私钥

• 2 通过椭圆曲线算法（ECDSA-secp256k1）由私钥推出公钥（共65字节， 1字节 0x04, 32字节为x坐标，32字节为y坐标）

• 3 将公钥通过 SHA-256 哈希算法处理，得到32字节的哈希值

• 4 对第3步得到的哈希值，通过PIPEMD-160算法得到20字节的哈希值

• 5 把由版本号+第4步得到的哈希值组成的21字节数据进行双SHA-256哈希运算，得到的哈希值的前4字节做校验和，放置到21字节的末尾

• 对25字节数据进行Base58编码，得到的就是比特币地址

上述内容中的第四步我们就用到了PIPEMD-160算法，该算法经历了补位、补长度、轮函数计算最终输出了20个字节的固定长度数据。由哈希函数难重复的特性（为了避免两个节点的地址出现相同的情况），我们在地址生成过程中调用了该函数，并得到了唯一的节点地址。

详细算法过程请参考：加密散列-PIPEMD160

2 SHA256算法

SHA256属于SHA（Secure Hash Algorithm，安全哈希算法）家族一员，是SHA-2算法簇中的一类，对于小于264位的消息，产生一个256位的消息摘要。

SHA256是构造区块链所用的主要密码哈希函数。区块头部信息以及交易数据均是用此哈希去计算，以保证数据的完整性。同时在比特币中，基于寻找给定前缀的SHA256哈希值理念，专家设计了工作量证明的共识机制。

image.png

根据上述图片所示，SHA-256其计算过程分为两个阶段：消息的预处理和主循环。在消息的预处理阶段，主要完成消息的填充和扩展填充，将所有输入的原始消息转换为n个512比特的消息块，之后对每个消息块利用SHA256压缩函数进行处理。这个计算流程就是一个迭代计算的过程，当最后1个消息块（第n块）处理完毕后，最终输出值就是原始消息的SHA256值。

我将详细的算法流程放在了下面：

image.png image.png image.png image.png image.png

在比特币系统中，SHA256最重要的是被用来完成POW（工作量证明）。按照我之前写过的激励机制区块链的那些事—论激励机制，Pow要求节点数和算力大致匹配，因为需要通过CPU的计算能力来进行投票、然而随着人们对SHA256的计算由CPU逐渐升级为GPU搭配FPGA直至ASIC矿机，这使得节点数和Pow算力逐渐失配。

对于Pow机制的引入，我们用下面的一个通俗的例子进行讲解：

场景一、A和B在篮球场


A：B，你是不是口渴了，你要不要去买水喝，顺便帮我买一瓶哈。

B：呵呵，你的小心思我还不知道，你自己也口渴了吧，你去，我不去。

A：哎哎，咱们不扯这些没用的，来抛硬币，好不好，正面你去，反面我去，公平吧，如何？

B：好吧。

………

场景二、A与B即时聊天中


B：A，今天来我家玩，来的路上，有一家披萨店，很好吃，顺便带一点哈。

A：哦，要不你来我家玩吧，你顺便带上披萨。

B：A，你竟然都这么说了，看来只能抛硬币解决了。

A：丫的，这个怎么抛，我怎么知道你有没有搞鬼。

B：嗯，那到也是。

1.考虑对结果加密


B：我心中想一个数，假设为N，然后N在乘以一个数P，得到结果M。N是我的密钥，我把结果M告诉你。你来猜N是奇数还是偶数，猜中了，算你赢。


A：这不行，如果你告诉我M是12，我猜N是奇数，你可以说N是4，P是3。我猜M是偶数，你可以说N是3，P是4。要不你告诉我M是多少的时候，也告诉我P是多少。


B：那这不行，告诉你M和P，不等于告诉你N是多少了，还猜个屁。不行得换个方式。

对于上述问题，我们就可以考虑使用哈希函数去处理。

我们知道哈希函数是不可逆的，m=>H(m)而 H(m) !=>m。所以A可以想一个m然后给B其H(m)，之后B进行猜测m相关信息，此时A可以公开对m进行验证，并不存在造假行为。

上述又称为原像不可逆。

3 哈希指针链

哈希指针是一类数据结构，除了包含通常的指针外，还包括一些数据信息以及这些信息相关的密码哈希值，这就使得正常的指针可用于取回信息。哈希指针用于验证信息是否发生改变，如下图表示了一个哈希指针链。

区块链就可以看成一类使用哈希指针的链表。这个链表链接一系列区块，每个区块包含数据以及只想表前一个区块的指针。区块中，前一个区块指针由哈希指针替换，因此每个区块不仅仅交代了前一个区块的位置，也提供了一个哈希值去验证区块中的数据是否变化。

4 Merkle哈希树

Merkle哈希树是一类基于哈希值的二叉树或多叉树，其叶子节点上的值通常为数据块的哈希值，而非叶子节点上的值，是将该节点的所有子节点的组合结果的哈希值。

image.png

在上图中我们可以知道，Hash-0节点是由hash 0-0 与 hash 0-1节点的值计算得到的。而 hash 0-0与hash0-1分别存储了L1、L2。于是像hash 0这种的非叶子节点的哈希值被称为路径哈希值，而叶子节点的哈希是实际数据的哈希。

而Merkle哈希树有什么作用呢？在计算机领域中，此应用通常用于进行完整性验证处理。其会减少数据传输量以及计算的复杂度。例如：A向B传输了一组数据块的哈希值，之后为了验证传输的值是否是正确的，B就会通过根哈希值进行验证。之后B会将自己的根哈希与A进行比较，只有根没有问题，那么所有的区块将都是正确的（基于哈希的强碰撞特性）。倘若根的值不同，那么我们通过此树也会降低定位问题区块的难度。（类似于二分，最后的时间复杂度为O(log(n))）。

下面举例说明如何验证。加入我需要验证Hash 0-0的区块中的哈希值是否正确，那么我只需要获得Hash 0-1、Hash 1这两个值就好（根节点默认拥有）。由此一来，我们减少了非常大的数据传送量（与获取所有的值相比）。

三、哈希的安全性—生日悖论与攻击

虽然我们知道哈希具有强碰撞性，但是哈希的范围终究是有限的（但是足够大）。例如，哈希的长度为256位，那么意味着我若从1，2，3.....，2^256+1这么列举出来，那么我至少会得到一组计算结果相同的哈希值。

那么什么是生日悖论呢？下面我引用一个例子来说明生日悖论

小明最近十分勤奋好学，看了很多数学书籍，数学成绩上升很快，于是被老师提拔为新任班长。刚好，小红最近快过生日了，于是小红就来问小明自己班上，或者隔壁班有没有和她生日相同的同学。小明知道自己班上有41个同学，而隔壁班上的人稍微少一点只有23个，但是小明手上现在没有花名册。于是他对小红说，我们班上一定有两个生日相同的人，隔壁班上有一半的可能有两个生日相同的人，但是我不太确定是不是你。

小红十分疑惑，问他：你怎么这么确定我们班上有生日相同的人，隔壁班上有一半可能有生日相同的人？

小明故作神秘的笑而不语，然后问小红： “你觉一个有23个同学的班上，有生日相同的同学的概率是多少？”

“23/365吧，这个概率应该很小吧”，小红说。

“但是，你的答案正确的概率更小。”，小明说。

Why？  OK，right now！我们来回答这个问题吧，首先需要提出一个概念：生日悖论。什么是生日悖论？其实就是上文中小明向小红提的那个问题；在一个23个人的人群中，有两人生日相同的概率是多少？我们直觉的答案是23/365，但是实际上，答案应该是0.5。同样，在一个41人的人群中，有两人生日相同的概率是0.9而不是40/365。这就是所谓的生日悖论！

是不是感觉到很奇怪？

但是，why？  要回答这一个问题，我们只需要做一个简单的计算：依次考虑每个人的生日，

第一个人：365/365；

第二个人；364/365；

第三个人：363/365；

……

第n个人：（365-n+1）/365

那么，在一个n人的群体中，有至少两人生日相同的概率为1-（365/365 * 364/365 * 363/365……（365-n+1）-365）

从上面的等式我们可以得知：

当n=23时，概率为0.5；

当n=41时，概率为0.9。

所以，小明才有把握说隔壁班上一定有生日相同的人 而自己班上有百分之五十的可能性有生日相同的人。

公式如下图：

image.png

对于生日攻击，我们进行如下解释：

A要对一个合同文件进行签名，然后把合同文件和签名一起发送给接收者。 
签名的方法：计算文件的哈希值（m位），然后使用A的私钥对这个哈希值进行加密。

接收者使用A的公钥进行解密，然后比较哈希值，这样他就能确认：

接收到的合同文件是A发送的 （因为：可以使用A的公钥对加密的哈希值进行解密）
合同文件未被修改过 （因为：解密的哈希值与合同文件的哈希值相同）

image.png

攻击者B想要伪造一份假合同文件，然后发送给接收者，并使接收者仍然相信：

接收到的合同文件是A发送的 （要求：必须能用A的公钥对加密的哈希值进行解密）

合同文件未被修改过 （要求：解密的哈希值与合同文件的哈希值相同）

image.png

攻击方法：

B先准备 2m/2 个有效合同文件（集合X），每个文件包含与原合同文件相同的意思。 
B再准备 2m/2 个伪造合同文件（集合Y），每个文件也都是希望的伪造合同的意思。

注：要产生包含相同意思的许多文件，其实不难做到。 例如要生成 2^32 个文件，方法是： 在文件中找到32个地方，每个地方使用两种方式表达相同意思，这样组合起来，就有了 2^32 个文件，这些文件要表达的意思都相同。

然后比较集合X和集合Y，找到哈希值相同的两个文件，一份是有效合同，一份是伪造合同。

B成功的概率会大于0.5，如果没有找到匹配的文件，就再准备更多的有效文件和伪造文件，直到找到两个匹配的文件。

B把找到的有效合同文件提供A，A看了一下，没什么问题，就做了签名，然后发送给接收者。

在接收者收到消息之前，B截获了这个消息，然后使用伪造合同替换了有效合同，再把伪造合同和原签名一起发送给接收者。

因为伪造合同与有效合同的哈希值相同，所以它们产生相同的签名。 

四、哈希算法的延伸—布隆过滤器

布隆过滤器是基于哈希算法的一种大胆的尝试。首先我们要了解Hash快速查找方法，这种方法比较简单，所以这里我们就不进行解释了。而我们知道传统的基于哈希的映射方法存在很大弊端，既需要开辟很大的数组空间来存储结果，并且会有很严重的冲突概率。于是“布隆过滤器”则孕育而生。

image.png

简单来说，其采用了多个hash函数来提高空间利用率。对一个给定的输入，多个哈希可以计算出多个地址，并分别在相应的地方标记1（如上图中一个邮件地址可以被八个函数计算、映射。）进行查找时，如果此八个地址均为1，那么我们就很有把握断定该输入的确存在。此方法大大提高了空间利用率，可以使用较少空间来表示较大集合的存在关系。

再者，我们可以发现此过滤器虽然存在误报情况，但是绝对不会存在漏报的情况。

详细解释请看布隆过滤器

五、总结

密码学是区块链的核心理论，而哈希又是密码学的代表作。在上述内容中，我们从什么是密码学开始，到区块链中的哈希算法到最后的哈希经典应用。一步一步从浅入深，而除了保证数据安全，提高工作效率外，哈希算法也在以后的区块链发展中有越来越重要的地位。希望文章能为大家带来帮助。

六、参考链接

• 1 https://blog.csdn.net/s_lisheng/article/details/77937202?locationNum=7&fps=1

• 2 https://shadowdragons.github.io/2018/04/05/ripemd160/

• 3 https://blog.csdn.net/s_lisheng/article/details/77937202?locationNum=7&fps=1

• 4 https://blog.csdn.net/ddk3001/article/details/52647990

• 5 https://blog.csdn.net/qq_16234613/article/details/82798892

本稿为原创稿件，转载请标明出处。谢谢。