区块链技术与应用01 北大肖臻

课程简介

记录一下课程吧。。还是记录以下要好，否则看完了和没看似的。。。。尴尬。。。。。。Fighting！！！！！！

区块链不等于比特币。

参考资料

比特币教学大纲

以太坊教学大纲

BTC-密码学原理

比特币是加密货币(crypto-currency)。但是加密过程是公开的，如交易额度等。

BTC主要用到了密码学中的两个部分：哈希和数字签名。

哈希函数

1. collision resistance 哈希的抗碰撞性质。 x≠y,H(x)=H(y) 不存在。
2. hiding 哈希函数是单向的。X→H(X) 不可逆，X空间足够大且分布均匀。采用一个随机值 nonce，H(X||nonce)
3. puzzle friendly 事先并不知道计算出的哈希值是什么样子的，落在什么数值范围中。在挖矿中，找到一个nonce(block header中的一部分)，使得 H(blockheader)≤target ，这个性质说明了挖矿没有捷径，找到 nonce 的人付出了一定的工作量，这个挖矿过程可以作为工作量证明 (proof of work)。挖矿很难，验证很容易(difficult to solve,but easy to verify)。

注：1+2 实现了 digital commitment or digital equivalent of sealed envelope。

BTC所用哈希函数 SHA-256。

数字签名

比特币分发开户，就是自己产生一对公钥和私钥。

签名用私钥加密，验证签名用公钥。

注：生成公私钥对要用好的随机源。每次签名时也要用好的随机源。

BTC的数据结构

哈希指针 hash pointer。

普通指针存储结构体在内存中的地址，哈希指针存储地址和这个结构体的哈希值，可以找到位置和检查是否被篡改。

区块链和普通的链表的区别：哈希指针代替了普通的指针。

第一个区块，genesis block 创世区块

最后一个区块，most recent block

H() hash pointer 计算方法：前一个区块的全部内容计算哈希，包括上一个指针的hash pointer

tamper-evidence-log性质 保存最后一个hash值，可以知道前面任何一个哈希值有没有发生变化

Merkle tree。

Merkle tree 和 binary tree 的区别：哈希指针代替了普通的指针。

根节点哈希值 root hash

底部的每个数据块都是一个交易。

每个区块分为块头(block header)和块身(block body)，块头存放根哈希，没有具体的交易内容，块身有交易列表。

全节点和轻节点。全结点保存块头和块身，轻结点只保存块头。

轻节点想知道黄色的这块交易是否已经被包含在这个树里面？轻节点只保存块头，块头里只存放了根哈希值。全结点收到这个请求，把红色部分哈希值发给这个轻结点。轻结点可以在本地计算出绿色的哈希值，就可以算出整棵树的根哈希值，跟block header里的根哈希值比较就可以知道这个黄色交易是否在这棵树里。

过程叫做 proof of membership(inclusion) 时间复杂度:o(logn)

proof of non-membership 如果对树不进行处理的话，证明一个交易不包含在这棵树里，时间复杂度：o(n)。

如果对树底部交易的哈希值进行计算，从小到大的排序。叫做 sorted Merkle tree，那么时间复杂度：o(logn)。

只要没有循环，都可以用哈希指针替代普通指针。

BTC-协议

Double spending attack 双花攻击。

一个数字货币，用银行的私钥加密，人民用公钥解密，可以花钱。但是造成双花攻击。复制可以花多次。

解决办法：给每一个货币添加一个编号，央行建立一个数据库，记清货币的来源和去处。

比特币系统中每个交易都包含输入输出两个部分，输入部分说明币的来源和A的公钥，输出部分说明收款人的公钥的哈希。

A获得了发行10个比特币的能力，A要把比特币转给B和C，要说明B和C的公钥哈希。

两种哈希指针，一种是上节课的用来连接区块的哈希指针。另一种指向前面某个指针，用来说明币的来源的，证明钱是有记录的，防范双花攻击。

最后面B给F比特币的那个区块，看起来是合法的，但是追溯到来源时发现是已经花出去的，不是合法的交易，删除。

写进区块链之前要做两件事情：1.A要知道B的公钥。A要知道转账给谁？2.为了验证A的签名，所有结点都需要知道A的公钥。

对于第二个问题，怎么知道A的公钥？在转账的时候，A要说明自己的公钥。要是有人顶替?上一个结点（coinbase tx 铸币）要输出的A的公钥，这个公钥要和交易的自己说的公钥相对应才可以，这样证明了A的身份。BitCoin Script

每个区块包括块头和块身两个部分：

块头包括宏观的信息。块身是交易列表。前一个区块的哈希值只是计算块头的哈希值。

