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

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）。

BTC的基本实现

transaction-based ledger：基于交易的机制。
UTXO：Unspent Transaction Output 未花费交易输出
$$TotalInputs=TotalOutputs$$
输入 大于 输出（中间的交易费）
transaction fee：交易费
随着时间推移，一个区块中“挖掘”出来的BTC价值变小，是有可能使得一次交易中的交易费大于交易金额的。

挖矿过程的概率分析

Bernoulli trial：a random experiment with binary outcome 单次随机的（等概率）并且仅有两种结果的实验。
Bernoulli process：a sequence of independent Bernoulli trials 一组无关联的伯努利实验组合
memoryless：无记忆性，每次实验都是独立的，当次实验结果不会影响下次实验的结果。

如果实验的次数比较多，并且实验成功的结果比较小，那么伯努利实验可以通过泊松实验来进行近似。Poisson process

上图中数轴代表的是概率密度，横轴代表出块时间，类似指数分布。
每次出块的概率都是相同的，与之前的实验没有任何的关系。（progress free：这个性质保证了挖矿的公平性）挖矿的时候就只是存在单次算力的差距，而不存在出块概率的差距。

geometric series BTC的数量

$$21万\times 50+21万\times 25+21万\times 12.5+...=21万\ast (1+\frac{1}{2}+\frac{1}{4}....)(几何级数)=2100万$$
对的，整个系统中BTC的数量是确定的，包括已经挖出和未被挖出的，总量就是2100万。
Bitcon is secured by mining.
挖矿的背后就是算力的比拼，只要系统中多数的节点正常运行争夺记账权，那么整个系统的安全性就不会发生重大问题（共识机制），所以单说挖矿只是纯粹的算力，但是对于BTC系统来讲挖矿能够保证系统的安全性。

恶意节点掌握记账权的情况

分叉攻击

此时两个链都是登场的合法链

$M\to A$是M向着A进行转账，$M\to M‘$是M向着自己进行转账，设定一个背景，当M从A购买东西的时候，M向A转账，A将物品交易给M，整个过程写入到了$M\to A$，并且加入到链中，表示当前的交易已经进行了记录。
但是如果M向着自己发起转账，并且算力够强的情况下额外增加节点，将下面强行变成当前系统中的最长合法链，那么后续读取记录的时候$M\to A$此纪录相当于没发生，M既获得了物品，又通过回滚的方式获得了货币。

解决方法
通俗一点来讲就是多等几个confirmation，使得上面的链一定是最长合法链的时候才会视为当前的交易是完成的不可篡改的交易。

上图中等待了后续六个节点才看作$M\to A$这个交易的完成，这样再次发生分叉攻击变换最长合法链的时候就变得非常的困难。
irrevocable ledger：不可篡改性
区块链是一个不可篡改的分布式账本，此处的不可篡改是在概率方面进行说明的，新加入的节点相对来说是比较容易篡改的，但是旧节点相对于新节点来说，篡改难度是指数倍数的增加，所以是“不可篡改”的。
zero confirmation：表面是区块链无需后续多个confirmation，实际上交易中已经保证了后续有了等待的时间。

selfish mining（挖出而不发）

在具有强大算力的支撑之下，如果已经挖出了几个块，但是不将这些块进行上链，等待好的时机的时候将所有的块都上链，这样也能操作最长合法链的判定。

当其他用户挖取上方的块时，如果有用户已经挖取了多个块，并且发出，那么不但上方的用户做了半天的无用功（进度全部作废），下方的用户能够一次性获取多个块的奖励（selfish）。