密碼學/區塊鏈筆記

in #cn • 7 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先講

7 years ago in #cn by
$0.00
    1 vote
    Reply 0