区块链：防篡改的哈希加密算法

一、引言

1.A和B打赌

同学A和B在教室里拋硬币，赌谁打扫卫生，正面朝上，则A打扫，反面朝上，则B打扫，这个策略没有什么问题。

然而，如果把情景迁移到网络聊天室，A和B同样进行抛硬币的游戏，估计B就不会答应了，因为当A拋了硬币，B不论是猜正面还是反面，A都可以说Ｂ猜错了。

怎么解决这个问题呢？要不先给抛硬币的结果加密，Ｂ再猜？这个方法可以试一下。

2.考虑对结果加密

假设任意奇数代表硬币正面，任意偶数代表反面。Ａ想一个数375，然后乘以一个258，把其结果告诉Ｂ为96750，并声明Ａ想的375为密钥，由他保管。
在接下来验证结果时，Ａ可以谎称258为他想的数，375为密钥，Ａ还是立于不败之地。那如果Ａ事先把密钥告诉Ｂ呢？Ｂ可以直接算出原始数字，失去了保密作用。

这种知道加密方法就知道了解密方法显然行不通，那有没有一种方法，知道了加密方法仍然无法恢复原文呢？

3.不可逆加密

显然是有的，在加密过程中加入不可逆运算就OK了。Ａ设计新的加密方式：

1.A想个数，然后加上5211314；
2.把结果取平方，选取其中第3~10位，组成一个8位数；
3.再把这个数除以123456求余数，然后把结果告诉B；
4.B猜A想的是奇数还是偶数；
5.A告诉B其猜想的数字，B按照加密过程计算一遍，可以验证结果是否与A给出的一致。

假设Ａ想的数是375，进行加密：

第一步： 375+5211314=5211689
第二步： 5211689x5211689=27161702232721
第三步：16170223mod123456=120943
(mod表示除法的求余数)

B拿到结果120943，但他几乎不能根据120943反算出密匙375。
如果B想要验证A是否说谎：

1. B猜测A想的数字是奇数或者偶数，A进行回答；
2. A告诉B他想的数字是什么；
3. B根据A告知的数字，通过加密算法，可以得到一个结果；
4. 通过验证该结果与A提供结果的一致性，则可判断A是否有说谎。

终于可以抛硬币了……

这种丢掉一部分信息的加密方式称为“单向加密”，也叫哈希算法。

4.等一下

有个问题：

A有没有可能事先找出一奇一偶，按上述加密运算得到一样的结果呢？

这个是有可能的，但可以解决，就是增加上述算法的难度，以致于A很难很难找到。

二、哈希算法

根据以上表述，一个可靠的哈希算法，应该满足：

1. 对于给定的数据M,很容易算出哈希值X=F(M);
2. 根据X很难反算出M;
3. 很难找到M和N使得F(N)=F(M)。

密码学中的哈希函数有3个重要的性质，即抗碰撞性、原像不可逆、难题友好性。

1.抗碰撞性

碰撞性，就是指A同学事先找出一奇一偶使得哈希结果一致，在计算上是不可行的。

首先，把大空间桑拿的消息压缩到小空间上，碰撞肯定是存在的。假设哈希值长度固定为256位，如果顺序取1，2，…2^256^+1， 这2^256^+1个输入值，逐一计算其哈希值，肯定能找到两个输入值使得其哈希值相同。

A同学，看到这里时， 请不要高兴的太早。因为你得有时间把它算出来，才是你的。为什么这么说呢？

根据生日悖论，如果随机挑选其中的2^130^+1输入，则有99.8%的概率发现至少一对碰撞输入。那么对于哈希值长度为256为的哈希函数，平均需要完成2^128^次哈希计算，才能找到碰撞对。如果计算机每秒进行10000次哈希计算，需要约10^27^年才能完成2^128^次哈希计算。

A同学，不要想着作弊了，估计你活不了这么久。当然如果计算机运算能力大幅提升，倒是有可能。

那么完整性还用其他什么用途呢？

用来验证信息的完整性，因为如果信息在传递过程中别篡改，那么运行哈希计算得到的哈希值与原来的哈希值不一样。

所以，在区块链中，哈希函数的抗碰撞性可以用来做区块和交易的完整性验证。

2.原像不可逆

因为一个哈希值对应无数个明文，理论上你并不知道哪个是。就如，4+5=9和2+7=9的结果一样，知道我输入的结果是9，但能知道我输入的是什么数字吗？

如果，对消息m进行哈希计算时，在引入一个随机的前缀r，依据哈希值H(r||m)，难以恢复出消息m，这代表该哈希函数值隐藏了消息m。

所以，B同学，根据结果想反推出原数据，这是不大可能的事，就犹如大海里捞针。

3.难题友好性

难题好友性，指没有便捷的方法去产生一满足特殊要求的哈希值。是什么意思呢，通俗的讲，就是没有捷径，需要一步一步算出来。假如要求得到的哈希结果以若干个0开头，那么计算找到前3位均为0的哈希值和找到前6位均为0的哈希值，其所需的哈希计算次数是呈一定数量关系。

这个可以怎么用呢？在区块链中，可以作为共识算法中的工作量证明。

三、小结

主要描述了哈希函数的3个重要性质：抗碰撞性、原像不可逆、难题友好性。

因为这些重要性质，区块链中的区块和交易的完整性验证、共识算法的工作量证明等功能用哈希函数来实现。

##参考资料
[1].邹均,张海宁.区块链技术指南[M].北京:机械出版社,2016.11
[2].长铗,韩锋.区块链从数字货币到信用社会[M].北京:中信出版社,2016.7
[3].张健.区块链定义未来金融与经济新格局[M].北京:机械工业出版社,2016.6