# Tip Selection The TSA is one of the key algorithms for the Tangle as it has a huge impact on the health and performance of the entire system. ## Status quo - IRI does a random walk ($\alpha=0$) starting from one of the latest MS (e.g. depth=4). - There is no difference between IRI tip selection and Compass milestone selection. - If the "depth" of the entry point is too large (too many new transactions) the RW will take very long, around 100-200TPS. - If the TSA does not return a tip within the given time limit (60s), the new MS will directly approve the last MS. (This effectively renders the network useless in high TPS scenarios.) ## Objectives - Let the Tangle grow in a healthy direction, even under attacks - Computationally efficient, even in high TPS scenarios - `belowMaxDepth`: Do not confirm tips that connect too far in the past #### Good to have (for nodes) - Nash-Equilibrium: Changing its own TSA makes the outcome worse - Incentives to select a tip that helps the network - Punish "lazy" tips :::warning There is no need to consider security or finality since we have the Coordinator. ::: ## Milestone selection The objectives are different: - Coordinator is a special node run by the IF. - The Coordinator has more computational power than the average node. - The MS does not make the Tangle grow; only indirectly. - Selection can be enforced. Maximizing (honest) CTPS is the main and only goal! ### Attack vectors #### Parasite Chain Creating a structure so that the confirmed transactions or honest confirmed transactions are low. ![](https://i.imgur.com/5VHkUCP.png) #### Blowball ![](https://i.imgur.com/JNhwetu.png) #### Splitting Dangerous, since many honest transactions can be invalidated with just two conflicts. ![](https://i.imgur.com/ePr5Gdt.png) ### Solutions #### Splitting - Keep conflicts in the Tangle. [Conflict White Flag](https://iota.cafe/t/conflict-white-flag-mitigate-conflict-spamming-by-ignoring-conflicts/233) - Guarantees 100% protection against splitting attack. - Very easy to implement, no network dependent parameters. ##### To decide - How a transactions ordered? Postorder depth first traversal (trunk, branch, root). > [name=Wolfgang Welz] Seems like a very good solution. - Are temporary overdrafts withing one milestone allowed? > [name=Wolfgang Welz] Temporary overdrafts get even more complicated with "conflict depth". They are currently not supported, so we should not introduce them. - Conflicts min depth: $-\infty$ works, but there is no local validity; 1 could lead to race conditions > [name=Wolfgang Welz] No problem computationally (without overdrafts), why do we want this? Are there any usecases or just for the sake of "clean Tangle"? > Discarding (not ignoring) conflicts causes splits, if the MS only picks up subsets of before valid conflicting transactions --> Don't discard only ignore! ![](https://i.imgur.com/NCbmCZU.png) #### Parasite Chain - Choosing secret checkpoints against hidden structures. - Issuing secret checkpoint transactions against self referencing structures. - Future cone marker makes filtering $O(1)$. ##### To decide - Possibility for the Coordinator to issue secret transactions? If yes, do it! - Is it enough to only select/issue one CP? - Selecting just one CP drastically simplifies the algorithm, updating information on-the-fly is more complex (e.g. marker). - Danger of picking a "local maximum" is OK when a low-variance tip selection is used. ![](https://i.imgur.com/x8QjTgP.png) #### Blowball - Any reasonable tips selection should work. - Heaviest branch / largest co-weight offers the strongest protection. > [name=Wolfgang Welz] Heaviest branch seems to be very good for the MS. Could be computationally expensive especially for very high TPS. But there are a few solutions: a) use bitsets b) issue more CPs c) use heuristic ![](https://i.imgur.com/CCa69IF.png) ## Tip selection - Keep NE/incentives in mind. - Should be "closer" to URTS. - Low orphanage rate. - Splitting does not need to be considered. - Validity of tx can be checked upon arrival: - Store MS-index (latest referenced MS) in every transaction - Check whether that tx can be applied to that ledger state - No need for a walk - Attack vectors: - Lazy tips - Blowball ### Ideas - Almost URTS: URTS but penalizing txs confirming too old transactions or transactions with too many children - Heaviest Branch heuristic - Combining heaviest branch with URTS - ...
Last changed by  
 
Wolfgang Welz
173

Read more

Mnemonic Seed RFC

Feature name: mnemonic-seed Start date: 2020-03-11 RFC PR: iotaledger/protocol-rfcs#0010 Summary The IOTA protocol uses a 81-tryte seed to derive all the private keys for one account. This RFC describes a method to represent that seed as a mnemonic sentence - a group of easily comprehensible words. Motivation The used seed is a 384-bit or 243-trit random string. There are several ways to represent this in a human-readable form, but a mnemonic sentence is far superior to raw binary or ternary strings. These sentences can be written down on paper much more naturally or even be spoken over a phone. Furthermore, having raw strings tempts the user to copy and paste the seed. This practice opens new attack vectors such as theft or manipulation of the string in the clipboard.

6/26/2020
Ledger State Calculation

The ledger is modeled using unspent transaction output (UTXO). It consists of a set of transactions, where each transaction has inputs and outputs and consumes the outputs of a previous transaction with its inputs. The unspent transaction outputs, i.e. the outputs that are never consumed by a transaction, represent the actual ownership of the assets. The UTXO model can be defined more formally as follows: UTXO Graph A UTXO graph is a directed hypergraph $H = (V,T)$, where the vertices $v \in V$ are also called transaction outputs and the hyperarcs $t=(I,O) \in T$ with $I,O \subset V$, are called transactions. The tail $I$ of transaction $t$ is also called inputs of $t$, while the head $O$ is called outputs. The hypergraph $H$ must further have the following properties: There exists one designated vertex $g \in V$, called genesis, and no transactions have $g$ as an output, i.e. $deg^{in}(g) = |{T=(X,Y) \in A \mid g \in Y}| = 0$. For each vertex $v \in V \setminus {g}$ there exists exactly one transaction with $v$ as an output, i.e. $deg^{in}(v) = 1$. We call a UTXO graph $H = (V,T)$ conflict free, if for every $v \in V$ there exists at most one transaction $t = (I,O)$ with $v\in I$, i.e. $deg^{out}(v) \leq 1$.

5/14/2020
GoShimmer Ledger State

Logic overview: Value message attachment/storing: Value Tangle attach to message Tangle solid event UTXO attach to Value object solid event From the solid payload we store the transaction inside the payload via its ID if new we link the inputs of the tx to the tx ID

5/8/2020
Bundle Mining Review

2/11/2020
Read more from Wolfgang Welz
Published on HackMD