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

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取哈希，再对这个哈希值签名。