区块链学习笔记（三）——第一章 密码学及加密货币概念
加密数字货币与法定货币不同在于，其安全规则需要完全通过技术手段实现，而非依赖中央机构
1.1. 哈希函数
哈希函数三个特性：
- 任意大小字符串均可作为输入；
- 产生固定大小输出；
- 能进行有效计算，即对应n位字符串，其哈希值计算复杂度为$O(n)$。
为使得哈希函数达到密码安全，要求其具有以下三个附加特性：
- 碰撞阻力(collision-resistance)
- 隐秘性(hiding)
- 谜题友好(puzzle-friendliness)
碰撞阻力：
如果无法找到两个值，$x$和$y$，$x \neq y$，而$H(x)=H(y)$，则称哈希函数$H$具有碰撞阻力。
这里写图片描述
P.s:根据鸽巢原理可知，必然有大量可能输入被映射到任意特定输出。因此，碰撞必然存在，但我们只需要保证其在概率上是难以实现的即可
- 应用：信息摘要——哈希有助于确认事物未被更改。
隐秘性：
哈希函数$H$具有隐秘性，如果：当其输入$r$选自一个高阶最小熵（high min-entroy）的概率分布，在给定$H（r‖x）$条件下来确定$x$是不可行的。
P.s：在信息论中，最小熵 是用于测试结果可预测性的手段，而高阶最小熵这个概念比较 直观描述了分布（如随机变量）的分散程度。具体来说，在从这样分布中取样时，我们将 无法判定取样的倾向。
简而言之，隐秘性保证：如果我们仅仅知道哈希函数的输出$y=H(x)$，我们没有可行的办法算出输入值x。
-
应用：承诺——类似于签名：
承诺协议一个承诺协议方案由两个算法构成：- $com:=commit(msg, nonce)$，承诺函数将信息$（msg）$和一个临时随机数 $（nonce）$作为输入，输出就是一个“承诺”。
- $verify(com, msg, nonce)$，验证函数将某个承诺输出$（com）$、临时随机数 $（nonce）$及信息$（msg）$作为输入，如果$com==commit(msg, nonce)$，则返 回“真”$（true）$；反之则返回“假”$（false）$。
谜题友好：
直觉上，谜题友好可以这样解释，如果有一个人想找到y值所对应的输入，假定在输 入集合中，有一部分是非常随机的，那么他将非常难以求得y值对应的输入。
安全哈希算法
SHA-256是一个主要被比特币世界采用，并且效果还很不错的哈希函数。
MD变换：只要我们能建立一 个用于固定长度输入的哈希函数，然后通过一般方法，就可以将接受固定长度的哈希函数 转化为可接受任意长度输入的哈希函数。
压缩函数：这种基础型，可用于固定长度，具备碰撞阻力的哈希函数被称为是压缩函数 （compression function）。经过验证，如果基本压缩函数具有碰撞阻力的特性，那么经过转换而生成的 哈希函数也具有碰撞阻力。
1.2 哈希指针及数据结构
哈希指针：哈希指针是一个指向数据存储位 置及其位置数据的哈希值的指针。一个普通的指针可以告诉你数据存储的位置，哈希指针 不但可以告诉你数据存储的位置，并且还可以给你一种方式，让你验证数据没有被篡改过。
哈希指针
区块链
我们通过哈希指针构建一个链表，我们将这个数据结构称为区块链 （block chain）
区块链
在区块链中，上一个区块指针被置换为哈希指针。因此，每个区块不仅能 告诉我们上一个区块的值在哪里，还包含了该值的摘要，使我们能够验证那个值没有改 变。我们存储链表头部（the head of list），即一个普通的哈希指针指向最近使用的数据区块。
创世区块：我们可以搭建一个包含很多区块的区块链网络，链表头部的 哈希指针被称作创世区块 （genesis block）。
- 应用：防篡改日志——只要我们将链表头部的哈希指针存储在对手无法改 动的地方，对手将不能做到在不被检测到的前提下，篡改任何区块（见图1.6）。
防篡改日志
梅克尔树：
我们可以用哈希指针建立的有用的数据结构是二叉树。使用哈希指针的二叉树 也叫作梅克尔树 (Merkle trees)，以其发明者拉尔夫·梅克尔（Ralph Merkle）的名字命名。
梅克尔树
这里写图片描述
类似于区块链，同样地仅仅通过记住顶部的哈希指针，任何企图篡改任何数据的行为都会被检测到。
-
应用：
- 隶属证明：
梅克尔树的一个特点是它可以实现简洁的隶属证明。我们只记住树根节点，然 后他需要展示给我们数据块信息，以及从该数据区块通向树根节点的那些区块，我们可以 忽略树的其余部分，这样做是因为这些区块已经足够让我们验证通往树根节点过程中所有 的哈希值。
- 隶属证明：
隶属证明
2. 非隶属证明：一个排序梅克尔树是把底层的数据通过某些排序得到的梅克尔树，这里排序规则可以 是字母表排序、词典排序、数字化排序，或者其他约定的排序方式。有了排序梅克尔树，我们可以在一个对数复杂度的条件下验证某一个数据区块并非来 自某梅克尔树。也就是说，我们可以证明某个特定区块不属于梅克尔树，而我们只是简单 通过展示被验证区块之前的区块路径，以及被验证区块之后的区块路径，就可以达到目的。
eg：如果之前、之后两个区块在树上是连续的，那么这说明了被验证区块与该梅克尔树之 间是非隶属关系。因为被验证区块确实隶属于梅克尔树，它需要在两个条目之间，而如果 两个条目是连续的话，二者之间则并没有空间。
1.3 数字签名
预期：
第一，只有你可以制作你自己的签名，但任何看到它的人都可以验证其有效性；
第二，我们希望签名只与某一特定文件发生联系，因此该签名不能用于表明你同意或 支持另一份不同的文件。
方案——由以下三个算法组成：
- $(sk, pk) :=generateKeys(keysize) $，$generateKeys$方法把$keysize$作为输 入，来产生一对公钥和私钥。私钥$sk$被安全保存，并用来签名一段消息；公钥$pk$是人 人都可以找到的，拿到它，就可以用来验证你的签名。
- $sig:=sign(sk, message) $签名过程是把一段消息和私钥作为一个输入，对于 消息输出是签名。
- $isValid:=verify(pk, message, sig) $验证过程是通过把一段消息和签名消 息与公钥作为输入，如果返回的结果是真，证明签名属实；如果返回的结果为假，证 明签名消息为假。
要求两个性质有效：
- 有效签名可以通过验证，即： $$verify(pk, message, sign(sk, message))==true$$
- 签名不可伪造。
实践考量：
- 随机性的良好来源很重要；
- 可以对于哈希指针进行签署。如果你签署了哈希指 针，那么该签名覆盖（或者说保护）整个结构——这不仅仅是哈希指针本身，还包括哈希 指针指向的整个区块链。比如，如果签署了区块链末尾的哈希指针，其结果就是你有效地 数字签署了整条区块链。
椭圆曲线数字签名算法：
比特币使用的数字签名方案叫作椭圆曲线数字签名 算法（ECDSA） 。ECDSA为美国政府的标准，是早前DSA算法利用了椭圆曲线的升 级版。这些算法经过了数年的细致密码分析，且被普遍认为是安全的。
1.4 公钥即身份
- 将公钥视为身份的一个结果是，你可以随时制定新的身份——你可以简单通过数字签 名方案中的generateKeys程序，生成新的密钥对sk和pk。pk是你可以使用的新的公共身 份，sk是相应的密钥，只有你自己知道并可以让你代表身份为pk发声。在实践中，你可能 会使用pk的哈希作为你的身份，这是因为公钥很大。如果是这样的话，为了验证消息来自 你的身份，人们会需要验证：（1）你的身份确实是pk的哈希；（2）信息能经过公钥pk验 证。
- 比特币对待身份的方式：去中心化身份管理——这些身份在 比特币语言中被称为地址。你可以常常听到地址这个词，用于比特币或加密货币相关的内 容中，而地址其实就是公钥的哈希值。作为去中心化身份管理方案的一部分，它就是某人 凭空捏造的一个身份而已。
两种简单的加密货币
-
高飞币：
两条规则：
1. 指定高飞可以随时创建新币，且这些 新创建的币都属于他。
2. 拥有此币的人可以将其转给其他人。转移一只币不是简单地 将币数据结构发送给接受者，而是必须通过密码程序来完成。
缺点：未解决双重支付问题 -
财奴币：财奴币的工作原理是人们可以看见哪些币是 有效的。它防止双重支付，因为每个人都可以查看区块链，看到所有交易都是有效的，每 一只币确实都只被消耗了一次，但其问题是，财奴的权利太大了。
