[學習筆記] 比特幣的運作機制

Bitcoin 的基本運作方式:
Append-only ledger: 交易紀錄是逐筆累加的, 每一筆紀錄永遠存在, 無法被竄改.

Decentralized consensus: 透過 peer-to-peer network 對交易紀錄達到共識.

Miners to validate transactions: 透過給予 Bitcoin 來激勵 miners 驗證每一筆交易的正確性.
本文探討達成上述運作方式背後的機制.

Bitcoin transactions


Account-based ledger (not Bitcoin):


每一筆 transaction 紀錄錢從哪個帳戶轉移到哪個帳戶.

這是很直覺的作法, 但缺點是要驗證一筆 transaction 是否 valid 時, 必須從頭開始逐筆計算, 看每個帳戶有多少錢, 轉帳時轉出的錢要 \(\leq\) 帳戶裡的錢. 或者得建立額外的資料結構, 為每個帳戶紀錄餘額.
Transaction-based ledger (Bitcoin):


每一筆 transaction 紀錄 input 及 output 的金額.

每一筆 transaction 有一個 unique ID (identifier).

每一筆 transaction 紀錄它是基於之前的哪個 transaction.

要驗證一筆 transaction 是否 valid, 只需要回溯至它所基於的那一筆 transaction, 檢查該筆 transaction 的 output 是否能 cover 目前這一筆 transaction.

可以容易做到 joint payment:

Bitcoin transaction 實際上的長相:


Metadata:



Transaction inputs:



Transaction outputs:

Bitcoin scripts


Bitcoin transaction 裡的 input "addresses" 及 output "addresses" 實際上是 scripts:
習慣上, input "addresses" 的 script 稱為 scriptSig, output "addresses" 的 script 稱為 scriptPubKey. 因為在最簡單的情況下, output script 指定 public key, 而 input script 指定 signature.

要驗證一筆 transaction 是否 valid, 把 input script 及 output script 結合起來執行, 如果沒有 error, 就視為是一筆 valid transaction.
Bitcoin script language ("Script"):
Design goals:
Built for Bitcoin (inspired by Forth)

Simple, compact

Support for crytography

Stack-based

Limits on time/memory

No looping
Bitcoin script instructions:
256 opcodes total (15 disabled, 75 reserved)
arithmetic

if/then

logic/data handling

crypto
hashes

signature verification

multi-signature verification
OP_CHECKMULTISIG
Built-in support for joint signatures

Specify n public keys

Specify t (threshold)

Verification requires t signatures: 至少要有 t 個 signatures 是 valid (共有 n 個 signatures)
Bitcoin scripts in practice (as of 2014):
Most nodes whitelist known scripts: 大多數的 nodes 會檢查 script 是否為白名單內標準的 scripts

99.9% are simple signature checks

~0.01% are MULTISIG

~0.01% are Pay-to-Script-Hash

Remainders are errors, proof-of-burn
Proof-of-burn
OP_RETURN
[arbitrary data]

執行到 OP_RETURN 時, 會 throw error, 停止執行.

OP_RETURN 後面的 data 不會被處理.

Transaction 裡的 bitcoins 會被 destroy.

用途:

1. write arbitrary data into the block chain. 可花費小額的 Bitcoin 把想要紀錄的資料永久記錄在 block chain 裡.

2. 可以用來把 Bitcoin 轉換成另一種貨幣.
Should senders specify scripts?


在交易中, 消費者是 sender, 如果要 sender specify scripts, 會造成交易的阻力.



Bitcoin 讓 sender 不必 specify 完整的 scripts, 只需要 specify hash of script, 稱之為 pay to script hash (相對的 normal mode of operation, 稱之為 pay to public key).

Bitcoin scripts 的應用


Escrow transactions
情境:

Alice 向 Bob 買東西, 但 Alice 不想在收到 Bob 的貨品前付款, Bob 不想在收到 Alice 的款項前寄送貨品.

Bitcoin 的解法:

