# The Coordicide 正體中文翻譯

Coordicide Team, IOTA Foundation
May 2019

原文：[The Coordicide](https://files.iota.org/papers/Coordicide_WP.pdf)

協作譯者:
- @jserv (Ching-Chun Huang `<[e-mail]>` )
- @jkrvivian (Ching-Hua Lin `<[e-mail]>`)
- @Waynew ()
- @proof.k ()
- @yillkid (Jyun-Yu Huang - `<[e-mail]>`)
---

## 詞彙表

詞彙 | 解釋
---- | -------
拜占庭節點 | 分散式系統中試圖故意破壞系統運行的參與者，例如，通過將消息不轉發給其他參與者來破壞系統。
共識 | 指如何在分散式多代理系統中對存在分歧的特定資料或值達成一致的問題。
協調器 (coordinator) | 發布里程碑的可信實體，以保證最終結果並保護 Tangle 免受攻擊。
字典攻擊 | 一種暴力攻擊技術，通過不斷嘗試無數種可能性（類似於查字典），來找出密碼以破壞認證機制。
日蝕攻擊 | 一種網路攻擊方式，旨在隔離並攻擊特定節點，而不是整個網路。
創世交易 | 在 Tangle 中產生的第一筆交易。
心跳 | 由硬體或軟體產生的周期性訊號，用於指示正常操作或同步計算機系統的其他部分。
歷史 | 被給定交易直接或間接驗證的交易記錄。
里程碑 | 協調器發佈的特殊里程碑交易。里程碑的屬性將在 2.1 節中詳細討論。
鄰居節點 | 在網路中相連的節點。
節點 | 作為 IOTA 網路中的機器，它的作用是發佈交易並驗證現有交易。
對等連接 | 發現並連接其他網路節點的過程。
工作量證明 | 一種通過高運算成本，耗時久的方式來產生資料以滿足某些要求，而其他節點可以快捷方便的驗證。
彩虹表攻擊 | 預先計算生成的表，用於反推攻擊雜湊函數。
隨機漫步 | 一種數學方法，描述由某些數學空間上的一系列隨機步驟所組成的路徑。
鹽 (salt) | 一種隨機數，被用於單向雜湊資料的附加輸入。
社交工程 | 以欺詐為目的，並使用不正當手段操縱個體洩露機密或個人資訊。
女巫攻擊 | 女巫攻擊是指試圖通過偽造多個虛假身份來控制對等網路。
Tip | 尚未被驗證的交易。
交易 | 在兩個節點之間傳輸價值或資料的資訊。如果某交易的完整歷史為已知狀態，則該交易是可靠的。

## 縮寫

| 英文縮寫解釋 | 中文解釋 |
---- | -------
|**ASIC** Application-Specific Integrated Circuit. | 特定用途的積體電路 |
| **CA** Cellular Automata. | 元胞自動機 |
| **CLIRI** Coo-Less IOTA Reference Implementation. | 不依賴協調器的 IOTA 參考實作 |
| **DAG** Directed Acyclic Graph. | 有向無環圖 |
| **DLT** Distributed Ledger Technology. | 分散式帳本技術 |
| **IF** IOTA Foundation. | IOTA 基金會 |
| **IRI** IOTA Reference Implementation. | IOTA 參考實作 |
| **PoW** Proof-of-Work. | 工作量證明 |
| **TSA** Tip Selection Algorithm. | Tip 選擇演算法 |
| **VDF** Verifiable Delay Function | 可驗證延遲函數 |

## 1 前言

IOTA 的願景是經由安全的零交易費和資料傳輸系統，為物聯網和未來的網際網路建構一個即時經濟體系。實作這一願景，是為瞭解決當前各種分散式帳本技術 (DLT) 普遍存在的一系列問題：首先，IOTA 需要有比區塊鏈明顯更高的吞吐量，而區塊鏈的內在瓶頸使得交易記錄聚合成鏈式資料；其次，交易手續費在小額交易中是一種障礙，但這種手續費在基於 PoW，同時包含用戶和礦工的 DLT 中卻是必要的。與這些現存的 DLT 不同的是，IOTA 使用一種叫做有向無環圖（DAG）的結構，如同 IOTA 白皮書[30]中所述，它在理論上可以達到無上限的資料吞吐量。此外，每個網路節點都能夠發布和批准交易，這種模型使得 IOTA 可以去除區塊鏈架構中的交易手續費，從而促進小額支付網路系統的構建[31]。

早期 DLT 專案的一個常見問題是，網路不夠健壯，不足以支撐它依賴的安全機制按照設計的方式運行，因為它們的安全機制需要假定網路已經足夠成熟。因此，DLT 通常在一開始就在外部採取各種「引導」措施，確保網路安全成長到成熟階段。在 IOTA 的目前實作中，同樣是仰賴一個中心化的協調器 (COO) 來確保安全性，以消除不誠實節點破壞尚未成熟網路的風險。在這個階段，IOTA 對共識的定義是，要求每一筆交易都被協調器簽署的交易(直接或間接)所確認。換言之，協調器可被視為「終極裁決設備」。

我們認為基於中本聰共識機制的加密貨幣體系的願景，可經由變更網路中關於多數算力的基本假設 (即最長鏈機制) 來進行改進。在 IOTA 目前的實作中，由於協調器的存在，則無需誠實節點來構成網路的主要算力。但這僅是個臨時的舉措，IOTA 的願景是超越傳統區塊鏈的網路共識機制。本文的目的即在於，論述 Coordicide 項目是如何經由一組相互配合的網路組件，來實作協調器的移除工作。這些組件的添加，不會對 Tangle 網路現有的基礎功能特性造成影響。

根據 IOTA 基金會作為一個非營利組織的章程，我們研究部門的目標包含：透明度，協作和社區參與。我們計劃開放式地展現研究工作，以期獲取學術界和社區志願者的反饋意見。有一點需要注意的是：由於我們的研究對象是高度動態的，因此需要對各種提案進行模擬和測試，然後才能在主網上對這些組件進行部署。我們強調，這裡展現的一些提案，依然還在研究當中，沒有完全定型。當我們的研究取得進展，進行模擬的時候，這部分提案是有可能被修改的。

---

1. 實際吞吐量受到硬體物理定律的限制
2. 例如，比特幣過去曾使用檢查點。鏈接: [Checkpoint Lockin
](https//en.bitcoin.it/wiki/Checkpoint_Lockin)

圖1：Coordicide 模組間的連接圖

為了移去對協調器的依賴，需要解決一系列的挑戰性問題。本文中涵蓋的這些問題，可以用圖 1 中的模組來表示。接下來，我們對 Coordicide 的當前狀態和未來的研究方向，給出一個簡要的概述：

* **節點責任**: 在第 3 節中，我們提出全域節點 ID 的概念，並且描述了一種在不需要節點擁有者去冒險或者展示資產的情況下，能夠防範女巫攻擊的保護機制。對發佈消息的節點進行識別，是執行特定網路拓撲(通過節點自動相互連接)或者懲罰不良行為(通過速率控制)的基礎。
* **節點自動相互連接**: 每個分散式系統都需要一個能夠發現，並且可靠地連接到鄰居的自動化過程。在第 4 節中，我們將會討論在 Tangle 網路中的節點自動相互連接機制。
* **速率控制**: 為了確保網路不超過其容量，在第 5 節中，我們引入一種機制來控制通過網路傳播交易的速率。這種方法可以根據發布節點的統計資訊，選擇性地過濾掉一些交易。
* **共識機制**: 基於以上的模組，我們最終得到了第 6 節所描述的擴展網路共識框架。這個框架由兩個部分組成：首先，我們描述了 tip 選擇演算法的目前研究成果(第 6.1 節)；然後，為了主動解決某些衝突，我們描述了兩種不同投票機制，使得節點之間可以找出他們對於網路當前狀態的意見。

## 2 最新技術情況

在前言中，我們提到當前的 IOTA 的主網採用協調器（Coordinator）來達到共識，更通俗的來說，是為了保證網路的安全。然而，該中心化的協調器應僅僅被認作是一個必要的前導機制，而不是一個長期的解決方案。在這個章節中，我們首先討論經由 IRI (IOTA reference implementation）軟體實作 IOTA 目前的主網狀態，然後介紹當我們按照 IOTA 白皮書構建一個不仰賴協調者（Coordinator）的網路 [30]。由於在當前協調器與其里程碑已深植於 IRI，因此去除這些依賴，不僅僅意味著對軟體進行全面地更改，而且還會導致新的研究問題。

### 2.1 目前的 IOTA 實作

根據 IRI 軟體實作目前的 IOTA 主網，其中協調器（Coordinator）起到重要的作用。在下文中，我們介紹在當前主網中主要實作的任務，並不是所有的任務都與共識密切相關：

* **手動添加節點（Manual peering）**。為了加入 Tangle，需要一個節點連接到一些現有的節點（peering）。當前 IRI 軟體僅允許手動添加節點（peering），即節點需要手動尋找其他 Tangle 節點的地址。節點互連（peering）是傳播/廣播交易與同步當前帳本狀態的基礎。至於後者，里程碑是判定兩個節點的是否已經同步的有用錨點：如果一個節點的最新可靠裡程碑低於它的節點中的里程碑，那麼這個節點可能是落後了。

* **速率控制機制（Rate control mechanism）**。為了發布交易，節點必須解決加密難題（工作量證明機制）。必須保證該節點不會在在網路中任意地發送垃圾交易（spam），或者避免它們注入超過網路所能處理的交易。

* **Tip 選擇策略 (Tip selection strategy)**。驗證交易是建構 Tangle 的 DAG 結構的基本過程。要驗證交易，節點必須驗證以確保不會向帳本引入不一致性。儘管不可能強制對哪筆交易進行驗證，但 IOTA 的白皮書提出了一種以隨機走訪（ random walk）為基礎的 tip選擇演算法：
(i) 阻止懶惰行為，而鼓勵驗證新的 tip；
(ii) 持續將小分支合併為一個單一的大分支，從而提高確認速率;
(iii) 如果發生衝突，僅會保留其中一個分支，其他所有分支都會被拋棄。

* **共識 (Consensus)**。里程碑的主要作用是確定共識。 Tangle 運用一個簡單的規則：當且僅當一筆交易被里程碑所引用，則該交易得到確認。在 IRI 中，它體現在 getBalances 與 getInclusionStates 這兩個 API 中，它們分別顯示帳號有多少代幣以及交易是否被確認。

此外，我們還想強調里程碑用來優化 IRI 代碼：例如，不是從創世交易開始計算全帳本狀態，而是為每個里程碑都保存了一個中間狀態；類似地，里程碑用於進行本地快照，即 IRI 修剪機制，其允許節點避免儲存 Tangle 中較早期的資料。

### 2.2 不依賴協調器的 IOTA 網路

作為不依賴協調器網路的初步實施，我們正在構建 CLIRI，它代表了不依賴協調器的 IRI。它的核心是 IRI 的一個分支，刪除了所有與協調器相關的組件。 CLIRI 的主要目的是提供一個工作測試平台，運行第一個不依賴協調器的 IOTA 網路，在該平台上我們可以模擬各種 Coordicide 提案。這是理解不依賴協調器的主網必將面臨挑戰的必要第一步。

如上所討論，協調器在目前的 IOTA 實作中起到至關重要的作用。因此，構建 CLIRI 會帶來許多挑戰。對於它的第一次迭代，我們在可能的情況下，遵循最初的 IOTA 白皮書[30]，我們選擇啟發式演算法及簡化模型：

* **帳本確認**。由於重寫無里程碑帳本的計算邏輯是一個重要的事情，CLIRI 第一個迭代僅支持零值交易。

* **本地快照**。我們在 CLIRI 上取消了本地快照模組，並且我們在每週自動刪除整個資料庫。

* **隨機走訪起點（random walk starting point）**。 CLIRI 隨機選擇一個 tip，然後回溯到過去達到「足夠遠」的交易。

目前 CLIRI 處於早期的開發階段，在 2019 年 5 月 5 日推出了第一個測試網路。

### 2.3 新的研究挑戰

CLIRI 除了上述的「工程」選擇之外，它的邏輯是基於 IOTA 白皮書的，因此它具有相同的模型假設。其中最重要的是（勤勉的）誠實交易佔多數的條件[8]：具體來說，網路可行的話，白皮書上的共識演算法要求大多數交易總是來自誠實的網路參與者，即誠實的行為者需要擁有絕大多數的雜湊算力並持續產生交易。這意味著誠實的節點需要不斷地發送交易，無論實際上他們是否使用網路。此外，實作大多數雜湊是昂貴的，否則作惡代理人很容易去購買足夠的雜湊算力並超越網路。這裡存在一個激勵問題，此外發佈交易還受工作量證明機制（PoW）的限制。由於它的複雜性，慢速的節點將被排除在參與網路之外。

以上問題直接導致以下的研究問題，將在整篇文章中進行研究：

速率控制: 需要一個更有效的速率控制演算法來解決以下問題：如果PoW 的難度太高，那麼小型設備（例如電話或感應器）將會花費過長時間來計算它，因此這將無法發送交易。另一方面，低難度可能會導致網路擁堵，並/或進行垃圾交易攻擊。

共識: 在沒有協調器的支持下，在誠實交易是多數的假設中，我們需要一個可靠的共識機制。

在下個章節中，我們將介紹節點身份的概念，它是解決上述研究課題的先決條件。

## 3 節點責任

在沒有協調器的網路中，各種應用程序需要可靠地將交易或其他消息與發佈這些交易或消息的節點進行關聯。這些應用包括：

速率控制: 在超負荷的場景中，節點嘗試發佈超過整個網路能夠處理的交易，這時尤其應阻止或懲罰那些交易量貢獻最大的節點。

基於投票的共識機制: 為了防止雙重投票，需要將投票與節點權重相關聯，實際投票必須與節點 ID 進行關聯。

在 3.1 節中，我們提議一種將全域身份與節點相關聯的方法。由於這個可能將網路暴露於潛在的女巫攻擊，因此在 3.2 節中，我們引入了mana， 一種新型的防女巫攻擊機制。

### 3.1 全局節點身份

為了識別節點，有必要引入全域節點身份。為此，我們設想使用普通公鑰加密對確定的資料進行簽名，並通過防篡改的方式將其關聯到其發佈節點。此外，我們要求發布節點添加它的公鑰到每個簽名資訊中。這樣，節點無需某種形式的全球資料庫的 ID 和密鑰，就可以校驗發佈節點的真實性。重要的是要注意，實施這些機制僅僅用來保護通信層及密鑰，並且一旦節點開始處理，ID 和簽名不需要存儲在 Tangle 中。這允許了更好的靈活性，因為可以交換實際簽名方案，而對存儲的資料沒有任何的影響。與之相反的是，相對於存儲在 Tangle 中的任何資料，通信層現在無需使用後量子加密演算法，但是當量子攻擊在未來變得更加流行時可以更換它。

當節點與身份相關聯的話，分散式系統容易受到女巫攻擊[16]，其中惡意實體偽裝成多個偽造身份。這將克服依賴於有限數量的此類身份的任何機制，網路就易於受到協調攻擊。 在接下來的章節中將介紹解決這些問題的可行方法。

### 3.2 女巫攻擊保護

讓女巫攻擊變得更加困難的一種常見方法稱為資源測試，每個身份必須證明擁有某些難以獲取資源的所有權。因為在加密貨幣世界中，用戶擁有一定數量的某些代幣，我們提出基於這些代幣所有權的女巫保護機制。然而，無需要求自身所有權的證明，我們允許網路中的每個用戶發佈交易時，將代幣分配給他選擇的任何節點。我們稱這些代幣為 mana；它們既是難以獲得的資源，也是某種形式的“名譽”，它可以分配給值得信任的節點。實際機制的基本原理如下：

當發佈交易時，它會產生雙重流程：

（i）它將資料或代幣從一個地址發送到另外一個地址，
（ii）並給某些節點分配虛擬代幣（稱為 mana)。

Mana 的數量對應轉移的代幣數量。必須在交易的簽名部分指定應接收mana 的節點 ID。節點在一定的時間後得到 mana。有必要防止節點為它們發出的每條資訊產生新 ID。只要實際代幣再次轉移，從先前引用的節點扣除相應的 mana，並可能將其重新分配給新節點。
我們再次強調，該過程不會以任何形式影響到實際餘額，但它僅用來為“受信任”節點賦予更高的權重。

人們可以委託的 mana 數量取決於他們擁有的多少代幣，這意味著在該過程中，持有更多代幣的人有更大的影響力。特別的是，節點不需要在它們自己的網路中質押很多代幣的，它就能積累許多 mana。在傳統權益證明共識的女巫保護機制中，每個節點需要證明它有一定數量的抵押品。相反，委託 mana 帶來一些關鍵優勢：因為 mana 作為常規交易的一部分，節點不需要經常使用它們賬戶的私鑰進行簽名，而那就會帶來嚴重的安全風險；此外，該方法不需要激勵節點運營商擁有或申報大量代幣；最後，用戶可以向節點發放額外的 mana，以便為社群提供好的服務。

因為我們現在已經建立了可信的節點身份，我們可以使用這些身份發現和連接到網路中其他的節點。

## 4 節點自動互連

在 IOTA 中，一個節點是一個存有 Tangle 所有資訊的設備。為了讓網路更高效地工作，節點之間互相交換資訊並即時更新帳本狀態。目前，節點需要一個手動配對過程，使之和其它節點成為鄰居。然而，手動配對可能容易受到攻擊（比如社交工程學攻擊）從而改變網路的拓撲結構。為了阻止這些攻擊，簡化新節點的配置過程，我們引入了一個允許這些節點自動配對的機制。節點運營人員在選擇鄰居的整個過程中無需手動干涉，這種方法叫自動配對互連。

具體而言，在這個章節中我們提出的自動互連機制可實作兩個重要目標：第一，它為新創立的節點提供基礎設施，使其更容易加入網路；第二，我們能夠確保在互連過程中，攻擊者不能瞄準一些特定的節點，比如，我們能夠確保網路能對抗日蝕攻擊。

### 4.1 節點發現

每個節點從一個潛在的互連節點列表中選擇它的鄰居。在無許可開放式的環境中，這個列表會隨著時間變化，因為每時每刻都有節點加入或者離開網路。為了保持列表實時更新，我們假定節點會定期對已知節點列表中的一部分節點與其他節點保持聯絡。這個機制簡單高效，因為它允許每個節點去瞭解其它的網路參與者。有一點需要指出，這個機制僅需要節點與一個足夠大的網路子集相連接，比如潛在互連列表包括“足夠”的節點。潛在配對節點的數量取決於 Gossip 協議和全網系統參數，比如鄰居的數量。

### 4.2 鄰居節點選擇

節點自己選擇一半的鄰居，節點的另外一半鄰居是讓鄰居來選擇它們。因此這兩種不同的鄰居分別稱作：

- 主動選擇的鄰居。節點主動從它的列表中選出的鄰居。
- 被動接受的鄰居。鄰居選擇這個節點作為互連節點。

為了從潛在互連節點列表中選出主動選擇的鄰居，我們通過如下距離方程來測量兩個節點的距離d：

d(nodeId1, nodeId2, ϛ) = hash( nodeId1 + ϛ) + hash(nodeId2)，

其中ϛ是公共鹽5。

密碼學中，鹽被定義為可用於防禦字典攻擊，或抵抗它們等效的雜湊，即預編譯的彩虹表攻擊。

為了連接到新的鄰居，每個具有 ID ownId 和公共鹽的節點保存著根據距離 d 分類的一個潛在連接列表。隨後，節點按照這個列表的升序排序方式，發給潛在的互連節點配對請求，請求中含有節點自己的 ID，目前的公共鹽和節點的地址（比如，IP + 埠號）。在這之後，收到請求的節點能夠用如下的方式決定接受或者拒絕連接請求。需要配對的節點反覆重複這個過程直到它和足夠多的鄰居建立連接。這些鄰居建立它的主動選擇的鄰居列表。演算法1也對這個過程進行了闡述。


LaTex format:
$$
\begin{array} { l } { \mathcal { P } _ { \text {sorted } } \leftarrow \text { sortByDistanceAsc } ( \mathcal { P } , \text { ownId, } \zeta ) } \\ { \text { foreach } p \in \mathcal { P } _ { \text {sorted do } } } \\ { \text { peer Request } \leftarrow \text { sendPeerRequest (p) } } \\ { \text { if peer Request. accepted then } } \\ { \text { if } | \mathcal { C } | > k / 2 \text { then } } \\ { \text { else } } \\ { \text { append ( } \mathcal { P } \text { , peer Request.proposed Candidates) } } \\ { \text { Psorted } \leftarrow \text { sortByDistanceAsc ( } P , \text { ownId, } \zeta \text { ) } } \end{array}
$$

和之前的情況類似，為了接受鄰居，每個帶有 ID ownId 的節點必須生成一個私有鹽ϛ*，當它接收到來自一個帶有ID remoteId 節點的配對請求時，它測量d(ownId, remoteId, ϛ* ) ，僅接受滿足至少以下一個要求的請求：

連接的節點比目前已存在的被動鄰居節點更近。

連接的節點沒有足夠的鄰居。

當不滿足上述要求時，這個節點拒絕配對請求，同時它能夠使用公共鹽得到一個新的潛在節點，並加入到新的潛在互連列表中。演算法 2 用形式化語言描述了這個過程。


LaTex format:
$$
\begin{array} { l } { \text { If } | \mathcal { A } | < k / 2 \text { then } } \\ { \text { accept } ( r ) } \\ { \text { distance } \left. _ { r } \leftarrow \text { distance (ownId, r.nodeld, } \zeta ^ { * } \right) } \\ { \text { foreach } a \in \mathcal { A } \text { do } } \\ { \text { distance } _ { a } \leftarrow \text { distance (ownId, a.nodeld, } \zeta } \\ { \text { if distance, - distance, then } } \\ { \text { accept ( } r ) } \\ { \text { drop } ( a ) } \\ { \text { return } } \end{array}
$$

### 4.3 網路重組

我們設想通過公共和私有鹽幫助產生不對稱的網路視角來阻止攻擊者破壞系統。事實上，瞄準一個節點的唯一方式是在自動互連過程中是通過暴力破解不同的節點身份和期望獲得比已有鄰居更近的距離（距離 d）。為了阻止暴力破解成功，我們讓鹽僅在特定時間範圍內有效，在這之後節點更新主動選擇的鄰居和被動接受的鄰居。

另外一個降低攻擊者控制網路拓撲能力的方法是，在產生鹽時加入一個“全局隨機源”。

這種頻繁的重組帶來雙重好處：首先，它可以防止攻擊者影響網路拓撲;第二，它傾向於想要加入網路的新節點，因為他們的互連請求將被更大的機率接受。

### 4.4 節點初始化

一個想加入網路的新節點最初對網路是一無所知的。它既不知道帳本的狀態，也不知道目前誰在網路中。為了讓所有新的節點獲取第一份含有“其他節點”的列表，我們使用一種可信的“入口節點”硬編碼列表，這個列表由 IOTA 基金會或者可信的社群成員運行，從而能夠響應新加入節點的互連請求。

這是常見的做法，幾乎在所有分散式網路中都以這種方式來處理。

## 5 速率控制

每個通信網路的基本目標是要通過限制加入網路的交易速率來控制其節點注入的流量。事實上，由於惡意行為者的原因，這種流量可能會導致不愉快的情況，例如由於資源限制導致的網路阻塞或垃圾資訊：

- 阻塞控制: 在大多數網路中，傳入的流量負載在有些情況下大於網路可以處理的能力。如果不限制流量的湧入，就會造成網路瓶頸，從而降低整個網路的速度。可以對分散式帳本進行相關分析，其中輸入的流量（即由網路中節點發布的交易）可以濫用諸如頻寬、計算能力或磁碟空間等有限資源。此外，節點可能會失去彼此之間的同步，有時甚至不會意識到這一點。

- 垃圾資訊檢測: Gossip 協定（目前用於在 IOTA 網路中進行交易轉發）是一種有效且可靠的傳播資訊的方式。然而，這些協定有一個缺點：它們無法限制垃圾資訊的傳播。實際上，消息在網路中冗餘地分佈，並且一小撮節點轉發垃圾消息，以致使大多數節點都接收到這些垃圾資訊。

通信網路的速率控制策略在阻塞控制[24]和垃圾資訊檢測[17]領域都有較為充分的研究。對於分散式帳本技術，PoW 是一種內置的速率控制機制，而不僅僅用於達成共識。然而，PoW 會帶來不良的副作用，例如挖礦競賽：較小的通用設備與優化的硬體之間，在 PoW 效能方面存在幾個數量級的差異。因此，任何基於 PoW 的速率控制最終都會使得算力較小的設備處於劣勢。因此，需要全新的交易速率控制機制來處理Tangle 網路的全局和每個節點的控制。

### 5.1 速率控制算法

在純粹基於 PoW 的體系中，高難度值會阻礙低算力節點發布交易，這不是令人滿意的，尤其是在物聯網環境中更不適合; 另一方面，低難度值就會很快導致網路阻塞。我們提出了一種自適應 PoW 演算法，允許每個節點發布交易，同時懲罰垃圾資訊攻擊行為。

在我們的演算法中，當一個節點決定發布一筆交易時，它必須解決一個加密難題，其中難度是所擁有的 mana 和最近發布的交易數量的函數。假設節點 i 在之前的 T»h 個時間單位時生成了 niT 筆交易，其中 h 是網路延遲時間，這意味著，如果在時間 t 時發送消息，則所有在線節點將在時間 t + h 內接收到相同的消息。節點 i 的 PoW 的難度設置為 di，其定義為：

di = d 0 + w(si, niT)，

其中 d0 是基本難度，w 是 mana 值 si 和交易數量 niT 的函數。我們基於所期望的全網均衡水平，來設置時間窗口 T，基本難度 d0以及函數 w 等參數。

作為一項額外的安全措施，我們要求用戶發出的交易總數限制為

niT ≤ z(si)，∀i， （1）

其中 z：R +→R + 是一個依賴於 mana 值 si 的函數，這樣使得節點的 mana 值 si 越大，同一節點可以發出的交易數量越多。方程（1）確保即使具有無限計算能力的用戶也不能隨意通過垃圾資訊進行網路攻擊。

### 5.2 實施細節

為簡單起見，我們假設傳入交易的順序與節點發出的順序相同。由於執行 PoW 所需的預期時間通常遠大於網路延遲時間 h，因此這是一個合理的假設。

當第一次看到交易時，節點存儲發出交易的節點 id，接收它的時間 t0 和 PoW 難度。可以使用第 3 節中描述的方法來確定發布節點的身份標識 id 以及 mana 的 sid。基於此資訊，可以檢查由同一節點在最近的 T 個時間單位內發布的交易數量不超過根據其 mana 數量所得到的最大數量 z(sid),並且最近這些交易的難度值確實足夠大。這些想法在演算法 3 中有更正式地描述。

### 5.3 可驗證的延遲函數

雖然本節中描述的自適應速率控制演算法解決了 PoW 的一些缺點，但我們相信，當前分散式帳本生態系統對更高效演算法的需求是顯而易見的。在下文中，我們提出了一種可持續性更好的機制，可代替 PoW 演算法：可驗證的延遲函數（VDFs）。

通俗地來說，VDFs 是特殊的函數：

(i)即使假定能夠擁有無限並行資源（即使用無限數量的CPU）[6]，也難以預測計算，

(ii)易於驗證: 大量研究人員根據特定的數論函數提出了不同的VDF（例如模態指數[17,27]，橢圓曲線上的超奇異同構[15]，橢圓曲線上的配對，有限域擴張之間的內射有理圖[5]）。與 PoW 相比，這些函數具有以下優勢：

- VDF可以被認為更環保，因為它們可以避免挖礦競爭。
- 由於它們不可並行化，因此無法有效地使用專用硬體（例如ASIC）從而解決了高算力節點和低算力節點之間的不公平問題。

抵抗並行化的條件使得對這些函數的追求成為一個有趣且非常重要的問題。從函數實作的角度來看，主要問題是函數計算求解（預測計算）所需時間與驗證其正確性（驗證）所需時間之間的比率。表 1 提供了不同VDF關於此效能指標比較的良好見解。

表1：不同VDFs的計算與驗證時間比率

> 關於可驗證延遲函數的第一個想法可以追溯到 Dwork 和 Naor 在抵抗垃圾資訊領域的開創性論文[17]，但只有在 Boneh 等人的論文[5]之後，對 VDF 的開發和實作的興趣才大大增加。實際上 VDF 已經成為某些 DLT 設計中的基本要素（例如，Chia Network7）。此外文獻[5]顯示了去中心化隨機性的潛在應用。我們相信 VDF 可以在替換基於 PoW 演算法方面提供很大幫助，因為它們能夠限制具有強大雜湊運算能力的節點的計算能力。

## 6 共識

由於網路中交易的傳播有延遲，在同一時刻每個節點未必擁有相同的視野。這可能使得在驗證的時候，會有多個互相有衝突的交易加入到Tangle 中。 IOTA 白皮書的一個基本假設是，Tangle 本身確實可以包含有衝突的交易。然而，在發生衝突時，節點需要決定哪些交易最終應被視為有效，即，他們需要就那些衝突的交易達成共識。

IOTA 白皮書中，僅通過使用 tip 選擇演算法（TSA）來達成目的。即,誠實節點目前基本上用隨機走訪 (random walk) 的方法來選擇有效交易 。如果交易有衝突，基本上會留下一個分支。但是正如本文中已經說明的那樣，該方法只有在誠實交易占多數的假設下有效。此外，這個解決衝突的辦法速度緩慢，這會導致選擇“錯誤”分支的交易，從而需要進行重新添加（ reattachments )。

在本文中，我們提出了一種新的共識機制，它含有著一個投票機制，有助於處理上述問題。雖然投票模型有其局限性，但它們已成功廣泛用於工程和經濟應用之中[2,26,33]，並導致了新興的社會物理科學產生[10]。為了便於說明，我們將共識分為兩個主要組成部分（另請參見圖2）：

- tip 選擇演算法: 在 6.1 節中，我們對 IOTA 白皮書中提出的基於隨機走訪(random walk)的演算法進行了一些重要的改進，目的是提高整體吞吐量以及對寄生鏈和分裂攻擊的防範。
- 投票機制: 在 6.2 節中，我們描述了兩種投票機制，其中節點相互通信，以便在有衝突交易時 Tangle 決定接受哪些交易。

圖2：我們的創新共識機制增加了一個投票層，以提高安全性和多數誠實節點之假設的缺陷。

### 6.1 Tip 選擇

Tangle 是根據以下規則構建而成的資料結構：

為了加入 Tangle，每筆交易必須驗證已有的兩筆交易。
交易的驗證是驗證一個地址是否擁有代幣的過程 8。如果交易 y 驗證了交易 x，我們說 y 直接驗證 x。相反，如果交易 x 和 y 之間沒有直接的驗證關係，但它們之間存在有向的驗證路徑，那麼我們說 y 間接地驗證 x。8) IOTA 中的實際驗證過程更加複雜，我們邀請感興趣的讀者可以連上 https://docs.iota.org 網站以獲取更多資訊。

IOTA 白皮書最初僅使用基於偏隨機走訪的 Tip 選擇算法（TSA）來確定要驗證的 tip 交易。這種 TSA 具有雙重好處：首先，它可以有效地對抗自私節點進行簡單的選擇（例如，純隨機選擇或選擇創世交易），從而避免自私節點進行這些簡單的 tip 選擇;第二，它使Tangle 對惡意節點執行例如寄生鏈攻擊更具抵抗力（見圖3）。但是，白皮書中的方法如第2節所述也有其自身的局限性;特別是多數交易為誠實交易這一假設是演算法安全性的必要條件。

圖3：寄生鏈攻擊的一個例子：交易 x 花費了攻擊者想要在交易 y 中再次花費的資金，然後顯式包含了交易 x 的子網路。為清楚起見，灰色區域包含許多沒有顯式表示出來的交易。粗藍線對應於典型的隨機走訪軌跡。

在本節的其餘部分，我們概述了 TSA 的研究現狀：具體而言，在6.1.1 節中，我們介紹了一種基於隨機走訪的 TSA，旨在改進原始白皮書中的演算法;然後，在 6.1.2 節中，我們研究了一種替代方法，其中使用兩種不同的演算法來選擇要驗證的兩個 tips 中的每一個。

值得重點強調的是，由於 TSA 沒有（並且不能）強制實施，特定 TSA的選擇最終取決於節點的所有者。因此，任何參與者將以合理的方式選擇他們自己的 TSA，如[31]中所述。由於這種內在的選擇自由，並且因為所有可能的 TSA 的「空間」是巨大的，所以可供選擇的合理演算法是至關重要的。我們絕對沒有義務滿足特定版本的 TSA; 相反，我們的願景是，與人類社會本身類似，系統將持續發展。因此，雖然現有的基於隨機走訪的 TSA 已經做得很好，但我們將在下面描述幾種有用的方法和研究方向，希望能夠邀請學術界提供更多有價值的資訊。

#### 6.1.1 基於隨機走訪的TSA

白皮書中的 TSA 是一個基於偏隨機走訪的算法，從創世交易開始，走向 tips。一旦行走到達前沿 tips，該 tip 被選為第一筆直接驗證的交易。然後進行第二次行走以選擇第二筆直接驗證交易。為了防止選擇驗證舊交易的“懶惰” tips 的隨機走訪，從交易 x 到交易 y 的轉移概率是有概率取向的，並且正比例於：

P[x->y] ~ exp( alpha * wy) (2)

其中 α> 0 是權重參數，wy 是累積權重 9，即直接或間接驗證 y 的交易數量。為了獲得實際概率，可以簡單地將方程（2）進行歸一化。由於每個節點看到的是一組不同的 tips，因此不可能強加特定的 TSA。

9）白皮書中對累積權重的定義略微更為一般化，並且還考慮了發布交易所需要的工作量。

在本節中，我們提供另一種基於隨機走訪的演算法，以提高演算法效能和安全性。正如前文已經指出的那樣，雖然 TSA 無法強制實施，但我們期望節點跟隨可用的「最佳」演算法。主要思想是引入 Tangle 的本地（即每節點）視圖，使得一些交易是基於節點本地可用的各種資訊而優選的。例如，固化時間 10 可用於降低寄生鏈攻擊的有效性：由於攻擊者需要一些時間來構建一個 subtangle，一個誠實的節點可能會決定懲罰一筆出現得比應該出現時間要晚的交易。這種局部視圖通常稱為局部修飾符[29]。

10）交易 x 的固化時間不僅包括交易本身，而且還包括給定節點接收交易x所引用的所有交易的時間。

一般來說，局部修飾符可實作多種特徵：它們可以增強 Tangle 的安全性，特別是對抗寄生鏈和分裂攻擊;它們減少了對 PoW 和累積權重計算的依賴;它們使網路能夠在暫時失去誠實交易的情況下生存下來。

設 tx（相應的 ty）是給定節點處交易 x（相應的交易 y）的固化時間。根據以上討論，從交易 x 到交易 y 的轉移概率正比例於：

其中β> 0 是權重參數，D 是時間差截止參數。如果 ty-tx≥D，則轉移概率變為 0，即從隨機走訪和累積權重計算中排除相應的引用邊。基本上，我們可以設想一種系統，其中 TSA 在現有交易的子集上執行，具體取決於節點的本地視圖。這個想法將在 6.2 節中進行擴展。

了解固化時間的引入是如何增加 Tangle 對抗寄生鏈和分裂攻擊的穩健性是極為有意思的。為了執行寄生鏈攻擊，惡意行為者在包含資金的原始交易已被接受之後，附加隱藏的 subtangle（批准雙重支付交易），並試圖使其增長。分裂攻擊則是這樣的一種情況，惡意節點代理將 Tangle 分裂成兩部分：當其中一個分支增長時，惡意節點同時也在另一個分支上發布交易以保持兩者都存活。分裂攻擊的目的是進行雙重支付並破壞網路。這兩類攻擊情況的共同點都是把那些交易隱藏了一段時間。從節點的角度來看，這種情況看起來像是新的交易驗證舊的交易。但通過交易的固化時間可以發現這種非典型異常的時間差異，並且這些攻擊可以有效地降低 TSA 選擇此類交易的概率。除上述情況之外，任何通過隱藏交易攻擊，或延長交易固化時間到超長時間，都可以通過使用局部修飾符來增強其穩健性。

同樣重要的是要提到方程（3）可以容易地進行擴展，以便模擬了解節點已知的任何本地資訊，例如發布節點信譽。作為這種擴展的另一個自然案例，考慮兩筆交 易x，y，其中 y 驗證 x。現在我們定義兄弟數s（y，x）∈N：如果交易 y0 ,.。 。 ，yk 是直接驗證交易 x，並且節點以此順序連續看到它們，然後我們定義 s（yi，u）= i。下面我們考慮對方程（3）進行如下修改：

其中γ∈（0,1）是一個重要參數，兄弟數。方程（4）中，當前位於u的行走者因此將更偏好對應節點之前看到的那些“後繼者”。為了解釋為什麼採用這種規則是合理的，請首先註意，平均而言每筆交易將（直接）被兩筆交易驗證，因此過多的直接驗證可被視為是可疑的。這確實是一個惡意行動者的策略，旨在“過濾”一筆正常交易（即阻止它被 TSA選中）：通過發布許多交易並將它們附加到同一筆交易，攻擊者希望TSA 通常會選擇“他發布的”那些交易之一，而不是被他攻擊的那筆良性交易。現在觀察上述修改，確實可以有效地防止這種行為的發展。

#### 6.1.2 替代 TSA

隨機走訪的 TSA 的隨意性使得併非所有交易最終都將被驗證的可能性存在。一般來說，這可以被視為一個特徵，因為這樣系統中有些交易被“留下”來了，並對 Tangle 具有潛在的損害。但是，如果合法交易未在一定延遲內得到驗證，則可以假設它不再會被驗證，因此這筆交易應該重新附加到較新的 tips。由於較低的確認率，這會給系統引入額外開銷，所以我們也在探索一種新的演算法，旨在確保所有交易在有限時間內得到驗證[21]。

關鍵的直覺是白皮書 TSA 中的高α值（參見前面的小節）有利於從創世交易到 tips 具有更長路徑，因此選擇較舊的 tips 的概率隨著時間增加會減少。相比之下，較小的 α 值允許選擇較舊的 tips，但它們使得 Tangle 容易受到雙重支付攻擊。這裡所提出的方法旨在通過使用兩種不同的演算法來選擇每個 tip 來組合兩種情景（大和小α值）的最佳屬性：通過使用具有高 α 值的白皮書演算法來選擇第一個tip ,從而確保優先選擇誠實的 tip 並保證安全;至於第二個 tip，我們使用隨機選擇來確保不會有任何 tips 被第一個 tip 所留下。

某些方向仍需要進行更仔細的研究。例如，無法阻止一個節點只進行tips 的隨機選擇，從而減少節點自己的驗證開銷。在這種情況下，可能需要額外的措施來防止這種懶惰行為。例如，一種可能的措施可以使用第 3 節中講到的節點責任特徵：網路的參與者可能以某種方式懲罰發布驗證那些“不應該驗證的內容”的交易的節點。

### 6.2 投票表決機制

在本節中，我們將討論一種投票機制，這個附加層能夠確保在被攻擊的情況下共識的安全性。其做法是節點向其他節點查詢他們當前帳本的內容，根據他們得到的其他節點意見之比然後調整自己，在經過幾輪之後，決定自己帳本的內容。在本節中，我們僅考慮對單個衝突取得共識的演算法，其結果是將—個交易標記為“喜歡”或“不喜歡”。

基本思路是讓節點相互通信，以便主動解決衝突。當有衝突時，從分散式帳本的初始狀態開始執如下：考慮一個交易 v，如果在給定的時間內節點沒有看到有其他交易從同一地址花費，我們說該節點喜歡交易 v; 否則，節點不喜歡交易 v(11)。並且，必須考慮 tip 是怎樣挑選的。最直接地的方法是，簡單地刪除不喜歡的交易，並且排除這個交易之後錐體形中的所有交易。

之後，我們會定期對 Tangle 中的每個交易應用一種投票方案，每個節點都會詢問一些鄰居的狀態。在投票後，一個交易要么被節點所喜歡，要么被一個節點肯定不喜歡，直到這種狀態不會改變。我們希望保持單調性，如果一個節點喜歡交易 u，那麼它就喜歡交易 u 贊同的任何交易，如果節點不喜歡交易 v 那麼它不喜歡贊同交易 v 的任何交易，參見圖 4。實作這一點，我們可以放心地假設我們只喜歡交易 v 當我們喜歡它的所有前錐體形，如果我們不喜歡 v 那麼我們不喜歡它的所有後錐體。

在以下兩個小節中，我們將描述我們正在考慮的兩種投票機制。第一個稱為“快速大概率共識”，它已通過嚴格的數學證明;但是，這個解決方案需要節點接受來自不是鄰居節點之連接，並使用非中心化的隨機數，這就需要另一個附加層。另一方面，第 6.2.2 節的”元胞自動機共識“方法沒有那麼多的要求，且快過第一種模式。然而，這種方案缺乏嚴格的證明，也需要更嚴格的自動互相窺視，以避免月蝕攻擊，不然就可能被孤立成可疑節點。這兩種解決方案可以被認為是相互不排斥的投票機制的實作，它們可以組合使用，以建立一個堅固的框架。

11 重要的是要注意，此規則不包括重新附加：如果 v1; ::: ;; vk都是同一交易的重新附加，我們要麼全部喜歡要麼全部不喜歡

#### 6.2.1 快速概率共識

論文[32]引入了一種通信複雜度低的協議，它允許一組節點通過(可以是隨機的)投票的手段對一位變量的值達成共識。 （參見文獻例如[3,13,14,18,19,25]及其中有關該主題的大量文獻; 我們也提到了關於（概率）拜占庭共識協議的經典工作，參見文獻例如[1,4,7 ,11,20,22,34]， 但通信複雜度要大得多）。文獻[32]中描述的機制的特點是允許更多數量的可疑（或拜占庭）節點，其數量可以佔節點總數的（固定）比例。那些可疑節點意圖是要麼推遲達成共識，要么打破共識（即至少讓一些誠實節點得出不同的結論）。儘管如此，該協議在適當選擇其參數時，它的成功的概率很大。在給定概率下明確估算產生共識的時間，參見定理2.1和2.4。

與這一領域的經典作法不同，它並不要求在—開始時，實作共識的概率就要高。相反：

- 如果最初時，沒有絕大部分的節點（12）更喜歡 1，那麼最終 0 值是共識的大概率;
- 如果，最初，絕對多數的節點(13)更喜歡 1，那麼最終 1 值的共識將具有大概率。

為解釋為什麼這與加密貨幣之使用有關，請考慮存在兩個相互矛盾的交易的情況; 例如，其中一個將地址 A1 的所有餘額轉移到地址 A2，而另一個交易將地址 A1 的所有餘額轉移到地址 A3 ！= A2。如果兩筆交易在網路中存在衝突，那麼安全的做法是聲明兩者都是無效的。另一方面，總是聲明它們無效的想法，不是一件好事。實際上，如果我們這樣做，那麼惡意行為者將能夠通過下列方式利用它：首先，他發布了合法的交易，例如，從商家購買一些商品。當他收到貨物時，他發布瞭如上所述的雙重支付交易，希望兩者都被系統取消，所以他會有效地收回他的退款（或者至少從商家那裡取回錢）。為了避免這種情況，如果，第一筆交易（付款給供營商是可以信任的）的那個時候，節點可能已經獲得了一些信任，所以保持這筆交易，那麼，隨後的雙重支付就可以被取消了。

[32]協議的一個特殊之處在於它利用了一系列隨機數，這些隨機數由可信來源提供或生成。節點本身使用一些分散的隨機數生成協議，參見例如[9,28,35,36]。重要的是要注意，即使可疑對手有時設法（全部或部分）控制了隨機數，這只能導致延遲達成共識，但他無法使不同誠實節點接收不同的結果，即，不違反安全性。而且，不必所有的誠實的節點，同意相同的數字;如果它們中的大多數都同意，這已經足夠達成共識（也就是說，生成的隨機數不需要任何特別類型的 “強烈共識“）。我們沒有在這裡描述所協議的所有細節，感興趣的讀者可閱讀[32]。

---

12 廣泛來說，一個顯著多數是指統計上超過 50/50 的情況; 例如，1-opinion 的比例大於某些 > 1/2 的比例。
13 這是一個鬆散的概念;絕對多數是已經接近共識的東西例如，超過90％ 的所有節點具有相同的意見。

#### 6.2.2 元胞自動機共識

本文討論的第二種實施是元胞自動機共識（CA）。 CA 方法最初是作為Ising 模型而開發的[23]。其他共識演算法相比，與其它共識比，CA 的最大優勢之一是它能實作非常高程度的並行化。僅這一優勢就能驅動更深入的研究。 CA 帶來了以下新穎的關鍵屬性

- 每個節點都充當一個元胞演變機制[12]，在存在衝突的情況下，僅根據其直接鄰居的狀態改變其觀點，並始終採用多數意見。
- 在一輪的運行期間，節點的鄰居集合不會改變。在這種情況下，第 4節中提到的重組只能在不同輪的運行中發生，即不一樣的衝突中。
- 在評估鄰居的意見時，節點將鄰居的鄰居意見著為“證據”。這將允許節點監視彼此的行為並防止節點獨立於其鄰居。
- 行為異常的鄰居，即持有與證據不一致的鄰居，將立即被除掉。這個資訊還傳播到網路，以便其他節點驗證並將該節點標記為惡意節點並防止將來的連接嘗試。

在每輪開始時，每個節點發送一個當前狀態的心跳。這包括其簽了名的自己的當前狀態，以及上一輪中每個鄰居的當時的狀態，每個狀態均由發布節點各自簽名。這使鄰居們的以前狀態不可能被偽造，每個節點都會接收到這個心跳，可以驗證當前的狀態是否正確，並遵循共識機制的規則。

我們將在下一小節中描述的共識協議中標準化上述想法。

Algorithm 4: 發送脈衝

LaTex format:
$$
\begin{array} { l } { \text { Function heartbeat (Node i, Round m): } } \\ { \text { foreach neighbor } j \in N _ { i } \text { do } } \\ { \qquad \begin{array} { l } { \text { send opinion } X _ { m } ( i ) \text { to neighbor } j } \\ { \text { foreach } j \in N _ { i } \backslash \{ j \} \text { do } } \\ { \text { L send opinion } X _ { m - 1 } \left( j ^ { \prime } \right) \text { to neighbor } j } \end{array} } \end{array}
$$

模型 假設存在一個由 n 個節點組成的網路，並且這些節點需要對一個一位二進制數的值達成共識。為清楚起見，我們在下文中假設每個節點通過第 4 節中描述的自動配對機制直接連接到 k 個鄰居。節點 i 的鄰居集由 Ni 表示。自動配對機制是這種方法安全性的關鍵因素：實際上，惡意節點不應該被選擇，也不能影響他的鄰居。

在演算法的每個階段期間，每個節點對這個二進制的一位數的的值保持意見。意見可以是 0,1 或空，具體取決於節點是選 0,1，還是空（即不是 0，不是 1）。第 m 輪中,節點 i 的觀點由 Xm（i）∈{0,1,空} 來表達。我們進一步假設，每個節點i具有初始意見 X0（i）∈{0,1} 中。

該協議取決於以下參數:
- k 屬於 N，每個節點的（初始）鄰居的數量。
- M 屬於 N，最大輪數
- l 屬於 N ，最終一至意見的脈衝次數。
- p：{0,….,k} -> R>=0 單調遞增權重函數，即將鄰居數量映射到權重。這樣可懲罰鄰居數少於 k 的鄰居的節點。

演算法5: 元胞自動機共識

LaTex format:
\begin{array}{l}{\text { foreach node i do }} \\ {\text { Send initial opinion } X_{0}(i) \text { to neighbors } N_{i}}{\text { for } m \leftarrow 1 \text { to } M \text { do }} \\ {\text { foreach node } i \text { do }} \\ {\text { foreach neighbor } j \in N_{i} \text { do }} \\ {\text { if } X_{m-1}(j) \text { is inconsistent wrt } X_{m^{\prime}}\left(j^{\prime}\right) \text { for }} \\ {\text { if node if } \mathbb{N}_{i} \backslash\{j\}} \\ {\text { if } \sum_{\left\{j \in N_{i} | X_{m-1}(j)=0\right\}} p\left(\left|N_{j}\right|\right)>\frac{\text { total then }}{2} \text { then }} \\ {\text { else if } \sum_{\left\{j \in N_{i} | X_{m-1}(j)=1\right\}} p\left(\left|N_{j}\right|\right)>\frac{\text {total}}{2} \text { then }} \\ {\text { else }}{ X_{m}(i) \leftarrow 1} \\ {L X_{m}(i) \leftarrow \perp}{\text { heartbeat }(i, m)} \\ {\text { if opinion } X(i) \text { did not change in the last } \ell \text { rounds then }} \\ {\text { L mark node } i \text { finalized }}\end{array}

演算法 每個節點 i 知道其鄰居 j ∈ Ni 的意見以及他們鄰居的鄰居 Nj 的意見。這通過廣播步驟來確保所有意見都以這樣的方式簽名，即意見始發節點以及廣播節點是沒法偽造的。這已在演算法 4 中表現出來。

CA (元胞自動機共識) 是這樣一種共識機制，其中每個節點都使用其鄰居的意見來更新自己的狀態。當大多數鄰居支持 0 或 1 時，節點採用該意見。如果不存在被大多數鄰居支持的意見，則採用”空”，即沒有。如果集合 Ni 至少對於 i 所有的鄰居都是已知的，任何節點都可以使用這些簡單規則來驗證所報告的鄰居 i 的意見與 Ni 中所有節點的意見是否一致。在演算法 5 中更形像地解釋了元胞自動機共識機制，並且在圖 5中可以找到示例場景的 CA 過程。


圖5：CA 共識過程的形象化：每個方塊對應於連接到隨機鄰居的節點。最初，兩個互相衝突的交易在網路上傳播。然後，節點在最終達成共識之前不停地調整他們的意見（0：紅色，1：青色，空：黑色）。

a) 意見“碰撞” (第一個節點更新意見)
b) 意見競爭(節點更新他們的意見)
c) 意見競爭(節點更新他們的意見)
d) 唯一一個意見”倖存”下來(網路達成共識)

