《区块链金融》课件 第3章 数据结构及相关技术

微课视频版区块链金融第3章数据结构及相关技术目录01.区块链与区块02.哈希函数03.Merkle树区块链与区块PART013.1.1区块链第3章数据结构及相关技术1.区块链起点链起点:区块链的根节点，是区块链的第一个区块，称为创世区块（GenesisBlock）。2009年1月3日，比特币的创世区块在芬兰产生，区块高度为0，后续所有区块，都依次顺序地连接到以创世区块为起点的链式结构。创世区块被静态写入比特币客户端软件，每个安装软件的节点都将存有创世区块的创建时间、首次交易内容、块结构及哈希值，所有区块都把创世区块作为起点，构建了一个可信的根节点。3.1.1区块链第3章数据结构及相关技术创世区块产生时间创世区块的币基交易（CoinbaseTransaction）是这样一句话：“TheTimes03/Jan/2009Chancelloronbrinkofsecondbailoutforbanks”。是“中本聪”添加在创世区块币基交易的信息，信息引用自2009年1月3日《泰晤士报》上的一个标题。表明创世区块产生的时间。3.1.1区块链第3章数据结构及相关技术创世区块主要数据：Hash:000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26fVersion：1Size：285Height：0Merkleroot:4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33bDifficulty：1.00nBits：486,604,799Nonce：2,083,236,893Timestamp：2009-01-0318:15:05InputValue：0.00BTCOutputValue：50.00BTCReward：50.00000000BTCNumTransactions：1Nextblockhash：00000000839a8e6886ab5951d76f411475428afc90947ee320161bbf18eb60483.1.1区块链第3章数据结构及相关技术2.单向单链区块链中每个区块的区块头存储前一区块的区块哈希值，通过区块间哈希指针链接形成了链式结构。从创世区块开始，依次顺序连接，形成单向单链，如图3-1所示。图3-1链式结构3.1.1区块链第3章数据结构及相关技术3.链分叉-系统延时产生的分叉网络连接以及传输时延等原因，几个节点“同时”产生新区块，并加以广播，新生成的区块长度相同、区块包含的交易信息相同，但是生成节点不同。一部分节点先收到Blockx区块，另一部分节点可能先收到Blocky区块，如图3-2所示，分叉由此产生。这种分叉是由于生成区块的时延造成的区块链接分叉。图3-2链分叉3.1.1区块链第3章数据结构及相关技术3.链分叉-版本升级产生的分叉系统版本升级时，新旧版本的某些规则不一致，导致整个区块链中升级了系统软件的节点（新节点）与未升级系统软件的节点（旧节点）运行在不同规则下，分叉就此产生。比特币的这种分叉通常分为硬分叉和软分叉。3.1.1区块链第3章数据结构及相关技术（1）硬分叉版本升级后，无法向前兼容，旧节点无法验证新节点产生的区块，产生的分叉称为硬分叉，如图3-3所示。旧节点不会链接新节点生成的区块，新节点也不会链接旧节点生成的区块。新、旧节点在不同的区块链上运行（挖矿、交易、验证等）。图3-3硬分叉结构图3.1.1区块链第3章数据结构及相关技术（2）软分叉版本升级后，向前兼容，旧节点可以兼容新节点产生的区块，产生的分叉称为软分叉，如图3-4所示。软分叉刚开始并不会产生两条区块链，因为新节点生成的区块可以被旧节点链接，但旧节点无法识别新规则的含义。所以新、旧节点仍然处于同一区块链上。图3-4软分叉结构图3.1.1区块链第3章数据结构及相关技术4.链选择链选择机制是为了解决链分叉问题，不同的区块链解决方案不同。比特币采用最长链、6次确认原则。新生成的区块选择最长的链进行链接，哪个分支在分叉节点后先达到6个新区块（称为“6次确认”），就是正确的链，如图3-5所示。图3-5链选择3.1.2区块第3章数据结构及相关技术区块链的基本数据单元是区块（Block）。区块生成就是向数据库或文件系统写入交易信息的过程。比特币的每个区块大小规定不超过1MB。3.1.2区块第3章数据结构及相关技术1.区块基本结构一个完整的区块数据结构如表3-1所示。

表3-1区块结构字段字节/B描述MagicNo4固定值0xd9b4bef9Blocksize4表示该字段之后的区块大小Blockheader80区块头Blockbody不确定区块体MagicNo：

魔数或神奇数，区块与区块之间用“魔数”间隔。固定常数0xf9beb4d9（小端存储0xd9b4bef9）。Blocksize：

