• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

FPGA应用篇【0】比特币SHA256算法实现——原理分析

互联网 diligentman 2周前 (05-03) 7次浏览

点开这篇文章的人应该已经都听说过比特币了,如果稍有了解的人就会说比特币挖矿是利用了双哈希算法SHA256。从2019年末到现在,比特币的价格经过了丧心病狂的上涨,导致市场上矿机价格飙升,大家也都买不到显卡了。不过显卡的价格不是比特币的锅,因为显卡已经几乎完全挖不到比特币了,比特币已经完全是矿机的天下。这里我们不探讨市场行为,不探讨挖矿是否浪费资源,单纯从可行性角度探讨用FPGA挖矿

不过阅读这篇博客的看官们请注意:这篇文章没法帮你挖到矿,原因很简单,现在随便一个矿机都能到达TH/s量级,而鄙人在FPGA上实现的最高不过100MH/s,不仅速度有量级的区别,而且能量利用率也远远不够。看到这里的看官如果还没关,那说明是对实现的技术感兴趣(或者就是好奇),那么客官里边请~

FPGA应用篇【0】比特币SHA256算法实现——原理分析

  • 哈希算法介绍
    • 初始化流程
    • 主循环
    • 测试案例
    • 比特币算法
  • 软件代码仿真
  • 硬件架构设计
  • 结论

哈希算法介绍

哈希算法是一种确定性的不可逆密码函数,对于一个给定长度的字符串,它能生成一个固定长度的密码字符串,如果有人改动了输入字符串中的任意一个字符,哪怕只是改了一个位置,都会导致输出密码串有很大的区别,由此可以用来快速确定是否有人修改了原文。比特币挖矿算法就是利用了哈希算法的不可逆性和混淆特性,让矿工不断尝试碰撞来得到结果,模拟挖矿的过程

在这篇英文文档中介绍了SHA256,SHA384和SHA512三种哈希算法的细节:Descriptions of SHA-256, SHA-384, and SHA-512

下面的内容是基于这篇文档的翻译和注释内容

初始化流程

被哈希编码的信息首先要:

  1. 在信息流末端补充信息,直到信息流长度为512比特的整数倍。补充的方式是先补充一位1,再补充k位0,使得最后长度对512的余数为448,最后补上64位为原始信息流的比特长度
  2. 把信息流分成512比特长的信息块

    M

    (

    1

    )

    M^{(1)}

    M(1)

    M

    (

    2

    )

    M^{(2)}

    M(2)……每一个信息快按照32bit分成16个小块

    M

    0

    (

    i

    )

    ,

    .

    .

    .

    ,

    M

    15

    (

    i

    )

    M_0^{(i)},…,M_{15}^{(i)}

    M0(i),...,M15(i)

信息快依次进行哈希编码,初始哈希值为

H

(

0

)

H^{(0)}

H(0),之后的编码公式为

H

(

i

)

=

H

(

i

1

)

+

C

M

(

i

)

(

H

(

i

1

)

)

H^{(i)}=H^{(i-1)}+C_{M^{(i)}}(H^{(i-1)})

H(i)=H(i1)+CM(i)(H(i1))

在这里C是SHA-256压缩方程,

H

(

i

)

H^{(i)}

H(i)

M

i

M^i

Mi的哈希值,而这里的加法是32bit的mod

2

32

2^{32}

232加法,例如

0

x

F

F

F

F

_

F

F

F

F

+

0

x

0000

_

0001

=

0

x

0000

_

0000

0xFFFF_FFFF + 0x0000_0001=0x0000_0000

0xFFFF_FFFF+0x0000_0001=0x0000_0000

SHA-256压缩方程C中有几个运算符需要提前定义,这里所有运算符针对的是32位数(原文中取反符号的定义为补码,个人理解这里应该是取反):

符号 简介

oplus

按位异或

land

按位与

lor

按位或

¬

lnot

¬

取反
+ mod

2

32

2^{32}

232加法

R

n

R^n

Rn

右移n位,高位补符号位

S

n

S^n

Sn

循环右移n位

哈希值的初始值是由初始8个素数(2,3,5,7,11,13,17,19)平方根的二进制小数部分头32位得到的:

H

1

(

0

)

=

0

x

6

a

09

e

667

H

2

(

0

)

=

0

x

b

b

