[区块链 Sec2] 密码学相关
所有的货币都需要通过各种安全属性以防止欺骗，不同于依赖于中央机构实现安全规则的纸币，比特币的安全规则完全通过技术手段实现，并只运用到了密码学中少量相对浅显的理论
1 哈希函数
哈希函数是一个数学函数，具有以下三个特性：
- 输入可为任意大小的字符串
- 产生固定大小的输出（为方便讨论假定为256位）
- 能进行有效计算，对应n位的字符串输入，计算复杂度为O(n)
我们将只专注于加密的哈希函数，要使哈希函数达到密码安全，要求其具有三个附加特性：
- 碰撞阻力（collision-resistance）
- 隐秘性（hiding）
- 谜题友好（puzzle-friendliness)
特性1：碰撞阻力
没人能找到该哈希函数的碰撞则称该函数具有碰撞阻力
但实际上，由于输入空间大于输出空间，碰撞必然存在。
生日悖论：通过检验可能输出数量的平方根次数，便大体能找到碰撞
然而这种近乎暴力的碰撞检测算法找到碰撞的概率比下两秒地球将被陨石摧毁的概率还小
应用场景：信息摘要，提供了一种验证事物完整性和正确性的手段
特性2：隐秘性
狭义理解：仅仅知道哈希函数的输出y=H(x)，没有可行的办法算出输入值x
实际情况中，有可能输入并非来自分散的集合（例如有限的集合，这意味着隐秘性容易遭到破坏），我们可以通过与另一个较为分散的输入进行结合来实现隐秘性。
应用场景：承诺
我们想做的事情称为承诺，它是一个数字化的过程。
比如我说明天的体育彩票开奖号码为123456，但我不想立刻告诉大家，只想让大家知道我预测了一个号码。开奖后如果不是我预测的号码，我给大家一人一万元。如何保证开奖前大家看不到我的预测，同时使得我无法更改自己的预测以抵赖？
在开奖前，将我预测的号码和一个随机数作为哈希函数的输入，将得到的输出公之于众，大家不可能通过我公布的输出推出我预测的号码。开奖后，我公布我预测的号码和这个随机数，那么大家都能验证我说的是否正确（通过公开的哈希函数），同时，我也不可能改变主意，赖掉这件事了。
在密码学中，这个随机数(nonce)意味着只能使用一次。这一点很重要，不少安全函数对随机数的随机性及使用次数都有明确规定。
特性3：谜题友好
谜题：对庞大空间进行搜索才能找到解决办法的数学问题
如果一个哈希函数具备谜题友好性，意味着对于这个谜题没有一个解决策略，比只是随机地尝试x取值会更好。
2 哈希指针及数据结构
哈希指针是一个不但可以指向数据存储的位置，还可以明晰某个时间戳下该数据的哈希值的指针
image
通过哈希指针而不是普通指针构建的一个链表，我们把这个链表称为区块链，每个区块不仅能告诉我们上一个区块的值在哪里，还包含了该值的摘要，使我们能验证那个值没有改变。
另一个我们可以用哈希指针建立的有用的数据结构是二叉树
梅克尔树(Merkle Tree)
image
梅克尔树的主要特点在于它可以实现简洁的隶属证明，即证明某个数据区块隶属于某梅克尔树
3 数字签名
数字签名得名于其实质上是对在纸上手写签名的数字模拟
往往对数字签名有两个特性要求：
- 只有你可以制作你自己的签名，但任何看到它的人都能验证其真实有效性
- 一个签名应该只与某个特定文件相联系，正如纸上签名不能被剪下来粘贴到别处一样
数字签名往往由三个算法步骤构成：
- 随机生成一对（可能具有某些输入参数）公钥和私钥
- 签名：把一段消息和私钥作为输入，输出就是签名（可简单理解为加密）
- 验证：把消息，公钥，签名作为输入，返回真则签名属实
公钥即身份：
公钥和私钥的体系，帮助我们引入去中心化的身份管理的理念。
如果你见到一条消息的签名被公钥pk正确验证，那么你可以认为pk就是在表达这条消息。从这个角度讲，公钥就是身份，让某人能为pk身份发生，它必须知道相应的私钥sk。
同时，你可以随时制定新的身份，只需要生成新的密钥对即可。