区块大小。Blockheader：

区块头。Blockbody：

区块体。3.1.2区块第3章数据结构及相关技术1.区块基本结构区块头（Blockheader）和区块体（Blockbody）是区块的基本结构，如图3-6所示。

图3-6区块基本结构3.1.2区块第3章数据结构及相关技术2.区块体结构区块体存储了规定时间段内的交易信息，包括：交易数据（Transactions）交易数量（numTransactions）交易数量长度（numTransactionsBytes）（1）Transactions字段。大小不确定，存储交易数据（币基交易和普通交易）（2）numTransactions字段。大小为1～9B，区块内的交易数量（币基交易和普通交易）（3）numTransactionsBytes字段。大小为1B，交易数量占用的字节长度3.1.2区块第3章数据结构及相关技术2.区块体结构numTransactions字段采用压缩方式存储，节省存储空间。通过numTransactionsBytes字段可以确定numTransactions在区块体中的存储位置，以便读取交易数量。先读取numTransactionsBytes字段值，根据值的不同做出如下规定。（1）如果numTransactionsBytes<253，则numTransactions=numTransactionsBytes。（2）如果numTransactionsBytes=253，则numTransactions等于numTransactionsBytes字段值之后的2个字节。3.1.2区块第3章数据结构及相关技术2.区块体结构（3）如果numTransactionsBytes=254，则numTransactions等于numTransactionsBytes字段值之后的4个字节。（4）否则，numTransactions等于numTransactionsBytes字段值之后的8个字节。3.1.2区块第3章数据结构及相关技术3.区块头结构区块头共80B，包含6个字段：nVersion：版本号hashPrevBlock：前一区块哈希值hashMerkleRoot：区块体的Merkle根哈希值nTime：区块生成时间（时间戳）nBits：难度值nNonce：随机数目标值、当前区块哈希值并不在区块中存储。注意：

区块头中的6个字段均以小端形式存储，即低有效位在前。3.1.2区块第3章数据结构及相关技术3.区块头结构区块头数据结构如表3-2所示。表表3-2区块头数据结构字段字节/B描述nVersion4当前版本号，用于跟踪软件/协议的更新hashPrevBlock32前一区块哈希值，SHA256(SHA256())hashMerkleRoot32交易信息的Merkle根哈希值，双SHA256计算nTime4区块生成的时间戳nBits4区块工作量证明的难度值nNonce4用于计算工作量证明的随机数3.1.2区块第3章数据结构及相关技术4.区块头字段解析（1）时间戳（nTime）区块生成时间：证明交易时间，形成时序结构，解决重复支付。1970年01月01日格林威治时间00:00:00（北京时间1970年01月01日08:00:00）到现在时间的总秒数（不考虑闰秒）。比特币的时间戳来自前11个区块的中位数时间。中位数时间和本地系统时间相差不超过70分钟。拒绝接受时间戳比本地系统时间快2小时的新区块。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数①目标值（Target）与难度值（nBits）目标值：256位无符号整数，是区块哈希的求解目标。目标值通过压缩变换，以32位的形式存储在难度值字段。难度值是目标值存储在区块头的特殊编码方式，用于区块哈希的计算。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数①目标值（Target）与难度值（nBits）Target压缩变换，以系数/指数的格式存储在nBits字段，占4B空间。压缩规则：nBits字段最高字节表示指数，存储目标值的有效字节数，即把目标值转换成16进制后去除前导0后剩余的字节数，如剩余字节的最高字节值大于0x7f，则是在此最高字节前添加00后的字节个数（即字节数+1）。nBits字段的后3个字节表示系数，存储目标值有效位的最高3个字节。如创世区块的难度值nBits=0x1d00ffff，则0x1d是指数，0x00ffff是系数。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数①目标值与难度值比特币规定，最大目标值为：Difficulty_1_Target=0x00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff（Difficulty_1_Target的值长度共64位，8个0，56个f）。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数②Target压缩成nBits以Difficulty_1_Target为例：有8个前导0，换算成二进制是32位，则剩余二进制位数为256-32=224位，用字节表示为224b/8=28B，即有效字节数为28个字节，因为有效字节的最高字节值0xff>0x7f，根据压缩规则，在有效字节位前添加00，则有效位变为0x00ffff……，剩余字节数为29，转换成十六进制是0x1d，故压缩后的nBits最高字节是0x1d；另3个字节存储的是有效位的最高3个字节，即00ffff，所以经换算后，最大目标值在nBits中存储的值是0x1d00ffff。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数③nBits变换为TargetnBits的第1字节用N1表示指数，后3个字节用N3表示系数，转换规则为：Target=N3*28*（N1-3）在nBits=0x1d00ffff中，1d是指数，00ffff是系数，则Target=0x00ffff*28*(0x1d-0x03)=0x00000000ffff0000000000000000000000000000000000000000000000000000结果是一个接近原值的近似值。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数④难度系数（Difficulty）通过Difficulty动态调节目标值，初始值Difficulty=1。例如：比特币规定10分钟生成一个区块。通过Difficulty动态调节恒定出块速率，Difficulty每两周调整一次。正常情况，每两周产生2*7*24*6=2016个区块，则标准出块时间是20160分钟。新难度系数=当前难度系数*（最近的2016个区块的实际出块时间/20160分钟）比特币挖矿难度的调整是在每一个节点上独立完成的。3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数⑤目标值与难度系数：难度系数=最大目标值与当前目标的比值即：Difficulty=Difficulty_1_Target/Target则：Target=Difficulty_1_Target/Difficulty例如，第100000个区块的难度系数是14484.16236122，则Target=Difficulty_1_Target/Difficulty=0x00000000ffff000000000000……0/14484.16236122=0x00000000004864c0000000000……0注意：目标值与难度系数成反比3.1.2区块第3章数据结构及相关技术4.区块头字段解析（2）目标值、难度值与难度系数⑥难度值、目标值与难度系数的计算关系

