4.1 The Tangle.md

4.1 The Tangle

This specification describes the data structure used in the IOTA protocol, and introduces its main terminology.

4.1.1 Description

The Tangle represents a growing partially-ordered set of messages, linked with each other through cryptographic primitives, and replicated to all nodes in the peer-to-peer network. The Tangle enables the possibility to store data and to keep a ledger, the latter being based on UTXO-DAG formed by transactions contained in messages.

In mathematical terms, the Tangle is a Directed Acyclic (multi)Graph with messages as vertices and directed edges as references to existing messages. Directed edges are labelled: $0$ represents direct references flagged as weak, and $1$ represents direct references flagged as strong (see Section approval switch). Messages are linked with each other through cryptographic hashes. The acyclicity condition means that there is no directed cycle composed of weak or strong edges.

4.1.2 Definitions

In this section we provide some useful terminology which is useful to understand the basic elements of the protocol.

4.1.2.1 Approval switch

Here we present the set of rules, called approval switch, which allow nodes to alternatively approve single messages or the entire past cone of a message.

• Parent: The protocol requires that each message contains a field parents in order to guarantee cryptographic references among messages in the Tangle. These references can be of two types, strong and weak, and are defined by the field parents type. Intuitively, we say that $y$ is a strong (resp. weak) parent of a message $x$ if $x$ has a directed strong (resp. weak) edge to $y$. Each message has a possible number of parents from 2 to 8 with repetitions (with 2 as a default value), where at least one is a strong parent. More information about parents can be found in Section 2.2 - Message layout.

• Approvers: A message $x$ directly approves $y$ if $y$ is a parent of $x$. Moreover, $x$ is a strong (resp. weak) approver of $y$ if $y$ is a strong (resp. weak) parent of $x$. More generally, we say that a message $x$ strongly approves $y$ if there is a directed path of strong approvals from $x$ to $y$, and $x$ weakly approves $y$ if there is a directed path of approvals of any type from $x$ to $y$.

• Past cone: We say that the (strong) past cone of $x$ is the set of all messages strongly approved by $x$, and the weak past cone of $x$ is the set of all messages weakly or strongly approved by $x$.

• Future cone: We define the future cone of a message $x$ as the set of messages that weakly or strongly approve $x$. Please note that, unlike its past cone, the future cone of a message changes over time.

• Genesis: The genesis is the message that creates the entire token supply. Note that this implies that no other tokens will ever be created or, equivalently, no mining occurs. This message has no outgoing edges and is in the weak past cone of every other message.

In short, strong approvals are equivalent to the approvals in the legacy IOTA: if $x$ strongly approves $y$, it approves also $y$'s past cone. Moreover, weak approvals emulate the White Flag approach from Chrysalis: approving a message does not necessarily approve its past cone. This feature allows, for instance, two conflicting messages to be part of the Tangle without creating unmergeable branches.

4.1.2.2 Validity

This subsection introduces the definitions of validity for transactions and messages.

• (Transaction) Validity: A transaction is valid if it passes the syntactical filter and its references are valid (see Section 2.3 - Payloads Layout for information):

  • It is syntactically correct.
  • Unblock conditions are met (see Section 5.1 - UTXO for further information).
  • Balances are zero, i.e., the sum of the inputs in the transaction's payload is equal to the sum of the outputs spent.
  • No conflicts in the past cone on the UTXO DAG (two transactions conflict if they consume the same UTXO output).

• (Message) Individual Validity: A message is considered individually valid if it passes all the objective filters, i.e. the ones included in the Message Parser (see Section 2.4 - Data Flow):

  • It is syntactically correct.
  • Its signature is valid.
  • Its Proof of Work is correct.

• (Message) Weak Validity: A message is weakly valid if:

  • Its Individually Valid.
  • Its parents are weakly valid.
  • Its transaction is valid.
  • It passes the Parent Age Check.

• (Message) Strong Validity: A message is strongly valid if:

  • It is weakly valid.
  • Its strong parents do not have a conflicting past.
  • Its strong parents are strongly valid.

4.1.2.3 Branches

In the IOTA protocol, multiple version of the ledger state can temporarily coexist. These multiple versions of the ledger state are called branches. As soon as conflicts are detected, new branches are generated where the outputs created by conflicting transactions and those created by transactions that spend these outputs are tracked. If all past conflicts are resolved and no new conflicts are detected, then only one branch will exist. More rigorously, we can refer to a branch as a non-conflicting collection of past cones of outputs in the UTXO DAG. Additional information, as well as the distinction between conflict and aggregated branches, is given in Section 5.2 - Ledger state.

4.1.2.2 Solidification

Due to the asynchronicity of the network, we may receive messages for which their past cone has missing elements. We refer to these messages as unsolid messages. It is not possible neither to approve nor to gossip unsolid messages. The actions required to obtain such missing messages is called solidification procedure, and are described in detail in Section 4.4 - Solidification.

4.1.3 Example

In the figure below it is shown an example of the Tangle (strong edges are with a continuous line, weak edges are with a dotted line). Message $D$ contains a transaction that has been rejected. Thus, in the legacy IOTA implementation, its future cone would be orphaned due to the monotonicity rule. In particular, both messages $E$ (data) and $F$ (transaction) directly reference $D$. In IOTA 2.0, the introduction of the approval switch allows that these messages can be picked up via a weak approval, as messages $G$ and $H$ exemplify.