確認(Confirmation)

討論確認相關的文件

之前提過 , 確認的交易可以拿來算帳

也就代表賣家可以交付數據 , 商品或服務的最低條件

先看最近的文件的圖

這段相關的原文

In the tangle above, transaction 9 is approved by two out of the four tips. If we were using uniform random tip selection, it would have a confidence of exactly 50%. However, the tips that approve it are apparently more likely than the tips that do not, which raises the confidence a bit.

$9$ 那筆交易在模擬的圖上 , 確認度是

$0.54$

這張圖來說 ,

$11$ ,

$12$ ,

$13$ ,

$7$ 都是

$tip$

而

$7$ 跟

$lazytip$ 比較接近

$lazytip$ 對於確認度的增加是比較低的

$13$ 與

$12$ 指向了

$9$

由於

$7$ 對確認度的增加是比較低的

所以

$9$ 的確認度應該超過

$0.5$

接著就是算講確認度很完整的文件了

直接來看文件上的圖

$\text{color}yellow1$ ,

$\text{color}yellow2$ 是

$tip$

$\text{color}greenFullyConfirmed$ 指的是確認度為

$1$

綠色的交易 , 都有被

$\text{color}yellow1$ 與

$\text{color}yellow2$ 間接指向到

藍色的交易 , 則是

$\text{color}yellow1$ 或

$\text{color}yellow2$ 其中一筆間接或直接指向到

接下來看

$\text{color}yellow1$ 剛加入

$DAG$ 的情況

$tip$ 有三個 , 分別是

$\text{color}grayz$ ,

$\text{color}grayy$ 和

$\text{color}yellow1$

注意到

$\text{color}yellow1$ 還沒加到

$DAG$ 時 ,

$\text{color}bluen$ 還不是綠色(

$\text{color}greenFullyConfirmed$)

$\text{color}yellow1$ 還沒加到

$DAG$

$tip$ 是

$\text{color}bluew$ ,

$\text{color}bluex$ ,

$\text{color}grayz$ 和

$\text{color}grayy$

這時直接或間接指向

$\text{color}bluen$ 的

$tip$ 是

$\text{color}bluex$ ,

$\text{color}grayz$ 與

$\text{color}grayy$

少了個

$\text{color}bluew$ , 所以還是藍色的

$\text{color}yellow1$ 加入

$DAG$ 後 , 會全部的

$tip$ 都直接或間接指向

$\text{color}bluen$

所以

$\text{color}bluen$ 會變成綠色(

$\text{color}greenFullyConfirmed$)

接下來的

$DAG$ 變成這樣

接著來看不是指向

$tip$ 的交易如何影響確認度

$\text{color}yellow5$ 是新來的

$tip$ , 不過沒有指向舊有的

$tip$ (

$\text{color}yellow1$ ,

$\text{color}yellow2$ ,

$\text{color}yellow3$ ,

$\text{color}yellow4$)

可以注意到

$\text{color}bluen$ 不是

$\text{color}greenFullyConfirmed$ 了

因為

$\text{color}yellow5$ 並沒有直接或間接指向

$\text{color}bluen$

可以看到 , 確認度不是一直增加的 , 是可能會減少的

接下來看有衝突交易的情況

這邊就跟白皮書有關了 , 有關的如下

節點間並不需要達成共識，因為合法的交易有權繼續在 tangle 中; 但要是出現衝突的交易，便需要決定哪筆交易要被孤立 (orphaned)，也就是這筆交易不會再被新進的交易間接驗證。決定哪筆交易是要被孤立的主要準則如下：一個節點進行多次的 tip 選擇演算法，接著觀察哪筆交易較可能被選到的 tip（間接）驗證。舉例來說：假設跑了 100 次 tip 選擇演算法，有一筆交易被選到 97 次，我們便說它有 97% 的信心被驗證到。

實在看不懂白皮書在說什麼 , 不過沒關係

文件會說明

注意到

$\text{color}red5$ 這筆交易在驗證先前的交易 , 預計是指向

$\text{color}yellow1$ 與

$\text{color}yellow2$

$\text{color}redw$ 與

$\text{color}redy$ 是衝突交易

$\text{color}red5$ 還沒選好指向的交易 , 所以還不算是

$tip$

這時的

$tip$ 是

$\text{color}yellow1$ ,

$\text{color}yellow2$ ,

$\text{color}yellow3$ 與

$\text{color}yellow4$

$\text{color}redw$ 只有被

$\text{color}yellow1$ 指向

$\text{color}redy$ 只有被

