Try   HackMD

權重

在進入選交易的算法前 , 要先討論交易的權重是如何變化的

注意到上面提到node讀的情況
我們想像DAG內有兩個衝突的交易a,b

目前a的權重最大
所以從node讀取會是a
blockchain需要有很難篡改的性質
所以如果在某個時間b的權重比a大
那就篡改了帳本

現在重點來了

選取交易的算法(被選到的交易會增加權重)
要能使一開始就是最大權重的交易 , 在往後任何時間都是最大的

另外 , 攻擊者可以發起對DAG上任意一筆與之衝突的交易
所以增加權重的算法 , 必須盡可能增加最多交易的權重

綜合上面所述 , 問題如下:

給定一個任意的DAG , 給定任意數量的新交易

這些新交易怎麼選 , 才能達到上面的目的？

所以接下來來考慮不同的交易情況 , 討論不同的選法

沒有指向DAG不存在的交易 , 一個增加一筆交易的例子

從簡單的情況開始討論

假設某個node的DAG如下圖







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c

a 是最一開始的交易

c 就是白皮書中提到的
tip

這邊給一下

tip 的定義

交易沒有被其他交易指到
就是

tip

我們假設每個交易的權重都是1

這樣

a 的權重是3

b 是2

c 是1

權重的計算是全部有驗證或間接驗證到該交易的加總

所以不會有一筆交易被算兩次

接下來的一段時間 , 來了新的一筆交易

d , 並接到DAG上

那它可能有三種接法(以上圖為例)

第一種　接到最初的交易







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->c





d->c

算一下
這時

a 的權重是4
b 還是2
c 還是1

會發現

b 和
c 都沒增加

第二種　接中間的交易







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->b





d->b

這時

a 的權重是4

b 是3

c ,
d 都是1

c ,
d 權重沒有增加

第三種　接到tip上







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->a





d->a

算一下權重

a 是4
b 是3
c 是2

只有

d 是1

當有交易指向DAG不存在的交易 , 一個增加一筆交易的例子

這邊分成兩種 , 一個是其中一個指到不存在 , 另一個是都指到不存在

其中一個指到不存在的交易

這邊要考慮指到不存在的交易的種類與新交易如何選的情況

所以例子比較多 , 比較複雜

先舉其中一種例子 , 觀察一下如何分析







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->b





Transaction doesn't exist in this node's DAG.

Transaction doesn't exist in this node's DAG.



d->Transaction doesn't exist in this node's DAG.





e

e



e->a





e->d

藍色的 , 是node舊有的

紅色的 , 是其中一個指到不存在的交易

綠色是新來的交易

實際上仔細觀察會發現 , 這跟兩筆所驗證的交易都在DAG是相同權重增加的情況

差別在於 , 所指的不存在的交易 , 會不知道是什麼樣的交易 , 如果是衝突的會有問題

都指到不存在的交易

這邊新來交易驗證的選擇 , 共有三種

如下

新交易兩邊都選指到不存在的交易







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



f

f



d->f





g

g



d->g





e

e



e->d





e->d

藍色的 , 是舊有的交易

紅色的 , 是兩筆選的交易 , 都是不存在的交易

f , g 兩個是不在node的交易

綠色是發起的交易

可以看到 , 舊有的交易(藍色

a ,
b ,
c)
都沒有增加到權重

新交易其中一個選到都指到不存在的交易







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



f

f



d->f





g

g



d->g





e

e



e->a





e->d

藍色的 , 是舊有的交易

紅色的 , 是兩筆選的交易 , 都是不存在的交易

f , g 兩個是不在node的交易

綠色是發起的交易

可以看到除了綠色的交易 , 其他的交易都會增加權重 , 包含

f , g

新交易都沒選都指到不存在的交易







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



f

f



d->f





g

g



d->g





e

e



e->a





e->a

藍色的 , 是舊有的交易

紅色的 , 是兩筆選的交易 , 都是不存在的交易

f , g 兩個是不在node的交易

綠色是發起的交易

只會剩下舊有的交易會增加權重

總結

回想一下之前的假設:

從tangle選衝突內最大權重的交易

這句話意味著:

可能的話 , 加入的交易
權重都要隨著時間而增加
而且 , 可能的話 , 要比第二大衝突的交易增加更多
所以與第二大的權重差不能隨著時間縮小

那從上面的討論很容易看出 , 一個好的選tip算法 , 應該要有:

選接到DAG上的tip
可以使之前的交易增加權重
且大部份舊的交易都被增加到

不過 , DAG不一定都是很簡單
新來的交易選的被驗證交易 , 不一定是同一個

例如:







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->a





d->b

d選b和c

這樣a,b,c還是有被增加權重

可以這樣說

新交易有選到原本node　DAG的tip
那就很容易大部份的交易權重都有增加

不過 , DAG不一定如上圖

比如說可以是







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c

三個變化不多拉

看五個的







tangle



a

c



b

b



a->b





c

a



a->c





b->c





b->c





d

d



d->a





d->b





e

e



e->c





e->d

有點複雜

從上面的情況

目前大概可以肯定

選取被驗證交易的算法
要盡可能選DAG的tip

接下來

看另一種情況







tangle



a

c



b

b



a->b





a->b





c

a



b->c





b->c





d

d



d->a





d->a





e

e



e->b





e->b





f

f



f->d





f->d

可以看到

e ,
f 都是tip

e 就是
lazy tip

可是新的交易接到

e
,
c ,
d ,
f 都不會增加權重

所以到這邊 , 可以得到結論

選交易的算法 , 要選tip且要盡可能不選lazy tip