67

a

e

85

H

3

(

0

)

=

0

x

3

c

6

e

f

372

H

4

(

0

)

=

0

x

a

54

f

f

53

a

H

5

(

0

)

=

0

x

510

e

527

f

H

6

(

0

)

=

0

x

9

b

05688

c

H

7

(

0

)

=

0

x

1

f

83

d

9

a

b

H

8

(

0

)

=

0

x

5

b

e

0

c

d

19

H_1^{(0)}=0x6a09e667\ H_2^{(0)}=0xbb67ae85\ H_3^{(0)}=0x3c6ef372\ H_4^{(0)}=0xa54ff53a\ H_5^{(0)}=0x510e527f\ H_6^{(0)}=0x9b05688c\ H_7^{(0)}=0x1f83d9ab\ H_8^{(0)}=0x5be0cd19

H1(0)=0x6a09e667H2(0)=0xbb67ae85H3(0)=0x3c6ef372H4(0)=0xa54ff53aH5(0)=0x510e527fH6(0)=0x9b05688cH7(0)=0x1f83d9abH8(0)=0x5be0cd19

主循环

主要循环的伪代码如下:

For i = 1 to N // N是补位后的信息快数量
{
  // a,b,c,d,e,f,g,h是八个哈希状态寄存器,每个32比特,如果是第一个信息快,则用初始哈希值
  a = H_1;
  b = H_2;
  c = H_3;
  d = H_4;
  e = H_5;
  f = H_6;
  g = H_7;
  h = H_8;
  // 使用SHA-256压缩方程来更新八个哈希状态
  For j = 0 to 63
  {
    // Ch, Maj, Sig0, Sig1, K 和W会在后面介绍
    T1 = h + Sig1(e) + Ch(e, f, g) + K[j] + W[j];
    T2 = Sig0(a) + Maj(a, b, c);
    h = g;
    g = f;
    f = e;
    e = d + T1;
    d = c;
    c = b;
    b = a;
    a = T1 + T2;
  }
  // 使用八个哈希状态来更新哈希值
  H_1 = a + H_1;
  H_2 = b + H_2;
  ...
  H_8 = h + H_8;
}
H_final = {H_1, H_2,..., H_8}; // 最终结果

画成流程图如下
FPGA应用篇【0】比特币SHA256算法实现——原理分析

上述伪代码中的W是扩展信息块,分为64份,

W

0

,

W

1

,

.

.

.

,

W

63

W_0, W_1,…,W_{63}

W0,W1,...,W63,它们的计算方式伪代码如下:

For j = 0 to 63
{
  if(j=0, 1,...,15)
    W[j] = M_i[j]
  else
    W[j] = Ep1(W[j-2]) + W[j-7] + Ep0(W[j-15]) + W[j-16]
}

其中M_i是输入数据,W_0至W_15是直接使用输入数据进行初始化的,输入是512比特的数据块,分为16块32比特的数据块,作为M_i。这同样可以画成流程图如下
FPGA应用篇【0】比特币SHA256算法实现——原理分析

另外其中的K是一组常数,它的具体数值为(形式为{

K

0

K_0

K0,

K

1

K_1

K1,…,

K

63

K_{63}

K63}):

{
	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
};

伪代码和扩展逻辑块计算中有六个逻辑函数Ch, Maj,

Σ

0

Sigma_0

Σ0 (Sig0),

Σ

1

Sigma_1

Σ1 (Sig1),

ϵ

0

epsilon_0

ϵ0 (Ep0)和

ϵ

1

epsilon_1

ϵ1 (Ep1),它们的计算方式如下:

C

h

(

x

,

y

,

z

)

=

(

x

y

)

(

¬

x

z

)

M

a

j

(

x

,

y

,

z

)

=

(

x

y

)

(

x

z

)

(

y

z

)

Σ

0

(

x

)

=

S

2

(

x

)

S

13

(

x

)

S

22

(

x

)

Σ

1

(

x

)

=

S

6

(

x

)

S

11

(

x

)

S

25

(

x

)

ϵ

0

(

x

)

=

S

7

(

x

)

S

18

(

x

)

R

3

(

x

)

ϵ

1

(

x

)

=

S

17

(

x

)

S

19

(

x

)

R

10

(

x

)

