哈希算法与区块链

blockchain
关于区块链的那些事儿。

最后更新于2019-01-26

听说最近区块链很火,作为一个与时俱进、不断学习、聪明勤奋的人,我觉得自己很有必要了解一下这门技术,这篇文章也算是我的学习笔记。

哈希算法

说到区块链,大家不免想到比特币,作为一款数字货币,在交易过程中的安全是必须要保障的,而哈希算法则提供了保障交易安全的可能。这里我们将简要了解哈希算法而不做深入研究。

介绍

SHA-256

哈希(Hash)算法又称散列算法,它能够将任意长度的输入通过一系列运算后转化为一个固定长度的输出。

哈希函数表达式:$Addr=H(key)$

哈希算法种类繁多,比较著名的哈希算法有MD4(由MIT的Ronald L. Rivest设计)、MD5(Rivest对MD4的改进版本)、SHA-1(NIST和NSA设计)等。比特币采用的是SHA-256算法,它输出的是256比特长度的值(SHA1输出的是160比特),比如,经SHA-256处理后:

$$\begin{align}hi \Rightarrow & 8f434346648f6b96df89dda901c5176b \\ & 10a6d83961dd3c1ac88b59b2dc327aa4 \end{align}$$

$$\begin{align}leng \Rightarrow & 23e2b040bab9c2ae5aafc7c03627ff49 \\ & 9a824f6550ef7257b0874b0aff8a3174 \end{align}$$

然而,值得注意的是:

$$\begin{align}Hi \Rightarrow & 3639efcd08abb273b1619e82e78c29a7 \\ & df02c1051b1820e99fc395dcaa3326b8 \end{align}$$

$$\begin{align}Leng \Rightarrow & 2f21ccb58c4228f519fdd12ad0864706 \\ & 906353360389ae7c9ebb8c3685740bf8 \end{align}$$

通过以上两个例子,我们发现即使是一个微小的改变,也会导致Hash之后的结果产生巨大的变化,这使得信息被篡改的风险大大降低。

你可以百度一下哈希在线加密,随便试一试。

总之,通俗地讲,哈希算法具有以下特性:

  • 结果确定:同样的信息通过哈希算法得到的是同样的结果。

  • 难以逆推:根据哈希值是难以逆推出原始信息的,除非你祖宗十八代保佑+你做了十八辈子圣人,运气逆天。

  • 难以篡改:上面的例子已经向我们展示了这一点。需要指出的是,这一特性对于区块链技术十分重要,它决定了区块链的不变性。

另外需要说明的是,所谓的结果确定也即具有抗碰撞能力。碰撞指的是对于同样的信息通过哈希计算产生不同结果的现象,SHA-256具有抗碰撞能力,但是应该注意,找不到碰撞不等于绝对没有碰撞。

算法安全性

那么哈希算法真的安全吗?其实,SHA-0和SHA-1已经有了完整的破解方案:

04年,清华的王小云团队在$2^{40}$复杂度内找到了SHA-0的完整碰撞。

一年后,王小云团队将SHA-0攻击方案优化到了$2^{39}$复杂度内。同时,他们发表了对完整版SHA-1的攻击方案,在少于$2^{69}$计算复杂度内就能找到碰撞

05年8月份,他们再次提高了攻击效率。

理论上讲,SHA-256算法要更加安全,那么在比特币的交易过程中要破解一个哈希值的原始信息又有多难呢?

我们之前就已经说过哈希算法是难以逆推的。但逆推到底可不可能成功呢?答案是可能。然而逆推可不可行呢?答案是不可行。

下面是两个例子:

现在我们掌握了一个年轻人年龄的哈希值,现在需要根据这个值确定他的年龄
这种情况,我们只需要尝试二三十个数,一一比对它们的哈希值即可,工作量并不大。

现在考虑,如果我们获得的哈希值来自一个分散的集合,我们又怎么得到它的原始值呢?
能否尝试随意输入,暴力破解呢?我们考虑256位的哈希值,来看一看工作量:
运气极佳:一次或几次(几十次也很不错了)就找到了答案。如果是这样,你可以靠买彩票发家了,每天买彩票或许就能成世界首富。
运气极差:尝试$2^{256}-1$次(所有的可能),假设你有一个十亿人的团队,每人每秒能尝试10次,每人能活100岁,你可以算算你们需要几辈子才能找到答案。
平均一下:尝试$2^{255}$次之后找到答案。$2^{255}$又是什么概念呢?你可以查查已知宇宙的大小,再和它比较比较。$你同样可以算算自己能在几辈子内找到答案。

上面的例子基本可以让我们了解到,在比特币的交易中,信息的安全是可以得到应有的保障的。而且你要知道,比特币的交易中,信息的加密通常远比这更加复杂。

区块链技术

我们已经对哈希算法有了一个大概的了解,那么什么又是区块链呢?其实,区块链技术还有一个别称——分布式账本技术,区块链在本质上是一个去中心化的数据库,你可以把它看作比特币交易中公开透明的账本。

记账方法

在比特币的交易中,每次记账时,包括序号、记账时间、交易记录在内的信息将被处理为一串Hash值:

$$Hash(序号0,记账时间,交易记录)=…$$

帐页信息和Hash值在一起构成第一个区块。我们暂且将这个Hash值记为$H1$

比特币系统中,每次记账时间间隔约为10分钟,在第二次记账时,将把上一个Hash值和新的序号、记账时间、交易记录处理成新的Hash值:

$$Hash(H1,序号1,记账时间,交易记录)=…$$

这样,第二个区块在记录本页账单信息的同时还包含了上一个交易的信息,按照此方法持续记账,我们在最新的区块中就能获得以往所有的信息。

所有的区块在一起就构成了区块链,这样的记账方法方便检验(只需验证最后一个区块)且不可更改(更改一点信息就会使Hash值发生巨变),能够保证比特币系统的安全。

工作量证明

那么记账的工作是由谁来完成的呢?作为去中心化设计的典型,比特币的记账工作是由该系统中每一个节点完成的。

为了鼓励各个节点记账,在比特币的交易中,记账是有奖励的,每一次记账都能获得一定量的比特币,这也是比特币的发行过程。大家常听到一个耳熟能详的词汇——挖矿,其实挖矿就是记账。

记账有奖励,在每一次交易中,如果记账仅仅是把我们之前提到的信息通过哈希算法处理打包成新的Hash值的话,记账的工作就太简单了,人人都能快速完成,这将引起大家争相记账,这种混乱会导致诸如账单不一致的问题,因此,必须增加记账的难度,使得每次只能有一个人能成功记账,于是比特币引入了工作量证明的机制。

待续

最后更新于19-01-26
助力本站发展