[學習筆記] 比特幣如何做到去中心化

Bitcoin (比特幣) 的去中心化 (decentralization), 是同時結合技術機制 (technical mechanism) 以及巧妙的激勵機制 (incentive engineering) 所實現的.

中心化 (centralization) vs. 去中心化 (decentralization)


中心化與去中心化並非 0 與 1
以 E-mail 為例, 它是去中心化的 protocol, 但實務上 webmail services 是由少數大廠中央控管.
去中心化的考慮面向:
1. 誰維護交易紀錄 (ledger)?

2. 誰有權決定 transactions 是 valid?

3. 誰創造 Bitcoins?

4. 誰決定系統的規則?

5. Bitcoin 的匯率如何決定?

Protocol 層面: 可以做到去中心化.

Protocol 之外的層面: exchanges, wallet software, service providers... 可能是中心化或去中心化.
檢視 Bitcoin 去中心化的程度:
Peer-to-peer network
任何人都可以參與, 進入門檻低
Mining
任何人都可以參與, 但具有大量運算資源的人具有較大的影響力
Updates to software
雖然理論上每個人都可以根據 bitcoin protocol 開發 software, 但實務上 bitcoin software 主要由 core developers 開發.

Core developers 受到 community 的信任, 具有很大的權力.

分散式共識 (Distributed consensus)


Why consensus protocols?
Traditional motivation: reliability in distributed systems (避免某個 node fail, 運作就因此 fail; 必須確保 data consistency)

Distributed key-value store enables various applications: DNS, public key directory (good target for Altcoins), stock trades...
Distributed consensus definition
The protocol terminates and all correct nodes decide on the same value.

This value must have been proposed by some correct node.
Bitcoin is a peer-to-peer system
When Alice wants to pay Bob: she broadcasts the transaction to all Bitcoin nodes

How consensus could work in Bitcoin?
在任何時間點:
All nodes have a sequence of blocks of transactions they've reached consensus on

Each node has a set of outstanding transactions it's heard about (每個 node 看到的 transactions 可能有所不同)


Node 之間透過 consensus protocol 確認某個 block 是否 valid, 若 valid, 加入左邊的 consensus block chain.

但 Bitcoin 的 consensus 機制並不是這麼運作的.
Why consensus is hard?
Nodes may crash

Nodes may be malicious

Network is imperfect
Not all pairs of nodes connected

Faults in network

Latency
no notion of global time.

not all nodes can agree to a common ordering of events simply based on observing timestamps
根據 distributed systems 的理論研究, 在 network is imperfect 的情況下, 達到 consensus 是不可能的.
Byzantine generals problem

Fischer-Lynch-Paterson (deterministic nodes): consensus impossible with a single faulty node
不過 Bitcoin 運作的 model 和這些理論所假設的 model (主要用於分散式資料庫) 有所不同
Bitcoin consensus works better in practice than in theory

Theory is still catching up

But theory is important, can help predict unforeseen attacks
Bitcoin 的作法和傳統分散式系統不同之處:
Introduces financial incentives
Possible only because it's currency
Embraces randomness
Does away with the notion of a specific end-point

Consensus happens over long time scales - about 1 hour

No persistent long term identities

Consensus without identity: the block chain


為什麼需要 identity?
實務上: 有些 protocols 需要 node IDs

安全上: 可以假設只有某部分的 node 是懷有惡意的.
為什麼 Bitcoin nodes 沒有 identities?
Identity is hard in a P2P system
沒有中央控管的單位給予 node identity.

Pseudonymity 是 Bitcoin 的目標.
Weaker assumption: select random node
類比: 買樂透時拿到 ticket 或 token (而不用登記名字), 開獎後, 拿 ticket 或 token 來領獎.

我們可以挑選 random ID 並 select that node.
我們先假設 50% 的機率可以挑選到誠實的 node, 稍後會說明如何透過激勵機制來設法讓 node 是誠實的.
Key idea: implicit consensus
In each round, random node is picked.

This node proposes the next block in the chain.

Other nodes implicitly accept/reject this block.
by either extending it

or ignoring it and extending chain from earlier block
Every block contains hash of the block it extends
Consensus algorithm (simplified):
1. New transactions are broadcast to all nodes

2. Each node collects new transactions into a block

3. In each round, a random node gets to broadcast its block

4. Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures)

5. Nodes express their acceptance of the block by including its hash in the next block they create
What can a malicious node do?
Steal bitcoin: 做不到, 因為無法偽造 signature.

不 service 某個 node: 故意不 extend 某個 node 的 block. 但其他 node 會 accept 該 node 的 block. 所以此攻擊無效.