Ch(x, y, z) = (xland y)oplus (lnot xland z)\ Maj(x,y,z) = (xland y)oplus (xland z)oplus (yland z)\ Sigma_0(x) = S^2(x)oplus S^{13}(x) oplus S^{22}(x)\ Sigma_1(x) = S^6(x)oplus S^{11}(x) oplus S^{25}(x)\ epsilon_0(x) = S^7(x)oplus S^{18}(x) oplus R^3(x)\ epsilon_1(x) = S^{17}(x) oplus S^{19}(x) oplus R^{10}(x)

Ch(x,y,z)=(xy)(¬xz)Maj(x,y,z)=(xy)(xz)(yz)Σ0(x)=S2(x)S13(x)S22(x)Σ1(x)=S6(x)S11(x)S25(x)ϵ0(x)=S7(x)S18(x)R3(x)ϵ1(x)=S17(x)S19(x)R10(x)
上面所有的逻辑计算都是32位的

测试案例

如果输入字符串为一个24bit的"abc",每个字符占用8个bit,则补位后的数据为

61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018

其哈希值最终结果为

ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad

当中随着时间推移,它的8个哈希状态变化如下,可以再仿真时提供参考:
FPGA应用篇【0】比特币SHA256算法实现——原理分析
FPGA应用篇【0】比特币SHA256算法实现——原理分析
FPGA应用篇【0】比特币SHA256算法实现——原理分析

比特币算法

现在的加密货币矿工已经很少有单独行动的,一般都通过矿池运作,从矿池获取数据头(608位,下一篇会介绍数据头的获取方式),填充32位的变量nounce,进行双重SHA256运算,观察结果的开头n位是否为0,如果符合条件则将算出的结果返回给矿池服务器,获得收益。不过这个收益不是1个比特币,而是按照服务器给你配置的难度系数获得的,难度系数和结果要求的开头n位0相关,n越大,难度越大,现在挖矿的难度要求已经非常大,至少70位,服务器会根据你的算力给你降低一定难度,使得你在一定时间内可以算出结果来(虽然算力需求也很高)

有关于挖矿算法,可以参考知乎的这篇文章:比特币挖矿算法详解

这里需要特别注意的是,比特币挖矿算法使用的是双重SHA256算法,第一重输入为640位,计算出第一个256位中间结果;再将这256位中间结果作为输入进入第二重SHA256算法,得到最终的256位结果

本文给出一个输入和输出,以及中间结果的案例,有需要的同学甚至可以以此为参考自己写一个逻辑:

BYTE input[] = {0x00,0x00,0x00,0x20,0xe3,0x02,0x67,0xc7,0x5d,0x2d,0x24,0xb7,0xdf,0xd8,0xb6,0x45,
	            0x9f,0xd8,0x37,0x44,0x79,0xd3,0xeb,0x27,0x8c,0x6a,0x0b,0x00,0x00,0x00,0x00,0x00,
	            0x00,0x00,0x00,0x00,0xf6,0x5c,0x34,0x24,0x2c,0x47,0x50,0x07,0x67,0xb5,0x34,0xc9,
	            0x49,0xc0,0xa3,0x8a,0xf4,0x99,0x07,0xb9,0x4a,0x6e,0x13,0x63,0x21,0x40,0x7c,0xbc,
	            0x19,0xd2,0x7e,0x62,0x87,0x07,0x2e,0x60,0xb9,0x21,0x0d,0x17,0x40,0x00,0x8b,0xf2};
BYTE middle_result[] = {0x61,0xa5,0x03,0x1b,0x3e,0x78,0x71,0xa6,
                        0x38,0x22,0x1c,0x99,0xc0,0xaa,0x10,0xd1,
                        0x2b,0x2f,0x4b,0x48,0x94,0xab,0xa3,0x5b,
                        0x0d,0x25,0x80,0x59,0x7d,0xe2,0x7c,0xcc};
BYTE result[] = {0x00,0x00,0x01,0xfe,0x42,0x2c,0x0e,0x30,
                 0x40,0xf5,0x6d,0x96,0x99,0xe2,0xfb,0xd6,
                 0x0f,0xbd,0x0e,0x8e,0x5d,0x64,0xfc,0x22,
                 0x22,0xc7,0x91,0x28,0x68,0xf1,0x7e,0x47};

