# 北大肖臻老师《区块链技术与应用》公开课学习 1
# 区块链
20 世纪经济学家 哈耶克 认为：欧美通货膨胀的根源在于货币是政府发行的，是中心化的，注定会为了铸币税而滥发。比特币是一种虚拟货币，它是为了解决哈耶克提出来的中心化货币必然会超发贬值的问题，而被创造出来的去中心化货币。
货币交易的过程中怎么确保记账不出错，不被篡改？
古代文明使用实体物质特别是贵金属。（无法凭空创造物质，元宝给了你我就没了） 近代国家进入纸币时代。（特殊印版、纸张、油墨，使得复制纸币变为不可能） 移动互联网时代使用的是网上支付。（第三方中介银行进行信用担保、密码系统）
那么比特币是怎么记账的呢？
牺牲隐私，每个账户的出账和入账都广播出来，整个记账过程让全网的人都看到，组成一条区块链。
那么怎么保证区块链上的之前的信息没有被篡改呢？
这就利用到了下面讲到的密码学原理。
# 密码学原理
比特币被称为加密货币 cryptocurrency。但其实区块链上内容都是公开的，包括区块的地址，转账的金额。
比特币主要用到了密码学中的两个功能: 1.哈希 2.签名
密码学中用到的哈希函数被称为 cryptographic hash function, 它有两个重要的性质:
collision resistance(抗碰撞性): 例如x≠y H(x)=H(y)两个不同的输入，输出却是相等的，这就称哈希碰撞 (opens new window)。它是不可避免的，因为输入空间总大于输出空间。哈希碰撞中，给出x，很难找到y，除非蛮力求解(brute-force)。难以发现碰撞的性质称为collision resistance- 作用：检测上传到云端的文件是否被更改，上传文件前先求该文件的hash值，过段时间下载该文件后，再求一次hash值，比较两值是否相等即可知道文件是否被篡改。
- 人工制造碰撞：我国著名密码学家王小云教授在 2004 年就找到算法，人工制造了哈希函数 MD5 的哈希碰撞，使得 MD5函数 安全性收到了冲击。如果无法人工制造哈希碰撞，那么坏人就只能用
brute-force蛮力穷举，这种工作量就巨大到不可能了。
hiding: 哈希函数的计算过程是单向的，不可逆的。例如从H(x)无法推导出x,hiding性质前提是输入空间足够大(不然很容易遍历完)，分布比较均匀(hash 结果不能只是某几个值)。如果输入不是足够大，一般在x后面拼接一个随机数，如x123213124，整体取哈希值。- 作用：和
collision resistance结合在一起，用来实现digital commitment(又称为digital equivalent of a sealed envelope)。把预测结果作为输入x，算出一个哈希值，将哈希值公布，hiding让人们知道哈希值而不知道预测值，最后再将x公布，因为有collision resistance的性质，预测结果是不可篡改的。
- 作用：和
puzzle friendly: 所谓puzzle friendly，意思是对于哈希函数，他的输出是无法预测的，要找到特定区间内的哈希值的输入x，没有捷径。 比如，我要找到SHA256函数（比特币中用的 hash 函数: Secure Hash algorithm）的哈希值，前60位都是零，我除了一个一个试验以外，没有其他的方法。 （挖矿很难，验证很容易）
关于签名，首先要介绍比特币中的账户管理，开户方式: 只需要创建一对公私钥即可（非对称加密），公钥是公开的，私钥是私密的。
那么每个人都有公私钥，可不可以不断生成公私钥，与区块链上已存在的公钥进行对比，如果相同，则用对应的私钥去攻击他。答案是不可能，因为概率微乎其微，但是前提是生成公私钥的时候要有好的随机源。
比特币的本质就是数字签名，对于一笔交易，要用发起人的私钥进行签名，大家可以用发起人的公钥对这笔交易进行验证。
关于非对称加密算法，比较常见的是椭圆曲线加密算法。简单可以理解为经过一条椭圆曲线，可以生成两个值 K 和 Q，对一个数 123 用 K 进行加密会生成毫无规律的数，再对其用 Q 进行解密，就又恢复成了 123。K 可以作为私钥，Q 可以作为公钥。
# 数据结构
# Hash Pointer（哈希指针）
在比特币中，其最基本的数据结构便是一个个区块形成的区块链。区块链与链表的区别就是用哈希指针代替了普通指针。 一般的链表我们都可以改造为使用哈希指针的链表，但当链表中存在环时，哈希指针便不能再使用。
对于链表中的节点，对链表中的内容做一次哈希运算，记 H() 为该节点的哈希值，该值与节点中内容有关。当节点（区块）中内容发生改变，该哈希值也会发生改变，从而保证了区块内容不能被篡改。
如图中所示，如果我们想要破坏区块链完整性。篡改B的内容，而C中保存有B的哈希值，所以C也得进行修改。而同样C后区块也得修改。而用户只需要记住最后一个区块链的哈希地址，就可以检测区块链上内容是否被篡改。 在实际应用中，一整条链可能会被切断分开保存在多个地方。若用户仅仅具有其中一段，当用到前面部分区块数据时，直接问系统中其他节点要即可，当要到之后，仅仅通过计算要到的最后一个哈希值和自己保存哈希值是否一致可以判断所给内容是否确实为区块链上真实的内容。
# Merkle Tree（默克尔树）
Merkle Tree 与 Binary Tree 的区别就是用哈希指针代替了普通指针。
上图即为一个简单的Merkle Tree，其中Tx0、Tx1、Tx2、Tx3为数据块，代表每一次交易。Tx0、Tx1各有一个哈希值，将其合并放在一个节点中，Tx2、Tx3同样操作，而后，针对得到的两个节点Hash01、Hash23分别取哈希，又可以得到两个新的哈希值，即为图中根节点。实际中，在区块块头中存储的是根节点的哈希值（对其再取一次哈希）
该数据结构的优点在于：只需要记住 Root Hash（根哈希值），便可以检测出对树中任何部位的修改。不论在哪里篡改了，都会通过哈希值向上反应，最终反馈到 Root Hash 值上。
在比特币系统中，不同区块通过哈希值指针连接，在同一个区块中的多个交易（数据块），则通过
Merkle Tree的形式组织在一起。区块本身分为两部分（块头和块身），在块头中存在有根哈希值（没有交易的具体信息），块身中存在交易列表。
# 轻节点与全节点(light node and full node)
全节点保存整个区块的所有内容，而轻节点仅仅保存区块的块头信息。 为什么要分轻节点和全节点？ 因为硬件的局限。一个区块大小为1MB，对于移动便携设备来说，如果存储区块的所有内容，则所需空间过大，而这是不现实的。所以轻节点只需要存储区块块头信息，全节点存储区块所有内容。
当需要向轻节点证明某条交易是否被写入区块链，便需要用到 Merkle proof。我们将交易到根节点这一条路径称为 Merkle proof，全节点将整个 Merkle tree 的信息发送给轻节点，轻节点即可根据其算出根哈希值，和自己保存的对比，从而验证该交易是否被写入区块链。只要沿着该路径，计算出来的根哈希值正确，说明内容没有被修改过。
那么全节点是否可以修改 Hash 值，向轻节点发送修改后的 Hash 值使得向上一层计算的 Hash 值仍然正确呢？
实际上，这种情况为人为制造哈希碰撞。由于哈希函数的
collision resistance性质，这种情况是不会发生的，保证了系统的不可篡改性。同时，这样一个Merkle Proof的事件复杂度为O(log n), 非常高效【证明交易存在】。如果要证明交易不存在，如果不对叶节点规定排序顺序，没有一个效率较高的方法证明不存在。在比特币系统中，没有相应的需求，所以在比特币系统中并没有对Merkle Tree进行排序。
# 协议
# 数字货币的问题
假设权威机构——中央银行发行数字货币，发行了数字货币，用央行的私钥签名，然后使用的时候，用户直接拿央行的公钥验证签名（假设大家都知道公钥）。
虽然签名保证了没办法篡改其中的内容，但是数字货币本质上还是一个文件，这样的数字货币可复制，就会造成双花攻击（double spending attack）。不像是纸质货币，花出去手上就没有。
# 中心化
为解决这个问题，央行还要维护一个数据库，即记录每个编号的数字货币是归哪个用户所有。
在支付时，不仅要用公钥验证签名是央行签署的，还要通过央行验证该货币是归自己所有，央行再将货币所有者改成支付给的那个用户。不仅数字货币的发行是由央行统一控制，而且每次交易都要由央行确认其合法性，这种方案是一个中心化的方案。
# 去中心化
将央行的职能改成由广大的用户来共同承担，也就是去中心化的方案，这是BTC等数字货币系统要解决的问题，即：
1️⃣ 怎么决定数字货币的发行及发行量 2️⃣ 怎么验证交易的合法性，防止双花攻击 第一个问题在 BTC 系统中是挖矿决定的 第二个问题的解决，要维护一个数据结构，由所有用户来共同维护，这个数据结构就是区块链。
假设用户 A 获得了铸币权，他发行了 10 个 BTC。然后他将这 10 个 BTC 转给 B 和 C，每个人分 5 个 BTC。接下来 B 给 C 2 个货币，给 D 3 个货币。最后 C 将所得的 7 个货币全部给 E。
红色箭头会说明【币的来源】，这也就防止了双花攻击，如过 B 已经将自己的 5个BTC 花掉了，假设 B 尝试再花一次，将 5个BTC 转给F。这时顺着区块链去检查这个区块到来源交易之间的区块，发现 B 已经花了来源区块的BTC，说明这新个交易是不合法的，也就不会接受这个转给F的区块进入区块链。
以 A 向 B 转账为例：
- B的公钥: A 向 B 转账，A 需要知道 B 的地址。因为 BTC 系统中的收款地址就是收款人的公钥取哈希再经过一些转换得到的。BTC系统也没有提供查询某用户的公钥或账户地址的功能，要向 B 转账，就需要 B 提供公钥或账户地址。这种情况 B 可以把公钥公布在网站上。（虽然公钥可以公开，但实际中更多公开的是公钥的哈希）
- A的公钥: A 向 B 转账，B 也需要知道 A 的公钥。因为一方面 A 的公钥代表 A 的身份，B 要知道转账的是谁，另一方面是为了验证 BTC 交易中 A 的签名（私钥签名公钥验证），也就是说所有结点都需要知道 A 的公钥才行，每个结点都需要独立验证，即使是一个和交易无关的旁观者也要验证这笔交易的合法性。
- 如何知道 A 的公钥: A 的公钥是 A 自己写在这笔交易的输入部分里，即在交易中付款方自己宣称的。实际中 A 转账时候提供的公钥需要和铸币交易中公钥对的上，这样就防止了恶意节点伪造 A 的公钥来“偷”走 A 的比特币。
- 在比特币系统中，通过执行脚本实现上述验证过程。将当前交易输入脚本与前一个交易输出脚本（说明币的来源的交易）拼接执行，如果可以正确执行，说明交易合法。
# 区块结构
全结点（fully validating node）是有块身的，需要验证所有交易的合法性；轻结点（light node）是没有块身的，没有办法独立验证交易的合法性。轻结点没有参与区块链的构造和维护，只是利用了区块链中的部分信息。系统中大部分结点是轻结点，全结点不是很多。下面主要是对全结点进行说明。
- 块头（block header）: 块头里保存的是区块的宏观的信息。
- version: 用的是BTC的哪个版本的协议
- 指向前一个区块块头的哈希指针
- Merkle root hash: 整棵 Merkle Tree 的根哈希值
- target: 挖矿的难度目标阈值target
- nonce: 挖矿用的随机数nonce，要使得
H(blockheader) ≤ target
- 块身（block body）
- 交易列表
# 共识协议
每个账户都可以发布交易，区块链可以看做去中心化的账本，那么发布的交易应该写在哪个区块里呢？交易广播给每个区块，每个人都在自己本地的区块链上写入交易，如何保证写入后的一致性？也就是说账本的内容要取得分布式的共识（distributed consensus）。
- FLP impossibility result: 讲的是在一个异步的系统（asynchronous system）中，网络传输的时延没有上限，即使只有一个成员是有问题（faulty）的，也不可能取得共识。
- CAP Theorem: CAP 是分布式系统想要的三个性质，Consistency 一致性、Availability 可用性、Partition tolerance 分区容忍性。而
CAP Theorem是说任何一个分布式系统中，CAP 三个性质最多只能满足其中两个，不可能三个全满足。 - 分布式共识中协议 Paxos 可以保证Consistency（若达成共识必然一致），但在某些情况下，可能会一直无法达成共识。
# 比特币共识协议
背景：假设系统中存在部分节点有恶意，但存在比例较小。大多数节点为“好”的节点，在这种情况下进行共识协议设置。 想法1：直接投票 某个节点打包交易到区块，将其发给其他节点，其他节点检查该候选区块，检查若正确投赞成票，若票数过半数，加入区块链。 存在的问题1——恶意节点不断打包不合法区块，导致一直无法达成共识，时间全花费在投票上。 存在的问题2——无强迫投票手段，某些节点不投票（行政不作为）。 存在的问题3——网络延迟事先未知，投票需要等多久？效率上会产生问题。 更大的一个问题——membership。如果是联盟链，对加入成员有要求，可以基于投票。但比特币系统，任何人都可以加入，且创建账户及其简单，只需要本地产生公私钥对即可。只有转账（交易）时候,比特币系统才能知道该账户的存在。这样，黑客可以使用计算机专门生成大量公私钥对，当其产生大量公私钥对超过系统中一半数目，就可以获得支配地位（女巫攻击 sybil attack）。所以，这种简单的投票方案也是不可行的。
比特币系统中采用了很巧妙的方案解决这个问题。虽然仍然是投票，但并非简单的根据账户数目，而是依据计算力进行投票。
在比特币系统中，每个节点都可以自行组装一个候选区块，而后，尝试各种 nonce 值（4 bytes），这就是挖矿。H(block header)<=target。当某个节点找到符合要求的 nonce，便获得了记账权，从而可以将区块发布到系统中。其他节点受到区块后，验证区块合法性，如果系统中绝大多数节点验证通过，则接收该区块为最新的区块并加入到区块链中。
验证合法性如检查
target的编码nBits域设置的是不是符合 BTC 协议规定的难度要求、检查带nonce的块头哈希值是不是小于target、检查块身中的每个交易是否都有合法的签名、检查每个交易都没有双花等
候选区块合法了就要去接收吗？
分叉攻击：A用户对上面的A转账给B的记录回滚，从而非法获取利益。但是在两条链上，发现交易都合法，但是转账给A'不应当被接受。这是一个典型的双花攻击。A给B转账后，用分叉攻击将钱又转回来，覆盖掉原来的记录。 在比特币系统中，这种情况实际上很难发生。因为大多数矿工认可的是最长的合法链，会沿着上面的链继续挖下去。而A这个攻击者要想回退记录，就必须使得下面的链变得比上面的链还长。理论上来说，攻击者需要达到整个系统中51%的计算力，才能使得这种攻击成功。
此外，区块链正常运行场景下，也可能会发生分叉。当两个节点同时获得记账权时，会有两个等长的合法链。在缺省情况下，节点接收最先听到的区块，该节点会沿着该区块继续延续。但随着时间延续，必然有一个链胜出，由此保证了区块链的一致性。（被扔掉的区块称为“孤儿区块”）
# 比特币的激励机制
让大家去竞争记账权的动力是什么？需要提供算力和电力成本，节点为什么要去做？获得记账权的结点本身有一定的权力，如可以决定哪些交易被写入下一个区块中，但这不应当成为竞争记账权的主要动力，因为 BTC 系统设计来希望所有交易都能被公平写入账本。出块奖励机制解决了这个问题。
BTC协议中规定，获得记账权的结点，在发布的区块里可以有一个特殊的交易——铸币交易，在这个交易中可以发布一定数量的BTC，这是发行BTC（产生新的BTC）的唯一方法，不必指定币的来源。这也就解决了前面谈及的去中心化系统中的第一个问题——谁来发行 BTC 和发行多少 BTC。
BTC刚出现时，出块奖励是 50 个BTC，BTC协议规定每
21万个区块之后，出块奖励就要减半，也就变成25个BTC。如今的情况是每个区块中能产生12.5个BTC。
为什么形容取得记账权的过程为挖矿（mining）？
矿的数量有限，BTC总量有限。 挖矿的过程很难，挖到矿的回报很大，BTC取得记账权来获得出块奖励也是一样。 争夺记账权的结点称为矿工。