北大肖臻《区块链技术与应用》学习笔记

$$区块链学习笔记$$
这是关于北京大学肖臻老师的《区块链技术与应用》课程的学习笔记。

BTC的数据结构

hash pointers：既保存结构体的对应地址位置（指针），又保存结构体对应映射的hash值（hash）。
区块链：本质就是一个一个区块组成的链表。
Block chain is a linked list using hash pointers.

后区块的hash pointer存放的是前区块的地址以及hash值。
对于一个区块的hash是连同这个块中所有的内容来取hash值的。
tamper-evident log：因为区块链中后区块存放着指向前一个区块的指针，如果其中的一个区块发生了变化，那么后续的区块指针都会变化，最终导致最后一个区块的hash pointer发生变化，从而可以侦测数据的变化以及变化的位置。

Merkel tree：相对于binary tree来讲，使用了哈希指针来代替了普通的指针。

树顶的块拥有的是根哈希值（对于根节点取hash 的哈希值）

对于Merkel树上任何一个节点的修改，都能通过根hash值来进行检索。

block header：存放hash值，但是不保存交易的具体信息。
block body：保存交易的具体信息。
Merkel proof：

树中最低层的交易（叶子节点），双亲节点中存储的hash值组合，然后逐级向上寻找节点，最后找到根节点，然后比较接收的Merkel proof中存储的信息与最终找到的信息是否一致，如果一致就说明这个交易就是发生在这个区块中。
collision resistance
proof of membership：O(logn)复杂度
proof of non-membership：O(n)复杂度
sorted Merkel tree：排序方便查询节点。

小细节：

对于普通的指针，上述结构是成立的，但是对于哈希指针就不成立，因为hash指针中的hash要根据指向的块的信息来确定，从而使得上述结构出现循环依赖。

BTC的协议

数字货币与纸质货币最大的区别：唯一性
double spending attack：双花攻击
数字货币要解决的中心问题：（去中心化）
①. 数字货币的发行问题
②. 如何验证交易的正确性（防范双花攻击）
$$中心化系统\stackrel{去中心化职能分担}{\to }区块链$$
小型区块链结构示意图：

私钥签名，公钥验证
输入部分：A的公钥与币的来源
输出部分：收款人公钥的hash
币的来源：证明交易的合法性与防范双花攻击。
交易双方信息互通：A需要知道B的地址，以此来对B进行转账交易。B以及其他所有的节点都需要知道A的公钥，来对这笔交易进行验证。
容易混淆的一点：A向B交易，加密的时候使用B公开的公钥进行加密，然后B接收到交易之后再B自己的私钥进行解密。

Block header

一般包含区块链比较宏观的信息
version：协议版本信息
hash of previous block header：前一个区块的hash值
Merkel root hash：
target：
nonce

Block body

transaction list：交易列表
full node：全节点，保存着区块链中所有的信息，也用于交易的合法性验证。
light node：只是保存当前block的相关信息，无法进行交易合法性查验。

distributed consensus 分布式共识

distributed hash table：分布式哈希表
FLP impossibility result：如果整个异步系统没有通信速率的上限，那么即使系统中仅有一个成员处于fault状态，那么整个系统中也不能存在共识。
CAP Theorem：下面的三个性质在一个分布式系统中最多只能满足两个条件，不能同时满足三个。
C：consistency
A：availability
P：partition
Paxos：分布式系统中如果系统到达了共识，那么这个共识必然是唯一的（但是该协议可能会导致整个系统无法达成共识）。

Consensus in BitCoin 比特币中的共识协议

（假设多数成员是好的）
基于投票的解决方案：关键是投票人员的投票权问题。
sybil attack：使用性能强大的计算机来注册大量用户，从而操作系统中的投票结果。

区块链中记账权的分配：
$$H(blockheader)<=target$$
保证块头信息的hash处于目标阈值内，就视为能够分配记账权。

最长合法链

比特币中新增的区块应当连接至最长合法链之后。
上述图中的新增分支是一种分叉攻击（forking attack），试图回滚已经发生了的交易。
当一个区块节点后接节点发生分叉的时候，就会出现如下的情况：

这种情况会保持一段时间，直到下一个区块进行链接的时候：

假设下一个区块连接到了上方的区块，此时上方的链就变成了当前的最长合法链，下方分叉处单独的区块自然就是非法的了。

block reward 出块奖励

coinbase transaction：比特币数量增加的唯一来源。
$$50BTC\to 25BTC\to 12.5BTC$$
随着时间的推移，挖掘一个区块获得的比特币数量，开始减少，但是单位比特币所相当的价值逐渐飞跃。

此图中下方的块就已经是无效块了，那么他其中所保存的BTC也就无效了，因为BTC交易的时候会查询的是区块链中最长合法链中BTC数据（上面一条链）。

❗❗比特币的共识机制本质是算力投票。
比特币中要取得的共识是去中心化账本中的数据，但是只有系统中具有记账权的区块才能够获得数据，所以大家需要获得记账权力。记账权力的分配就是通过：
$$H(blockheader)<=target$$
解决这个问题，使得结果在阈值内来获得的。
但是上述这个问题根据puzzle friendly特性，必然是需要通过大量数据验证（没有捷径）来进行操作的，所以从根上面来讲计算速度越高，获得记账权的概率就越大。这就是比特币共识机制是算力主导的本质。
比特币争夺记账权的过程就是挖矿（mining）。
争夺记账权的节点成为矿工（miner）。