Fantom Archive — Virtual Machine

Disclaimer: Fantom Archive articles date back to early 2019, around January and February.

Introduction

Current blockchain based virtual machines have inefficiencies in terms of speed, optimization and cost. Opcodes have fixed execution cost fees, causing execution to be prohibitively expensive. Execution can not be parallelized, and each consensus participating node must execute the state transition to have the same state outcome.

We propose an asynchronous, optimized, register based virtual machine, capable of verifiable computing, while decoupling the token model to provide a distributed execution marketplace with probabilistic payments.

Background

The original design of the EVM was to provide a generalized world computer. Leveraging the total available resources of the network to create a new supercomputer. Instead, given how execution occurs, the network has only as much compute power as the slowest participating consensus node. Each participant has to execute the full VM instructions. If execution would take 3 hours to complete, then each participating node would need to execute the full 3 hours of execution. For this reason execution has fee and gas limits. These intrinsic limits do not allow for complex computing or allow for execution capability to be leveraged on a global scale.

To achieve a generalized compute engine we need to be able to decoupling execution and create a bidder based marketplace. Execution itself however effects state, and as such we still need to apply state changes without needing to execute the full system state. This does mean that there needs to be a realistic limit to on-chain state.

Architectural Overview

• Registration, reputation, and transparency in payments and penalties for the workers occurs on-chain
• Workers provide computational power to the system
• Verifiers are staked entities that issue tasks and verify results

Off-chain protocol between Verifiers and Workers for execution results, receipts, histories, and blockchain payments.

Probabilistic Payment Model that allows for trustless, stateless payments that scale with number of tasks.

Trustless Verifiable Computing

The objective is trusted computing. We have a job provider j, and we have a worker w, with computation c(a, b). j wishes to incentivize w to perform c(a, b). w is assumed malicious. w could perform zero calculation and provide output . j has no way to verify the validity of . j rewards w.

Strategy One, j gives computation c(a, b) to w1, w2, w3, … wn. In order mentioned they provide , , , , j can assume is correct. j needs to reward w1,w2, w3, till wn. This is consensus based trustless computing. j rewarded for each successful result. This is expensive.

Strategy Two, trusted hardware. Trusted hardware ensures execution. Intel SGX is the most widely adopted. Requires pre-compilation of c(a, b) into the enclave. Ensures c(a, b) is trusted. Cloud providers do not currently have SGX mass adoption. This excludes a large of a user base.

Strategy Three, zk-SNARKs (Strategy Three b, zk-STARKs, not currently production ready). Trusted execution. Can be deployed to any system, no hardware limitation, one to one usage.

We will use libsnark and Zokrates to demonstrate how zk-SNARKs can solve trustless computing.

Given function c(a, b) we can define it in as

def main(a,b):

return a+b

Compiled via Zokrates, we receive output

Compiling add.code

Compiled program:

def main(a,b):

return (a + b)

Compiled code written to ‘out’,

Human readable code to ‘out.code’.

Number of constraints: 1

Now we need to generate proof, given a witness of “a”: 1, ”b”: 1, ”out”: 2 and inputs of 1, 1, 1, 2, we generate proofand verification key

Given Proof , and Inputs i we can use Verification Key , to validate Inputs i (public inputs a, b and outputs o) for computation c(a, b)

To understand the above, let us discuss interactive proofs in a practical example. b want to buy item x from a for 1 token ( 1tk ). a wants to make sure that b has 1tk, b show a their wallet address 0xb, a can confirm it contains 1tk. a is unsure that b is the owner of wallet 0xb, so they use the public key (or wallet address) 0xA to sign message m, that creates hash h. a gives b hash h. b uses their private key pk to decrypt hash h and read message m, b respond to a with message m (or instead as answer to a question phrased in message m).

a has proof that b owns 0xb. This was an interactive proof.

If instead b wanted to preempt a’s request for proof. b could create message m (With the time and a’s name) which outputs hash h. If b then gives a m, h and 0xb, a can confirm that h was created from m by the pk for 0xA. This was a non interactive (or zero knowledge) proof.

Consider this same concept for zk-SNARKs, we can confirm that Verification Key is generated by compiling c(a, b), and given inputs i and outputs o the worker w can create a Proving Key pk that can be used along with to confirm the output.

