The story of IOTA
The first time I discovered the Iota project, I immediately thought - we are a small thing - to the friendly cashier of one of the neighborhood butcher shops to which I sometimes go to do my shopping (yes, I have the chance to live in a neighborhood where there are still some shops known as "proximity") ... She is in fact used to receive her customers who wish to pay by credit card, presenting them an electronic payment terminal and thus apostrophizing them with a malicious air: "It's up to you to work! "- pretending to believe that composing his four-digit secret code is an exercise that deserves our attention ...
Behind her joke that makes her laugh every time, does she know only that there is thus summed up the latest ingenious developments concerning modern payment systems? Developments that could play a considerable role in the famous- still in the making - internet of things, transfers of order and possibilities of micro-payments.
Developers, miners, users, a blockchain
Let's take Bitcoin and all his successors, including Ethereum. A cryptocurrency is in general: developers, miners and a blockchain. The whole is based on a scientific guarantee that can take the form of a simple pre-publication, or a foundation. (Let's open a parenthesis. What happened on August 2 at Stanford University is significant. The brilliant and modest Dan Boneh - I report the opening of his elementary cryptography 1 course on September 5 on Coursera - spoke to a well-informed audience of Bitcoin Core developers and miners, some of whom came from far away, presenting a number of future challenges, the text of which is available at this address. A read for the maths "bitcoiners" …)
All cryptocurrencies share the same model: a clear distinction between users who are only there to give orders and make new transactions and miners who group all these transactions, verify that there is no fraud, store them in blocks and guarantee the security of the network. In theory, everyone can be a miner. But in practice, mining is the business of real companies essentially based in geographical areas where the cost of electricity is (virtually) zero.
A word all the same here on the cryptocurrencies with Proof of Stake. In this case, the mining is a bit special because it is completely virtual and does not require high-performance computing equipment to carry out calculations. See page 231 of Princeton's book on Bitcoin on this issue. The distinction between real users and miner who secure the network is therefore less strong than in the case of cryptocurrencies with Proof of Work because participating in the "lottery" of the new block is accessible to all; Everyone can participate without special effort ... Nevertheless, we do not always want to participate in the large mining lottery - especially if we are not very rich because then we have very little chance to win ... The model remains the same: a blockchain and miners.
Seen in this light, the difference with the traditional world of finance is not obvious, since in this world which is ours, transaction security is usually provided by banks based on international regulations. And no more the customer of his neighborhood butcher who pays with his bank card than the speculator who buys or sells his bitcoins on a trading platform, no one has the impression, with his operation, to participate in the security of the network he uses. On the contrary, he has the vague feeling of creating a problem that will be managed by competent people (one has the right to hope!).
To finish with the blockchain!
And then here is IOTA that changes everything ... Initially, there is a start-up in 2014 that seeks to develop new types of microprocessors in order to give life to a certain Internet of Things (we recognize in the beginning of IOTA, The acronym "IOT" for "Internet of Things"). Developers quickly realize that there is a lack of technology linking all connected objects. We would like to connect them around a blockchain especially since David Sønstebø and Sergey Ivancheglo who are at the head of the project are great connoisseurs of blockchains and cryptocurrencies. But none can be suitable in practice. Indeed, none provides the possibility of micro-transactions without transaction fees. In addition, all known blockchains have scale problems that can be too restrictive.
At the same time, on the NXT forum, where Serguey regularly posted at the beginning under the pseudonym "Come-from-Beyond" (some even imagine he is the enigmatic creator of this cryptocurrency appeared at the end of 2013), Internet users begin to think of another way of organizing transactions only in blocks. And if, instead of grouping the transactions in packages, they were left free individually while connecting them astutely with each other? After 2013, with the GHOST protocol, Aviv Zohar and Yonatan Sompolinsky had cleared the way by inviting the entire tree structure of transactions to be taken into account in order to reinforce the protocol of existing cryptocurrencies (Vitalik Buterin will take over this proposal in Ethereum).
But how can we connect transactions between them if there are no blocks or miners? Each new transaction X, in order to exist, could be required to approve past transactions. This would require that when registering X on the network, it is necessary to select some existing transactions. In the drafting of X, the user should therefore be forced to choose past transactions, to verify that there is no incompatibility between them and to oblige him to solve a problem of Proof of wWrk - hope that it serves to secure the network. There would be no more block, but any transaction would be a mini-block.
Such was the idea that was beginning to emerge on the NXT forum and in the first tests realized by David and Serguey. By passing a transaction, the user would therefore act not only in his own interest but also in the interest of all. A simple transaction would serve to secure the entire network ... There would be no common ledger available to all and which increases by one page every ten minutes on average as for Bitcoin. There would simply be no more blockchain! Enough to rejoice all those who can no longer see this word overused and taken over by people serving very different interests for what it was originally created ... It remains of course to imagine concretely the protocol and the rules to avoid the attempts of double expenditure but immense new possibilities seem to be offered to us ... Instead of a linear sequence of blocks, we would thus be led to see the set of transactions as a Directed Acyclic Graph. We are in 2015, the IOTA project is being formed.
Markov is in the place …
And then here is Sergei Popov who brings his mathematical expertise. Sergei is a great mathematician, professor at Unicamp University in Brazil and a member of the NXT community. Thanks to him, IOTA will win a scientific guarantee. He will formalize the ideas of David and Serguey and write the founding paper of IOTA.
The ingenious idea he had was to have somehow "probabilized" the acyclic graph of the transactions cited above, that is, to have transformed it into a true Markov chain.
Concretely here, what avoids attempts to scam at double expense is the possibility of exploring this chain of transactions as a Markov chain as a hiker would do by a Monte Carlo type method. The results of these random walks make it possible to disqualify fraudulent transactions.
Let's briefly explain how IOTA works. What makes it possible to trust the network is no longer the number of blocks that covers a given transaction (in Bitcoin, if a transaction is buried under six or seven blocks, it is considered absolutely safe). Here, each transaction has a cumulative weight that changes over time. It is defined as the number of subsequent transactions that have approved it directly or indirectly. More precisely, it is the sum of the working power used by all these transactions.
A legal transaction will naturally become "heavy" due to all the transactions that will come after and gradually point to it. And just as in Bitcoin, a seller waits for a given transaction to be covered by six or seven blocks before it can give his consumer good to the customer, so here the seller will wait until the customer's transaction has reached a certain cumulative critical weight.
At the time of writing, a new transaction will choose with Popov's algorithm two transactions waiting for validation. These two transactions are the result of two random hikes by a Monte Carlo method starting from a place of the graph extremely safe (no need to go back to the origin). To avoid approving fraud attempts, it is therefore necessary to find a good measure of probability which allows to remain on the part of the graph that contains only honest transactions.
What probability to choose?
Morally, an honest transaction has a much greater weight than a fraudulent transaction (there is no real illegal transaction, but I mean a fraudulent transaction that reflects an attempt at double expense). Indeed, in normal operation, an honest transaction is taken over by the whole network while an attempt at double expense is chosen only by an attacker. It is considered here that it is not possible to own more than half of the computing power of the network alone.
The probability measure must therefore be chosen so that it is almost unlikely to pass from a site x of the graph having a cumulative weight H(x) of importance to another site y connected to it but having a weight H(y) very weak. In passing, note that a transaction that points to y points a fortiori to x, so that H(x)>H(y). It is then natural to take as a measure of probability a measure such that the probability of passing from x to y is proportional to exp(-(H(x)-H(y)) and this is the probability on the Markov chain. In the end, it is the rapid growth of the exponential that makes very unlikely the possibility of jumping from an honest part of the graph to a dishonest party ...
Moreover, if, unfortunately, the two transactions chosen were incompatible with one another (because one of them is the result of an attempt at double expense, for example) then Popov's algorithm retains only the transaction most likely To be accepted by others. To do this, it is necessary to repeat several random walks and to obtain ultimately a measure of probability on all the ends of the graph.
Has the summit been touched with IOTA? We are right to think so …
Note for folklore that one can always imagine the presence of miners in this network but since there is no block, there is no reward either. The only possible mining job is to issue an empty transaction (without money transfer). This work is unpaid but like all other transactions, it secures the network as it helps to increase the cumulative weight of honest transactions.
Let us also draw the consequence that there is no longer a blockchain. More blockchain means more conventional miners and therefore more money creation. It is therefore that the whole quantity of money was issued from the beginning …
What is fascinating in the history of mankind is that inventions often do not arrive at a given place but often simultaneously in several different places. It is thus of the invention of writing in particular. If I write this, it is because independently of the beginnings of IOTA, Sergio Lerner on his blog also imagined to end the distinction between miners and users. But too worried about the success of Rootstock, it has probably not been possible for him to develop his intuition and implement his DAGcoins ...
There is now a community of IOTA users: more than three hundred pages of threads on bitcointalk, an increasingly active slack, and a blog. We can easily imagine connected objects that pass orders on Iotatoken. And all, obviously without transaction fees …
What more can be said ? The Popov article contains other extremely interesting little calculations as a totally natural (but I have never seen elsewhere) use of the theory of large deviations to prove that IOTA is resisting a certain attack scenario. All can only be said in an article ... I let you visit the site of IOTA.
Congratulations to Serguei Popov, David Sønstebø and Sergey Ivancheglo ... Hats down gentlemen!
TN: This article is a translation with minor changes of Cyril Grunspan’s article.