密码学的哈希函数

哈希函数的特性：

任意的输入
固定长度的输出
合理时间内，能计算出输出；对应n位的输入，输出的计算复杂度为 O(n)

适用于密码安全的哈希函数，还需要满足额外的三个特性。

碰撞阻力 collision-resistance

对于某个哈希函数H，无法找到两个值，当 x != y 时，而 H(x) = H(y)。
无法找到的意思是无法在合理时间内找到。以256长度的输出为例，如果输入值的空间是 2^256+1，那么理论上必然会发生碰撞。当随机选择2^128个输入值时，就有可能找到两个相同的输出(99.8%)。但是，计算2^128次哈希函数所需要的时间是一个天文数字。如果1秒计算10000个哈希值，那么需要10^27多年的时间。
利用这个特性，我们可以使用哈希输出值来确定输入是否相同。

隐秘性 hiding

隐秘性指的是当输入r选自一个高阶最小墒的概率分布，在给定H(r||x)条件下确定x是不可能的。简单的说，就是无法从输出得到输入。墒是混乱程度的度量，越混乱墒越大。高阶最小墒 high min-entropy，其实指的是最小墒最大的分布。对于密码学而言，随机性是事关影响密码学是否能正常运行的属性。这里的高阶最小墒其实也就是为了保证输入的良好随机性。
该特性可以应用于承诺：将信息和一个随机数(nounce)作为输入，所得的输出即为承诺。这里的承诺包含两方面的意思：通过承诺，其他人无法知道你的输入；而你一旦公开了承诺，你无法欺骗别人该承诺是另外一个信息。所以，这里应用到了隐秘性。此外，每次的承诺都需要一个新的的随机数，这对承诺的安全性很重要。

谜题友好 puzzle-friendliness

谜题友好指：对于n位输出的y值，假设k满足高阶最小墒分布，那么无法在比2^n小很多的时间内找到k，满足H(k||x) = y。直观地说，该特性似乎和隐秘性类似。但其实不然：隐秘性说的是确定x，谜题友好说的是找到k。这一特性应用在比特币中的地方，就是寻找nounce除了一个一个尝试以外，没有其他更好的方法。
该特性的应用有搜索谜题——搜索一个庞大空间来解谜，除此之外，别无他法。

SHA-256

比特币中使用的哈希函数是SHA-256，即输出值的长度为256。因为哈希函数的输入值可以为任意长度，因此需要基于MD(Merkle-Damgard)变化，把固定长度输入的哈希函数转化为接收任意长度输入的哈希函数。接收固定输入的哈希函数叫压缩函数，如果它具有碰撞阻力特性，那么转化后的可以接收任意长度的哈希函数也具有碰撞阻力。

哈希指针

哈希指针是指向数据存储位置及其位置数据的哈希值的指针，即它指向的是数据存储的位置，同时能验证数据的真实性。

哈希指针

区块链就是通过哈希指针构建的，这种数据结构的好处在于：

知道上一个区块位置
验证该值是否被篡改：如果只是某个数据被篡改，那么由于哈希指针还存储着数据的哈希值，因此可以立即判断出数据的真伪

区块链

另外一个使用哈希指针构建的数据结构是梅克尔树。基于哈希指针的特性，梅克尔树可以快速地判断出某个数据或交易序列是否隶属于梅克尔树(二叉树查找log(n))。

梅克尔树

此外，比特币中专门提到一种交易情况：

                A               A
              /  \            /   \
            B     C         B       C
           / \    |        / \     / \
          D   E   F       D   E   F   F
         / \ / \ / \     / \ / \ / \ / \
         1 2 3 4 5 6     1 2 3 4 5 6 5 6

因为 H(F)=H(F,F)=C，[1,2,3,4,5,6]和[1,2,3,4,5,6,5,6]有相等的根结点。在SHA256具有碰撞特性的前提下，为了避免这种情况，比特币中会检测hash输入的两个值相同的情形。

数字签名

数字签名指的是对一段信息制作签名表示对其的认可，这个认可只对该信息有效，并且第三方无法根据该签名构造你对其他信息的签名。数字签名方案包括：

生成公钥私钥对，私钥用于签名，必须安全保存；公钥可以公开，用于他人验证签名有效性
把信息和私钥作为输入，输出即为签名
使用公钥，信息和签名作为输入，进行验证

在实践中，我们往往通过对哈希值进行签名，这样可以实现对任意长度信息的签名。

椭圆曲线数字签名算法 ECDSA

ECDSA是比特币中使用的数字签名方案(另有标准椭圆曲线 secp256k1)，涉及到的参数有：

私钥：256位
公钥：512位(未压缩) 257位(已压缩)
待签名信息：256位
签名：512位

这里需要强调的是，需要提供良好的随机性来生成密钥。
基于数字签名，我们可以认为公钥代表着不同的身份：当某个公钥能够验证某个签名，可以视作该公钥发布了该消息；同时，你必须知道相应的私钥。因此，可以通过算法生成多个公钥/私钥来表示你自己，这里算法需要保证：别人生成和你相同密钥的概率很低，低到在实践中往往不可能发生。

在比特币中，个人的身份就是通过公钥的哈希值来表达，但是是否这样就能保证个人信息的匿名信，值得商榷。因为你通过该公钥做出的声明，交易的数据，还是可以用于推断你的身份信息。但是，比特币至少实现了一种去中心化的身份管理体系。