北京大學(xué)公開課《區(qū)塊鏈技術(shù)與應(yīng)用》由肖臻老師講授,主要講解區(qū)塊鏈的基本概念和實(shí)現(xiàn)原理，面向廣大對(duì)區(qū)塊鏈技術(shù)和應(yīng)用感興趣的同學(xué)。通過(guò)這門課的學(xué)習(xí)，能夠掌握比特幣、以太坊等區(qū)塊鏈技術(shù)的設(shè)計(jì)思路并有效解決實(shí)際問題。了解更多北京大學(xué)區(qū)塊鏈課程的信息， 獲取課程相關(guān)資料請(qǐng)?jiān)L問肖臻老師的homepage：http://zhenxiao.com/
北京大學(xué)肖臻老師《區(qū)塊鏈技術(shù)與應(yīng)用》公開課
第一節(jié)：緒論
第二節(jié)：密碼學(xué)原理
crypto-currency
一、 cryptographic hash function
性質(zhì) ;1 collision resistance(hash
碰撞 ) 指 H(x)=H(y) ，而 x≠y 對(duì)于哈希函數(shù)，哈希碰撞是
常見的，但是要人為的制造哈希碰撞幾乎是不可能的
例子： H(m) ，m 為 message ，如果 m 被人篡改，那么
H(m) 會(huì)發(fā)生改變。
ps: 哈希弱碰撞目前是無(wú)法被數(shù)學(xué)證明的，但與此同時(shí)，我們還沒有很好的辦法人為制造哈希碰撞。
可是對(duì)于不同類型的哈希函數(shù)其安全性隨著計(jì)算機(jī)科學(xué)和數(shù)學(xué)方法的進(jìn)步，
也是有可能被破
解的，例如 MD5
性質(zhì) 2 hiding 指哈希函數(shù)的計(jì)算不可逆，對(duì)于給定
x 可以計(jì)算 H(x) ，可是我們幾乎不可能
從 H(x) 反推出 x.
digital commitment/digital equivalment of a sealed envelope
由于預(yù)測(cè)本身可能會(huì)影響結(jié)
果，需要一種方法在預(yù)測(cè)結(jié)果不能提前公開的情況下，保證預(yù)測(cè)結(jié)果的真實(shí)性。
將預(yù)測(cè) x 的哈希值公開，待到結(jié)果出現(xiàn)時(shí)再公開預(yù)測(cè)以檢驗(yàn)預(yù)測(cè)與實(shí)際是否相符。在實(shí)際操作中，也有將
x 和隨機(jī)數(shù)一起做
HASH 以保證取值的分布足夠離散。
比特幣中的哈希函數(shù)所需性質(zhì)：
性質(zhì) 3 puzzle friendly
指除了遍歷以外， 沒有任何辦法可以做出哈希碰撞，
這樣才可以作為
挖礦證明， 然而想驗(yàn)證一個(gè)人的挖礦證明卻是非常快捷的，
因?yàn)橹恍枰?jì)算一次哈希函數(shù)值
就可以了。
比特幣中所使用的哈希函數(shù)為：
SHA256 —— Secure Hash Algorithm
二、數(shù)字簽證
1.public key private key
asymmetric encryption algorithm
非對(duì)稱加密算法
由于區(qū)塊鏈系統(tǒng)是完全公開的，所以并不需要公私鑰對(duì)進(jìn)行保密通信，而是進(jìn)行數(shù)字簽名，
以驗(yàn)證自己的身份，即私鑰加密，公鑰解密
對(duì)于 256 位的公私鑰對(duì)，很難有兩個(gè)賬戶擁有完全相同的公私鑰對(duì)，所以很難通過(guò)產(chǎn)生公
私鑰對(duì)再比對(duì)的方法來(lái)冒名他人。
第三節(jié) 數(shù)據(jù)結(jié)構(gòu)一、
hash pointers
區(qū)塊鏈 (block chain) 是最基本的數(shù)據(jù)結(jié)構(gòu)，
他和普通的鏈表的區(qū)別在于，
使用 hash pointers
取代了普通的指針
genesis block: 創(chuàng)世紀(jì)塊，指第一個(gè)區(qū)塊
most recent block
指最后一個(gè)產(chǎn)生的區(qū)塊
在區(qū)塊鏈中，每一個(gè)
block 都含有一個(gè) Hash pointer 指向前一個(gè)塊，而最后一個(gè)塊的指針
就保存在系統(tǒng)中！
Hash pointer 的值是前一個(gè)塊的所有數(shù)據(jù)的
hash 函數(shù)的取值！
所以無(wú)論區(qū)塊鏈中的哪一個(gè)塊發(fā)生了改變，
都會(huì)導(dǎo)致之后所有的
Hash 全部改變， 因此只需
要檢驗(yàn)最后一個(gè)
Hash ，即系統(tǒng)中的
Hash 來(lái)檢驗(yàn)區(qū)塊鏈中數(shù)據(jù)是否被修改。在實(shí)際操作過(guò)
程當(dāng)中， 也不需要將整條區(qū)塊鏈完整的保存下來(lái)，
而只需要將最后的若干長(zhǎng)度的區(qū)塊鏈緩存
下來(lái)，實(shí)時(shí)更新，進(jìn)行驗(yàn)證。
二、
Merkle tree
Merkle tree 是另外一種給基本的數(shù)據(jù)類型，他與普通的樹的區(qū)別在于，使用
Hash pointers
取代了普通的指針
Merkle tree 的指針從葉節(jié)點(diǎn)指向根節(jié)點(diǎn)，將左
(右)節(jié)點(diǎn)的 Hash 值保存在當(dāng)前節(jié)點(diǎn)的左
(右)Hash 指針，最后將根節(jié)點(diǎn)的
Hash 值保存在系統(tǒng)中！對(duì)于 Merkle tree 而言，其最原本的數(shù)據(jù)是保存在整棵樹的葉節(jié)點(diǎn)上的，而根莖部分都是保
存了上一級(jí)的哈希值。
Merkle proof:
全節(jié)點(diǎn)保存了交易的全部信息，而輕節(jié)點(diǎn)只保存
block header ，為了向輕節(jié)
點(diǎn)證明一個(gè)新的交易已經(jīng)被寫入
Merkle tree 了！那么需要在樹中找到這個(gè)交易葉子，并且
從葉子出發(fā)回到根節(jié)點(diǎn)，
在這個(gè)過(guò)程中， 輕節(jié)點(diǎn)所在的本地主機(jī)需要不斷計(jì)算出當(dāng)前節(jié)點(diǎn)的
Hash 值，如果沿途的
Hash 值正確，那么交易正常√。這樣一條路徑就是
Merkle proof
如果對(duì)交易按時(shí)間順序進(jìn)行排序，
然后布置成 Merkle tree(sorted Merkle tree)
，那么就可以
用一種簡(jiǎn)單的方法證明非法交易并不存在于區(qū)塊鏈中
ps:Hash 指針必須要先確立一個(gè)節(jié)點(diǎn)的值，
才能去計(jì)算與之相關(guān)的區(qū)塊的值，
因此這個(gè)類型
的指針是不可以應(yīng)用在環(huán)形數(shù)據(jù)結(jié)構(gòu)當(dāng)中的。第四節(jié) 協(xié)議
帶權(quán)力中心的數(shù)字貨幣需要一個(gè)權(quán)力中心，
權(quán)力中心發(fā)行貨幣的公鑰公開，
用私鑰加密數(shù)字
貨幣， 這樣每個(gè)人都可以用公鑰驗(yàn)證貨幣來(lái)自于權(quán)力中心。
但是數(shù)字貨幣的本質(zhì)是文件，
如
果用戶大量復(fù)制數(shù)字貨幣，
每個(gè)貨幣都擁有被權(quán)力中心認(rèn)可的數(shù)字簽名，
這樣就可以用偽造
的數(shù)字貨幣進(jìn)行交易，也叫做
double spending attack(
雙花交易 )
處理方法： 在數(shù)字貨幣上再額外添加唯一編號(hào)，
這樣就可以區(qū)別每一張貨幣，
防范雙花交易，
但是這種方法必須由中央權(quán)力機(jī)構(gòu)來(lái)維護(hù)一個(gè)數(shù)據(jù)庫(kù)來(lái)實(shí)時(shí)存儲(chǔ)貨幣編號(hào)和持有人信息，
即
每一筆數(shù)字交易都必須由中心權(quán)力機(jī)構(gòu)確認(rèn)合法性。
在去數(shù)據(jù)中心的數(shù)字貨幣系統(tǒng)中，需要使用區(qū)塊鏈技術(shù)來(lái)避免雙花交易。
1. 鑄幣
鑄幣交易是每個(gè)用戶都擁有的權(quán)力，即鑄幣權(quán)，可以記作：→
A(10)
2. 轉(zhuǎn)賬
由某個(gè)用戶交易個(gè)某組用戶貨幣的行為，可以記作
:A→B(5),A →C(5) 此時(shí)區(qū)塊鏈中有兩種哈希指針
1).鏈接交易的指針； 2).說(shuō)明貨幣來(lái)源的指針
轉(zhuǎn)賬行為需要：轉(zhuǎn)賬方的簽名；收賬人的地址
在驗(yàn)證交易合法性的時(shí)候， 需要上一筆交易的輸出和下一筆交易的輸入合起來(lái)來(lái)測(cè)試能否正
常運(yùn)行—— BitCoin Script
區(qū)塊鏈的組成：
1.
Block header
version
hash of previous block header
只算前一個(gè)區(qū)塊的塊頭
Merkle root hash
target
nonce
2.
Block body
transaction list( 交易列表 ) 節(jié)點(diǎn)的分類
1.
full mode 全節(jié)點(diǎn)，也叫做
fully validating node
2.
light node 只保存 block header ，因此輕節(jié)點(diǎn)不能獨(dú)立做驗(yàn)證。
distributed consensus
分布式共識(shí)，即共享賬本可以被所有用戶承認(rèn)
FLP impossibility result ：在一個(gè)異步的系統(tǒng)中，即使只有一個(gè)成員出錯(cuò)，那么也不可能取
得分布式共識(shí)。
CAP Theorem(C: consistency
一致性 ,A: Availability
可用性 ,P: Partition tolerance
容錯(cuò)
性)CAP 三條性質(zhì)只能同時(shí)滿足兩條
我們需要找到這樣一個(gè)
nonce 使得 H(block header) ≤target 成立，這樣該賬戶才能擁有往區(qū)
塊鏈中寫入交易的權(quán)力。
分叉攻擊： 通過(guò)往區(qū)塊鏈中間插入合法交易來(lái)進(jìn)行回滾，
因此區(qū)塊鏈應(yīng)當(dāng)只接受能延拓最長(zhǎng)
合法鏈的交易
coinbase transaction
是唯一鑄幣的方法。每產(chǎn)生一個(gè)新的交易，那么擁有投票權(quán)的賬戶可以擁有 block reward ，即使用 coinbase transaction
去鑄造 bitcoin 。協(xié)議中規(guī)定初始鑄造數(shù)
量為 50BTC ，但是每當(dāng)區(qū)塊鏈延長(zhǎng)
21W ，鑄造數(shù)量減半，目前
block reward 為 12.5BTC.
只有通過(guò)計(jì)算求解
nonce 才能獲得記賬權(quán)，獲得記賬權(quán)就能得到
block reward ，利用
coinbase transaction
鑄造新的貨幣。
因?yàn)閰^(qū)塊鏈的特殊性質(zhì)，計(jì)算
nonce 是沒有任何捷徑的。
因此尋找 nonce 的過(guò)程就被稱作挖礦，獲得記賬權(quán)的節(jié)點(diǎn)就被稱為礦工第五節(jié) 實(shí)現(xiàn)
Block chain 是一個(gè)去中心化的共享賬本
以 Bitcoin 為例， Bitcoin 是一個(gè)基于交易的賬本模式
transaction-based ledger
UTXO: Unspent Transaction Output
未被花掉的交易的集合
通過(guò)查詢 UTXO 來(lái)確認(rèn)新的交易中使用的貨幣是否在
UTXO 中，若在，則合法，否則不合
法。因此全節(jié)點(diǎn)內(nèi)存中需要頻繁使用
UTXO 來(lái)確認(rèn)交易的合法性。
交易會(huì)不斷的更新
UTXO 。
UTXO 中被交易使用掉的貨幣
=UTXO 中因交易產(chǎn)生的未使用的貨幣。
total inputs= total outputs
transaction fee 交易費(fèi)
交易費(fèi)的金額較小，但是隨著減半效應(yīng)的存在，最終會(huì)轉(zhuǎn)變成以
transaction fee 為主體的
挖礦行為。
以太坊是一個(gè)基于賬戶的賬本模式
account-based leger
