[學習筆記] 加密及加密貨幣簡介 (Introduction to Crypto and Cryptocurrencies)

本文說明「比特幣」及「區塊鍊」的基礎原理.

Cryptographic Hash Functions


Hash function:
input: string of any length

output: fixed-size (e.g. 256 bits)

efficiently computable
Security properties:
collision-free

hiding

puzzle-friendly
Collision-free:
沒有人可以找到 \(x\) 與 \(y\) 使得 \(x \neq y\) 且 \(H(x) = H(y)\)

並不是沒有 collision, 因為 hash function 本質上是會有 collision 的, 而是一般人使用一般的電腦無法找到 \(x\) 與 \(y\) 使得 \(x \neq y\) 且 \(H(x) = H(y)\).

應用: Hash as message digest
如果我們知道 \(H(x) = H(y)\), 我們可以安全地假設 \(x = y\).

要確認某個檔案是否被竄改, 我們只要對該檔案內容計算 hash value, 檢查和原本紀錄的 hash value 是否相同.
Hiding:
我們想要: 給定 \(H(x)\), 無法找到 \(x\).

但如果 \(H(x)\) 的值不夠分散, 試幾組 \((x, H(x))\), 能夠從 \(H(x)\) 找到 \(x\).

如果 \(r\) 是從具有 high min-entropy 特性的 probability distribution 選取而來, 給定 \(H(r | x)\), 是無法找到 \(x\) (\(|\): means catenate).

High min-entropy: the distribution is "very spread out", 因此沒有任何一個特定的值會有大於可忽略的發生機率.

應用: Commitment
把訊息密封在信封裡, 日後再打開信封.

Commit to a value, reveal it later.
Commitment API
\((com, key) := commit (msg)\)

\(match := verify(com, key, msg)\)

把訊息 \(msg\) 密封在信封裡:
\( (com, key) := commit (msg)\)

公開 commitment: \(com\).
打開信封:
公開 \(key, msg\)

任何人都可以使用 \(verify()\) 進行驗證.
Security properties:
Hiding: 給定 \(com\), 無法找到 \(msg\).

Binding: 無法找到 \(msg' \neq msg\) 使得 \(verify(commit(msg), msg') == true\).
i.e. \(msg\) commit 後不能改變心意, 假裝 commit 的是 \(msg'\).
Commitment API implementation:
\(commit(msg) := (H(key | msg), key)\)
where key is a random 256-bit value
\(verify(com, key, msg) := (H(key | msg) == com) \)

Security properties:
Hiding: 給定 \(H(key | msg)\), 無法找到 \(msg\).

Binding: 無法找到 \(msg' \neq msg\) 使得 \(H(key | msg') == H(Key | msg)\)
Puzzle-friendly:
對於每個可能的 \(y\), 如果 \(k\) 是由具有 high min-entropy 特性的 distribution 選取而來, 無法找到 \(x\) 使得 \(H(k | x) = y\).

應用: Search puzzle
給定 "puzzle ID" \(id\) (從 high min-entropy distribution 選取而來), 以及 target set \(Y\).

駭客試著找到 "solution" \(x\) 使得 \(H(id | x) \in Y\).

Puzzle-friendly 意味著沒有任何 solving strategy 優於嘗試 random values of \(x\).
SHA-256 hash function


Theorem: If \(c\) is collision-free, then SHA-256 is collision-free.

Hash Pointers and Data Structures


Hash Pointer:
pointer to where some information is stored, and the cryptographic hash value of the information

If we have a hash pointer, we can
get the information back

verify that the information has not changed
Blockchain (區塊鍊):


Can detect tampering.

Use case: tamper-evident log.

假設駭客竄改了某筆 data (如下圖中的 \(data_3\)):



因為 hash function 有 collision free 的特性, 竄改過的 \(data_3\) 結合 \(H()_3\) 經由 hash function 計算所得的 hash value 和 \(H()_2\) 儲存的 hash value 會不 match, 因此我們可以得知 \(data_3\) 或 \(H()_3\) 受到竄改.

而如果駭客同時竄改了某筆 data 和它的 hash value (如下圖中的 \(data_3\) 和 \(H()_2\)):



