1.5.0 TipSelection Algorithm
===

[TipSelection Algorithm Documentation](https://hackmd.io/s/Skow-8Hb7)

[IRI 1.5.0 Tip 選擇演算法](https://hackmd.io/s/BJDli7K-m)

# 選出兩個 tip 的過程

這次的更新

實際上官方的模擬器就有實作了

[iotavisualization (one-by-one)](https://github.com/iotaledger/iotavisualization/tree/one-by-one)

首先先從 Tangle 取出當下的 subgraph (起點從 milestone 開始)


藍色部份是　subgraph (有標示累積權重假設是 milestone)

接下來算出 subgraph 內每筆交易的累積權重

其中一些交易的累積權重:


接下來就如模擬器中的動畫 , 用權重影響的 random walk 選出兩個 tip

## 與模擬器的差異

計算累積權重 , 模擬器是算全部有指向的交易

IRI 有個上限 , 目前是寫死最多 [5000](https://github.com/iotaledger/iri/blob/dev/src/main/java/com/iota/iri/service/tipselection/impl/CumulativeWeightCalculator.java#L31)

如果起點的 milestone 深度夠深 , 使的附近的交易計算累積權重時 , 都超出 5000 的數目

那會變成從起點開始的 random walk , 移動到下一筆交易的機率是均勻的分佈

而理想應該是移動到累積權重大的交易機率越大

# 檢查選出的兩個 tip

個人以為 , 這才是這次 tip selection 更新最重要的部份

英文:
:::success
1. It is not solid and we cannot reconstruct its state, since a portion of the Tangle this transaction references is unknown.
2. It references a transaction too far in the past, namely beyond latestSolidMilestone - maxDepth. Please refer to section 1.1 for further explanation.
3. The ledger state computed from it is not consistent, such as trying to spend missing funds or double-spending.
4. The validator maintains a list of transactions that have been checked for validity. Every time a new transaction gets validated, it is also checked against these.
:::
中文:
:::success
1. 它不是 solid 而且我們無法重新架構出它的狀態，因為在一部份的 Tangle 中此交易的參考點(references)會是未知的。
2. 它驗證的交易太久了，遠超出 latestSolidMilestone - maxDepth 的範圍。這部分就回到章節 1.1 的討論。
3. 計算出的帳本狀態並不一致，像是沒有資金或是出現雙花。
4. 驗證者會對照一串交易列表來檢查完整性。每當有新的交易驗證實，它同時也會對照此列表來檢查。
:::

第一點指的是交易的 trunk 或 branch
在 Tangle 不存在

如果選到這樣的 tip , 會重選

第二點就是避免選 lazy tip , 很久之前的 lazy tip 選到的機率是 0

第三點重要 , trunk 與 branch 所指向的交易

這些交易要有下列性質:
* 所有 address 餘額都沒有負數
* 所有 address 餘額相加要等於最初的發行量

trunk 與 branch 要滿足這樣的性質 , 這兩個性質跟共識演算法有關

第四點是第三點的內容 , 不多做說明

## getTips

IRI 新增了檢查 trunk 與 branch 的函數後

可以用在 getTips 上

這樣會讓 iota-swarm-node 用 getTips 拿到正常的 tip , 不會是 milestone 不會驗證的 tip

# IRI 1.5.0 更新後 mainnet 的情況

來看幾張圖


會發現 CTPS 比之前的情況好了

而且方差的現象也有改進

###### tags: `IOTA`