首先计算难度系数

再根据难度系数求解目标值

目标值经过压缩变换存储为难度值3.1.2区块第3章数据结构及相关技术4.区块头字段解析（3）随机数（nNonce）作用：在区块头其余5个字段值不变的情况下，改变随机数，以使区块头的哈希值发生变化。区块哈希是对区块头的字段求解而来，也就是区块哈希值由区块头字段确定。要对同一个区块头反复求解哈希值，区块头的字段值必须保持变化，才能每次算出不同的哈希值。随机数nNonce从0开始严格按照线性方式增长，每次计算都会增长。前一区块哈希值、区块体的Merkle根哈希值将在后续章节介绍。3.1.2区块第3章数据结构及相关技术5.区块标识符每个区块有两种标识符：区块哈希和区块高度。区块的主标识符是区块哈希，通过对区块头6个字段进行两次SHA256哈希计算产生的256位的值被称为区块头哈希值，简称为区块哈希。区块哈希可以唯一、确切地标识一个区块，并且任何节点都可以对区块头进行独立计算，获得该区块的哈希值。区块的第2个标识是区块高度，区块高度一般从0开始，之后产生的区块高度+1。区块高度不是唯一标识符，当区块分叉时，两个或多个区块竞争同一高度。3.1.3区块生成第3章数据结构及相关技术区块体中的交易信息被存储到数据库或文件中之前，都是暂存在缓存中的，区块数据被存储到数据库或文件中，就表示区块链系统生成了一个新区块。1.挖矿挖矿是“中本聪”设计的用于维护比特币运行的机制。区块生成通过挖矿实现。挖矿：节点求解一个数学题（求解随机数）的过程。矿工：参与挖矿的节点。3.1.3区块生成第3章数据结构及相关技术1.挖矿以比特币为例，求解的数学题可以表述为：根据当前区块的数据，通过穷举法发现一个随机数（nNonce），使区块头数据的双SHA256哈希值小于或等于目标值，即：SHA256(SHA256(nVersion+hashPrevBlock+hashMerkleRoot+nTime+nBits+nNonce))<=Target挖矿的本质就是发现一个随机数的过程。3.1.3区块生成第3章数据结构及相关技术2.挖矿流程（1）挖矿流程3.1.3区块生成第3章数据结构及相关技术2.挖矿流程（2）节点校验节点校验是挖矿成功的节点将求解的随机数存储至区块，即新区块生成，然后广播至全网，其他节点收到新区块后，校验所求解的随机数是否满足要求的过程。校验挖矿结果比较简单。收到新区块的节点对该区块头进行一次双SHA256哈希运算，并判断运算结果是否小于或等于目标值即可。3.1.3区块生成第3章数据结构及相关技术3.挖矿目的与激励机制（1）挖矿目的。挖矿目的：获得区块记账权。区块链的核心思想是节点获得记账权，所有设计及运算均围绕着这个目标进行。记账权：把暂存在内存中的区块数据、交易信息写入数据库或文件的权利。3.1.3区块生成第3章数据结构及相关技术3.挖矿目的与激励机制（2）激励机制记账权由激励机制驱动，鼓励节点踊跃参与挖矿，共同维护网络成长和运行稳定。比特币的激励机制包括两类。①挖矿奖励：获得比特币，最初是50个比特币，数量每隔4年减半，直至为0。挖矿奖励是比特币发行的唯一方式，当挖矿奖励的比特币数量降至0时，全网的比特币数量将永久维持在一个恒定的水平。②交易手续费：有记账权的节点将获得区块内所有交易的手续费。挖矿奖励为0后，交易手续费将成为比特币激励机制的唯一手段。哈希函数PART023.2.1哈希函数第3章数据结构及相关技术1.函数定义函数是一种映射，在非空数集之间的映射称为函数。假定一个非空数集A，对A施以对应法则f，记作f(A)，得到数集B，如果B=f(A)，则这个关系式称函数关系式，简称函数。哈希函数是一种函数，也称散列函数、单向杂凑函数、数据（消息）摘要函数、数字摘要等。3.2.1哈希函数第3章数据结构及相关技术2.哈希函数的定义哈希函数可以表示为：h=H(M)其中，M是任意长度的消息；H是哈希函数，h是对消息M进行哈希运算得到的结果，也称消息摘要或报文摘要。RSA公司MD系列中的MD2、MD4、MD5美国NIST的SHA、SHA-1，欧盟RIPE项目的RIPEMD、RIPEMD-128、RIPEMD-160。区块链技术常采用的散列函数是SHA256和RIPEMD-160。哈希函数的特性给定M，容易计算出h=H(M)给定h，找到满足H(M)=h的M在计算上不可行给定M，找到M

