# 比特币和数字货币技术 第一周总结

**Published by:** [markchern](https://paragraph.com/@markchern/)
**Published on:** 2022-11-04
**URL:** https://paragraph.com/@markchern/zOoCcP1pGs7v9RfFcMmv

## Content

前置知识： 哈希函数 哈希函数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和当前块。 Merkle-Damgård transform 哈希指针和数据结构 ![hash pointers ](https://images.mirror-media.xyz/publication-images/Ji3lWBDwiJenyQAW5458n.png?height=170&width=189) ![Block Chain ](https://images.mirror-media.xyz/publication-images/qx6IMf0kMZI_mqwxLuk2\_.png?height=225&width=570) tamper-evident 区块链具有防篡改的性质。每次我们添加新的区块链时，我们首先快速检查每个块的hash是否可以和前一个对上。这需要O(n)次检查。另一种具有相同性质数据结构是Merkle Tree Merkle Tree 假设攻击者想篡改某一个数据块，那么产生的新hash将和之前的哈希对不上。我们只需知道根hash，从下到上重新计算一次hash，比对之前的根hash就可以知道是否被篡改。 较之前的链式结构，树结构可以更快证明某一块数据是否属于文件。 链式需要O(n)和所有hash值,而树只需要O(logn)和少量的几个hash值进行验证。 电子签名 首先我们生成一对密钥，(sk,pk)分别表示为私钥和公钥。将公钥公开，保密私钥。 然后使用签名函数和私钥对信息进行签名sign := sign(sk, msg)。 最后别人使用公钥验证签名是否出自我们。verify(pk, msg, sign)。返回true表示签名有效。 公钥作为身份 好处是无需注册，完全匿名，有效保护隐私。但是公钥的活动还是有可能与现实中的人联系起来。

## Publication Information

- [markchern](https://paragraph.com/@markchern/): Publication homepage
- [All Posts](https://paragraph.com/@markchern/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@markchern): Subscribe to updates