3.1 哈希算法
哈希算法在区块链系统中的应用很广泛：比特币使用哈希算法通过公钥计算出了钱包地址、区块头以及交易事务的哈希值，梅克尔树结构本身就是一棵哈希树，就连 挖矿算法都是使用的哈希值难度匹配；以太坊中的挖矿计算也使用了哈希算法，其中的梅克尔–帕特里夏树同样也是一棵哈希树；其他的区块链系统也都会多多少少 使用到各种哈希算法，因此可以说哈希算法贯穿到区块链系统的方方面面。
3.1.1 什么是哈希计算
密码学上的哈希计算方法一般需要具有以下的性质：
·函数的输入可以是任意长的字符串；
·函数的输出是固定长度的；
·函数的计算过程是有效率的。
这个说法比较学术化，说白了，就是通过一个方法将一段任意输入的字符串计算出一个固定长度的值，相当于计算出一个 身份证号。通过哈希算法计算出的结果，是无法再通过一个算法还原出原始数据的，即是单向的，因此适合用于一些身份验证的场合，同时由于哈希值能够起到一个 类似于身份证号的作用，因此也可以用于判断数据的完整性，哪怕数据发生微小的变化，重新计算后的哈希值都会与之前的不一样。
一般来说，为了保证哈希函数在密码学上的安全性，必须满足以下3个条件。
1）抗冲突（collision-resistance）。简单来说，哈希函数抗冲突指的是不同的输入不能产生相 同的输出。这就好像到电影院买票看电影，对于付出真金白银买了电影票的人，他们的座位号不能是一样的。？同时必须说明的是，抗冲突并不是说不会有冲突，只 不过找到有冲突的两个输入的代价很大，不可承受。这就好像暴力**一个有效期为20年的密码，整个**过程长达30年，虽然最后密码被**了，但是由于密 码有效期过了，所以也就失去了意义。
2）信息隐藏（information hiding）。这个特性是指如果知道了哈希函数的输出，不可能逆向推导出输入。这在密码学很好理解：即使敌人截获了公开信道（比如无线电波），获取了传送的哈希信息，敌人也不可能根据这段信息还原出明文。
3）可隐匿性（puzzle friendly）。如果有人希望哈希函数的输出是一个特定的值（意味着有人事先知道了哈希函数的输出结果），只要输入的部分足够随机，在足够合理的时间 内都将不可能**。这个特性主要是为了对付伪造和仿制。近来某位当红歌星的演唱会门票超贵，10000元一张。这就催生了假票行当：伪造个人演唱会的门 票。这里门票是公开的，大家都知道长什么样，用什么材质，这相当于已知哈希函数的输出。可隐匿特性就是要做假票的明明知道输出长什么样，但不知道使用何种 “原料”和“工艺”造出一模一样的票来。
由于哈希算法的输出值是固定的，而原始数据的长度却是多种多样的，这就注定了在理论上存在不同的原始数据却输出同一种哈希值的可能，这种情况在原始数据的 数量极其庞大的时候就会出现。比如，邮件系统的抗垃圾邮件算法，我们一般会对每一个邮件地址计算一个哈希值，存储为过滤库，可是全世界的邮件地址何其多， 而且什么样格式都有，这个时候会对邮件地址进行多种哈希计算，将计算出来的多个值联合起来判断是否存在某个邮件地址，这也是布隆过滤器的基本原理，在比特 币中就使用了布隆过滤器使SPV节点可以快速检索并返回相关数据。
3.1.2 哈希算法的种类
密码学中常用的哈希算法有MD5、SHA1、SHA2、SHA256、SHA512、SHA3、RIPEMD160，下面简单介绍一下。
·MD5（Message Digest Algorithm5）。MD5是输入不定长度信息，输出固定长度128bits的算法。经过程序流程，生成4个32位数据，最后联合起来成为一个 128bits哈希。基本方式为求余、取余、调整长度、与链接变量进行循环运算，得出结果。MD5算法曾被广泛使用，然而目前该算法已被证明是一种不安全 的算法。王晓云教授已经于2004年**了MD5算法。
·SHA1。SHA1在许多安全协议中广为使用，包括TLS和SSL。2017年2月，Google宣布已攻破了SHA1，并准备在其Chrome浏览器产品中逐渐降低SHA1证书的安全指数，逐步停止对使用SHA1哈希算法证书的支持。
·SHA2。这是SHA算法家族的第二代，支持了更长的摘要信息输出，主要有SHA224、SHA256、SHA384和SHA512，数字后缀表示它们生成的哈希摘要结果长度。
·SHA3。看名称就知道，这是SHA算法家族的第三代，之前名为Keccak算法，SHA3并不是要取代SHA2，因为目前SHA2并没有出现明显的弱点。
·RIPEMD-160（RACE Integrity Primitives Evaluation Message Digest160）RIPEMD160是一个160位加密哈希函数。它旨在替代128位哈希函数MD4、MD5和RIPEMD-128。
事实上，除了以上的算法，哈希算法还有很多种，有一些是不太讲究加密特性的，比如在负载均衡领域常用的一致性哈希算法，目的只是将服务器地址快速地计算出一个摘要值，而不是加密，因此会使用一些其他的快速哈希算法。
3.1.3 区块链中的哈希算法
1.区块哈希
所谓区块哈希就是对区块头进行哈希计算，得出某个区块的哈希值，用这个哈希值可以唯一确定某一个区块，相当于给区 块设定了一个身份证号，而区块与区块之间就是通过这个身份证号进行串联，从而形成了一个区块链的结构。这样的结构也是区块链数据难以篡改的技术基础之一。 比如，一共有100个区块，如果要更改10号区块的数据，则11号就不能与10号连接，区块链就会断开，这样等于篡改无效了，而如果篡改了11号，就接着 要篡改12号，以此类推，几乎就是牵一发动全身。如果区块链很长，那么要想更改之前的历史数据几乎就是不可能的了。从这个角度来看，哈希值相当于一个指 针，传统的指针提供了一种获取信息的方法，而哈希指针则提供了一种检验信息是否被改编的方法，如果信息被篡改，那么其哈希值和哈希指针的值必定是不等的。
2.梅克尔树
我们在第1章简单介绍过梅克尔树，梅克尔树在不同的区块链系统中有不同的细节，但本质是一样的，我们就以比特币中 的梅克尔树来说明。比特币中的梅克尔树称为二叉梅克尔树，每一个区块都有自己的梅克尔树，是通过将区块中的交易事务哈希值两两结对计算出新的哈希值，然后 哈希值再两两结对进行哈希计算，递归循环，直到计算出最后一个根哈希值，这样的一棵树也称为哈希树。梅克尔树既能用于校验区块数据的完整性，也能对SPV 钱包进行支付验证。
举一个生活中常见的例子，当我们签订一份n页的合同时，通常都会在每页合同上盖章，只不过每一页上的章都是一样 的，这就给作弊留下了空间。如果我们稍微改变一下做法，给每一页合同盖一个数字印章，并且每一页上的数字印章是前一页数字印章和本页内容一起使用哈希算法 生成的哈希值。例如：
1）合同第一页的数字印章是本页内容的哈希值，即第一页数字印章=Hash（第一页内容）。
2）合同第二页的数字印章是第一页的数字印章及第二页内容加在一起后再哈希的值，第二页数字印章=Hash（第一页的数字印章+第二页内容）。
3）合同第三页的数字印章是第二页的数字印章及第三页内容加在一起后再哈希后的值，即第三页数字印章=Hash（第二页的数字印章+第三页内容）。
4）上述过程以此类推。
这样对第一页合同的篡改必然使其哈希值和第一页上的数字印章不符，且其后的2，3，4，5，…，n页也是如此；对第二页合同的篡改必然使其哈希值和第二页上的数字印章不符，且其后的3，4，5，…，n页也是如此。
从上面的例子，我们可以发现梅克尔树的优势：
1）我们能知道信息是否被篡改；
2）我们还能知道是第几页或者第几块的信息被篡改了。
为了便于理解，我们看下梅克尔树的典型架构，如下图所示。
我们看到，首先这是一个树结构，在底部有4个哈希值，假设某个区块中一共有4条交易事务，那么每条交易事务都计算一个哈希值，分别对应这里的Hash1到 Hash4，然后再两两结对，再次计算哈希值，以此类推，直到计算出最后一个哈希值，也就是根哈希。这样的一棵树结构就称为梅克尔树（merkle tree），而这个根哈希就是梅克尔根（merkle root）。我们再来看一个示意图：
可以看到，每一个区块都是具有一棵梅克尔树结构的，同时可以发现，梅克尔树中的每一个节点都是一个哈希值，因此也可以称之为哈希树，而比特币中的梅克尔树是通过交易事务的哈希值两两哈希计算而成，所以这样梅克尔树称为二叉梅克尔树，那么这样的树结构有什么作用呢？
比特币是分布式的网络结构，当一个节点需要同步自己的区块链账本数据时，并没有一个明确的服务器来下载，而是通过 与其他的节点进行通信实现的。在下载区块数据的时候，难免会有部分数据会损坏，对于这些一条条的交易事务，如何去校验有没有问题呢？这个时候，梅克尔树就 能发挥作用了，由于哈希算法的特点，只要参与计算的数据发生一点点的变更，计算出的哈希值就会改变。我们以第一个示意图来说明，假设A通过B来同步区块数 据，同步完成后，发现计算出的梅克尔根与B不一致，也就是有数据发生了损坏，此时先比较Hash12和Hash34哪个不一致，假如是Hash12不一 致，则再比较Hash1和Hash2哪个不一致，如果是Hash2不一致，则只要重新下载交易事务2就行了。重新下载后，再计算出Hash12并与 Hash34共同计算出新的梅克尔根比较，如果一致，则说明数据完整。我们发现，通过梅克尔树，可以很快找到出问题的数据块，而且本来一大块的区块数据可 以被切分成小块处理。
来源：我是码农，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=104