AION: Timewarps
A simple concept that got complicated
This article is, not surprisingly, about timewarps! Part of what is explained is already implemented and some parts of it are still work in progress. This article serves to document my ideas and general design but also to let the broader iota community become familiar with the concepts. And last but not least: so others can poke holes in.
One of the core concepts of my selective permanode project for IOTA are timewarps. The concept is very simple: one of the tips of a transaction points to a much older transaction, essentially ‘skipping’ large parts of the tangle. If confirmed it takes part in tip selection and therefore becomes part of the tangle.
Why do this? Optimization of storage and pathfinding. An optimization that is, unfortunately, a requirement for AION to work.
The base concept of timewarps is very simple. But it becomes tricky pretty quickly if you don’t want to flood the tangle with a large number of transactions constantly and want to reuse an existing one. If my node would be the only one issuing these timewarps and I am the only one using it then well… easy. However what if a 1000 people want to run AION nodes? Are all of them going to issue timewarp transactions? All the time? That would mean a lot of extra stress on the network and we don't want that if it can be avoided.
However, the tangle is an open data-structure so anyone can anything. Now, what if someone wants to hijack your timewarp? What is someone stopping from issuing timewarp transactions referencing your timewarp? Which one is actually correct or honest? Both? One? And when do I even decide? Could someone do this all the time and point to a useless part of the tangle? Making AION’s timewarping essentially useless?
How do we even convey these timewarps? How are they defined and how strong can we trust this definition? Timestamps are mostly unreliable in the tangle. The closest thing we have is trusting the coordinator’s timestamps but we also want AION to work in a post coordinator network.
Here we see a very simple concept turn in a bit more complex problem. However…. and I really want to stress this, we are in the world of crypto and discussions about security are usually very opinionated. I want to point out that AION does not work with funds a thus concepts of rigorous and very strong consensus are not that relevant here. Everything described is just to ‘be nice’ for the tangle and prevent the standard use of AION to flood the network with transactions.
Given the above-described complexities we roughly have six problems to solve:
- How do we detect a timewarp?
- How do we detect it stopped or is faulty?
- How do we know the same person/actor is issuing timewarp transactions continuously?
- How many active timewarps at any time are needed?
- If there are too few active timewarps, how do we know which AION node needs to start issuing a new timewarp?
- How do we prevent dishonest or accidentally faulty transactions from influencing/gaming this leadership election process too much?
Timewarp autonomy.
To start off it is important to know what timewarps exactly are in AION, what is in the transactions and why. Some of these concepts have interdependencies to the other stated problems and will be explained further down the article.
“A timewarp is a set of signed transactions that connect distant parts of the tangle with the goal of fast graph traversal, a tangle index.”
In order to achieve this, I had to construct a unique WOTS based signature scheme that fits all into a single standard transaction. I am building a storage reduction system, so fewer transactions are better.
For the key generation, the signature scheme uses the normal address generation from the IOTA lib. So Seed+Index with security one, because we only want to use a single transaction.
Normally the IOTA signature scheme signs the bundle essence hash. But for timewarp signing, we construct this essence hash a bit differently. Let's take a look at the following diagram to make it more clear.
The first message XXX is unique in the timewarp set. Unique because it is used to kickstart the timewarp and it is used later for the leadership election process. Note that this transaction is not signed yet!
The Address A of transaction XXX is the public address of seed+index0+security1. The tag of the transaction ends with TW. Note that all timewarp transaction tags will end with TW. This as an easy pre-filter for processing, the first transaction is no different.
The following transactions are a bit more complicated but also much more interesting! Transaction YYY, is created roughly 90 seconds after the first XXX transaction. 90 seconds was picked from experimenting with timewarps and this has the highest chance of being included by milestones, is subject to change. This transaction we need to sign and we do that with the private key of transaction XXX, so address A. What we sign is a normalized hash of and altered essence. Where normal transactions sign with address+timestap+obsoleteIag+value+current&lastindex. Timewarp signatures use Address + TrunkTX + BranchTX + tag . Where normally the obsoleteTag is used for bundle normalization, timewarp transactions use the first 11 trytes of the tag field to achieve normalization instead of the obsoleteTag. Then for the rest, we include all other relevant information for timewarps in the tag field.
Index: every timewarp transaction must up its index by 1 each new issuance. With 5 trytes we can fit enough timewarps that can last for 40 years.
Timewarp ID: That is the first 9 trytes of the first timewarp transaction (XXX). This ID will be the same across all timewarp transactions and to be a valid timewarp this is not allowed to change.
All in all, this gives timewarps an identity similar to a MAM stream but only works backward. Each new transaction observed must be detected as a timewarp by itself.
Timewarp detection
Now we know how timewarp transactions are created let's have a look at how they are detected.
AION uses the ZMQ interface of IRI to create an in-memory representation of the tangle by listening to the tx_trytes topic. When receiving transactions it will tag them internally having either a ‘sane’ timestamp or not. This simply means that the transaction received through ZMQ is within (configurable) ~15 seconds of the time of the machine. This sanity is important to prevent following up faulty timewarps. That means sanity can only be tagged if transactions are observed live, therefore AION takes some time to actually ‘warm up’ when started.
When the sn topic confirms transactions AION will start detecting timewarps on the confirmed transactions. For each incoming transaction:
Detecting how it stopped
AION keeps a rolling average of the timestamp differences between timewarp transactions. If within 1.5 times the rolling average there is no timewarp transaction it is considered stopped. Pretty simple and straight forward. If there are below 5 (or 3 or X, threshold undecided yet) timewarps existing, something more interesting will happen.
Leadership election
We now know how timewarps are created and how they are detected. But to play nice with the tangle and not create a large number of extra transactions we need to somehow communicate between the nodes, unknown how many of them are there! Luckily the tangle is also a data transfer mechanism!
As some might know is that I am a big fan of deterministic interpretation of the tangle by its relevant observers. In this case: AION nodes. The hard part is synchronizing -when- to make a decision. I have some idea’s on how to do this in a similar deterministic approach on potential incomplete data but for now, AION will use the coordinator to synchronize the moment for decisions, for now at least.
Consistent hashing
For the sake of argument, we set the minimum amount of timewarps to 5, just like the 90 seconds this is subject to change. This means we have 5 timewarp slots to fill. To determine the slots we use a so-called consistent hash ring (See image below). The hash ring uses the Timewarp ID(first 9 trytes of the first transaction) as a selection mechanism. These 9 trytes make the numerical range of 0–7,625,597,484,987 that is used by the hash ring and where all TimewarpID’s will be part of.
Above we can see the so-called candidate space. This is a part of the hash ring where AION nodes will try to issue their timewarp in.
Candidate selection
Above we see the candidate selection process. As we can see is that the original transaction of timewarps (XXX With address A) is used to pre-determine if our generated transaction is even eligible for this slot. If it is not eligible then we simply won’t broadcast it and bother the rest of the tangle with this. This would eliminate roughly 4/5 of the transactions for electing a timewarp slot leader. Because timewarps require an extra transaction, as discussed at the timewarp detection part of this article, we can’t detect them yet.
So after 90 seconds we issue our first signed timewarp transaction and this sets us up for the voting round. When X time or Milestones pass we take all candidate transactions and make a consistent random choice. This choice is based of a random offset in candidate space that is generated by XOR-ing all TimewarpID’s.
What the evaluation process is achieving is a consistent random choice that is hard to game. Because of the ordered XOR of the (PoW generated) Timewarp ID’s generating the offset you will be literally shooting on a moving target because each time your transaction fits in the set, the offset moves. The only way to make it more secure is to include the hash of the milestone as part of the XOR process. But for now, I don’t want to rely on that yet but warrants further discussion.
Besides that, remember this is to play nice. Everyone will be able to run a timewarp regardless of taking part in this election process or not. In the end, it is a permissionless system after all.
How is AION using timewarps?
This is a topic for another blogpost ;)
Feel free to contact me with questions or suggestions on https://discord.iota.org: Olaf van Wijk#1273
Or follow me on twitter: @ovanwijk
