第一章｜密碼學與加密數位貨幣介紹
===
###### tags: `區塊鏈金融創新`

世界上各個國家的法定流通貨幣都必須控制總量以及防偽，而加密貨幣也必須要有相對應的防偽技術。對加密貨幣而言，它必須防止「混淆」，每一次的交易必須是獨立的，所交易的貨幣不能重複。與普通貨幣不同的是，加密貨幣的防偽靠的是技術方法而不是中央的貨幣控管機構。

:::success

:bookmark: **目錄**
:::spoiler

[TOC]

:::

## 雜湊

### 什麼是雜湊(hash)
將不固定的長度輸入雜湊函數中，將會輸出固定長度的數值，並且具備下列特點：

1. 可以輸入任意大小數值
2. 輸出固定大小數值，無法回推出原始值
3. 雜湊值必須跟著明文的改變而改變
4. 在合理的時間內計算出雜湊值

雜湊函數若須達到一定的安全性，必須到達以下目標：
1. 防碰撞（Collision-resitance）
3. 隱蔽性（Hiding）
4. 不方便解密性（puzzle-friendliness）

### 防碰撞


當X與Y輸入相同雜湊函數H()，若輸出結果相同，則這個雜湊函數便是會碰撞的雜湊函數，需要重新設計。反之，若是找不到任何碰撞，那麼我們則可以稱這個函數為「防碰撞」。

所有的雜湊函數都有可能找到碰撞，我們舉例某個能輸出256-bit的雜湊函數，若是窮舉計算$(2^{256}+1)$中的任意二數，便可以預知某兩個輸入值一定會相同。因為輸入集合遠大於輸出集合，意味著一定會發生碰撞。

### 隱蔽性

若某值r來自一個高階最小熵的機率分布時，便代表即使在最保守的情況下，r也有許多的可能性，簡單的來說就是很亂很安全的亂數。且如果在H(r || x)雜湊函數中，完全找不到x的值，那麼我們可以說雜湊函數H具備隱密性。

>熵(entropy)：
>熵是用來描述一個系統的混亂程度，換句話說，若一個隨機事件它的可能性越多，就代表它的熵越大。比如說：丟一個六面的骰子與八面的骰子，八面的熵會比較大。

> 最小熵（min-entropy）：
> 最保守的可能性。

> 高階最小摘（high min-entropy）：
> 最小墒最大的分布。熵越小，可能性越少，越不安全。所以高階最小熵的意思是，在可能性最保守的情形下，最多的可能性。比如說，某值由一個$2^{256}$面的骰子決定，這個$2^{256}$面骰子就是一個有「高階最小熵」的概率分布。

#### 承諾協議(commitment)
承諾協議是密碼學最常探討的應用，它分為兩個部分。

承諾函數：

com = commit(msg,nonce)
//commit函數是一個預防碰撞的雜湊函數。

驗證函數：

isValid = verify(com,msg,nonce)

#### 猜拳問題

若今天a與b在無法見面的情況下進行猜拳，a先將猜拳的內容寄信給b，若b先收到信，便可以寄出絕對勝利的答案。

透過承諾協議的加入，我們就可以避免這個情形生。


1. 今天A與B先亂數製造出nonce(唯一亂數)，並且將要出的拳先決定出來，透過commit函數製作出不可逆的雜湊碼。

2. A與B分別將承諾函數所產出的雜湊碼「成諾」給予對方。


3. A先將nonce與出拳傳遞給B。
B透過isValid驗證函數傳入A產出的承諾、亂數、出拳。
驗證函數會把Anonce與Amsg再一次使用承諾函數加密，再比較這一次的加密結果與A第一次傳來的「承諾」是否全等。
4. 若全等，B將會把他亂數與出拳傳給A，讓A進行同樣的判斷。

經過具有隱蔽性的雜湊函數的加密，在承諾協議下，A或B都無法以第一次的com(承諾)推導出對方出了什麼拳。第二次的交換後，將會以驗證函數再驗證所傳來的內容，若有一方不相等，則是說謊。

### 不方便解密性

對於一個雜湊函數來說，若無法在$2^n$的時間內找到輸出值對應的輸入值為多少，如：H(k || x) = y成立，那麼我們就稱這個函數為不方便解密的雜湊函數。

#### 搜索難題
應用不方便解密性可以設計出搜索難題，而搜索難題的特點在於，需要搜索非常大的集合空間，在沒有捷徑的方式找到解答。

