# Week 10 - Blockchain
###### tags: `WS2020-IN2259-DS`

## Introduction

### Distributed Ledger Technology (DLT)
* 分散式帳本技術
* Cryptography (密碼學) 用於：
* 加密資料
* 防止修改
* 插入新 blocks
* 執行交易 (transaction)
* ...
* 圖示：

### Comparison with Databases
* 主要的不同在於使用 **cryptography**，允許於「非集中式的不可信任環境 (decentralized trustless environment)」執行動作 (operations)。
* 圖示：

### Public Key Cryptography
* Asymmetrical Cryptography：非對稱式加密。
* 公鑰 (**public key**) 用來加密 (**encrypt**)
* 私鑰 (**private key**) 用來解密 (**decrypt**)
* 無法使用公鑰解密！
* 圖示：

### What is a Blockchain?
> A blockchain-based distributed ledger
* An **append-only** log storing transactions
* Fully **replicated** across a large number of peers (called miners)
* Comprised of **immutable (不可變的)** blocks of data
* **Deterministically verifiable (確定可以驗證的)**
* 透過使用 blockchain data structure 來完成。
* Able to execute transactions **programmatically**
* 可以用寫程式的方式進行交易。
* 例如：Bitcoin transactions、smart contracts
* Fully **decentralized**, does not rely on a third party for trust

### Immutability (不變性) using Hashing
* Blockchain data structure **maintained at every `peer`**
* 每一個 `block` 會加入上一個 `block` 的 hash 來做自己的 hash。
* 需要 **Byzantine consensus algorithm** 來確下一個要新增上去的 `block`。
* 圖示：

## Background: Byzantine Generals Problem

### 起源：Byzantine Generals (拜占庭將軍)
* Devised by Lamport, 1982; a model and thought experiment
* A distinguished process (the **commander**) proposes initial value
* e.g., “attack”, “retreat”
* Other processes, the **lieutenants**, communicate the commander’s value
* Malicious processes can lie about the value
* i.e., are faulty
* Correct processes report the truth
* i.e., are correct
* Commander or lieutenants may be faulty
* **Consensus** means
* If the commander is correct, then correct processes should agree on commander’s proposed value
* If the commander is faulty, then all correct processes agree on a value
* *any value, could be the faulty commander’s value!*

### 3f+1 Condition (1 failure, 4 nodes)
* 左圖有達成共識，但右圖沒有達成共識 (也沒有衝突)：

### Counter-Example (1 failure, 3 nodes)
* 兩圖的 `P2` 將無法選擇要接受 commander 抑或是另一個 node 的值

### With Blockchains (Proof-of-Work – Thought Experiment)
* Idea #1:
* 每個 `message` 需要 5 分鐘來串接自己的 `block` 已建立新的 `message`。
* 下圖 `P3` 將會魚5分鐘時接收並驗證 `P2` 傳送的每個 `block`。
* 圖示：
* Idea #2:
* 每個 `process` 可以精準地量測一個 `process` 創立 `message` 所需要的時間。
* 下圖 `P2` 嘗試去偽造 `P1` 的 `block`，但是會花費太多時間！
* 圖示：

### Consensus in the Bitcoin Blockchain
* The peers need to **agree on**
* 即將串到 blockchain 上的 transactions 有哪些？
> Which recently broadcast transactions go into the blockchain?
* 這些 transactions 將依照什麼順序串上去？
> In what order they go into a block?
* The general anatomy (剖析) of consensus:
* 三步驟：
* Make a proposal
* Reach a consensus
* Announce the decision
* Tough problem
* 在 1983 年之前，還有數十種**不可能**的結果。
* **無法擴增規模**超過 30 至 100 participants。
* 需要**很長的收斂時間**。

## Proof of Work and Mining

