Mathematical Foundations of IOTA Cryptocurrency

The Tangle Serguei Popov

Problem Scenario Concept of transaction fee for transactions of any value in cryptocurrencies. Heterogeneous nature of systems: Transactions issuers and Transaction approvers resulting in conflicts which requires spending some sources on conflict resolution. Scalability issues High hardware and resource requirements

Contributions Analyze the mathematical foundations of IOTA, a cryptocurrency targeting IoT. The tangle, a directed acyclic graph(DAG) for storing transactions. A family of Markov Chain Monte Carlo algorithms for selecting tips in the tangle.

Some terminologies Sites: Transactions represented on the tangle graph. Nodes: Nodes are entities that issue and validate transactions. Tips: Unapproved transactions in the tangle graph. Height: the length of the longest oriented path to the genesis. Depth: the length of the longest reverse-oriented path to some tip. Genesis: very first transaction in Tangle

Issuing a transaction The transaction making process in IOTA is a simple, 3 step process: Signing: Sign the transaction inputs with your private key Tip Selection: MCMC (Markov chain Monte Carlo) is used to randomly select two tips (i.e. unconfirmed transactions), which will be referenced by your transaction. Proof of Work: In order to have your transaction accepted by the network, you need to do some Proof of Work similar to Hashcash (spam and sybil-resistance)

A parasite chain attack and a new Tip Selection Algorithm

Weighted MCMC algorithm 1. Consider all sites on the interval [W, 2W], where W is reasonably large. 2. Independently place N particles on sites in that interval. 3. Let these particles perform independent discrete-time random walks towards the tips , meaning that a transition from x to y is possible if and only if y approves x. 4. The two random walkers that reach the tip set first will sit on the two tips that will be approved. However, it may be wise to modify this rule in the following way: first discard those random walkers that reached the tips too fast because they may have ended on one of the lazy tips .

Weighted MCMC algorithm (transition probability) if y approves x (y x), then the transition probability Pxyis proportional to

Weighted MCMC algorithm This algorithm is used for two purposes. 1. 2. For choosing two unconfirmed transactions(tips) when creating a transaction. For determining the confirmation confidence of a transaction. The MCMC tip selection algorithm also offers protection against the lazy nodes as a bonus.

Resistance to different attacks 1. Large weight attack where in order to double-spend, the attacker tries to give a very large weight to the double-spending transaction so that it would outweigh the legitimate subtangle. As a solution, limit the own weight of a transaction from above, or set it to a constant value. When the input flow of honest transactions is large enough compared to the attacker s computational power, the probability that the double-spending transaction has a larger cumulative weight will be very low. The attack method of building a parasite chain makes approval strategies based on height or score obsolete since the attacker s sites will have higher values for these metrics when compared to the legitimate tangle. This is where the MCMC tip selection algorithm seems to provide protection against this kind of attack. 2. 3.

Resistance to quantum computations Quantum computers, still a hypothetical construct as of today will be very efficient for checking nonces to find a suitable hash. I.e do PoW. However, the number of nonces that one needs to check in order to find a suitable hash in tangle is not unreasonably large. On average it is around 38. So, quantum computation wont benefit much in case of tangle.