比特币中的密码学原理 - 知乎
本文约 3000 字，预计阅读 10 分钟。
人们通常把比特币称为加密货币（crypto-currency）。但其实加密货币是不加密的，因为比特币 “账本” 上记录的所有信息，包括交易账户的地址、转账的金额等，都是公开的。
既然如此，为什么要称它为加密货币呢？
在回答这个问题之前，我们先来学习密码学的两个技术：哈希、签名。
哈希
简单来说，哈希就是把任意长度的输入值，通过散列算法（哈希函数）计算出固定长度的哈希值。假设哈希函数为 H，输入值为 m，哈希值为 Digest，即： 。
哈希常被应用于存储和查找，我们对要存储的信息做一次哈希，然后将哈希值作为存储地址。这样以后要查找这条信息的时候，只要再算一次哈希，就能快速查找到它的存储地址。
两个性质
比特币和哈希有什么关系？
首先我们要了解哈希函数的两个性质：
- Collision Resistance
- Hiding
Collision Resistance
即：哈希很难碰撞。
现有哈希函数 H，如果存在 x ≠ y ，使得 H(x) = H(y) ，这就叫哈希碰撞。
为什么会发生哈希碰撞？
前面提到，哈希是把任意长度的输入值，通过哈希函数计算出固定长度的哈希值。
比方说，我们生成的哈希值是 256 位，那么：
- 输入空间却是无限大的（任意长度）
所以理论上，因为输入空间大于输出空间，所以肯定是存在哈希碰撞的。
发生碰撞的概率有多大？
设 d 是输出空间，n 是碰撞次数，那么不碰撞的概率为：
\begin{align} R(d,n) &= 1\cdot\frac{d-1}{d}\cdot\frac{d-2}{d}\cdot(\cdot\cdot\cdot)\cdot\frac{d-(n-1)}{d} \\ &= 1\cdot(1-\frac{1}{d})\cdot(1-\frac{2}{d})\cdot(\cdot\cdot\cdot)\cdot(1-\frac{n+1}{d}) \\ \end{align}
根据泰勒公式：
e^x = \sum_{k=0}^\infty \frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdot\cdot\cdot
当 x \rightarrow 0 时， e^x \approx 1 + x ，所以：
R(d,n) = 1 \cdot e^{-\frac{1}{d}} \cdot e^{-\frac{2}{d}} \cdot(\cdot\cdot\cdot)\cdot e^{-\frac{n-1}{d}} = e^{-\frac{n(n-1)}{2d}}
所以，碰撞的概率为：
P(d,n) = 1-R(d,n) = 1-e^{-\frac{n(n-1)}{2d}}
如果我们的输出空间 d=2^{256} ，碰撞次数 n=2^{100} ，计算得到碰撞概率依然是 P\to0 。
所以，哈希碰撞的概率非常非常小。
然而，目前人们寻找哈希碰撞的方法还是 brute force（暴力求解）。
但这工作量非常大，在现实中是不可行的。
注：有一些哈希函数已经被破解了，比如 md5。
在比特币中的作用
区块链的每个区块，都记录着上一个区块信息的哈希值。
因为哈希碰撞的概率非常小，也就是如果某个区块上的信息发生了变化，那么计算出的哈希值肯定也会变。所以，如果区块被篡改，下个区块的信息也会变，下下个区块的信息也会变，环环相扣。
牵一发而动全身，这可不行。这就保证了区块链的 “不可篡改”。
其它应用场景
现在有一个需求：
往服务器存文件，很久之后再下载回来，怎么保证服务器上的文件不会被人篡改？
很简单。
我们只要把文件内容的哈希值存在本地，毕竟哈希值只是一个字符串，占不了多少空间。然后下载文件的时候，重新计算哈希值，并与本地的哈希值进行对比，如果相同，就代表没有被篡改。
Hiding
即：哈希具有隐匿性。
哈希过程不可逆
我们有一个输入值 m，就可以快速通过哈希函数求得哈希值。但是我们如果只知道哈希值，是无法倒推 m 的，这就是哈希过程的不可逆性。
换句话说，哈希值不会泄露输入值，这保证了安全性。上面说过，我们只能通过暴力求解，遍历所有的输入，直到找到相同的哈希值，才能找到这个输入值，成本非常高。
两个应用
基于以上 2 个性质（碰撞难、不可逆），再来介绍 2 个应用：
- Digital Commitment
- Puzzle Friendly
Digital Commitment
即：数字承诺。这是什么呢？
有个大神，说自己可以预测股市，怎么证明他的预测是否准确呢？
一种方法是，让他提前一天公布预测结果，等到第二天看看就能验证了。但这有一个问题：因为他是大神，所以如果提前公开，必然会影响市场情绪。也就是说，预测结果不能提前公开。
如果要他提前预测，却不能提前公开，那怎么才能保证这个预测一直没有被篡改呢？于是我们就让大神把预测提前写在一个信封里，放到公证机构，等到第二天再打开看结果。
但其实在密码学中，这就是一次哈希。我们可以把大神的预测算出哈希值（写入信封），然后公开这个哈希值（放到公正机构）。这时候，大家并不能通过哈希值来倒推大神的预测（不可逆），第二天等股市收盘后大神再公开自己的预测，只要这个预测的哈希值和之前公开的哈希值相等，就能保证没被篡改过。
加一个随机数
但是，股票的数量一共就几千只，哈希函数的输入空间很小，人们很容易通过暴力求解出大神的预测，这就相当于 “信封” 可能会被人偷看。针对这个问题，常用的方法是在预测内容（输入值）的后面拼接一个随机数（nonce），即 Digest=H(m|nonce) 。
这样一来，第二天大神只要公布预测结果和随机数，大家就可以进行验证了。
Puzzle Friendly
还可以玩猜谜游戏（puzzle）。
游戏规则
我们已经知道，通过哈希值去求解输入值，只能暴力碰撞，这是非常困难的。那我们不妨就降低一点难度，只要哈希值落在某个范围之内就行了，这样难度总小一些了吧？
比如说，如果哈希值的前 k 位都是 0，就算满足要求。我们称这个 k 为游戏难度，假设难度是 k=6，那么谁先找到一个输入值 m，使得 H(m) = 000000... （开头至少 6 个零），就胜出。
什么样的输入值可以算出这样的哈希值呢？没有捷径，只能大量地去试。
Proof of Work
实际上，这个游戏在比特币中，就是大名鼎鼎的——挖矿！
比特币区块链的每个区块头（header）除了包含一些区块信息，还包含一个随机数（nonce），这个 nonce 就是挖矿的人们通过 “游戏竞赛” 的方式得出的。
谁先找到一个 nonce，然后把这个 nonce 和 header 里的其它信息拼在一起作为输入值做一次哈希，如果哈希值满足条件，就胜出（获得打包区块的权力），并可以把自己辛苦算出来的 nonce 写入区块头。
只要有人找到这个 nonce 并发布出去，其他人验证是很简单的，只需要计算哈希值是否满足条件就行了，因为进行一次哈希运算是非常快的，即 difficult to solve，but easy to verify。
所以挖矿就是不停地去试随机数，直到找到满足条件的为止。一般来说，谁的工作量比较大（试得多），谁就更有可能胜出，所以这个过程又被称为工作量证明（Proof of Work），即 POW。
其中，比特币用的哈希算法是 SHA256（Secure Hash Algorithm），满足以上性质。
环保问题
比特币通过 POW 机制来维持整个区块链系统，这也使参与挖矿的人必须不断提高自己的算力，甚至出现了全职矿工、大型矿场。大家没日没夜地计算着，耗电量巨大。
从这个角度来看，比特币的区块链系统似乎是不太环保的。
签名
讲完哈希，我们再看看另一个技术：数字签名。
我们在日常生活中，如果想开户，只要带上证件去银行办理即可，这是中心化。
但在比特币中，我们自己就可以完成开户，不需要任何人的批准，这就是去中心化。
过程很简单，只要创建一对公钥（public key）和私钥（private key）就好了。
有了一对公钥和私钥，能做两件事：
- 加密解密
- 签名验证
加密解密
其实最早的时候，只有对称加密，即加密和解密都用的同一个秘钥。这有一个前提，就是必须有一个安全的渠道来分发秘钥，这非常不方便，也是对称加密最大的弱点。
后来人们发明了非对称加密，即生成一对公钥和私钥，加密用公钥，解密用私钥。公钥是公开的，任何人可以获取公钥，然后把信息加密后再传给服务器。服务器收到信息后，通过私钥来解密。
因为私钥是保密的，只被保管在服务器端，所以其他人无法解密信息。即使有人在中途截获信息进行篡改（加密后的信息），服务器收到后肯定也就解不出来了，就会放弃这个信息并报错。
签名验证
开头提到，比特币区块链上的交易内容是不加密的，那我们要公钥和私钥干嘛？
和上面反一下，加密用私钥，解密用公钥，就可以用来做签名验证。
我先把我的公钥发给大家，然后用我的私钥来加密一条信息，并把加密后的信息发出去。大家收到后，只要用我的公钥去解密，如果能解出来，就能验证这条信息是我发的。
在比特币中，我发起的转账会先用自己的私钥做签名，然后再广播出去，这样大家就可以用我的公钥来验证这条操作确实是我本人发起的。
所以，如果你正在投资比特币，一定要保护好私钥！
另外，在生成公钥和私钥的时候，需要一个好的随机源（a good source of randomness），否则前面的分析就不成立了。在比特币系统中，不仅在产生公钥和私钥的时候需要好的随机源，在签名的时候也需要一个好的随机源，否则就容易泄露私钥。
比特币的签名，一般是先对信息进行哈希（随机源），再对哈希值签名。
如果觉得这篇文章对你有帮助，恳请帮忙点赞、转发。码字不易，非常感谢！