区块链学习笔记 | 比特币中用到的密码学原理

喜欢就关注我们吧!

JAVAandPython君

本文来自“小震同学”公众号投稿


区块链这个名词,大家都不陌生,那么区块链的本质究竟是什么?有人说区块链是下一代的价值互联网;也有人说它是世界上最慢的数据库。的确,如果把它当数据库用的话是非常的慢,而且仅仅只能实现数据库中的一小部分功能。

可以说区块链这项技术是饱受争议,有人把它捧上了天,将其与工业革命相提并论,说它是像蒸汽机一样的伟大发明;也有很多贬低区块链的,将它说成是庞氏骗局。但无论是哪种说法,真正懂区块链的人是不多的,很多人其实只是在讨论区块链的商业模式,而且有的商业模式和区块链的本质其实并没有什么关系。

虽然从比特币的价格走势来看,现在似乎已经错过了比特币暴涨的好时候,但实际上,从区块链的整体发展来看,现在还是处于非常早期的阶段,所以从现在开始学习的话,可以说是这个领域的先行者了。而且,区块链不等于比特币,比特币只是基于区块链技术的一种加密货币而已,千万不要被比特币限制了想象力!

学习前提:学习的前提是已经学过基本的数据结构和算法,掌握了基本的编程技能

参考资料

  • BitCoin and Cryptocurrency Technologies
  • 以太坊白皮书、黄皮书、源代码
  • Solidity文档

比特币中用到的密码学原理

比特币被称作是加密货币,但实际上加密货币是不加密的,区块链上所有的交易内容都是公开的,包括账户的地址、转账的金额等等。比特币中主要用到密码学中的两个内容:哈希签名

哈希

密码中的哈希函数被称作:cryptographic hash function,它有两个重要的性质:collision resistance和 hiding 。

collision resistance

其中的collision是指哈希碰撞,什么是哈希碰撞?

若有哈希函数H(),假设两个输入 x , y 且 x 不等于 y ,使得H(x) = H(y),则称为哈希碰撞。

collision resistance 的解释是:Collision resistance is a property of cryptographic hash functions: a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.

it is hard to find 意思是很难找到两个不同的输入使得二者的哈希值相等,也就是说想要人为地制造哈希碰撞是非常难的,但哈希碰撞是客观存在的,例如当我们使用哈希表的时候,不同的输入可能会被映射到哈希表中的同一个位置,因为输入空间大于输出空间。

那么collision resistance这个性质有什么用呢?

它可以用来对一个massage求digest,例如有一个massage m ,取它的哈希值H( m )作为digest 用来检测m是否被篡改,因为当m被篡改时,它所对应的哈希值H(m)就会发生变化,而根据collision resistance性质可以知道,很难找到另一个输入m ' 使得H( m ' ) =H( m ),因此想要篡改内容而不被检测出来几乎是不可能的。

举个例子:你想要把一个文件存到云存储服务上,当你某一天要用需要下载回来的时候,如何确定下载的文件就是当初保存的那份文件呢?这时就可以用到哈希函数的collision resistance性质,在上传的时候用文件的内容作为输入算一个哈希值出来,保存到本地,将来取文件的时候再算一个哈希值出来,与原先本地的哈希值进行比较,如果一致则说明文件没有被篡改。

但需要注意的是,哈希函数的 collision resistance 这一性质从理论上是无法证明出来的,它是由实践经验得出的,而有的哈希函数则可以人为地制造哈希碰撞,很著名的一个例子就是MD5,它之前是一个很流行的哈希函数,当初人们认为它很安全,但是现在已经能够人为地制造哈希碰撞了。

hiding

这一性质是指哈希函数的计算过程是单向的、不可逆的。

意思是给定一个输入 x ,可以算出它的哈希值H(x),但无法根据哈希值H(x)反推出原来的输入x ,也就是说,哈希值H(x)没有泄露有关输入 x 的任何信息。

但是仔细一想,真的就没有办法通过H(x)反推出 x 吗?其实是可以通过蛮力求解的方法得出输入 x 的,只要把输入所有可能的取值遍历一遍,将每一个取值的结果与目标H(x)作比较,直到找到相同的结果就可以知道对应的输入了。

因此,hiding这一性质成立的前提是输入空间要足够的大,使得上述这种蛮力求解的方式行不通,而且输入的分布要比较均匀,各种取值的可能性是差不多的。这一点很好理解,因为即使输入空间足够大,但是如果常用的输入都比较集中在某一些值,那么也是可以通过蛮力破解的。

hiding这一性质有什么用呢?

hiding可以和collision resistance 这一性质结合在一起用来实现 digital commitment,有时候也把它称作 digital equivalent of a sealed envelope,直译过来可以理解为 数字加密信封。

举个例子来说明下sealed envelope(加密信封)在现实生活中的意义:比方说有一个人,他想要预测第二天的股票是否会涨,那么如何来证明他的预测是否是准确的呢?

一种方法是,他提前一天对外公布第二天的某某股票会涨,等到第二天的结果出来后再判断他的预言是否准确,那么这种方法是否存在问题呢?如果这个人是股票界的权威人士,那么他的预测势必会直接影响到第二天股票是否会涨,可能使得原本不会涨的股票反倒涨了。

