何謂區塊鏈?(二) - SHA256 與 礦工

上一篇提到礦工要鬥快解一個數學問題,就算用電腦來解這個數學問題也要花上幾天幾夜,那到底是甚麼問題要讓電腦也要算這麼久?

答案是: SHA-256

SHA是Secured Hash Algorithm 安全散列算法的簡寫,256是因為它的輸出有256個位元。

有時候在網上下載軟件的時候,網站會提供一個checksum 讓大家比對:

SHA256

上面是下載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是怎麼算出來的吧!
小篇將於另一文章詳細解釋。


延伸閱讀