2018年明星級項目Algorand簡介
2018年明星級項目Algorand簡介
6 人贊了文章
這個項目的白皮書及其生澀難懂，而且它還有兩個白皮書，一個2017年的，一個2018年的。兩個白皮書有一些地方意思相同但是表達方法又完全不同，理解起來簡直是讓人抓耳撓腮。我來來回回看了倆遍，因為不是學這個出身的，僅能靠著上下句理解把白皮書大概翻譯一下。有錯誤的地方請大牛出來指證，謝謝。
什麼是Algorand
Algorand是一款新型的付款協議，換句話說，就是和比特幣一樣的分散式記賬本。在我們繼續介紹之前，先介紹一下什麼是拜占庭將軍問題：
拜占庭將軍問題是Leslie Lamport（2013年的圖靈講得主）用來為描述分散式系統一致性問題（Distributed Consensus）在論文中抽象出來一個著名的例子。這個例子大意是這樣的：
拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。這10支軍隊在分開的包圍狀態下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊（一半以上）同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵騎馬相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們才能保證有多於6支軍隊在同一時間一起發起進攻，從而贏取戰鬥？
拜占庭將軍問題中並不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問題。Lamport已經證明瞭在消息可能丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。所以，在研究拜占庭將軍問題的時候，已經假定了信道是沒有問題的.
單從上面的說明可能無法理解這個問題的複雜性，我們來簡單分析一下：
先看在沒有叛徒情況下，假如一個將軍A提一個進攻提議（如：明日下午1點進攻，你願意加入嗎？）由通信兵通信分別告訴其他的將軍，如果幸運中的幸運，他收到了其他6位將軍以上的同意，發起進攻。如果不幸，其他的將軍也在此時發出不同的進攻提議（如：明日下午2點、3點進攻，你願意加入嗎？），由於時間上的差異，不同的將軍收到（並認可）的進攻提議可能是不一樣的，這是可能出現A提議有3個支持者，B提議有4個支持者，C提議有2個支持者等等。
再加一點複雜性，在有叛徒情況下，一個叛徒會向不同的將軍發出不同的進攻提議（通知A明日下午1點進攻， 通知B明日下午2點進攻等等），一個叛徒也會可能同意多個進攻提議（即同意下午1點進攻又同意下午2點進攻）。
叛徒發送前後不一致的進攻提議，被稱為「拜占庭錯誤」，而能夠處理拜占庭錯誤的這種容錯性稱為「Byzantine fault tolerance」，簡稱為BFT。
中本聰在比特幣中創造性的引入了「工作量證明（POW: Proof of Work）」來解決這個問題，有興趣可進一步閱讀工作量證明。通過工作量證明就增加了發送信息的成本，降低節點發送消息速率，這樣就以保證在一個時間只有一個節點(或是很少)在進行廣播，同時在廣播時會附上自己的簽名。
這個過程就像一位將軍A在向其他的將軍（B、C、D…）發起一個進攻提議一樣，將軍B、C、D…看到將軍A簽過名的進攻提議書，如果是誠實的將軍就會立刻同意進攻提議，而不會發起自己新的進攻提議。
以上就是比特幣網路中是單個區塊（賬本）達成共識的方法（取得一致性）。理解了單個區塊取得一致性的方法，那麼整個區塊鏈（總賬本）如果達成一致也好理解。我們稍微把將軍問題改一下：假設攻下一個城堡需要多次的進攻，每次進攻的提議必須基於之前最多次數的勝利進攻下提出的（只有這樣敵方已有損失最大，我方進攻勝利的可能性就更大），這樣約定之後，將軍A在收到進攻提議時，就會檢查一下這個提議是不是基於最多的勝利提出的，如果不是（基於最多的勝利）將軍A就不會同意這樣的提議，如果是的，將軍A就會把這次提議記下來。這就是比特幣網路最長鏈選擇。
Algorand不使用POW機制，而是選擇了新的方向 – RPOS（Random Proof of Stake）。使用這種方式的前提是必須二分之三的網路用戶是不作惡的。如果超過的這個範圍，則拜占庭將軍問題本身將無解。這一點其實也是這個項目被有些人詬病，但是通過巧妙的設計，Algorand將可以在網路被嚴重惡意控制下仍舊自主無錯運行。我會把2017年的白皮書和2018年的白皮書結合分析。
Algorand項目優點
產生區塊時間短
區塊產生時間在大家都是良性用戶時，只需要兩步。如果有任何惡性用戶企圖篡改信息，則需走完五步。即使是這樣，產生一個區塊的時間是固定的（幾分鐘）。在這裡，所有用戶不需要同步他們的時間，他們只需要在自己規定的時間內完成工作並保證每個用戶的時間流逝的速度是一致的即可（在紐約的一秒鐘和在日本的一秒鐘長度一樣）。
反分叉
協議制定沒有兩個良性用戶可以同意兩個不同的消息。因此只能有一個消息為真實消息，如果有人試圖雙花攻擊（詳見下）。則理論上他可以開一個新的區塊裡麪包含錯誤的信息並把上一個區塊的廣播時間延到無限長，但是受制於第一條的限制，每個區塊產生時間為固定並通過之後會介紹的五步方法，任何的惡意分叉都會被幹掉。
雙花攻擊：
雙花攻擊（double spend attack），在介紹51%攻擊的時候出現過這個詞語。光看中文名可能會因為漢語的多重含義而理解錯，但英文名就很明顯的表達出意思了。雙花攻擊就是一筆錢花了兩次，也可以稱之為雙重支付攻擊。
快速從分叉中恢復
如果強行出現分叉，新的分叉將會被五步方法幹掉，然後全網把分叉浪費掉的時間歸零，從新開始。
Algorand如何做到這些特點的
隨機預言機與電子簽名
黑盒隨機預言機來進行256位的公/私鑰生成。每個公/私鑰對應一個可防選擇性祕文攻擊的電子簽名。這是如何做到的呢？根據我的翻譯（誤）應該是這樣的：每個公/私匙鑰對應其禪達的消息（m），其電子簽名只有一堆位元組中的一串位元組。即使有個惡意的產生出新的公/私鑰，他也無法通過選擇性祕文攻擊猜到真正的電子簽名的位元組是什麼。
設立臨時簡單假設
這個假設包括總用戶的數量為3x惡性用戶數量+1。換句話說，就是良性用戶無論在什麼狀況都比惡性用戶對於維護拜占庭將軍協議穩定性上多一個人。（N=3t+1，t為惡性用戶）如果超過了維護拜占庭將軍協議穩定性的話，我們定其為「臨界值」。
每一個用戶i會對協議在一開始的時候有一個輸入為vi。一堆用戶的vi組成了「大V」（誤）。所有用戶的職責為同一大V中的一個數字。
如果有人惡意攻擊並生生新的公/私鑰，則這個惡意的公/私鑰生成的「vi」將不在大V裏。（⊥ ∈/ V）。我們給他它起個名字叫「惡意值」。
協議中會有一個一直保持自動（無互動）和隨機的函數字元串R。作為選擇隨機用戶的指標。
從有許可權系統到無許可權系統的過度
有許可權即所謂的超級節點，工作證明等方式給驗證者施以門檻。無許可權即進入協議的用戶不需要被驗證。他們可好可壞。即使當惡意用戶可以在任何時間立即協調控制任何他想控制的用戶（前提是2/3的用戶是善意的）；惡意用戶可以完美的協調大量被控制的用戶。在這種條件下，惡意用戶也不能進行惡意分叉（雙花）。這種過度意味著會使大量用戶聚集到Algorand的協議下，因為相對容易並沒有入門門檻。
協議交流
這個部分稍微生澀一些。我們如何解決協議的不可能三角（Impossible Trinity）：安全性，可拓展性與分佈性呢，Algorand的五步法如下：
第一步：價值提案
情況1：在一個固定時間段內，用戶i收到的協議上反饋數量超過臨界值數量的惡意值時，系統自判用戶i提議vi（壞）。
情況2：反之，用戶i提議v（好）。
第二步：過濾
在情況1的前提下，用戶i指認其領導者L，系統自判用戶i軟提議v，我們可以看到，對於情況1，這是一個惡意用戶，但是系統會鑒別其惡意值並在惡意值爆表的前提下，為這個惡意用戶對領導者L投贊成票（在這裡我們認定領導者的決策是善意的），我們在這裡可以把vi看成是惡意票，v為善意票。
情況2：反之，用戶i提議v（好）。
第三步：認證
如果用戶i發現整個協議中投善意票的用戶超過了臨界值，則用戶i對其軟投票進行認證，認證後，我們可以認為這個投票即為有效票。如果善意用戶並沒超過臨界值，則軟投票報廢，系統繼續提取隨機用戶進行再投票（即用戶的可替代性，這個替代可以是在這五步內的任何一個環節）。
第四步：完成環節1
在用戶i認證本輪投票後，他的下一輪的投票即為v，這等於協議判定這個用戶在下一輪的投票中自帶良性身份（v）。反之，則自帶惡人身份。
第五步：完成環節2
如果用戶i在本輪投票後未被下一輪選中，則他的身份變成待定良性身份（va）。反之，則自帶待定惡人身份。
其他
區塊的形成和廣播同步。這樣用戶i可以在看不到區塊的前提下進行軟投票。因為軟投票的速度比區塊生成要快，因此，在生成真正的區塊前，超出臨界值數量的良性用戶應該早已完成了驗證，保證了區塊形成的速度。
