區塊鏈技術概觀(二):資料分割與密碼學

作者 | 發布日期 2017 年 08 月 09 日 14:31 | 分類 Fintech , 數位貨幣 , 科技教育 follow us in feedly

前篇講到了如何利用大型流水系統來產生可取代傳統貨幣的數位貨幣系統,那麼這個系統為何稱做區塊鏈呢?我們接下來再做個技術概觀。



將流水帳資料分成區塊

傳統的流水帳有如電腦系統的 Log 一樣,將所有資料一行一行寫入,其實相當容易竄改,而且死無對證,加上一直不斷寫入也不能確定有沒有漏寫或少寫。為了解決這個問題,將資料按照出現的時間點切分成區塊就顯得必要了!那麼鏈又從何來的呢?

過去某些應用程式中,的確曾經出現過將連續性資料切分成許多小區塊的做法,且每個區塊都會使用一些有檢查效果甚至錯誤更正效果的檢查碼來確保它的正確性,好比 Checksum。如果我們把前一個區塊的 checksum 也帶入後一個區塊的內容,一起計算出後一個區塊的 checksum 會如何呢?馬上可以見到在這種資料結構下,如果想要更動某一區塊的內容,那就必需重新計算由目標區塊起往最末端區塊中所有 checksum!因此要更動歷史資料就變得很麻煩了!這樣子的資料結構由於前後密切相關,因此稱為區塊鏈。我們可以很簡單地看到,愈早的資料愈難以修改,因此愈早的資料愈安全,而最新的資料最不安全。

Proof-of-Works

在新型資料鏈技術中有一個很大的安全性保障就是 Proof-of-works。回頭看一下早期的資料鏈,如果依現在的電腦計算力,要重新計算十萬個 checksum 會有多難?就算用到 SHA3 加上一般 CPU 來做,恐怕也不用幾分鐘吧?(筆者的 i 牌 2680 就可以輕鬆達到近每秒 1K hash 的效能了),如果用 SHA-1 就更驚人了,一用上 GPU 大概沒幾秒就破光光了。因此可以發現,光是使用傳統 checksum 概念全然沒有安全性可言。當初設計比特幣的中本聰先生就導入了原本用以防止 SPAM Mail 的 Proof-of-Works 概念,讓每個區塊的「Checksum」代換成「種子數 + 特定範圍內的 hash 解」,這樣就達成了確保每個區塊都要花上不少時間來包裝。

所謂的 Proof-of-Works 概念相當簡單,只是一般人很難一下子理解。電腦傳送資料時常會導入 checksum 的觀念,以防止資料在傳輸過程有錯誤。因此在資料結尾加上 checksum 是天天在做的事,Proof-of-Works 只不過是把資料尾端加上一個種子數字,套入一個數學函數,去計算結果的值,我們可以在協定中設計好,這個值必需符合某種規範才能叫正確解。通常這個種子數會由 0 開始一直往上加到極大,如果條件很難,那麼計算出結果就要試非常多次,也等於會花掉很多時間。因此叫做 Proof-of-Works。

我們來玩一段非常簡單且有「笑」的 Proof-of-Works:假設我們要傳的資料在數字層面來看,資料碼是 0×F0、0×A1、0×08、0×32,就這樣 4 個 byte 的資料好了,如果設計一個 Proof-of-Works 規則是:將 4 個 byte 做無進位相加起來,再加上一個 byte 的種子數,它的結果必須是 0×00,那麼我們由 0 開始要試幾次才能找到解呢?我們先把 4 個數字做無進位相加得到了 0×CC,再加上種子數字 1,得到 0×CD……一直試到第 51 次,在種子數為 51 的時候終於找到解了!所以 Proof-of-Works 的解答就是(51,0),而且我們試了 51 次。當然任何一個學過密碼學的人現在應該都笑到抽筋了,因為加法是可以逆推的演算法,也就是現實世界裡,當我們把 4 個數字加起來得到 0×CC 時,我們馬上就可以用 0 去減 0×CC 得到 51,根本連試的必要都沒有。以上只是給各位一個概念,Proof-of-Works 是如何運作。

Hash 函數登場

