区块链
比特币
一、密码学原理
1.哈希函数
collision resistance:抗碰撞性
即很难找到两个数可以通过同一个Hash函数得到同一个输出，H(a) = H(b)
哈希碰撞是很常见的，因为输入空间是无穷大的，但是输出空间是有限的
目前没有哪个函数可以证明是collision resistance的，只是没有能找到人为制造hash碰撞的方法，所以认为是抗碰撞的（MD5）
hiding:不可逆性
即给定一个输入x，使得通过Hash得到的H(x)无法反推出x
实现这一性质需要一些条件，包括足够大的输入空间和比较均匀的输出取值
puzzle friendly:谜题友好性
即Hash的结果是不可预测的，所以如果想让某个值落在一定的范围内，就只能一个一个去尝试x
在比特币挖矿的过程中就是在寻找一个随机数nonce，与该区块的其他信息block header合在一起作为Hash的输入，使得结果小于等于所要求的目标阈值
H(block header + nonce) <=target
而这个寻找随机数的过程，也叫做工作量证明PoW（Proof of Work），计算机节点需要通过解决一个复杂的数学问题来证明它们在创建新区块时进行了足够的工作，通常是一个哈希函数，结点需要不断尝试不同的值来确定一个符合条件的，这是挖矿必须经历的过程，因为没有别的途径
虽然寻找随机数是困难的，但是得到随机数之后验证很简单，只需要算一次Hash就可以了
比特币中所使用的SHA-256算法对于以上的性质都是满足的
2.数字签名
如何在比特币或者说区块链中创建一个账户，即为创建一对公钥和私钥，是一种非对称的加密方式
通过随机数生成器生成私钥，再通过私钥创建公钥，再通过公钥创建账户的地址
公钥和私钥分别对应账户中的账号和密码，别人可以知道你的公钥，然后将钱转入你的账户，你可以通过你的私钥从你的账户中取出钱来
而如果我要进行交易和转账，如何知晓这笔交易是由我本人发起的呢，就需要在我发起交易之前，用我自己的私钥对这笔交易进行签名，生成一个摘要（digest），别人想要验证签名的正确性就需要用我的公钥进行验证
即加密是用接收者的公钥加密，然后接收者再用接收者的私钥解密
而签名则是发送者用发送者的私钥签名，接收者再用发送者的公钥验证
示意图：
二、数据结构
1.哈希指针
首先它具有指针的作用，存放地址，其次，它还保存着上一个区块的哈希值，因此它能够检测出前面的内容是否被修改
区块链就是一个一个块组成的链表，而哈希指针则是链接各个区块的部分
2.Merkle Tree
类似于二叉树，其中分支结点使用的都是哈希指针，叶节点是数据块，用于存放交易信息
每个区块中包含着两部分，block header和block body，根结点的哈希值就存放在block header中，而交易的列表则存放在block body中
为什么要使用Merkle Tree呢，目的是为了利用Merkle Proof，来证明交易是否正确
用Merkle Proof向一个轻结点（例如手机中的比特币钱包，只有块头）证明某个交易写入了区块链 ,找到交易所在的位置(最底行的其中一个区块)，这时该区块一直往上到根节点的路径就叫Merkle Proof，不断验证沿途路径上的哈希值最后得到根哈希，与保存的根哈希值进行比较即可得出是否篡改
证明一个Merkle Proof所需要的时间复杂度是多少呢，假设有n个交易，那么时间复杂度为O(logn)
如果要证明一个交易不存在该区块中，那么需要把整棵树都传给轻结点，轻结点在验证过所有结点都是没有问题的，只有这些交易存在，那么就证明提供的交易是不存在的，但是这样的时间复杂度是O(n)的，比较麻烦
当把区块中交易的哈希值进行排序后，那么证明不存在就容易很多了，只需要证明该交易的哈希值相邻的两个交易是切实存在的、无误的，那么就证明这个交易是不存在的了，时间复杂度也只要O(logn)，但是需要提前对哈希值进行排序
3.比特币区块信息：
| block header | block body |
|---|---|
| version（版本） | transaction list（交易列表） |
| Hash of previous block（指向前一个区块的哈希指针） | |
| Merkle Tree root hash（默克尔树根哈希值） | |
| target（挖矿难度目标阈值） | |
| nonce（随机数） |
结点分为全结点和轻结点，全结点包含了所有信息，block header和block body，而轻结点则只包含block header
三、协议
双花攻击：虽然数字货币摆脱了第三方中心化机构，但因为数字货币本身是一种数据文件，所以可以花出去两次
数字货币的铸造和发行：比特币系统中由挖矿这一动作决定的
那么如何脱离第三方机构的控制，且仍能验证交易的有效性，防止双花攻击，实现去中心化的交易系统？便是要依赖区块链这一数据结构
下面是一个比特币的流通示意图，A在这个过程中具有铸币权，铸造了10个比特币，然后将10个比特币分别给了B和C，然后B又将比特币分给了C和D，最后C将自己的比特币给了E。在这个过程中，A给出自己的比特币时，要给出自己比特币的来源，即铸造所来，之后B的交易也是如此，需要给出自己的比特币是由A所给出，在C与E的交易中，C的比特币来源有两个，所以要指向前面两个块
值得注意的是，每个区块至少有两个哈希指针，一个指向前一个区块，另一个指向比特币的来源（可能有多个来源，那么有多个指针），可以说明该比特币并非凭空捏造，防止双花攻击
在A交易的过程中包含两个部分，输入部分和输出部分，输入部分包括币的来源以及A（付款人）的公钥，输出部分包括B（收款人）公钥的哈希和A的公钥
这样收款方B知道了付款方A的公钥，可以对付款方A的签名进行验证，同时，在转账过程中A所提供的公钥也要与铸币之后给出的A的公钥一致，防止有其他恶意结点伪造A的身份进行转账交易
在比特币系统中，通过执行脚本实现上述验证过程。将当前交易输入脚本与前一个交易输出脚本（说明币的来源的交易）拼接执行，如果可以正确执行，说明交易合法，这一过程将在脚本那一章节展开。
比特币共识协议：
账本内容要取得分布式的共识（distributed consensus）
女巫攻击：如果直接让用户投票，会让攻击者通过不断生成新账户导致占投票人数的大多数，但是由于比特币是通过算力进行投票，也就是PoW（工作量证明）来分发记账权，所以可以避免
分叉攻击：在同一区块之后回滚交易
四、实现
比特币采用的是基于交易的账本模式：
UTXO:Unspent Transaction Output，没有被花掉的交易的输出所组成的集合，全节点进行维护的数据结构
交易费：作为第二个激励机制，当记录别人的交易记录时，会产生交易手续费（total inputs与total outputs的差值）
比特币出块奖励减半的时间：每10分钟输出一个块，每输出21万个块，出块奖励减半，大约是4年时间
验证（Confirmation）：在交易后等待6个块，根据扩展最长链原则，新出的区块会出现在最长链上，以避免双花攻击
以太坊采用的是基于账户的账本模式：
显式的记录每个账户所拥有的货币数量
使用的是PoS机制作为以太坊的共识机制
在权益证明中，每个验证者必须锁定一定数量的加密货币作为抵押品，这些抵押品也被称为“股份”或“权益”。节点持有的加密货币数量越多，它们被选中的概率就越大。因此，持有更多加密货币的节点可以更容易地成为验证者。这种选择方式也被称为“股份抵押证明”
五、网络
应用层：BitCoin BlockChain
网络层：P2P Overlay Network
通过将交易集合发给所有相邻结点，也就是flooding（洪泛）
六、挖矿难度
difficulty = difficulty_1_target/target
difficulty_1_target 挖矿难度等于1的时候所对应的目标阈值
target 目标阈值
比特币的挖矿难度控制在每10分钟出1个区块，可以有效的防止分叉攻击，防止出现很多分叉，导致算力分散，使得恶意结点实现攻击更容易实现
比特币大约每两个周调整一次目标阈值:target = target actual time/*expected time