课程介绍
北京大学公开课《区块链技术与应用》由肖臻老师讲授,主要讲解区块链的基本概念和实现原理，面向广大对区块链技术和应用感兴趣的同学。通过这门课的学习，能够掌握比特币、以太坊等区块链技术的设计思路并有效解决实际问题。了解更多北京大学区块链课程的信息， 获取课程相关资料请拜候肖臻老师的homepage：http://zhenxiao.com/
北京大学肖臻老师《区块链技术与应用》公开课
第一节：绪论
第二节：密码学原理
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 commitment/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