那麼世界上有適用於實做高強度,且效果可預期的計算方法嗎?有的,就是密碼學常用到的各種 Hash 函數。密碼學用的 Hash 函數都要符合幾個特性才算設計成功:

  • 輸出長度最好固定,不會因為資料變動一個 Byte,輸出長度就爆增 10 個 byte。輸出的空間大小也要夠大,否則用猜的就可以暴力破解了。
  • 隨機性要很好,Hash(雜湊)的用意就是將一大段數字,映射到一個目標空間中,好比 SHA-256 就是將輸入的資料,映射到 256 bit 的數字空間任意一個數字。因此要有隨機很好的特性,否則如果特定分布在某個段落,駭客也不用真算了,只要去猜那幾個段落就會有很高的中獎率。
  • 不可逆推,我們無法像加減法一樣,看到結果就知道原本的數值(看看上面的例子就知道了)。
    傳統上 Hash 的使用方法是將資料丟進雜湊函數中,得到一個值,這個值基本上就代表那個資料在解答空間的映射特徵,其他文件與它有同樣值的機率小到可視為 0。因此我們可以靠檢查雜湊值來知道文件是否有被修改或傳輸錯誤。

Hashcash 運作觀念

當年垃圾信件氾濫又沒有很好的擋信方案時,有部分人士提出 Hashcash 的觀念,來確保你不是寄垃圾信的人,做法就是標準的 Proof-of-Works。Hashcash 當時要求寄件者在把 Email 內容加上一串種子數字做 SHA-1 160 bit 雜湊運算,如果得到結果它的前 N bit 都是 0,那麼就把那個種子數字及 hash 結果加在信件標頭中,這個標頭顯示的是前 20 bit 都為 0 的強度要求以及種子數和解。

X-Hashcash: 1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi

當時要做到求出前 20 bit 為 0 的解需要花掉數十秒,因此這個方法可以確保送信的 CPU 每十至數十秒才能送出一封信,對於一般寄信人的影響應該不大,但是對要發送上萬封圾垃信的人影響就很大了。我們可以簡單由機率論來推出要試幾次才能得到解:如果 SHA-1 非常隨機,那麼要求出前 20 bit 都為 0 的次數就差不多在 2^20 這麼多次(1Mega = 1048576)。如果只要第一個 bit 為 0,那麼只要兩次就差不多找到了。

那麼收件方如何確認對方真的找到解了呢?當然只要做一次快速驗算就知道了,在寄信者的標頭已包括了正確的種子數以及求出來的解,因此拿來做一次 SHA-1 運算馬上就可以知道正確與否了。這樣子一來,寄件者非常辛苦忙了幾十秒,但收件者很輕鬆就搞定了,也是 Proof-of-Works 重要的特性之一。而 Hashcash 被採用的原因之一,則是它提供了不同難度的設定,可以將它寫在協議中,這點也很重要,試想網路中如果只有一台挖礦機,絕對擋不了駭客攻擊,但是如果有成千上萬台挖礦機,而難度維持不變,那麼也無法維持平均每 10 分鐘包裝出一個區塊的速度。因此比特幣的設計就會以近兩週的包裝速度來為基準計算是否該將難度提升。

比特幣如何做?

Hashcash 誕生的時間很早,且 SHA-1 編碼事實上後來也被發現可用較短時間找出解的破解方法,比特幣的設計者當然不可能在多年之後還照抄。我們先來看看比特幣如何把資料串成鏈:比特幣的區塊大致分成兩區,第一區叫標頭,第二區則是放置交易資訊。比特幣會將 Proof-of-Works 的結果,以及前一個區塊的 Proof-of-Works 放在標頭,標頭中並沒有交易資訊,但是有第二區中的交易資訊做的 hash,這些交易資訊 hash 出來的結果,會依馬可夫鏈的排列方式寫在標頭中一個叫 Merkle Root 的欄位,當區塊在做 Proof-of-Works 時,事實上只做標頭部分,但因為交易資訊的 hash 已放入標頭了,因此若單獨改變交易資訊而不改變標頭的 Merkle Root,其他人會發現交易的 hash 值和標頭的不符合,所以雖然交易資訊本身沒有進區塊鏈運算,但是安全性仍然很好。

Block #477922

