IOTA and SPECTRE

The most exciting development in the cryptocurrency world is the incorporation of Directed Acyclical Graphs (DAGs) instead of blockchains. The people at the forefront of this development are the guys behind SPECTRE, Aviv Zohar, Yoad Lewenberg, and Yonatan Sompolinsky, and the guys behind IOTA, Serguei Popov, Sergey Ivancheglo, David Sønstebø, and Dominik Schiener.

Aviv and Yonatan were interviewed about their research into DAGs in a recent podcast you can listen to here:

In this interview they were briefly asked to comment on IOTA. The transcript goes like this (starting at about 1:02:30):

Host Brian Fabian Crain: “Ya, wow well this certainly sounds like an amazing technology and amazing things happening there. Now there are currently some projects in the cryptocurrency space that are doing work in this direction, probably the best known of them is a project called IOTA which is using these DAGs as well. Can you guys comment on what they are doing and how it compares to SPECTRE?

Aviv Zohar: “So I think it is a little bit hard to give a good opinion of IOTA. We have looked at the white paper that they wrote. They have some interesting ideas for the protocol, but one thing that is missing for us to fully evaluate the paper is — well we are academics, we are used to a very high level of formalism. Basically theorems where you state your assumptions, you prove that you get certain properties from the protocol. So if you were to go to look at SPECTRE, we took our 90-page paper basically to very carefully state the properties of protocol, what the assumptions are of the network, and then its easier for us to understand if either the assumptions are wrong or the proof is wrong, but if you accept the assumptions, and the proof, then the end result has to be true. IOTA gives a protocol, but it doesn’t do so very formally so it is very hard to analyze. The white paper is also I guess kind of old so I am not really sure what is implemented in code versus what is in the white paper. So we had concerns about, I guess, the white paper, but it could be just that we are misreading what the protocol does because it is not stated formally enough for us. Other papers in the area sometimes have the same problem for us.”

In the IOTA slack channel, I asked if the guys behind IOTA could respond to this, and they were kind enough to do so.

First Sergey Ivancheglo (Come-from-Beyond), had this to say:

“Well, they are academics and want to see formalism. I’m an engineer and want to see a working system. They use unreadable formulas, I use simulations. Looks like our universes don’t intersect at all…

But we can ask users if they need something working or something existing only as a spherical horse in vacuum.

Here is another example — It’s impossible to solve this problem with formalism yet:”

“Cryptocoins don’t have established paradigms yet, it’s hard to exercise formalism in such conditions

A single turn in a wrong direction and you stop only hitting Epistemology wall”

Serguei Popov (@mthcl) followed up with this:

“Well, as you know, I’m a research mathematician. I know how to formalize things. I would like to have done it in the IOTA whitepaper. The problem is that it is nearly impossible to rigorously prove anything about that random walk which does the tip selection — its state space is random, and it has a complicated structure anyway. The whole idea of the (general) MCMC method is that you have some object that you can’t access directly, and you let a suitable Markov chain to approach it for you. What I can say, is that the Markov chain’s intuition that I have tells me that the thing would work as expected. But we need to confirm all that experimentally (by running simulations), and this is something that is taken care of now. ___________________________________________________________________

1. What does a node want? It wants his transactions be confirmed by others.

2. To be approved by the society, you have to behave the way the society expects you to behave. In our case, specifically, you tips must be “good”, in the sense that they are (relatively) likely to be chosen by others.

3. So, suppose that our node is so selfish that it doesn’t care at all about following the protocol, it just wants its transaction to be confirmed. But for this he has to discover where to place it in such a way that it maximizes the probability that other nodes will choose it for confirmation.

4. Now, how does he discover that place? Assuming that at least a good proportion of others follow the default algorithm (which is quite a reasonable assumption in IoT) the better way seems to be just running the default MCMC algorithm several times and see where it gets you. This is a very important point: when you deal with a complex MC, the best way to understand how does it behave is just to run it and see what happens.

5. So, we kind of arrive to the conclusion that even a very selfish node should better use the default algorithm. Well, yes, a node with good knowledge of the current state of the tangle and good computing power may be able to really optimize its choice and choose the two tips to approve in such a way that the probability that others choose it will be maximized. But the gain from this won’t be so large, probably quite marginal. Besides, such an optimization requires time and resources, and the state of the tangle changes rapidly…

6. Thus, any “selfish” strategy should be in some sense close to the default MCMC. The latter acts as an attractor, in some sense.

👆 That’s a heuristic argument, but not a rigorous proof, of course.”

Fahad Sheikh (@hellsingfan) followed up with another question:

“So as ‘simulations’ are the proof for the way things should work, will the IOTA Whitepaper [2.0] rely on simulations and justify that the things are working as expected. Like will arguments be presented why IOTA works and that why it can not be formalized but that simulations are presented as substitute?”

Serguei Popov (@mthcl):

“You can be sure we’ll do our best to justify that the things are working as expected. 😃

On a side note, do you guys understand that the whole current public-key cryptography relies on unproven assumptions?

Fahad Sheikh (@hellsingfan):

“Maybe you should highlight those unproven assumptions [in the IOTA Whitepaper 2.0] too just to drive the point home.”

Serguei Popov (@mthcl):

“That’s all those statements that “doing something is computationally difficult,(e.g., factoring big numbers). In a way, all this amounts to that famous “P vs. NP” problem:”

It would be great for the SPECTRE guys to follow up and keep this discussion going.