哈希#
大家應該都比較熟悉哈希函數的工作原理，密碼學中用到的哈希函數被稱為crypto-graphic hash function。
它有兩個重要的性質：一個叫做 collision resistance。這個地方的 collision 是指哈希碰撞。如果有兩個輸入 x, y且 x ≠ y，hash 函數是H(v)，但是H(x) = H(y)。這就叫做哈希碰撞。兩個不同的輸入算出來的哈希值是相等的。哈希碰撞是很常見的。像我們使用哈希表的過程中就會遇到 hash 碰撞。不同的輸入可能會被映射到 hash 表中的同一個位置。一般來說哈希碰撞是不可避免的。因為輸入空間是遠遠大於輸出空間的，比如說我們有 256 位的 hash 值。那輸出空間有多大呢？所有 hash 值的可能性就是 2 的 256 次方，輸出空間就只有這麼大。但是輸入空間可以是無限大的。所以它是有任意多樣的可能性。按照鴿籠原理的話，必然會出現有兩個輸入被映射到同一個輸出的情況。所以我們這裡說的collision resistance並不會出現哈希碰撞。有的📖上管這個性質叫做collision free。這個說法我不是特別喜歡。因為它對人很容易造成誤解。好像是碰撞不會發生。實際上碰撞是客觀存在的。它這個意思是實際上沒有什麼高效的方法，人為的去製造哈希碰撞。就給定一個x，沒有什麼好的辦法，你能找到另外一個y，使得H(x)和H(y)的哈希值恰好相等。沒有什麼高效的方法去找。你硬要找的話可以用蠻力求解的方法。比如說這個x和y，你就遍歷所有輸入的可能性。然後看看哪一個算出來的哈希值正好相等。這種叫做brute-force。遍歷所有的取值，最後找了一個哈希值恰好碰撞在一起。如果輸入空間比較大。比如說對於 hash 值是 256 位的話，實際上你要用蠻力求解的方法在實際中是不可行的。他的工作量實在是太大了。
那麼collision resistance這個性質有什麼用呢？它可以用來對一個message求digest。比如我們有一個message叫做m，我們取它的哈希值H(m)。這個哈希值可以認為是這個消息的digest。用來檢測對這個message的篡改。比如說有人改這個message的內容，它的 hash 值就會發生變化。那麼collision resistance這個性質就是說你找不到另一個m'使得H(m')跟H(m)恰好相等。沒有辦法篡改內容，而又不被檢測出來。比如說你有一個很大的文件。你想把它存在到某個雲存儲服務上。相當於你用到的時候再把它下載回來，那麼你怎麼知道你下載的版本，跟你當初上傳的版本是一樣的呢？這就可以用到 hash 函數的 collision resistance 性質。在你上傳這個文件之前，先算一個 hash 值出來。這個 hash 值存在本地。將來你下載之後，再算一個 hash 值。跟原來你存的 hash 值比較一下。如果是一樣的話，那麼說明上傳的這個文件沒有被篡改。下載的還是原來當初的版本。這就是 collision resistance 的一個用途。
有一點大家注意。沒有那個 hash 函數，能夠在數學上證明是 collision resistance 的。也就是說我們剛剛講的這麼重要的一個性質，從理論上是證明不出來的。這個只能靠實踐中的經驗。有些 hash 函數經過時間的長期檢驗。世界上有那麼多的密碼學專家，誰也沒有能夠找到人為製造 hash 碰撞的方法。所以我們就認為這些 hash 函數是 collision resistance 的。也就是實踐經驗。也有一些 hash 函數以為我們認為是 collision resistance 的，但是後來大家找到了，製造 hash 碰撞的方法。這裡面一個很重要的例子就是 MD5，MD5 曾經是個很流行的 hash 函數，大家原來以為它很安全。但現在已經不行了，我們已經知道怎麼人為的製造 hash 碰撞了。
密碼學用的 hash 函數還有第二個性質：hiding。hiding 是什麼意思呢？hiding 是說 hash 函數的計算過程是單向的。是不可逆的，給定一個 x 可以算出他的 hash 值H(x)，但是從 hash 值H(x)沒有辦法反推出原來的輸入x，換句話說，這個 hash 值H(x)沒有洩漏有關輸入x的任何信息。這叫做 hiding。但是其實你想一想你想要知道這個輸入的話，也是有辦法的。怎麼辦，還是用蠻力的辦法。我把這個輸入所有可能的取值，遍歷一遍，看看有那個輸入的值求解H(x)跟原來的H(x)相等。這就我能猜出來原來的輸入 x 是什麼。所以蠻力求解是一種辦法。hiding 這個性質成立的前提是，這個輸入空間要足夠的大，使得這種蠻力求解的方法是不可行的。而且這個輸入的分佈要比較均勻。各種可能的取值的可能性都是差不多的。如果這個輸入空間雖然是很大，但是絕大數情況下都是取值都是在幾個少數幾個值，那麼也是比較容易被破解的。
hiding 這個性質有什麼用呢？它可以和 collision resistance 這個性質結合在一起。用來實現 digital commitment。這個 digital commitment 也叫做 digital equivalent of a sealed envelope。
我們說一下現實生活中 sealed envelope 是跟什麼用的？比如說有一個人他能夠預測股市，可以預測第二天那些股票會漲停。那怎麼證明這個人預測的是不是準確呢？一種辦法是這個人提前一天這個人在電視台上公布預測結果（我預測 xxx 股票第二天漲停。）。第二天收盤之後呢看一下這個股票是不是真的漲停。就知道預測的準不準了。這樣做有什麼問題嗎？這好像是預測準不準的方法。有什麼問題嗎？如果你預測結果提前公布了，可能會影響股市。比如說這個人很有名氣，大家覺得這個人是個股神。本來這支股票不會漲停，他這麼公開預測，大家拼命的去買。結果他變成了漲停。當然了方向的情況也有可能發生。就這支股票本來確實是需要漲停的，有人想踢場子。你不是預測他漲停嗎，我就不讓他漲停。拼命的砸盤。這都有可能發生。這說明預測結果不能提前公開。但是預測結果不提前公開。你等第二天收盤之後再公開，那你怎麼知道這個預測結果有沒有被篡改過。你最後公開的結果是不是你提前一天做出來的。這個就要用到我們說的 sealed envelope。你把你的預測結果寫在一張紙上，放到一個信封裡給封好了。這個信封要交給第三方的公正機構保管。等第二天收盤之後再把它打開，驗證一下這個結果準不準。現實中 sealed envelope 就是這個。
那在電子世界裡呢，我要有一個 digital sealed envelope 我要怎麼實現呢？把這個預測結果作為輸入 x 算出一個 hash 值來。然後把這個 hash 值可以公布出去。因為我們有這個 hiding 的性質。所以你從這個 hash 值不知道預測結果是什麼。然後第二天收盤之後呢，我再把預測結果公布出去。因為有這個 collision resistance 的性質。所有我這個預測結果是不可能篡改的。你要是改了的話就給當初公布出來的這個 hash 值是對不上的了。這就起到了 sealed envelope 的功能。實際操作中有一些細節要注意。就我們說 hiding 這個性質的前提是什麼。輸入空間要足夠大。分佈要比較均勻。如果這個輸入不滿足這個性質。像這個例子，預測第二天哪隻股票會漲停。股票就那麼幾千隻輸入空間不是足夠大。那麼常用方法是把這個輸入後面隨機拼接一個隨機數。然後再一起取 hash。就這個不是x了，而是 x 的後面拼接一個 nonce，然後整個取 hash。H(x | Nonce)。這個 nonce 是我們選取的隨機數，保證我們選舉之後，整個輸入是足夠隨機的。然後分佈也是足夠均勻的。這是實際中操作要注意的一些細節。
除了密碼學中要求的這兩個性質之外，比特幣中用到的 hash 函數還要求第三個性質。叫 puzzle friendly。它這個意思是說，hash 的計算是事先不可預測的。你光看這個輸入，你很難知道它這個 hash 值是什麼。所以你想到你算出來的 hash 值是落在某個範圍之內的。那沒有什麼好辦法你只能一個一個去試。看那個輸入算出來是恰好落在要求的那個範圍之內。比如說你想得到一個 hash 值。前面k位都是 0。0000000…0000000xxxxxxx..xxx整個是 256 位，必須以k個零開始。那什麼要的輸入會算出這個 hash 值呢？不知道 puzzle friendly 這個性質是說你事先是不知道的。那個輸入更有可能算出這個 hash 值。那你要得到這個 hash 值就一個一個去試。沒有什麼捷徑。這個性質為什麼叫做 puzzle friendly 後面我們講到比特幣挖礦的過程。大家可能聽說過挖礦這個詞。挖礦實際上就試找一個 nonce。找這麼一個隨機數，這個 nonce 跟區塊的塊頭裡的其他信息合在一起。作為輸入，取出一個 hash 來，那個 hash 值要小於等於某個制定的目標閾值。這是H(block header) ≤ target。比特幣是區塊鏈，區塊鏈就是一個一個區塊組成的鏈表，每一個區塊都有一個塊頭，block header，block header 中有很多的域。其中有一個域是我們可以設置的隨機數 nonce。那挖礦的過程就是不停的去試各種不同的 nonce，使得整個 block header 取 hash 之後，落在指定的範圍之內。就比如說這是整個的輸出空間 outspace。我們要求算出來的 hash 值只有前面這一點是合法的。這是 target space。這個 puzzle friendly 這個性質是說，這個挖礦的過程沒有捷徑。只能够不停的去試大量的 nonce，才能找到符合要求的解。所以這個過程才可以用來作為工作量證明。叫做 proof of work。你挖到礦了找到了符合要求的 nonce，一定是因為你做了大量的工作。因為沒有別的捷徑。
這裡大家注意，雖然這個挖礦的過程需要很多的工作量，才能找到一個符合要求的 nonce。但是一旦有人找到這樣一個 nonce，發布出去之後，其他人要驗證這個 nonce 是不是符合要求，是很容易的，只要算一次 hash 就行了。這個 nonce 作為 header 的一部分，算一次 hash 值看它是不是小於等於這個目標的閾值。挖礦很難驗證很容易。這個性質叫做 difficult to solve, but easy to verify。我們設計這種 mining puzzle 的時候要注意這個性質。
比特幣中用的 hash 函數是 SHA-256，這個 sha 的意思是，secure hash algorithm。我們說的這三個性質它都是滿足的。有同學可能覺得 puzzle friendly 和 collision resistance 很像。這兩個性質是有一定的聯繫，但是不是完全一樣。我們說比特幣用到了密碼學中的兩個功能，一個是 hash，一個簽名。
簽名#
到這裡我們把第一個功能 hash 講完了。我們下面講簽名。
要講簽名我要講一下比特幣系統中的賬戶管理。日常生活中你想要開個賬戶怎麼辦，帶上證件去銀行辦理開戶手續。這就是中心化系統中的賬戶管理方式。那比特幣是去中心化的，他沒有銀行之類的這類機構。那怎麼開賬戶呢？每個用戶自己決定開戶。不需要任何人批准。開戶的過程很簡單，就是創立一個公鑰和私鑰的對 pair。(public key, private key)。在本地創立一個公私鑰對。就是一個賬戶。這就在比特幣中代表了一個賬戶，公私鑰這個概念是來自非對稱加密這個體系。叫做 asymmetric encryption algorithm，最早的加密體系是對稱的。叫做 symmetric encryption algorithm。比如說兩個人之間要進行通信，我要把某個信息發給你。但是這個通信的網絡是有可能被竊聽的。那怎麼辦呢。咱們兩個事先商量一個密鑰。一個叫做 encryption key。我把這個信息加密之後發送給你。你收到之後再用這個密鑰解密。因為這個加密和解密用的是同一個密鑰。所以這個叫做對稱的加密體系。他這個前提是假設。有某種安全的渠道。能夠把這個密鑰分發給通信的雙方。因為你顯然的不能把這個密鑰在網絡上以明文的形式傳輸。我們假設網絡本身就是不安全的。有可能被竊聽，這個就是對稱加密體系的一個弱點。密鑰的分發不是很方便。解決這個問題非對稱加密體系就提出來我們不是用一個密鑰，而是用一對密鑰。有一個公鑰還有一個私鑰。加密用的是公鑰，解密用的是私鑰，比如說我要把一個信息傳給你，我用你的公鑰給這個信息加密，你收到之後再用你的私鑰解密。得到原來的信息。大家注意這個加密和解密用的是同一個人的公鑰和私鑰。都是這個接收方的公鑰和私鑰。
這有什麼好處呢？公鑰是不用保密的，加密用的公鑰是不用保密的，你可以告訴所有的人。有的人他的 homepage 就列出來他的 pbk：public key。大家都可以知道。私鑰是要保密的，解密是要用私鑰解密的，但是私鑰只要保存在本地就行了。不用傳給對方。就給你通信的那個人不需要知道你的私鑰。他是用你的公鑰加密的。你要回復他的話你用他的公鑰加密。都不需要知道對方的私鑰。這就解決了對稱加密體系中密鑰分發的不方便的問題。比特幣系統中呢，你要創建一個賬戶。就在本地产生一對公私鑰。這個公鑰就相當於你的銀行賬號。別人要給你轉賬，只要知道你的公鑰就行了。這個私鑰相當於你的賬戶密碼。知道這個私鑰就可以把這個賬戶上的錢轉走。那麼有一個問題我們前面說比特幣系統是不加密的。他叫加密貨幣他其實不是加密的。信息都是公開的。那我要這個公鑰和私鑰幹什麼呢？實際上用來做簽名。
比如說我要轉 10 個比特幣給你。然後我這個交易發布到區塊鏈上，別人怎麼知道這個交易確定是我發起的呢？會不會是有人冒名頂替。偷偷把我帳上的錢轉走呢？這就需要我在發布這個交易的時候要用我自己的私鑰對這個交易進行簽名，那其他人收到這個交易之後呢，在用我的公鑰去驗證這個簽名的正確性。簽名用的是私鑰。驗證簽名用的是這個人的公鑰。
仍然都是同一個人。既然每一個人都是獨立的產生賬戶。本地獨立的生成公私鑰對。不需要任何人相等，那萬一兩個人生成的公私鑰對相同。怎麼辦？比如說有人想偷取比特幣，一種方法是不停的產生公私鑰。然後對比一下我產生的公鑰。跟區塊鏈上某個已有的公鑰是不是相同。如果是一樣的話，就可以用私鑰把這個帳上錢給偷走。這種攻擊方法從理論上說好像是可以的。但是實際當中是不可行的。比如說你是 256 位的 hash 值的話。產生相同的公私鑰的可能性是微乎其微的。比如你有一台超級計算機每天產生大量的公私鑰對。出現來兩個人的公私鑰對相同的情況概率也是可以忽略不計的。這個概率比地球爆炸的概率還要小。到目前為止還沒有發現那個人用這種方法。能夠攻擊成功的先例。這裡要強調一點，我們這裡假設。產生公私鑰的時候有一個好的隨機源。這叫做 a good source of randomness。生成公私鑰的過程顯然是隨機的。如果選取的隨機源不好的話，那麼前面的分析就不存在了。就會出現兩個人的公私鑰對生成的是一樣的。比特幣中用的簽名算法不光是，生成公私鑰的時候要有好的隨機源。之後每一次簽名的時候也要有好的隨機源。只要有一次簽名用的隨機源不好的話，就有可能洩露私鑰。然後就全完了。這一點大家要一定注意。
我們講了兩個功能一個是 hash，一個簽名。這兩個功能是可以結合起來使用的。比特幣系統中一般是先對一個消息求一個 hash，然後再對這個 hash 值簽名。