# Prototyping on Enabling Ethereum Virtual Machine on top of IOTA/Tangle

## Introduction

IOTA is a revolutionary new, next generation public distributed ledger that utilizes a novel invention, called a “Tangle”, at its core. The Tangle is a new data structure based on a Directed Acyclic Graph. As such it has no Blocks, no Chain and also no Miners. Because of this radical new architecture, things in IOTA work quite differently compared to other Blockchains

> [IOTA, a new data structure based on Directed Acyclic Graph(DAG), is expected to utilize the next-generation public distributed ledger with its core called “Tangle.” This revolutionary technology breaks the boundaries of blockchain, neither block nor chain to implement. Therefore, miners are limited to contribute their efforts in the system.]

The purpose of prototyping is to allow users to run Ethereum smart contract on the DAG-based cyptocurrency, especially for IOTA/Tangle. It is done with the policy of eliminating modifications against IOTA Reference Implementation (IRI) as possible.

> [This essay aims to create an envionment or impose specific conditions that allow users to implement Ethereum smart contract on DAG-based structure, such as IOTA/Tangle. In this case, IXI module can be one solution. We introduce IXI module for IOTA's IRI(IOTA Reference Implementation) node to realize Ethereum Virtual Machine and simultaneously stay compatible with the existing IOTA network. However, things hardly work as we prototype. With further investigation, we list down the four major problems we encounter as below.]

IXI module for IOTA's IRI node is introduced to load an instance of Ethereum Virtual Machine along with IRI at our first glance. If we use the IXI module to do this, we can be directly compatible with the existing IOTA network. However, it did not really work while we were working on prototyping. The problems are listed as following:

> [
>1. Limitation of Transaction-Centric System: IOTA imposes strict standards to ensure transaction go smoothly. If the execution result of any contract gets involved in unbalancing the entire system, mere IXI change cannot achieve anything.

>2. No Storage Space for VM State: As mutable varaible, EVM machine state has difficulties finding a place on fixed storage field. Also, the form of storage could be another issue.

>3. Order Dilemma: Without certain sequence, transaction order is toughly determined on tangle. Thus, the conflits in different nodes are predictable as the order problem is not well-solved.

>4. Unhandy Account Verification: Since IOTA adopts Winternitz One-time Signature as identifier, single-use addresses are complicated for ideneity authentication. A better way should enable users to consistently hold their accounts.]

- All IOTA behavior is around transaction
> if the contract execute result is about transferring contract's balance , we cannot express that just through IXI
- There is no storage on tangle storing the vm state
> because evm machine state is variable (it will change when receiving message call)
- There is no way to determine the order of the transactions on tangle
> There is no certain sequence in the block chain tangle.
- Because IOTA uses winternitz one-time signature [ ], address cannot reuse, it is genuinely difficuclt to represent account in IOTA
> So we need a way to consistently show that you are the owner of this account.

These problems are incompatible with the IOTA's own architecture, so using IXI will not solve our problems.
We present some methods and processes to solve these problems.

> [All of them result in the incompatibility with IOTA architecture. Therefore, we abandon the idea of IXI and propose another method as a solution to realize Ethereum smart contract on IOTA.]

## Smart contract
Smart contract, the idea being described by computer scientist and cryptographer Nick Szabo in 1994, has become one of best part of blockchain. Ethereum is a blockchain featuring smart contract functionality. In Ethereum, if you want to create a contract or invoke a contract, you need to send a transaction. We call this transaction the creation of contract transactions which purpose is to deploy a contract, or message call which purpose is to interact with a contract
It should have the following characteristics about this transaction.

1.Transaction only changes world state after confirmation
> Only after the transaction has been confirmed is it a valid call to invoke it to execute the contract.

2.Transaction can only change world state once. It means that the same call should not be executed multiple times.

## IOTA network state
The next scenario we are going to talk about is the presence of a coordinator on the IOTA network.
Because according to the IOTA white paper[], in the absence of a coordinator, the way the network is used to agree on the current state
is : we execute the MCMC algorithm N times, the probability of your transaction being accepted is therefore M of N (M being the number of times you land on a tip that has a direct path to your transaction)

In IOTA, you have complete freedom to decide with what probability you will start accepting transactions. If you are happy with 51% probability, you execute MCMC 100 times, and if 51 times or more there is a path, you accept the transaction and exchange goods. For high value transaction, you can increase this threshold to 99 or even 100[]

The above approach conflicts with the two principles mentioned in the previous section. First of all, we have to wait until the transaction is confirmed, but it is difficult for a node to know that a specific transaction has been confirmed, and it is time to execute the contract code.
Because checking whether the transaction is confirmed is through the user active MCMC algorithm to perform, but for nodes, it is not known that a specific transaction has been confirmed.

If the time point for execution of the contract is designated as some query node specific transaction for confirmation, and the result is true, it is difficult to make sure whether the contract is executed only once.
The contract may be marked as already performed, but there could be a lot of people looking at it simultaneously and there is a race condition problem. At the same time, it makes the actual process more complicated.
Therefore, we choose to do it in the condition of having the coordinator, and using the coordinator's milestone can be very easy to actually do our Prototype. The transaction can only be confirmed by the node when the milestone reference is made. HENCE, we can set the time of execution of the contract on the node to receive the milestone and confirm the specific transaction, which can be very simple to meet the above two principles. Transaction only changes world state after confirmation and Transaction can only change world state once.

## Smart contract on IOTA

According to the contents of the Ethereum Yellow Paper[].we need ethereum virtual machine to execute ours contract.We hope that our contract can be written directly through solidity,and use ethereum virtual machine for execution.
For increasing new consensus rule on the performance of contracts on IOTA.We need to have ethereum virtual machine on each IOTA full node.We also need to record the machine state for each contract through increasing the new field in IOTA rocksdb,which is called evmstate.

| key|value|
|----|-----|
|contract address|evmstate|

when we want to perform a message call we have to load the vmstate according contract_address first.
Because there is no way to distinguish the db data smartly,the contnet in evmstate we put a Merkle Patricia trie in the vlue column.Then we can simply verify the execution of the contract by comparing the root hash.
We also need to define the order of transactions because the order of execution smart contract is the most important.Then,dealing with problems that can not be reused with iota addresses.

## Order of Transactions

The tangle is a graph with only a partial order structure, which makes it difficult to establish the correct time order of transactions[], but the order of transactions is very important for smart contracts.

Through the timestamp on the trading, because of the possibility of malicious nodes, it is really hard to discharge a sequence. Therefore, we suggest another way to help us exhaust the order of the transaction

The important thing is not the authenticity of the order, but the consistency. We should ensure that the order of each node transaction is the same. As for the authenticity of transaction order, other block chains such as Ethereum are not solved.

Our approach here is to set some rules to get the order of transactions(confirm by this milestone) when the node receives the milestone to synchronize.

First introduce the node synchronization mode.

**Last Milestone index** is the highest index of a milestone transaction you have seen

**Last Solid Subtangle Milestone index** is the highest index of a milestone transaction where you have received all referenced transactions as well

When they differ, the node will try to start synchronization, find out the transaction between the two indexes, request other node for missing transaction data and verify that it is legal. After it has done these, setting the **Last Solid Subtangle Milestone index** index to **Last Milestone index**.

For determining confirmation state, the node will consider a transaction confirmed if and only if it is (directly or indirectly) approved by the latest solid subtangle milestone. This milestone is also used to compute the authoritative balances returned when you ask the node for an address' current balance

We found that just limiting the sync milestone index can only add one value at a time. For example, your **Last Solid Subtangle Milestone index** is 42983, and you have to synchronize with index 42984 first.
In this way, we can determine how many transactions between 42983 and 42984 are confirmed, and the result of each node should be the same.
We can order these quantitative transactions in a single order, and notice that the order must be the same in all nodes. Thus we need an algorithm, and the node is just going to execute it and we get the same result
Here we have an idea that, after Dag is cut by the milestone, we can simplify it to binary trees. We can simply give a travel path to the binary tree by DFS algorithm or other algorithm which can refer time stamp, made a more reasonable algorithm

## The experiment design

we intro the milestone in this simulation,
without the milestone, the starting point for randomwalk was genesis.
There is a mechanism by which the coordinator invokes milestone that we don't really know, because the coordinator is not open source.
We assume that the behavior of the coordinator initiates the milestone.
The trunk transaction MCMC starting point will set at the lastsolidmilestone, and branch tx can set at another transaction which you choose,or it can be more deeper than the lastsolidmilestone, depending on your parameter. And we set it up in the genesis.
Let's assume that the frequency of issuing the milestone is fixed.and the frequency is β.
According to the author,the total time unit of the simulation is equal to the total number of transactions divided by the λ(the rate of incoming transactions).
So every fixed time unit (β) will issue a milestone in our simulation.

## algorithm
Our goal is that each node can get the same order through the milestone.
One scenario must be considered, the milestone order received by each node may be different.
We have to ensure that we get the same results when we synchronize the ledger of different milestone indexes.

For instance, the transaction 4 is milestone with index 1, and we get the transaction order through our algorithm is 0 , 1 , 4 .
then the transaction 8 which is milestone with index 2 , the transaction order of the first half must be the same as the index 2. The result is 0 , 1 , 4 , 3 , 6 , 2 , 5 , 8 .

Let's assume that two different nodes have same equal lastsolidmilestone index 0 , One of them received an index 1 milestone and another one received an index 2 milestone.
The intersection of transactions which are confirmed by the milestone index 1 and the milestone index 2. In this case is { 0 , 1 , 4 }, their order must be the same in both nodes.
Even if you start with the milestone index3, you must follow it.
The result is 0 , 1 , 4 , 3 , 6 , 2 , 5 , 8 , 7 , 10 , 11
How did we get there? First of all, we must assume that the behavior of the coordinator is the same with IRI, set the starting point of the trunk tx in the lastsolidmilestone when performing a MCMC, and because the milestone was launched by the coordinator, wouldn't have missed any milestone. This guarantees that each milestone on the starting point of the trunk tx is the previous milestone index . And then we're going to dissolve the dag into a binary tree.
We first set up the left subtree along the trunk of the transaction, and if there is a branch transaction we will evaluate whether we want to add it to the right subtree, by comparing its snapshot index
Then we can get a binary tree, and at the same time we can guarantee that the previous milestone's binary tree will be part of its left subtree.
After that, we can get a set of orders for the DFS or other tree travel methods.

## IOTA Address

Due to Winternitz One-Time Signature Scheme, if we want to reuse IOTA addresses, it will be under risk of leaking your private key. It is important for that smart contract to identify which account the transaction is issued from.
Take ethereum SOLIDITY Special variables for example.
msg:the data associate with transaction
- **msg.gas (uint)**: gas that remains
Omitted
- **msg.data (bytes)**: complete calldata
Omitted
- **msg.value (uint)**: amount of wei which was sent along with the message

- **msg.sender (address)**: message sender (current call)
important, we have to resole the account problem in iota, because we have to distinguish who you are through your address or somthing you offer your info along with transaction
- **msg.sig (bytes4)**: calldata’s first four bytes (i.e. function identifier)

Back to IOTA, the seed is the private key of an account. We can extrapolate multiple addresses from seed, but we cannot infer the seed back from address(Who is the owner of this account).
To solve this problem we maybe can put alias on IOTA address[].
The author of this article has given a brilliant idea, but it is not feasible in reality, and we have provided some ideas to make up for the deficiency above.

If we want to attach an alias to the address, we need to send a transaction to the address where the “obsoleteTag” field will contain a new alias. Every node that will receive this transaction will check if the alias is unique. If it is not the transaction, it will be considered “invalid”. Otherwise, the node will store this alias for the address and once the transaction is confirmed, we can be sure that the alias is added to the address.

The transaction is look like that

| Address|QGNXKYQ9CMNPMCTONCOWJS.....|
|----|-----|
|Value|0|
|Obsolete Tags(alias)|ALIASTAG.......|
|Signature|XXXXXXXXXXXXXXXX.....|
|currentIndex|0|
|...(other)| |

Then, we think we need to add a column to the IOTA's database for alias.

|key|value|
|---|-----|
|alias|address|

Article mentioned the alias of the existence of a obsoleteTag trading field, we cannot just store alias information in the transaction
it is very difficult to achieve the goal about check if the alias is unique in database.

part of IOTA full node rocksdb data storage structure(about this idea)

|key|value|
|---|-----|
|address|list[transaction hash]|
|transaction hash|transaction(8019 trits,2673 trytes)|
|...(other field)||

the obsoleteTag is Store in transaction trytes
trytes.slice(2295, 2322)
and address info is store in trytes.slice(2187, 2268)

because we need to keep other transaction's transaction hash to query the alias info, it does not make sence. Therefore, it is reasonable to add new fields to record the matter.

This raises some problems, we need to wait until the transaction is confirmed before we can put the alias into the database, which, as mentioned above, can be done through the synchronization milestone phase. Another scenario is when two or more people are claiming ownership of the same alias, a sequence is required for the transaction.
This can also be solved if we use the method mentioned above.

改成使用msg用json格式來存
To change the alias by another alias we need to send a transaction to the address where the “obsoleteTag” filed will contain a new alias. In this case the transaction has to be signed. Again every node that will receive the transaction will check if the new alias is unique and the signature is valid. If everything is okay, it will replace the old alias by the new alias.
To remove the alias from the address is very likely, the only difference is obsoleteTag filed should be empty (“9” trytes)

Our side is to use an alias to represent an account, so when we want to change address, we need to transfer our alias, which can be done through the combination of removing an alias from an address and attaching the same alias on other address. It have to be done automatically.

Fortunately, we can do this through bundle[], which is made up of several transactions, and they will be confirmed at the same time.
If we want to transfer alias, the bundle will look like that.

| address|QGNXKYQ9CMNPMCT.....|
|----|-----|
|value|0|
|Obsolete Tags(alias)|9999999999999(Remove Account alias)|
|signature|XXXXXXXXXXXXXXXX.....|
|currentIndex|0|
|bundle|ABC.....|
|...(other field)||

| address|next unspent address|
|----|-----|
|value|0|
|Obsolete Tags(alias)|OURALIAS99999999999(Account alias)|
|signature|XXXXXXXXXXXXXXXX.....|
|currentIndex|1|
|bundle|ABC....(same as above)|
|...(other field)||

## Contract Creation

Then discuss how to deploy your contract on the IOTA network.
First, you must claim your own account by attach an alias to your address.After you successfully attached the alias to the address.
We can begin to prepare for the contract creation of the transaction.
Before that we need to compile the written contract into ethereum virtual machine byte code.Then start packing our transaction.
We need to make some changes to the bundle in order to be able to figure out who issue the transaction through compare the alias on the IOTA network.This is only a change in the transaction related to the contract, and the rest is not affected.Nodes can be easily distinguish which transaction is related to the contract, through comparing the address whether there really is vmstate field exists.
We have to be able to claim that we have this alias in the transaction.The claim of alias mentioned in the previous section is equivalent to a proof of existence.
We specify that in the bundle index one, it must be used to indicate that it has an alias, So you have to attach the signature of the address that claims to have the alias on IOTA network.

| address|Contract address|
|----|-----|
|value|(Based on demand)|
|Obsolete Tags(alias)|XXXXXXXXXXXXXXXXX|
|signature(message)|evm byte code|
|currentIndex|0|
|bundle|ABC.....|

| address|address correspond alias on network|
|----|-----|
|value|0|
|Obsolete Tags(alias)|OURACCOUNTNAME|
|signature|signature of address correspond alias |
|currentIndex|1|
|bundle|ABC....(same as above)|

| address|other address |
|----|-----|
|value|(Based on demand)|
|Obsolete Tags(alias)|999999999999999999999999|
|signature|signature|
|currentIndex|2|
|bundle|ABC....(same as above)|

|...(other transaction in same bundle)||
|----|-----|

When this transaction is referenced by milestone,it means that it has been confirmed.Back when the chapter mentioned transaction's order.
When the node receives a new milestone and starts synchronizing, it sets the order for the transaction.After verifying that the new milestone is legal, it is time to execute the contract.
After the execution of the contract's constructer.the results are deposited into the vmstate field of IRI rocksdb

client->iri: alias your address
iri-->client:confirm alias tx
client->iri: contract transaction
Note right of iri:  create contract address
Note right of iri: after revive milestone
Note right of iri: execute evm bytecode

## Message Call

It is kind of like a contract creation transaction, but it's a lot more complicated, and there are a lot of exceptions that have to be dealt with.
The main process is to take the previous state from the vmstate column,execute the contract according to the input parameters and state,and get the result of evm execution.We are translating this result into some steps to change the status of IOTA.
Before delving deeper into the process. let's compare the data that Ethereum and IOTA have on the storage account.

### IOTA account behavior

As we know, the ethereum is saved with account base.
Unlike the ethereum, this is part of IRI's database.
| key|value|
|----|-----|
|address|List[tx hash]|
|tx hash|Transaction[8091 trits]|
The following is the process of obtaining an account information.
Start with the zero index of the seed and convert the corresponding address.Query whether the address has a transaction record until contact with no transaction record is met.Then add these related transactions which have been confirm together and the result is the balance for the account.
Note that IOTA's accounts are closely related to transactions.
What we are going to discuss is the transfer of the contract.
The contract is transferable, and we can transfer the balance in the contract to other accounts through the execution code. In the ethereum, this is a simple matter, as long as the balance of the account is calculated according to the execution result of the contract.
But for iota, as we said above, it can only be described through transactions. For contracts, there should be no seed, because these are unreasonable.The transfer is supposed to be done through consensus on the outcome, not not through a third party to help us sign the transaction. So we don't need multiple signatures to solve this problem.
We propose a new type of transaction to help us solve this problem.

### Internal transaction

This type of transaction must conform to the following principles.
1. It can only be produced through the execution of the contract.
- Because its purpose is to describe the behavior of the contract, it is the transaction that iri generated when executing the contract and will not broadcast it.

2. It won't have any signature.
- It can only move the balance in the contract address, and the money in the contract address should be written in accordance with the contract.And how should the money in the contract address be used, according to the contract content

3. It should have been confirmed when it was created.
- As mentioned above, the time point of contract execution is iri's synchronization of the new milestone, when the MSG call transaction has been confirmed by the iota network. As a subsidiary transaction describing its behavior, it should also be confirmed to change the network status of iota at the same time.

How do we achieve the upper order condition?It's very simple, but it's hard to understand.

First of all, how do iri know whether a transaction is confirmed or not?
Each transaction in the iri will have a value called the snapshot index. It is not recorded in the transaction. It is generated when the iri executes synchronization and is set to the last solid milestone index at that time.We know that the transaction that was referenced by the last solid milestone on the node is confirmed. As long as the snapshot index of the transaction is a confirmation transaction before the last solid milestone index.
To get back to our theme, as soon as this new type of transaction is created, we set up its snapshot index for last solid milestone index
In this way, the above principle can be reached.
We do not need to worry about someone forged this transaction, because the fake transaction will not be confirmed. Because the snapshot index are set through performing the iri synchronization, illegal transactions cannot be milestone reference, under our mechanism, this new type transaction occur only through the contract will be confirmed
We also need to analyze the behavior of the contract, because it is not only the transfer of the contract that needs to be described in this transaction.For example, there will be a lot of refunds, when certain instructions fail.

## Reward for miner

In our prototype, the contract will also be limited by gas. Because iota has no miners, we have to redesign the incentives.
Because there is no incentive to set up iota's full nodes at this stage.And to initiate a transaction, you still have to go through the full node.We can give gas to the erector of the full node as a reward,because of the split between all nodes is unreasonable.
Our mechanism is who help you to initiate transaction it can get the gas along with it.
And the bidding of iota tokens and gas.You can design it a little bit more elastic.But we want to simplify the process and calculate ,
each of these transaction has to be bought for a certain amount of gas, and the price is fixed.This design only in order to simplify the process ,and it can be designed to be more spiritual

## Conclusion

In this work, we propose a way to combine IOTA with ethereum VM, so that smart contract can be run on IOTA. we provide a specific way to arrange the order of transactions on the tangle. And propose a solution to the fact that addesses in IOTA cannot be reused due to winternitz one-time signature. By the way, providing incentives to encourage the erection of full node.

## Future work

Because all of our ideas are running on the premise of coordinator's existance. Currently, the TPS of the IOTA network is very low, close to one or two. However, the future of IOTA network is going toward the absence of coordinators. We can do research on this. Our goal is to combine ethereum VM and IOTA network [In addition, the virtual machine directly uses the ethereum virtual machine at this stage.] In terms of compatibility, A more mature vm state design can be studied. In this work, we also points out some of the missing parts of the IOTA network, which hopefully will be referenced in the current iota network.