## 7 結論

在本文中，我們概述了 Coordicide 專案的實作方法。其中，我們重點圍繞著共識機制，安全性和防禦攻擊，垃圾郵件管控和自動選擇對等節點等方面闡述了我們的想法；所有這些都為實作 Coordicide 項目提供了重要的基礎。儘管我們已經明確定義實作 Coordicide 的步驟，但我們仍然在評估各種選項和設定，以便在整體框架中實施和部署這些組件。

## 參考資料

[1] Marcos K. Aguilera and Sam Toueg. The Correctness Proof of Ben-Or's
Randomized Consensus Algorithm. Distributed Computing, pages 371–381,
2012.
[2] Sven Banisch, Tanya Ara´ujo, and Jorge Lou¸c ˜a. Opinion dynamics and
communication networks. Advances in Complex Systems, pages 95–111,
2010.
[3] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale,
and Luca Trevisan. Stabilizing Consensus with Many Opinions. In Symposium on Discrete algorithms, pages 620–635. SIAM, 2016.
[4] Michael Ben-Or. Another Advantage of Free Choice (Extended Abstract):
Completely Asynchronous Agreement Protocols. In ACM Symposium on
Principles of Distributed Computing, pages 27–30, 1983.
[5] Dan Boneh, Joseph Bonneau, Benedikt B¨unz, and Ben Fisch. Verifiable
Delay Functions. In Annual International Cryptology Conference, pages
757–788. Springer, 2018.
[6] Allan Borodin and Ian Munro. The Computational Complexity of Algebraic
and Numeric Problems. North-Holland, 1975.
[7] Gabriel Bracha. Asynchronous Byzantine Agreement Protocols. Information and Computation, pages 130 – 143, 1987.
[8] Quentin Bramas. The Stability and the Security of the Tangle. Preprint,
2018.
[9] Ignacio Cascudo and Bernardo David. SCRAPE: Scalable Randomness
Attested by Public Entities. In International Conference on Applied Cryptography and Network Security, pages 537–556. Springer, 2017.
[10] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical
physics of social dynamics. Reviews of Modern Physics, page 591, 2009.
[11] Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance
and Proactive Recovery. ACM Transactions on Computer Systems, pages
398–461, 2002.
[12] Edgar F. Codd. Cellular Automata. Academic Press , 1968.
[13] Colin Cooper, Robert Els¨asser, and Tomasz Radzik. The Power of Two
Choices in Distributed Voting. In International Colloquium on Automata,
Languages, and Programming, pages 435–446. Springer, 2014.
[14] Colin Cooper, Rob ert Els¨asser, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast Consensus for Voting on General Expander Graphs.
In International Symposium on Distributed Computing, pages 248–262.
Springer, 2015.
28
[15] Luca De Feo, Simon Masson , Christophe Petit, and Antonio Sanso. Verifiable Delay Functions from Supersingular Isogenies and Pairings. Cryptology ePrint Archive, Report 2019/166, 2019., 2019.
[16] John R. Douceur. The Sybil Attack. In International Workshop on Peerto-peer Systems, pages 251–260. Springer, 2002.
[17] Cynthia Dwork and Moni Naor. Pricing via Processing or Combatting Junk
Mail. In Advances in Cryptology, pages 139–147, 1993.
[18] Robert Els¨asser, Tom Friedetzky , Dominik Kaaser, Frederik MallmannTrenn, and Horst Trinker. Rapid Asynchronous Plurality Consensus. arXiv
preprint arXiv:1602.04667, 2016.
[19] Giulia Fanti, Nina Holden, Yuval Peres, and Gireeja Ranade. Communication Cost of Consensus for Nodes with Limited Memory. arXiv preprint
arXiv:1901.01665 , 2019.
[20] Paul Feldman and Silvio Micali. An Optimal Probabilistic Algorithm for
Synchronous Byzantine Agreement. In Automata, Languages and Programming, pages 341–378. Springer, 1989.
[21] Pietro Ferraro, Christopher K. King, and Robert Shorten. IOTA-Based Directed Acyclic Graphs without Orphans. arXiv preprint arXiv:1901.07302,
2019.
[22] Roy Friedman, Achour Most´efaoui, and Michel Raynal. Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems. IEEE International Symposium on Reliable Distributed Systems,
pages 228–237, 2004.
[23] Ernst Ising. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift f¨ur
Physik A Hadrons and Nuclei, pages 253–258, 1925.
[24] Frank P. Kelly, Akhil K. Maulloo, and David KH Tan. Rate Control
for Communication Networks: Shadow Prices, Proportional Fairness and
Stability. Journal of the Operational Research Society, pages 237–252, 1998.
[25] Frederik Mallmann-Trenn. Probabilistic Analysis of Distributed Process es
with Focus on Consensus. PhD thesis, PSL Research University, 2017.
[26] Hong-Li Niu and Jun Wang. Entropy and recurrence measures of a financial
dynamic system by an interacting voter system. Entropy, pages 2590–2605,
2015.
[27] Krzysztof Pietrzak. Simple Verifiable Delay Functions. In Innovations
in Theoretical Computer Science Conference. Schloss Dagstuhl-LeibnizZentrum fuer Informatik, 2018.
[28] Serguei Popov. On a Decentralized Trustless Pseudo-Random Number Generation Algorithm. Journal of Mathematical Cryptology, pages 37–43, 2017.
29
[29] Serguei Popov. Local Modifiers in the Tangle. 2018.
[30] Serguei Popov. The Tangle, 2018.
[31] Serguei Popov. IOTA: Feeless and Free. IEEE Blockchain Technical Briefs,
2019.
[32] Serguei Popov. On Fast Probabilistic Consensus in the Byzantine Setting.
Preprint, 2019.
[33] Piotr Przyby la, Katarzyna Sznajd-Weron, and Maciej Tabiszewski. Exit
probability in a one-dimensional nonlinear q-voter model. Phys. Rev. E,
2011.
[34] Michael O. Ra bin. Randomized Byzantine Generals. In Annual Symposium
on Foundations of Computer Science, pages 403–409. IEEE, 1983.
[35] Philipp Schindler, Nicholas Stifter, Aljosha Judmayer, and Edgar Weippl.
HydRand: Practical Continuous Distributed Randomness. Cryptology
ePrint Archive , Report 2018/319, 2018.
[36] Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris Kogias, Nicolas Gailly,
Linus Gasser, Ismail Khoffi, Michael J. Fischer, and Bryan Ford. Scalable
Bias-Resistant Distributed Randomness. In IEEE Symposium on Security
and Privacy, pages 444–460, 2017.

###### tags: `coordecide` `iota`