可以看到最终结尾的头20比特为0,这么设置可以让人快速确认结果是正确的。当然实际挖矿不会让你只有20位的

软件代码仿真

下面用C语言实现SHA256的基础功能。为了凸显算法细节,我们这里不调用任何库文件。具体代码参考了B-con的github并加以提取修改如下:

/*************************** HEADER FILES ***************************/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

/****************************** MACROS ******************************/
#define SHA256_BLOCK_SIZE 32            // SHA256 outputs a 32 byte digest

#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))
#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

/**************************** DATA TYPES ****************************/
typedef unsigned char BYTE;             // 8-bit byte
typedef unsigned int  WORD;             // 32-bit word, change to "long" for 16-bit machines

typedef struct {
	BYTE data[64];
	WORD datalen;
	unsigned long long bitlen;
	WORD state[8];
} SHA256_CTX;


/**************************** VARIABLES *****************************/
static const WORD k[64] = {
	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
};

数据定义部分结束,下面是SHA256算法的核心部分,首先是16个数据位的更新以及8个状态寄存器的更新函数sha256_transform()

/*********************** FUNCTION DEFINITIONS ***********************/
void sha256_transform(SHA256_CTX *ctx, const BYTE data[])
{
	WORD a, b, c, d, e, f, g, h, i, j, t1, t2, W[64];

	for (i = 0, j = 0; i < 16; ++i, j += 4)
		W[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);
	for ( ; i < 64; ++i)
		W[i] = SIG1(W[i - 2]) + W[i - 7] + SIG0(W[i - 15]) + W[i - 16];

	a = ctx->state[0];
	b = ctx->state[1];
	c = ctx->state[2];
	d = ctx->state[3];
	e = ctx->state[4];
	f = ctx->state[5];
	g = ctx->state[6];
	h = ctx->state[7];

	for (i = 0; i < 64; ++i) {
		t1 = h + EP1(e) + CH(e,f,g) + k[i] + W[i];
		t2 = EP0(a) + MAJ(a,b,c);
		h = g;
		g = f;
		f = e;
		e = d + t1;
		d = c;
		c = b;
		b = a;
		a = t1 + t2;
	}

	ctx->state[0] += a;
	ctx->state[1] += b;
	ctx->state[2] += c;
	ctx->state[3] += d;
	ctx->state[4] += e;
	ctx->state[5] += f;
	ctx->state[6] += g;
	ctx->state[7] += h;
}

sha256_init()函数是八个状态寄存器的初始化函数

void sha256_init(SHA256_CTX *ctx)
{
	ctx->datalen = 0;
	ctx->bitlen = 0;
	ctx->state[0] = 0x6a09e667;
	ctx->state[1] = 0xbb67ae85;
	ctx->state[2] = 0x3c6ef372;
	ctx->state[3] = 0xa54ff53a;
	ctx->state[4] = 0x510e527f;
	ctx->state[5] = 0x9b05688c;
	ctx->state[6] = 0x1f83d9ab;
	ctx->state[7] = 0x5be0cd19;
}

sha256_update()函数的作用是将输入数据data分为长度为512比特的数据块,留下最后一个长度不足512比特的数据块等待最后操作

void sha256_update(SHA256_CTX *ctx, const BYTE data[], size_t len)
{
	WORD i;

	for (i = 0; i < len; ++i) {
		ctx->data[ctx->datalen] = data[i];
		ctx->datalen++;
		if (ctx->datalen == 64) {
			sha256_transform(ctx, ctx->data);
			ctx->bitlen += 512;
			ctx->datalen = 0;
		}
	}
}

最后一个数据块需要根据总数据长度进行填充,进行最后一次更新。另外需要考虑大头优先和小头优先的区别,将最终数据进行转换输出。这些操作由sha256_final完成

