Coordicide 重點節錄
移除 Coordinator 一直是 IOTA Foundation 的目標，而日前他們將白皮書 [1] 釋出了，大致上可以理解移除 Coordinator並引入投票機制作為主要解決方案，另外還有以下的目標將會以模組的形式在往後加入節點中：
- 將交易最終確定時間降為秒級
- 降低 Reattach & Promote 的需求
- 自動尋找節點的機制
- 壓縮訊息傳遞的 Metadata
以下將會整理變更的重點，並簡介每層新的協定與共識機制。
節點身份與魔力(Mana)
在沒有 Coordinator 的網路下，我們需要能夠識別出節點的身份才能讓它們投票。這樣的話每個節點會需要產生獨自的身分識別，並以此來簽署訊息或者進行投票來確保可靠性。但這樣的分散式系統又容易遭受女巫攻擊。要防止這樣的攻擊方式的話，就需要要求節點在投票時提供稀缺資源，像是在 PoW 使用的算力，或者在 PoS 的 stake。PoS 雖然的確不像 PoW 那樣受到擴展性的難題，但是在「最長鏈準則」下的話 PoS 卻會有以下兩種常見的攻擊向量。一是「nothing-at-stake」，stakeholder 可以同時投兩筆互斥交易而且不會被懲處或承擔任何風險。另一個則是「long range attacks」，龐大的 stakeholders 可以預先秘密組起另一條鏈然後在之後才進行廣播。
由於 Coordicide 的解決方案並不依賴於最長鏈準則，以下提出的方法並不會有這些問題。這個提出的信譽系統稱為魔力(Mana)：
- 進行交易轉移 IOTA 時，使用者會對轉移得 IOTA 證明擁有權
- 使用者可以連結交易到他們選擇的節點，將節點 ID 加到交易簽章中。在大多數的情況下，傳送交易時應該都會使用相同的節點
- 交易會讓魔力從之前指派的節點轉到下個節點
魔力系統是個建立在資金上抵禦女巫攻擊的信譽系統，魔力不僅可以透過轉移 IOTA 交易獲得，也能透過提供良好的服務給社群或傳播有效交易來獲得。而這些魔力作為良好的信譽評比，在之後也能夠用來獎勵這些可信任的節點，像是速率控制（rate control）或是投票模組。魔力還建立在信譽是非常難取得且容易失去的條件下。信譽系統最重要的能力之一就是能夠撤銷不良份子之前所獲得的信譽。在 IOTA 的話，如果使用者發現他所用的節點行為不正常像是傳遞無效交易的話，只要轉移指派到其他節點即可。
最後與其他抵擋女巫攻擊的機制不同的地方是，魔力的 nodeID 並不需要擁有者連結私鑰然後強播使用者參與複雜且具風險的 staking 處理機制。魔力系統確保原本的資金就能投入參與信譽系統中。
鄰居自動互聯(Auto-peering)
在對等(peer-to-peer)網路中節點的鄰居是唯一資訊的來源，任何尋找鄰居的機制都需要專注在連接到健康且誠實可信的節點。IOTA 接下來會實作自己的 peering 機制讓每個節點都有自己的標準來選擇潛在鄰居。攻擊者沒辦法在選擇過程影響節點的決定，節點對於網路觀察到的面貌會是本地端且無法預測的。這能夠抵擋外部攻擊（像是日蝕攻擊）並且讓攻擊者無法鎖定特定節點的互聯過程，確保節點永遠最少有一定數量的誠實鄰居。除此之外，此互連機制還會嘗試組織小世界網路(Small World Network)，讓每個節點都可以透過最少的一定步數，以期藉此加速共識。
防止濫發(Spam Protection)
目前 Tangle 使用基於 PoW 的簡單機制來防止濫伐，不過用 PoW 來控制交易產生速率是不實際的，因為這會帶來挖礦競賽(Mining Race)。新的機制會使用自適應的速率控制機制，他會按照不同因素像是最近產生的交易與魔力，來自動變更每個節點的 PoW 難度。注意這與 PoW 共識不同，這邊做的 PoW 是作為速率控制以防止挖礦競賽，所以也不會用到特別大量的算力。
在此模型中，越高魔力的節點能夠產生越多的交易，且需求不會比低信譽節點花費來得高。但是在一段時間內產生越多交易的話，PoW 難度也會隨之增加。速率低的話難度則只要一點點就足夠。這樣的機制能夠有兩項好處：
- 讓網路能防止資源夠多的節點，像是 ASIC 節點能夠影響共識
- 在 IoT 情境下，大多數會是算力低且速率較慢的節點，這讓這些節點能快速穩定傳送交易
Tips 選擇演算法(TSA)
在過去節點使用一個特定的隨機漫步作為 TSA，這能夠組織起健康且判別出權重最重的 Tangle。但這卻也帶來一些不想要的結果：
- 誠實交易如果沒有累積足夠權重的話容易被遺棄，目前轉圜的方式是透過促進(Pomotion)和重新連接(Reattach)。但這樣卻大大降低了交易的考靠性
- 攻擊者可以去嘗試挑戰隨機漫步並組成惡意的架構像是寄生鏈，或者進行分裂攻擊阻止網路達成共識
- 計算權重相當花費資源，這讓協定的擴展會有些困難，尤其是在高吞吐量的情形下
如果加上投票機制能決定哪部分的 Tangle 是多數傾向的話，不僅可以讓選擇 tip 的過程更迅速和便宜，更能帶來:
- 衝突解決能更迅速，並降低交易連接到 Tangle 不合理的部分的機率
- 不再用權重判定 TSA ，降低合理交易被遺棄的風險
解決衝突
只透過建立在權重上的 TSA 共識機制目前仍讓 IOTA 受制於挖礦競賽。所以為了解決此問題，IF 提出了一層安全機制讓節點交換投票意見。在過去幾年來這類的投票模型就有不少研究過: 在機率模型下使一節點與一小群節點互相交換意見數輪，並互相左右自己的意見。在 70 年代投票模型就曾獨自被 Holley/Liggett 與 Clifford/Sudbury 提過(https://projecteuclid.org/euclid.aop/1176996306 以及 https://academic.oup.com/biomet/article-abstract/60/3/581/217208)，然後自從那時起就有不少相關的研究論文依序出現。有了投票機制後可以帶來不少益處:
- 與其等待狀況自行解決，節點與鄰居會自行交談來親自解決衝突
- 節點的投票權重依據自己有多少魔力。因此良好的節點能夠大大地影響網路
- 就算誠實節點沒有在產生任何交易，他們仍會用投票保護網路。加上之前提到的女巫攻擊防禦機制(魔力)，這樣能不依賴 PoW，取代區塊鏈上用誠實算力的方式
- 達成共識不再依靠 TSA 或 Tangle 的結構，這讓其他 DLT 能夠快速銜接，如果達成未來有其他的需求。這也能防止任何形式的攻擊，像是操縱 Tangle 結構來破壞共識機制，包含那些白皮書提到的危險攻擊，像是寄生鏈攻擊等
-
而傳統投票機制的缺點是，他們沒辦法有效的擴大規模。他們通常都需要網路參與者完整機確的意見，而這會造成大量的訊息傳遞阻塞。所以 IF 提出了新的方案 Shimmer，一個可以克服這些傳統機制造成的問題的投票方案。
微光 (Shimmer)
Shimmer 會是個獨立自主的媒介，會依照一些預先定義的規則去反應，在大自然中有很多這樣的系統，像是蜜蜂、螞蟻以及魚群等等。一些簡單的規則就能夠建構出複雜難以置信的功能，並隨著時間形成系統中的緊急應變特性。Shimmer 共識演算法也一樣，與其讓所有節點都嘗試整理出同樣的意見，Shimmer 只關心一小群子集中節點的意見，並讓共識組織成網路中的緊急應變系統。當衝突發生時，Shimmer會讓節點多次交換他們所能解決衝突的交易給其他鄰居，直到達成共識為止。節點會拿到所選擇的 Tangle 部分的全域觀點，這步是保證共識的關鍵步驟。在某些狀況下，節點甚至能決定將這些部分列為最終確認。這代表他會結束參與投票，且不會再更改決定，就算有攻擊發生讓意見更改了。在 Shimmer 作為 Tangle 的共識機制後，喜歡或不喜歡一筆交易都將會造成廣大的影響。如果交易被節點喜歡的話，就代表該節點也喜直接或間接驗證此交易的後續交易。反過來說，如果交易被不喜歡的話，那後續的交易也不可能被喜歡。
值得注意的是對所有交易投票並不是必須的，沒有產生衝突的交易可以直接依據本地調整碼(local modifiers)來直接視為喜歡(像是經過一定的時間都沒產生衝突)。投票只需用來解決衝突或者特殊情況。節點會拒絕那種一次喜歡兩筆衝突交易的票，這讓節點必須決定一個唯一的生存者，要視節點違反此規則的話，則會遭受忽視或者永久被其他鄰居遺棄。除此之外，誠實節點也沒有理由去投兩筆互斥交易，因為這完全沒有誘因也沒有任何獎勵(更可能被懲罰)。
接下來會介紹兩種方式讓投票如何進行並保全整個機制，他們會是未來實作的候選，並在往後會在測試網路進行審查，他們分別是:
- 細胞共識(Cellular Consensus)
- 快速機率共識(Fast Probabilistic Consensus) [2]
細胞共識(Cellular Consensus)
在細胞共識中投票過程被塑造成細胞自動機 (cellular automaton)，可以把節點想成是一個細胞然後會監控周圍鄰居的狀態，然後依此調整他們的意見。而實際的共識演算法也非常簡單，只需要五行就能解決:
If NumberOfNeighborsPreferringTransaction(tx) > NumberOfNeighbors / 2 {
PreferTransaction(tx)
} else {
DislikeTransaction(tx)
}此機制主要能讓節典能採納大多數鄰居的意見，並以此絕大多數來決定喜歡或不喜歡那些交易。而且這十分快速且穩定，以下圖示顯示一萬個節點如何在 128 個衝突交易中達成共識(不同眼色代表不同節點)，可以看出網路要達成共識只需要幾秒的時間:
隨著節點數量增加，網路中交易傳遞的時間也會隨之增加，但這不會影響達成共識的時間。意見是在本地端決定的，所以網路中節點都是同時進行。不過一直與相同鄰居交換意見的話也很容易被攻擊，所以這還會再加上一層依據魔力信譽系統的互連機制，節點會傾向與魔力接近的鄰居相連。這讓攻擊者的成本大幅增加，甚至是想成為鄰居都會有困難，這也增加另一個保持高信譽的誘因。隨著誠實節點補魔越多，網路也會因此越來越安全穩固。
意見八卦(Gossip about Opinion): 有機體的免疫系統
將節點對待為像是有機體的細胞讓這樣的系統可以實作出「免疫系統」。這讓網路能抵禦攻擊，強制參與者必須按照規則走，並提供比傳統的女巫攻擊防禦機制更安全的防禦手段。因為所有鄰居都是隨機選擇的， Shimmer 達成共識會是非常依靠機率的。但在節點觀點上的話，細胞共識會能夠是確定性的。如果我們可以知道節點的意見，那我們便可以驗證節點的行為。惡意節點違反規則的話便能夠被偵測出來，並馬上被鄰居驅逐。此協定被稱為「意見八卦」 (Gossip about Opinion)，而大致上的做法如下:
- 每隔一段間隔，每個節點會傳送「心跳」(heartbeat) 訊息給鄰居。訊息會包含他目前的意見以及為何未產生這樣的意見(像是因為它鄰居在前一輪有這樣的意見)
- 為了壓縮交換訊息的數據，只有在連續心跳中有不同時才會傳送出去，像是只有那些交易 hash 喜歡的狀態變更時
- 節點會簽署心跳訊息及意見確保真實性
這樣一來有心跳訊息的話就能夠達到:
- 強制節點產生正常的聲明並在網路中保持活躍
- 同步鄰居間的意見，讓節點能依據上述規則更新自己的意見，且不必持續向其他節點請求
這樣讓節點能夠驗證鄰居是否為誠實的，那些違反協定擅自更改意見的鄰居將會馬上驅逐於網路。而且既然訊息是有簽章的，不正常的行為便也能夠追蹤，查證出訊息是從哪個節點發出的。這樣的做法還有幾項特點，它是非同步的、簡單容易實作，訊息傳遞非常有效率，而且達成共識的速度極快，讓攻擊能夠快速被避免。
雖然緊急應變現象是常見於生物系統中且證實非常有效的，但它非常難用數學去模組化，因為通常這是複雜且混亂的行為本質。此方式最大的問題是很難有效地用正規科學方式證明它。要部署到主網前，會需要在測試網路詳細地研究驗證細胞共識。
快速機率共識(Fast Probabilistic Consensus)
為了彌補細胞共識的缺點，IF 同時還分析了另一種投票過程，並且已經用數學模型闡述並驗證了，這個方式稱為快速機率共識(Fast Probabilistic Consensus)。它基本的準則和細胞共識類似，但是和同時間在鄰居間非同步進行投票不同，其投票過程會分成數輪。在每輪每個節點會選擇新的隨機節點子集並請求它們現在的意見。節點的意見就會依據大多數節點回傳的來形成，但是這邊的絕大多數不會是 50%，而是用一種去中心化的隨機數列 [3] 來產生閾值。選擇不可預測的全域閾值讓我們可以防止攻擊者想要延遲共識。此投票過程會收斂的非常迅速，就算在最糟糕的策略且有惡意節點的狀況下投票也是如此。而且這也已經過論文證明，大致上的規則如下:
- 如果對手知道誠實節點所用的規則，那它便能夠預測他們的行為並調整策略來持續延遲過程
- 想像一下如果誠實節點要改變意見的閾值是固定的，那麼擁有足夠節點的惡意角色便能夠調整它的節點歡/不喜歡的交易來強迫網路保持在分裂(或無法達成共識)的狀態下。有了全域隨機數值的話，便能夠消除這樣的可能性，在規則一致的同時，使對手無法進行預測
- 這讓網路在一定時間後永遠無法保持在分裂狀態下，而且這些隨機數值僅會在網路初期分裂狀態時才會有影響，而不會造成網路共識的衝擊
在經過數輪投票後，如果節點都沒有變更意見的話，那這樣的意見便能視為最終確認的，且不必再進行投票。至於是幾輪則是依據網路能夠達成的事的情況，通常都會是非常高能達成共識。
References
[1] The Coordicide White Paper: https://files.iota.org/papers/Coordicide_WP.pdf
[2] On fast probabilistic consensus in the Byzantine setting: https://arxiv.org/pdf/1905.10895.pdf
[3] On a decentralized trustless pseudo-random number generation algorithm: https://eprint.iacr.org/2016/228.pdf