This allows us to achieve verifiable computing in a trustless space.

Trustless VM

We have established that variable computing is possible in a trustless space. Next, we look at the Virtual Machine.

A Virtual Machine (VM) is an encapsulated execution environment. Following our previous example of Worker w, Job Provider j, and computation c(a, b), w does not wish to execute arbitrary function c(a, b) provided by j since j might be malicious and attempt to damage w’s systems. So instead w executes c(a, b) in a virtual machine.

The VM does not execute c(a, b), c(a, b) is compiled to bytecode b and then b lives inside the VM. This then allows b:c(a, b) to be called.

The above separation is important for understanding the (Ethereum) Virtual Machine.

At the bottom layer we have the VM (EVM), as the second layer, living inside of the EVM we have the binary (compiled contracts and Application Binary Interface (ABI)), and at the top layer we have solidity contracts.

For those familiar with Java, this is the same as the JVM (Java VM), ByteCode (class files) and Java source code. We would have HelloWorld.java, compile it via the Java Compiler (javac) to HelloWorld.class, and then we can execute via the JVM.

For the EVM, we have HelloWorld.sol, we compile and deploy to address 0xc. We can execute functions inside of 0xc.

Consider 0xc as the address pointer.

For this article, we consider a stateless EVM. No data will be saved. Consider the stateless function;

def f(a,b):

return a+b

Two important parts here. One, did the EVM compile the code correctly, and Two, if we execute f(1, 1), does it execute correctly.

For both of these, we provide a zk-SNARK enabled compiler, and a zk-SNARK enabled EVM.

Execution of f(a, b) will provide witness “b” : 2, ‘a” : 1, “out0” : 3 as well as the Proving Key pk.

Execution in the EVM (or other compatible VMs) is ensured in a trustless environment. Consensus is no longer required for execution, EVM processing can be asynchronously parallelized, allowing for trusted off-chain execution.

Stateless Computing

The above however describes stateless computing.

Use cases include;

• Machine Learning
• Protein Folding
• Image classification

For dApps stateful computation is required. Standard options are available;

• IPFS
• Standard centralized data stores
• Anchoring Chain
• Decentralized Storage

To achieve state we must defer to consensus. Current options;

• Each node executes the full state transition (Ethereum)
• State updates are applied after verification (Leader based)
• State differences are applied after attestation

In TEE or Zero Knowledge proof systems attestation can be used. Attestation could be more expensive than the actual execution. Also has concerns towards forked states and resolution.

Achieving Fast Attestations

We will use graph computation algorithms to achieve fast attestations among a large-scale network of distributed nodes.

We use mutual attestations and gossip protocols among nodes to collaboratively construct a web-of-trust.

A node attests the integrity of other nodes. It collects the attestation results. which are modelled as its Direct trust to a target node and stored in its local database.

Di,j(t) = tn AHj(t)2k-(t(tn))

Di,j(t) is calculated by combining the timestamps maintained in the attestation history, which records the attestation tickets towards the neighbour (Nj ). It is an integer interpreted as a bitmap vector with the length of k. Each bit represents a timestamp one step away from its higher adjacent bit, and the highest bit indicates the time t. A bit is set to 1 when an attestation is performed at the step it stands for. Thus, the direct trust, calculated as above, reflects all the recent successful attestations up to time t. AHj(t) denotes the attestation history for node Nj at time t. As a step is defined as minimum attestation interval, different timestamps t in AH do not indicate a same bit index. We can thus safely use summation instead of bitwise OR (“|”) for setting the corresponding bits.

This definition allows two evaluation values be compared. The larger one indicates the more recent an attestation is performed, and hence indicates a higher trust credibility. This property is used for modelling the Transitive Trust.

Direct trust values are propagated among the logical surrounding neighbours by exchanging the corresponding kernel contents using the gossip protocols. Therefore, from the kernel, a node is able to determine how its neighbours attest to each other. This thus helps modelling the Transitive Trust, which is represented by a path of connections.

The gossip protocols allow each node to disseminate the trust relationship it gathers to other related nodes, so that redundant attestations will be reduced. There are three ways of gossip dissemination;

