Try   HackMD

IOTA Consensus Algorithm Introduction

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

交易

一筆交易

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

Address

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

Value

正代表 Address 錢增加

負代表 Address 錢減少

Trunk

交易會組成 DAG

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

Branch

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

Trunk 與 Branch

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

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

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

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

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

這邊需要詳細解釋

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

整個 DAG 只有兩個 address

A 和
B , 初始餘額分別是 10 , 5 , 總發行量是 15

交易

0 是 A , -5

交易

2 是 B , 3

交易

3 是 B , 2

來看交易

6 所驗證的交易(紅色部份):
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

紅色的交易是交易

6 所認可的帳本

經過計算 ,

A 的餘額是 5 ,
B 的餘額是 10

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

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

這兩個條件是這樣來的

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

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

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

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

帳本

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

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

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

如下圖表示:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

藍色是認同交易

2 的交易

可以看出 , 交易

2 大部份都認同

確認

來看官方所給的確認算法

跑100次 Tip selection , 看有多少個 tip 驗證到查詢的交易 , 那就代表有多少%的確認度

以下圖為例:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

假設要查詢交易

7

跑一次 tip selection , 選到交易

11

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

交易

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

如果是選到交易

13
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

交易

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

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

例如交易

2:
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

全部 tip 都驗證到交易

2 了

這邊也得到 tip selection 的一個要求:

tip selection 要讓一筆交易被 tip 驗證的比例 , 隨著時間要越來越高

有問題的帳本

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

舉個例子說明

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

假設交易

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 驗證的交易是大家的共識

如下圖:







init



a

c



c

a



a->c





a->c





b

b



b->c





b->c





e

e



e->a





e->b





d

d



d->a





d->b





21

21



21->e





21->d





11

11



11->e





11->e





31

31



31->d





31->d





22

22



22->21





22->31





12

12



12->21





12->11





32

32



32->21





32->31





41

41



41->e





41->d





23

23



23->22





23->32





13

13



13->32





42

42



13->42





42->31





42->41





33

33



33->22





33->42

11 與
31 是衝突交易

31 被比較多交易驗證

這樣大家就決定出 ,

31是大家接受的

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

既然

31 被比較多交易驗證 , 那有個數值可以幫助 tip selection 做出選擇

就是一筆交易的累積權重

累積權重(cumulative weight)

以一張圖來說明如何計算







init



a

c



c

a



a->c





a->c





b

b



b->c





b->c





e

e



e->a





e->b





d

d



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

簡單一句話 :

交易累積權重越大 , 驗證該交易的 tips 被選到的機率越大

可以用 Iota Tangle Visualization 觀察

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

以圖說明







init



a

c



c

a



a->c





a->c





b

b



b->c





b->c





e

e



e->a





e->b





d

d



d->a





d->b





21

21



21->e





21->d





11

11



11->e





11->e





31

31



31->d





31->d





22

22



22->21





22->31





12

12



12->21





12->11





32

32



32->21





32->31





41

41



41->e





41->d





23

23



23->22





23->32





13

13



13->32





42

42



13->42





42->31





42->41





33

33



33->22





33->42





new

new



new->12





new->23

11 和
31 是衝突交易

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

由於

31 累積權重比
11 大 , 所以交易
23 保留 , 重新選一個 tip

可能會是這樣的選擇:







init



a

c



c

a



a->c





a->c





b

b



b->c





b->c





e

e



e->a





e->b





d

d



d->a





d->b





21

21



21->e





21->d





11

11



11->e





11->e





31

31



31->d





31->d





22

22



22->21





22->31





12

12



12->21





12->11





32

32



32->21





32->31





41

41



41->e





41->d





23

23



23->22





23->32





13

13



13->32





42

42



13->42





42->31





42->41





33

33



33->22





33->42





new

new



new->23





new->33

這樣

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

tags: IOTA
Last changed by 
 
blockchain
Blockchain 研究
0
1247
Published on HackMD