哈希#
大家应该都比较熟悉哈希函数的工作原理，密码学中用到的哈希函数被称为crypto-graphic hash function。
它有两个重要的性质：一个叫做 collision resistance. 这个地方的 collision 是指哈希碰撞。
如果有两个输入 x, y且 x ≠ y , hash 函数是H(v), 但是H(x) = H(y)。 这就叫做哈希碰撞。
两个不同的输入算出来的哈希值是相等的。哈希碰撞是很常见的。像我们使用哈希表的过程中就会遇到 hash 碰撞。
不同的输入可能会被映射到 hash 表中的同一个位置。一般来说哈希碰撞是不可避免的。
因为输入空间是远远大于输出空间的，比如说我们有 256 位的 hash 值。那输出空间有多大呢。
所有 hash 值的可能性就是 2 的 256 次方，输出空间就只有这么大。但是输入空间可以是无限大的。
所以它是有任意多样的可能性。按照鸽笼原理的话。必然会出现有两个输入被映射到同一个输出的情况。
所以我们这里说的collision resistance 并不会出现哈希碰撞。有的📖上管这个性质叫做collision free。
这个说法我不是特别喜欢。因为它对人很容易造成误解。好像是碰撞不会发生。实际上碰撞是客观存在的。
它这个意思是实际上没有什么高效的方法，人为的去制造哈希碰撞。就给定一个x，没有什么好的办法，
你能找到另外一个y，使得H(x) 和H(y)的哈希值恰好相等。没有什么高效的方法去找。你硬要找的话可以用蛮力求解的方法。
比如说这个x和y，你就遍历所有输入的可能性。然后看看哪一个算出来的哈希值正好相等。这种叫做brute-froce。
遍历所有的取值，最后找了一个哈希值恰好碰撞在一起。如果输入空间比较大。比如说对于 hash 值是 256 位的话，
实际上你要用蛮力求解的方法在实际中是不可行的。他的工作量实在是太大了。
那么collision resistance 这个性质有什么用呢？
他可以用来对一个message求digest。
比如我们有一个message叫做m，我们取它的哈希值H(m)。
这个哈希值可以认为是这个消息的digest。用来检测对这个message的篡改。
比如说有人改这个message的内容，它的 hash 值就会发生变化。
那么collision resistance 这个性质就是说你找不到另一 m'使得H(m')跟H(m)恰好相等。
没有办法篡改内容。而又不被检测出来。比如说你有一个很大的文件。你想把它存在到某个云存储服务上。
相当于你用到的时候再把它下载回来，那么你怎么知道你下载的版本，跟你当初上传的版本是一样的呢？
这就可以用到 hash 函数的 collision resistance 性质。在你上传这个文件之前，先算一个 hash 值出来。
这个 hash 值存在本地。将来你下载之后，再算一个 hash 值。跟原来你存的 hash 值比较一下。如果是一样的话。
那么说明上传的这个文件没有被篡改。下载的还是原来当初的版本。这就是 collision resistance 的一个用途。
有一点大家注意。没有那个 hah 函数，能够在数学上证明是 collision resistance 的。
也就是说我们刚刚讲的这么重要的一个性质。从理论上是证明不出来的。
这个只能靠实践中的经验。有些 hash 函数经过时间的长期检验。
世界上有那么多的密码学专家。谁也没有能够找到人为制造 hash 碰撞的方法。
所以我们就认为这些 hash 函数是 collision resisitance 的。也就是实践经验。
也有一些 hash 函数以为我们认为是 collision resistance 的。
但是后来大家找到了，制造 hash 碰撞的方法。这里面一个很重要的例子就是 MD5，MD5 曾经是个很流行的 hash 函数，大家原来以为他很安全。
但现在已经不行了，我们已经知道怎么人为的制造 hash 碰撞了。
密码学用的 hash 函数还有第二个性质：hiding。hiding 是什么意思呢？hiding 是说 hash 函数的计算过程是单向的。
是不可逆的，给定一个 x 可以算出他的 hash 值H(x), 但是从 hash 值H(x)没有办法反推出原来的输入x，换句话说，
这个 hash 值H(x)没有泄漏有关输入x的任何信息。这叫做 hiding。但是其实你想一想你想要知道这个输入的话，
也是有办法的。怎么办，还是用蛮力的办法。我把这个输入所有可能的取值，遍历一遍，看看有那个输入的值求解H(x)跟原来的H(x)相等。
这就我能猜出来原来的输入 x 是什么。所以蛮力求解是一种办法。hiding 这个性质成立的前提是，这个输入空间要足够的大，
使得这种蛮力求解的方法是不可行的。而且这个输入的分布要比较均匀。各种可能的取值的可能性都是差不多的。如果这个输入空间虽然是很大。
但是绝大数情况下都是取值都是在几个少数几个值。那么也是比较容易被破解的。
hiding 这个性质有什么用呢？他可以和 collision resistance 这个性质结合在一起。用来实现 digital commitment。这个 digital commitment 也叫做 digital equivalent of a sealed envelope.
我们说一下现实生活中 sealed envelope. 是跟什么用的？
比如说有一个人他能够预测股市，可以预测第二天那些股票会涨停。
那怎么证明这个人预测的是不是准确呢？一种办法是这个人提前一天这个人在电视台上公布预测结果（我预测 xxx 股票第二天涨停。）。
第二天收盘之后呢看一下这个股票是不是真的涨停。就知道预测的准不准了。
这样做有什么问题吗？这好像是预测准不准的方法。有什么问题吗？如果你预测结果提前公布了，
可能会影响股市。比如说这个人很有名气，大家觉得这个人是个股神。本来这支股票不会涨停，他这么公开预测，
大家拼命的去买。结果他变成了涨停。当然了方向的情况也有可能发生。就这支股票本来确实是需要涨停的，
有人想踢场子。你不是预测他涨停吗，我就不让他涨停。拼命的砸盘。这都有可能发生。这说明预测结果不能提前公开。
但是预测结果不提前公开。你等第二天收盘之后再公开，那你怎么知道这个预测结果有没有被篡改过。
你最后公开的结果是不是你提前一天做出来的。这个就要用到我们说的 sealed envelope。
你把你的预测结果写在一张纸上，放到一个信封里给封好了。这个信封要交给第三方的公正机构保管。
等第二天收盘之后再把它打开，验证一下这个结果准不准。现实中 sealed envelope 就是这个。
那在电子世界里呢，我要有一个 digital sealed envelope 我要怎么实现呢？把这个预测结果作为输入 x 算出一个 hash 值来。然后把这个 hash 值可以公布出去。因为我们有这个 hiding 的性质。所以你从这个 hash 值。不知道预测结果是什么。然后第二天收盘之后呢，我在把预测结果公布出去。因为有这个 collision resistance 的性质。所有我这个预测结果是不可能篡改的。你要是改了的话就给当初公布出来的这个 hash 值是对不上了。这就起到了一个 sealed envelope 的功能。 实际操作中有一些细节要注意。就我们说 hiding 这个性质的前提是什么。输入空间要足够大。分布要比较均匀。如果这个输入不满足这个性质。像这个例子，预测第二天哪只股票会涨停。股票就那么几千只输入空间不是足够大。那么常用方法是把这个输入后面随机拼接一个随机数。然后再一起取 hash。就这个不是x了，而是 x 的后面拼接一个 nonce，然后整个取 hash。H(x | Nonce). 这个 nonce 是我们选取的随机数，保证我们选举之后，整个输入是足够随机的。然后分布也是足够均匀的。这是实际中操作要注意的一些细节。
除了密码学中要求的这两个性质之外，比特币中用到的 hash 函数还要求第三个性质。叫 puzzle friendly。他这个意思是说，hash 的计算是事先不可预测的。你光看这个输入，你很难知道他这个 hash 值是什么。所以你想到你算出来的 hash 值是落在某个范围之内的。那没有什么好办法你只能一个一个去试。看那个输入算出来是恰好落在要求的那个范围之内。比如说你想得到一个 hash 值。前面k位都是 0。0000000…0000000xxxxxxx..xxx 整个是 256 位，必须以k个零开始。那什么要的输入会算出这个 hash 值呢？不知道 puzzle friendly 这个性质是说你事先是不知道的。那个输入更有可能算出这个 hash 值。那你要得到这个 hash 值就一个一个去试。没有什么捷径。这个性质为什么叫做 puzzle friendly 后面我们讲到比特币挖矿的过程。大家可能听说过挖矿这个词。挖矿实际上就试找一个 nonce。找这么一个随机数，这个 nonce 跟区块的块头里的其他信息合在一起。作为输入，取出一个 hash 来，那个 hash 值要小于等于某个制定的目标阈值。这是H(block header) ≤ target。 比特币是区块链，区块链就是一个一个区块组成的链表，每一个区块都有一个块头，block header， block header 中有很多的域。 其中有一个域是我们可以设置的随机数 nonce。那挖矿的过程就是不停的去试各种不同的 nonce，使得整个 block header 取 hash 之后，落在指定的范围之内。就比如说这是整个的输出空间 outspace。我们要求算出来的 hash 值只有前面这一点是合法的。这个是 target space。这个 puzzle friendly 这个性质是说，这个挖矿的过程没有捷径。只能够不停的去试大量的 nonce，才能找打符合要求的解。所以这个过程才可以用来作为工作量证明。 叫做 proof of work。 你挖到矿了找到了符合要求的的 nonce，一定是因为你做了大量的工作。因为没有别的捷径。
这里大家注意，虽然这个挖矿的过程。需要很多的工作量，才能找到一个符合要求的 nonce。但是一旦有人找打了这样一个 nonce。发布出去之后，其他人要验证这个 nonce 是不是符合要求。 是很容易的，只要算一次 hash 就行了。这个 nonce 作为 header 的一部分，算一次 hash 值 看他是不是小于等于这个目标的阈值。挖矿很难验证很容易。这个性质叫做 difficult to solve, but easy to verify. 我们设计这种 mining puzzle 的之后要注意这个性质。
比特币中用的 hash 函数是 SHA-256，这个 sha 的意思是，secure hash algorithm. 我们说的这三个性质她都是满足的。有同学可能觉得 puzzle friendly 和 collision resistance 很像。这两个性质是有一定的联系。但是不是完全一样 。我们说比特币用到了密码学中的两个功能， 一个是 hash，一个签名。
签名#
到这里我们把第一个功能 hash 讲完了。我们下面讲签名。
要讲签名我要讲一下比特币系统中的账户管理。日常生活中你想要开个账户怎么办，带上证件去银行办理开户手续。这就是中心化系统中的账户管理方式。 那比特币是去中心话的，他没有银行之类的这类机构。那怎么开账户呢？每个用户自己决定开户。不需要任何人批准。开户的过程很简单，就是创立一个公钥和私钥的对 pair。(public key, private key). 在本地创立一个公私钥对。就是一个账户。这个就在比特币中代表了一个账户，公私钥这个概念是来自非对称加密这个体系。叫做 asymmetric encryption algorithm, 最早的加密体系是对称的。叫做 symmetric encryption algorithm。比如说两个人之间要进行通信，我要把某个信息发给你。但是这个通信的网络是有可能被窃听的。那怎么办呢。咱们两个事先商量一个密钥。一个叫做 encyption key. 我把这个信息加密之后发送给你。你收到之后再用这个密钥解密。因为这个加密和解密用的是同一个密钥。所以这个叫做对称的加密体系。他这个前提是假设。有某种安全的渠道。能够把这个密钥分发给通讯的双方。因为你显然的不能把这个密钥在网络上以明文的形式传输。我们假设网络本身就是不安全的。有可能被窃听，这个就是对称加密体系的一个弱点。密钥的分发不是很方便。解决这个问题非对称加密体系就提出来我们不是用一个密钥，而是用一对密钥。有一个公钥还有一个私钥。加密用的是公钥，解密用的是私钥，比如说我要把一个信息传给你，我用你的公钥给这个信息加密，你收到之后再用你的私钥解密。得到原来的信息。 大家注意这个加密和解密用的是同一个人的公钥和私钥。都是这个接收方的公钥和私钥。
这有什么好处呢？公钥是不用保密的，加密用的公钥是不用保密的，你可以告诉所有的人。有的人他的 homepage 就列出来他的 pbk： public key。大家都可以知道。私钥是要保密的，解密是要用私钥解密的， 但是私钥只要保存在本地就行了。不用传给对方。就给你通讯的那个人不需要知道你的私钥。他是用你的公钥加密的。 你要回复他的话你用他的公钥加密。都不需要知道对方的私钥。这就解决了对称加密体系中密钥分发的不方便的问题。 比特币系统中呢，你要创建一个账户。就在本地产生一对公私钥。这个公钥就相当于你的银行账号。别人要给你转账，只要知道你的公钥就行了。这个私钥相当于你的账户密码。知道这个私钥就可以把这个账户上的钱转走。那么有一个问题我们前面说比特币系统是不加密的。他叫加密货币他其实不是加密的。 信息都是公开的。那我要这个公钥和私钥干什么呢？实际上用来做签名。
比如说我要转 10 个比特币给你。然后我这个交易发布到区块链上，别人怎么知道这个交易确定是我发起的呢？会不会是有人冒名顶替。偷偷把我帐上的钱转走呢？这就需要我在发布这个交易的时候要用我自己的私钥对这个交易进行签名，那其他人收到这个交易之后呢，在用我的公钥去验证这个签名的正确行。签名用的是私钥。验证签名用的是这个人的公钥。
仍然都是同一个人。既然每一个人都是独立的产生账户。本地独立的生成公私钥对。不需要任何人相等，那万一两个人生成的公私钥对相同。怎么办？比如说有人想偷取比特币，一种方法是不停的产生公私钥。然后对比一下我产生的公钥。跟区块链上某个已有的公钥是不是相同。如果是一样的话，就可以用私钥把这个帐上钱给偷走。这种攻击方法从理论上说好像是可以的。但是实际当中是不可行的。比如说你是 256 位的 hash 值的话。产生相同的公私钥的可能性是微乎其微的。比如你有一台超级计算机每天产生大量的公私钥对。出现来两个人的公私钥对相同的情况概率也是可以忽略不计的。这个概率比地球爆炸的概率还要小。到目前为止还没有发现那个人用这种方法。能够攻击成功的先例。这里要强调一点，我们这里假设。产生公私钥的时候有一个好的随机源。这叫做 a good source of randomness. 生成公私钥的过程显然是随机的。如果选取的随机源不好的话，那么前面的分析就不存在了。就会出现两个人的公私钥对生成的是一样的。比特币中用的签名算法不光是，生成公私钥的时候要有好的随机源。之后每一次签名的时候也要有好的随机源。只要有一次签名用的随机源不好的话，就有可能泄露私钥。然后就全完了。这一点大家要一定注意。
我们讲了两个功能一个是 hash，一个签名。 这两个功能是可以结合起来使用的。比特币系统中一般是先对一个消息求一个 hash，然后在对这个 hash 值签名。