，满足H(M)=H(M

)在计算上不可行找出两条M和M

，满足H(M)=H(M

)在计算上不可行第3章数据结构及相关技术哈希函数的性质哈希函数不能由输出反向推导出输入。即给定h，无法找到H(M)=h的M。单向性哈希函数具有随机性，任何微小差异的输入都会产生截然不同的输出。如果M1≠M2，则H(M1)≠H(M2)。随机性哈希函数具有定长性，即无论输入多长的数据，输出长度固定。定长性抗碰撞性体现在，一定输入范围内，不同的输入不会产生相同的输出。如果M1≠M2，不会得到H(M1)=H(M2)。抗碰撞性第3章数据结构及相关技术3.2.2SHA函数第3章数据结构及相关技术1.SHA系列安全散列算法（SecureHashAlgorithm，SHA）共有2个系列7个标准，分别是SHA-1、SHA-2，SHA2包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224和SHA-512/256。SHA系列算法由美国NSA设计，美国国家标准与技术研究院（NIST）发布。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理对于任意长度的消息M，SHA256都会产生一个256位的哈希值，称作消息摘要消息摘要长度为32B，通常用64个十六进制字符串表示。下面先介绍SHA256算法的基础，如常量初始化、信息预处理、逻辑运算等概念，然后再介绍SHA256算法的运算过程。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（1）常量初始化SHA256算法用到8个哈希初始值（表3-3）、64个哈希常量（表3-4）初始值是对自然数的前8个质数（2,3,5,7,11,13,17,19）平方根的小数部分取前32位。如2的平方根的小数部分约为0.414213562373095048，而0.414213562373095048

6

16-1+a

16-2+0

16-3+9

16-4+e

16-5+6

16-6+6

16-7+7

16-8质数2平方根的小数部分前32位得到0x6a09e667。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（1）常量初始化表3-3哈希初始值3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（1）常量初始化表3-4哈希常量哈希常量是对自然数中前64个质数：（2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89…）的立方根的小数部分取前32位。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（2）信息预处理在消息后面填充附加位，使整个消息长度是512的整数倍。预处理分两步：填充附加位和附加长度。①填充附加位在消息末尾填充，使消息长度对512取模后余数为448。填充方法：第一位填充1，其余位都填充0，直到长度对512取模后余数是448。消息必须进行填充。原始消息长度对512取模后余数为448，也必须填充附加位。填充的位数应是512位，即填充1个1，511个0。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（2）信息预处理①填充附加位以消息“abc”为例说明填充附加位的过程。a、b、c对应的ASCII码分别是97、98、99，二进制为：011000010110001001100011先在消息末尾填充一个“1”：0110000101100010011000111再继续填充423个“0”：0110000101100010011000111000000000000000…00000000填充后消息如下（用十六进制表示，以大端形式编码）：61626380000000000000000000000000……000000003.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（2）信息预处理②附加长度值。64位二进制表示原始消息长度，添加到后面。上例中，消息“abc”有3个字符、24位，所以长度值为24。在最末尾填充附加长度值后，整个消息为（用十六进制表示）：61626380000000000000000000000000……000000000000000000000018第一步附加位填充至448，第二步再附加64位的长度值，448+64=512原始消息长度加上两次填充，共512位，正好满足512整数倍的要求。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（3）逻辑运算6个逻辑函数进行逻辑位运算，每个函数输入32B，输出32B。