void sha256_final(SHA256_CTX *ctx, BYTE hash[])
{
	WORD i;

	i = ctx->datalen;

	// Pad whatever data is left in the buffer.
	if (ctx->datalen < 56) {
		ctx->data[i++] = 0x80;
		while (i < 56)
			ctx->data[i++] = 0x00;
	}
	else {
		ctx->data[i++] = 0x80;
		while (i < 64)
			ctx->data[i++] = 0x00;
		sha256_transform(ctx, ctx->data);
		memset(ctx->data, 0, 56);
	}

	// Append to the padding the total message's length in bits and transform.
	ctx->bitlen += ctx->datalen * 8;
	ctx->data[63] = ctx->bitlen;
	ctx->data[62] = ctx->bitlen >> 8;
	ctx->data[61] = ctx->bitlen >> 16;
	ctx->data[60] = ctx->bitlen >> 24;
	ctx->data[59] = ctx->bitlen >> 32;
	ctx->data[58] = ctx->bitlen >> 40;
	ctx->data[57] = ctx->bitlen >> 48;
	ctx->data[56] = ctx->bitlen >> 56;
	sha256_transform(ctx, ctx->data);

	// Since this implementation uses little endian byte ordering and SHA uses big endian,
	// reverse all the bytes when copying the final state to the output hash.
	for (i = 0; i < 4; ++i) {
		hash[i]      = (ctx->state[0] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 4]  = (ctx->state[1] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 8]  = (ctx->state[2] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 12] = (ctx->state[3] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 16] = (ctx->state[4] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 20] = (ctx->state[5] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 24] = (ctx->state[6] >> (24 - i * 8)) & 0x000000ff;
		hash[i + 28] = (ctx->state[7] >> (24 - i * 8)) & 0x000000ff;
	}
}

手动配置输入和预期输出,进行两次sha256操作,并比对其是否与预期结果相符

int sha256_test()
{
	BYTE input[] = {0x00,0x00,0x00,0x20,0xe3,0x02,0x67,0xc7,0x5d,0x2d,0x24,0xb7,0xdf,0xd8,0xb6,0x45,
	                0x9f,0xd8,0x37,0x44,0x79,0xd3,0xeb,0x27,0x8c,0x6a,0x0b,0x00,0x00,0x00,0x00,0x00,
	                0x00,0x00,0x00,0x00,0xf6,0x5c,0x34,0x24,0x2c,0x47,0x50,0x07,0x67,0xb5,0x34,0xc9,
	                0x49,0xc0,0xa3,0x8a,0xf4,0x99,0x07,0xb9,0x4a,0x6e,0x13,0x63,0x21,0x40,0x7c,0xbc,
	                0x19,0xd2,0x7e,0x62,0x87,0x07,0x2e,0x60,0xb9,0x21,0x0d,0x17,0x40,0x00,0x8b,0xf2};
	BYTE expect_result[SHA256_BLOCK_SIZE] = {0x00,0x00,0x01,0xfe,0x42,0x2c,0x0e,0x30,0x40,0xf5,0x6d,0x96,0x99,0xe2,0xfb,0xd6,
                                             0x0f,0xbd,0x0e,0x8e,0x5d,0x64,0xfc,0x22,0x22,0xc7,0x91,0x28,0x68,0xf1,0x7e,0x47};
	BYTE middle_result[SHA256_BLOCK_SIZE];
	BYTE final_result[SHA256_BLOCK_SIZE];
	SHA256_CTX ctx;
	int pass = 1;

    int i;
    sha256_init(&ctx);
	sha256_update(&ctx, input, 80);
	sha256_final(&ctx, middle_result);
	printf("middle hash is: ");
	for(i=0; i<32; i++) printf("%.2x", middle_result[i]);
	printf("n");
	sha256_init(&ctx);
	sha256_update(&ctx, middle_result, 32);
	sha256_final(&ctx, final_result);
	printf("final hash is: ");
	for(i=0; i<32; i++) printf("%.2x", final_result[i]);
	printf("n");
	pass = pass && !memcmp(expect_result, final_result, SHA256_BLOCK_SIZE);

	return(pass);
}

int main()
{
	printf("SHA-256 tests: %sn", sha256_test() ? "SUCCEEDED" : "FAILED");

	return(0);
}

软件代码和SHA256算法介绍中的内容基本一致:

  1. 使用sha256_init()初始化一个哈希
  2. 调用sha256_update()将字符串前部分超过512bit的部分打包成512bit的信息块
  3. 调用sha256_transform()更新八个哈希状态,得到新的哈希值
  4. 对于剩下小于512bit的字符串,调用sha256_final()把它补位成最后一个或者两个信息块,分别调用sha256_transform()更新哈希状态
  5. 得到最终的哈希结果后和预期的结果比较

硬件架构设计

