比特币 (3):区块链中的Hash算法

By | 2018-03-25
49,162 views | 5,510 Comments

请在阅读本文之前或者之后,先重新阅读《精通比特币》的第1章到第7章。

一、Hash算法的身影

可以看到,在生成比特币地址(《精通比特币》第4章提到),以及生成区块唯一标识(《精通比特币》第7章提到):区块Hash值时(即挖矿的过程),都使用了Hash算法,特别是SHA256算法。比特币系统本身也就是加密算法的衍生物。

二、SHA256算法过程

本文主要简述一下SHA256算法的过程,下一篇会大概说一下它的理论基础。

1. 输入信息x

SHA256要求报文长度不超过2^64bit。

2. 补位

因为采用的是分组加密的方法,每组长度是512bit,而原始的信息x,不一定是512的倍数,也就是说不一定能刚好分成每组都是512bit的情况。这时候需要补位。

在x后面先补一个1,然后再补多个0,一直到总长度(x以及补的位数)模512是448

3. 补长度

为什么第二步不直接把总长度补到512的倍数呢,因为后面还要补64位,记录原始信息x的位数。(64 + 448) % 512 = 0。可以看到,只有64位表示原始信息x的位数,所以x的最大长度是2^64。

4. 计算Hash值

前面已经将消息补成了512的倍数,总长度变为512 * N。计算hash值的基本思想是:先将处理完的消息分成N个512bit的数据块:M[1],M[2],……,M[N],然后一块一块的处理:哈希初值H[0]经过第一个数据块M[1]得到H[1],H[1]经过第二个数据块M[2]得到H[2],……,依次处理,最后得到H[N]。每个哈希值,比如H[0],由8个32bit组成,32bit又称为字,也就是说每个hash值都由8个字组成。最后将H[N]的8个字连接成256bit(8 * 32 bit)的最终值。至于为什么可以这么做,我们下一篇再介绍,先看流程。

1) 哈希初值H[0]

SHA256算法中用到的哈希初值H[0](共有8个32bit)为:

H[0][0] = 0x6A09E667
H[0][1] = 0xBB67AE85
H[0][2] = 0x3C6EF372
H[0][3] = 0xA54FF53A
H[0][4] = 0x510E527F
H[0][5] = 0x9B05688C
H[0][6] = 0x1F83D9AB
H[0][7] = 0x5BE0CD19

0x表示的是十六进制,十六进制中一位表示4bit。

注:这些初值是对自然数中前8个质数2、3、5、7、11等的平方根的小数部分取前32bit而来。

2) 循环计算


# M的下标从1开始,M即为M[1], ..., M[N]
for i in range(1, N + 1): 
 # 第一步,先根据16个32bit的原始消息,生成64个32bit
 W = [0] * 64
 for t in range(0, 64):
  if t < 16: 
   W[t] = M[i][t]
  else:
   W[t] = SSIG1(W[t - 2]) + W[t-7] + SSIG0(W[t-15]) + W[t-16]
 # 第二步,将上次的hash值,也就是8个32bit,赋值到8个临时变量,用这8个临时变量计算
 # 原本的hash值在本轮结束的时候仍然需要使用
 a = H[i - 1][0]
 b = H[i - 1][1]
 c = H[i - 1][2]
 d = H[i - 1][3]
 e = H[i - 1][4]
 f = H[i - 1][5]
 g = H[i - 1][6]
 h = H[i - 1][7]
 # 第三步,执行散列计算,内循环是64轮,使用了上面的64个W,以及提前定义好的64个K
 for t in range(0, 64):
  t1 = h + BSIG1(e) + CH(e, f, g) + K[t] + W[t]
  t2 = BSIG0(a) + MAJ(a,b,c)
  h = g 
  g = f 
  f = e 
  e = d + t1
  d = c 
  c = b 
  b = a 
  a = t1 + t2
 # 第四步,将本轮经过64个内循环新计算的临时值和上次的hash值求和,作为本轮最终的hash值
 H[i][0] = a + H[i - 1][0]
 H[i][1] = b + H[i - 1][1]
 H[i][2] = c + H[i - 1][2]
 H[i][3] = d + H[i - 1][3]
 H[i][4] = e + H[i - 1][4]
 H[i][5] = f + H[i - 1][5]
 H[i][6] = g + H[i - 1][6]
 H[i][7] = h + H[i - 1][7]
# 最终H[N]的8个32bit返回,即为该消息的SHA256结果

3) 函数和常量说明

(1) 64个常量K为:

K = [
 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 ]

注:这些常数的取值是从自然数中前64个质数的立方根的小数部分取前32bit而来的。

(2) 利用到的函数为:

# 本段代码没有使用python语法
CH(x, y, z) = (x AND y) XOR ((NOT x) AND z)
MAJ(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
BSIG0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x)
BSIG1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x)
SSIG0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x)
SSIG1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x)

其中,除了与或非外,XOR是异或, ROTR^n是循环右移n位,SHR^n是右移n位。

三、总结

上面就是SHA256的计算过程。至于为什么可以把数据切成好几组计算,为什么需要用到里面的这些函数,请见下一篇。

5,510 thoughts on “比特币 (3):区块链中的Hash算法

  1. Pingback: apk for windows 7 download

  2. Pingback: sous traitance web

  3. UgoRot

    Prior to you start the procedure notify your doctor of any wellness disorders you have that might potentially affect the amount you are prescribed. You will certainly quickly find out exactly how you can purchase Tadalafil that would certainly be equally as high in top quality as its trademark name version, but it will certainly be the exact same aged generic Tadalafil made by a reliable firm. It’s a great opportunity for you to stay away from investing your cash and still obtain excellent quality in return! Shop this medicine at the area temperature out of the reach of people and children to whom it was not recommended. Drinking grapefruit juice is also not recommended as it could cause some possibly dangerous communications with buy tadalafil 5mg. Tadalafil (Cialis) is effective in the treatment of ED (erectile disorder).

    Reply
  4. Pingback: app apk download for windows 10

  5. Pingback: free download for windows 10

  6. Pingback: apps download for windows 10

  7. Pingback: games for pc download

  8. Pingback: pc apps for windows 7

  9. Pingback: sex toy for women

  10. Pingback: MP4 Songs

  11. Pingback: Obiano News

  12. Pingback: JAMB Registration

  13. Pingback: best cbd gummies

  14. Pingback: education science projects

  15. Pingback: strongest bullet vibrator

  16. Pingback: money help

  17. Pingback: Google

  18. oprolevorter

    I’ll immediately snatch your rss feed as I can not in finding your email subscription hyperlink or newsletter service. Do you’ve any? Please permit me understand so that I could subscribe. Thanks.

    Reply

发表评论

电子邮件地址不会被公开。