Full node,fully validating node 这节课主要讲全节点，轻节点没有参与区块链的构造和维护。

Light node 轻节点只是利用区块链的信息进行查询。

分布式共识。Distributed consensus

区块链是一个去中心化的账本，账本的内容要统一。也就是说，账本的内容要取得分布式共识。

一个简单的例子，分布式的哈希表。distributed hash table 。key-value pair。

不可能结论(impossibility result)。

FLP。在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。

CAP理论。Paxos理论。 不详细解释，和这节课关联不大。

Consensus in bitcoin。

投票机制,过半数票即同意。任何基于投票的方案首先要确定谁有投票权(membership)。不是谁都可以加入。

本地产生一个公私钥对，即为一个账户。恶意节点，用一台超级计算机产生各种各样的账户，产生的账户超过总数的一半，即可以控制投票的结果了。叫做女巫攻击(sybil attack)。

获得nonce的节点获得记账权并发布下一个区块。所谓记账权就是往比特币，即去中心化账本中，写入下一个区块的权力。

分叉攻击(forking attack) 通过往区块链中间插入一个区块来回滚某个已经发生了的交易。

最长合法链。接受的区块应该是在扩展最长合法链。

若同时获得nonce呢？区块链接受最早被接收的那个区块。哪条链先被延长，就谁有效。下面的就叫orphan block然后被抛弃

怎么判断是否接收一个区块？如果收到区块，往下继续扩展区块，就是认可这个区块。

激励机制(block reward)。

每21万个区块后激励减半。每个块奖励50个BTC。现在每个块奖励12.5个BTC。

靠算力投票(hash rate)。每秒钟尝试的nonce数目。

防范投票过程中的sybil attack 女巫攻击。创建的账户数多并不代表hash rate高。

BTC-实现

基于交易的账本模式(transaction-based ledger)

比特币的全节点维护一个UTXO(unspent transaction output)的数据结构,还没有被花掉的交易的输出组成的集合。

一个交易有多个输出。A的转账交易，给B转了5BTC，给C转了3BTC，B收到比特币花掉了，输出不在UTXO里面，C还没有花掉，输出在UTXO里面。

UTXO中的每个元素，要给出产生这个输出的交易的哈希值以及它在这个交易里是第几个输出，就可以定位到UTXO的输出。为了检测双花。想花的BTC在UTXO里面，可以花掉。否则，不可以。

total inputs=total outputs

如果只有出块奖励，如果结点比较自私，不管别人的交易，只打包自己的交易。所以设计了第二个激励机制——交易费(Transaction fee)。

1BTC 0.99BTC其中的0.01当做交易费给了那个结点

21万个区块，每十分钟生成一个，大约每4年，出块奖励就减少一半。以后交易费可能成为主要的激励。

基于账户的模式(account-based ledger)。以太坊，系统显式的记录账户上有多少币。类似于银行账户模式。

比特币基于交易的模式，隐私性比较好，但要说明币的来源。因为没有账户的概念。

具体例子。

这个区块包含686个交易，出块奖励大概是交易费的100倍，Height是区块的序号。Difficulty是挖矿的难度，每隔2016个区块要调整难度，保持出块时间在10分钟左右。Hash，这个区块块头的哈希值，Previous Block ,前一个区块块头的哈希值。凡是符合挖矿难度的哈希值，算出来都需要一长串的0。

nonce域只有32位，但是现在难度很大，即使尝试完 2^{32} 个nonce值也未必能挖到块，空间不够大。header中还有哪些域可以调整？

可以调整根哈希值。

CoinBase Transaction中 CoinBase域可以写入任何内容。

真正挖矿过程中有两层循环，外层循环调整CoinBase域的nonce，算出block header里面的根哈希值后，内层循环再调整header里面的nonce。

普通的转账交易，两个输入和两个输出。

注意：输入那里指明输入来自哪两个输出。输出那里Unspent表示还没有花掉，保存在UTXO里面。

输入和输出都是用脚本来制定的。把这个交易里的输入脚本和提供币的来源的上一个交易的输出脚本配对校验交易合法性。

存在问题的ppt，不需要对交易求哈希，实际上求哈希的时候只有block header，因为block header中有Merkle root hash，已经包含了所有的交易信息。

挖矿。

挖矿就是不断地尝试nonce，来求解puzzle，每次尝试叫做

Bernoulli trial：a random experiment with binary outcome。

Bernoulli process: a sequence of independent Bernoulli trials。

memoryless独立无记忆，以前的实验结果对目前的实验结果没有影响。

Bernoulli process 在每次实验时成功的概率很小，可以用泊松分布(Poisson process)来近似。

整个系统的出块时间(注：不是每个矿工的出块时间)服从指数分布(Exponential distribution)。

