Part I
Sometimes Ethereum is compared to a singleton Virtual Machine. While this is correct in some sense; I think it is a bit more. First of all what is a singleton in a distributed system? It is merely a set of values that some threshold of participants have come to consensus on. A Virtual Machine is a computational environment that is isolated from the physical computer and from other environments.
A hypervisor allows the physical machine to be multiplexed into many VMs. According to this definition a common hypervisor is the web browser where webpages are VMs. Another example of a hypervisor would be Ethereum as each contract gets its own isolated computational environment.
There are many differences between the common web browser and Ethereum, but one of the more interesting ones is how VMs communicate and interact with each other. Web browsers don’t provide a way for VMs to directly interact while Ethereum on the other hand provides some simple mechanism for VM interaction; the opcodes CALL, DELEGATECALL, CALLCODE, CREATE. In this post will explore the question; What other rules could exist? Can we generalize VM interactions and provided an abstract framework for these interactions? And from this framework can we reason about distributed hypervisors?
Most of this post will resemble ambient calculus but there are several notable differences from ambient calculus and what is presented here. The diagrams can be thought of as bigraphs but they should also be self explanatory. Part I will describe the rules of ambients and then apply them to Ethereum. Part II will discuss scaling in the terms of ambients as laid out by part I.
What is an Ambient?
An ambient is a bounded place in which computation can occur. A boundary determines what is inside and what is outside an ambient. For ambients we call this boundary a membrane. The area inside an ambient is hierarchical namespace. Objects can exist inside an ambient. The objects are addressable via the namespace. There are three base elements in ambient calculus. Objects, Namespaces and Messages.
Hierarchical Namespaces
One of the most familiar namespace is the file system tree. Namespaces allow us to identify objects with paths or names. Namespaces here have the following properties
- For every possible path there exists a null or an object
- At any point in the namespace you can move up or down. This is what is implied by hierarchical.
- Every path has a root associated with it. The root uniquely identifies the content for all the paths below the root. You can think of the root as a pointer to the content of the path.
- Paths can be read from or written to
- Messages can be sent along paths to objects
Object Types
What is an object? It is just a value. In real life computing its just some data. This data can be interpreted in several different ways. Any Object can be read as data. The pink circle is some data that exists in the grey ambient.
Objects can also be interpreted as ambients. This allows ambients to have sub-ambients. Here the orange and grey circles are ambients.
Objects can also be interpreted as ports. Two or more ports form a I/O channel. Channels allow messages to be sent to ambients in a different namespaces. Channels can be thought of as tunnels through an ambient’s membrane. Both the entrance and exit ports must exist somewhere in a namespace. Here the green objects represent ports.
Lastly messages can also be considered to be an object. Messages are special since they are defined as objects in motion or thought of as objects with velocity.
To Recap; Objects can be the following types
Objects :: =
Data
Port
Ambient
Message
Messages
As stated above messages are objects that are in transit. Messages can be sent through a namespace and through channels. Messages have the following properties that are set by the systems message handler. They are not all intrinsically part of the message but as you will see later they make working with messages easier.
- To – The path to the destination of the message. This is immutable.
- From – The sender of the message. This is immutable.
- Type – The type of message. This is immutable.
- Data – The message’s body. This is immutable.
- Heading – The destination relative to its current position. If `Heading` is `null` then the message has arrived at its destination and will travel no further. This is not directly encoded in the message but instead set by the systems message handler. This is mutable.
- Direction – Which direction the message is traveling. It can either be going ‘out’ of the ambient or going ‘in’ to the ambient. This is mutable.
Message Types
Message have the following types which have corresponding commands used to send them.
Set(path, value) - Sets a path to a given value
Get(path) - Gets a value of the given path
SetRoot(path, root) - sets the root of `path` to `root`
GetRoot(path) - Gets the path’s root
Call(path, data) - Sends a message along the given path
Connect(to, from, options) - creates a channel between two paths.
Deleting
It might not be immediately obvious how to delete an ambient or other objects. To do this we use the `Set` and `SetRoot` message.
The Set message sets the value of a path. Setting a path to null is equivalent to deleting the contents of that path. For example Set(‘pinkAmbient’, null) Here the pink ambient is set to null. Note the the orange ambient was not deleted.
The SetRoot message sets the root of a path. If the root is set to null all the path values below the root will become null. For example CopyRoot(‘pinkAmbient’, null) will set the pink ambient’s root to null which will also cause the orange ambient be to null.
Of course if we did something like SetRoot(‘a’, ‘pinkAmbientsRoot’) we would copy the pink Ambient and all of it contents to path “a”
Iterating the through a Namespace.
In many cases it useful to iterate through all the ambients in a given namespace. One way we could approach this is to `get` each path in the namespace. But the problem is that most namespaces are infinite. A better way would be to provide an explicit iteration method. Let’s add a message
Next(path) - Given a path return the next non-null path in the namespace.
This implies that namespaces all must have an order. Also this provides us with a nice way to build more complicated ambient operations like merging two or more ambients. We also need this to build type checking.
Membrane computing
The ambient’s border is its membrane. It can filter message coming into and going out of it. For example the if the grey ambient sends a Set(‘blueAmbient’, null) message to the path of the ‘blueAmbient’ it will go through the membrane of the orange ambient. The orange ambient can decided whether or not to let the message pass through.
A Membrane API
Lets walk through a small example of what programming ambients might look like.
Ambient A is trying send a message to ambient B but the message has to go through Ambient C. Since A is a sub-ambient of C, C can control this message. Here is what an api for dealing with messages might look like. Let say that we have a function ‘onMessage’ that gets ran whenever the ambient gets a message. Here is what C membrane could look like.
/** * Allow any message to pass through the membrane except messages from Ambient D * @method onMessage * @param message - the message that is leaving the ambient * @retruns Boolean */
function onMessage(message)
if(Message.sender != ”A” && Message.direction == ‘out’)
Message.heading = ‘D’
C filters any messages coming from the path ‘A’ that are going out of it. Instead of letting the message go to its intended location C reroutes the message to location “D”. Notice how C set the heading on the message. If C set Message.heading to null then the message would stop there. C can only decide where to forward the message or to stop it.
The ability of ambients to filter and decide which message can travel through them is an important one. This is also known as Membrane computing. It will allow you to build flexible and easily composable contracts. Especially when it comes to administration of sub-contracts.
Mapping ambients to a Ethereum
Now that we have the basics of ambients let’s apply them to a one of our favorite data structures, the merkle tree. To start you might have already recognized the fact that a contract in Ethereum is like an ambient and the namespace is provided by the merkle tree.
Namespace ::=the merkle tree
This could be visualized like this
In Ethereum each ambient has an address that is 20 bytes long and looks like the following 0x1158c3c9a70e85d8358972810ed984c8e6ffcf0f. Ethereum ambients have storage that allow them store store arbitrary values permanently. Storage is accessed and manipulated with the SSTORE and SLOAD opcodes. The equivalent to these are the set and get messages. Also command Call is equivalent.
SetRoot, GetRoot and Connect do not have equivalents in Ethereum currently. SetRoot and GetRoot would read from and manipulate the underlying mekle trie.
Now we are going to deviate from current Ethereum to Ethereum + Ambients. Let us say the contract 0x1158c3c9a70e85d8358972810ed984c8e6ffcf0f sets the value ‘doge’ at the addresses ‘coin’ which is 636f696e in hex. The address 0x1158c3c9a70e85d8358972810ed984c8e6ffcf0f/636f696e would then contain the value ‘doge’. Also ‘doge’ could also be interpreted as code if a Call was made to that path.
Personal Accounts
Lets use a personal Ethereum account as an example. For convenience we are going to say the address of the account is “accountA” which will be represented as the grey ambient. This ambient would hold the basic signature validation code as seen in the currency and crypto abstraction. If the user wanted to place a spending limits on herself then she could create a “Savings Account” which would only permit a certain amount of ether to be spent per day. Furthermore the user could create her own custom Name Reg or other financial apps. The hierarchical nature of the ambients allows you to build up administrative “zone”. They can make code very modular since the “saving account” and other contracts don’t need to have any code dedicated to checking if the user is an admin or checking other credential since that could be done by the accountA’s ambient.
In this section we will explore some ideas about scalability in terms of ambients.
The basic idea of scalability is fairly simple. Most methods proposed so far involve these properties:
- Separating some part of the state into a shard that is processed independent of the other shards
- Some sort of cross validation; where some portion of a shard’s work is checked by other shards which is usually triggered by cross shard communication.
We are also assuming we have a Proof of Stake algorithm like Casper and this algorithm is implemented in a set of ambients. Along with casper we have a currency ambient that tracks the amount of ether each account ambient has. These ambients are grouped together into the system ambient. There maybe many more ambients in the system ambient but for now we will just consider these.
For now we will simply assume that casper works and produces the correct state for the “Ethereum Ambient”.
Sharding
If Ethereum is successful, the volume of transaction will increase over time. After a while a high volume of transactions will cause the price of gas to increase. At a certain threshold determined by a Threshold function the Casper ambient will produce a shard. It should be noted that only from the casper ambient’s perspective is Ethereum sharded. Everyone else sees Ethereum as one continued namespace extending through many ambients.
There is some threshold that is needed to create a shard in Casper. This is not the focus of this post but we can image some of the parameters it might be based off of. It could use gasPrice to transaction ratio. Or could it use a voting system or a bidding system or combination of all them.
Besides the Threshold function we will assume the following about Casper:
- Anyone can contest a state transition.
- Validators are randomly assigned to shards. These form a validation group that run Casper for that shard.
- Validator may be assigned to more than one shard
- New shards must be initially validated by all validators
- The total amount in bond in a validation group of a shard should be equivalent to what the shard is worth.
Creation of Shards
- For now we will assume that new shards will start out as an empty ambient. But keep in mind this might not always be the case- for example a particularly successfully dapp could perhaps pay the Casper contract enough to make it worthwhile for the validator to create a shard out of it. But for now it is empty.
- The first thing that happens to the new shard ambient is the system contracts are copied to it. But we don’t want an exact copy of the current system ambient. This is because it contains the current state. We want an empty currency contract and an empty Casper contract, etc. To do this the Ethereum ambient must have an “abstract” system ambient from which we then copy. We can image the abstract system ambient would have a message handler that only allowed messages that were copying it. It could looks something like this:
function onMessage(message)
The new shard would send a `getRoot` to the abstract system. Then it would use `setRoot` internally to copy the abstract system its namespace.
- Part of the threshold function might be pledges from other ambients to move to a new shard once it is created. When the new shard is created, all the accounts that pledged to move are automatically moved to the new shard. This is done after the system ambient is in place. The accounts are also copied with the `CopyRoot` command.
- After they have been copied their original address is replaced by a port (created by the “Connect” command) creating a channel to their new account on the new shard.
- The currency contract then sets the amount of ether that the shard has to the sum of the accounts that pledge to move.
- Lastly the in the new shards currency, the contract is populated by the values of the copied accounts.
Fractal chains?
The end result will be that the top level ambients no longer “see” the individual accounts that are in the new shard, instead it only see the value of the sum of the account on the new shard ($82 in the diagram). While the new shard’s currency contract keeps track of the individual accounts in the shard. This resembles a fractal in the way that part of the whole is encoded in every section of the structure.
Also if anyone uses the old address of an ambient that moved, their messages will be forwarded to them via the channels. There are some disadvantages to using the channels; 1) its will be more costly 2) there will be higher latency.
Financial Isolation – Counterfeiting Attacks
The shards can be seen forming a hierarchy; each shard ambient keeping track of its accounts and the sum of the accounts in its children shards.
This creates a strong guarantee of the correctness of account balances. No shard can create counterfeit currency and send it to another shard. Furthermore the security is additive. Meaning that the more shards that a message crosses the stronger the guarantee that it is correct. We are assuming that every validation group will check that transaction going through it. If a transaction is going from shard C to C.A.B then shards C, C.A and C.A.B all will check the transaction and ask the shard C for merkle proof of the sender’s account. If the transaction was found to be invalid after the validator’s approved it then the validators in all three groups would lose their deposits. If accounts were defrauded they would first be refunded from the validators deposits.
Let’s consider a long range counterfeit attack. This is where a validation group on a shard creates an account with an invalid amount of currency associated with it and then they just leave it in the shard. If they ever try to move it from the shard the parent validation group will request a complete transaction log that shows how the accounts got its money. At this point the attack would fail unless the parent validation group was also compromised. And in a long range attack the attackers wait until the parent validation group is compromised. The best way to counter this is to make each validation group responsible for the complete history of its shard and not to release the bonds to unbonded validators after several epochs. This gives the current validation group an incentive to check the previous validation groups work.
One way in which a validation group can check the previous validation group work quickly is to just sum the transaction graph. We can think of all messages that transfer currency as forming a directed graph. Since we know the global amount of currency that the shard has, a validation group just needs to sum up the total amount the accounts had for each block in the previous epoch and check it against the known global amount.
To recap, several properties that can increase security are:
- Give the Parent Validation group an incentive to check the work of their children.
- Give validator an incentive to check previous work
Validation Group Groups (Hierarchical validation groups)
Validators may have to put up a very high bond to participate in validation. The amount of bond needed is a function of the target number of validators which is a function of the number of shards that exists.
But this poses a problem since if there were a higher number of validators it would be harder to coordinate a bribe attack on a shard but on the other hand Casper can become inefficient when there are large number of validators. One way this might be solved is to have validators themselves composed of validation groups. The validation group would run in a separate ambient on a separate blockchain from Ethereum.
In the validation group ambient, work is further subdivided into smaller chunks. Each individual validator would get assigned several ambients from the shard that validator group was assigned to. This should effectively allow even a small device to participate in validation increasing the total number of participants that briber would have to potentially coordinate with.
Channels outside the Ethereum ambient
To do this the validation group would create a new ambient that was connected by a channel to the validator group’s ambient. You might wonder how it is possible to link to an ambient outside of Ethereum. But underneath its straightforward.
Initially there would only be a validators account controlled by multisig on the Ethereum blockchain. Then the validators would create their own blockchain (represented as an ambient) which would have the same system ambients and Casper ambients as Ethereum. After creation, the validator group would connect the two ambients with a channel. Any message entering or exiting the ports the must be agreed upon by all the validators, so the channel should also be protected by a multisig. The code for the multisig would exist in the ports message handler. The channel could only be followed by those running both sets of ambients. Nodes running just the Ethereum ambient would see the channel but would not be able to follow it.
This provides a pattern that could be elsewhere as it provides a generic way to connect arbitrary ambients to the Ethereum blockchain. These ambients could stand for the state of your personal computer or an arbitrary feed of data. Beyond the examples given here, there are many other design patterns that make thinking in ambients useful. While there are still many lacunae ambients could be a useful model for computational environments. Ambients adds a new dimension to Ethereum’s hypervisor. Quite literally too. It allows for contract to be even more modular and provides for a convenient way to create administrative domains and model many everyday situations.
NOTES and PROBLEMS
Here are some additional things to think about.
- SetRoot would have to fail if the root didn’t exist in the current namespace. If SetRoot was explicitly used the parent namespace (../<root>) then that tree would be copied to the namespace. If this happened between shards the tree would be serialized into a transaction.
- Message
- All messages are assumed to be async. messages can timeout.
- Messages all have a response. The response need to be recoded as transaction on requesting shard and the responding shard.
- Blocks would need two parts; in transaction and out transactions.
- Capture and delete – The sibling ambient sets a value to a path above another sibling with code for to create an ambient that deletes all of its sub-ambients.
- Solution 1 any action that might affect a sibling ambient must go through its message handler
- Solution 2 an ambient could define a message handle for all internal message that explicitly disallowed certain types of messages.
- Solution 3 reintroduce capabilities as presented in ambient calculus