Blockchain and Bitcoin Brief introduction for entry level programmer

yhorngProgramming

What kind of problem blockchain try to solve?

跟 Blockchain (區塊鍊) 功能最相近技術，我認為是 P2P 的檔案分享。就是多數的使用者，在網路上分享自己硬碟裡的檔案，當檔案不完全時，可以從其他人的電腦裡找到失落的片段、分享、下載、並補齊。在使用的意義上跟 Blockchain 其實很像。

P2P 的檔案分享有幾個問題，最致命的是無法確保你下載的檔案真的就是你要的，有使用過的應該都遇過檔名和下載下來的東西完全無關的事情 (像是下載了 “cplusplus_class_102.mp4” 結果裡面是明日花綺羅的最新力作之類的)。

而 Blockchain 的字義上就是要把一份資料 (一個檔案當然也是一份資料) 放在一個叫 Block 的資料結構中，連結成一個 Chain， 使用者有權取得所有的資料，也可以把資料加在 Chain 的最後面，但是不准修改已存在的資料。因為有防止使用者修改線上存在的文件的機制，所以可以在分散是系統下維持文件的正確性和安全性。

How to do it?

一個最簡單的 Block 的寫法是

class Block
{
  int index;
  Byte[] data;
  Byte[] previous_block_hash;  
  Byte[] this_block_hash;
};

其中 this_block_hash 的計算方法如下

this_block_hash = hash( index, data, previous_block_hash );

因為 Hash 的不可逆 (well, at some level)，當使用者要更改 Chain 內的某一個 Block，他需要重新計算與更動所有 Block 的 hash 資料。在分散式系統中，當資料衝突時，我們把佔多數的資料視為正確，因此在 Blockchain 上，要更動某個存在的 Block，除了要更新整個 Block 外，還要同步更新超過百分之五十的其他使用者的電腦資料。當使用者數量多時，幾乎是不可能的。這也就是 Blockchain 維持資料的不可變更性的基礎。

Hash

Hash 是把資料壓縮重整成一小塊類似指紋的小資料或字串，轉換出來的資料或字串稱為 Hash Value 。理想狀態下，這是不可逆的，也就是我們無法把 Hash value 還原成原始資料。

隨便舉個簡單的例子吧。我們把英文字 A 到 Z 標註成 1 到 26，然後把每一個英文單字轉換成一個整數，像是 book 的整數是 2151511，因為 b 是 2，o 是 15，k 是 11。然後我們把資料中獨立的英文單字加起來，就可以當成是一種簡單的 Hash function。像是 “this is a book” 就是 “208919 + 919 + 1 + 2151511″，Hash value 為  2361350。

我們可以很簡單的從 “this is a book” 算出 2361350。但是要從 2361350 還原成 “this is a book” 相對的很難，因為窮舉法是很耗時間的。

當然以上的 Hash algorithm 漏洞百出，像是資料只有一個單字時的處理，或是有很多種組合都可以對應到同樣的 Hash value 的問題等等。

設計的越好的 Hash algorithm 越該滿足以下的特性

  • 避免不同的資料有相同的 Hash value
  • 避免類似的資料有類似的 Hash value
  • 極大化從 Hash value 還原成原始資料的難度

Private / Public Key

接下來是確保建立新的 Block 時的安全性，或說白話點，如何防止別人冒名偽造新資料，像是我冒用你的名字賣你的 Bitcoin 之類的。

先從密碼學的基礎複習起。

非對稱加密是用一組 Private Key 和 Public Key 將加密和解密的工作分開。Private Key 可以產生 Public Key。在 SSL 中，receiver 用自己的 Private Key 產生 Public Key 再把 Public Key 送給 sender，sender 用 Public 加密資料並送給 receiver。receiver 再用自己的 Private Key 解密資料。因為 Public Key 不能用來解密，所以資料在網路上是無法被打開或修改的 (i.e. 無法用中斷攔截的方法駭客)。

順帶一提，產生 Private Key，或是用 Private Key 產生 Public Key 的方法請參考 Elliptic Curve Cryptography。特別提這點是因為在 Bitcoin 中，所謂的 address 就是用 Elliptic Curve 的座標 (x, y) 加上版本資訊和 checksum 組合出來的，這部分不會在這篇文章中說明。

很重要的一點，Private / Public Key 也可以反過來用，也就是 Private Key 用來加密而 Public Key 用來解密，這是下面會提到的 Digital Signature 的基礎。

Digital Signature

進入正題，防止別人冒用你的 “名字” (whatever it means) 建立資料的方法，就是提供一些只有 Private Key 持有者和資料建立者才能提供的資訊。這個 “資訊” 我們叫 Digital Signature。

最簡單的 Digital Signature 的產生方法如下

  1. Sender 將資料 Hash，並用 Private Key 將 Hash 加密後叫做 Digital Signature。
  2. Sender 送資料、Public Key、和 Digital Signature 送給 Receiver。
  3. Receiver 用 Public Key 解開 Digital Signature 並比較是否跟資料的 Hash 值相同。