为了让FPGA进行SHA256算法,我们首先要分析这个算法在软件架构和硬件架构的区别,先进行优化设计。FPGA和软件逻辑区别是,硬件逻辑是并行执行的,软件逻辑中调用循环执行的操作,在FPGA中只要资源足够就可以在一个时钟周期内完成,因此时钟能达到多快可以决定其哈希算力大小,我们的优化目标就是尽可能提高时钟频率。

算法流程图优化

哈希算法中的核心是扩展信息块循环和哈希状态循环,循环64次可以得到最终哈希结果。假设整个哈希模块在同一个时钟域,也就是所有逻辑使用同一个时钟频率,可以到达的最高时钟频率是由其中最复杂的逻辑决定的。逻辑复杂度由逻辑级数和布线延迟决定,比如两个32位数的加法比两个16位数的加法复杂,三个32位数的加法比两个32位数加法复杂

我们将扩展信息块循环再看一次:
FPGA应用篇【0】比特币SHA256算法实现——原理分析
其中最复杂的逻辑就是W[j] = Ep1(W[j-2]) + W[j-7] + Ep0(W[j-15]) + W[j-16] ,四个32位数相加,其中两个还要经过Ep0或者Ep1函数处理,我们的处理方法是通过寄存器将大块的逻辑分割成几个相对小的逻辑块。我们优化的原则是,两个相邻寄存器之间只处理一个逻辑函数或者两个32位数的加法。需要注意的是,每次到下一个时钟周期,寄存器中的W[j]就会成为W[j-1],因此要移动取输入数据的位置

修改设计如下:

t=0: tmp1[0]=Ep0(W[j-12]);
t=1: tmp2[1]=tmp1[1]+W[j-14]=Ep0(W[j-13])+W[j-14];
t=2: tmp3[2]=tmp2[2]+W[j-6]=Ep0(W[j-14])+W[j-15]+W[j-6];
     tmp4[2]=Ep1(W[j-1]);
t=3: W[j]=tmp3[3]+tmp4[3]=Ep1(W[j-2])+W[j-7]+Ep0(W[j-15])+W[j-16];

这样就把一个大的计算逻辑分割成了五个相对较小的逻辑,可以大幅度提高性能。修改后的流程图如下
FPGA应用篇【0】比特币SHA256算法实现——原理分析
下面优化八个哈希状态的更新,初始状态机如下:
FPGA应用篇【0】比特币SHA256算法实现——原理分析
比较复杂的两个计算分别是a和e的更新:

e = Sig1(e) + Ch(e,f,g) + W[j] + K[j];
a = Sig0(a) + Maj(a,b,c) + Sig1(e) + Ch(e,f,g) + W[j] + K[j];

这里我们不能再使用前面的扩展信息块相似的移动延迟位置的做法,因为状态机更新中的e的输入就包含了e的输出,没有空间可以操作。因此我们使用另一种思路,使用多通道架构思路来处理。示意图如下:
FPGA应用篇【0】比特币SHA256算法实现——原理分析
从图中可以看到红绿蓝黄四种颜色,代表四个不同的数据通道,每个状态机都由一个寄存器变为四个通道数据的FIFO,这样对于一个数据通道而言,其一个数据与下一个数据之间由一个时钟周期变为四个时钟周期,并且剩下三个时钟周期也没有闲着,用来处理其他三个信道的数据

通过这种设计,让一个时钟处理一个数据的模式变为了四个时钟处理四个数据,虽然看起来没有区别,但由于两个寄存器之间的逻辑简化了,FPGA最终能达到的最高时钟频率变高,也就提高了效率

之所以这里可以这么做,是因为挖矿操作就是不停的尝试新的数据,而不是一般加密文件时只进行一次操作,因此可以并行处理大量数据

为了和状态机更新的架构匹配,我们重新设计上面的扩展信息块循环如下,设计思路一样,就不解释了:
FPGA应用篇【0】比特币SHA256算法实现——原理分析

结论

这一篇中分析了SHA256算法和比特币挖矿算法的关系,给出了C语言的逻辑仿真,并对FPGA实现SHA256算法的核心硬件架构进行了初步的设计,下一篇我们在此基础上写出相应的Verilog代码并进行仿真


程序员灯塔
转载请注明原文链接:FPGA应用篇【0】比特币SHA256算法实现——原理分析
喜欢 (0)