密碼學/區塊鏈筆記

in #cn7 years ago

起google都搵到唔少Bitcoin簡介文,但係通常都係寫得好簡單,寫左幾個特點出黎就當解釋左。
咩「去中心化」
「掘bitcoin即係解一個好複雜既方程式組」
「blockchain安全性非常之高」
但係又唔講果條方程式係咩,點解咁安全又會有新聞話bitcoin比人偷左

所以我睇緊書學cryptocurrency底層既理論同技術
唔敢話好識,只係想一路睇書一路做筆記,順便分享下比大家睇。
有咩理論問題可以拎出黎討論一下。

我係由理論層面出發,想知道cryptocurrency係點樣implement
「邊個faucet好用」
「邊個exchange好用」
「邊隻altcoin值得投資」
「join邊個mining plan最快回到本」
呢D我真係唔係好識

如果你有技術上既問題都可以post出黎大家研究一下。

因為cryptocurrency入面最出名既係bitcoin,所以好多時候都會用bitcoin做例子
而且bitcoin係始祖,其他altcoin都係改進左bitcoin既弊病而誕生
要明白altcoin有咩好,就要先明白bitcoin有咩唔好
要真正明白Bitcoin,就要學識最基本既cryptography先。
所以會先講下cryptography既基本概念先

初頭諗住講下
cryptographic hash function
digital signature

然後再講下
bitcoin既address構成
咩叫做block, 咩叫做blockchain, 咩叫做mining

chapter 1 (Cryptographic) Hash function

大家平時download software既時候可能都見過checksum。
checksum係用黎比你驗証download落黎既file係咪corrupt左。
例如download VLC Player既時候
checksum
佢SHA-256既checksum係9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd
download完之後你可以行command睇下個checksum夾唔夾

bash-3.2$ shasum -a 256 vlc-2.2.6.dmg
9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd vlc-2.2.6.dmg

SHA其實就係一款hash function, 全名係secure hash algorithms
SHA可以大致分為SHA-1, SHA-2, SHA-3
SHA-256係SHA-2既其中一種,佢叫做SHA-256係因為佢既output size係256bits
頭先個例子入面, 9826a85aab0c6dca2361c70a97fa12d8f2aa140328bdc80e68b659f9228f22fd其實係16進制
轉番做2進制黎表示既話:
1001100000100110101010000101101010101011000011000110110111001010001000110110000111000111000010101001011111111010000100101101100011110010101010100001010000000011001010001011110111001000000011100110100010110110010110011111100100100010100011110010001011111101
唔信你可以數下,上面有256個位。

hash function既input係一個file, 或者任何可以用數字黎表示既野
而output就係一串好長好長既數
比多幾個例子大家(output用16進制表示)
SHA256("I am underpants")=37225F6B3F4A62E6FA48BC1A00244EBCD371E752227C55A48100EFCBF2466BDE
SHA256("I am underpants.")=854E461F648B3317B4C9A47A611176F4775DC01B123978CB0AAB406CBF2BEA56
SHA256("I am underpants1")=66CC10677AA3C55C4F02E8D45B4DD5104F553C5072D681E28A194ED500F987A7
SHA256("I am underpants2")=11FAFDCEC29B4907ED5DAE61E0AD0BF19B64A56801689102A2980D781E35147E
留意input入面既"係無pass入去function, 只係用黎表示input係一條string
大家可以見到,條input string只係有一個字母唔同左,成個output係完全唔同

咁要符合咩條件先可以叫做cryptographic hash function呢?

  1. 要好快就計得到
    當然唔係講緊人肉可以好快計到,而係電腦可以好快計到
    一部家用電腦閒閒得一秒鐘可以計到2000萬次SHA256
    如果用埋GPU行parallel processing仲可以一秒幾億次

  2. 你估我唔到(hiding / pre-image resistance)

你比個hash function output我,我係無好快既方法估到你個input係乜。
換句話講呢個係1-way function. 所有有inverse既function 都唔係1-way function
例如sin, cos, tan就唔係1-way, 因為有時機都唔洗禁就知input係咩
sin(x) = 1
=> x = pi/2

