第 1 章 密码学及加密货币的概述
所有货币都需要通过某种方式控制供给，并需要实施各种安全属性以防止欺骗行为发生。
1.1 密码学哈希函数
哈希函数是一个数学函数，具有以下三个特性：
● 其输入input 为任意大小的字符串
● 它产生固定大小的输出
● 它能进行有效计算：对于特定的输入字符串，在合理时间内，我们可以算出哈希函数的输出。对应n位的字符串，其哈希值计算的复杂度为O（n）。
要使哈希函数达到密码安全，我们要求其具有以下三个附加特性：（1）碰撞阻力（collision-resistance）；（2）隐秘性（hiding）；（3）谜题友好（puzzle-friendliness）。
● 特性1: 碰撞阻力
碰撞指的是两个不同的输入，产生相同的输出。
碰撞阻力：如果无法找到两个值，x和y（x≠y），使得H(x)=H(y)，则称哈希函数H具有碰撞阻力
注：我们说没人能找到碰撞，并不表示不存在碰撞。根据鸽巢原理（Pigeonhole Principle），我们可以得出，必然会有大量可能的输入被映射到任意特定输出。
因为哈希函数的输入空间包含所有长度的任意字符串，但输出空间只包含特定固定长度的字符串。因为输入空间比输出空间大（输入空间是无限的，而输出空间是有限的），一定会有输入字符串映射到相同的输出字符串。
哈希函数的碰撞检测
仅仅通过检验可能输出数量的平方根次数，便大体能找到碰撞，这一事实在概率学中被称为是生日悖论（birthday paradox）。这个碰撞检测算法对每个哈希函数都有效，但是它的问题是其计算需要花很长很长时间才能完成。
我们已经证明，世界上没有哈希函数具有防碰撞特性。我们实践中依赖的加密的哈希函数仅仅是人们经过不懈努力之后暂未成功找到碰撞的函数。。
应用：信息摘要（message digest）
以SecureBox为例，Alice上传了很大的文件，并希望能够在之后下载时确认她下载的文件与上传的文件相同。使用无碰撞哈希函数，Alice只需要记住原文件的哈希值，从SecureBox下载文件后，她可以计算下载文件的哈希值，并与原文件哈希值进行对比。
这里的哈希函数对于一个信息生成固定长度的摘要，这为我们提供了一种记住之前所见事物，并在今后认出这些事物的有效方法。虽然整个文件可能非常大，存储规模达数G，但其哈希值的长度固定如256位，这样极大地降低了存储要求。
● 特性2: 隐秘性
隐秘性保证，如果我们仅仅知道哈希函数的输出y=H(x)，我们没有可行的办法算出输入值x。为了能够实现隐秘性，我们需要x的取值来自一个非常广泛的集合。
隐秘性：哈希函数H具有隐秘性，如果：当其输入r选自一个高阶最小熵（high min-entroy）的概率分布，在给定H（r‖x）条件下来确定x是不可行的。
双竖线‖为连接符号，代表把一系列事件、事情等联系起来。
在信息论中，最小熵是用于测试结果可预测性的手段。而高阶最小熵这个概念比较直观描述了分布（如随机变量）的分散程度，在从这样分布中取样时，我们将无法判定取样的倾向。
应用：承诺（commitment）
承诺协议：一个承诺协议方案由两个算法构成：
◊ com:=commit(msg, nonce)，承诺函数将信息（msg）和一个临时随机数（nonce）做为输入，输出就是一个“承诺”。
◊ verify(com, msg, nonce)， 验证函数将某个承诺输出（com）、临时随机数（nonce）以及信息（msg）作为输入，如果com==commit(msg, nonce)，则返回true；反之则返回false
我们要求以下两个安全特性成立：
◊ 隐秘性：已知com，没有可行的方法找到msg
◊ 约束性：没有可行的办法找到两组(msg, nonce)和(msg’, nonce’)，msg≠msg’，而commit(msg, nonce)==commit(msg’, nonce’)。
对于每次的承诺值，你都需要选择新的随机值，这一点很重要。在密码学中，术语nonce是指，该取值只能使用一次。
使用加密的哈希函数来实现，考虑以下承诺协议的实施方案：
commit(mag, nonce):=H(nonce||msg)，其中nonce为长度为256位的临时随机数
● 特性2: 谜题友好
如果有一个人想找到y值所对应的输入，假定在输入集合中，有一部分是非常随机的，那么他将非常难以求得y值对应的输入。
谜题友好：如果对于任意n位输出值y，假定k选自高阶最小熵分布，如果无法找到一个可行的方法，在比2n小很多时间内找到x，保证H(k‖x)=y成立，那么我们称哈希函数H为谜题友好。
应用：搜索谜题
安全哈希算法（Secure Hash Algorithm 256, SHA-256)
MD（Merkel-Damgard）变换：我们建立一个用于固定长度输入的哈希函数，然后通过一般方法，就可以将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数，我们称这个转换过程为MD 变换 。
压缩函数（compression function）：这种基础型、可用于固定长度、具备碰撞阻力的哈希函数被称为是压缩函数 。经过验证，如果基本压缩函数具有碰撞阻力的特性，那么经过转换而生成的哈希函数也具有碰撞阻力。
