collision-free#

定义：粗略来说，即无法找到x!=y使得h(x)=h(y)，但经过足够的计算总是找的到的。但至少不存在针对该哈希函数的高效方法。 应用：辨识，即对于hash(x)=hash(y)，我们可以假定x=y。从而可以用hash(x)来代替x，节省空间，例如使用hash判断两个文件是否相等。

hiding#

定义：简单说，即无法从hash(x)推导出x。但我们会发现，若在x的选取范围非常小的情况下，仅需暴力尝试-彩虹表即可列出所有输出及其对应输入。于是，我们一般使用一个随机序列r来对x进行加密，即hash(x+r)。r选取自一个高最小熵的分布，难以遍历。故正式定义：若r选取自一个高最小熵的集合，则给定H（r|x)，无法找到x。这里|表示拼接。

应用：承诺

def commit(message,key):
    return (hash(message+key),key)
def verify(message,commit,key):
    return hash(message+key)==commit

我们可以使用key对message进行加密，然后公开我们的key与commit作为承诺。当我们公开自己的承诺内容后，其他人可以用commit与key对message进行验证。这一过程可以应用在零知识证明中，即证明者可以证明自己知道某个值，而不需要公开这个值。其中collision-free保证了我们不能找到两个message同时满足承诺，即message的确定性；而hiding保证了在我们公开message之前，其他人无法通过commit与key推导出message，即message的保密性。

puzzle-friendly#

定义：若k选取自一个高最小熵的分布，则无法找到x，使得Hash(x|k)=y。这里y是一个已知的值，又或者一个已知的集合。 注意：hiding中的无法找到x是指无法解析出被用于计算commit的原始消息，而puzzle-friendly则强调无法找到满足条件的x。因为即使x满足条件，也未必就是原始信息（哈希函数总存在碰撞）。

应用：POW

Block Chain#

区块链正是哈希指针的典型应用之一。

简单来说，区块链是一个链表，每个节点包含一个哈希指针，指向其前一个节点。由于第n个区块中的哈希指针保存了第n-1个区块的哈希值，故我们可以检测出n-1区块是否被修改；而由于该哈希值又参与到了第n个区块的哈希计算中，被保存于第n+1个区块，从而我们亦可以检测出第n-1个区块的哈希值是否被修改。以此类推，攻击者若想篡改区块链中的任意一个区块，必须同时篡改其后所有区块的哈希值，这一过程往往是不可行的（POW要求十分庞大的工作量）

Merkle Tree#

默克尔树是哈希指针的另一个典型应用。

默克尔树是一个二叉树，每个节点包含一个哈希指针，指向其左右子节点。由于每个节点的哈希值又参与到了其父节点的哈希计算中，故我们可以检测出其子节点是否被修改。因此我们仅需记住根节点的哈希指针的哈希值，就可以验证树中任何一个节点的内容是否被篡改。

默克尔也提供了另一种零知识证明的手段：我们希望证明某个节点属于某棵默克尔树，仅需提供从该节点开始到根节点的全部兄弟节点即可，而无需对比整棵树。

变种的排序默克尔树则可以通过展示排序上连续的两个节点，证明本该存在二者中间的节点不存在。

数字签名实现-API层面#

数字签名所需的API如下：

def generate_keypair(key_size):
    # 生成公钥和私钥
    return public_key, private_key

def sign(message, private_key):
    # 用私钥签署消息
    return signature

def verify(message, signature, public_key):
    # 用公钥验证消息
    return True or False

按照该API来描述数字签名的特性即:

$verify(message, sign(message, private_key), public_key) == True$

以及

$无法依靠PK与Sig制造出伪造的签名$

数字签名实现-实践细节#

1. 确保随机性
2. 对消息的hash签名
3. 对哈希指针签名，即是对其指向内容的签名
4. 公私钥算法