三個特性：

1.collision resistance

2.hiding

3.puzzle friendly

生成公私鑰要有個好的隨機(jī)源。

重點(diǎn)：哈希和簽名

密碼學(xué)到此結(jié)束

第三課 比特幣數(shù)據(jù)結(jié)構(gòu)

哈希指針 hash pointers

比特幣中最基本的數(shù)據(jù)結(jié)構(gòu)是區(qū)塊鏈

相比于一般的鏈表，使用了哈希指針代替一般指針；

區(qū)塊鏈中，每個區(qū)塊鏈中有指向前一個的哈希指針，哈希指針的值是前一個區(qū)塊鏈完全取哈希得出的值。所以無論鏈中哪一個區(qū)塊發(fā)生變化，都會影響最終的哈希值（和普通鏈表不一樣）；因?yàn)檫@個特性可以保存最近的區(qū)塊鏈而不用完全保存。

比特幣另外一個特性：merkle tree

區(qū)別于一般 binary tree，用哈希指針代替一般指針。

檢測root hash值，就能檢測任何節(jié)點(diǎn)的修改。block header中包含root hash ，block body中包含交易信息。

比特幣中的節(jié)點(diǎn)有兩類，全節(jié)點(diǎn)和輕節(jié)點(diǎn)

全節(jié)點(diǎn)，包含 block header 和block body

輕節(jié)點(diǎn)，包含 block header

為了讓輕節(jié)點(diǎn)查到交易信息，使用merkle proof；

輕節(jié)點(diǎn)只有根哈希值，為了知道黃色交易是不是包含在merkle tree， 向全節(jié)點(diǎn)請求merkle proof，全節(jié)點(diǎn)接收到請求后發(fā)送紅色哈希值給輕節(jié)點(diǎn)，輕節(jié)點(diǎn)接收到之后在本地算出綠色哈希值，算出root hash 之后和輕節(jié)點(diǎn)中block header中的值比對，看是否一致。

以上證明 也叫 proof of membership 復(fù)雜度log（n）

如何證明 proof of non-membership（證明沒 交易）

高效證明方法基于假設(shè)，否則只能傳整個樹 復(fù)雜度n

對葉節(jié)點(diǎn)的順序做一些要求，譬如按照交易的hash值排序，對葉節(jié)點(diǎn)的包含的交易內(nèi)容取一次hash值，按hash值從小到大排序，我查的交易取hash值，看是否在區(qū)間中。復(fù)雜度 logn 比特幣中沒有排序。

數(shù)據(jù)結(jié)構(gòu)只要是無環(huán)，都可以用hash pointer代替 一般指針。

第四課 設(shè)計(jì)加密貨幣

數(shù)字貨幣主要處理雙花攻擊（double spending attack）

中心化方案統(tǒng)一由央行發(fā)行，記錄交易

去中心化方案由廣大群眾一起承擔(dān)

去中心化貨幣要解決兩個問題

1.數(shù)字貨幣的發(fā)行

在比特中由挖礦決定

2.驗(yàn)證交易的有效性

在比特幣中也是需要數(shù)據(jù)結(jié)構(gòu)，由用戶一起承擔(dān)，就是區(qū)塊鏈。

連接區(qū)塊鏈的是 hash pointer

說明交易的來源是另外一個指針，解決雙花攻擊

A需要知道B的地址，B需要知道A的公鑰，驗(yàn)證A身份；

非對稱加密：A發(fā)送給B信息，需要B提供的公鑰加密，B接收完用B的私鑰解密。

bitcoin script腳本用來驗(yàn)證交易。

block header中包含

1、bitcoin的版本協(xié)議 version

2、指向前一個區(qū)塊指針 hash of previous block header

3、整塊merkle tree的hash值

4、挖礦的難度目標(biāo)閾值 target

5、隨機(jī)數(shù) nonce

H(block header)<= target

系統(tǒng)中大多數(shù)是輕節(jié)點(diǎn)，但是輕節(jié)點(diǎn)利用區(qū)塊鏈的特性而不參與區(qū)塊鏈的構(gòu)建，主要講解全節(jié)點(diǎn)。

分布式共識：distributed consensus

distributed hash table解決一致性；

FLP impossibilty result：在一個異步的系統(tǒng)里，即網(wǎng)路傳輸延遲沒有上限的系統(tǒng)，即使只有一個成員是有問題的 （faulty），也沒法達(dá)成共識。

CAP Theorem: Censistency 、Availability、 Partition tolerance 只能同時滿足滿足兩個，不能三個同時滿足。

分布式共識的一個著名協(xié)議:paxos，能保證一致性，即如果協(xié)議達(dá)成共識，這個共識一定是一致的;

bitcoin中的共識協(xié)議，consensus in Bitcoin，

假設(shè)系統(tǒng)中只有少數(shù)節(jié)點(diǎn)有惡意，關(guān)于投票，比特幣按計(jì)算力來投票，每個節(jié)點(diǎn)可以在本地組裝候選區(qū)塊，試驗(yàn)nonce滿足H（block header）<= target ,如果某一個節(jié)點(diǎn)找到了nonce，獲得記賬權(quán)，有記賬權(quán)才能發(fā)布下個節(jié)點(diǎn)。

分叉攻擊：

如果出現(xiàn)兩個礦工差不懂同時同時出現(xiàn)兩個節(jié)點(diǎn)，等長的區(qū)塊鏈會持續(xù)一段時間，看哪一個先找到后一個節(jié)點(diǎn)，稱為longest valid chain，另外一個拋棄。

為了解決合法都接納，采用 block reward機(jī)制。

唯一產(chǎn)生新的幣的途徑：coinbase transaction

比特幣掙奪計(jì)賬權(quán)的過程稱為挖礦。