首先, Alice sign 一個 transaction, 只要 Alice, Bob, Judy 三者之中有兩者同意, 就可以運用一筆金額為 x 的 Bitcoin:
Transaction: Pay x to 2-of-3 of Alice, Bob, Judy (MULTISIG) - SIGNED (ALICE)
如果 Bob 寄送貨品給 Alice, Alice 收到了, Bob 和 Alice 可以共同 sign 一個 transaction 把 x Bitcoin 付給 Bob:
Transaction: Pay x to Bob - SIGNED (ALICE, BOB)
如果 Bob 寄送有瑕疵的貨品, Alice 不願接受, 此時 Judy 可以做公正的裁決, 決定把 x Bitcoin 還給 Alice:
Transaction: Pay x to Alice - SIGNED (ALICE, JUDY)
Green addresses
情境:

Alice 向 Bob 買東西, 但 Bob 無法 access blockchain.

Bitcoin 的解法:

Alice 付 Bitcoin 給 bank, 由 bank 付 Bitcoin 給 Bob:
Pay x to Bob, y to Bank - SIGNED (BANK)
Bob 需要信任 bank 不會 double spend.

先前提供這樣的服務的公司 Instawallet 和 Mount Gox 都出現了問題, 因此實際上這個作法目前大家比較不敢採用.
Efficient micro-payments
情境:

Bob 向 Alice 提供服務, Alice 進行許多小額付款, 因為是小額付款, 希望不要負擔過高的 transaction fee. 舉例來說, Bob 是電信業者, Alice 每分鐘的通話需要付費給 Bob.

Bitcoin 的解法:

首先, Alice sign 一個 transaction, 需要 Bob 及 Alice 同時同意, 才能運用這筆 Bitcoin.
Input: y; Pay 100 to Bob/Alice (MULTISIG) - SIGNED (ALICE)
隨著 Alice 每分鐘的通話, Alice sign transactions 提供給 Bob, 而非 publish 到 blockchain:
Input: x; Pay 01 to Bob, 99 to Alice - SIGNED (ALICE)

Input: x; Pay 02 to Bob, 98 to Alice - SIGNED (ALICE)

...
最後 Alice 結束通話, Bob sign 一個 transaction, publish 到 blockchain:
Input: x; Pay 42 to Bob, 58 to Alice - SIGNED (ALICE, BOB)
但如果 Bob 不 sign transaction, Alice 的 100 Bitcoin 會被凍結無法使用, 避免的方式是在 Alice 開始 sign transaction 提供給 Bob 之前, 先和 Bob 一起 sign 一筆 transaction, 設定在時間 t 之後, publish 這筆 transaction 到 blockchain, 把 100 Bitcoin 還給 Alice:
Input: x; Pay 100 to Alice, LOCK until time t - SIGNED (ALICE) SIGNED (BOB)

Bitcoin blocks


Why bundle transactions together into blocks?
Single unit of work for miners that bigger than individual transaction size: reduce overhead

Make length of has-chain of blocks shorter: faster to verify history
Bitcoin block structure
由兩種 data structure 組成:

1. Hash chain of blocks

2. Hash tree (Merkle tree) of transactions in each block



Bitcoin block 的實際例子:



Bitcoin block header 的實際例子:



Bitcoin coinbase transaction (創造 Bitcoin 的 transaction) 的實際例子:



有許多網站可以讓 user 觀察 block chains, 例如: blockchain.info

The Bitcoin Network


Bitcoin P2P network:
Ad-hoc protocol (runs on TCP port 8333)

Ad-hoc network with random topology

All nodes are equal - no hierarchy, no centralized, special nodes, no master nodes

New nodes can join at any time

Forget non-responding nodes after 3 hr
Joining the Bitcoin P2P network:


首先找到 seed node, 問 seed node 它知道其他哪些 node, 再問那些 node 知道哪些 node, 依此類推. 然後選擇要和其中哪些 node 進行 peer-2-peer talk.
Transaction propagation (flooding):


在 Bitcoin 中, 要讓所有的人都知道新的 transaction 發生了.