雖然竄改後的 \(data_3\) 結合 \(H()_3\) 透過 hash function 計算而得的 hash value 和竄改 \(H()_2\) 裡所儲存 hash value 可以 match, 但因為 \(H()_2\) 受到竄改, \(H()_2\) 結合 \(data_2\) 透過 hash function 計算而得的 hash value 和 \(H()_1\) 會不 match, 因此我們可以得知 \(data_2\) 或 \(H()_2\) 受到竄改.

同理, 如果駭客進一步竄改 \(H()_1\), 我們可以偵測得知.

因此駭客必須一路竄改到 \(H()\), 而我們必須確保機制上 \(H()\) 是無法被竄改的.

Blockchain 可以偵測 data structure 是否遭到這些修改: insertion of a block, deletion of a block, tampering of data in a block, re-ordering of blocks.
Binary tree with hash pointers (Merkle tree):


和 blockchian 相同, Merkle tree 也可以用來 detect tampering.



如果要驗證 Merkle tree 中的某個 block 是否屬於 Merkle tree 沒有遭到竄改, 只需要從該 block 一路往上 traverse 到 root, 不需要 traverse 整棵 tree. Time complexity: \(O(log(n))\).

如果對 Merkle tree 做 sorting, 可以 verify non-membership in \(O(log(n))\).
Hash pointer 可以用在各種 pointer-based acyclic data structures.

Digital Signatures


我們希望 signatures 能夠做到:
只有某個人可以 sign, 而每個人都可以 verify.

Signature 綁定某份文件 (不能被剪貼到另一份文件).
API for digital signatures:
\((sk, pk) := generateKeys(keysize)\)
\(sk\): secret signing key

\(pk\): public verification key
\(sig := sign(sk, message)\)

\(isValid := verify(pk, message, sig)\)
Requirements for signatures:
能夠驗證 signatures
\(verify(pk, message, sign(sk, message)) == true\)
不能偽造 signatures
駭客知道 \(pk\) 和對於某個 \(message\) 的 \(signature\), 但他無法對於另一個 \(message\) 產生有效的 \(signature\).
實務上的考量:
algorithms are randomized (否則 \(sk\) 會容易被 hack)

limit on message size (use hash value of the message instead of message itself)

sign a hash pointer (to cover the whole structure)

Public key as identities


可以把 public key \(pk\) 視為一個 identify:
如果看到 \(pk, msg, sig\) 而且 \(verify(pk, msg, sig)==true\), 可以想作是 \(pk\) 說 "\(msg\)".

要為 \(pk\) 發言, 必須有相對應的 secret key \(sk\).
建立 identify 的方式:
Create a new random key-pair \( (sk, pk) \).

\(pk\): the public "name" you can use

\(sk\): let you "speak for" the identify
Decentralized identity management:
任何人, 在任何時候, 都可以自行建立新的 identify, 不需要向中央管控的單位申請.

在比特幣 (Bitcoin), 這些 identities 稱為 "addresses".
Privacy:
Addresses 並沒有直接連結到真實世界的 identity.

但觀察者可以觀察同一個 address 隨著時間所進行的活動, 推測真實世界的 identity.

A simple cryptocurrency


GoofyCoin:
1. Goofy can create new coins and new coins belong to Goofy
2. A coin's owner can spend it
3. The recipient can pass on the coin again.
Double-spending attack:

Double-spending attack 是設計加密貨幣主要的 design challenge.



GoofyCoin 無法抵抗 double-spending attack, 因此是不安全的.
ScroogeCoin:
Scrooge publishes a history of all transactions (a block chain, signed by Scrooge).



Optimization: put multiple transactions in the same block.

CreateCoins transaction:
create new coins.

PayCoins transaction:
consumes (and destroys) some coins, and creates new coins of the same total value (which belong to some other recipients).



The transaction is valid if:
the consumed coins are valid.

the consumed coins are not already consumed (not double-spending).

total value of the coins come out of the transaction = total value of the coins come in the transaction

the transaction is signed by the owners of all of the consumed coins
ScroogeCoins are immutable coins:
Coins can't be transferred, subdivided, or combined.

But you can get the same effect by using transactions.
Crucial question:
ScroogeCoins 可進行 transactions, 可避免 double-spending.

但是 ScroogeCoins 受到 Scrooge 的管控, 如果 Scrooge 不誠實, 或因為各種原因而做出異常的事情, 這個機制就會 fail.

因此加密貨幣的另一個主要的 design challenge 是: 如何去中心化, 不需要中央控管就能夠運作.

延伸閱讀


[Coursera] Bitcoin and Cryptocurrency Technologies