比特大陆蚂蚁矿机S7

比特币与密码学之哈希函数

沣述 发布在 比特币 27 9173

什么是哈希函数

Hash Function,音译为哈希函数,也称为散列函数或杂凑函数。哈希函数是一个公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值、杂凑值或者消息摘要。哈希函数满足以下三个性质:

  1. 消息M的任何改变都会导致哈希值H(M)发生改变;
  2. 在给定某个哈希函数H和哈希值H(M)的情况下,得出M在计算上是不可行的;
  3. 无碰撞性。即对于消息M1和哈希值H(M1),找到M2使得H(M2)= H(M1) 在计算上不可行(弱碰撞);或者,找到任意两个M1和M2使得H(M1)= H(M2) 在计算上不可行(强碰撞)。

所谓的“在计算上不可行”依据计算复杂度理论的说法,是指对于该运算不存在一个多项式时间算法,例如大数分解和离散对数问题。上述计算不可行是哈希函数安全性的基础,但是需要强调的是,常见的包括MD5和SHA系列在内的哈希函数的安全性是无法证明的,可证明安全哈希函数是另外一个概念。如果把一段消息比作一个人,这段消息的哈希值就是这个人的指纹,是这个人的独一无二的特征。

目前大多数哈希函数是基于异或和求模运算的多轮迭代结构,其输出也就是哈希值具有近似的伪随机特性。伪随机序列是由规则方法产生,其伪随机特性表现在统计特性和相关特性上。二元伪随机序列的统计特性包括:0和1出现的次数相差1次(元素分布),把n个元素连续出现叫做一个长度为n的元素游程,则序列中长度为n的元素游程比长度为n+1的元素游程多一倍(游程分布);伪随机序列的相关特性包括:自相关函数值为0,互相关函数值的绝对值接近Welch下限(Welch bounds)。简单来讲,哈希值虽然并不完全满足上述伪随机定义,但其中的单个及多个元素出现的次数近似相等。例如:

  • SHA256(“The quick brown fox jumps over the lazy dog”)
  • 0x d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
  • 1101011110101000111110111011001100000111110101111000000010010100011010011100101010011010101111001011000000001000001011100100111110001101010101100101000111100100011011010011110011011011011101100010110100000010110100001011111100110111110010011110010110010010

其中有125个0,131个1,长度6的游程000000和111111分别有3个和1个,长度5的游程00000和11111分别有8个和6个,等等。

SHA256的输入为长度小于2^64比特的任意消息(必须是或者扩展成为512比特的倍数),输出长度为256比特的哈希值,使用异或等逻辑运算,以及平移、循环等置换方法,共经过64次迭代。理论上对于SHA256的攻击尝试从低迭代次数进行,例如对52次迭代SHA256的原相攻击和对46次迭代SHA256的碰撞攻击。关于SHA256算法的细节参见这里这里

哈希函数与工作量证明

在比特币协议中引入哈希函数,更重要的作用是解决双重花费的问题。一段比特币交易代码中的输入部分,代表了该交易的提出者对相应数额比特币的所有权,输出部分的代码代表指向接收者的比特币发送行为,这里暂且忽略比特币交易的找零机制。当巴比特大熊把自己的比特币发送给宋欢平时,在该交易完成之前,他又试图把同一段输入再发送给大猫,这时我们就面临如何避免让大熊把一份钱当两份花的问题,即双重花费问题。

在比特币协议中,网络节点检验大熊的交易是否正常的前提是,必须首先解决一个数学问题。这就是著名的工作量证明机制,以解决交易区块所携带的数学问题为基础,实现以问题的解换取检验交易的话语权,有效避免了僵尸节点对不合格交易的随意确认。当然,避免双重花费需要大量节点对该区块的检验结果达成共识,区块检验合格,那么区块包含的交易验证签名后也会通过,最终实现全网大账本的统一更新(更多解释请搜索区块链的确认和51%攻击)。由于大熊的交易的非法性,基于工作量证明机制的原理,找到足够多的网络节点使得这个不合格交易蒙混过关就变得极其困难。

