# Team 7
## Hw1
------------請在以下編輯-----------Hw1
------------Pitcure-----------
-------Email Information------
Pow為圖片經過SHA256轉換完的2進制

**系統收信時間：2018/10/5/20：03 by TA**
------------Pow---------------
1001100011001111000100110111100010100000101100000011110000110010001000111100011100010011110001000001010100110111101111011101110101110010000010001101010111011110011110011100101111111001101111010101111001101001101101001101110000101001001101111101000100111
------------Score---------------
**e.g. 80 by Team15 (TA)**

=========================
# 期中報告
[11/12 ppt](https://docs.google.com/presentation/d/1sRQiEiSULrLSXxF-HzN7xOBMnzgw7ggolnrWp5bTnUM/edit#slide=id.p)
[Blockchain Consensus Protocols in the Wild（Permissioned blockchain）筆記](https://hackmd.io/atb0uuCyQOus18hclYvVEQ)
# 期末報告
[1/7 ppt](https://drive.google.com/open?id=1uK7n_2IouHtUq9sDAZpJn79s2_R25q_u)
[Proof of WSJ討論摘要](https://hackmd.io/bq_27KjXTPiMfeX3wVH0Sg?both)
------------請在以下編輯-----------
## 宗旨
**Bulid a fairer and greener alternative protocol for cryptocurrency**
## 目前問題
對於我們小組來說，我們認為，目前問題最大的其實是比特幣的耗電問題。

由於比特幣本身是採取POW共識，node之間相互競爭的是彼此之間的算力，在利益的的推動之下，大家會開始不計代價的購買CPU、GPU來提升自己挖到礦的機率，但正因為如此，因比特幣而消耗的電力歷年下來不斷的在成長，到了去年2018，其耗電量佔全世界的0.5%，若將比特幣當成一個國家，在全世界國家消耗電力排行榜中，他可以排到第43名，共超越了100多個國家，同時，根據研究估計，若以相同的成長速度來看，比特幣的耗電量將會在2019年佔全世界的5％，將未來全世界國家耗電量排名的第9名，耗電量為第14名台灣的4倍，這是一個相當恐怖的數字。
## 解決方案
**他人的解法**

為了解決耗電量問題，其實有非常多新穎的解法，這邊我們將焦點放在2015年所提出的新共識—Prove-of-space(PoSpace)(或叫做Prove-of-capacity, PoC)，相較於比較node間算力的PoW來說，他將比較的標的物改成了disk內所剩餘的空閒容量，用這樣的方式避免算力競爭以降低整體的耗電量。於此同時，許多的貨幣及應用相應而生，e.g. Filecoin, MaidSafe, IPFS等等，但其中最為著名的，是所謂的奇亞幣，此公司創辦人為布萊恩・科亨（Bram Cohen），他同時也是BT(BitTorrent)的發明者，於2017創辦公司，目前已募資340萬美元，預計募資金額為5400萬美元，這是一個相當驚人的數字，同時也讓我們相信密碼貨幣這樣的一個發展方向是相當具有競爭力的。

**我們的解法**

想法：回顧他人解法，我們發現到雖然他能解決一部份的耗電問題，能仍舊是換湯不換藥，依然會專注在“比較”這樣的方法上，回顧人類歷史與生活，只要有比較，雖然一開始可能會提升競爭力，但接踵而來的，總是令人喘不過去的心理壓力及創傷，因此，PoC這樣的方式，也許在未來會有我們還未想到的問題，正因為如此，我們才想用一樂透彩券的方式，使node在不做比較的狀況下達成共識。

流程：每一輪樂透當中，每個node先各自猜一個號碼並將他傳播給其他nodes，直到樂透時間截止後，將每個node的位置及所猜測的號碼當作一input輸入到一公開函式f內，會得到此期樂透彩的中獎號碼，得獎者就可以做block。

## 難題及討論
這樣的一個共識，看起來雖然簡單，但在實作上若要考慮到各式各樣的corner cases，整個問題會變得相當的複雜，以下舉幾個我們在設計此演算法時所面臨到的問題來給大家當做參考。

### **莊家問題**

定義：在傳播各自所猜測的號碼時，大家都會各自收集其他nodes所傳播的消息並將其存入自己的list裡，但因為網路速度不同，時間戳也不同，彼此所收集的到的list會長得不一樣，那究竟要信任哪張list就是一大問題（因為得出來的中獎號碼會不樣）

解法：既然是樂透彩，那有頭獎也可以再增設一個二獎，若一node為上一輪的二獎得主，那在下一輪的樂透彩中，就以他所收集到的list為主，換句話說，就是讓二獎得主來主持下一輪的樂透彩，同時，為了維護公平性，他本身不能參與競猜。

主持流程：二獎得主p在收集完成自己的list之後，會將此list傳播給其他在此list上的node，而這些node會發表他們對於這份list同不同意的意見，若同意的人數超過一定比例，則可決定出頭獎號碼，反之重投。

### **惡意拒絕**
儘管上述的方式看起來很完整，但若是帶入人性本惡的情境來思考，則會發現許多淺在的問題。

定義：因為二獎得主在收集大家的意見之前，會先將他收集好的list傳播給其他nodes，但是，在這些nodes拿到list時，同時又有公開的function f，他們就可以直接推測出頭獎號碼是啥，在這樣的狀況下，假如他們發現自己沒有中獎，他們就會反對這個list，整體下來，因為只有一個node會同意，就會一直不斷的重複投票而無法收斂。

解法：上述狀況會發生的根本原因，其實是因為在大家投票之前就已經知道了中獎號碼，那麼反過來想，我們只需要讓大家在不知道頭獎號碼的狀況下做投票即可。我們的解法是，在二獎得主傳播list時，不要傳播完整的list，而是某些內容被遮蓋過的list即可。


### **Fake list**
二獎得主非常的邪惡

定義：雖然二獎得主本身無法參與投票，但他可以設法讓自己的好朋友、親戚等等中獎，之後再一直世襲下去。而為了要達到這個目的，他可以有兩種做法：
1. 一開始就傳假的list給其他nodes
2. 等大家都同意之後公開假的中獎號碼


1的解法：非常簡單，因為在一開始猜測號碼時，是會將號碼傳播給所有的nodes，也就是說，每個人會收集自己的list，這時只要將自己的list與二獎得主傳播的list做交集比對，正確的在一定比例以上就同意，反之就可以拒絕。


2的解法：在二獎得主傳播list前，先將此list內的所有內容當作SHA256的input，計算對應的hash值H，並將此H傳給所有的nodes，等到大家第一階段同意時，在公開完整的list，讓大家比對是否跟H是相互對應的。
但其實這樣做會有一個問題，因為第二階段同意時，大家又會得到完整的list，這樣又會重回到剛剛惡意拒絕的問題，所以必須將與Ｈ比對這件事情寫死，也就是說，二獎得主不需要將H傳給大家，而是在公開中獎號碼時，直接硬性比較跟H是否相互對應。


### 涵蓋以上三種問題與調整，整體架構如下

## Feature Work
1. 將現有的protocol涵蓋進去（e.g. Collect opinions可用PBFT實現）
2. 也許頭獎者可以主持下一次的樂透，而不需要二獎者這個角色。

## 體悟與感想
任何一個簡單的共識問題，只要放入**人性本惡**這個假設，整個架構與思考邏輯就會變得非常的複雜。