### Blockchain "Puzzles"
* 目標：令 **`verify(nonce, data)`** 函式，合乎某種**特定條件**。
* 方法：利用「**trapdoor functions**」，也就是 hash functions 來完成目標。
* 不停地嘗試塞入 random values，直到此 hash functions 滿足「特定條件」。
* 就像是嘗試不同的數字組合以解開行李箱密碼鎖一樣。
* 因此，擁有愈多愈強的 computing power，你就將愈快解開 puzzle。
* **`Magic blocks`**：意即 blocks with puzzles。

### Proof-of-Work Example
* 挑戰：找出 `nuouce` 令 `sha256sum(“data:nonce”)` 的值第一個字元為 `0`，
* 通常特定條件會更複雜。
* 例如 18 個 `0`。
* **正常情境**：P1 wants to send “`1:v`” to P2
* **偽造情境**：
* 如果 P2 想偽造 `v` 為 `w` 再傳送給 P3，
* 那首先 P2 要先找到 `n1` 滿足 `sha256sum(1:w:n1)`，
* 再找到 `n2` 滿足 `sha256sum(2:1:w:n1:n2)`。
* 因此，如果 P3 有方法**偵測** P2 **做了太多工作**，就等於偵測到了這個欺詐 (fraud)。

### Proof-of-Work in Bitcoin
* 待命的交易 (transactions) 位於 `Pending Transactions Pool` 中，將會被傳送給礦工 (miners)。
* 礦工會驗證並將交易放進 `block` 裡，然後開始尋找 `nounce`。
* 根據 **global *hash-rate*** 來決定要多少個 leading zeroes。
* 例如：一個 `block` 平均十分鐘解決的標準。
* 礦工可能會幸運地將解出來的 puzzle 塞上 blockchain，或是因為其他人解出來而停止計算。
* 一筆交易有愈多的 confirmation，就愈不容易消失。
* 圖示：

### Branching
* 兩個 `block 3` 被同時算出來 (非常稀少的情況)。
* 之後一位各種變數的影響，一定會有一條 `branch` 的礦工先做出 `block 4`。
* 變數如 network delays 等等。
* 當礦工收到較長的 `branch` 時，就會丟棄自己手上另一條較短的 `branch` 了。
* 圖示：

### Incentives (獎勵措施)
* **Block reward**
* started with 50 BTC, 25 BTC, 12.5 BTC. ...
* Creating of new coins
* The only means to create coins
* Reward reaped by miner whose block ultimately makes it into the chain
* Block reward will **converge toward zero**
* **Transaction fee**
* Small amount that is paid by transaction issuer to miner
* Not a fixed amount, amount declared by issuer
* Ultimately, market forces may set this value

## Transactions and Transaction Flow

### Bitcoin Transactions (Bitcoin 交易)
* 每個 user 透過 public/private key pairs 來識別自己擁有的 `wallet`。
* User 使用 private key 來簽署 (sign) 自己的 `Transaction C`。
* `Transaction C` 內容包含至指定錢包的 address。
* 要獎勵給礦工的 transaction fee 會附加於 `Transaction C` 的最後。
* `Transaction C` 必須參考以前的 `committed block`，檢查 unspent transaction outputs (UTXOs) 是否等於本次 `Transaction C` 的輸出金額。
* 直接拿來用的概念？
* 只要一完成交易，一個 transaction outputs 將無法再次使用。
* 礦工會驗證每筆交易。
* 圖示：

### Wallets and Addresses
* Users require a **wallet** to store money
* Includes any user, including but not limited to miners
* Wallet is authenticated and identified by a **public/private key pair**
* Generated using **ECDSA** (Elliptic curve cryptography)

### Loosing Your Private Key
* Loss of private key means the wallet and its **funds are permanently locked**, as it is **no longer possible** to sign proofs redeeming existing UTXOs.
* This **money is** essentially **lost**, thereby reducing the total amount of currency in Bitcoin
* Trusting an online service to store key is also risky, since there is no way to prove that you are the rightful owner if the key is stolen or misused
* **The most reliable solution is to store your private keys on tamper-proof hardware wallets (防篡改的硬體錢包)**

