比特币中的密码学原理
加密货币（crpto-currency）中用到的密码学主要是 哈希 和 签名。
密码学中的哈希
密码学中用到的哈希函数称为crptographic hash function，有2个重要性质：
-
collision resistance：抗碰撞性 -
hiding：不可逆
collision resistance
抗碰撞性：对于一个哈希函数 HHH，如果几乎不可能找到不同的输入 xxx 和 yyy 使得 H(x)=H(y)H(x) = H(y)H(x)=H(y)，那么这个哈希函数是碰撞抗性的。
此处的collision指的哈希碰撞，不同的输入可能会映射到哈希表的相同位置，一般情况下哈希碰撞不可避免，因为输入的范围大于输出的范围。
有的书上将该性质称为 collision free，该称呼会有歧义，因为该称呼看上去似乎碰撞不会发生，但事实上碰撞是客观存在的。
给定一个x，没有特别好的算法可以得到一个y，满足x和y的hash值恰好相等。如果通过 brute-force去遍历所有输入可能去寻找和x的hash恰好相等的另一个输入，在输入空间比较大的（例如hash空间256位），这种遍历在实际中就因为工作量就特别大而不可行。
该性质可以用来对一个message求digest，用来检测这个message是否被篡改。虽然不同的message的哈希可能相等，但是想要将篡改一个message，令其篡改前后的hash相等，这种工作量在实际中不可行。
没有哪个hash函数在数学上是被证明了的collision resistance。目前的哈希函数都是凭借现实经验，在世界上还没有数学家发现该能够制造该函数哈希碰撞的方法时，认为该函数具有collision resistance。
也有一些哈希算法，曾经认为是collision resistance，后来被数学家发现了可以制造哈希碰撞的方法，最出名的就是 MD5。
碰撞抗性的意义
碰撞抗性确保了哈希值的唯一性，即使输入数据不同，输出的哈希值也应不同。这在以下方面非常重要：
- 数据完整性：在传输数据时，接收方可以使用哈希值验证数据的完整性。如果数据被篡改，其哈希值会发生变化。
- 数字签名：数字签名依赖于哈希函数来生成固定大小的签名。如果存在碰撞，攻击者可以找到不同的数据来生成相同的签名，从而破坏签名的唯一性。
- 密码学应用：许多密码学协议依赖于哈希函数的碰撞抗性，以确保系统的安全性。
攻击方法
尽管找到碰撞很困难，但有几种攻击方法试图找到碰撞：
- 生日攻击：利用生日悖论，攻击者试图通过生成大量消息并计算它们的哈希值来找到碰撞。对于一个n位的哈希函数，生日攻击的复杂度约为 2n/22^{n/2}2n/2。
- 暴力攻击：直接尝试所有可能的输入来寻找碰撞，但这种方法通常需要极其巨大的计算资源。
hiding
哈希函数的计算过程是单向的，是不可逆的。给定一个 x，可以求出其哈希值 y。但是通过 y 不能反推回 x。
hiding性质存在的前提是 输入值的范围要无限的大，否则就可能被通过暴力遍历输入的方式得到输入值。而且输入值的分布要比较均匀，如果输入空间很大，但是绝大多数输入都是少数几个值，也是可能会暴力遍历出来的。
哈希函数的性质作用
hiding性质可以和 collision resistance性质结合在一起，用来实现 digital commitment（有时也称为 digital equivalent of sealed envelope）。
sealed envelope：密封的信封。现实中的含义：例如一个可以预测股市涨跌的股神，为了证明自己预测结果，可以有两种做法：
1.在前一天将预测结果公布，这样可能会因为发布该预测结果而影响第二天的股市；
2.将第二天的预测结果写到一张纸上，放到一个信封中密封起来，第二天打开来验证。这个密封的信封就是sealed envelope。
在数字世界中，digital equivalent of sealed envelope的实现是：将预测值x做哈希运算，将哈希结果公布出去。因为哈希函数的hding性质，人们无法通过哈希结果推出原来的预测值x；而因为collision resistance的性质，这个预测值是不能被篡改的，如果篡改了那么哈希结果就会和公布出去的对应不上。
在实际操作中，因为hiding性质的前提是输入的范围要足够大，而对于股票这种总量只有几千个的，为了防止暴力破解，常用的方法是：选取一个随机数nonce，将原始的预测值 x 拼接上nonce，保证输入的数是足够随机的、分布足够均匀的。
比特币中的哈希
比特币的哈希性质
在比特币中，对哈希函数除了要求具有密码学的哈希函数2个性质外，还有另一个性质：puzzle friendly。
puzzle friendly：
哈希值的计算事先是不可预测的，在知道输入的情况下也很难知道最终的哈希结果是什么。所以如果想要让最终的哈希结果落在某个范围内，除了一个个输入去尝试外没有其他好办法，看最终哪个输入的结果恰好落在要求的范围内。
该性质和collision resistance性质有一定的联系，但是含义不同。
“挖矿”的过程其实就是在找一个随机数nonce，这个nonce和区块头中其他信息合在一起作为输入取出hash，这个哈希结果要小于等于某个指定的哈希阈值。因为比特币中哈希函数的 puzzle friendly 性质，“挖矿”的过程没有捷径，只能一个个尝试，所以这个**“挖矿”的过程才可以作为工作量证明（proof of work）**。
虽然寻找nonce的这个过程很难，但是验证很容易，只需要将该nonce和区块头拼接做一次哈希即可。这个性质称为：difficult to solve，but easy to verify。
比特币的哈希算法
比特币中用到的哈希算法是 SHA-256（Secure Hash Algorithm），该算法同时满足以上3个性质：collision resistance、hiding、puzzle friendly。
账户的开户
日常生活中，开一个普通的银行账户，需要带着资料到银行去审批开户，这就是普通的“中心化”，银行就是那个“中心“。
而在“去中心化”的比特币中，开立一个账户无需经过审批，只需要在本地创建一个公钥-私钥对，就是创建了一个账户，这个公私钥对就是一个账户。这种公私钥的算法称为 asymmetric encryption algorithm（非对称加密算法）。
签名
比特币虽然叫做“加密货币”，但实际上是不加密的，所有的信息都是公开的。此处的公私钥对是为了做签名。例如防止自己账户的比特币被他人冒名顶替转给另一个人。A给B转账，A用自己的私钥做一个签名，B收到之后，可以用A的公钥进行验证该签名。
两个人产生相同256位的公私钥对的概率极低，即使用超级计算机一直声称公私钥对，也很难产生一条和其他人恰好相同的公私钥对，在实际中不可行。避免了这种不断产生公私钥对去盗取他人公私钥对的攻击方式。
这个性质成立的前提是要有一个好的随机源（a good source of randomness）。如果随机源选取的不好，就可能会出现两个人产生的公私钥是相同的。
比特币中使用的签名算法，除了在生成公私钥时候有好的随机源，之后在每次签名时也要有好的随机源。只要有一次签名时使用的随机源不好，就可能造成私钥泄漏。
哈希和签名的结合
在比特币中，先对一个message取哈希，然后再对这个哈希结果签名。
