# Blockchain TL;DR
###### tags: `Study` `Blockchain`

:::danger
本區討論僅作為本人吸收後的摘要，故只會有大略描述，詳細內容仍得看藍色連結。
:::

---

## 查詢關鍵字
`BFT` `PoS` `DPoS` `Stealth` `ZKP`

## 找時間看的討論
:::spoiler
* **BLS**
- [x] https://medium.com/taipei-ethereum-meetup/ethereum-casper-%E8%AA%8D%E8%AD%98-bls-signature-f9fdecf63bb0
- [ ] https://blog.dash.org/secret-sharing-and-threshold-signatures-with-bls-954d1587b5f
- [ ] https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
* **zk-SNARK**
- [ ] https://medium.com/taipei-ethereum-meetup/%E6%B7%B1%E5%85%A5%E7%9E%AD%E8%A7%A3-zk-snarks-7a0187f399f1
- [ ] https://blockchain.iethpay.com/zkSNARK-intro.html
- [ ] https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
- [ ] https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
- [ ] https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
* **ECC & ECDSA**
- [ ] http://kimiwublog.blogspot.com/2018/06/ecdsaethereumsign-message.html
* **Security**
- [x] https://www.semanticscholar.org/paper/A-Survey-of-Solutions-to-the-Sybil-Attack-Levine-Shields/dd3fb51e02592dfa1a87c1e55b1a5dcf3edffa9d
* **Gitbooks**
- [x] https://gitbook.creat.kim/blockchain-tutorial/
* **GHOST protocol**
- [x] https://ethereum.stackexchange.com/questions/38121/why-did-ethereum-abandon-the-ghost-protocol
* **HyperLedger**
- [x] https://www.smelearning.org.tw/sys/public/getAttachs.php?f=ssOM3q7n1klOTVQ9hEdKm6Z/BugEWvYzC3DpKDOGeV2HpH8klg19/bAfUs4WqAlqfzI0vH/qUPCD+CvKv+w6EwMdr9FunGg2R6tjysfl9/V1A0jmEJ+RMGYgoisz1uM4N98Tjnm65/KQewr4ABrYJ4R930KLYaJ6uUvzf8e60L6OsWELou+zzClw0PfJ3l/ylqDNW71XZ9g/Bm/MzeYAPVy2TflOkotOMhZtTfZiA8cRGOiz4ZaLsDbHDM5YHQ/E
:::

## Vitalik 討論 Public chain 與 Private chain
:::info
* https://blog.ethereum.org/2015/08/07/on-public-and-private-blockchains/
:::

## 為何 BFT 的容錯率是不超過 1/3 個 Byzantine Node ?
:::info
* https://zhuanlan.zhihu.com/p/36000412
:::
* BFT 的假設有 Safety 與 Liveness :
* **Safety** : 任意非拜占庭節點不會產生不同的結果。
* **Liveness** : 任意非拜占庭節點最終都可以得出結果。
* 假設以下參數 :
* 總節點數(Totoal Nodes)為 $N$
* 拜占庭節點(Byzantine Nodes)數為 $F$
* 這邊假設滿足 Safety 與 Liveness 的門檻 $F_{safety}$ 與 $F_{liveness}$ 為同一組 $F$
* 誠實節點數(Honest Nodes)為 $N-F$
* 共識達成最低人數(Quorum)為 $Q$
* 滿足 $2Q-N>F$ 表示達到 **Safety** :
* $Q$ 為超過總體一半的人數，也就是 $2Q$ 至少要含括全部的人
* 此函式代表任意兩 Quorum 所交集的節點數比惡意節點還多
* 如果惡意節點剛好等於交集節點數，則會使得惡意節點可以再兩個不同的 Quorum 中回覆不同的結果
* 滿足 $N-F \ge Q$ 表示達到 **Liveness** :
* 誠實節點數量大於等於 Quorum ，則永遠可以取出足夠說服的 Quorum
* 以下推論 $F$ 應為多少 :
* $2Q-N>F\\=>2Q>F+N$
* $N-F \ge Q\\=>2(N-F) \ge 2Q$
* $F+N<2Q \le 2(N-F)$
* $F+N<2(N-F)\\=>F<(1/3)N$
* ==得證 $F$ 不能超過總節點的 $1/3$==
* 以下推論 $Q$ 應為多少 :
* $F<(1/3)N\\=>3F<N$
* $3F+1$ 是最小的 $N$
* 代入 $F+N < 2Q$ 得 $F+(3F+1) < 2Q$
* 最後可得 $Q > 2F+(1/2)$ ，又因節點沒有半個的，故 $Q \ge 2F+1$
* 把 $F < (1/3)N$ 代回 $Q \ge 2F+1$
* 可得 $Q\ge(2/3)N+1$
* ==得證 $Q$ 至少要超過總節點的 $2/3$==
:::success
**另外的證明**
* 在 Crash-Fail Tolerant(CFT) 環境 : (Liveness)
* $N$ 為總節點，故障節點 $F$ 只會不回應或者回應錯誤的結果。
* 在全系統上傳遞的訊息有 $N-F$ 個正常節點的與 $F$ 個故障節點的，==節點的目的是為了要辨識哪些是 $F$ 的訊息==。
* 為了要讓正常節點可以被發現，所以需要是多數決，可以推得 $N-F>F$ 。
* $N>2F$ 即是 $N \ge 2F+1$ 。
* 在總共 $2F+1$ 的數量下，可以分辨出 $F$ 與 $F+1$ 兩個群集。
* $F+1$ 會是一個 Quorum 。
* Paxos 與 Raft 即是在此環境。
* 在 Byzantine-Fail Tolerant(BFT) 環境 : (Safety)
* $N$ 為總節點，惡意節點 $F$ 可能會對不同節點回應不同的結果。
* 在 $N-F$ 的正常節點中，可能還會有額外的 $F$ 個節點遭受惡意節點影響，但仍需要在此情況下辨識出惡意節點。
* 故可推得 $(N-F)-F>F$ ，也就是 $N \ge 3F+1$ 。
* 在總共 $3F+1$ 的數量下，可以分辨出 $F$ 與 $2F+1$ 兩個群集。
* $2F+1$ 會是一個 Quorum 。
* PBFT 與 Tendermint 即是在此環境。
:::

