何謂區塊鏈?(二) - SHA256 與 礦工
上一篇提到礦工要鬥快解一個數學問題，就算用電腦來解這個數學問題也要花上幾天幾夜，那到底是甚麼問題要讓電腦也要算這麼久?
答案是: SHA-256
SHA是Secured Hash Algorithm 安全散列算法的簡寫，256是因為它的輸出有256個位元。
有時候在網上下載軟件的時候，網站會提供一個checksum 讓大家比對:
上面是下載VLC Player的例子，它的SHA-256 checksum 是9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd
這麼長的又數字又字母，其實都是一個數，只是用了十六進制來表達的64位數，因為電腦裏的東西通常都是用二/八/十六進制來表示的， 硬是要把它變回十進制也可以: 68819855110913045309627488261796352778926607536183342041121832740778402587389
SHA-256 簡介
在SHA-256 的結果最小是: 0000000000000000000000000000000000000000000000000000000000000000 最大是: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
用十進制來表示的話
最小是0
最大是115792089237316195423570985008687907853269984665640564039457584007913129639935
或者用簡單一點的方式來表示: 2^256
簡單介紹一下16進制
F>E>D>C>B>A>9>8>7>6>5>4>3>2>1>0
把A/B/C/D/E/F 理解成10/11/12/13/14/15就對了
總之你把SHA-256 checksum 看成是一個超級大的數就可以了
下載完成後，如果你想檢查你剛下載下來的檔案，是不是真的VLC Player，還是黑客已經竊取你的網線，並偷偷掉了包讓了下載了一個木馬程序 你可以跑下面這個命令:
在Mac OS環境裏:
[i]bash-3.2$ shasum -a 256 vlc-2.2.6.dmg
9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd vlc-2.2.6.dmg[/i]
在Windows環境裏
D:\>certutil -hashfile vlc-2.2.6.dmg SHA256
SHA256 hash of vlc-2.2.6.dmg:
9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd
你算出來的SHA256，跟網站提供的SHA256 checksum是一樣的，這便証明你的檔案沒掉包，沒損壞，可以信任。
因為這個世界上，隨了你剛下載下來的檔案，幾乎沒有可能找到另一個檔案能算出同一個SHA256 checksum，留意我只是說幾乎沒可能，不是說肯定沒可能，後面會再解釋
其實不只是檔案可以算SHA256，隨便一個詞，甚至是句子都可以拿來算SHA256，比如說:
SHA256("apple")=3A7BD3E2360A3D29EEA436FCFB7E44C735D117C42D1C1835420B6B9942DD4F1B
SHA256("Apple")=F223FAA96F22916294922B171A2696D868FD1F9129302EB41A45B2A2EA2EBBFD
SHA256("orange")=7EB7F358DECB954ACAEF10BA4249456D2359F3256EEFD6D4A914DA39D85F8776
SHA256("Orange")=78E7771B8B46E11DDB34BA48887E1330525215F96D94778980D1186E6F09F6B4
SHA256("Bill Gates pay me 10 dollars")=E1AEB27164CBA0E563069BC557B990B52E1387DD4DAEB15CB85E1BDDC0C53F9F
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.")=C6BF247E46CD27AAA2EEA0CC62E1FD9DAF6CA4DA29C7B223B0BBF1276A348191
在密碼學上，SHA256是一個密碼雜湊函數(cryptographic hash function)，這類函數有甚麼特點呢?
1. 對於電腦來說，給定一個輸入，很容易算出SHA256的輸出， 意思是，我給一個詞"apple"，要電腦算它的SHA256，幾微秒就能得出3A7BD3E2360A3D29EEA436FCFB7E44C735D117C42D1C1835420B6B9942DD4F1B
2. 給定一個輸出，很難很難很難找出輸入。 比如，我告訴你某某詞的SHA256 是3A7BD3E2360A3D29EEA436FCFB7E44C735D117C42D1C1835420B6B9942DD4F1B 要不是我剛剛讓你看過的話，你幾乎沒可能逆向推敲出輸入是"apple"。
用數學一點的方法來說，SHA256的逆函數(inverse function)是不存在的，連估算(approximate)的方法都不存在。
3. 給定一個輸入A，很難很難很難找到另一個輸入B，such that 它們的SHA256 結果是一樣的。
就是說，除了apple之外，你能找出另一個詞/另一個檔案，它的SHA256輸出跟apple一樣是是3A7BD3E2360A3D29EEA436FCFB7E44C735D117C42D1C1835420B6B9942DD4F1B嗎?
幾乎沒可能找到，但是...
找不到不代表不存在
找不到不代表不存在
找不到不代表不存在
很重要所以要說三遍
用鴿巢原理(piegon hold principle)就能推理出不同的輸入得到同樣的SHA256輸出的例子，肯定是存在的。
SHA256輸出只有2^256+1個可能性，但是輸入有幾乎無限個可能，SHA256的輸入長度上限是(2^64)-1個bit，即是2Exabytes
(1 Exabyte = 1024 Petabyte = 1024^2 Terabyte = 1024^3 GB)
總之possibe input 數量比possible output 數量要大上不知多少倍。
用一個生活化例子來解釋:
如果你有367個朋友或以上，那麼肯定有其中兩個朋友，他們是同一天生日的。
因為一年最多就只有366天(潤年也算)，就算湊巧你頭366個朋友全部都是不同日子生日的第367個朋友無可避免要跟頭366個朋友的其中一個相沖。
所以肯定存在兩個不同的輸入，它們的SHA256輸出是一樣的。只是到目前為止都沒人找得到，如果你這麼天才找得到這一對輸入的話，我估計google也要邀請你出發表演說解釋一下你是怎樣找到。
為甚麼花這麼大的勁去解釋SHA256?
因為整條區塊鏈的安全性就是靠SHA256去維護，而且礦工花錢買的礦機就是專門用來算SHA256
礦工的任務就是算SHA256
例子:礦工手上的區塊裏面記載了兩條交易:
"Bill Gates pay me 10 dollars."
"I pay you 20 dollars."
礦工要算的是找出一個x，such that
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.x") < 0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
後面這個數是(一個0後面跟著63個F)
當x=1時:
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.1") = A62072044E4CBCC83BE92A1D4C022266FC3E86A4A6EA71117DBDC0E2B5806762
當x=2時:
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.2") = 321D75F3E355EF880871494BAD829BEA48E890301CA527317A64FEEF7B99192F
當x=3時:
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.3") = 916DD5676C09B01B99750338AF91DF05825BEFB252DE4E7E6257C3B01E80CCB5
但是這幾個結果都比(一個0後面跟著63個F)大，因為它們的第一位數都不是0，所以1/2/3都不是答案。
礦工一直試一直試，一直試到...
x=12345651231654798421231654556
SHA256("Bill Gates pay me 10 dollars. I pay you 20 dollars.12345651231654798421231654556") = 06AEB4DB892E1A5090657F25D94E509162A0D6D8B7B7718A2E8EBAE176EF7D50
終於找到了!! 這個數比上面說的(一個0後面跟著63個F)要少一點點， 這時候礦工就可以對外宣布，我找到了，下一個憑空生成從天而降的比特幣是屬於我的啦!!!(如果沒其他礦工同時找到的話)
當礦工算出答案後，主要作用是:
1. 挑選寫下一個block 的礦工2. 確保將來無人可以修改這個block
更多礦工的運作，請留意下一篇文章。
什麼是Difficulty?
上面的例子裏，SHA256輸出上限是(一個0後面跟著63個F)，現實世界裏的比特幣網絡中，上限要比這個小很多很多。
上限是根據網絡中的difficulty定出來的，而difficulty又是根據網絡上的算力定出來的，越多人一起算，難度越高。
拿比特幣第510697個區塊來說說看:
https://blockchain.info/block/00000000000000000040d11e7840b9b737aeae79d8075f850c3e8f4fe1d1e075
它的difficulty是3007383866429
當前上限可以用公式2^224/3007383866429
大約是000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF(18個0後面跟著46個F)
所以礦工要找的就是: "我手上的1000條交易，到底要拼上那一個數或詞，得出來的SHA256會比(18個0後面跟著46個F)小?"
讓電腦算一次SHA256，很快就完成，但是在比特幣的世界裏，大概要算幾億億億次SHA256才能找到一個輸出比指定上限小。
現在整個網絡的總算力大概是20,000,000TH/s (2018年2月)
1TH/s 就是說一秒算1,000,000,000,000次 SHA256
所以現在是一秒算20,000,000,000,000,000,000次 SHA256
所有礦工加起來還要算大概600秒才找到一個答案，總共算了12,000,000,000,000,000,000,000次 SHA256
而你家裏的電腦一秒大概能算...1000次SHA256吧
所以只靠你家裏的電腦去算的話，12,000,000,000,000,000,000秒就能找到答案
大概是10^9個世紀的時間，你慢慢等啊...
說到這裏, 大家應該很有興趣知道SHA256是怎麼算出來的吧!
小篇將於另一文章詳細解釋。
上一篇: 何謂區塊鏈 BlockChain?