### Transaction Flow
1. **Bob** generates and sends a **public key address**.
2. **Alice** **creates** a **transaction** using this address.
3. Alice sends the new transaction to the network.
4. Transaction is **broadcasted using gossiping**.
5. Transaction is included in a mined block.
6. **Bob** **can verify** the transaction is in the blockchain.
7. **Bob** **can now sign** new transactions which **redeems this address**.

### Preventing Double Spending: 51% Attack
* `TX A` 為正常的消費交易。
* `TX B` 為偽造的 Double Spending。
* 攻擊者製造含有 `TX B` 的 `Block N`，並持續計算 `Block N+1`、`Block N+2`、`Block N+3`...。
* 若最後攻擊者製造的 Blockchain 比原本的那條長，那麼 `TX A` 就會被成功替換成 `TX B`。
* 圖示：
:::info
* **Magic Watch** 是在主鏈上**連續生成 (continuous generation)** 的 blocks，這可以限制攻擊者建立自己 chain 的時間。
* 攻擊者需要擁有整個網路中大於 51% 的能量 (>51% the power in the network)，才能有足夠的時間完成偽造。
:::

### Limitations of Bitcoin
* **Limited expressiveness (表現力有限)**
* **Cryptocurrency only**：用途只有**加密貨幣**
* Each app (new coin) requires new platform
* NameCoin, PrimeCoin, CureCoin
* **Slow block time (10 mins)**
* Also slow confirmation time (1+ hour for 6 confirmations)
* 無法即時交易，例如買咖啡
* **Hard/Soft forks**：各個版本的相容性問題
* 更新程式造成 fork
* Hard forks are not compatible (不相容)
* Duplicated money
* 5 Bitcoin forks
* 如：Bitcoin Classic
* Slow transaction rate
* 7 transactions/second
* VISA Network: 2000 tps (average)
* 解決方法：
* 減少 global hash-rate
* 增加 limited block size (1MB -> 2MB)
* Environmental impact of PoW
* ~1000x more energy than credit card
* Ahead of 159 countries for energy consumption
* 如 Ireland
* 很多人一起挖礦，一個人挖到，其他人浪費能源。
* Long bootstrap time for a miner
* Full ledger: 270 GB (2020/04)
* CPU/I/O cost to **verify each transaction/block**
* Takes hours/days

## Platform and Applications - Blockchain Platforms

### Ethereum
* Managing entity: **Ethereum Foundation (以太坊基金會)**
* Major players: Deloitte, Toyota, Microsoft, ...
* Enable **decentralized applications (Dapps)** et al.
* Open-source, flexible, general platform
* Permisionless (public) ledger, proof-of-work-based(alternative mechanisms are work in progress)
* Cryptocurrency: 1 Ether = 1e18 Wei (~150 USD, 2020/4)
* **Smart contracts**
* Solidity, Remix (Web IDE), Truffle (Dev./Test), Viper (programming language to build Dapps)
* Ethereum Virtual Machine (EVM)

### Smart Contracts
* `Contracts` 是程式，編譯成 bytecode 以執行於 EVMs 上。
* `Contracts` 擁有自己的 internal storage (internal state)。
* `Contracts` 可以被一個 transaction 或其他 contract 觸發。
* `Contract` 的執行時間受到 **gas** 的限制。
* **Gas**：燃料，消耗多少就要繳多少燃料費，類似手續費的概念。
* 圖示：

### Account State (“World State”)
* Patricia Tree：參考「[基數樹 - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%A0%91)」

### Execution

