An Intro to TrueBit: A Scalable, Decentralized Computational Court.
or: “An Intro to Panopticomputers: Code Execution Courts for Scalable, Decentralized Computation”.
The Ethereum community never ceases to amaze me. So many smart people working at the fringes of what’s possible. We haven’t really scratched the surface of what’s possible in the current iteration and we are already seeing amazing new opportunities come to the fore.
For the unenlightened, Ethereum can be described as a distributed “world computer” using blockchain technology. It allows developers the ability to upload code to a blockchain, upon which it executes the code when activated to change some information on a shared ledger. In other words, you can apply arbitrarily complex state changes to a shared, public (relatively) immutable ledger. Every node in the p2p network runs these state changes, whilst specific computers (the miners) make sure these state changes are difficult to reverse (by being rewarded the subsidy & fees). In order to execute state changes & computations one pays proportionally with the cryptocurrency of the platform, ether. The more computations you want to do, the more you will pay for it. The amount of computations are measured in a separate unit, called “gas”.
An issue with this current model (Ethereum being young & new) is that whilst it allows a rudimentary, distributed world computer, 1) all nodes still need to run state changes although they aren’t being rewarded for it in order to stay at the top of the current truth of the shared ledger (dubbed the “verifier’s dilemma”) & 2) it’s slow & can’t process large amounts of computations & information. Because all nodes need to run computations & because the state changes are based on ordering of transactions, Ethereum, although distributed, is basically as fast as its slowest computer in the network. There are scalability solutions in the pipeline that will parallelise transactions & drastically improve the amount of transactions it can run. Not all computers in the network will need to run all state changes in the future. It will move towards a model where it more accurately compounds the computers in the network to form a large single distributed computer. These solutions are still ways off and are actively being worked on.
Another interesting model to achieve grand scalability is to use Ethereum as a computational court. Piper Merriam designed a computation market. It is ideally used when it is too costly to regularly run these computations on Ethereum. It saves costs by doing the following:
- A developer uploads the smart contract code.
- It specifies in the market that it wants to execute a function with certain input. The cost it puts up to pay the market is less than the cost to actually run it on Ethereum.
- A 3rd off-chain party runs the computation and posts the results to the market. It does this along with a deposit that will be enough to execute the actual transaction in case of a dispute.
- Another third-party can also run it. In the event that it sees that another 3rd party lied in the market, it can force the on-chain execution to happen with that deposit they put down. If the submitter was originally correct, they get their deposit and the amount they should be paid. If they were wrong, they don’t get the payment and get the rest of their deposit back that hasn’t been spent on the execution.
- After a certain period, if there were no challenges, then the answer is “accepted”, upon which the payment is made and the deposit can be returned.
In this market, one only needs one honest actor in a sea of malicious actors. It’s a very effective system and generally would only really see wrong answers in the event of a wrong computation result (which seems unlikely, considering that the EVM is deterministic and has no randomness) OR someone is actually trying to cheat and hoping no one cares. However, in a fully functioning market, active checking would most likely occur, upon which it will most likely diverge to a situation where one can run computations for considerably cheaper than executing them on Ethereum itself. The trade-off is that one might need to wait for some time to continue doing subsequent executions, since one needs to wait for the challenge period to be finished to be 100% sure. A more efficient market will mean that the waiting period can be reduced, knowing that there’s an army of verifiers out there, ready to challenge and force the hand of cheaters. This is assuming that verifications are going to be run in the first place. This computational court, if working correctly will diverge to a situation where it is never really run, because it makes it so infeasible to cheat.
It’s a “panopticomputer” (a “panopticon computer”).
Without force, computers keep themselves honest, with the fear that computational force could be invoked if they misbehave.
The limitations of the computation market are that
- You need to put up ALL your code on Ethereum & require the whole execution to happen on Ethereum in the event of a challenge. This ultimately still reduces the possible spectrum of computation that can be run by the current gas limit.
- It is limited by the capability of the EVM. You need to write code in it and can’t offload computations to other programming languages.
Thus, for now, you will use Ethereum in its current iteration if you want to build applications that require decentralized convergence on state & decentralized control. This is costly, but still has a lot of benefits. You won’t really see it running a neural network, for example… Except… This is where TrueBit comes in. A proposal by Christian Reitwießner, Jason Teutsch & Loi Luu.
It’s a pretty mind-blowing combo. It takes the computation market concept, but adds the ability to verify instructions at a lower cost than running the full instruction if it were on-chain. In other words, verifying if a submitted answer is correct costs less computation than running it. You don’t have to run the whole instruction to verify that the submitter is cheating. You can thus verify that results have been posted for instructions that are much larger than would ever feasibly fit into Ethereum.
So, using Ethereum, one would only need to upload the verification scripts to the blockchain. These are written in the EVM, but it could verify *any* turing language. You can verify C++ or Rust for example.
It uses our favourite data structure: the merkle tree. Using binary search, an interactive game is played out between 2 entities (solver & challenger) at various points in the turing instruction set, to see when the merkle proofs of the memory & state in between computational steps do not add up anymore, in which case it is provably known (statistically significant chance given odds of hash collisions) which of the two cheated. The verification game is played out on Ethereum itself. The contract requests the merkle hashes at a certain point, and only applies one state change to see if the resulting merkle hashes match up to what was requested. Writing these verification scripts are required to run the game & do the intermediate changes.
The basis of this verification can be read in this whitepaper. It is expanded in this blog post from Christian Reitwiessner on smart contract courts.
It turns Ethereum from a *slow* distributed, world computer, to a massively scalable one. It turns it into a massive decentralized, mathematical court. In the event of computational disputes, it forces the hand by running the verification scripts. As previously mentioned, the beauty of it, is that it only needs to run the verification scripts in the first place if something goes wrong: someone is trying to cheat. You only need one honest actor to destroy all malicious cheaters.
This is revolutionary. It turns Ethereum as a base layer for a new, decentralized computing substrate substantially further. Here’s a paragraph from Christian explaining the possibility of a neural network running on Ethereum:
Using the TrueBit project, smart contract can actually ask external programs to execute routines for them in a trustless manner, and they can use terabytes of data for that (which is needed for modern deep learning): If you encode the root hash of a gigantic data collection into the smart contract, it can use that to train a neural network (which is of course also only stored as its root hash) and make decisions based on this data. The data can even be updated by updating the root hash. As long as the data is available to an external executor (and at least one honest verifier), the system keeps running. At the point where we swarm, the smart contract can actually economically enforce the availability of the data.
Marginal Cost of All Software Services Goes to Zero?
If you extrapolate on this possibility, it becomes rather dizzying… The potential exists that the marginal cost of all software services goes to zero. Blockchains & Ethereum introduced the concept that we can now run software that does not require organisations anymore to sustain them. Software always required the meatspace shell of humans & organisations to sustain themselves. We had to build organisations around software. However, with a collective compute infrastructure, the model is turned inside out. Software exists independently and thrives on a pay-per-execution model. It will always be around, until it executes, going dormant until executed again. This means, that in order to thrive, the software agent marginally, only needs to pay for its own upkeep. This idea sparked many discussions in the Bitcoin community in the early days about the concepts of self-driving cars owning themselves. Because it is a car, it doesn’t need to make a profit. It only needs to cover its own costs: serving humans. Organisations to run software is an expensive endeavour in the face of this possibility. Organisations have humans that need to be fed, have rights & have incentives like greed, making more money than is required for the service to exist on its own. Software doesn’t (or doesn’t need to have it).
This means that over time, from an economic perspective, moving over to software being executed at zero marginal cost seems inevitable. However, blockchains as they stand today won’t lead to all software to run at zero marginal cost. It’s still slow. However, with TrueBit, it seems it becomes possible to execute any software service at its zero marginal cost. This cost would be: the cost of paying for the market, it’s own internal functioning system and the cost of the external participant to run the computation (energy + potential human).
As part of Trent McConaghy’s post on AI DAOs, I submitted a WIP version of a service that produces art itself using futarchy & TrueBit. The better art it produces, the more art it can continue to make. There’s no humans it needs to support anywhere in the process. I’ve already started work on a more generic version of this and needs some more design work. The basic, early thinking is (could be holes in here):
- A smart contract is tasked to provide a certain service. Some ether is sent to it, to “birth” it.
- Futarchy is then used to find & attach external code to it to fulfil this service.
- The smart contract automatically starts delivering the service asking the TrueBit market to execute results for it.
- The price it asks for it, should be enough that it can continue to operate futarchies for improvement and postings to the market (at zero marginal cost).
Using TLSNotary proofs (as employed by Oraclize.it), it’s even possible for it to interact with the web as it stands now. With EIP 101 in Ethereum, the smart contract only needs to be prodded, and the smart contract can pay for the gas costs itself, not the user activating it.
In the end, this goes more and more into the direction that software doesn’t have to pay for the humans behind it. It only needs enough costs to keep itself capable of producing the service.
Uncertainties
The current implementation is not without its uncertainties though. The verification scripts need to be written such that it correctly can verify computations (which seems like a difficult task).
There’s some crypto-economic conditions of the market that need to be eked out. A timeout is still required, for example, hoping that if a cheater submits a wrong answer, there is enough time for a challenger to arrive. The interactive game, when forced, would take several blocks to play itself out (not long). This limits it somewhat for a certain set of computations. If the other scalability solutions are implemented, the game could be substantially faster. Additionally, some economics around potential sybil attacks for answer submission could derail it. None of these seem insurmountable though.
#Future
The potential of TrueBit seem quite revolutionary. It turns Ethereum into a decentralized computational court, allowing a lot of software to potentially run at zero marginal cost.
What are the farfetched ideas from this standpoint? It seems possible to run a neural network, enforced by Ethereum, leading to questions about AI DAOs? And what about all those ideas of decentralized virtual simulated realities? It becomes more possible at least.
In the past few years, I can count on one hand when I’ve encountered new tech that truly blew my mind: Bitcoin, Ethereum, IPFS (& IPLD), and now this. I really hope to see it get developed, tested and used.
—
I’m an engineer at @
.Thank you very much to Christian Reitwießner for taking time out & explaining some parts of it & fielding some of my questions. Appreciate it! Thanks for all the amazing work that you do.
Thanks to Dave Hoover & Joseph Chow for edits/feedback.