工作量证明中的数学问题具体是什么呢?将网络中的一系列交易和大熊的交易一起打包成一个区块,区块自身有一个标记L(block_header),设x是一个32比特的随机数字,这个数学问题就是寻找x,使得Hash(L,x)的输出满足一定的要求,例如Hash(L,x)小于等于某个设定的门限值Target,Target代表问题难度,等价于所谓的Blocks Difficulty,类似于SHA256的输出,是一个256比特长的0/1序列,等价于一个十进制数字,当前值为11756551917,比特币协议会根据网络算力的发展调整Target的大小,以保证区块确认的速度适中。哈希函数的三个性质和哈希值的伪随机特性决定了,寻找x是一个没有确定算法只能穷举的问题。

  • Hash(L,x)=SHA256(SHA256(block_header, nonce_x))
  • block_header=version+Merkel+nbits+ntime+pre_hash

Version是当前区块的版本号,该区块所包含的多个交易的Hash值构成区块的Merkel数据结构,nbits是当前比特币协议设定的计算复杂度,ntime是区块的时间戳,pre_hash是时间上距离当前最近的一个区块的Hash值,这在《解密比特币》书中也有提及。比特币相关文章中所说的Hash通常就是指Hash(L,x),但实际上Hash(L,x)是两次SHA256运算,需要能够区分这一点。挖矿即是指某个节点第一时间寻找到满足条件的随机数x后,成功获得了该区块内的第一笔名为coinbase交易中的比特币作为奖励,“挖到矿产”,也就是所说的比特币的生产或者发行。同上一段,比特币协议会每2016个区块调整一次Target的大小,控制比特币的发行速度,这样就可以实现将2100万枚比特币的发行持续到2140年的设计方案。

假设网络中的一个节点将最新收到的交易加入自己创建的新的区块中(从BlockChain可以看到,每一个成功确认的区块所包含的交易的数量是不相同的),如果该节点的挖矿程序对该区块进行大量计算后未得到满足要求的随机数x,程序会通知节点重新创建区块,这时节点会选择更新上面的区块中的交易以及时间戳,再次交给挖矿程序进行随机数x的计算。又或者,挖矿程序尚在运算过程中时,获知一个新的区块已经被其他节点完成了数学问题的计算,区块得到了确认,那么它也必须立即停止,更新自己手中的区块包含的上一区块的Hash值pre_hash,重新构建新的区块,重新开始寻找x的计算。上述两种情况均描述了一次挖矿失败,

全网算力

比特币全网算力以Hash/s为单位计算,是指比特币网络所有节点每秒钟共进行了多少次Hash运算,一次Hash(L,x)运算包括两次SHA256,所以1Hash/s相当于一秒钟进行了2次SHA256运算。有许多网站提供当前算力,例如http://bitcoin.sipa.be 。由BlockChain提供的数据显示当前算力已经接近10^5THash/s=100PHash/s,1T=10^12。据观察,各家估算结果的差异在1000 THash/s量级。在bitcoinchartsbitcoinwatch可以查看当前比特币网络的算力分布,不同的矿池各有特点,高Hashingrate矿池和低Hashingrate矿池的区别在于,在第二类矿池中挖矿时确认区块的速度慢,经常争不过前者,但是一旦完成区块确认则所获得的奖励比例会更大,参与两者挖矿的收益不分伯仲。

我们知道SHA256的输出是256个比特,那么所有的输出就有2^256种可能,于是,(2^256/Target)是一个区块得到确认(寻找到正确解)平均需要的Hash次数,由于寻找过程具有随机性,区块的出块速度可慢可快。根据相邻两个区块的时间戳,短则几分钟,慢的话有超过20分钟的。所以根据区块之间的时间差,以及当前比特币协议设定的难度,就可以估算出对应当前区块的算力。在设定的难度不变的时期内,根据最新的一批区块的生成时间,可以在统计意义上计算出当前时间段内的算力大小。

