4.2 Timestamps.md

description	image	slug	keywords
While online nodes may leverage FPC to vote on timestamps, nodes that join the network at a later time use an approach based on the approval weight to determine the validity of timestamps.	https://i.imgur.com/rndN8qc.jpg	4.2Timestamps	epoch message timestamp sync approval weight mana consensus transaction

4.2 Timestamps

4.2.1 Motivation

In order to enable snapshotting based on time constraints rather than special messages in the Tangle (e.g. checkpoints), nodes need to share the same perception of time. Specifically, they need to have consensus on the age of messages. This is one of the reasons that messages must contain a field timestamp which represents the creation time of the message and is signed by the issuing node.

Having consensus on the creation time of messages enables not only total ordering but also new applications that require certain guarantees regarding time. Specifically, we use message timestamps to enforce timestamps in transactions, which may also be used in computing the Mana associated to a particular node ID.

In this document, we propose a mechanism to achieve consensus on message timestamps by combining a synchronous and an asynchronous approach. While online nodes may leverage FPC to vote on timestamps, nodes that join the network at a later time use an approach based on the approval weight (described in Section 6.4 - Approval Weight and Finality) to determine the validity of timestamps.

This specification also outlines a tool called "Epochs", which groups messages into different objective periods. This tool may be used for the following purposes:

• finality and approval weight: the activity of certain nodes within an epoch can be recorded, and then the approval weight (i.e. the number of nodes, weighted by consensus, which issued a message referencing a particular message) can then be measured as a percentage of "active consensus mana".
• committee selection: a committee elected as the highest active consensus mana holders can be easily and objectively formed for the DRNG committee.

4.2.2 Preliminaries

4.2.2.1 Requirements

In DLTs, there are many ways to potentially introduce timestamps. Any useful timestamping scheme however must satisfy the following requirements.

1. Nodes must have consensus on the timestamp associated to each message.
2. For every time t, there is a t_1>t such that any new message issued with timestamp t and received by a node after t_1 (measured by its local clock) will be considered too far in the past and will be orphaned.

4.2.2.2 Dependencies

• Opinion Setting
• FPC: used to perform voting on timestamps.
• Approval weight: corrects opinions on timestamps when out of sync.

4.2.3.3 Modules Dependent on Timestamps

• Tip selection: only messages with correct timestamps will be eligible for tip selection.
• Active Consensus Mana in approval weight uses epochs.
• DRNG uses Epochs.
• The Congestion control orders messages by timestamps, and only processes messages whose timestamp is close to the current time.
• The rate control system uses timestamps to compute the correct PoWs.
• The snapshotting uses timestamps to determine which messages to prune from the tangle.

4.2.2.4 Parameters

Name	Type	Description
DLARGE	duration	Gratuitous network delay estimate~ 15 s
W	duration	window ~1 minute. Require W>2DLARGE
DELTA	duration	Maximal difference between a message timestamp and its parents' message timestamp. Require DELTA>W+DLARGE
TW	duration	Maximal difference between message timestamp and transaction timestamp
EPOCHLENGTH	duration	Length of each epoch = 1 hour
SYNCH_THRESHOLD	duration	the max difference between CurrentTime and TangleTime in which we consider our node in sync
TIMESTAMP_CUTOFF	duration	messages with timestamp older than this will be disliked with level 3 knowledge

4.2.2.5 Clock Synchronization

Nodes need to share a reasonably similar perception of time in order to effectively judge the accuracy of timestamps. Therefore, we propose that nodes synchronize their clock on startup and resynchronize periodically every 60min to counter drift of local clocks. Instead of changing a nodes' system clock, we introduce an offset parameter to adjust for differences between network time and local time of a node. Initially, the Network Time Protocol (NTP) (Go implementation) may be used to achieve this task.

We gracefully shut down the node if:

• initial synchronization of time fails
• resynchronization fails for more than maxSyncAttempts times

4.2.3 General Timestamp Rules

Every message contains a timestamp, which is signed by the issuing node. Thus the timestamp itself is objective and immutable. Furthermore, transactions will also contain a timestamp, which will be also signed and thus immutable. We first discuss the rules regarding message timestamps.

In order for a message to be eligible for tip selection, the timestamp of every message in its past cone (both weak and strong) must satisfy certain requirements. These requirements fall into two categories: objective and subjective. The objective criteria only depend on information written directly in the Tangle and are applied immediately upon solidification. Thus all nodes immediately have consensus on the objective criteria. In this section, we will discuss these objective criteria.