因為只有 Sender 擁有 Private Key，所以能產生 Digital Signature 的只有 Sender。但所有人都有 Public Key，所以所有人都可以確認是否 Digital Signature 跟資料相符，這就是 Digital Signature 的基本概念。

簡化的說，就是以下二個 function

Byte[] sign( byte[] private_key, byte[] data);
bool verify( byte[] public_key, byte[] data, byte[] signature);

在 Bitcoin 中每個使用者都持有自己的 Private Key，當然，是不公開的。但在 Digital Signature 中，使用的方法更為複雜。除了會用到 Elliptic Curve 的座標 (x, y) 外，也會加入亂數做為資料的 prefix。

對了，因為 Bitcoin 所謂的 “帳號” 或 “使用者” 只是一個 Private Key，所以硬碟一壞，Private Key 不見了，你的 Bitcoin 就再也找不回來了。從這個層面來說，Bitcoin 是終究是會通縮的 (笑)。

Bitcoin 的交易

Bitcoin 在使用 Blockchain 的技術時，是將交易量當作 Block 中的資料，像是 A 送了 3 個 bitcoins 送給 B 之類的。因為 Block 中並沒有記錄該 “帳號” 的 Bitcoin 總量，所以在做一筆交易時，都需要回顧過去的所有交易，才知道目前 “帳號” 內有沒有足夠的錢來完成這次的交易。

Bitcoin 的網路時間差攻擊

假設一個使用者 A 擁有一個單位的 Bitcoin，A 同時送這一個 Bitcoin 給 B 和 C 二人。當然，A 給了 B 錢就不夠給 C，同樣的，給了 C 就不夠錢給 B。但是在沒有中心管理機制的分散式系統中，同時送二筆或多筆交易出去，利用網路的時間差搞亂系統是很簡單的。

Proof of Work

為了防止這樣的事情，我們用 Proof of Work (POW) 這個機制來確保一個時間只會完成一筆交易。新資料 (Block) 要加入 Blockchain 時的流程如下

  • 將新的 Block 放入 Pending Pool
  • 在 Pending Pool 中利用 POW 決定下一個要加入 Blockchain 的 Block
  • 將該 Block 加入 Blockchain

而 POW 說穿了只是個利用數學將每一筆新資料加入 Blockchain 的時間加長。假設以下的 Hash Function

// hash a data concatenate with random_data and return an integer
int hash( Byte[] block_data, Byte[] random_data );

如果我們要求，要找到回傳的數字小於 10 的 random_data 才能把 Block 加入 Blockchain 中 ，使用者們就需要花時間去嘗試各種組合，而我們要驗算時卻不用花甚麼時間，這就是 POW 的基本概念。

當然，算這種東西要花 CPU power，為了獎勵肯幫忙一起算的使用者，Bitcoin 會提供交易獎勵 (交易費?) 給算出來的使用者，也就是說每一筆成功交易都會產生新的 Bitcoin，這種行為叫 “挖礦 (mining)”。

Bitcoin 是有總量管制的，每四年就將產出總量減半，會在 2140 年全部挖完，現在挖了約八成五。

Public and Private Blockchain

在 Bitcoin 中，所有的使用者都是匿名的，或是說更準確一點，所有的使用者都只是個 Private Key。這樣所有人隨時都可以加入並看到所有資料的 Blockchain 叫 Public blockchain。

當然我們可以限制 Blockchain 只能給限定的人或是需要認證的單位才能使用，這種 Blockchain 叫 Private Blockchain。像是有人將門禁系統套用在 Blockchain 上，當然看的到出入資料的 “人” 或是能加入新的出入資料的 “門” 都是要控管的，這種都要用 Private blockchain。

Proof of Stake

在 Proof of Work 中，誰的 CPU 運算能力越強，就越可能提早算出問題並拿到獎勵。在這種前提下，每個使用者的條件是不一樣的，也因此有所謂的 “聯盟” 出來，聚集複數人的力量來取得獎勵。

而 Proof of Stake 是將 “算出問題” (again, whatever it means) 的機會平均給每個使用者，而非 CPU 越強就越有利。

這種概念可以套用在不那麼怕時間差攻擊的東西，像是用 Private Blockchain 的停車資訊系統，如果還在每一個 Block 要花十分鐘加入，那不就被罵到臭頭嗎? 當然有些虛擬幣也是用 Proof of Stake 來增加其公平性和當吸引人加入的賣點。

結語

這篇文章是在幫同事上課時整理出來的，本來只是寫在筆記本上，想想有點可惜所以重寫了一份在這。同事會想要了解 Blockchain 是因為這個技術最近大量的被提起與用在各種地方，像是門禁、停車、法務合約等等上面。但老實說仔細想想 Blockchain 的技術和特性，我個人覺得很多應用並非真的有其必要，與其說是技術，不如說是商業上的考量，像是門禁或停車資訊這種東西用分散式系統的好處是甚麼? 嗯…

Anyway，基本的介紹結束了，有興趣的可以更進一步的去了解加密的部分、或是 PoW 處理時間差問題的部分囉。