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

By [markchern](https://paragraph.com/@markchern) · 2022-11-04

---

前置知识：

哈希函数
----

哈希函数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](https://storage.googleapis.com/papyrus_images/006649f31874a49565eb75d7fcff8b3f179b573d287f514800fb53717795588e.png)

Merkle-Damgård transform

哈希指针和数据结构
---------

!\[hash pointers

\]([https://images.mirror-media.xyz/publication-images/Ji3lWBDwiJenyQAW5458n.png?height=170&width=189](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](https://images.mirror-media.xyz/publication-images/qx6IMf0kMZI_mqwxLuk2%5C_.png?height=225&width=570))

![tamper-evident 
](https://storage.googleapis.com/papyrus_images/1bfcf58d4ccd8cc853a47ea27c6524f902c8bf1abd1e45a9b91b335d413e4f0c.png)

tamper-evident

区块链具有防篡改的性质。每次我们添加新的区块链时，我们首先快速检查每个块的hash是否可以和前一个对上。这需要O(n)次检查。另一种具有相同性质数据结构是Merkle Tree

![Merkle Tree](https://storage.googleapis.com/papyrus_images/438720123293ec83b0489ddeaedd8715034f8810c00c2e128e0b0ceff79b5bc7.png)

Merkle Tree

假设攻击者想篡改某一个数据块，那么产生的新hash将和之前的哈希对不上。我们只需知道根hash，从下到上重新计算一次hash，比对之前的根hash就可以知道是否被篡改。

较之前的链式结构，树结构可以更快证明某一块数据是否属于文件。

![](https://storage.googleapis.com/papyrus_images/09e1297011b918f54016f79820f82fb9cec752c046a74899fbf0cd31d31b25ad.png)

链式需要O(n)和所有hash值,而树只需要O(logn)和少量的几个hash值进行验证。

电子签名
----

首先我们生成一对密钥，(sk,pk)分别表示为私钥和公钥。将公钥公开，保密私钥。

然后使用签名函数和私钥对信息进行签名sign := sign(sk, msg)。

最后别人使用公钥验证签名是否出自我们。verify(pk, msg, sign)。返回true表示签名有效。

公钥作为身份
------

好处是无需注册，完全匿名，有效保护隐私。但是公钥的活动还是有可能与现实中的人联系起来。

---

*Originally published on [markchern](https://paragraph.com/@markchern/zOoCcP1pGs7v9RfFcMmv)*