### Hyperledger
* Managing entity: Hyperledger Consortium
* Major players: IBM, NEC, Intel, R3, ...
* Enterprise blockchains
* Permissioned ledger (private and consortium networks，私人與財團網路)
* **Smart contracts** in general purpose language(s)
* Open-source, configurable, pluggable consensus
* **World state** on CouchDB, LevelDB, et al.
* Hyperledger is a family of projects
* **Fabric: PBFT Consensus et al.**
* Sawtooth: Proof-of-elapsed time (using Intel SGX)
* Composer: Smart contract language and development tool
* Cello: Blockchain-as-a-Service framework
* Key **differentiators**
* Assumes a **more trusted environment** than Bitcoin/Ethereum
* Requires **authentication** to partake in business network
* **Dozens of peers** that manage distributed ledger (not 1000s)
* **No cryptocurrency**, **no tokens** (could be build on top)
* **No proof-of-work-based consensus** (traditional consensus)
* **No mining**, no intrinsic inventive mechanisms
* Intended **use cases**
* Trade finance (tracking financial transactions and goods)
* Supply chains, logistics (tracking goods, assets, etc.)
* Cross-border trade
* Inter governmental information exchange
* Health-care networks (provider, insurer, laboratory, end-user)

### Chaincode Example
* Digital Rights Management for Music (DRM)
* Dunction `play()`：
* Reads an artwork
* Reads the royalty (版稅) related to that artwork
* Increments a count to track royalty payments
* Writes the new count
* Inplementation：

    async play(ctx, artWorkId) {
        const metadata = await ctx.stub.getState(artWorkId);
        let royaltyManagementAsset = await
        ctx.stub.getState(metadata.royaltyManagementId);
        royaltyManagementAsset.incrementPlayCount();
        await ctx.stub.putState(metadata.royaltyManagementId, royaltyManagementBuffer);

* **`play(context, 04672033)`** 產生以下 **read-write set**：

### Transaction Flow in Fabric
* Endorser：背書人。
* 圖示：

## Platform and Applications - Blockchain Applications

### Blockchain 1.0: Currency

### Blockchain 2.0: Decentralized Apps (DApps)
* **DApps** are applications built on **blockchain platforms** using **smart contracts**.
* Cryptocurrency：[Ethereum](https://ethereum.org/en/developers/)
* Crowdfunding：[Token Distribution](https://www.onflow.org/token-distribution)
* Charity donation payment：[Qalice](https://alice.si/)
* Forecast market：[Gnosis](https://gnosis.io/)
* 如：betting、insurance
* Decentralized virtual world：[ETHERIA](http://www.etheria.world/)
* 圖示：

### Blockchain 3.0: Pervasive Apps (普及應用)
* Applications involve entire **industries**, **public sector (公共部門)**, and **IoT**.
* Diamonds Provenance
* Land Registry in Honduras
* Electronic Health Records
* Transparent Voting System

### Why Study Blockchains?
* Drivers (驅動力)
* Avoid middlemen：去中心化，沒有第三方，也就沒有來自中間人的開銷。
* Provide transparency, audit trail：透明可追蹤的帳本資料。
* Eliminate friction during conflicts (non-repudiation)：有詳實的記錄，所有事件都可以進行歸詢。
* Research challenges for 1.0:
* Identify theoretical **security flaws**
* **Sustainability (可持續性)** of legacy systems
* Research challenges for 2.0:
* **Verify** smart contracts
* 有可能會有 bug，進行驗證是很難的問題。
* Create generic middleware **services**
* Research challenges for 3.0:
* Develop **scalable and fast** systems
* Guarantee data **privacy**
* Verify **correctness** of data entry points (CPS interface barrier)
* 如何驗證鑽石的真偽？這是現實面上的難題。

### Conclusions
* Blockchains provide **decentralized storage and code execution**, and can be used to `combat fraud`, `avoid redundancy`, and `provide transparency`.
* Blockchains rely on **cryptography** and **massive replication** using a `robust consensus mechanism`.
* Blockchains are useful for a wide variety of applications, ranging from cryptocurrency (1.0) to health (3.0).
* Research directions exist across the **6 layers** for all kinds of applications (from 1.0 to 3.0).