①Ch(x，y，z)=(x

y)

(

x

z)②Ma(x，y，z)=(x

y)

(x

z)

(y

z)③

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)公式中的逻辑运算符3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程①消息分块填充后的消息分成n个512位的消息块M0，M1，M2，…，Mi，…，Mn-1，运算N次迭代，结果就是原始消息M的消息摘要。一个256位的初始值为H0，与第一个消息块M0进行函数运算，得到H1，即完成了第一次迭代；H1与第二个消息块M1进行函数运算得到H2……最后得到Hn就是原始消息M的256位消息摘要。3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程SHA256算法中的最小运算单位称为“字”（Word），一个字是32位二进制，256位二进制可以分成8个“字”，从左至右依次设为a、b、c、d、e、f、g、h。在第一次迭代中，256位的初始值就是表3-3的8个哈希初始值，即3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程a=H0,b=H1,c=H2,d=H3e=H4,f=H5,g=H6,h=H7表3-33.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程迭代第一步，将每个消息块扩展成64个字，扩展方式如下。首先，将消息块Mi分成16个32位的字，记为W[0]，W[1]，…，W[15]，每个字以大端形式编码，即每个字的第一个字节是最高位字节。消息块Mi前16个字直接由消息块分解得到。然后，每个消息块的后48个字由如下迭代公式得到。Wi

1(Wi-2)+Wi-7+

0(Wi-15)+Wi-163.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程第二步，进行64次循环。每次循环更新：a、b、c、d、e、f、g、h运算逻辑如图3-8所示。图3-8循环运算逻辑图3.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程循环运算流程可用如下公式表述。forj=0to63T1

h+

1(e)+Ch(e，f，g)+Kj+Wj（Kj是表3-4中的第j个，Wj是本消息块的第j个字）T2

0(a)+Ma(a，b，c)h

g；g

f；f

e；e

d+T1；d

c；c

b；b

a；a

T1+T23.2.2SHA函数第3章数据结构及相关技术2.SHA256原理（4）SHA256计算过程②迭代过程64次循环结束后，公式如下Hi0=a+H(i-1)0；Hi1=b+H(i-1)1；Hi2=c+H(i-1)2；Hi3=d+H(i-1)3Hi4=e+H(i-1)4；Hi5=f+H(i-1)5；Hi6=g+H(i-1)6；Hi7=h+H(i-1)7第i个消息块的摘要Hi=（Hi0，Hi1，Hi2，Hi3，Hi4，Hi5，Hi6，Hi7）“+”是mod232加法，即两个数相加，对232取余，Hi是消息块Mi的消息摘要。3.2.2SHA函数第3章数据结构及相关技术3.比特币的SHA256应用比特币采用双SHA256哈希运算。比特币的区块哈希值包括前一区块哈希值及当前区块哈希值，两者计算方法相同。区块哈希（hashBlock）由区块头数据经哈希函数运算而得。把区块头的6个字段按顺序连接在一起，组成一个长字符串作为哈希函数的输入，运算结果就是区块哈希。即hashBlock=SHA(SHA256(区块头字符串))=SHA256(SHA256(nVersion+hashPrevBlock+hashMerkleRoot+nTime+nBits+nNonce))3.2.3RIPEMD-160函数第3章数据结构及相关技术RACE原始完整性校验消息摘要，1996年发布。（RACEIntegrityPrimitivesEvaluationMessageDigest，RIPEMD）1.RIPEMD系列1996年发布的是RIPEMD-128版本，性能与SHA-1类似，使用MD4的设计原理。RIPEMD系列函数包括RIPEMD-128、RIPEMD-160、RIPEMD-256、RIPEMD-320四个版本。RIPEMD-160是RIPEMD-128的改进版本，运算结果是160位二进制。RIPEMD-256和RIPEMD-320版本减少了意外碰撞的可能性，但安全性并没有提高。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理RIPEMD-160基于MD4原理设计。运算逻辑与MD相同，分左、右侧通过多轮循环进入不同的运算函数，再与一些既定的常数项运算。16个32位寄存器作为输入缓存（64B）存储需要运算的消息。5个32位寄存器作为输出缓存（20B）存储中间结果及最终哈希值。5个32位寄存器作为左侧运算缓存（20B）存储左侧中间结果及左侧最终哈希值。5个32位寄存器作为右侧运算缓存（20B）存储右侧中间结果及右侧最终哈希值。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（1）常量初始化定义5个输出寄存器初值、常数项K、位移量S、左侧索引项L[i]和右侧索引项R[i]的值。①输出寄存器初值5个32位输出寄存器的初始值如表3-6所示。表3-6输出寄存器初始值3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（1）常量初始化。②常数项K值常数项K的取值如表3-7所示，每轮运算左右侧分别取一个K值，共5轮。表3-7常数项K值3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（1）常量初始化③位移量S左、右两侧运算函数中分别向左移的位移量S取值如表3-8所示。表3-8位移量S3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（1）常量初始化。④左右索引项从W[i]中选择数值，放在左侧区域（Left）和右侧区域（Right）的顺序i值如表3-9所示。表3-9左右侧索引项3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（2）信息预处理①填充附加位在消息末尾进行填充，使消息长度对512取模后的余数为448。填充方法：在第一位填充1，其余位都填充0，直到整个消息长度对512取模后余数是448。②附加长度值用64位表示的原始消息的长度值添加到后面，以大端形式存储。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（2）信息预处理③逻辑运算RIPEMD-160定义了5个逻辑函数F1-F5，输入32位，输出32位。函数如下：F1(H1,H2,H3)=H1

