區(qū)塊鏈技術(shù)與應(yīng)用

1、北京大學(xué)肖臻老師區(qū)塊鏈技術(shù)與應(yīng)用公開(kāi)課第一節(jié)：緒論第二節(jié)：密碼學(xué)原理crypto-currency 一、cryptographic hash function性質(zhì);1 collision resistance(hash碰撞) 指H(x)=H(y)，而xy 對(duì)于哈希函數(shù)，哈希碰撞是常見(jiàn)的，但是要人為的制造哈希碰撞幾乎是不可能的例子：H(m)，m為message，如果m被人篡改，那么H(m)會(huì)發(fā)生改變。ps:哈希弱碰撞目前是無(wú)法被數(shù)學(xué)證明的，但與此同時(shí)，我們還沒(méi)有很好的辦法人為制造哈希碰撞?？墒菍?duì)于不同類(lèi)型的哈希函數(shù)其安全性隨著計(jì)算機(jī)科學(xué)和數(shù)學(xué)方法的進(jìn)步，也是有可能被破解的，例如MD5性質(zhì)2 hi

2、ding 指哈希函數(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é)果不能提前公開(kāi)的情況下，保證預(yù)測(cè)結(jié)果的真實(shí)性。將預(yù)測(cè)x的哈希值公開(kāi)，待到結(jié)果出現(xiàn)時(shí)再公開(kāi)預(yù)測(cè)以檢驗(yàn)預(yù)測(cè)與實(shí)際是否相符。在實(shí)際操作中，也有將x和隨機(jī)數(shù)一起做HASH以保證取值的分布足夠離散。比特幣中的哈希函數(shù)所需性質(zhì)：性質(zhì)3 puzzle friendly 指除了遍歷以外，沒(méi)有任何辦法可以做出哈希碰撞，這樣才可以作為挖礦證明，然而想

3、驗(yàn)證一個(gè)人的挖礦證明卻是非?？旖莸模?yàn)橹恍枰?jì)算一次哈希函數(shù)值就可以了。比特幣中所使用的哈希函數(shù)為：SHA256Secure Hash Algorithm二、數(shù)字簽證1.public key private keyasymmetric encryption algorithm 非對(duì)稱(chēng)加密算法由于區(qū)塊鏈系統(tǒng)是完全公開(kāi)的，所以并不需要公私鑰對(duì)進(jìn)行保密通信，而是進(jìn)行數(shù)字簽名，以驗(yàn)證自己的身份，即私鑰加密，公鑰解密對(duì)于256位的公私鑰對(duì)，很難有兩個(gè)賬戶(hù)擁有完全相同的公私鑰對(duì)，所以很難通過(guò)產(chǎn)生公私鑰對(duì)再比對(duì)的方法來(lái)冒名他人。第三節(jié) 數(shù)據(jù)結(jié)構(gòu)一、 hash pointers區(qū)塊鏈(block chain

4、)是最基本的數(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)，而只需

5、要將最后的若干長(zhǎng)度的區(qū)塊鏈緩存下來(lái)，實(shí)時(shí)更新，進(jìn)行驗(yàn)證。二、 Merkle treeMerkle tree是另外一種給基本的數(shù)據(jù)類(lèi)型，他與普通的樹(shù)的區(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ù)是保存在整棵樹(shù)的葉節(jié)點(diǎn)上的，而根莖部分都是保存了上一級(jí)的哈希值。Merkle proof: 全節(jié)點(diǎn)保存了交易的全部信息，而輕節(jié)點(diǎn)只保存block header，為了向輕節(jié)點(diǎn)證明一個(gè)新的交易已經(jīng)被寫(xiě)入M

6、erkle tree了！那么需要在樹(shù)中找到這個(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è)類(lèi)型的指針是不可以應(yīng)用在環(huán)形數(shù)據(jù)結(jié)構(gòu)當(dāng)中的。第四節(jié) 協(xié)議帶權(quán)力中心的數(shù)字貨幣需要一個(gè)權(quán)力中心，權(quán)力中心發(fā)行貨幣的公鑰公開(kāi)，用私

7、鑰加密數(shù)字貨幣，這樣每個(gè)人都可以用公鑰驗(yàn)證貨幣來(lái)自于權(quán)力中心。但是數(shù)字貨幣的本質(zhì)是文件，如果用戶(hù)大量復(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è)用戶(hù)都擁有的權(quán)力，即鑄幣權(quán)，可以記作：A(10)2.

8、 轉(zhuǎn)賬由某個(gè)用戶(hù)交易個(gè)某組用戶(hù)貨幣的行為，可以記作:AB(5),AC(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 headerversionhash of previous block header 只算前一個(gè)區(qū)塊的塊頭Merkle root hashtargetnonce2. Block bodytransaction list(交易列表)節(jié)點(diǎn)的分類(lèi)1. full mode 全

9、節(jié)點(diǎn)，也叫做 fully validating node2. light node 只保存block header，因此輕節(jié)點(diǎn)不能獨(dú)立做驗(yàn)證。distributed consensus 分布式共識(shí)，即共享賬本可以被所有用戶(hù)承認(rèn)FLP impossibility result：在一個(gè)異步的系統(tǒng)中，即使只有一個(gè)成員出錯(cuò)，那么也不可能取得分布式共識(shí)。CAP Theorem(C: consistency一致性 ,A: Availability可用性 ,P: Partition tolerance 容錯(cuò)性)CAP三條性質(zhì)只能同時(shí)滿(mǎn)足兩條我們需要找到這樣一個(gè)nonce使得H(block header)ta

10、rget成立，這樣該賬戶(hù)才能擁有往區(qū)塊鏈中寫(xiě)入交易的權(quán)力。分叉攻擊：通過(guò)往區(qū)塊鏈中間插入合法交易來(lái)進(jìn)行回滾，因此區(qū)塊鏈應(yīng)當(dāng)只接受能延拓最長(zhǎng)合法鏈的交易coinbase transaction 是唯一鑄幣的方法。每產(chǎn)生一個(gè)新的交易，那么擁有投票權(quán)的賬戶(hù)可以擁有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是沒(méi)有任何捷徑的。因此尋找nonce的過(guò)程就被稱(chēng)作挖礦，獲得記賬權(quán)的節(jié)點(diǎn)就被稱(chēng)為礦工第五節(jié) 實(shí)現(xiàn)Block chain是一個(gè)去中心化的共享賬本以Bitcoin為例，Bitcoin是一個(gè)基于交易的賬本模式 transaction-based ledgerUTXO: Unspent Transaction Output 未被花掉的交易的集合通過(guò)查詢(xún)UTXO來(lái)確認(rèn)新的交易中使用的貨幣是否在UTXO中，若在，則合法，否則不合法。因此全節(jié)點(diǎn)內(nèi)存中需要頻繁使用UTXO來(lái)確認(rèn)交易的合法性。交易會(huì)不斷的