前置知识：
哈希函数f(x)是输入x是任意字符串,输出f(x)的固定长度的字符串和可高效计算的函数。高效计算更专业的说法是一个n bit长度的字符串时间复杂度是O(n)。
为了加密的安全，哈希一般由如下性质。
性质一：抗碰撞性
如果已知输入x和输出f(x),那么要找到y != x且f(y)= f(x)是不可行的，难以实现的或者要耗费大量时间。
性质二：隐匿性
如果已知输出f(r + x),r是选自平均分布的值。那么要找到x是不可行的，难以实现的或者要耗费大量时间。
事实上如果输入是硬币的正反面，输出分别是字符串正面和反面。只要试全部输入，那么很容易在知道输出的情况下知道输入。原因在于输入过于集中分布，于是我们可以从平均分布的集合选取r，将r和x连接作为新的输入，那么新的值将是平均分布。
应用：承诺
类比你写下一个数字，放入信封，密封。然后你的承诺是里面的数字你没动过，虽然别人不知到数字是多少，但是当揭开信封时可以核实这个数字是否被动过。
com := H(nonce + msg)
verify(com, msg, nonce)
nonce表示只用一次的平均分布的随机数，+表示字符串拼接。
性质三：谜题友好
一个哈希函数H
一个平均分布的数id
一个目标集Y
找到x使f(id + x) 属于Y
谜题友好的性质保证没有可行的方法所需时间显著小于2^n
Merkle-Damgård transform
将一个文件分为若干块，每块的输入是前一块的hash和当前块。
区块链具有防篡改的性质。每次我们添加新的区块链时，我们首先快速检查每个块的hash是否可以和前一个对上。这需要O(n)次检查。另一种具有相同性质数据结构是Merkle Tree
假设攻击者想篡改某一个数据块，那么产生的新hash将和之前的哈希对不上。我们只需知道根hash，从下到上重新计算一次hash，比对之前的根hash就可以知道是否被篡改。
较之前的链式结构，树结构可以更快证明某一块数据是否属于文件。
链式需要O(n)和所有hash值,而树只需要O(logn)和少量的几个hash值进行验证。
首先我们生成一对密钥，(sk,pk)分别表示为私钥和公钥。将公钥公开，保密私钥。
然后使用签名函数和私钥对信息进行签名sign := sign(sk, msg)。
最后别人使用公钥验证签名是否出自我们。verify(pk, msg, sign)。返回true表示签名有效。
好处是无需注册，完全匿名，有效保护隐私。但是公钥的活动还是有可能与现实中的人联系起来。