区块链学习(一)——区块链中的密码学,Hash与签名

Posted by Lain on 11-10,2019

0

最近有个想实现的东西,因此一直在学习多线程,分布式相关的知识,由于想做成去中心化的,所以还是要学习一下区块链,于是空闲时间学习了北大的区块链公开课。本系列文章作为笔记使用。这节只是一些概念介绍,都是比较常识化的内容,本来不打算记的,但是老师又讲的比较精彩,因此还是记一下吧(

比特币被称为加密货币,但实际上它并不是加密的,比特币上所有的信息都是公开的,每个区块,每个区块上记录的转账信息等等,实际上都是可以直接看到的。
比特币主要是运用了密码学中的两个功能,一个是HASH函数 一个是 签名

HASH函数

HASH很常见,比如我们下载的时候,下载提供方往往会提供一个HASH值给你,用于校验文件是否被篡改。
比特币中用到了HASH函数的两个特性:HASH碰撞抗性(Collision Resistance)和 单向不可逆性(Hiding)

HASH碰撞抗性

HASH碰撞抗性指的是,对于X≠Y,很难找到这么一对值,使得Hash(X) = Hash(Y)。当出现Hash(X) = Hash(Y)的时候,我们把这种现象叫做Hash碰撞。Hash碰撞是客观存在,且无法避免的。假设我们通过Hash函数H(X)计算出一个256位的hash值,对于hash值的可能性,只有2256个,然而对于输入值X,是有无数个可能值的,因此对于同一个Hash值,出现不同的两个X是必然的,无法避免。我们所说的Hash碰撞抗性,是指的是没有一种快速有效的方式,来为一个Hash值找到另一个不同的输入值X,只能通过暴力枚举,然而这个计算量极其之大,不能构成有效的攻击手段。

要注意一点的是,没有哪个Hash函数,是能被证明是具有Hash碰撞抗性的,只能通过实际经验来判断,全世界这么多密码学专家,长期以来一直没有找到某个hash函数的人为制造Hash碰撞的方法,那我们就认为它是具有Hash碰撞抗性的。有些我们以前认为是具有Hash碰撞抗性的Hash函数,比如著名的MD5,之后也被证实为无法防止Hash碰撞,因此不适用于安全性认证等用途。

单向不可逆性

Hash函数作为一种信息摘要函数,它具有算法不可逆性,也就是说我们无法通过一个Hash值,推导出它的输入值。当然也不是没有办法,我们把它可能的输入值全部输入一遍,然后拿输入结果来和Hash值进行比较,如果两者一样,我们就能获得原来的一种可能的输入值。因此Hash函数的单向不可逆性成立的前提,就是输入值的区间要尽可能的大,而且分布均匀,如果可能的输入值就只取几个,那么要想暴力枚举就很轻而易举了。

利用Hash函数上面的两个特性,我们能做到什么呢?
我们可以用来做数字承诺(Digital Commitment)

什么是数字承诺?

数字承诺(Digital Commitment)有个通俗点的叫法叫做Digital Equivalent Of A Sealed Envolope,也就是说,对于一个被密封在信封里的东西,我们在封入信封前,对其计算出一个电子凭证,该凭证保证了信封里的东西再次被取出的时候,只要再次计算出的电子凭证和原来的电子凭证相等,则可以证明这个东西没有被人篡改过,而且这个电子凭证,无法透露出信封内东西的内容。

这样说可能有点绕,举个实际的例子。我们常常说“事后诸葛亮”,但是诸葛亮也没办法,因为如果他要预测一件事情,在事情发生之前就将其公布的话,是会对事件本身有影响的,比如诸葛亮他预测了明天的战局,魏军如此如此,必败,被司马懿知道了,他就故意反着来,针对诸葛亮的预测排兵布阵,结果打赢了,这样预测结果就不对了,因此不能让预测的内容被别人知道。但是你不公布,谁又相信你预测对了呢?这不就成事后诸葛亮了吗?

数字承诺就能做到这一点,利用Hash的HASH碰撞抗性,我们可以得到预测内容的信息摘要,他保证了内部的信息没有被篡改,且可以将这个摘要公之于众,声明自己做出了预测,然而由于单向不可逆性的存在,公众又无法通过摘要去获取预测的内容,只要在预测中的事情发生了之后,再公布预测内容,并且和信息摘要比对,就可以证明你确实做了预测,而且预测是真实有效的。

除了密码学上的这两个性质之外,用于比特币上的Hash函数还要求有一个性质,叫做Puzzle Friendly(不知道该怎么翻译)。

什么叫做Puzzle Friendly呢?

我们知道,Hash值是不可预测的,如果我们有这么一个要求,我们要求计算出来的Hash值,都落在某个范围内,如下图所示:
1
我们要求其前K位必须都是0,总长256位。要得到这样一个Hash值,我们只能不停的去尝试所有可能的输入值,要经过大量的计算工作。
这个特性有什么用呢?我们都听说过挖矿,实际上挖矿就是在找这么一个nonce(随机值),这个nonce和区块的块头里的其他信息合在一起作为输入计算hash,这个hash值小于等于一个目标值。
也就是:H(Block Header) ≤target

Puzzle Friendly指的就是这个挖矿的过程,没有捷径,只能通过一次次的试nonce这么个随机值,才能找到符合要求的解,所以这个过程才可以被用来作为工作量证明(Proof Of Work),因为没有捷径。

虽然挖矿的过程需要大量的工作量,但是一旦有人找到了这个值,并且将它发布出去,其他人要验证这个nonce的合法性也很容易,因为只要对区块头做一次Hash,判断输出值是不是符合要求就行了。挖矿很难,验证很容易,这种特性我们称之为Difficult to solve,but easy to verify(解决很难,但验证简单)

比特币中使用的Hash算法是SHA-256(Secure Hash Algorithm),这个算法就符合上述的三个条件。

签名

说到签名,我们来插播一个场景。在传统的银行中,我们想要开一个账户,需要银行的审核与批准。在去中心化的比特币中,我们要开一个账户,不需要任何人批准,而是使用一个本地创建的公私钥对。
公私钥对这个概念来自于密码学里的非对称加密。关于非对称加密,我觉得没必要在这里赘述,平常非常常见的,比如SSL。总的来说就是一句话,使用公钥加密,使用私钥解密。公钥可以告诉任何想和你进行通讯的人,在发送信息给你的时候使用你的公钥进行加密,然后你再用自己的私钥进行解密,这样解决了传统对称加密中,密钥分发困难的问题。
在比特币中,用户的账号密码就是一个公私钥对,公钥相当于你的账户,私钥相当于密码,别人想向你转账,只需要知道你的公钥值,如果你想从区块链中转走自己的比特币,这就需要用到自己的私钥。

那么问题来了,前面说到,比特币是不加密的,所有信息都是公开透明的,那么这个公私钥对有什么用处呢?
答案当然是用来签名。假设我发起了一笔交易,区块链怎么知道这个交易是我本人发起的呢?会不会是别人冒名顶替我的?这就需要我在发布这个交易的时候,使用自己的私钥,对这个交易进行签名,别人使用我的公钥来验证这个签名(ECDSA算法)。如果别人要冒充我,假设私钥是256位的hash值,那他就得不停的生成公私钥对,来计算出我和我公钥相等的私钥,从概率学上来讲,这是目前不可能完成的事。

注意,生成公私钥以及签名的时候,都需要有一个好的随机源,否则很容易造成私钥泄漏,导致上面的所有分析都不成立。

比特币中一般是对一个message取一个hash,然后对hash值进行签名。