Bitcoin 筆記 2 - Hash pointers and Block chain data structures

Hash pointer

基本上就是一個指向某個被hash function保護的 data structure的pointer，沒什麼特別的，但是他除了pointer功能外，由於儲存了hash value，所以同時也能驗證data是否更改了(故名hash pointer)。

Block chain data structure

被has function保護的data blocks可以透過hash pointer形成一個data structure，稱為block chain。
block chain只要是acyclic(沒有形成迴圈的指向)，可以是例如linked-list或是binary tree.，例如以下的linked list implementation:

這個linked-list就是一般的linked list，特別的是每個element指向previous element的pointer是一個hash pointer。

舉例來說block chain的scenario: 可以用來做tamper-evident log。也就是每個block儲存某個時段的log，但是當某人更改了previous block中使用到的data，hash pointer就能發現資料變動了的證據(稱為tamper evident)。

假設有一個人想要更改下圖中最左邊block的data:

則中間block的hash pointer就會verification fail，因為左邊block的hash value該改了，所以此人是必得要把chain上的所有block data都修改，並且竄改相對應的hash pointer才能不被發覺:

另一個可能的data structure是binary tree (又稱為Merkle tree，以發明人命名):

底層的leaf node是真正data的block，non-leaf nodes的blocks是含有兩個children的hash pointer，所以要更改某個leaf block data的話，至少要改動所有相關路徑上的blocks直到root block，對手需要竄改的數量相較於linked-list implemenation較少，asypmtotically O(log n)，但相對的要驗證(membership)某個data是屬於這個block chain也只要O(logn) hash，這比起linked-list是一種tradeoff。

上述的Merkel tree能夠O(logn)驗證membership，但是不能O(logn)驗證non-membership，因為必須窮盡所有paths才能知道一個data block不是這個chain的成員。但是如果leaves data依照某些規則sorted之後，可以O(logn)複雜度來驗證non-membership。