第三節:比特币的資料結構
普通指針存儲的是某個結構體在記憶體中的位址。假如P是指向一結構體的指針，那麼P裡面存放的就是該結構體在記憶體中的起始位置。而哈希指針除了要存位址之外，還要儲存該結構體的哈希值H()。好處是:從哈希值這個哈希指針，不僅可以找到該結構體的位置，同時還能夠檢測出該結構體的内容有沒有被篡改，因為我們儲存了它的哈希值。
比特币中最基本的結構就是區塊鍊，區塊鍊就是一個一個區塊組成的連結清單。區塊鍊和普通的連結清單相比有什麼差別:
①用哈希指針代替了普通指針(B block chain is a linked list using hash pointers)
區塊鍊第一個區塊叫作創世紀塊(genesis block) 最後一個區塊 是最近産生的區塊(most recent block) 每一個區塊都包含指向前一個區塊的哈希指針
一個區塊的哈希指針怎麼算:是把前面整個區塊的内容，包括裡面的hash pointer ，合在一起取哈希值。通過這種結構，可以實作tamper-evident log。如果有人改變了一個區塊的内容，後面一個區塊的哈希指針就對不上，因為後一個區塊哈希指針是根據前一個區塊的内容算出來的，是以後一個哈希指針也得改，以此類推，我們保留的是最後一個哈希值也會變化。
②普通連結清單可以改變任意一個元素，對連結清單中其他元素是沒有影響的。而區塊鍊是牽一發而動全身，因為隻需要儲存最後一個哈希值，就可以判斷區塊鍊有沒有改變，在哪裡改變了。
是以比特币沒有要儲存所有區塊的内容，可以隻保留最近的幾千個區塊。如果要用到以前的區塊，可以向系統中其他節點要這個區塊。有些節點是有惡意的，怎麼判斷?這裡要用到哈希值一個性質，如下:
其他節點給你一個區塊，如何判斷它是正确的?算出它的哈希值，與保留的區塊的哈希值對比，即可。
比特币中的另外一個結構是:Merkle tree。(見拍的圖②，其中最下面一層是資料塊(data blocks)，上面三層内部節點都是哈希指針(hash pointers)，第一層是根節點，根節點的區塊也可以取個哈希，叫根哈希(root hash))
另外一個概念:binary tree。
這種結構的好處:隻要記住根哈希值，就能檢測出對樹中任何部位的修改。
它們的差別:①用哈希指針代替了普通指針。
比特币當中各區塊之間用哈希指針連接配接在一起，每個區塊所包含的交易組織成一個merkle tree的形式，最下面一行data blocks每個區塊實際上是一個交易，每個區塊分為兩部分，分别是塊頭和塊身(block header ,block body)。塊頭裡面有根哈希值，每個區塊所包含的所有交易組成的merkle tree的根哈希值存在于區塊的塊頭裡面，但是，塊頭裡沒有交易的具體内容，隻有一個根哈希值，塊身裡面是有交易的清單的。
merkle tree 的作用:①提供merkle proof
比特币中的節點分為兩類:全節點(儲存整個區塊的内容，即塊頭塊身都有，有交易的具體資訊)和輕節點(例如手機上的比特币錢包)(隻有塊頭)
這時存在一個問題:如何向一個輕節點證明某個交易是寫入區塊鍊的?
這時需要用到merkle proof :找到交易所在的位置(最底行的其中一個區塊)，這時該區塊一直往上到根節點的路徑就叫merkle proof。
最上面一行是小型的區塊鍊，該圖展現的是一個區塊的merkle tree，最下面一行是包含的交易。假設某個輕節點想知道圖中黃色的交易，是否包含在了merkle tree裡面。該輕節點沒有包含交易清單，沒有這顆merkle tree的具體内容，隻有一個根哈希值。這時輕節點向一個全節點送出請求，請求證明黃色的交易被包含在這顆merkle tree裡面的merkle proof。全節點收到這個請求之後，隻需要将圖中标為紅色的這三個哈希值發給輕節點即可。有了這些哈希值之後，輕節點可以在本地計算出圖中标為綠色三個哈希值。首先算出黃色交易的哈希值，即它正上方的那個綠的哈希值，然後跟旁邊紅色的哈希值拼接起來，可以算出上層節點綠色的哈希值。然後再拼接，再算出上層綠色哈希值，再拼接，就可以算出整棵樹的根哈希值。輕節點把這個根哈希值和block header裡的根哈希值比較一下，就能知道黃色的交易是否在這顆merkle tree裡。
全節點在merkle proof裡提供的這幾個哈希值，就是從黃色的交易所在的節點的位置到樹根的路徑上用到的這些哈希值。輕節點收到這樣一個merkle proof之後，隻要從下往上驗證，沿途的哈希值都是正确的即可。(驗證時隻能驗證該路徑的哈希值，其他路徑是驗證不了的，即該圖中紅色的哈希值是驗證不了的)
這樣是否不安全呢?假如黃色交易被篡改，它的哈希值發生了變化，那能不能調整旁邊紅色的哈希值，使得它們拼接起來的哈希值是不變的呢?不行，根據collision resistance，這是不可行的。
merkle proof可以證明merkle tree裡面包含了某個交易，是以這種證明又叫proof of membership或 proof of inclusion。
對于一個輕節點來說，驗證一個merkle proof 複雜度是多少?假設最底層有n個交易，則merkle proof 複雜程度是θ(log(n))。
如何證明merkle tree裡面沒有包含某個交易?即proof of non-membership。可以把整棵樹傳給輕節點，輕節點收到後驗證樹的構造都是對的，每一層用到的哈希值都是正确的，說明樹裡隻有這些葉節點，要找的交易不在裡面，就證明了proof of non-membership。問題在于，它的複雜度是線性的θ(n)，是比較笨的方法。
如果對葉節點的排列順序做一些要求，比如按照交易的哈希值排序。每一個葉節點都是一次交易，對交易的内容取一次哈希，按照哈希值從小到大排列。要查的交易先算出一個哈希值，看看如果它在裡面該是哪個位置。比如說在第三個第四個之間，這時提供的proof是第三個第四個葉節點都要往上到根節點。如果其中哈希值都是正确的，最後根節點算出的哈希值也是沒有被改過的，說明第三、四個節點在原來的merkle tree裡面，确實是相鄰的點。要找的交易如果存在的話，應該在這兩個節點中間。但是它沒有出現，是以就不存在。其複雜度也是log形式，代價是要排序。排好序的叫作sorted merkle tree。比特币中沒有用到這種排好序的merkle tree，因為比特币中不需要做不存在證明。
這節講了比特币中兩種最基本的結構:區塊鍊和merkle tree，都是用哈希指針來構造的。除了這兩種之外，哈希指針還能用另一個方面。
隻要一個資料結構是無環的(非循環連結清單)，都能用哈希指針代替普通指針。有環的話存在一個問題，他們的哈希值沒法計算，沒法确定一個哈希值固定的區塊。