Timestamping

[ovanwijk]

I just finished watching the video on coordicide and specifically the part about timestamping. As some might know I have been onto getting timestamping in the tangle for a while now and I would really like to see a definitive answer on why the following is not preferred over voting on time.

For simplicity, I use a message (/transaction) M with trunk T and branch B that could be either a bundle or variable-sized. The message has a timestamp (ts) that is independent of the payload. Just like trunk and branch, it is an integral part of the tangle structure.

A timestamp is in milliseconds and represents wall-time. An imperfect representation of global ordering. Something, considering we use the tangle, we all agree on simply doesn’t exist. None-the-less still a very useful measure for all sorts of mechanisms.

Add to the tangle as a rule (Make it a vector/logical/Lamport clock):

M.ts >= T.ts && M.ts >= B.ts

This simple rule always needs to be valid, just like your trunk and branch needs to be existing. No upper or lower bound on this validation rule.

Creating a transaction:

We have two main actors: The Node & The Client, they each have their own clock.

The client calls the node for tip selection. Tip selection is the standard URTS with an upper bound of the node’s clock. Meaning no transactions with a timestamp higher then the node’s clock will be selected by this particular node. The node returns a trunk and branch and it’s own current timestamp.

The client checks if the timestamp is within ± 30(N) seconds. If not the client libs will throw an error. The local modifier is on the client.

The message that the client creates contains the timestamp obtained together with tip selection. While doing proof of work this timestamp is increased as time passes.

When the proof of work is finished, send the message to the node and in turn checks if the message timestamp is ± 30(N) seconds. It then stores and broadcasts it.

This very simple mechanism creates a vote per message on what each machine(be it client or node) on the planet thinks what the current time is. Relative to each trunk and branch we already know the ordering is correct and that the flow of time is in one direction. But now each message votes it’s perceived global order of events relative to the rest of the messages.

My main question is, what are the problems with this approach vs voting every 30 minutes?

It seems so simple and timestamps become much more accurate as TPS goes up.

I am aware of and it’s deterministic described method could be used for transactions to calculate it’s confidence.:
https://assets.ctfassets.net/r1dr6vzfxhev/4iQXZ7bZGwSsE26SkqOQao/2ebf046578dabec5c1d3c48ed442c86f/On_timestamps_in_the_Tangle.pdf

And just now it seems a similar idea was proposed:

Clocks and DLTs

Although we are all busy with coordicide, there is always time for a bit of theory. The ideas here were developed during many good chats over beer with other Iota researchers. What is a clock A tempo is a state machine whose state are enumerated by \mathbb{N} and state i can only transition to state i+1 (note, this is my own terminology and not a standard definition). Each state change is effectively “beat” or a “tick”. For example, consider a watch counting seconds since a certain point i…

[william.sanders]

The reason why it doesnt work is because the timestamps are easily faked. In order for a timestamping scheme to be useful, it needs the following property: for any number t, there exists a time T (which is predictable) such that no message entering ledger after time T will have timestamp t.

Without this property, timestamps cannot be used for snapshotting or any “proof of existence” application. Consider snapshotting: I can only snapshot a message if Ia m sure that I can treat any new messages referencing it as an unsolidifiable message, i.e. as an invalid message. Similarly, you can use voted upon timestamps to prove that information existed before a certain point.

In the scheme above, I can create a message that references the genesis with any timestamp I choose.

[ovanwijk]

While your first statement is true I would argue it is independent of snapshotting or proof of existence.

The validity of the timestamp comes from it’s surrounding messages/context. The rule itself doesn’;t create a valid timestamp. The entire network actively publishing messages does. The accumulated weight of all future message and deviation analysis (most messages are N milliseconds apart and selected messages reference a message that is weeks or even minutes old is not hard to detect) should suffice to detect if a timestamp was in-line with all other messages.

You essentially have to build up a side tangle of timestamps from genesis up to now (at 100tps, this means 100 TPS in serie(!!) to not get detected by a very simple deviation analysis) and get included into the live ledger to make this an attack. Side tangles, in general, is a problem independent of timestamps.

As for snapshots, snapshots are a local modification to a local database and each node has it’s own clock it trusts. If it also issues messages it can easily use those for it’s own for snapshots. If not it could just issue a message and use that for snapshotting in the future. Or pick a node that issues messages with a trustworthy interval and use those messages as basis for snapshotting. Or even on a voted message as is now proposed. But even when using voting on a transaction that everyone uses for snapshotting, it doesn’t invalidate the idea that you can still have high confidence timestamp analysis on a per transaction basis by implementing those simple rules.

[william.sanders]

If the timestamp is easily faked, then it has limited use, although I could imagine that your timestamps are useful for some sort of application.

In the current coordicide proposal, we dont need to worry about side chains because the timestamps are enforced, and we have the below max depth rule.

Also, for snapshotting, you can prove using the arguments I give that workable shapshotting algorithm is actually equivalent to a having a timestamping scheme with the property I gave in the last post.

After thinking a bit, I realized that your timestamps are similar to a combinatorial invariant (quasi) rank. The rank of a message is the 1+max(rank of trunk, rank of branch). Youre timestamps effectively assign times to various ranks, but they are more or less the same thing.

[ovanwijk]

I think we have a different definition of ‘easily’ faked.
To me easily faked means that, whatever is checking/observing the timestamp, is easily convinced that whatever timestamp you are claiming to be on the message was indeed within that time-frame given the context it has in the tangle. This considering an attacker does not have the majority of mana, hashpower or voting power.

Referencing genesis with any timestamp after genesis without any further messages (or even a single long tail of messages) should be easily detectable. Therefore I simply don’t consider this a ‘good/easy fake’.

If you have an upper (now) and lower bound (30 minutes ago) on the default tip selection algo I see very little room to effectively fake the timestamp. If it is too far in the past it won’t be referenced and if it is too far in the future it will only be referenced once it’s time has come. It becomes an endless stream of votes on wall-time. By just observing the transactions in the tangle you will get a pretty good estimate at what the nodes consider ‘now’ without the need to trust a few.

If someone wants to calculate a correctness probability it is up to the observer to spend effort analyzing it. Mostly, a quick analysis would suffice. But for large legal issues, you could just as easily analyze very large chunks of the tangle just to be more certain about a timestamp.

Having a trusted timestamp by an oracle or smart contract/ quorum could easily be a solution. And honestly, I think it is very useful to have. But by soley relying on network wide voting on a single instance of time is not the way I think. The base concept of the tangle is of course that there is no global ‘now’.

When having such a mechanism in place you can build in many more rules that could allow for much quicker adjustments in rate control limits. Or when walking the tangle it becomes much more efficient to perform depth-first search and detect when to switch to breath first. (I already do this with AION but is now just unreliable, even though it mostly works because I locally detect and tag transactions as oke-ish timestamps.).

[william.sanders]

I think we are agreed that your timestamps can be faked by making a side tangle. Thus, in order to check if a timestamp is valid, what you have to do is check if the transaction is in a side tangle. How do you do this exactly? We developed some methods in our parasite chain detection paper, but the tests are not ironclad, and I imagine the same is true for any side tangle detection. So essentially, these timestamps would be somewhat reliable, but a sufficiently motivated attacker can fake them.

Note if you want to prevent side chains from forming on a protocol level, then you need strictly enforced timestamps. Indeed, preventing a sidechains is equivalent to saying “any new message which approves these messages is invalid.” But this is a temporal statement. For a message M, the first moment where a node will not accept incoming messages referencing M is effectively a timestamp. Moreover, coming to consensus on such a time is equivalent to consensus on timestamp.