横轴是整个系统的平均出块时间，纵轴是概率密度。整个系统的平均出块时间为10分钟。

Progess free：将来还要挖多少时间跟过去已经挖多少时间是没有关系的。这样恰恰是挖矿公平性的保证，如果不这样的话，算力强的矿工会有不成比例的优势。

奖励。

比特币的数量构成一个几何序列。比特币总数：

Bitcoin is secured by mining.挖矿表明无意义，但是提供了凭借算力计票的有效手段，只要大部分算力掌握在诚实的节点手里，系统的安全性得到保证。

安全性

攻击者M强行把A的钱转给自己。

我们不能保证记账权不会落在恶意的结点上。攻击者M打算强行把A的钱转给自己，但是他没有A的签名是无效的，这样诚实的节点不认账，在上面进行挖矿。根据最长合法链原则，攻击者不但偷不到钱，还损失了出块奖励。

注意：检测恶意攻击的标准是诚实结点能否接受这个交易。扩展最长合法链。

攻击者把已经花出的币再花一遍。双花攻击。

注：矿工在挖矿前就要确定插在哪个位置。

花钱买东西，商家看到已经写到结点里了，发货了，然后攻击者又发起一个交易，把钱转给了自己，延长下面的链。这样使上面的交易作废，既收钱又收货。

攻击者这么做，概率是很低了，必须不断获得记账权。想要回滚操作，难度很大。防范方法就是多等几个区块，多等几个确认(confirmation)。比特币中缺省的是要等6个confirmation，才认为前面的交易是不可篡改的，大约1个小时。

区块链是不可篡改的账本(irrevocable ledger),这种不可篡改性只是概率上的保证，刚写进来的时候还是容易篡改的。但是随着确认的增多，不可篡改性呈指数级降低。

还有一种叫0个确认(zero confirmation)比较普遍使用，转账交易发布出去但是还没有被写入区块链里(也就是下一个区块还没有被挖出来)。

原因2个：

1.比特币协议节点接受最先听到的交易，先发布 M \rightarrow A,再发布 M\rightarrow M',大部分诚实的节点并不接受。

2.付款成功到发货存在天然的时间差。

发布的区块没有包含合法交易。

比特币协议规定每个区块大小有限定，最多不能超过1MB。如果交易数据太多了，有些交易只能等到下一个交易再记录。

保存具有多个记账权的区块不发布(selfish mining)。

首先，你不发布别人发布，就得不到出块奖励了。恶意结点需要占据很大的算力，如51%。

selfish mining不仅是为了分叉攻击，还为了减少竞争，大家还在挖上一个区块。他挖出两个了，上一个也被挖出了，他马上发布，减少竞争，但是存在风险。

BTC-网络

比特币协议运行在应用层，底层运行P2P Overlay 网络。比特币所有节点都是对等的，没有超级节点(super node)或主节点(master node)。想加入比特币网络，首先得知道一个种子节点(seed node)，和种子节点联系，种子节点会告诉我们其它节点的消息。节点之间通过TCP通信。离开不需要其它动作，其它节点经过一段时间没有你的消息，就会将你删掉。

比特币网络原则：简单，鲁棒而不是高效(simple,robust but efficient)。每个节点维护一个邻居节点的集合。消息传播采取 flooding 的方式，节点第一次听到消息时，把它传播给所有的邻居节点，同时记录这个消息我已经收到过了。邻居节点是随机地，不考虑底层拓扑结构，增强了鲁棒性，但是失去了效率。

每个节点都有一个等待上链的集合，节点第一次听到某个交易，把这个交易加入到等待上链的集合，再把它传播给所有的邻居节点。以后再收到这个消息就没有必要转发了，避免消息在网络上无限的传输下去。

转发的前提是合法的，签名的合法，之前比特币没有花过。

假设有两个有冲突的交易，差不多同时被广播到网络上。A \rightarrow B,A \rightarrow C 。根据交易在网络中位置的不同，有的节点先收到 A \rightarrow B 的交易，有的先收到 A \rightarrow C 的交易。

比如：有的节点先收到 A→B 的交易，再收到 A→C 的交易，就不会理会后一个交易。如果这个节点听到 A→C 或者 A→B 的交易写入了区块链，那么就要将 A→B 从自己的等待上链的集合中删除。

新发布的区块在网络上的传播方式和新发布的交易类似，每个节点除了检查区块的内容的合法性之外，还要检查它是否在最长合法链上，区块越大，传播越慢。

网络是best effort，一个交易发布到网络上，不一定所有的节点都收到，并且节点收到交易的顺序也是不一样的，网络存在延迟，有的节点也可能不按照协议转发，有的节点也会转发不该转发的交易。尽力而为。