H2

H3F2(H1,H2,H3)=(H1

H2)

(

H1

H3)F3(H1,H2,H3)=(H1

(

H2))

H3F4(H1,H2,H3)=(H1

H3)

(H2

(

H3))F5(H1,H2,H3)=H1

(H2

(

H3))

表3-10逻辑运算符3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程RIPEMD-160算法输出160位。运算过程包括左右两侧，每侧5轮、每轮16次循环共80次。最后，左右两侧的最终运算输出使用模232加法合并生成最终结果。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程①消息分块将填充后的消息分成n个512位的消息块M0、M1、M2、…、Mi、Mn-1，每个512b的消息块Mi被分成16个32位的字，记为W[0]，W[1]，…，W[15]。每个字的最终结果是32位，5个32位哈希值连起来就是160位哈希值。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程②迭代过程左右各进行5轮、每轮16次（共80次）运算。左右两侧采用的逻辑函数F相同，但采用顺序正好相反。左侧逻辑函数的顺序是F1、F2、F3、F4、F5。右侧逻辑函数顺序是F5、F4、F3、F2、F1。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程②迭代过程第一步，将输出寄存器初值H0，H1，…，H4分别复制到左侧运算寄存器和右侧运算寄存器。第二步，由运算函数按图3-9和图3-10所示流程分别进行5轮各16次的迭代位移运算。3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程②迭代过程图3-9左侧函数运算流程图图3-10右侧函数运算流程图3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（3）计算过程②迭代过程round1(j=0:15)，执行：for(intj=0；j<16；j++)//右侧寄存器的运算{tmp=leftrotate((A_r+F5(B_r,C_r,D_r)+W[R[j]]+K1_right),S[j]_right)+E_r；A_r=E_r；E_r=D_r；D_r=leftshift(C_r,10)；C_r=B_r；B_r=tmp；}for(intj=0；j<16；j++)

//左侧寄存器的运算{tmp=leftrotate((A_l+F1(B_l,C_l,D_l)+W[L[j]]+K1_left),S[j]_left)+E_l；A_l=E_l；E_l=D_l；D_l=leftshift(C_l,10)；C_l=B_l；B_l=tmp；}

defineleftshift(x,n)=x<<n//定义左移位函数，对x左移n位defineleftrotate(x,n)=(x<<n)|(x>>(32-n))//定义循环左移n位，3.2.3RIPEMD-160函数第3章数据结构及相关技术2.RIPEMD-160原理（4）输出将左右两侧最终运算结果与原输出寄存器初值进行相加运算即为输出，作为下一个512位分组处理的输出寄存器初始值，运算逻辑如图3-11所示。对所有512位的分组处理完成之后,最终产生的160位输出即为消息摘要。tmp=H[1]+C_l+D_r；H[1]=H[2]+D_l+E_r；H[2]=H[3]+E_l+A_r