Bitcoin 採用的作法是 gossip process - 把消息通知自己知道的人, 聽到的人再通知其他人, 依此類推, 最終所有的人都會知道.

以上圖為例, node 4 有一筆 transaction 要 publish, 他會通知 node 2 和 3, node 3 會通知 node 6 和 7, 依此類推.
當一個 node 收到通知有一筆 transaction 發生, 它判斷是否要通知其他 node 有這一筆 transaction 的方式:
Transaction valid with current block chain

(default) script matches a whitelist: avoid unusual scripts

Haven't seen before: avoid infinite loops

Doesn't conflict with others I've relayed: avoid double-sepnds
Race conditions: Transactions or blocks may conflict
情境:



Alice 進行 double spend, 透過 node 4 宣告 Alice 要付一筆錢給 Bob, 同時透過 node 1 宣告 Alice 要付同樣一筆錢給 Charlie.

Bitcoin 解法:

Default behavior: accept what you hear first. Node 遇到 conflict transaction, 會捨棄新的那一筆.

Network position matters: 如果遇到 conflict transaction, 最終的結果會取決於 transaction 在網路中發生的位置.

Miners may implement other logic
Block propagation
Relay a new block when you hear it if:

Block meets the hash target

Block has all valid transactions: run all scripts, even if you wouldn't relay

Block builds on current longest chain: avoid forks
Block propagation times
一個新的 block 傳遞給網路上的所有 node 需要花費的時間 (平均大約 30 秒):



Source: Yonatan Sompolinsky and Aviv Zohar: "Accelerating Bitcoin Transaction Proceedings", 2014
How big is the Bitcoin network?
Impossible to measure directly

Estimates up to 1M IP addresses per month

Only about 5-10k "full nodes", and this number may be dropping!
fully-validating nodes:

permanently connected: so that it can hear about all the transactions

store entire block chain
storage costs:



Tracking the UTXO set
Unspent Transaction Output
everything else can be stored on disk
Currently ~12M UTXOs
out of 44M transactions
Can easily fit into RAM
Hear and forward every node/transaction
Thin / Simple Payment Verification clients (not fully-validating)
Idea: don't store everything

Store block headers only

Request transactions as needed: to verify incoming payment

Trust fully-validating nodes

1000x cost savings! (20GB vs. 23MB)

Limitations and Improvements


Hard-coded limits in Bitcoin:
10 min. average creation time per block

1 M bytes in a block

20,000 signature operations per block

100 M satoshis per Bitcoin

21 M total Bitcoins maximum

50, 25, 12.5, ... Bitcoin mining reward

後 3 項因素會影響經濟力量的平衡 (現有 miner 假設情況如此而據此投資 resource 進行 mining), 因此不太可能改變.
Throughput limits in Bitcoin:
1 M bytes per block (10 min.)

>250 bytes per transaction

7 transactions per second

Compared to:

VISA: 2,000 - 10,000 transactions per second

PayPal: 50 - 100 transactions per second
Cryptographic limits in Bitcoin:
Only 1 signature algorithm (ECDSA/P256)

Hard-coded hash functions

Crypto primitives might break by 2040
Hard-forking
如果 Bitcoin 有新版 features, 有些 nodes 升級到新版, 有些 nodes 沒有升級, 如果有 transaction 使用了新版 features, 沒有升級的 nodes 會看不懂而 reject, 這些沒有升級的 nodes 會被 cut off from the Bitcoin network, 導致 block chain split, 這是無法被接受的.
Soft forks
Observations: we can add new features which only limit the set of valid transactions (new features 只能讓 rules 變得更嚴格)

Need majority of nodes to enforce new rules

Old nodes will approve

Risk: old nodes might mine now-invalid blocks
Soft fork example: pay to script hash


Old nodes will just approve the hash, not run the embedded script
Soft fork possibilities
New signature schemes

Extra per-block metadata
Hard forks
New op codes

Changes to size limits

Changes to mining rate

Many small bug fixes

延伸閱讀


[Coursera] Bitcoin and Cryptocurrency Technologies