double spending:
首先, Alice 把 Bitcoin 轉移給 Bob, Bob 看到包含該筆 transaction 的 block, 提供商品給 Alice:



Alice 在下一個 round 的 broadcast, 故意 ignore 包含該筆 transaction 的 block, 而且包含一筆 transaction 把 Bitcoin 轉移給自己控制的 node Alice':



避免遭到 double spending attack 的方式:

1. honest nodes will extend the longest valid branch.

2. N confirmations 之後再確認一筆 transaction 是 valid 並提供商品給對方. (N 越大, transaction 是 valid 的機率越高).



Double spending probability decreases exponentially with # of confirmations.

Most common heuristic: 6 confirmations.

Incentives and proof of work


我們不能單純地假設 node 是誠實的.

Q: 我們是否可以設計某種獎勵機制, 來鼓勵 node 採取誠實的行為?



上圖中, 標上紅色的 node, 做了 double spending, 我們有辦法懲罰這樣的行為嗎?

因為 node 沒有 identity, 因此我們無法逮到他並且懲罰他.

因此我們換一個角度思考, 我們有辦法獎勵上圖中建立了被包含在 long-term consensus chain 的 blocks 的 nodes 嗎?

因為 node 沒有 identity, 因此我們無法寄支票給 node, 但我們可以提供 Bitcoin 給行為良好的 node 作為鼓勵.

Bitcoin 有下列 2 個獎勵機制:
Incentive 1: block reward
Creator of block gets to
include special coin-creation transaction in the block

choose recipient address of this transaction
Value is fixed, currently 25 BTC, halves every 4 years

可以把它視為 payment in exchange for the service of creating that block to go onto the consensus chain.

建立 block 的 node 只有在它建立的 block 存在於 long-term consensus branch, 它才能夠得到這個 reward.
Incentive 2: transaction fees
Creator of transaction can choose to make output value less than input value

Remainder is a transaction fee and goes to block creator

Purely voluntary, like a tip
Remaining problems:
1. How to pick a random node?

2. How to avoid a free-for-all due to rewards? (不做事就拿到免費的午餐)

3. How to prevent Sybil attacks? (駭客創造一堆 nodes, 偽造 consensus)
上述三個問題互相有關聯, 有一個解決方法可以同時解決這三個問題, 稱之為 Proof of work:
To approximate selecting a random node:
select nodes in proportion to a resource that no one can monopolize (we hope)
in proportion to computing power: proof-of-work

in proportion to ownership: proof-of-stake
Equivalent views of proof of work:
1. Select nodes in proportion to computing power

2. Let nodes compete for right to create block

3. Make it moderately hard to create new identities
Proof of work 的機制: hash puzzles
To create block, find nonce such that \( H(nonce || prev\_hash || tx || ... || tx) \) falls into a small target space within the output space of hash.

Proof-of-work 的 3 個特性:
PoW property 1: difficult to compute
As of Aug 2014: about \( 10^{20} \) hashes / block

Only some nodes bother to compete - miners
PoW property 2: parameterizable cost
Nodes automatically re-calculate the target (the size of the target space as a fraction of the output space) every two weeks

Goal: average time between blocks = 10 minutes

Probability of Alice wins next block = fraction of global hash power she controls

Key security assumption: attacks infeasible if majority of miners weighted by hash power follow the protocol

For individual miner, \( \text{mean time to find a block} = \frac{\text{10 minutes}}{\text{fraction of hash power}} \)
PoW property 3: trivial to verify
Nonce must be published as part of block

Other miners simply verify that \( H(nonce || prev\_hash || tx || ... || tx) < \text{target} \)

每個 node 都可以 verify, 不需要 central control 的單位才能 verify.

Putting it all together


Mining economics:
mining reward (block reward + transaction fees) > hardware + electricity cost \(\rightarrow\) profit

Complications:
fixed (hardware) vs. variable (electricity) costs

reward depends on global hash rate

exchange rate of Bitcoin

miners may deploy some other mining strategies instead of always finding the next block that extends the longest valid branch (a complex game theory problem)
Bitcoin has 3 types of consensus:
Value: 某個 address 所擁有的 Bitcoins 以 block chain 的形式紀錄在 Bitcoin peer to peer network 裡. 因此 Bitcoin 的所有權 (ownership), 實際上是由 peer
to peer network 所認定.

State: 發生了哪些 transactions

Rules: 透過 soft forks 及 hard forks 對於規則的改變達成共識
Bitcoin is bootstrapped:

What can a "51% attacker" do?
Steal coins from existing address? X

Suppress some transactions?
From the block chain: V

From the P2P network: X
Change the block reward? X

Destroy confidence in Bitcoin? V

延伸閱讀


[Coursera] Bitcoin and Cryptocurrency Technologies