Summary
Number Of Transactions 1657
Output Total 26,295.84722444 BTC
Estimated Transaction Volume 2,449.84737287 BTC
Transaction Fees 1.19323829 BTC
Height 477922 (Main Chain)
Timestamp 2017-07-28 06:41:02
Received Time 2017-07-28 06:41:02
Relayed By AntPool
Difficulty 860,221,984,436.22
Bits 402736949
Size 996.843 KB
Version 0x20000002
Nonce 1445765072
Block Reward 12.5 BTC
Hashes
Hash 0000000000000000012bfae6f7ad25c56e53729ff9adfee157b6c7f28c4201d4
Previous Block 00000000000000000036154762753295f46fa39b609c6f676f2fd60406412ecd
Next Block(s)
Merkle Root 492d9973d12330ade7f103a44926926830d9fadb5a811baede590b1dfd35255f

 

從上圖中我們可以看到比特幣的 Proof-of-Works 是採行 256 bit 的輸出結果,那是因為比特幣用的是改良後的 SHA-1,計算結構很相近但其中部分參數不同,輸出的結果也由 160 bit 擴增至 256 bit。不過在 2005 年一篇論文中已證實 SHA-1 有潛在危險,有機會較少的嘗試次數就破解(事實上在今年初,Google 的研究團隊的確找到方式,成功在有限時間內破解 SHA-1。所謂破解的意思是,當文件被小幅度修改時,原本 SHA-1 值就會隨機改變,要再利用短時間且小幅的改變文件其他部分來找到同樣 hash 值的機率機乎為 0,但利用破解手法就可在短時間且只要適量的計算力就辦到)。

SHA-256 既然是 SHA-1 的變體,那麼同樣的漏洞自然也存在(但由於空間較大因此目前還是比較難破解),比特幣為了安全性問題使用 Double SHA-256,也就是 Hash 結果 = SHA256 ( SHA256 ( 本文內容 ) )。這樣子就算使用速算破解法難度還是會拉高到天文數字,所以我們在比特幣標頭看到的 Proof-of-Work Hash 值都是 Double SHA256。

我們在標頭還可以看到種子數的欄位,其實由這個欄位筆者就可以判斷出中本聰一定是一個年紀比筆者還大的老人,因為可看到一個幾近吝嗇而危害安全性的設計:它只有 32 位元!我們從機率論來倒推,基本上只要 Hashcash 的難度達到 32 個 0 之後,這個欄位就不夠用了,而目前比特幣的難度早就飆破天際了。看看上圖足足有 52 個 0!那麼為何不一開始就寫死足夠的長度在固定欄位使用呢?通常只有很老的工程師才會有這種壞習慣,因為以前電腦記憶體不足,網路不快,大家都省著用,沒到達必需擴增前都不想使用太多位元來放東西。現在的比特幣種子數只有最低的 32 位元放在 Nonce 欄位內,其他多出來的部分是 coin base transaction 中拿沒用的欄位來放,且協定沒有寫得很明確應該如何做,是靠開發者社群協議達成的。

標頭也有目前難度,過去 Hashcash 一次就往後跳一個 0,難度增加一倍,這是固定的倍增法,但比特幣為了維持更好的精確性,控制每分鐘左右產出一個區塊,所以沒有用倍增的方法(如果用倍增法,那麼只要調整一次難度,就會讓原本 10 分鐘可產生的區塊變成 20 分鐘),因為短期內的計算量增加根本不可能倍增,而是使用了只要 hash 值小於一個特定整數就算找到解的方式。

原本 Hashcash = 解答要小於 2^N(最前面的 160-N bit 要為零)
比特幣用的 Hashcash = 解答小於一個系統計算出的整數即可。目前的難度為 860,221,984,436.22

目前的比特幣區塊長度只定義到 1MB,因此如果短期內擠進太多交易量,就會有些交易沒有包到了。當然按照比特幣的定義,這交易絕不會隨便消失,會一直等到區塊使用量足夠包裝這筆交易時再被封進區塊鏈。

近來有不少交易都延遲得很嚴重,就是因為區塊空間不夠大,這和比特幣原本的設計精神有違,因此社群開發者也在討論將區塊空間放大 4 倍的方法(當然這被放大成一場比特幣大分裂的政治風暴又是可另外討論的議題了)。

(首圖來源:shutterstock)

延伸閱讀: