区块链中的：哈希算法

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

什么是哈希算法。

哈希算法又称散列算法它是一个单向函数可以把任意长度的输入数据转化为固定长度的输出

h\=H(x)h=H(x)h\=H(x)

例如对 morning 和 bitcoin 两个输入进行某种哈希运算得到的结果是固定长度的数字

H("morning") = c7c3169c21f1d92e9577871831d067c8
H("bitcoin") = cd5b1e4947e304476c788cd474fb579a

我们通常用十六进制表示哈希输出。

因为哈希算法是一个单向函数要设计一个安全的哈希算法就必须满足通过输入可以很容易地计算输出但是反过来通过输出无法反推输入只能暴力穷举。

H("???????") = c7c3169c21f1d92e9577871831d067c8
H("???????") = cd5b1e4947e304476c788cd474fb579a

想要根据上述结果反推输入只能由计算机暴力穷举。

哈希碰撞

一个安全的哈希算法还需要满足另一个条件碰撞率低。

碰撞是指如果两个输入数据不同却恰好计算出了相同的哈希值那么我们说发生了碰撞
H("data-123456") = a76b1fb579a02a476c789d9115d4b201
H("data-ABCDEF") = a76b1fb579a02a476c789d9115d4b201

因为输入数据长度是不固定的所以输入数据是一个无限大的集合而输出数据长度是固定的所以输出数据是一个有限的集合。把一个无限的集合中的每个元素映射到一个有限的集合就必然存在某些不同的输入得到了相同的输出。

哈希碰撞的本质是把无限的集合映射到有限的集合时必然会产生碰撞。我们需要计算的是碰撞的概率。很显然碰撞的概率和输出的集合大小相关。输出位数越多输出集合就越大碰撞率就越低。

安全哈希算法还需要满足一个条件就是输出无规律。输入数据任意一个bit某个字节的某一个二进制位的改动会导致输出完全不同从而让攻击者无法逐步猜测输入只能依赖暴力穷举来破解

H("hello-1") = 970db54ab8a93b7173cb48f55e67fd2c
H("hello-2") = 8284353b768977f05ac600baad8d3d17

哈希算法有什么作用

假设我们相信一个安全的哈希算法那么我们认为如果两个输入的哈希相同我们认为两个输入是相同的。

如果输入的内容就是文件内容而两个文件的哈希相同说明文件没有被修改过。当我们从网站上下载一个非常大的文件时我们如何确定下载到本地的文件和官方网站发布的原始文件是完全相同没有经过修改的呢哈希算法就体现出了作用我们只需要计算下载到本地的文件哈希再和官方网站给出的哈希对比如果一致说明下载文件是正确的没有经过篡改如果不一致则说明下载的文件肯定被篡改过。

大多数软件的官方下载页面会同时给出该文件的哈希值以便让用户下载后验证文件是否被篡改

和文件类似如果两份数据的哈希相同则可以100%肯定两份数据是相同的。比特币使用哈希算法来保证所有交易不可修改就是计算并记录交易的哈希如果交易被篡改那么哈希验证将无法通过说明这个区块是无效的。

常用哈希算法

常用的哈希算法以及它们的输出长度如下

哈希算法	输出长度(bit)	输出长度(字节)
MD5	128 bit	16 bytes
RipeMD160	160 bits	20 bytes
SHA-1	160 bits	20 bytes
SHA-256	256 bits	32 bytes
SHA-512	512 bits	64 bytes

比特币使用的哈希算法有两种SHA-256 和 RipeMD160

SHA-256的理论碰撞概率是尝试2的130次方的随机输入有99.8%的概率碰撞。注意2130是一个非常大的数字大约是1361万亿亿亿亿。以现有的计算机的计算能力是不可能在短期内破解的。

比特币使用两种哈希算法一种是对数据进行两次SHA-256计算这种算法在比特币协议中通常被称为hash256或者dhash。

另一种算法是先计算SHA-256再计算RipeMD160这种算法在比特币协议中通常被称为hash160。

const
    bitcoin = require('bitcoinjs-lib'),
    createHash = require('create-hash');

Run

运行上述代码观察对一个字符串进行SHA-256、RipeMD160、hash256和hash160的结果。

区块链不可篡改特性

有了哈希算法的预备知识我们来看比特币的区块链如何使用哈希算法来防止交易记录被篡改。
区块本身记录的主要数据就是一系列交易所以区块链首先要保证任何交易数据都不可修改。

Merkle Hash

在区块的头部有一个Merkle Hash字段它记录了本区块所有交易的Merkle Hash

Merkle Hash是把一系列数据的哈希根据一个简单算法变成一个汇总的哈希。

假设一个区块有4个交易我们对每个交易数据做dhash得到4个哈希值a1a2a3和a4

a1 = dhash(tx1)
a2 = dhash(tx2)
a3 = dhash(tx3)
a4 = dhash(tx4)

注意到哈希值也可以看做数据所以可以把a1和a2拼起来a3和a4拼起来再计算出两个哈希值b1和b2

       ┌───────────────┐               ┌───────────────┐
       │b1=dhash(a1+a2)│               │b2=dhash(a3+a4)│
       └───────────────┘               └───────────────┘
               ▲                               ▲
       ┌───────┴───────┐               ┌───────┴───────┐
       │               │               │               │
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│a1=dhash(tx1)│ │a2=dhash(tx2)│ │a3=dhash(tx3)│ │a4=dhash(tx4)│
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘

最后把b1和b2这两个哈希值拼起来计算出最终的哈希值这个哈希就是Merkle Hash

                     ┌───────────────────┐
                     │merkle=dhash(b1+b2)│
                     └───────────────────┘
                               ▲
               ┌───────────────┴───────────────┐
               │                               │
       ┌───────────────┐               ┌───────────────┐
       │b1=dhash(a1+a2)│               │b2=dhash(a3+a4)│
       └───────────────┘               └───────────────┘
               ▲                               ▲
       ┌───────┴───────┐               ┌───────┴───────┐
       │               │               │               │
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│a1=dhash(tx1)│ │a2=dhash(tx2)│ │a3=dhash(tx3)│ │a4=dhash(tx4)│
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘

如果交易的数量不恰好是4个怎么办

例如只有3个交易时第一个和第二个交易的哈希a1和a2可以拼起来算出b1第三个交易只能算出一个哈希a3这个时候就把a3直接复制一份算出b2这样我们也能最终计算出Merkle Hash

                     ┌───────────────────┐
                     │merkle=dhash(b1+b2)│
                     └───────────────────┘
                               ▲
               ┌───────────────┴───────────────┐
               │                               │
       ┌───────────────┐               ┌───────────────┐
       │b1=dhash(a1+a2)│               │b2=dhash(a3+a3)│
       └───────────────┘               └───────────────┘
               ▲                               ▲
       ┌───────┴───────┐               ┌───────┴───────┐
       │               │               │               │
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌ ─ ─ ─ ─ ─ ─ ┐
│a1=dhash(tx1)│ │a2=dhash(tx2)│ │a3=dhash(tx3)│
└─────────────┘ └─────────────┘ └─────────────┘ └ ─ ─ ─ ─ ─ ─ ┘

如果有5个交易我们可以看到a5被复制了一份以便计算出b3随后b3也被复制了一份以便计算出c2。总之在每一层计算中如果有单数就把最后一份数据复制最后一定能计算出Merkle Hash

                  ┌─────────┐
                  │ merkle  │
                  └─────────┘
                       ▲
           ┌───────────┴───────────┐
           │                       │
         ┌───┐                   ┌───┐
         │c1 │                   │c2 │
         └───┘                   └───┘
           ▲                       ▲
     ┌─────┴─────┐           ┌─────┴─────┐
     │           │           │           │
   ┌───┐       ┌───┐       ┌───┐       ┌ ─ ┐
   │b1 │       │b2 │       │b3 │        b3
   └───┘       └───┘       └───┘       └ ─ ┘
     ▲           ▲           ▲
  ┌──┴──┐     ┌──┴──┐     ┌──┴──┐
  │     │     │     │     │     │
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌ ─ ┐
│a1 │ │a2 │ │a3 │ │a4 │ │a5 │  a5
└───┘ └───┘ └───┘ └───┘ └───┘ └ ─ ┘