IOTA Consensus Algorithm Introduction
===

:::danger
以下內容是 proof.K 根據官方資料和推理而得，只討論最簡單的情況，而且時有變更，請留意
:::

# 交易

[一筆交易](https://thetangle.org/transaction/LDBHUZJJDDZJQTIDVCJOIHYXGIGSJLMQCRCKTQBCTGIJGBMUUVBQDJMWQGT9DULGEFHHCPDHHK9M99999)

列出跟本次簡介有關的欄位

## Address

可以看成是銀行或郵局的帳號

## Value

正代表 Address 錢增加

負代表 Address 錢減少

## Trunk

交易會組成 DAG

Trunk 代表交易其中一個有向邊

## Branch

同 Trunk 的解釋 , 代表交易另一個有向邊

# Trunk 與 Branch

決定 Trunk 與 Branch 的算法稱為 tip selection

一筆交易 Trunk 與 Branch 所指向的交易

從帳本的角度看 , 必須有下列性質:

1. 所有被指向的交易 , 全部的 address , 餘額不是負的

2. 所有被指向的交易 , 全部的 address , 餘額加起來是最初的發行量

這邊需要詳細解釋

假設目前交易形成的 DAG 如下圖:

整個 DAG 只有兩個 address $A$ 和 $B$ , 初始餘額分別是 10 , 5 , 總發行量是 15

交易 $0$ 是 A , -5

交易 $2$ 是 B , 3

交易 $3$ 是 B , 2

來看交易 $6$ 所驗證的交易(紅色部份):

紅色的交易是交易 $6$ 所認可的帳本

經過計算 , $A$ 的餘額是 5 , $B$ 的餘額是 10

所以符合第一個條件 , 所有 address 都沒有負的

也符合第二個條件 , 所有 address 總和是最初的發行量

這兩個條件是這樣來的

每次買賣 , 都有一方給錢 , 一方收錢 , 是單純的錢從某個戶頭轉到另一個戶頭

所以戶頭總共的金額是不變的 , 這是第二個條件

另外 , 戶頭無法轉移超出戶頭的金額 , 這就是第一個條件

這樣看 , 可以理解每一筆交易的 Trunk 與 Branch 都是對一些交易組成帳本的認可

# 帳本

分散式帳本可以理解為人人有一本 , 上面戶頭的金額大家一樣

上面提到每筆交易 trunk 和 branch 代表對先前交易的認同

所以一筆交易如果是大家認同的交易 , 那會有許多的交易驗證

如下圖表示:

藍色是認同交易 $2$ 的交易

可以看出 , 交易 $2$ 大部份都認同

# 確認

來看官方所給的確認算法
:::info
跑100次 Tip selection , 看有多少個 tip 驗證到查詢的交易 , 那就代表有多少%的確認度
:::

以下圖為例:

假設要查詢交易 $7$

跑一次 tip selection , 選到交易 $11$


交易 $7$ 沒有被驗證到(不是紅色) , 所以沒有增加1%的確認度

如果是選到交易 $13$

交易 $7$ 是紅色的 , 代表有驗證到 , 所以增加 1% 的確認度

可以觀察到 , 有許多 tip 驗證到的交易 , 確認增加 1% 的機率很大

例如交易 $2$:

全部 tip 都驗證到交易 $2$ 了

這邊也得到 tip selection 的一個要求:
:::success
tip selection 要讓一筆交易被 tip 驗證的比例 , 隨著時間要越來越高
:::

# 有問題的帳本

有問題的帳本自然是有 address 的餘額是負

舉個例子說明


假設交易 $13$ 所驗證到的交易

只有兩個 address $A$ 和 $B$

$A$ 與 $B$ 的初始餘額為 10 , 5

交易 $0$ , $1$ , $5$ 都是 0 元交易

交易 $2$ 是 $A$ , -10
交易 $7$ 是 $B$ , 10

交易 $4$ 是 $A$ , -10
交易 $10$ 是 $B$ , 10

這樣第二個條件會滿足 , 但是第一個條件不滿足

$A$ 的餘額是 -10

所以交易 $13$ 的 Trunk 與 Branch 需要重選

## 有衝突交易下確認的情況

之前提到是以高比例的 tip 有指向作為大家的共識

所以有衝突交易的情況

自然是最高比例 tip 驗證的交易是大家的共識

如下圖:

digraph init{
                rankdir=RL;
			 
				 a[ label="c" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				b[label="b" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                 e[label="e" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                  d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]	
			
          21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]	 
          
          11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]	
         
         31[label="31" color=red, fontcolor=red, fontsize=24, shape=box]	
        
         22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]	

12[label="12" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
    41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]	
     
    23[label="23" color=blue, fontcolor=blue, fontsize=24, shape=box]	
  
   13[label="13" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]	

33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
				a -> c;
                b -> c;  
				a -> c;
                b -> c;
                e -> a;
                e -> b;
                d -> a;
                d -> b;
                21->e;
                21->d;
                11->e;
                11->e;
                31->d;
                31->d;
                22->21;
                22->31;
              41->e;
              41->d;
              12->11;
              12->21;
              32->21;
              32->31;
              23->22;
              23->32;
              42->41;
              42->31;
              13->32;
              13->42;
              33->22;
              33->42;
          }