## Federated Byzantine Agreement 為何一樣是 1/3 個惡意節點?
:::info
* [Safety vs. Liveness in the Stellar Network](https://www.scs.stanford.edu/~dm/blog/safety-vs-liveness.html)
* [Is Stellar As Secure As You Think?](https://arxiv.org/abs/1904.13302)
:::

* FBA(Federated Byzantine Agreement) 跟一般的 BFT 協定一樣，需要去考慮 Safety 與 Liveness ，但這邊分別考慮 $F_{safety} (F_s)$ 與 $F_{liveness}(F_l)$ 。
* 要注意的是，一個 BFT 系統如果可以容忍 $x$ 個 Byzantine node ，則稱此系統為 `x-FT system`(x-fault tolerant system)，此 $x$ 取決於 $min(F_s,F_l)$ 。
* 以下為參數設置 :
* $N$ : 所有 Quorum 加總節點數
* $T$ : 各 FBA 的 Quorum slice 的大小
* $F_s$ : 保有 Safety 的拜占庭節點門檻數
* $F_l$ : 保有 Liveness 的拜占庭節點門檻數
* 符合 Safety : $2T-N>F_s$
* 任意兩 Quorum 交集的節點必須要大於 $F_s$ 個惡意節點，換句話說，至少交集有一個非惡意節點存在。
* 符合 Liveness : $N-F_l\ge T$
* 一個 Quorum 扣除交集節點後，必需仍可以透過 slice 得出結果
* 
* 以下推論 $F_s$ 、 $F_l$ 與 $N$ 的關係 :
* 把 $N-F_l\ge T$ 帶入 $2T-N>F_s$
* $2(N-F_l)-N>F_s => N-2F_l-F_s>0$
* $N-F_l-F_s > F_l$ 為關係式
* 可以看作是所有正確節點必須大於惡意節點
* 接下來分為兩個 case 來分析， $F_s \ge F_l$ 與 $F_s < F_l$ : ($F_s$ 或 $F_l$ 都有可能較小)
1. $F_s \ge F_l$ :
* 由於 $F_l$ 較小，故 x-FT system 以 $F_l$ 來考慮，由關係式可得 $N-2F_l > F_s$ ，並帶回 $F_s>F_l$ 。
* 可得 $N-2F_l>F_l => N/3>F_l$
* 可得 $F_l$ 必須小於全部總共節點的 1/3
* 當 $F_l = F_s$ 同理
* $F_l=1, F_s=3$ :
2. $F_s<F_l$ :
* 由於 $F_s$ 較小，故 x-FT system 以 $F_s$ 來考慮，由關係式可得 $(N-F_s)/2 > F_l$ ，並帶回 $F_l>F_s$ 。
* 可得 $(N-F_s)/2>F_l => N/3>F_s$
* 可得 $F_s$ 必須小於全部總共節點的 1/3
* $F_l=2, F_s=1$ :

* 由此可知，不論 $F_l$ 與 $F_s$ 何者較小，都必須小於整體 1/3 ，故 FBA 並沒有比一般 BFT 有優勢。

## PoS 是怎麼知道 Target Difficulty ?
:::info
* https://staking.tech/blog/post/understanding-utxo
* http://earlz.net/view/2017/07/27/1904/the-missing-explanation-of-proof-of-stake-version
:::
* PoS 最早由 [Peercoin](https://peercoin.net/) 所提出，產生區塊的過程稱為「鍛造」而非挖礦，越多資產的人，擁有越高的機率成為出塊者。
* 和 Algorand 的 Pure PoS 不太相同， PoS 仍需要做部分的 PoW 。
* PoS 計算 target 所需要的 hash 的 pseudo-code :
* `utxo.value` 為當下 stake transaction 的金額。
* `previousStakeModifier` 是上個區塊的 hash 。

while(true){
    foreach(utxo in wallet){
        blockTime = currentTime - currentTime % 16
        posDifficulty = difficulty * utxo.value
        hash = hash(previousStakeModifier << utxo.time << utxo.hash << utxo.n << blockTime)
        if(hash < posDifficulty){
            done
        }
    } 
    wait 16s -- wait 16 seconds, until the block time can be changed
}

* ==當 stake transaction 的 balance 越高，那挖礦的難度也會隨之降低==。

## 什麼是 PoS 的 Nothing at Stake 攻擊 ?
:::info
* https://medium.com/coinmonks/understanding-proof-of-stake-the-nothing-at-stake-theory-1f0d71bc027
* https://golden.com/wiki/Nothing-at-stake_problem
* https://ethereum.stackexchange.com/questions/2402/what-exactly-is-the-nothing-at-stake-problem
:::
* Nothing-at-stake 攻擊指的是 PoS 在產生區塊沒有任何成本的情況下，礦工可以替所有的 fork 分支鏈接上自己的區塊。
* ==假設==所有礦工都將自己的 stake 壓在任何 fork 上，因此一開始並沒有主鏈。
* 可以想像成任一條的 fork 都有 100% 的 stake 在上面，因為不需要任何代價，只要擁有 token 。
* 因為任何 fork 都有機會成為主鏈，礦工為了達到最大利益，會去對每條 fork 提出自己的區塊並抵押 stake ，反正也沒有任何損失。
* 只要有攻擊者保留 1% 的 stake ，不把自己所有的 stake 壓在任意的 fork ，那他就可以使用自己那 1% 的 stake 來隨意切換主鏈，造成雙花攻擊。
* Ethereum 的 Casper 共識機制就是使用 PoS ，其解決 Nothing-at-stake 的方法是透過抵押 stake ，如果礦工將 stake 壓在錯誤的 fork ，則該筆 stake 會被沒收。
* PoS 要如何知道礦工有將 Stake 壓在其他 fork 呢 ? ([參考](https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/))
每個 PoS 的區塊除了產塊者外，還需要其他礦工的簽章，如果有礦工對錯的 fork 簽章，那該簽章就可以作為證據來懲罰。
* **PoW 不會有 Nothing-at-stake 攻擊**，因為一旦礦工把算力分給其他的 fork ，那他主鏈便會輸給別人，總而言之就是算力有限，無法顧及所有的 fork 。

## 什麼是 PoS 的 Fake Stake 攻擊 ?
:::info
* https://medium.com/@dsl_uiuc/fake-stake-attacks-on-chain-based-proof-of-stake-cryptocurrencies-b8b05723f806
* https://staking.tech/blog/post/understanding-utxo
* http://earlz.net/view/2017/07/27/1904/the-missing-explanation-of-proof-of-stake-version
:::
* PoS 的共識機制會擁有較多 stake 的節點可以有較高的機率出塊，但是要檢查該 stake transaction 是否合法 (valid) 或尚未被花費 (unspent) 就需要花費很多時間，所以許多 PoS 檢查 stake 的方法並不是完整性的檢查，這也導致了需多弱點被發現。
* 使用 PoS 的 UTXO 區塊鏈系統會有以下「Fake Stake」的弱點 :
1. **I Can’t Believe it’s not Stake** :
* 目標 :
* 沒有任何 stake 的攻擊者可以透過此弱點來使受害者節點的 RAM 超載。
* 原因 :
* 因為區塊內的 stake transaction (此交易會是礦工挖礦時的 stake) 只在 block body 出現，礦工無法透過 block header 知道該區塊擁有多少 stake ，從而無法驗證區塊是否合法，因此把 block body 下載到 RAM 是必要的。
* 換句話說，==在尚未下載 block body 之前，是無法得知此區塊是否合法==。
* 攻擊者因此可以送出一堆 stake 為 0 的區塊到網路上，使其他節點需要下載其 block body 來驗證，但卻又會導致 RAM 過載。
2. **Spent Stake Attack** :
* 早期的 PoS 可以避免此攻擊，例如 Peercoin ，因為在把 block body 存入 RAM 之前，會去檢查以下兩點 :
1. 檢查 output 是否已經被花費 (double-spending) ? :arrow_left: 透過 transaction database 來記錄目前主鏈的交易狀態。
2. 檢查 PoS 的 hash 是否有達到 difficulty target ?
* 但這兩種檢查仍有其他疑慮 :
* `檢查1.` 只能確定該 output 是存在的，但是無法確定他是否尚未被花費 (unspent) 。
* 就算驗證了一個區塊的 stake transaction 是 unspent 的，但也可能因為它是對於主鏈的 fork 導致該交易被 roll-back 。
* **Spent Stake Attack** 就是基於繞過上述疑慮的攻擊 :
* 攻擊方法 :
* 將 stake transcation 放成已被花費的交易。
* 通過 PoS 挖礦的 difficulty target ，但是為了能快速出塊，所以需要有大量的 stake ，因此又產生另一種攻擊， **Stake Amplification** 。
* PoS 的取捨是==一方面想早點拒絕非法區塊，但另一方面卻又不希望延誤同步上主鏈的時間==。

## Delegated Proof of Stake 系列討論
:::info
* [Bitshare、Steemit、EOS](https://help.bybit.com/hc/zh-tw/articles/360021940694-從EOS-Bitshare和Steemit了解大神BM的傳奇往事)
* **DPoS** (Bitshare, Steemit, EOS_1.0)
* https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper
* https://bitshares.org/technology/delegated-proof-of-stake-consensus/
* **BFT-DPoS** (EOS_2.0)
* https://medium.com/eosio/dpos-bft-pipelined-byzantine-fault-tolerance-8a0634a270ba
:::

## BLS Signature (Threshold Signature)
:::info
* https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
:::
* BLS 簽章又可以稱為「門檻簽章」，只需產生一個可以使用 k 組公鑰來驗證的簽章。可以確保簽章有至少 k-n 個私鑰做數位簽章過。
* **Diffie Hellman Key Exchange** :
* $g$ 為一個有限循環群 $G$ 的 generator 。(雙方公開)
* $A$ 為 Alice 的公鑰， $a$ 為私鑰， $p$ 為雙方皆知道的質數。
* Alice 將 $(g,A,p)$ 交給 Bob 。
* Bob 透過自己的私鑰 $b$ 產生一個公鑰 $B$ ，並交給 Alice 。
* Alice 計算 $B^a=(g^b)^a$ ， Bob 計算 $A^b=(g^a)^b$ ，兩者結果同為 $K$ 。
* **[Bilinear Pairing](https://www.math.uwaterloo.ca/~ajmeneze/publications/pairings.pdf)** :
* Pairing 指的是將兩個不同的群 $G_1, G_2$ 透過函式 $e$ 來應設置第三個群 $G_T$ 如下所示 $e: G_1 \times G_2 \to G_T$ 。
* 且符合以下條件 :
1. (bilinearity) $e(R+S,T)=e(R,T)e(S,T)$
2. (non-degeneracy) $e(P,P)\ne1$
3. (computability) $e$ can be computated
* 根據 bilinearity 可以推出 $e(xP,Q)=e(P,Q)e(P,Q)...e(P,Q)=e(P,Q)^x=e(P,xQ)$
### BLS Scheme (ECC version) :

* 令 $H(m)$ 為 hash to curve G function ，可以將訊息 $m$ 雜湊至橢圓曲線 $G$ 上。
* 以下為 BLS 所需之 term :
* Generator point : $G$
* Public Key : $P=pk\times G$
* Private Key : $pk$
* Message : $m$
* Signature : $S=pk \times H(m)$
* 透過 Bilinear Pairing 可以得到以下特性 :
* $e(P,H(m))=e(pk \times G, H(m))=e(G,pk \times H(m))=e(G,S)$
### Signature Aggregation
* 令 $S=S_1+S_2+...+S_{100}$ 來表示 100 個簽章可以匯集成一個簽章 $S$ 。
* 令 $P=P_1+P_2+...+P_{100}$ 來表示相對應的公鑰。
* 故 $e(G,S)=e(G,pk_1 \times H(m)+pk_2 \times H(m) + ... + pk_{100} \times H(m))$$=e(PK_1,H(m))e(PK_2,H(m))...e(PK_{100},H(m))$
$=e(P,H(m))$
* 又稱為 **n-of-n multisignature** 。
* 要驗證 $S$ 的合法性，只需要將公鑰加總 $P$ 與訊息雜湊值 $H(m)$ 做 Pairing ，其結果與 $e(G,S)$ 相同即可。
### Subgroup Multisignature Scheme (m-of-n multisignature)
* 令 $P=a_1 \times P_1+a_2 \times P_2+a_3 \times P_3, a_i=hash(P_i,\{P_1,P_2,P_3\})$ 。
* 令 $MK_i=(a_1pk_1) \times H(P,i)+(a_2pk_2) \times H(P,i)+(a_3pk_3) \times H(P,i)$ 為 membership key 。
* 假設 $pk_1$ 與 $pk_3$ 一起做 2-of-3 multisignature :
* $S_1=pk_1 \times H(P,m)+MK_1$; $S_3=pk_3 \times H(P,m)+MK_3$ 。
* 令 $(S',P')=(S_1+S_3, P_1+P_3)$ 。
* $e(G,S')=e(G,pk_1 \times H(P,m)+pk_3 \times H(P,m)+MK_1+MK_3)$
$=e(G,(pk_1+pk_3) \times H(P,m))\cdot e(G,MK_1+MK_3)$
$=e(P',H(P,m)) \cdot e(P,H(P,1)+H(P,3))$
* 整體流程可以看成 :
1. 各簽章成員擁有 $pk_i$ 與 對應的 membership key $MK_i$ 。
2. 各成員使用自己的私鑰與 membership key 去對 $H(P,m)$ 做簽章，此簽章即是 **signature share**。
3. 任何成員可以透過蒐集 n-of-m 的 signature shares 來組成可驗證的 **threshold signature**。

## UTXO-based v.s. Account-based blockchain
:::info
* https://medium.com/nervosnetwork/my-comparison-between-the-utxo-and-account-model-821eb46691b2
* https://medium.com/@ConsenSys/thoughts-on-utxo-by-vitalik-buterin-2bb782c67e53
* https://ethereum.stackexchange.com/questions/326/what-are-the-pros-and-cons-of-ethereum-balances-vs-utxos
:::
### UTXO-based (Bitcoin)
* 因為使用者的 UTXO address 會一直改變，所以想比之下**較有隱私**。
* 一次的交易中，可以平行處理多筆的 input 與 output ，具有較好的 scalability 。

### Account-based (Ethereum)
* 交易較省空間，相較於 UTXO-based ，每個 input 都需要數位簽章， Account-based 只有一個 input 與一個 output 。
* 直覺上較好理解，能夠支援圖靈完備的程式碼。

## Shamir's Secret Sharing 與 Multi-signature 的差異
:::info
* **Shamir's Secret Sharing**
* https://medium.com/taipei-ethereum-meetup/%E7%A7%81%E9%91%B0%E5%88%86%E5%89%B2-shamirs-secret-sharing-7a70c8abf664
* https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
* **Multi-signature**
* https://en.bitcoin.it/wiki/Multisignature
* **Comparison**
* https://medium.com/coinsafeapp/shamir-secret-sharing-vs-multi-sig-124a42bc1662
* https://bitcoin.stackexchange.com/questions/53041/is-there-a-difference-between-the-multi-signature-and-shamirs-secret-sharing/53043
:::
### Shamir's Secret Sharing
* 在 k-of-N 的情況下，只要能湊到 k 份 shared secret ，就可以重組回秘密。
* 每個參與者使用**共用金鑰對**，但是被拆散成數份 share 。
* 在區塊鏈使用 SSSS 的步驟為 : ([DEMO](http://point-at-infinity.org/ssss/demo.html))
* 產生一對金鑰 (Pulbic key, Private key) 。
* 將私鑰作為 shared secret 並透過 SSSS 來產生 N 份 share 。
* 只要有 k 份的 share ，那就可以組回私鑰並使用它。
* **缺點** :
* 需要一個發布者來分發這 N 份的 share ，有集中化的問題。
* 一旦 k 份的 share 被重組回 shared secret ，那必定會有人要用此 secret 來做簽章，因此一旦組回後，此 secret 便不再安全。

### Multi-signature
* `multisignature` 是 Bitcoin 的一種簽章方法，能使用多組的私鑰來對交易做簽章驗證。
* 每個參與者**各自擁有金鑰對**。
* 下圖是 Bitcoin 的 `multisignature` 驗證多重簽章的方法 :
* 有三組 Public key ，需要至少有兩組相對應 Private key 的簽章才算是有認證過。
* **缺點** :
* 只有 Bitcoin 在協定上支援多重簽章，其他區塊鏈多為使用 SSSS 來達成。

## 專注於隱私的加密貨幣與其技術
:::info
* **Monero**
* [Medium](https://medium.com/taipei-ethereum-meetup/monero-%E9%96%80%E7%BE%85%E5%B9%A3-%E9%9A%B1%E5%8C%BF%E4%BA%A4%E6%98%93%E7%9A%84%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-423451f4e8b4)
* https://cryptonote.org/whitepaper.pdf
* **Ring signature**
* https://people.csail.mit.edu/rivest/pubs/RST01.pdf
:::
* ==詳細技術解釋== : https://hackmd.io/@ofAlpaca/privacycoin
### Monero 門羅幣
* Ring Signature (環狀簽章)
* 將真實的簽章者混入一群簽章者內，使他人無法得知誰是真正的簽章者。
* Stealth Address (隱藏位址)
* 保護 receiver 的隱私，令他人無法知道接收者是誰。
* Ring Confidential Transaction (環簽交易)
* 使用 **Pedersen Commitments** 來混淆交易的金額，令他人無法確切知道交易的金額，但卻又可以被驗證，保護了發送者與交易內容。

## Homomorphic encryption with noise (Why Boostraping)
:::info
* https://crypto.stackexchange.com/questions/35150/noise-in-homomorphic-encryption
* https://eprint.iacr.org/2009/616
:::
* 為何需同態加密需要雜訊(noise)? 是為了避免密文跟明文被配對在一起；noise 通常是在加密時加入的隨機數，為了避免每次加密都產生相同的密文。
* 以下為簡單描述如何增加雜訊：
* 令 $p$ 為 private key
* 令明文為 1-bit $m$ ，隨機產生 $q$ 與 $r$ ，加密後可得密文 $c=pq+2r+m$ 。
* 要解密，可以先 $c \mod p$ 後再 $\mod 2$ 來取得明文 $c$。原理是 $\mod p$ 後會剩下 $2r+m$ ，只要其小於 $p$ 就可以再透過 $\mod 2$ 來得到明文 $m$ 。
* 同態特性為何需要 bootstraping：
* 令 $c_0=pq_0+2r_0+m_0$，$c_1=pq_1+2r_1+m_1$ 。
* $c_0+c_1=p(q_0+q_1)+2(r_0+r_1)+(m_0+m_1)$
* 由此可以發現雜訊變為 $r_0+r_1$ ，如果大於 $p$ 則會讓解密解果不同，故需要做 bootstraping 來清除 noise 。
* 總而言之，因為雜訊會隨著同態計算而增加，故需要透過 bootstraping 來清除雜訊以保全計算的正確性。
## Zero-Knowledge Proof
:::info
* https://en.wikipedia.org/wiki/Zero-knowledge_proof
* https://blog.goodaudience.com/understanding-zero-knowledge-proofs-through-simple-examples-df673f796d99
:::
* 「零知識驗證」是一種可以讓 Prover (要求被驗證者) 不用透露秘密而可以說服 Verifier (要求驗證者) 他是真的知道那個秘密的方法。滿足以下三大特性:
* **Completeness**
* Everything that is true has a proof
* Prover 可以拿出足以說服 Verifier 的證明
* **Soundness**
* Everything that is provable is true
* 如果 Prover 拿得出正確的證明，那該證明絕對是正確的，無法被造假
* **Zero-knowledge**
* Only the statement being proven is revealed
* Prover 證明過程不會透露任何秘密的資訊
* 零知識驗證可以有「交互式」與「非交互式」，前者為一般的的情況下，雙方都必須在場才可以驗證；後者是 Prover 丟出證明後，其他 Verifier 自己再去做驗證。
* 抽象範例(阿里巴巴洞穴):
* Prover 隨機選擇 A 或 B 的通道進入，而 Verifier 則在外面等候。 A 、 B 通道有一道祕門可以連通。
* Verifier 隨機選擇一條通道要求 Prover 從該通道走出。
* 如果 Prover 有該密門的鑰匙的話，不論今天 Verifier 要求從哪條通道出來，應該都沒問題。如果是假的 Prover ，有可能會有幾次證明被矇到而成功，但在 50% 的機率下，不可能永遠都猜對。
* 實際範例:
* Prover 要證明自己知道秘密 $x$ :
1. Prover 計算一次性的 value $y=g^x\mod p$ 給所有可能的 Verifier
2. Prover 反覆計算隨機的 value $r$ 與 $C=g^r \mod p$ ，並把 $C$ 給 Verifier
3. Verifier 要求 Prover 計算與傳出 $(x+r) \mod (p-1)$ 或是 $r$
4. 如果 Verifier 要求 $(x+r) \mod (p-1)$ ，則 Verifier 可以透過計算 $g^{(x+r) \mod (p-1)} \mod p \equiv (C \cdot y) \mod p$ 來判斷是否正確。
5. 如果 Verifier 要求 $r$ ，那只要計算 $g^r \mod p \equiv C$ 即可。
* Prover 在沒有 $x$ 的情況下，猜測 Verifier 會要求 $r$ :
* 猜對，公布給 Verifier $C=g^r \mod p$ 並傳給他　$r$ ，驗證通過。
* 猜錯，無法計算 $(x+r) \mod (p-1)$ 給 Verifier ，驗證失敗。
* Prover 在沒有 $x$ 的情況下，猜測 Verifier 會要求 $(x+r) \mod (p-1)$ :
* 猜對，令 $r'$ 為要公布的 $(x+r) \mod (p-1)$ ，透過計算 $C'=g^{r'} \cdot y^{-1} \mod p$ 來公布 $C'$ 為 $C$ 值並傳給他 $r'$ ， Verifier 計算 $C' \cdot y=g^{r'} \cdot (g^x)^{-1} \cdot g^x \mod p \equiv g^{r'} \mod p$ ，驗證通過。
* 猜錯，因為不知道 $x$ ，故無法從 $C'=g^{r'} \cdot (g^x)^{-1} \mod p$ 回推 $r'-x$ 是多少，驗證失敗。
* 假 Prover 每次都有 50% 的機率會成功，但只要 Verifier 重複驗證夠多次， ZKP 失敗機率就會極低。

## Decentralized Identifiers (DID)
:::info
* https://www.w3.org/TR/did-core/
* https://medium.com/taipei-ethereum-meetup/intro-to-ssi-e643cd7300fa
:::
* DID 可以看成是除去集中式驗證機構的全球數位身分 (Unique Identifier)。
* 可以註冊於任何分散式帳本
* DID 的內容如下圖 :
* `DID Method` 為其註冊方式，例如 eth 。
* `DID Method SPecific String` 則是特殊的 identifier 。
* 每個 DID 會對應到一個 DID Document ，內容通常為代表身分的公鑰或是其他可驗證、認證的資訊。

## Blockchain Pruning
:::info
* https://medium.com/coinmonks/how-a-pruned-ethereum-node-can-fully-verify-the-blockchain-bbe9f29663ed
* https://dev.to/5chdn/the-ethereum-blockchain-size-will-not-exceed-1tb-anytime-soon-58a
:::
* 根據區塊鏈的架構可以分為 UTXO-based 與 Account-based ，兩者對於區塊鏈資料修剪 (Pruning) 的方式也有所不同。
* UTXO-based (Bitcoin) 的在 [Bitcoin TL;DR](https://hackmd.io/@ofAlpaca/BtcTLDR#Bitcoin-Reclaim-Disk-Space) 裡提過。
* Account-based (Ethereum) 的在 [Ethereum TL;DR](https://hackmd.io/@ofAlpaca/EthTLDR#Ethereum-State-Tree-Pruning) 裡提過。

## 以應用種類區分共識或區塊鏈系統
:::info
* https://zhuanlan.zhihu.com/p/35847127
:::

graph hierarchy {

                nodesep=0.1 // increases the separation between nodes
                
                node [color=Blue,fontcolor=Blue] //All nodes will this shape and colour
                edge [color=Black] //All the lines look like this

                Consensus -- {Public,Consortium,Private}
                Public -- {PoW,PoS,DPoS,FBFT}
                Consortium -- {PBFT,DBFT,HotStuff}
                Private -- {Paxos,Raft}
}

* **Ripple**, **Stellar** 皆為 FBFT 的使用者。
* **EOS** 有提出類似 BFT + DPoS 的 BFT-DPoS 。
* **NEO** 使用 DBFT 。
* **Libra** 的 LibraBFT 就是基於 HotStuff 。

### 隱私保護的區塊鏈
:::warning
* **Zcash** : zk-SNARK(ZKP)
* **Monero** : Ring Signature, Confidential Transaction
* **Grin** :
:::

### 隨機算法的區塊鏈
:::warning
* **Algorand** : VRF
* **Ontology** :
* [VBFT](https://medium.com/ontologynetwork/ontology-launches-vbft-a-next-generation-consensus-mechanism-becoming-one-of-the-first-vrf-based-91f782308db4)
* **DEXON** : VRF
* **Cardano(Ouroboros)** : PoS + VRF
:::
### Ontology
* VBFT 為 PoS + VRF + BFT 的結合共識。
* 透過 VRF 來選出 proposal node ，可能有複數個(原因同 Algorand)，各自提出自己的區塊。
* 透過 VRF 來選擇 Verification node ，他們會選出並驗證最高 priority 的區塊。
* 透過 VRF 選出的 Confirmation node 會對選出的區塊進行 BFT 投票。
* 最後投票通過的區塊會由 Confirmation node 廣播給大家，並進入下一輪。

### 拜占庭容錯(BFT)區塊鏈
:::warning
* **Cosmos(Tendermint)** :
* [知乎討論](https://zhuanlan.zhihu.com/p/38252058)
* [BlockGeek](https://blockgeeks.com/guides/tendermint/)
* [PBFT/HotStuff/SBFT/Tendermint 比較](https://decentralizedthoughts.github.io/2019-06-23-what-is-the-difference-between/)
* [Reddit 討論](https://www.reddit.com/r/cosmosnetwork/comments/8i42qa/compared_with_traditional_pbft_what_advantage/)
* [Tendermint Doc](https://tendermint.readthedocs.io/en/v0.11.1/index.html)
* [Tendermint/Casper/PBFT comparsion](http://blog.pranay01.com/consensus-protocols-tendermint/)
* **Hyperledger** : PBFT
* **Ripple/Stellar** : Federated BFT
* **Libra** : HotStuff
* [Medium HotStuff](https://medium.com/ontologynetwork/hotstuff-the-consensus-protocol-behind-facebooks-librabft-a5503680b151)
* [極客公眾號](https://www.geek-share.com/detail/2787159560.html)
* [LibraBFT](https://www.jianshu.com/p/3b3551833726)
* **Harmony** : Fast BFT
* **ThunderCore** : [PaLa protocol](https://docs.thundercore.com/thunder-whitepaper.pdf)
* **Ethereum** : [Casper-FFG](https://github.com/ethereum/research/blob/master/papers/casper-basics/casper_basics.pdf)
:::
### Tendermint
* Tendermint 考慮「安全性 (Security)」高過於「可用性 (Liveness)」。
* Tendermint 最大的缺點在於當 $f\ge1/3$ 時，系統會 halting 直到 $f$ 回歸正常，這也是以太坊未採用 Tendermint 的最大原因。
* 使用 PoW 則是考慮 Liveness 高於 Security ，因為他會有分支且是機率性的確認；Tendermint 則是相反，具有 deterministic 的確認。
* Tendermint 不會有像 PBFT 的 normal-case 或是 view-change phase ，統一跑到底。
* 同一個 round ，只會有 `value` 或是 `nil` 兩種值存在。
* Tendermint 總和上來講，特色為 :
* 使用 gossip protocol ($O(nlogn)$) 而非 broadcast 。
* 具有 locking 機制來確保 consistency 。
* 使用 DPoS 來選擇該回合的 leader 。
* Tendermint 討論 :
* 被 lock 住的 v 之後會被認定為唯一的 proposal ， (v,r+n) 可以接受，但是 (v',r) 不行。節點可以在不同 round 時投不同的值，但僅限 v 或 nil。
* 由於當 value v 被 lock 住後， round 是用於發生 halting 時，以區間 (round r+n) 去等待其他人的投票。round 對於每個節點可以是不一樣，但是最新的 round 會視為該回合最新的票。例如同個節點 (nil,r) 跟 (v,r+1) ，大家會採取的是 r+1 回合的票。
* 假設一次 round 無法達成共識，則會進行數次 round ，狀況有可能是 (nil,r) -> (v,r+n) 或是 (v,r) -> (nil,r+n) ，前者是原本該節點蒐集不到 2/3 的 prevote 或是 precommit ，後來網路恢復正常後蒐集到才投給 v ；後者則是相反。
* **PBFT,SBFT** 屬於 `stable leader paradigm` ，當 leader 出問題時才會去做 leader 更換，也就是 view-change 。
* **Tendermint,HotStuff** 屬於 `rotating leader paradigm` ，每回合的 leader 都會去做更換。
* **HotStuff** 為四階段投票，為的是省去不必要的等待時間 delta 。