第2章 区块链技术基础

2.1 哈希

哈希（Hash）是一种数学运算转换，即把任意长度的输入值通过哈希算法转换为固定长度的输出值。哈希的目标是把任意长度的输入值压缩到固定长度，并使输出值作为输入值的数字指纹。哈希函数（Hash Function）是给定的输入值x对应的输出值f （x）中的数学函数f。哈希函数的典型特征是，若给定的f （x₁）≠ f （x₂），则不存在x₁=x₂，即不允许输出值不同时输入值相同。对于表T和任意输入值x，若我们可通过将f （x）作为索引来计算出x在表T中存储的位置，则表T可称为哈希表（Hash Table）。碰撞（Collision）是指当输入值x₁≠x₂时，存在f （x₁）= f （x₂）的情况。好的哈希函数要尽量避免碰撞。

哈希函数具有压缩、易计算、抗碰撞等特性，而加密领域的哈希函数需具备以下3个典型特性。

1）抗-原像攻击（Pre-image Resistance）

抗-原像攻击，即给定一个哈希值y= f （x），人们几乎不可能在有限时间内算出x。在加密应用中，抗-原像攻击是非常重要的特性，它可以防止攻击者获取原始的加密内容。举个例子，用户登录网站的密码一般在数据库中存储为哈希值，不会直接存储为密码明文，假定攻击者从数据库中获取到哈希值，他们很难根据哈希值获得密码明文，这意味着攻击者无法登录网站。

2）抗-次原像攻击（Second Pre-image Resistance）

抗-次原像攻击，即给定一个输入值x₁，人们几乎不可能在有限时间内找到一个与x₁相同的值x₂来使 f （x₁）= f （x₂）。这意味着攻击者无法使用一个相近或相似的原像来替换原像。

3）抗碰撞

抗碰撞即很难找到任意的两个相同的输入值 x₁和 x₂，从而使f （x₁）= f （x₂）。它与抗-次原像攻击的不同之处在于， x₁不是指定的，这意味着穷举范围是无穷大的。

常见的加密哈希算法包括MD5、SHA-1、SHA-2，主要应用于文件和信息校验、数字签名验证、密码校验、工作量证明等场景，下面我们对这几种算法进行简单的介绍。

MD5全称为Message-Digest Algorithm 5（信息-摘要算法5），是1991年Ronald Rivest设计的替代MD4的算法，可以参考RFC1321中对其进行的详细描述，是在SHA-2没出现之前广泛应用于安全领域的哈希算法。其特点是对于输入值，会固定输出128bit（128/8=16Byte）的哈希值。但是MD5被发现可以人为构造碰撞，以文件哈希为例，相同的MD5可以通过构造不同的文件让两者的哈希值相等。目前，MD5在来源不可信的情况下不推荐使用，在区块链领域更加不可采用。

SHA-1全称为Secure Hash Algorithm 1（安全哈希算法-1），1995年由美国国家安全局（NSA）设计，并由美国国家标准技术研究所（NIST）发布为联邦数据处理标准（FIPS）。SHA-1会根据输入值生成160bit（160/8=20Byte）的哈希值，哈希值通常的呈现形式为40个十六进制数，又称消息摘要。SHA-1在许多安全协议中得到广泛使用，如TLS（Transport Layer Security）和SSL（Secure Sockets Layer）、PGP（Pretty Good Privacy）、SSH（Secure Shell）、S/MIME （Secure Multipurpose Internet Mail Extensions）和 IPSec （Internet Protocol Security）。SHA-1在2005年已经被发现存在有效攻击方式；2017年2月23日，Google经过两年的研究，声称已经成功破解SHA-1的加密，目前各大机构均推荐使用SHA-2和SHA-3来替换SHA-1。

SHA-2的全称为Secure Hash Algorithm 2（安全哈希算法-2），2001年由NSA设计，由NIST发布为FIPS，是SHA-1的继任者，包括SHA-224、SHA-256、SHA-384、SHA-512，SHA 后面的数字指的是哈希后的位数。下面我们重点描述SHA-256，目前它被重点应用于区块链技术中，因为SHA-256有256bit（256/8=32Byte）的哈希值，每一位可能为0或1，即有2²⁵⁶种组合，对于数量如此庞大的可能性，人们用当下的计算机暴力破解需要漫长的时间，这意味着SHA-256的碰撞概率是极小的。因此，区块链技术大量使用了SHA-256等安全哈希算法。SHA-256通常用64bit的十六进制字符串表示，譬如输入：

测试SHA-256长度字符串。

输出：

90edfab86aace2d98a417426f6f32c3fb13695a2a2e674631b1fdd3c79321343

哈希主要作用于区块链的几个重要场景，包括默克尔树（Merkle Tree）、钱包地址等，比特币等常用的是SHA-256，下面我们详细介绍默克尔树。