一個搜索難題會包含：
*　雜湊函數H
*　一個謎題id，取自於高階最小熵的機率分佈
*　一個目標集合Y
這個難題的X必須滿足下列公式：
> H(id || x)∈Y

如果H()有一個n位的輸出，那麼就代表取值擁有$2^n$個。

若要解決這個難題，必須要找到一個x，並且輸出的結果落在在集合Y之中。並且，目標Y集合的元素數小於H(x)集合的元素數。Y集合的大小決定了這個謎題的難度。

謎題id取決於一個高階最小熵的分佈，代表這個id是純粹的亂數，不包含任何特徵。若是今天這個搜索難題不方便解密，代表我們必須透過隨機嘗試x的值，尋找落在Y集合中的正確解答。

比特幣的挖礦就是基於這樣子的搜索難題進行設計，礦工無法透過比隨機運算更好的策略來解答搜索難題，而透過計算，最先算出搜索難題者便可以獲得一定數量的比特幣作為獎勵。比特幣有一定的機制利用調整搜索難題的難度，控制比特幣的發放數量，創造比特幣的稀珍性與可信賴性。

## 雜湊指標與區塊鏈

### 雜湊指標（Hash pointer）


Hash pointer為一個指向被某個雜湊函數所保護的資料結構(data structure)的指標，它除了指標的功能外，還儲存了雜湊值(hash value)，便也帶有驗證某個資料結構是否被修改的能力。

### 區塊鏈

> 被雜湊函數保護的資料區塊可以透過雜湊指標形成一個鏈，便被稱為區塊鏈
>

每個區塊都會有一個Header，用來儲存雜湊指標，這個雜湊指標指向最近的一個區塊。依照雜湊指標的特性，Header不只替我們指向上一個區塊的確切位置，也擁有上一個區塊的摘要(被hash過的結果)，讓我們可以驗證上一個區塊的數值是否有被竄改過。


圖片中的每個元素指向上一個元素的指標就是雜湊指標。

#### 創始區塊（genesis block）

區塊鏈的最源頭，是不可修改的區塊，它儲存著最原始的雜湊指標。透過創始區塊的建立，我們可以確保整個區塊鏈的安全性與可信任性。

若今天，有人試圖要攻擊區塊鏈中的某個區塊，那就必須依需修改所有的區塊的雜湊指標。在向上修改雜湊指標的過程中，必定會遇到創始區塊的雜湊指標，但我們可以確定創始區塊絕對會在無法修改的地方。

#### 防竄改日誌（tamper-evident log）

在區塊中，我們會儲存日誌，當有人更改了上一個區塊的資料，那麼雜湊指標就能夠透過已經儲存的上一個資料的摘要，找到有人無故更變區塊資料的證明。

假設有人想要更改上一個區塊的資料，那麼將會被雜湊指標發現，因為雜湊指標中儲存著上一個區塊最原始的資料所加密後的摘要：


#### Mekle樹

這是區塊鏈的第二種資料結構：透過雜湊指標可以建立起二元樹，這棵樹就叫 Mekle tree也稱做 hash tree。


底層的葉節點原始資料的區塊，期它節點的區塊皆含有兩個子節點，並且這些子節點都有自己的雜湊指標。

所以若是有人要更改某個葉節點的資料，只少要改動有關路徑上的區塊直到遇到根區塊(根節點)。到達根區塊便無法修改（同創世區塊）。也就是說，我們只要記得根區塊的雜湊指標，就能確定這整顆樹是否有被修改過。

#### 成員資格證明

Merkel tree的一個特色是成員資格證明，他與上一個資料結構不同的是，證明某個資料區塊是否屬於某個Merkel tree非常簡單。我們只需要從根區塊開始，忽略掉其他部分，只驗證一條路徑是否符合雜湊指標所記載的內容，就可以驗證某筆資料是否為某棵樹的合法成員。

## 數位簽章

數位簽章代表一個人的身分，並且有無法模仿的特性。通常數位簽章透過非對稱加密實現，非對稱加密的特點是每一次的加密都會有公鑰與私鑰參與加解密。

### 簽章模型


公私鑰產生函數：

(sk,pk) = generateKeys(keysize);
// generateKeys產生一組公鑰與私鑰。
// 私鑰用於加密訊息，而公鑰則是所有人都可以用來驗證你所加密的訊息。