这说明预测结果不能公开,那如果预测结果不公开,等到第二天结果出来后再公开,那又如何保证预测的结果是否被篡改过呢?这就需要用到sealed envelope,将预测结果写下来,放入一个信封,把信封交由第三方公证机构保管,等到第二天结果出来后再验证预测是否准确。这就是现实生活中sealed envelope的用处。

那在电子世界中,如何实现一个digital sealed envelope呢?

将预测结果作为输入 x 算出一个哈希值,将这个哈希值公布出去,由于hiding这个性质,只知道公布的哈希值是无法反推出输入,也就是预测结果;而又由于collision resistance性质,使得输入无法被篡改,因为输入一旦篡改,得出的哈希值就会和当初公布的不一样。这就起到了digital sealed envelope的功能。

但在实际操作中有一些细节需要注意,因为hiding性质的前提是输入空间要足够大,分布要比较均匀,而在上述股票预测的例子中,它的输入空间却不是足够大,因为股票的支数是有限的。常用的解决方法是:在输入后面拼接一个随机数作为整体取哈希,来保证拼接之后的输入足够随机,分布足够均匀。

puzzle friendly

在比特币中,除了用到上述两个性质之外,还要求第三个性质:puzzle friendly

它的意思是,哈希值的计算事先是不可预测的。光看输入很难猜出最后的输出是什么,所以当想要算出来的哈希值是落在某个范围之内(target space),那就只能一个一个地算,没有其他的捷径。例如:想要得到一个256位哈希值,前面k位都是0,什么样的输入能算出这样的哈希值?唯一的办法就是一个一个试,直到试出某个输入符合要求。

后面讲到的比特币挖矿的过程就是基于这样的一个原理。挖矿实际上就是找一个随机数nonce,它和区块块头(block header)中的信息合在一起作为输入取哈希,使得得出的哈希满足某一个条件。由于只能一个一个随机数去试,因此挖矿的过程才能用来作为工作量证明(proof of work)。

虽然挖矿的过程需要很大的工作量才能找到符合条件的nonce,但是一旦有一个人找到了这个nonce,将它公布出去后,其他人要验证它是否符合要求很容易的,只需要进行一次哈希运算就可以了,这一性质叫做difficult to solve,but easy to verify 。

比特币中用的哈希函数叫SHA-256,上述的三个性质它都满足。

签名

介绍签名之前需要先了解一下比特币系统中的账户管理,在日常生活中,如果想要开一个账户,我们需要带上证件去银行办理开户手续,这就是中心化系统的账户管理方式。而比特币是去中心化的,没有类似于银行这样的机构。那如何进行账户管理呢?

每一个用户自己决定是否开户,不需要任何人批准,开户的过程很简单,就是在本地创立一个公钥和私钥的对:(public key , private key ),这个公私钥对就代表了一个账户,公钥是公开的,私钥是只有自己知道的。公私钥这个概念来源于非对称加密体系(asymmetric encryption algorithm)

在说非对称加密之前先来将一下对称加密(symmetric encryption algorithm),比如:小A要将信息传给小B,但是通讯的网络是有可能被窃听的,为了解决这一问题,小A和小B事先商量好一个秘钥encryption key,小A用秘钥将信息加密传给小B,小B收到信息后再用这个秘钥进行解密,因为加密解密用的是同一个秘钥,所以称为对称加密。但是这样做的前提是小A小B之间要有足够安全的通信渠道,来保证秘钥的传输,显然这是对称加密的一个不足之处。

为了解决这个问题,非对称加密就被提了出来:用公钥加密,用私钥解密。这时候,小A传信息给小B时,需要用小B的公钥对信息进行加密,小B收到信息后用自己的私钥进行解密。也就是加密和解密用的都是接收方的公钥和私钥。由于公钥是公开的,发信息时只需要知道对方的公钥,而私钥不需要彼此透明,因为它是用来解密的。因此这就解决了对称加密中秘钥分发存在的安全问题。

在比特币系统中,创立账号只需要一对公私钥,公钥可以理解为银行账户,而私钥则是账户的密码,密码是只有你自己知道的,别人给你转账时只需要知道你的公钥。

假设这样一个场景:某一天,小A转了10个比特币给小B,然后广播到区块链上,那其他人怎么知道这笔交易确实是小A操作的呢,会不会是有其他人冒名顶替?这时候就需要用到公私钥了,为了解决这个问题,小A需要在发布交易的时候用自己的私钥对这笔交易进行签名,其他人收到交易的信息之后用小A的公钥验证这笔交易签名的正确性,来确定这笔交易就是小A操作的。

看到这里,有人可能就会有疑问了,既然每个人都能生成自己的公私钥对,那会不会出现两个人生成的公私钥对恰好相同呢?实际上,这种可能性是微乎其微的,即使你有一台超级计算机,每天啥事不干,就去产生公私钥对,也几乎不可能产生同样的公私钥对。这里需要强调的是,产生公私钥的时候需要有一个好的随机源(a good source of randomness),如果随机源不好的话,就有可能出现两个人生成的公私钥对相同的情况。比特币中用到的签名算法,不光是生成公私钥的时候要有好的随机源,之后的每一次签名也要有好的随机源,否则就有可能泄露私钥。

比特币系统当中,哈希和签名是结合起来用的,一般是对一个massage取哈希,再对这个哈希值签名。

原文发布于微信公众号 - JAVAandPython君(JAVAandPythonJun)

原文发表时间:2019-08-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券