$\text{color}yellow2$ 指向

如果

$\text{color}red5$ 指向

$\text{color}yellow1$ 與

$\text{color}yellow2$

這時

$tip$ 是

$\text{color}red5$ ,

$\text{color}yellow3$ 與

$\text{color}yellow4$

而

$\text{color}redw$ 和

$\text{color}redy$ 確認度都會增加 (從四分之一變成三分之一)

這樣是不行的 , 衝突交易內只能有一筆能增加確認度

選擇的判斷條件是衝突交易內的累積權重(

$cumulativeweight$)

選衝突內最大累積權重那筆交易

如果累積權重相同 , 那就隨機選一個

$\text{color}yellow5$ 指向了

$\text{color}blue1$ 和

$\text{color}blue4$

這樣選並沒有讓

$\text{color}redw$ 和

$\text{color}redy$ 都增加確認度 , 所以不用重選

可以看到

$\text{color}redw$ 的確認度是比

$\text{color}redy$ 高的

只要一直持續下去 ,

$\text{color}redw$ 會過確認度的門檻 , 而

$\text{color}redy$ 的確認度將越來越小 (因為

$\text{color}yellow7$ 逐漸變成

$lazytip$)

這樣就達到效果:

衝突交易只能一筆是確認

基金會的確認度算法

文章

算法:

The confirmation confidence of a transaction is computed as follows:

1. Run the tip selection algorithm 100 times.
2. Count how many of those 100 tips approve our transaction, and call it A.
3. The confirmation confidence of our transaction is “A percent”.

In other words, the confidence of a transaction is the percentage of tips which approve it.

放一下與基金會成員討論的一段內容:

proof.K - 上星期二晚上9點13分
If tangle has two tips "a" and "b".
A transaction "c" is referenced by "a"."b" doesn't reference "c".
Run the tip selection algorithm 100 times . If all selects "b" , confirmation confidence of "c" is 0. If all selects "a" , confirmation confidence of "c" is 1. Right?
If yes , consistent result is impossible in every node.

alongal - 上星期二晚上11點51分
@proof.K What your wrote is correct. I didn't understand your last statement

不要懷疑 , 確認度每次查詢的數值都不一樣
而且是 0%~100% 內的整數都有可能

講講確認度是隨機值會有的結果

低機率 , 衝突交易皆確認

這裡假設確認的門檻是

$1$

考慮一個

$DAG$ 如下:

$\text{color}redf$ 與

$\text{color}red32$ 是衝突交易

跑100次tip的選取算法(MCMC) , 看裡面有幾次直接或間接指向要算確認度的交易

這意謂著 , 有可能100次都是

$\text{color}blue11$
那

$\text{color}redf$ 就是確認
或100次都是

$\text{color}blue43$ , 那

$\text{color}red32$ 就是確認的

而這兩種情況機率都不是0

nodes最終一致的機率很大 , 但是在一致前有低機率其他的交易是確認

nodes最終一致的機率很大 , 原因在一筆交易最終的權重增長

當很大機率接任何

$tip$ 都會增加權重 , 也意謂直接或間接指向的

$tips$ 比例是很高的

所以最終一致的機率會很大

可是問題在於 , 由上小節的說明 , 在還沒達到最終一致前

衝突交易內的數筆交易就可能是確認的

大量

$tip$ 指向兩筆衝突交易

這種情況是下列的圖:

$\text{color}redd$ 和

$\text{color}red11$ 是衝突交易

灰色的交易是攻擊者發的

這種情況會讓

$\text{color}redd$ 與

$\text{color}red11$ 都能增加確認度

要避免這種情況 , node不能收直接或間接指向兩筆衝突交易的交易

指向一筆交易的

$tip$ 比例

由上面的

$DAG$ , 考慮

$\text{color}blue21$ 與

$\text{color}blue42$ 這兩筆交易

指向

$\text{color}blue21$ 有

$\text{color}blue13$ ,

$\text{color}blue23$ 和

$\text{color}blue33$

指向

$\text{color}blue42$ 只有

$\text{color}blue33$

依照基金會的確認度算法

$\text{color}blue21$ 會是

$1$ , 因為所有

$tip$ 都有指向

$\text{color}blue21$

$\text{color}blue42$ 不會是

$1$ , 因為只有一個

$tip$ 指向

$\text{color}blue42$

可以看到 , 越多

$tip$ 指向交易 , 越高機率確認度是高的

得到結論

越高的

$tip$ 比例指向交易a , 交易a的確認度更高機率接近

$1$

tags: IOTA