• Gossip about gossip: when the local node and a target node only have few common in their Kernels, the gossip about gossip protocol is initiated to directly exchange their Kernels.
• Gossip about reduced gossip: when the local node and a target node have much common in their Kernels, the gossip about reduced gossip protocol is initiated to only exchanged the complemental parts.
• Targeted gossip: any time when a local node updates its Kernel, it identifies the set of target nodes who will be benet from the updated data and sends the updated data package directly to the set of nodes.

Gossip about gossip enforces batched exchanges of attestation relationship data, this allows a new node to quickly obtain the up-to-date global data. Reduced gossip allows two “not-too-closed” nodes to exchange their data in batches, while reducing networking overheads. Targeted gossip allows new attestation relationship information to quickly propagate among the “closely-related” nodes to without putting too much burden on the network traffic.

The combination of these three gossip strategies achieves both quick information propagation rate with low networking overheads. With transitive trust relationship gathered by remote attestations and gossip protocols, The graph further builds a`Conspiracy Breaching’ model for nodes to illustrate how intense a target node is attested by other nodes. This model helps locating the nodes who have the greatest `diculties to lie’. Meanwhile, small world network algorithm improves the networks’ robustness.

Execution Trust

Even at a software architectural level we can assume the above gossip about gossip protocol to achieve a trust score for adjacent nodes and spread this information via a graph structure. This allows us to achieve trust ratings, this could branch out into one of two choices;

• High trust score, apply state diff
• Low trust score, execute state transition

Decoupling Token Value

A fee based token economy marketplace will be used to ensure fair value.

Tasks are associated with a bid: the amount of coin offered for performing the task. Bidders can adjust the bid on their pending tasks to expedite their execution. Workers will decide if a bid is sucient for them to execute upon. Since this is a competitive market, workers will execute work when profitable for them to do so.

When work is completed the attestation and state diff are provided. The state engine updates state diff based on attestation score and assigns the bid to the workers coinbase.

Pledge Penalty

Workers will submit a signed pledge of staked coins as collateral. This becomes forfeit if attestation proves malicious behavior.

Contract Life Cycle

User a creates ERC20 smart contract sc

def transfer(to,val):

to.add(val)

this.from.sub(val)

Compute nodes need local state as well as a global shared state. (State Redundancy)

Transaction in Ethereum are ACID (Atomicity, Consistency, Isolation, Durability).

For scalability this should be BASE (Basically Available, Soft state, Eventual consistency).

We assume n nodes in the ecosystem.

We assume k nodes are willing to execute an instruction.

k/n nodes create sc.

k/n nodes provide attestation and state trie. (Redundant step*)

a has a balance of 10, a sends 10 to b in tx1 and 10 to c in tx2

Compute Node cn1 processes tx1, valid state.

Compute Node cn2 processes tx2, valid state.

Consensus layer can only accept one state and must inform the other of incorrect execution.

Privacy Preserving

Encrypted state

Additional Improvements

FastVM

• Reducing the data word size from 256 bit to 128 bit
• Introducing LLVM JIT as the execution engine

https://github.com/aionnetwork/aion_fastvm

Solidity++

• EVM compatibility
• Asynchronous Semantics
• Contract Scheduling
• Standard libraries
• String manipulation
• Floating-point operations
• Basic mathematical operations
• Containers
• Sorting

Event Driven

In the protocol of Ethereum, a transaction or message may affect the status of multiple accounts. For example, a contract invocation transaction may cause the status of multiple contract accounts to change at the same time through message calls. These changes occur either at the same time, or none at all. Therefore, the transaction in the Ethereum is actually a kind of rigid transaction that satisfies the characteristics of ACID (Atomicity, Consistency, Isolation, Durability), which is also an important reason for the lack of expansibility in the Ethereum.

Based on considerations of scalability and performance, we adopted a final consistency scheme satisfying BASE (Basically Available, Soft state, Eventual consistency) semantics.

Specifically, we design an Event-Driven Architecture (EDA). Each smart contract is considered to be an independent service, and messages can be communicated between contracts, but no state is shared. Therefore, we need to cancel the semantics of synchronous function calls across contracts, and only allow message communication between contracts. The EVM instructions affected are mainly CALL and STATICCALL. These two instructions can’t be executed immediately, nor can they return the result of the call. They only generate a request transaction to write to the ledger. Therefore, the semantics of function calls will not be included in this instruction, but rather sends messages to an account.