如果果個係cryptographic hash function
SHA256(x)=7d1a54127b222502f5b79b5fb0803061152a44f92b37e23c6527baf665d4da9a
咁x=咩呢???
如果我唔開估既話,你係好難好難好難搵得到個x係"abcdefg"
因為SHA256既inverse function係無closed form, 甚至連approximation既close form都無
如果真係要估,唯一方法就即係暴力破解,由0開始逐個逐個慢慢試。

  1. 防撞(collision resistance)
    就算天才都搵唔到兩個唔同input,經過hash function計算後得出同一個output
    留意我係話「天才都搵唔到」,唔係話呢D inputs唔存在。
    事實上呢D inputs一定存在。

用一個簡單既例子(Birthday Problem): 你有無可能起你既facebook friend list入面搵到兩個人係同一日出世?一定有可能。
一年最多得365日(唔計潤年),假設你有365個朋友,可能真係咁「橋」你365個朋友都係唔同日子出世。
但係如果你有366個朋友,咁就肯肯定,至少有其中兩個人既生日日期一樣。

同樣道理
SHA256既output係256bits, 即係話佢既可能既output數只有2^256個。
(每個bit只可以係1或者0 兩個可能性, 有256個位,所以係2^256)
只要你有恆心試下2^256+1咁多個input, 就肯定搵到其中兩個inputs會得出同一個output

因為好重要,所以要重覆多一次:導致SHA256 output一樣既inputs一定存在,問題係搵唔搵得到/有無快既方法搵得到。
SHA256面世到而家都未有人搵到唔同input但係一樣output既case
因為output數量實在太多
2^256大約等於10^77, 而呢個世界上見得到既atom數都只不過係10^80

你想挑戰一下既話,可以去http://passwordsgenerator.net/sha256-hash-generator/
試下入唔同既string,睇下SHA256既output
如果你真係咁犀利搵到兩條唔同string ,得出黎既SHA256 output係一樣,請通知一聲,呢個發現夠你揚名立萬

用數學既方法黎表示上面兩個特質:
x1, x2係input
y1, y2係output

Hiding:given y1, 好難好難好難搵到x1 such that SHA256(x1) = y1
collision resistance:好難好難好難搵到x1, x2 such that SHA256(x1) = SHA256(x2)

數學家發明既hash function有好多款
但就唔係款款hash function都符合到上面兩個要求
例如SHA family入面既SHA1(output length: 160 bit)
美國政府起1995年發表SHA1, 所有科技巨頭包括Apple Google Microsoft 當時都用左呢個cryptographic hash function
用暴力破解SHA1既話計2^80次先會搵到一對input導致collision
直到2005年,一個中國女數學家-王小雲 發現左個方法,只需要計2^63次就會搵到collision input
注意王小雲只係諗到個方法,但係果時佢都未真係搵到x1,x2 such that SHA1(x1)=SHA1(x2)
要再隔多12年,即係2017年既二月, Google先成功製造到兩份唔同既PDF file , 佢地既SHA1 output係一樣既
所以而家SHA1已經無資格做cryptographic hash function, 只能夠做一個普通hash function

如果大家有留意chrome既新聞,應該聽過chrome由v.56開始唔再支援SHA1生成既certificate
就係因為google知道chrome已經唔再安全,通過到SHA1認證都唔代表乜野
唔係話SHA完全無用,例如git而家仲用緊SHA1黎做file integrity check
只係大家已經唔可以倚靠呢個function黎保護系統

hash function仲有好多值得講既topic
例如birthday attack: 160bit output length既hash function點解只需要2^80步就可以暴力破解(i.e. 搵到collision input)到collision,而唔係2^160步?
點為知好難好難好難搵到?有無單手游出公海咁難?

講左咁耐,究竟hash function同bitcoin有咩關係?
SHA256正正係所有礦工日計夜計既數:Find x such that SHA256(x) < target
而且成條blockchain之所以安全,之所以無可能被篡改,都係多得SHA2既collision resistance property
詳情就留番後面既chapter先講