区块链技术与应用.doc

北京大学肖臻老师《区块链技术与应用》公开课

第一节：绪论

第二节：密码学原理

crypto-currency
一、cryptographic hash function
性质;1 collision resistance(hash碰撞) 指H(x)=H(y)，而x≠y 对于哈希函数，哈希碰撞是常见的，但是要人为的制造哈希碰撞几乎是不可能的
例子：H(m)，m为message，如果m被人篡改，那么H(m)会发生改变。
ps:哈希弱碰撞目前是无法被数学证明的，但与此同时，我们还没有很好的办法人为制造哈希碰撞。
可是对于不同类型的哈希函数其安全性随着计算机科学和数学方法的进步，也是有可能被破解的，例如MD5
性质2 hiding 指哈希函数的计算不可逆，对于给定x可以计算H(x)，可是我们几乎不可能从H(x)反推出x.

digital mitment/digital equivalment of a sealed envelope 由于预测本身可能会影响结果，需要一种方法在预测结果不能提前公开的情况下，保证预测结果的真实性。

将预测x的哈希值公开，待到结果出现时再公开预测以检验预测与实际是否相符。

在实际操作中，也有将x和随机数一起做HASH以保证取值的分布足够离散。

比特币中的哈希函数所需性质：
性质3 puzzle friendly 指除了遍历以外，没有任何办法可以做出哈希碰撞，这样才可以作为挖矿证明，然而想验证一个人的挖矿证明却是非常快捷的，因为只需要计算一次哈希函数值就可以了。

比特币中所使用的哈希函数为：SHA256——Secure Hash Algorithm

二、数字签证
1.public key private key
asymmetric encryption algorithm 非对称加密算法

由于区块链系统是完全公开的，所以并不需要公私钥对进行保密通信，而是进行数字签名，以验证自己的身份，即私钥加密，公钥解密

对于256位的公私钥对，很难有两个账户拥有完全相同的公私钥对，所以很难通过产生公私钥对再比对的方法来冒名他人。

第三节 数据结构
一、 hash pointers

区块链(block chain)是最基本的数据结构，他和普通的链表的区别在于，使用hash pointers 取代了普通的指针
genesis block:创世纪块，指第一个区块
most recent block 指最后一个产生的区块
在区块链中，每一个block都含有一个Hash pointer 指向前一个块，而最后一个块的指针就保存在系统中！
Hash pointer的值是前一个块的所有数据的hash函数的取值！
所以无论区块链中的哪一个块发生了改变，都会导致之后所有的Hash全部改变，因此只需要检验最后一个Hash，即系统中的Hash来检验区块链中数据是否被修改。在实际操作过程当中，也不需要将整条区块链完整的保存下来，而只需要将最后的若干长度的区块链缓存下来，实时更新，进行验证。

二、 Merkle tree

Merkle tree是另外一种给基本的数据类型，他与普通的树的区别在于，使用Hash pointers取代了普通的指针

Merkle tree的指针从叶节点指向根节点，将左(右)节点的Hash值保存在当前节点的左(右)Hash指针，最后将根节点的Hash值保存在系统中！

对于Merkle tree而言，其最原本的数据是保存在整棵树的叶节点上的，而根茎部分都是保存了上一级的哈希值。

Merkle proof: 全节点保存了交易的全部信息，而轻节点只保存block header，为了向轻节点证明一个新的交易已经被写入Merkle tree了！那么需要在树中找到这个交易叶子，并且从叶子出发回到根节点，在这个过程中，轻节点所在的本地主机需要不断计算出当前节点的Hash值，如果沿途的Hash值正确，那么交易正常√。这样一条路径就是Merkle proof

如果对交易按时间顺序进行排序，然后布置成Merkle tree(sorted Merkle tree)，那么就可以用一种简单的方法证明非法交易并不存在于区块链中

ps:Hash指针必须要先确立一个节点的值，才能去计算与之相关的区块的值，因此这个类型的指针是不可以应用在环形数据结构当中的。

第四节 协议
带权力中心的数字货币需要一个权力中心，权力中心发行货币的公钥公开，用私钥加密数字货币，这样每个人都可以用公钥验证货币来自于权力中心。但是数字货币的本质是文件，如果用户大量复制数字货币，每个货币都拥有被权力中心认可的数字签名，这样就可以用伪造的数字货币进行交易，也叫做double spending attack(双花交易)

处理方法：在数字货币上再额外添加唯一编号，这样就可以区别每一张货币，防范双花交易，但是这种方法必须由中央权力机构来维护一个数据库来实时存储货币编号和持有人信息，即每一笔数字交易都必须由中心权力机构确认合法性。

在去数据中心的数字货币系统中，需要使用区块链技术来避免双花交易。

1. 铸币
铸币交易是每个用户都拥有的权力，即铸币权，可以记作：→A(10)
2. 转账
由某个用户交易个某组用户货币的行为，可以记作:A→B(5),A→C(5)

此时区块链中有两种哈希指针1).链接交易的指针；2).说明货币来源的指针

转账行为需要：转账方的签名；收账人的地址
在验证交易合法性的时候，需要上一笔交易的输出和下一笔交易的输入合起来来测试能否正常运行——BitCoin Script

区块链的组成：
1. Block header
version
hash of previous block header 只算前一个区块的块头
Merkle root hash
target
nonce
2. Block body
transaction list(交易列表)

节点的分类
1. full mode 全节点，也叫做 fully validating node
2. light node 只保存block header，因此轻节点不能独立做验证。

distributed consensus 分布式共识，即共享账本可以被所有用户承认
FLP impossibility result：在一个异步的系统中，即使只有一个成员出错，那么也不可能取得分布式共识。

CAP Theorem(C: consistency一致性 ,A: Availability可用性 ,P: Partition tolerance 容错性)CAP三条性质只能同时满足两条

我们需要找到这样一个nonce使得H(block header)≤target成立，这样该账户才能拥有往区块链中写入交易的权力。

分叉攻击：通过往区块链中间插入合法交易来进行回滚，因此区块链应当只接受能延拓最长合法链的交易

coinbase transaction 是唯一铸币的方法。每产生一个新的交易，那么拥有投票权的账户可以拥有block reward，即使用coinbase transaction去铸造bitcoin。协议中规定初始铸造数量为50BTC，但是每当区块链延长21W，铸造数量减半，目前block reward为12.5BTC.

只有通过计算求解nonce才能获得记账权，获得记账权就能得到block reward，利用coinbase transaction铸造新的货币。
因为区块链的特殊性质，计算nonce是没有任何捷径的。
因此寻找nonce的过程就被称作挖矿，获得记账权的节点就被称为矿工

第五节 实现
Block chain是一个去中心化的共享账本
以Bitcoin为例，Bitcoin是一个基于交易的账本模式 transaction-based ledger
UTXO: Unspent Transaction Output 未被花掉的交易的集合
通过查询UTXO来确认新的交易中使用的货币是否在UTXO中，若在，则合法，否则不合法。因此全节点内存中需要频繁使用UTXO来确认交易的合法性。
交易会不断的更新UTXO。
UTXO中被交易使用掉的货币=UTXO中因交易产生的未使用的货币。
total inputs= total outputs

transaction fee交易费
交易费的金额较小，但是随着减半效应的存在，最终会转变成以transaction fee为主体的挖矿行为。

以太坊是一个基于账户的账本模式 account-based leger