# 權重
在進入選交易的算法前 , 要先討論交易的權重是如何變化的
注意到上面提到node讀的情況
我們想像DAG內有兩個衝突的交易a,b
目前a的權重最大
所以從node讀取會是a
blockchain需要有很難篡改的性質
所以如果在某個時間b的權重比a大
那就篡改了帳本
現在重點來了
:::success
選取交易的算法(被選到的交易會增加權重)
要能使一開始就是最大權重的交易 , 在往後任何時間都是最大的
:::
另外 , 攻擊者可以發起對DAG上任意一筆與之衝突的交易
所以增加權重的算法 , 必須盡可能增加最多交易的權重
綜合上面所述 , 問題如下:
:::info
給定一個任意的DAG , 給定任意數量的新交易
這些新交易怎麼選 , 才能達到上面的目的？
:::
所以接下來來考慮不同的交易情況 , 討論不同的選法
## 沒有指向DAG不存在的交易 , 一個增加一筆交易的例子
從簡單的情況開始討論
假設某個node的DAG如下圖
```graphviz
digraph tangle{
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]
a -> b;
b -> c;
a -> b;
b -> c;
}
```
$\color{blue}{a}$ 是最一開始的交易
$\color{blue}{c}$ 就是白皮書中提到的 $tip$
這邊給一下 $tip$ 的定義
:::success
交易沒有被其他交易指到
就是 $tip$
:::
我們假設每個交易的權重都是1
這樣 $\color{blue}{a}$ 的權重是3
$\color{blue}{b}$ 是2
$\color{blue}{c}$ 是1
權重的計算是全部有驗證或間接驗證到該交易的加總
所以不會有一筆交易被算兩次
接下來的一段時間 , 來了新的一筆交易 $\color{green}{d}$ , 並接到DAG上
那它可能有三種接法(以上圖為例)
### 第一種 接到最初的交易
```graphviz
digraph tangle{
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]
d[label="d" color=green, fontcolor=green, fontsize=24, shape=box]
a -> b;
b -> c;
a -> b;
b -> c;
d -> c;
d -> c;
}
```
算一下
這時
$\color{blue}{a}$ 的權重是4
$\color{blue}{b}$ 還是2
$\color{blue}{c}$ 還是1
會發現 $\color{blue}{b}$ 和 $\color{blue}{c}$ 都沒增加
### 第二種 接中間的交易
```graphviz
digraph tangle{
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]
d[label="d" color=green, fontcolor=green, fontsize=24, shape=box]
a -> b;
b -> c;
a -> b;
b -> c;
d -> b;
d -> b;
}
```
這時
$\color{blue}{a}$ 的權重是4
$\color{blue}{b}$ 是3
$\color{blue}{c}$ , $\color{blue}{d}$ 都是1
$\color{blue}{c}$ , $\color{green}{d}$ 權重沒有增加
### 第三種 接到tip上
```graphviz
digraph tangle{
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]
d[label="d" color=green, fontcolor=green, fontsize=24, shape=box]
a -> b;
b -> c;
a -> b;
b -> c;
d -> a;
d -> a;
}
```
算一下權重
$\color{blue}{a}$ 是4
$\color{blue}{b}$ 是3
$\color{blue}{c}$ 是2
只有 $\color{green}{d}$ 是1
### 當有交易指向DAG不存在的交易 , 一個增加一筆交易的例子
這邊分成兩種 , 一個是其中一個指到不存在 , 另一個是都指到不存在
### 其中一個指到不存在的交易
這邊要考慮指到不存在的交易的種類與新交易如何選的情況
所以例子比較多 , 比較複雜
先舉其中一種例子 , 觀察一下如何分析
```graphviz
digraph tangle{
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]
d[label="d" color=red, fontcolor=red, fontsize=24, shape=box];
e[label="e" color=green, fontcolor=green, fontsize=24, shape=box];
a -> b;
b -> c;
a -> b;
b -> c;
d -> b;
d -> "Transaction doesn't exist in this node's DAG.";
e -> d;
e -> a;
}
```
藍色的 , 是node舊有的
紅色的 , 是其中一個指到不存在的交易
綠色是新來的交易
實際上仔細觀察會發現 , 這跟兩筆所驗證的交易都在DAG是相同權重增加的情況
差別在於 , 所指的不存在的交易 , 會不知道是什麼樣的交易 , 如果是衝突的會有問題
### 都指到不存在的交易
這邊新來交易驗證的選擇 , 共有三種
如下
#### 新交易兩邊都選指到不存在的交易
```graphviz
digraph tangle{
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]
d[label="d" color=red, fontcolor=red, fontsize=24, shape=box];
e[label="e" color=green, fontcolor=green, fontsize=24, shape=box];
a -> b;
b -> c;
a -> b;
b -> c;
d -> f;
d -> g;
e -> d;
e -> d;
}
```
藍色的 , 是舊有的交易
紅色的 , 是兩筆選的交易 , 都是不存在的交易
$f\space ,\space g$ 兩個是不在node的交易
綠色是發起的交易
可以看到 , 舊有的交易(藍色 $\color{blue}{a}$ , $\color{blue}{b}$ , $\color{blue}{c}$)
都沒有增加到權重
#### 新交易其中一個選到都指到不存在的交易
```graphviz
digraph tangle{
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]
d[label="d" color=red, fontcolor=red, fontsize=24, shape=box];
e[label="e" color=green, fontcolor=green, fontsize=24, shape=box];
a -> b;
b -> c;
a -> b;
b -> c;
d -> f;
d -> g;
e -> d;
e -> a;
}
```
藍色的 , 是舊有的交易
紅色的 , 是兩筆選的交易 , 都是不存在的交易
$f\space ,\space g$ 兩個是不在node的交易
綠色是發起的交易
可以看到除了綠色的交易 , 其他的交易都會增加權重 , 包含 $f\space ,\space g$
#### 新交易都沒選都指到不存在的交易
```graphviz
digraph tangle{
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]
d[label="d" color=red, fontcolor=red, fontsize=24, shape=box];
e[label="e" color=green, fontcolor=green, fontsize=24, shape=box];
a -> b;
b -> c;
a -> b;
b -> c;
d -> f;
d -> g;
e -> a;
e -> a;
}
```
藍色的 , 是舊有的交易
紅色的 , 是兩筆選的交易 , 都是不存在的交易
$f\space ,\space g$ 兩個是不在node的交易
綠色是發起的交易
只會剩下舊有的交易會增加權重
### 總結
回想一下之前的假設:
:::info
從tangle選衝突內最大權重的交易
:::
這句話意味著:
:::info
可能的話 , 加入的交易
權重都要隨著時間而增加
而且 , 可能的話 , 要比第二大衝突的交易增加更多
所以與第二大的權重差不能隨著時間縮小
:::
那從上面的討論很容易看出 , 一個好的選tip算法 , 應該要有:
:::success
選接到DAG上的tip
可以使之前的交易增加權重
且大部份舊的交易都被增加到
:::
不過 , DAG不一定都是很簡單
新來的交易選的被驗證交易 , 不一定是同一個
例如:
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=Blue, fontcolor=Red, fontsize=24, shape=box];
b[label="b" color=Blue, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=Blue, fontcolor=Red, fontsize=24, shape=box]
d[label="d" color=Blue, fontcolor=Red, fontsize=24, shape=box]
a -> b;
b -> c;
a -> b;
b -> c;
d -> a;
d -> b;
}
```
d選b和c
這樣a,b,c還是有被增加權重
可以這樣說
:::info
新交易有選到原本node DAG的tip
那就很容易大部份的交易權重都有增加
:::
不過 , DAG不一定如上圖
比如說可以是
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=Blue, fontcolor=Red, fontsize=24, shape=box];
b[label="b" color=Blue, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=Blue, fontcolor=Red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
}
```
三個變化不多拉
看五個的
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=Blue, fontcolor=Red, fontsize=24, shape=box];
b[label="b" color=Blue, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=Blue, fontcolor=Red, fontsize=24, shape=box]
d[label="d" color=Blue, fontcolor=Red, fontsize=24, shape=box]
e[label="e" color=Blue, fontcolor=Red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> b;
b -> c;
d -> b;
d -> a;
e -> d;
e -> c;
}
```
有點複雜
從上面的情況
目前大概可以肯定
:::success
選取被驗證交易的算法
要盡可能選DAG的tip
:::
接下來
看另一種情況
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=Blue, fontcolor=Red, fontsize=24, shape=box];
b[label="b" color=Blue, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=Blue, fontcolor=Red, fontsize=24, shape=box]
d[label="d" color=Blue, fontcolor=Red, fontsize=24, shape=box]
e[label="e" color=Blue, fontcolor=Red, fontsize=24, shape=box]
f[label="f" color=Blue, fontcolor=Red, fontsize=24, shape=box]
a -> b;
b -> c;
a -> b;
b -> c;
d -> a;
d -> a;
e -> b;
e -> b;
f -> d;
f -> d;
}
```
可以看到 $\color{red}{e}$ , $\color{red}{f}$ 都是tip
$\color{red}{e}$ 就是 $lazy \space tip$
可是新的交易接到 $\color{red}{e}$
, $\color{red}{c}$ , $\color{red}{d}$ , $\color{red}{f}$ 都不會增加權重
所以到這邊 , 可以得到結論
:::success
選交易的算法 , 要選tip且要盡可能不選lazy tip
:::
# 衝突交易
來看如果有衝突的交易
## 有向邊可搜尋到的衝突交易
先講結論:
:::success
不用管
:::
考慮一般情況的衝突示意圖
如下
```graphviz
digraph tangle{
rankdir=RL;
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
a[label="a" color=red, fontcolor=red, fontsize=24, shape=box];
a -> init;
b -> d;
c -> a;
d -> a;
e -> d;
f -> b;
}
```
$\color{red}{a},\color{red}{b}$ 是衝突的交易
$init,c,d,e,f$ 是 $sub-DAG$ 或 沒有交易
可以看到新來的交易不管選哪個
$\color{red}{a}$ 的權重都會是最大的
不會出現 $\color{red}{b}$ 會是最大權重的情況
(在 $c,d,e,f$ 有交集也成立)
所以 $\color{red}{b}$ 永遠替代不了 $\color{red}{a}$
## 有向邊搜尋找不到的衝突交易
一樣先看簡單的
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
}
```
紅色的是衝突的交易 , 藍色是正常的交易
以上圖來說 , b與c是衝突的交易 , a是正常的
很明確的 , c往有向邊的方向搜尋 , 是找不到衝突的交易
b同樣也是
可是DAG內有衝突的交易
現在來看增加一筆新交易d的情況 , 只看接在tip的情況（接在比b,c前面不會增加b與c的權重,不考慮這種情況）
### 接在b
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]
d -> b;
d -> b;
a -> c;
b -> c;
a -> c;
b -> c;
}
```
b的權重是2
c是1
b權重最大
### 接在c
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]
d -> a;
d -> a;
a -> c;
b -> c;
a -> c;
b -> c;
}
```
b的權重是1
c的權重是2
c權重最大
### b與c都接
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]
d -> a;
d -> b;
a -> c;
b -> c;
a -> c;
b -> c;
}
```
c的權重是2
b也是2
b與c權重一樣大
### 小總結
恩 , 從上面的結果
什麼情況都有
代表這種類型的衝突交易很危險
容易被用來篡改帳本
選取被驗證交易的算法 , 要避免這種情況
## 衝突交易的選擇
由前面共識演算法的一致性
可以知道:
:::success
要讓衝突內最大權重的交易 , 一直是最大權重的
:::
### node 發現衝突交易與沒發現衝突交易的行為
node沒發現DAG有衝突交易的話 , 那衝突的交易都可能增加權重
node發現有衝突的交易 , 選的交易會讓衝突交易中權重最大的交易增加權重
例如:
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]
d -> b;
d -> b;
a -> c;
b -> c;
a -> c;
b -> c;
}
```
這是一個有衝突交易的DAG
藍色是正常的交易
紅色是衝突的交易
可以看到 $\color{red}{b}$ 是衝突交易內最大權重的
所以當node發現有衝突的交易時 , 是這樣選的
```graphviz
digraph tangle{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=Red, fontsize=24, shape=box];
c[label="a" color=blue, fontcolor=blue, fontsize=24, shape=box]
d[label="d" color=blue, fontcolor=blue, fontsize=24, shape=box]
e[label="e" color=green, fontcolor=green, fontsize=24, shape=box]
d -> b;
d -> b;
a -> c;
b -> c;
a -> c;
b -> c;
e -> d;
e -> d;
}
```
綠色的交易 , 是新發起的交易 , 選到d
這樣 $\color{red}{b}$ 的權重就增加
然後其他衝突交易的權重就沒有增加到
這樣帳本的紀錄就會是 $\color{red}{b}$ , 跟沒有綠色交易的DAG一樣
## 衝突交易的檢查
### 有衝突交易的DAG
有許多種情況 , 基本都要是有向邊搜尋不到的衝突交易
#### 距離
這裡距離是指沿著有向邊 , 找到相遇的交易後 , 共經歷過幾筆交易 , 例如:
假設DAG如下
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
以紅色的交易代表是衝突的交易
附近是這種情況
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=red, fontcolor=red, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=red, fontcolor=red, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
這樣就是比較近的交易 , 他們有 $\color{blue}{21}$ 這筆相遇的交易
當然 , $\color{blue}{31}$ 這筆也是
可能會有多個 , 看最少那個 , 這個是距離1的
來看相較比較遠的
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=red, fontcolor=red, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
$\color{blue}{e}$ 會是相遇的 , 距離是3
中間經過 $\color{blue}{e}$ , $\color{blue}{41}$ 和 $\color{blue}{42}$
#### 兩筆衝突交易距離比較近
分三種 , $lazy \space tip$ 附近 , $tip$ 附近 , 不是 $tip$ 附近
##### lazy tip 附近
就是衝突交易其中一筆 , 是 $lazy \space tip$
例如
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=red, fontcolor=red, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
或
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
51[label="51" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
51->e;
51->e;
}
```
##### tip 附近
就是上面
:::success
應該選 $tip$ , 盡可能不選 $lazy \space tip$
:::
所說的 $tip$
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=red, fontcolor=red, fontsize=24, shape=box]
33[label="33" color=red, fontcolor=red, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
或
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=red, fontcolor=red, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=red, fontcolor=red, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
##### 不是tip 附近
基本上是一種
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=red, fontcolor=red, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=red, fontcolor=red, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
隨著時間過去 , 如果沒node發現的話
會變成類似下圖的情況
```graphviz
digraph init{
rankdir=RL;
a[ label="c" color=red, fontcolor=red, fontsize=24, shape=box];
b[label="b" color=red, fontcolor=red, 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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
#### 兩筆衝突交易距離比較遠
##### 有tip
* $lazy \space tip$
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=red, fontcolor=red, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
* 不是 $tip$
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=red, fontcolor=red, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
12[label="12" color=blue, fontcolor=blue, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
12->11;
12->21;
}
```
* 只有 $lazy \space tip$
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=red, fontcolor=red, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->a;
11->a;
22->21;
22->31;
33->22;
33->42;
}
```
##### 沒tip
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=red, fontcolor=red, fontsize=24, shape=box]
43[label="43" color=blue, fontcolor=blue, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=blue, fontcolor=blue, fontsize=24, shape=box]
f[label="f" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->f;
22->21;
22->31;
33->22;
33->42;
f->a;
f->a;
}
```
### 白皮書提到的交易選取算法問題
這邊假設檢查衝突交易是在選被驗證交易算法中隨機檢查
嚴格來說 , 檢查交易與選被驗證交易是可以分開的兩件事
但是以官方release的資料來看 , 是一起做的
在選被驗證交易時檢查交易
以其中一張有衝突交易的圖為例
$\color{red}{5}$ 是發現 $\color{red}{w}$ , $\color{red}{y}$ 是衝突的交易
可是 $\color{yellow}{1}$ 和 $\color{yellow}{2}$ 卻沒發現
這跟如何檢查交易是有關係的
一筆交易檢查交易 , 是沿著DAG邊的方向去檢查的
例如 $\color{yellow}{1}$ 可能會檢查 $\color{red}{w}$ , $\color{blue}{x}$ , $\color{blue}{q}$ , $\color{blue}{s}$ 和 $\color{blue}{u}$
當然可以檢查更深入的交易 , 例如 $\color{green}{m}$ 與 $\color{blue}{p}$
不過不必要檢查太深的 , 例如 $\color{green}{a}$
因為已經有許多交易檢查過了
所以 $\color{yellow}{1}$ 會發現有衝突的交易
但是在 $\color{yellow}{1}$ 所檢查過的交易 , 並沒有與 $\color{red}{w}$ 衝突的
所以選擇 $\color{red}{w}$ 作為 $\color{yellow}{1}$ 被驗證的交易是可以的
同樣的情況 , $\color{yellow}{2}$ 也是
所以 $\color{red}{5}$ 才能發現
因為 $\color{red}{5}$ 是選 $\color{yellow}{1}$ 和 $\color{yellow}{2}$ , 所以會發現 $\color{red}{w}$ 與 $\color{red}{y}$ 是衝突的
那就不能選 $\color{yellow}{1}$ 與 $\color{yellow}{2}$ , 其中一個要換掉
#### Uniform 不好找到衝突交易的DAG
這蠻多的 , 衝突交易不是 $tip$ 的都是(包含 $lazy \space tip$)
#### MCMC 不好找到衝突交易的DAG
如下的DAG , MCMC不容易發現衝突交易
```graphviz
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]
41[label="41" color=blue, fontcolor=blue, fontsize=24, shape=box]
31[label="31" color=blue, fontcolor=blue, fontsize=24, shape=box]
42[label="42" color=blue, fontcolor=blue, fontsize=24, shape=box]
21[label="21" color=blue, fontcolor=blue, fontsize=24, shape=box]
32[label="32" color=blue, fontcolor=blue, fontsize=24, shape=box]
43[label="43" color=red, fontcolor=red, fontsize=24, shape=box]
33[label="33" color=blue, fontcolor=blue, fontsize=24, shape=box]
22[label="22" color=blue, fontcolor=blue, fontsize=24, shape=box]
11[label="11" color=red, fontcolor=red, fontsize=24, shape=box]
a -> c;
b -> c;
a -> c;
b -> c;
e -> a;
e -> b;
d -> a;
d -> b;
41->e;
41->d;
31->d;
31->d;
42->41;
42->31;
21->e;
21->d;
32->21;
32->31;
43->42;
43->32;
11->e;
11->e;
22->21;
22->31;
33->22;
33->42;
}
```
# 權重計算的實作
[cumulative weight](https://github.com/alongalky/iota-docs/blob/master/cumulative.md)
###### tags: `IOTA`
Sign in with Wallet
Connect another wallet