$\color{red}{11}$ 與 $\color{red}{31}$ 是衝突交易

$\color{red}{31}$ 被比較多交易驗證

這樣大家就決定出 , $\color{red}{31}$是大家接受的

所以 tip selection 要使 DAG 長成上圖的樣子

既然 $\color{red}{31}$ 被比較多交易驗證 , 那有個數值可以幫助 tip selection 做出選擇

就是一筆交易的累積權重

# 累積權重(cumulative weight)

以一張圖來說明如何計算

digraph init{
                rankdir=RL;
			 
				 a[ label="c" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				b[label="b" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                 e[label="e" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                  d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]	 
			
          
				a -> c;
                b -> c;  
				a -> c;
                b -> c;
                e -> a;
                e -> b;
                d -> a;
                d -> b;
                
                
                
              
          }

假設 $a$ , $b$ , $c$ , $d$ , $e$ 的自身權重分別是 3 , 9 , 3 , 3 , 9

那 $a$ 的權重就是有驗證到 $a$ 的交易自身權重和 $a$ 本身的權重相加

所以 $a$ 的累積權重是 3 + 9 + 3 + 3 + 9 = 27

$b$ 有 $e$ , $d$ 驗證

所以 $b$ 的累積權重是 9 + 3 + 9 = 21

## 交易自身權重

依照白皮書

交易自身權重跟交易的 Transaction Hash 有關


藍色反白就是交易的 Transaction Hash

注意到 hash 尾端有 5 個　9

這代表交易所做PoW問題的hash格式

PoW問題越難 , 交易自身權重越大

以這個例子 , 權重 15 , Transaction Hash 尾端就要有 5 個 9

# Tip Selection

從以上的討論 , 可以知道累積權重通常代表大家對某筆交易的認可

現在來看看 , 累積權重是如何幫助 tip selection

1. 累積權重影響 tip selection
2. 當 trunk 與 branch 所驗證的交易有衝突交易 , 選累積權重大的

## 累積權重影響 tip selection

簡單一句話 :
:::success
交易累積權重越大 , 驗證該交易的 tips 被選到的機率越大
:::

可以用 [Iota Tangle Visualization](https://github.com/iotaledger/iotavisualization/tree/one-by-one) 觀察

## 有衝突交易 , 選累積權重大的

以圖說明

digraph init{
                rankdir=RL;
			 
				 a[ label="c" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				b[label="b" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                 e[label="e" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                  d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]	
			
          21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]	 
          
          11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]	
         
         31[label="31" color=red, fontcolor=red, fontsize=24, shape=box]	
        
         22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]	

12[label="12" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
    41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]	
     
    23[label="23" color=blue, fontcolor=blue, fontsize=24, shape=box]	
  
   13[label="13" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]	

33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
				a -> c;
                b -> c;  
				a -> c;
                b -> c;
                e -> a;
                e -> b;
                d -> a;
                d -> b;
                21->e;
                21->d;
                11->e;
                11->e;
                31->d;
                31->d;
                22->21;
                22->31;
              41->e;
              41->d;
              12->11;
              12->21;
              32->21;
              32->31;
              23->22;
              23->32;
              42->41;
              42->31;
              13->32;
              13->42;
              33->22;
              33->42;
              new->12;
              new->23
          }

$\color{red}{11}$ 和 $\color{red}{31}$ 是衝突交易

$new$ 所驗證的交易 , 不滿足第一個條件

由於 $\color{red}{31}$ 累積權重比 $\color{red}{11}$ 大 , 所以交易 $23$ 保留 , 重新選一個 tip

可能會是這樣的選擇:

digraph init{
                rankdir=RL;
			 
				 a[ label="c" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				b[label="b" color=blue, fontcolor=blue, fontsize=24, shape=box];
				
				c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                 e[label="e" color=blue, fontcolor=blue, fontsize=24, shape=box]	
				           
                  d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]	
			
          21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]	 
          
          11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]	
         
         31[label="31" color=red, fontcolor=red, fontsize=24, shape=box]	
        
         22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]	

12[label="12" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
    41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]	
     
    23[label="23" color=blue, fontcolor=blue, fontsize=24, shape=box]	
  
   13[label="13" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
 42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]	

33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]	
 
				a -> c;
                b -> c;  
				a -> c;
                b -> c;
                e -> a;
                e -> b;
                d -> a;
                d -> b;
                21->e;
                21->d;
                11->e;
                11->e;
                31->d;
                31->d;
                22->21;
                22->31;
              41->e;
              41->d;
              12->11;
              12->21;
              32->21;
              32->31;
              23->22;
              23->32;
              42->41;
              42->31;
              13->32;
              13->42;
              33->22;
              33->42;
              new->23;
              new->33;
          }

這樣 $new$ 所驗證的交易就是正常的帳本了

###### tags: `IOTA`