Tip Selection Algorithm
Selecting blocks to be referenced by newly issued blocks is a critical component of the consensus protocol.
Suppose a node adopts the slot commitment chain and maintains the tip poolCollection of blocks selected by the node for potential selection as a parent. , which consists of eligible tips. It is impossible to reference all existing blocks in the tip pool as it would lead to a large block size. Instead, the number of references for each reference type is limited by
blockMaxParent for normal blocks and by
blockTypeValidatorMaxParent for validation blocksValidation Blocks is a special type of blocks that are issued by members of the Validator Committee. These block allows to reach consensus in the network..
Tip Selection Rules
When a node issues a new block (e.g., committee members must issue their blocks every
frequencyValidationBlock seconds), it follows these rules to select the list of references to be included in the new block:
1. Strong Parents
The node selects uniformly at random at most
blockTypeValidatorMaxParent for validation blocks) unique tips from the tip pool as strong parents.
2. Shallow-like References
blockTypeValidatorMaxParent) shallow-like references are not sufficient to align the branch, the strong parent is removed from the list of references and moved to the weak tip pool , which is initialized as an empty set before running the tip selectionThe process of selecting previous transactions to reference in a new transaction. These references allow a transaction to tie into the existing data structure. IOTA and Shimmer only enforce that a transaction approves up to eight other transactions, the tip selection strategy is left to the user (with a suitable default provided by Shimmer). algorithm.
3. Weak References
The node selects uniformly at random (at most)
blockTypeValidatorMaxParent) unique tips from the weak tip pool .
Before adding a weak tip to the list of references, the node checks if the transaction included in the weak tip conflicts with the preferred reality. If the transaction is not conflicting, the weak tip is added to the list of references.
To guarantee consistency for generated slot commitments, nodes need to only keep tips likely to be approved and accepted by the committee in the tip pool. For instance, a tip is bad if it approves an unaccepted block that is issued in an already committed slot.
Accepted Tangle Time (ATT)
A node's accepted Tangle time (ATT) is the largest timestamp across all accepted blocks (in the local perception of the node).
A block is called an eligible tip for a node that adopts slot commitment chain if the following conditions hold:
- the block is not yet referenced.
- the slot commitment included to is consistent with , i.e., it is equal to for some .
- Any unaccepted block in the past cone of is scheduled to gossip and the difference between ATT and the timestamp is at most
livenessThreshold. The value
livenessThresholdis set to