衝突交易

來看如果有衝突的交易

有向邊可搜尋到的衝突交易

先講結論:

不用管

考慮一般情況的衝突示意圖
如下







tangle



b

b



d

d



b->d





a

a



init

init



a->init





d->a





c

c



c->a





e

e



e->d





f

f



f->b

a,b 是衝突的交易

init,c,d,e,f 是
sub−DAG 或 沒有交易

可以看到新來的交易不管選哪個

a 的權重都會是最大的

不會出現

b 會是最大權重的情況
(在
c,d,e,f 有交集也成立)

所以

b 永遠替代不了
a

有向邊搜尋找不到的衝突交易

一樣先看簡單的







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c

紅色的是衝突的交易 , 藍色是正常的交易

以上圖來說 , b與c是衝突的交易 , a是正常的

很明確的 , c往有向邊的方向搜尋 , 是找不到衝突的交易
b同樣也是

可是DAG內有衝突的交易

現在來看增加一筆新交易d的情況 , 只看接在tip的情況（接在比b,c前面不會增加b與c的權重,不考慮這種情況）

接在b







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c





d

d



d->b





d->b

b的權重是2

c是1

b權重最大

接在c







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c





d

d



d->a





d->a

b的權重是1

c的權重是2

c權重最大

b與c都接







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c





d

d



d->a





d->b

c的權重是2

b也是2

b與c權重一樣大

小總結

恩 , 從上面的結果
什麼情況都有
代表這種類型的衝突交易很危險
容易被用來篡改帳本
選取被驗證交易的算法 , 要避免這種情況

衝突交易的選擇

由前面共識演算法的一致性

可以知道:

要讓衝突內最大權重的交易 , 一直是最大權重的

node 發現衝突交易與沒發現衝突交易的行為

node沒發現DAG有衝突交易的話 , 那衝突的交易都可能增加權重

node發現有衝突的交易 , 選的交易會讓衝突交易中權重最大的交易增加權重

例如:







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c





d

d



d->b





d->b

這是一個有衝突交易的DAG

藍色是正常的交易

紅色是衝突的交易

可以看到

b 是衝突交易內最大權重的

所以當node發現有衝突的交易時 , 是這樣選的







tangle



a

c



c

a



a->c





a->c





b

b



b->c





b->c





d

d



d->b





d->b





e

e



e->d





e->d

綠色的交易 , 是新發起的交易 , 選到d

這樣

b 的權重就增加

然後其他衝突交易的權重就沒有增加到

這樣帳本的紀錄就會是

b , 跟沒有綠色交易的DAG一樣

衝突交易的檢查

有衝突交易的DAG

有許多種情況 , 基本都要是有向邊搜尋不到的衝突交易

距離

這裡距離是指沿著有向邊 , 找到相遇的交易後 , 共經歷過幾筆交易 , 例如:

假設DAG如下







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

以紅色的交易代表是衝突的交易

附近是這種情況







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

這樣就是比較近的交易 , 他們有

21 這筆相遇的交易

當然 ,

31 這筆也是

可能會有多個 , 看最少那個 , 這個是距離1的

來看相較比較遠的







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

e 會是相遇的 , 距離是3

中間經過

e ,
41 和
42

兩筆衝突交易距離比較近

分三種 ,

lazy tip 附近 ,
tip 附近 , 不是
tip 附近

lazy tip 附近

就是衝突交易其中一筆 , 是

lazy 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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

或







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e





51

51



51->e





51->e
tip 附近

就是上面

應該選

tip , 盡可能不選
lazy 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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

或







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e
不是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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

隨著時間過去 , 如果沒node發現的話

會變成類似下圖的情況







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

兩筆衝突交易距離比較遠

有tip
  • lazy 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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e
  • 不是
    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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e





12

12



12->21





12->11
  • 只有
    lazy 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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->a





11->a
沒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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





f

f



11->f





f->a





f->a

白皮書提到的交易選取算法問題

這邊假設檢查衝突交易是在選被驗證交易算法中隨機檢查

嚴格來說 , 檢查交易與選被驗證交易是可以分開的兩件事

但是以官方release的資料來看 , 是一起做的

在選被驗證交易時檢查交易

以其中一張有衝突交易的圖為例

5 是發現
w ,
y 是衝突的交易

可是

1 和
2 卻沒發現

這跟如何檢查交易是有關係的

一筆交易檢查交易 , 是沿著DAG邊的方向去檢查的

例如

1 可能會檢查
w ,
x ,
q ,
s 和
u

當然可以檢查更深入的交易 , 例如

m 與
p

不過不必要檢查太深的 , 例如

a

因為已經有許多交易檢查過了

所以

1 會發現有衝突的交易

但是在

1 所檢查過的交易 , 並沒有與
w 衝突的

所以選擇

w 作為
1 被驗證的交易是可以的

同樣的情況 ,

2 也是

所以

5 才能發現

因為

5 是選
1 和
2 , 所以會發現
w 與
y 是衝突的

那就不能選

1 與
2 , 其中一個要換掉

Uniform 不好找到衝突交易的DAG

這蠻多的 , 衝突交易不是

tip 的都是(包含
lazy tip)

MCMC 不好找到衝突交易的DAG

如下的DAG , MCMC不容易發現衝突交易







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





41

41



41->e





41->d





31

31



31->d





31->d





42

42



42->41





42->31





21

21



21->e





21->d





32

32



32->31





32->21





43

43



43->42





43->32





33

33



33->42





22

22



33->22





22->31





22->21





11

11



11->e





11->e

權重計算的實作

cumulative weight

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