* sk：secret signing key(sk)：每一次簽名所使用的金鑰
* pk：public verification(pk)：驗證簽名真偽

簽名函數：

sig = sign(sk,message);
//sign負責將一段訊息和私鑰作為輸入，輸出是加密後的字串。

驗證函數：

isValid = verify(pk, message, sig);
//透過利用pk解密sig的訊息後，比對message是否相符

### 公開金鑰即是身分

public key 與 private key 必定是一同產生的金鑰，在數位簽章中，我們利用private key 加密我們的訊息並且散播簽名，所有人通過公開金鑰pk都可以驗證我們所散播的訊息與簽名。那麼我們可以說public key陳述(state)了這段訊息。

換句話說， private key 可以想像成真實隱密的你，而 public key 則是對外的公開身分(identity)。

#### 去中心化身份管理(decentralized identity management)

在去中心化管理的系統中，我們不用倚賴一個中央單位，就可以自己創造出新的身分。就像比特幣一樣，你隨時可以創造身份，或是同時擁有多個身份。而這些身分僅僅是某一組public key 與 private key 罷了。

對比特幣來說，這些身份(identity)叫做位址(address)，而這個位只便是public key hash過的結果，也代表每個比特幣使用者的身分。

## 簡單的貨幣加密系統

一個簡單的貨幣加密系統必須有下列功能：
* 創造貨幣，並且每個貨幣是獨立的（唯一序號）且可以歸屬於任何人。
* 利用數位簽章驗證每個貨幣以及交易的合法性。
* 任何人都可以追朔貨幣的交易歷史，但不能更改資訊只能被銷毀。

### GoofyCoin


上圖模擬一個虛擬貨幣的交易紀錄。

假設Goofy想要把某個它所產出的幣交給Alice，那麼對於整個區塊鍊來說，只是將新的持有者Alice的雜湊指標指向上一個交易。

#### 重複交易問題


在虛擬貨幣系統中每個錢幣都有自己的獨立性，並且透過雜湊指標進行指向，紀錄整個幣的交易過程。如上圖，若今天Alice一幣兩賣該怎麼預防？

### Scrooge Coin

面對GoofyCoin重複交易的問題，Scrooge Coin提出了解決方法。

在Scrooge Coin中有一個中心機構：Scrooge，負責驗證創建貨幣與交易的合法性。


Scrooge Coin系統中允許Scrooge建立起一個區塊鍊，每個區塊紀錄每次交易的ID、內容與上一個區塊的雜湊指標。

* 在第一次的交易中，假設Scrooge創造了10個幣給自己。
在Scrooge Coin系統中我們不會懷疑錢幣的可靠性，因為Scrooge這個中心化的系統有權力創造新的幣。

* 第二次的交易，Scrooge給予Alice 3.9個幣，同時給予Bob 5.9個幣，並且交易費為0.2個幣。

* 第三次的交易有兩個輸入與一個輸出，Alice和Bob將9.7個幣給予到Mike，交易費用為0.1個幣。

每一筆交易都會有輸入與輸出，在所有transaction中，輸入必須使用雜湊指標來指向前一個事務的輸出，並且使用該交易的所有者的私鑰進行簽名，因為所有者需要在接下來的transaction中證明同意花費。

並且，每個輸出都與接收者的公鑰相關，這是他在Scrooge中的地址。

#### 創建新幣


每個Public ID 都可以製作自己的幣，在創建錢幣的交易紀錄中可以紀錄多個錢幣，每個遷幣有編號、價值與擁有者(public id)。

#### 支付貨幣


支付貨幣可以同時合併多個交易，消費的ID所代表的是當前的交易硬幣議定在先前的某次交易出現，且附有本次消費的公鑰。

在支付貨幣中，消耗貨幣的同時將會產生新的貨幣。例如上圖的交易，有三個還沒有被消耗的貨幣在本次交易終將會被消耗。而這三個貨幣的持有人必須都簽屬本次的交易紀錄，證明他所授權的錢幣被消耗掉，同時本次的交易也將會創造出等值的錢幣賦予新的擁有者。

#### 去中心化

Scrooge Coin 雖然解決了 GoofyCoin 重複交易的問題，卻倚賴一個中心機構：Scrooge進行貨幣發行與驗證。若是今天Scrooge並不是一個誠實的發行者或是不願意為每筆交易進行數位簽章，整個系統將會無法運作。