哈希函数

Hash函数

哈希函数

$H: \{0,1\}^*\rightarrow\{0,1\}^k,k\in N^+$

可以把任意长度的输入，映射到固定长度上的输出

性质：

• collision-resistant 抗碰撞
• hiding 隐藏
• Puzzle- friendly

collision- resistant 抗碰撞

定义：$\forall x\neg\exist y\ne x,H(x)=H(y)$

即x与H(x)是绑定关系，

如迅雷文件下面有一个MD5, SHA1, SHA256，来保证下载的文件与上传的文件相同

牵一发而动全身，任何轻微的改动，都会对MD5值造成重大的改变

任何大小的文件，都能映射到一个固定长度的字符串上

• 用的比较多的就是：SHA-256
• MD、SHA-1被淘汰，被破解了

hash as message digest 信息摘要，不用担心内容溢出

Hiding 隐藏性

给H(x)很难找到x

预测股票哪支大涨

承诺

让大家看部分，证明确实有答案，但是不能全让看

知道花钱的事实，但是不知道花了多少钱

每次给看部分，验证正确性，然后，

在不让别人知道答案的情况下，证明我知道解法。

零知识证明 zero-knowledge proof

Puzzle- friendly

对每个可能输出值y，如果k是

$H(k||x)=y$

比特币要求每10分钟出一块

挖矿x是一个随机数，

k是父区块的哈希，x是随机数

难度：t，要求前t位是0

要求前

哈希指针和数据结构

哈希函数抗碰撞，用哈希函数来作为指针，找到下一位区块

两类节点

• 权节点：需要记录所有的交易信息
• 轻节点：只保留一个哈希，这个哈希就可以囊括整个链所有的信息

根节点哈希值会包含所有

实验有这个默克尔哈希树，自己构建

随便选去一个哈希函数，然后可以拿数组实现这个算法

证明元素不存在于默克尔树的方法：对data排序，就可以看到这个元素是否在里面

Tree holds many items but just need to remember the root hash

Can verify membership in O(log n) time/space

Variant: sorted Merkle tree can verify non-membership in O(log n)

(show items before, after the missing one)

操作记录存在data里面，

merkle tree不可篡改，根节点保留了一个摘要，高度保存了整个数的信息

如果需要证明一个点存在

只有hash的摘要，我有整个所有的信息要验证

验证一个节点存在

Merkle tree 可以用来验证一个节点是否存在于数据集合中，方法是通过计算这个节点的哈希值，然后与 Merkle tree 的根节点比较¹。具体步骤如下：

1. 首先，找到这个节点在 Merkle tree 中的位置，也就是它的叶子节点。
2. 然后，沿着 Merkle tree 向上遍历，每次取出这个节点的兄弟节点（相邻的另一个叶子节点），并与之进行哈希运算，得到一个新的哈希值。
3. 重复第二步，直到到达根节点，这时得到的哈希值就是 Merkle tree 的根哈希。
4. 最后，将这个根哈希与给定的 Merkle tree 的根哈希进行比较，如果相同，则说明这个节点存在于数据集合中；如果不同，则说明不存在或者数据被篡改了¹。

Merkle tree 的优点是可以用很少的信息来验证一个大量的数据³。只需要知道 Merkle tree 的根哈希和一些中间节点的哈希值，就可以验证任意一个叶子节点是否存在³。这样可以节省网络传输和存储空间³。

纪委的项目非常常用这个的技术，数字取证

验证一个节点不存在

验证者只有根节点hash值，试证者有整棵树的内容

遍历法可以但是是不好的方式，如何优化

方式一：二叉搜索树

把叶子结点排序，构造一棵有序的二叉搜索树

证明节点不存在：

• 证明比他小的元素和大的元素存在且相邻，logn

（这种方法既可以证明存在也可以证明不存在）

方式二：累加器

利用多项式做加密函数，每个节点就是一个根

且可以有重复元素

（多重集合）

很多币就是这样设计的

统计分析：

• 把这个多项式展开，n-1次幂的系数就是交易总合
• 除以最高次就是平均额

可以用hash函数对这个多项式做隐藏，然后实现零知识证明

没有扩张，只需要给多项式系数即可，没有额外扩张

merkle tree缺点

• 增加很难，又添加高度
• 删除很难，后续元素往前填，上层的树需要重构

比特币是merkle，只能证明存在但是没法做统计分析，只能再有第三方的代理但是很麻烦，也需要有区块链的性质

块头，块身

Bitcoin数据结构

父区块哈希||MerkleRoot

一旦验证通过，大家就终止了，这个验证的人就是记账的人

区块链系统里面，第一块交易就是转给自己的（铸币交易coinbase ）

清节点只需要保留区块头，下面的交易不需要存

交易额的0.05%作为奖励，这种不太好，小交易没人记了

难度值两周调一次

测验题：

每十分钟出一个区块，每次有一定奖励，一开始奖励50BTC，后面每4年奖励减少一半，求总的数量（无穷级数

4*365*24*60/10*50*2

21024000块

字节	字段	说明
4	版本	区块版本号，表示本区块遵守的验证规则
32	父区块头哈希值	前一区块的哈希值，使用SHA256(SHA256(父区块头))计算
32	Merkle根	该区块中交易的Merkle树根的哈希值，同样采用SHA256(SHA256())计算
4	时间戳	该区块产生的近似时间，精确到秒的UNIX时间戳，必须严格大于前11个区块时间 的中值，同时全节点也会拒绝那些超出自己2个小时时间戳的区块
4	难度目标	该区块工作量证明算法的难度目标，已经使用特定算法编码
4	Nonce	为了找到满足难度目标所设定的随机数，为了解决32位随机数在算力飞升的情况下 不够用的问题，规定时间戳和coinbase交易信息均可更改，以此扩展nonce的位数

UTXO、工作量证明

签名的特征：

1. 不可复制、不可伪造（安全需求）
2. 认可、个人行为（私钥）
3. 消息知情（公开）
4. 公开验证（公钥）

Digital Signature：数字签名

过程

$keuGen(\lambda)\rightarrow (pk,sk)$，非确定性算法

$Sign(m,sk)\rightarrow \sigma$，非确定性算法

$Verify(\sigma,sk,m)\rightarrow 1$，确定性算法

缺点：

1. m越大，计算开销越大

   解决：对m做哈希，然后将哈希值做Sign

比特币用的是ECDSA，椭圆曲线