Bitcoin 筆記 1 - Cryptographic Hash Function

Cryptographic hash function H(x)
首先，需要一個高效率的cryptographic hash function，能夠將string x map到一個固定長度(e.g. 256 bits) 的output，且擁有以下的特點:

• collision free - 沒有人能找出hash collision的可能: collision一定會存在，因為沒有完美的hash function，但這邊需要的特性是"不能讓人用任何computation找到collision keys"。在這個特性的前提下，每當H(x) 的值等同於 H(y)，我們可以放心地認為string x = y 。
• Hiding - 無法從hash value逆推回去key: 要不然還得了! 這邊的問題在於，如果key set很小，則任何人都可以一一比對每個key的hash value，來檢查目前看到的hash value是哪一個key，所以一個方法是擴大key set，利用把key concatenate 某個出現機率極小的string(e.g. random產生的256-bit string，則每個string出現的機率為1/2^256，相當的小)，這樣相當於key set被擴大了，對手只能暴力去比對，但以目前電腦能力是無法解決的。
• puzzle-friendly - 無法產生某個特定的hash value: 這應該是跟hiding property有異曲同工之妙的性質，因為有能力產生某個特定的value，意即你找出了hash function定義是啥，根據collision-free的特性，這key可以說是唯一，而這個key/value pair就被破解了，違反hiding property。

Commitment

cryptographic hash function其中一個應用為"commitment"，他的意思是把某個訊息密封(稱為commit to a message)在某個信封內，此時雖然每個人都可以看到這個密封的信封(稱為commitment)，但是裡面的訊息對每個人來說都是秘密。之後要有辦法打開這個密封的信封(利用密封時產生的key)，讀取這個訊息，但是不破壞這個密封。

應用上通常是拿來verify某個 3-tuple (key, commitment, message)是否為同一組commit過程的產物:

整個過程的implementation用到了hash function，首先定義 commit(msg) 這個function回傳以下2-tuple:

key就用到hiding property中提到的256-bit random string，用來和msg concatenate來擴大key set。

而verify的implementation如下:

其實就是簡單比對hash value。這邊用到了hash function的collision-free property，否則我們無法透過比對兩個hash value來驗證兩個key相等。

SHA-256

bitcoin使用SHA-256當作其cryptographic hash function。

運作流程如下: 首先把message分成512-bit blocks，如果最後一個block不足512 bit則做padding補足。寫在spec的某個256-bit初始值 IV 加上第一個512 bit block的bits，總共湊成768 bits先投入compression function c (就是hash function)，output出256 bits，接著再加上block 2的512 bits湊成第二次的768 bits 去做hash，這樣一直做直到所有的的message bits都被hash完，最後hash出來的256 bits就是SHA-256的結果。

記住SHA-256是符合cryptographic hash function特性的hash function，所以沒有人能找到collision，即便collision一定存在。