但是,这样对算力的解释仍然不够准确,比特币的代码显示,扩展后的block_header是128个字节,分成长度相等的两段进行SHA256运算,第二段的SHA256运算的前3次迭代不包括随机数x,最后2次迭代不影响最终Hash值的前面几位,于是这5次迭代运算对于寻找x是一种类似预处理的作用,在测试不同的x的计算过程中是相同的。所以Hash/s以SHA256的迭代次数为衡量标准更加可靠。

BTC: 19fZ5WVfhrDToC3ioMFY71D1ARXsQJu8MK

版权声明: by nc" sa 作者保留权利。文章为作者独立观点,不代表巴比特立场。

评论:27

您需要登录后才可以回复 登录|注册
    Author Image
    巴比特资讯 898 天前

    ea9723e42a2708e1de58bb503350c3233d7fdfc15f5fa4bf007033f7a9d4c000

    +1
    +1
    我要点评
    Author Image
    癫痫小蒙牛 912 天前

    敬礼!

    +1
    +1
    我要点评

    有高人当面指教,求之不得[赞][赞][赞]

    +1
    +1
    我要点评

    有高人当面指教,求之不得

    +1
    +1
    我要点评
    拉嘎唛
    拉嘎唛 913 天前

    完蛋了,昨晚上梦见个男的,想了一早上@短路的二极管Mumu http://t.cn/z8AIeLw

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@沣述:[爱你]有机会能向您当面请教最好了。

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@沣述:有机会能向您当面请教最好了。

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    我再修改一下 @那年的三月173151686

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    [吃惊][吃惊][吃惊] 不能一点点基础都没有寄希望于一篇文章打通任督二脉吧

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    不能一点点基础都没有寄希望于一篇文章打通任督二脉吧

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    [汗][汗][挖鼻屎]//@那年的三月173151686:写的太好了,完全看懂里面的每个字,然后到底说啥?

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@那年的三月173151686:[汗][汗][挖鼻屎]

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@那年的三月173151686:

    +1
    +1
    我要点评

    写的太好了,完全看懂里面的每个字,然后到底说啥?

    +1
    +1
    我要点评

    //@疯狂-BTC: 转发微博

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@沣述:[哈哈]你研究的真专业!真要花点功夫,才能真看懂。。。

    +1
    +1
    我要点评
    bitPaul
    bitPaul 913 天前

    回复@沣述:你研究的真专业!真要花点功夫,才能真看懂。。。

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    忘记@你了[嘻嘻]

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    忘记@你了

    +1
    +1
    我要点评
    Author Image
    bitPaul 913 天前

    十分敬佩沣述 ,能把这些严谨、枯燥的数学知识,给我们娓娓道来。花点时间来理解一下,增一下见识。

    +1
    +1
    我要点评
      Author Image
      沣述 913 天前

      多提意见大猫

      +1
      +1
      我要点评
        Author Image
        薄荷凉幼 912 天前

        谢谢沣述!!!我竟然看的有些懂了~~多学习几次就好~~

        +1
        +1
        我要点评
        Author Image
        bitPaul 912 天前

        ……….可以啊,等我看明白、融会贯通后,再来提意见吧。。。说实话,我目前对算法的理解,处于门外汉和入门的级别。

        +1
        +1
        我要点评
    bitPaul
    bitPaul 913 天前

    [挖鼻屎]哈希数学!谢谢分享!

    +1
    +1
    我要点评
    巴比特资讯
    巴比特资讯 913 天前

    《比特币与密码学之哈希函数》http://t.cn/RvJrn9P http://t.cn/RvJrn9P 哈希函数,也称为散列函数或杂凑函数。可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值、杂凑值或者消息摘要。在比特币协议中引入哈希函数,更重要的作用是解决双重花费的问题。@沣述

    +1
    +1
    我要点评
    大学兄弟投资
    大学兄弟投资 913 天前

    //@比特币导航BitTOP100:转发微博

    +1
    +1
    我要点评
    沣述
    沣述 913 天前

    系列文章第三篇:《比特币与密码学之哈希函数》,http://t.cn/RvJrn9P @巴比特资讯 @魔力大熊

    +1
    +1
    我要点评