The quality of the timestamp is a subjective criterion since it is based on the solidification time of the message. Thus, nodes must use a consensus algorithm, e.g. FPC, to decide which messages should be rejected based on subjective criteria. Specifically, nodes will use FPC to vote on whether or not a timestamp plus W is before the arrival time.

Consensus matters are not discussed in this document: see sections 6.1, 6.2 and 6.3 to discuss how FPC votes on timestamps.

Lastly, for any time t, a node is sure that it has received all the messages with timestamp less than t which will be finalized when

• CurrentTime >= t + TIMESTAMP_CUTOFF = t + W + 2*DLARGE, i.e. wait ~1.5 minutes
• SyncStatus = TRUE Indeed, after TIMESTAMP_CUTOFF = W + 2*DLARGE all messages which arrive will be considered bad with level of knowledge 3: see Section 6.1 - Object of Consensus. If the node is in sync, then it will have received all old messages which will be confirmed.

4.2.3.1 Age of Parents

It is problematic when incoming messages reference extremely old messages. If any new message may reference any message in the Tangle, then a node will need to keep all messages readily available, precluding snapshotting. For this reason, we require that the difference between the timestamp of a message and the timestamp of its parents must be at most DELTA units of time. Additionally, we require that timestamps are monotonic, i.e. parents must have a timestamp smaller than their children's timestamps.

4.2.3.2 Message Timestamp vs Transaction Timestamp

Transactions contain a timestamp that is signed by the user when creating the transaction. It is thus different from the timestamp in the message which is created and signed by the node. We require

transaction.timestamp+TW >= message.timestamp >= transaction.timestamp

where TW defines the maximum allowed difference between both timestamps.

If a node receives a transaction from a user with an invalid timestamp it does not create a message but discards the transaction with a corresponding error message to the user. To prevent a user's local clock differences causing issues the node should offer an API endpoint to retrieve its SyncedTime according to the network time.

4.2.3.3 Reattachments

Reattachments of a transaction are possible during the time window TW. Specifically, a transaction may be reattached in a new message as long as the condition message.timestamp-TW >= transaction.timestamp is fulfilled. If for some reason a transaction is not picked up (even after reattachment) and thus being orphaned, the user needs to create a new transaction with a current timestamp.

4.2.3.4 Age of UTXO

Inputs to a transaction (unspent outputs) inherit their spent time from the transaction timestamp. Similarly, unspent outputs inherit their creation time from the transaction timestamp as well. For a transaction to be considered valid we require

transaction.timestamp >= inputs.timestamp

In other words, all inputs to a transaction need to have a smaller or equal timestamp than the transaction. In turn, all created unspent outputs will have a greater or equal timestamp than all inputs.

4.2.4 Consensus on timestamps

The accuracy of the timestamps will be enforced through FPC voting. Specifically, FPC will allow nodes to come to consensus on whether or not timestamp+W is greater than the arrival time: see Section 6.2 - Opinion Setting. Messages which are deemed to fail this criterion will be rejected. Messages whose entire past cone is both valid, and satisfies this criterion, will be flagged as eligible and can be referenced messages selected by the Tip Selection Algorithm: see Section 4.3 - Tip Selection Algorithm.

4.2.4.1 Not in Sync

Any node not in sync will receive messages much later than the rest of the network. Thus, all messages will appear to have inaccurate timestamps and will be wrongfully rejected by the algorithms in Section 6.2 - Opinion Setting. Thus nodes will not actively participate in any voting until their status is in sync, see Section 4.2.5.

In general, a node that just completed the syncing phase must check, for each message, how much mana is in its future cone and set the opinion accordingly.

More specifically:

1. Run the solidification up to being in sync (by following beacons)
2. Derive local markers
3. Decide eligibility for every message (5-10% mana min threshold)

Clearly this synchronization procedure may only work to make an apparently bad timestamp reset to be a good timestamp. For example, if a node receives a message one day later than the rest of the network, the node will initially reject the timestamp. However, the resync mechanism will recognize the message is correct because it is buried under an entire day's worth of messages.

What about the converse situation? Being out of sync will only delay the arrival of a message. If a node receives a message with a timestamp satisfying timestamp+W>arrivalTime, this condition would also be satisfied for all nodes which received the message earlier. Thus, if a node is out of sync and is receiving messages later than everyone else, if this node likes a timestamp, all other notes will have already liked it. Therefore, nodes will not like timestamps which were previously rejected by most of the network.

4.2.4.2 Future Timestamps

