Interplanetary Linked Computing: Separating Merkle Computing from Blockchain Computational Courts
I see a Blockchain Computer (such as Ethereum) as having 2 parts:
- A Merkle Computer (hash-linking and easy verification of state).
- A Computational Court (consensus and enforcement of state).
The former provides a way to verify code execution & the latter is a way to enforce it.
Currently, the computational courts are bundled along with the Merkle computers in blockchain computers (it is always on). Merkle computing provides various benefits that are worth exploring on its own. Current computational courts (blockchains) are the equivalent of enacting the death penalty for jaywalking. As James Young also put it: “What if you had to go to court for every business contract that you sign?”
More diverse and varied computational courts are possible, and needs to be explored.
These thoughts have been gathering for several months now after several discussions with folk in the space: from talking to Christian Reitwiessner in Berlin, to Juan Benet in Shanghai. It was buffeted by thinking about how we more effectively scale verified computing. Trent McConaghy’s ideas around decentralized autonomous AI organisations and Christian’s original blog post on TrueBit sparked deeper thinking.
This post is dense and covers various topics: linking to various articles, ideas & code. It’s likely that in the future I’ll expand more on these concepts in separate posts.
Merkle Computers
Merkle computers are different to normal computers in that they hash-link state changes sequentially (attached to a log) according to a state machine, and use Merkle Trees to verify contents of the state efficiently. Bitcoin & Ethereum are examples of systems that contain an internal Merkle computer.
This excellent infographic from Yunyun Chen explains the benefits of encoding information into a Merkle Tree using bananas. 🐒
The Merkle Tree data structure is currently used in blockchains (such as Bitcoin & Ethereum) to verify contents of its state.
This is especially useful in distributed computing contexts (in blockchains), where states have to be verified due to interoperation with strangers (that can be potentially nefarious or antagonistic).
In Bitcoin, this is used to verify if a transaction occurred in a block without having to contain/download the whole set.
In Ethereum this is extended to also verify *other* state easily without having to retain the whole state of the distributed computer:
eg, a query like: “Tell me all instances of an event of type X (eg. a crowdfunding contract reaching its goal) emitted by this address in the past 30 days.” is now possible.
Having the state of a computer stored in a Merkle Tree data structure is useful for not only verifying its state more efficiently, *but* it also allows one to easily verify the computations itself.
Canetti, Riva & Rothblum designed a “Practical Delegation of Computation using Multiple Servers” that relies on Merkle Trees. It’s implementation does not employ Ethereum’s modified Merkle Trees (Patricia Trees) which would be more useful as it allows for faster recalculation of the trees. The delegation scheme forms the basis of TrueBit, a scalable computational court, designed to be deployed on Ethereum.
In the event of delegation, if a dispute occurs (the final states don’t match), an arbitrator can verify who cheated. If one didn’t use hash-linking or Merkle Trees for the state, then an arbitrator would need to start at the starting state and run *all* the computations themselves in order to verify, which is cumbersome and costly.
Since one is hash-linking state changes, and encapsulating state into a Merkle root, at some point an invalid state change can be caught & verified in less time (logarithmic) than doing the whole computation. If one has access to the state change mechanism (state A -> do computation X -> state B), then one can employ a binary search over the state change log, and apply the state change to verify when the Merkle roots differ between state changes. It’s a bit more complicated than that. Christian Reitwiessner has more technical explanations of how this works with regards to employing an interactive verification of this on Ethereum.
This ability to verify general computations are not used currently in blockchains, because blockchains have built-in courts (they maintain constant verification as part of their functioning). One can’t commit to the computer an invalid state, and everyone who runs the network (redundantly) verifies it. As Colin Platt puts it (paraphrased): “The current system is reconciled at every state change.”
The use of a cryptographic token in a blockchain (solves coordination & other problems), and the benefits of consensus around a shared database allows the state to remain valid as it functions.
Computational Courts
A Computational Court can be defined as a system that enforces code execution through only using code (not humans). A blockchain computational court enforces code execution through economic incentives.
Blockchain courts currently work in a very strict way. Invalid computations are not possible. Consensus algorithms (such as of Proof of Work), are directly tied into the Merkle structures of blockchains. The work being done to verify & secure it produces tokens that in turn is required to produce state changes. Each block allows rules that gives the miner the ability to issue themselves their allotted bitcoin/ether. The nonce that conforms to the work requirements is a part of the hash of the block. The computational court is thus directly a part of this specific Merkle computer.
The economic incentive design is a Schelling (focal) point to converge on a computer and its state by not requiring a specific actor (from a systemic perspective) to interact with it.
This is at odds with how law & reality currently works. We can do whatever we want (within limits of physics), but only be punished retroactively. Honest participants don’t need to invoke the cost of the courts. We can construct our own “shared delusions” as much as we want, but when we want something enforced when a dispute in reality happens, we “pay” the courts and accept the agreed upon constructs of that specific court (legislation).
Merkle Computing is useful in that it allows:
- Audit trail of computations.
- Cheap, cryptographic verification of computations.
- Content-addressing of computational state.
One could potentially want distributed computing without the desire for strict enforcement *before* it is required.
Blockchain courts are useful in that you:
- Have guarantees of execution enforcement at the *time* of execution. Many applications will want this feature. i.e., there’s no requirement for the invocation of a court or dispute resolution periods. This guarantee, although more costly at the onset, might sometimes be cheaper if a dispute is costly. It depends on what guarantees are desired.
- It allows for more dynamic games (because participants don’t have to coordinate on a court). Anyone can enter/exit games (like a decentralized exchange).
(Note: A “game” here is defined in relation to game theory: games of coordination.)
However, some distributed, games start and finish with a defined set of participants, and have no problem with a dispute resolution period. We thus use Merkle computing to interact, and use its features for verification only in the event of a dispute. We have the audit trail of computations and can verify cheaply where it went wrong and who is to blame. This post explains the troubles with implementing a game of Chess on Ethereum.
CBOR + IPLD as a Merkle Computer
One can design a Merkle computer that lives on InterPlanetary File System (IPFS). Using Concise Binary Object Representation (CBOR) objects conforming the Interplanetary Linked Data (IPLD) standards , they can follow a hash-linked structure. Orbit uses the event-log system to design a chatroom on IPFS. Mediachain has an RFC on how to modify metadata over time. The objects that are hash-linked would conform to a state machine. Theoretically, one would be able to remodel the Ethereum Virtual Machine in CBOR and then have it be able to uploaded into IPFS. However, the EVM is already a Merkle computer (stored in its own native formats, rather than in CBOR).
Recently, IPLD have started changing to allow one to read & traverse the Ethereum computing substrate in IPFS itself. Aaron “Kumavis” Davis has been building components to read public Ethereum state from IPFS. It’s exciting. Here’s a resolver for reading Ethereum transaction information in IPFS.
Moving to a substrate where *all* Merkle computing takes place is an exciting idea though. Ideally, Ethereum, and other Merkle computers would live next to each other. And so far, I hope that moves to IPFS. We won’t just then have an Interplanetary File System & Interplanetary Linked Data substrate, but also an Interplanetary Linked Computing (IPLC?) substrate.
For example, at Ujo, we are using IPFS to store the audio files and artist images. We plan to use the the COALA IP spec + CBOR IPLD for interoperation of intellectual property across blockchains. Ethereum is used for coordinating economics and business logic of artist rights management. If you add the ability to link to computing states, you can potentially link directly to outcomes of events in rights management. e.g. “Here’s the outcome of a dispute over copyright claims.”
For more info on Ujo’s technical roadmap, have a read:
Interplanetary Linked Computing
As is, without employing the need to verify states, designing computing around having hashed audit trails results in the ability to recreate state from a genesis state, and link to specific states of various computers. There is thus no specific computer anymore, only *many* computing states, and we can link between them and retrieve them.
This has benefits for all kinds of auditing. Colin Platt has a good example:
The implementation of a separate Merkle Computer to allow parties to handle calculations offchain, reporting state at set frequencies then settling transactions net at the Computational Court at pre-agreed intervals could allow for, not only a drastically improved through-put of the blockchain, but a greater ability for counterparties to manage and settle unfunded transactions (i.e., derivatives positions) fully within a verifiable and “blockchain-friend” environment. As you suggest, when a transaction settles, counterparties can retroactively check the position against known States over time and take a contentious calculation to arbitration only when required. This dramatically reduces the cost when compared with the current system in which calculation must be done at every “State” and then reconciled.
Knowing, and being able to access verified computing state directly can also have influences on things like AI: using this model and thinking from Trent McConaghy, it could result in being able to link to *how* an AI made choices, available for all to see and re-compute: in a open substrate.
Storage will increasingly become negligibly cheap. Our bottlenecks in the future will be bandwidth, and energy. Thus along with building an archive of all information, we can build an archive of *all* computing states. Having a hashed state is already useful in large, distributed computers (like Ethereum). Using systems such as IPFS, we can retrieve computing states from our closest peers. In the far future, it also means when doing interplanetary computing, we don’t have to point to a computer on Earth. We can do content-addressing of computational states (ps: love the “interplanetary” prefix for precisely this reason).
Having cryptographically verifiable computing state means one can further also divorce hardware away and the reliance upon it. Urbit, a “personal OS”, is experimenting similarly with this vision.
“Urbit’s state is a pure function of its event history. In practice it uses a memory checkpoint and an append-only log. Every event is a transaction; Urbit is an ACID database and a single-level store.”
Consensus
As described previously, currently consensus/verification is baked directly into the Merkle computers. However, this can hopefully be done orthogonally. “Block” objects are containers hash-linking to state changes, with its consensus information embedded into it.
The block system (in blockchains) helps to come to consensus on the order of state changes. Coordinating around one single state-change log without this coordination tool is more difficult.
I’m not 100% sure, technically when there are multiple, dynamic participants, how you can achieve this. But it seems possible. Perhaps there’s multiple state change logs (state log per application?), or one could employ conflict-free replicated data types (used in Orbit) perhaps to merge them safely?
However, if possible, separating the state change log from the consensus log would mean one can more easily swap out consensus protocols (if desired).
*Other* Computational Courts
The first example that comes to mind in using Merkle computing with other types of computational courts is to use Ethereum as an arbitrator in the event of a dispute. This would allow scaling of verified computations above and beyond the strict internal court.
An example of this is having a pre-arbitrator for participants’ state machine, bonded to a state channel on Ethereum. If there’s any misbehavior, the arbitrator can be invoked, and paid for recreating the state and (cheaply) verifying it, settling the dispute.
- Opt into a state channel with an arbitrator (bonded with deposits from participants). The arbitrator specifies what oplog (operation log) state machines it will be able to verify.
- Pass along signed hash in the channel, that is the head of the oplog. Each participant updates the head according to rules, and passes messages around as appropriate. Each update is a hash-linked state change.
- If everything goes according to plan, both participants can sign to get deposit out of escrow (with a fee to the arbitrator).
- If a dispute occurs (someone tries to cheat), then an appeal can be made to the arbitrator.
- The arbitrator then takes the head of the oplog and verifies if this was allowed or not. The cheater then loses their deposit. The arbitrator takes a cut for its service.
Without requiring much additional coding, this is possible right now. If someone wants to roll with this, let me know. I have a more detailed implementation in mind.
Furthermore, since CBOR can be deserialized in Ethereum, it could even be possible to automate arbitrators, teaching it how to verify different styles of Merkle computers, and further reduce the marginal cost of computing dispute resolution. For example, Martin Lundfall has written a Solidity contract to verify an IPFS hash. In another example, Christian Reitwiessner has written an scrypt verifier in Solidity.
The extreme of this is to move towards finishing and implementing TrueBit, which will create a generic, trust-less, market for *any* computation on Ethereum: even being able to verify the outcomes of large neural network data-sets and computations. Tim Watts wrote a simple Perceptron in Solidity. However, with the ability to verify outcomes outside Ethereum, you don’t have to write this in Solidity itself.
Limitations
I’m not certain at all how *fast* Merkle computing can really become, and whether it will mainly be used for a subset of computing goals (rather than replacing all computing with these additional audit-ing capabilities). I’m also not certain whether putting it into a networking layer like IPFS makes sense. Bandwidth might limit effective ability to propagate computing. For example, Ethereum is *very slow*, currently, compared to other computers. State changes are enforced at 15 second intervals, and is currently not faster than a single computer. Sharding & the use of state channels could improve the speed radically.
It remains to be seen how it will all evolve now that we have invented Merkle computing & computational courts. It will be interesting to explore its full potential in the coming years.
For humans, opting into computational courts means it has to be better than our current social courts. We can now create a market for courts, and we are exploring how to make better courts with this technology. It’s likely that the first use of these courts will be around systems that want global enforcement, where global courts don’t reach atm (or ever will):
However, in an only machine-to-machine economy, the only courts are computational courts. Empowering machines to coordinate without humans, and adding in scalability of AI to make decisions about markets faster and better than humans will cause some crazy, weird things to happen and potentially *huge* amounts of economic value.
Decentralized, virtual worlds (and simulations) will also not have access to social courts. Experimenting in this layer could have useful implications for how our current courts work and run.
Conclusions
Having consensus on computing outcomes are useful, in that many applications can without requirement of arbitration connect with each other without human permission. Thus, something like Ethereum is useful: consensus on many applications in the same computing substrate.
Blockchain computers introduced Merkle computing. Currently the verification & enforcement are in the same system (blockchains).
On the edges, however, cheaper and more varied Merkle computing could open a much wider, more open, audit-able, shared & verifiable computing substrate.
Exploring more generic and varied Merkle computing with different styles of computational courts could lead to some very interesting, emergent applications.
It’s exciting.
Thanks to the following folk who have sparked ideas in various places the past few months and gave feedback on this topic and post. Juan Blanco, Kirk Dameron, James Young, Mike Goldin, Ameen Soleimani, Aaron “Kumavis” Davis, Juan Benet, Karl Floersch, Christian Reitwiessner, Trent McConaghy, Greg McMullen, Tyler Reed, Joseph Lubin, Joseph Chow, Colin Platt, Igor Lilic and Martin Lundfall.
Liked this piece, sign up here for our weekly newsletter!
Disclaimer: The views expressed by the author above do not necessarily represent the views of Consensus Systems LLC DBA Consensys. ConsenSys is a decentralized community with ConsenSys Media being a platform for members to freely express their diverse ideas and perspectives. To learn more about ConsenSys and Ethereum, please visit our website.