Note that the resync mechanism only works because we only dislike a message if it is too old. If we disliked messages whose timestamps were in the future, then it is possible that some nodes would like it, and others disliked it. Suppose for example at 11:00:00 a node issues a message X with timestamp 12:00:00, and that then all nodes rejected this timestamp for being too far in the future. Now suppose at 12:00:00 a new node N joins the network at receives X. According to node N, the timestamp of X is accurate, and will accept it, while other nodes will reject it. The resynchronization mechanism fails in this case.

To protect against messages with a timestamp that is issued in the future, the congestion control algorithm does not schedule the message until the timestamp is less than or equal to CurrentTime. Thus messages from the future will not be added to the Tangle until the appropriate time. If an attacker sends too many future messages, these messages may overload the scheduler's queues. However, this is a standard type of attack that the congestion control algorithm is prepared to handle.

4.2.5 Tangle Time

4.2.5.1 Motivation

For a variety of reasons, a node needs to be able to determine if it is in sync with the rest of the network, including the following:

• to signal to clients that its perception is healthy,
• to know when to issue messages (nodes out of sync should not issue messages, lest they are added to the wrong part of the Tangle),
• to schedule messages at the correct rate: out of sync nodes should schedule faster in order to catch up with the network,
• and to optimize FPC: nodes should not query while syncing, but instead rely on the approval weight.

4.2.5.2 Tangle Time

Every DLT is a clock, or more specifically a network of synchronized clocks. This clock has a natural correspondence with "real time". If the DLT clock differs significantly from local time, then the we can conclude that our DLT clock is off from all the other clocks, and thus the node is out of sync.

For IOTA 2.0, we make precise the meaning of the DLT clock with what we dub "Tangle time".

FUNCTION Time = TangleTime
 RETURN largest timestamp of all grade 3 final messages

Thus Tangle time is the last timestamp in a message which was been confirmed. Tangle time cannot be attacked without controlling enough mana to accept incorrect timestamps, making it a reliable, attack-resistant quantity.

Typically speaking, CurrentTime - TangleTime is, on average, the approximate confirmation time of messages. Thus, if this difference is too far off, then we can conclude that we do not know which messages are confirmed and thus we are out of sync. In this spirit, we are able to define the following two functions.

FUNCTION Time = SyncAmount
RETURN CurrentTime - TangleTime

FUNCTION bool = SyncStatus
IF SyncAmount <= SYNCH_THRESHOLD
    RETURN TRUE
ELSE
    RETURN FALSE

4.2.6 Epochs

Epochs are universal time intervals that group messages in the Tangle based on their timestamps.

• An epoch is identified by its unique epoch index. Epoch indices are strictly increasing with respect to time.
• Every time interval EPOCHLENGTH, a new epoch is started and the previous ends.
• A message M or a transaction belongs to an Epoch X, if its timestamp falls into the time window of Epoch X such that T(M)∈ [t_X-1, t_X), where
  • T(M) is the timestamp of message M,
  • t_x-1 is the end of the previous epoch,
  • and t_x is the end of Epoch X.
• A transaction might not be in the same epoch as the message containing it.
• The start of the network corresponds to t₁, that is the end of Epoch 1.
• Epoch 0 and Epoch 1 are special epochs, since they only contain the genesis message(s), and their content is defined before starting the network. These two epochs might be used to initialize the network and active consensus mana states to a desired values.
• For every network, the end of Epoch 0 is defined as an arbitrary point in time, similarly to how Unix epoch time is defined as 00:00:00 UTC on 1 January 1970.
• Epoch interval EPOCHLENGTH cannot be chosen arbitrarily: it must be much larger than DELTA. Furthermore, short epochs can potentially cause make certain calculations involving the approval wait more complicated.

Figure 1 gives a brief overview of how the Tangle is divided into epochs:

Epoch 0 contains the genesis message(s), that hold the genesis output(s). By allowing multiple outputs to exist before the start of the network, a desired initial state for the network can be set. Epoch 2 is the first epoch after the start of the network, when nodes may start issuing messages. Note, that a message can be valid with one strong parent only.

Upon processing a message and verifying its timestamp as described in Opinion Setting Specification, the message is solidified and can be added to the epoch. Epoch 2 ends at t₂, but it can happen that a message is issued just before t₂, therefore it reaches most nodes and gets solidified during Epoch 3. In this case, the node can still determine the correct epoch the message belongs to due to the consensus on the message timestamp. This also means, that finalizing an epoch (declaring that no more messages can be added to it) is delayed after the end of the epoch by at least W time.

4.2.6 Limitations

• When not in sync, a different behavior is required which complicates the protocol.
• Using NTP as clock synchronization mechanism as proposed is a single point of failure. It can only be considered as an initial implementation into GoShimmer and needs to be replaced by a decentralized alternative.