TrueBit: Scalable Computation - Christian Reitwiessner

Okay. So, I will try to explain to you what true bit is all about. Um why we need it and uh what can be used for. Um to start uh I would like to talk about the topic of of scalability. This is a chart of uh Bitcoin transactions per day and it starts in January 2009 and this is basically now it's a a linear scale and you can already see that yes so um it's growing there's not so much uh in the last months but yeah and Uh it's similar chart for Ethereum.

This is yeah transactions per day also starting in uh July August 2015 uh until now. And I would also say it's kind of growing. And um yes. So the the question is um yeah so we most of you might have heard that blockchains do not scale currently and this is one of the main uh debates in the Bitcoin community. But what does it mean?

What does to scale mean? Um to put it simply, something scales if it performs equally well as it grows. And currently for Bitcoin, uh there is empiric evidence that this is not the case because it's so it gained more and more popularity over time and now it's harder and harder uh to get transactions accepted and they also get more expensive. And of course this problem exists in exactly the same way for Ethereum. Perhaps even uh worse since transactions can be more complicated.

But currently Ethereum did not hit uh this this limit yet. Um and what is the reason that uh blockchains don't scale? The the simple answer to that is that every full node has to process every single transaction. or verify every single transaction. And of course, this does not really work well because you have a so you have the the fixed block time, the time between two blocks and in in this time if the system grows, which means it has more and more transactions, then uh every node would have to process more and more transactions in the same time interval.

Um in scalable scalable database systems for example you have the property that uh if if the the usage increases of something of that database system then you can just add more servers and it will balance that out. So if you add more nodes then uh you can uh cope with with higher demand and that is not possible with blockchains because of this property that every full node has to process every single block and uh of course we have this property uh because of trust. Um if if we if we distribute uh transactions just across some nodes then uh those nodes might be able to cheat because yeah not all other nodes verify the transactions and so as I already said scalability is also exactly the same problem in Ethereum and uh the difference between Ethereum and bitcoin point is that uh we were very well aware of that from the very start. Um which does not mean that we knew the solution for the very start or that we had some way to to already uh yeah prepare for scalability but we at least knew that we will have to do at least one artwork uh to to cope with the scalability problem. Um and there are at least uh three proposals how to yeah scale the Ethereum blockchain and the first one is the the Casper research program.

So Casper is not just about proof of stake but also about uh trying to scale the blockchain and uh the idea in Casper is that you use uh yeah a concept called sharding that's more or less the same concept that is used also used for these uh scalable distributed databases. uh the idea is that yeah you you just send transactions to just certain nodes for verifying but uh Casper makes it secure again by rotating these uh verifiers in regular intervals. Um then there is uh Raiden which is the Ethereum analogy of the lightning network which is yeah the bitcoin lightning network and there the idea is that you can scale transactions by grouping them in a certain way. you you move them off chain. So you don't process them in the blockchain but you process them in a a different network and then at the end uh you group them you group mountain transaction into a single transaction and just put that transaction on the blockchain in very very uh simple words.

So you can get more transa you can get more yeah transactions in quotes into a single actual transaction on the blockchain and that's how it scales. Um and uh true bit is the third way and there the idea is to yeah scale computations. I will explain a bit more later how what that actually means and uh the way to scale it is using interactive verification that we will also go into detail later on that um yeah and also a nice thing to note is that only only Casper requires an actual fork because the other two ways to scan can be directly implemented on the smart contract mechanism. Okay. Um why do we need to scale computation?

so yeah, Ethereum has smart contracts which means computations running on the blockchain but they are limited in in complexity limited in resource usage uh because of the fact that every full node has trans has to process every transactions and uh with true bit you can get smart contracts which do not have a guess limit essentially they can written any programming language. Um the reason behind that is so if you don't have a guess limit you can just uh take a program written in Python and then just put the Python interpreter on the blockchain and uh run the Python program through that. uh Ethereum smart contracts can be driven by neural networks so that we can have artificial intelligence on the blockchain and you can even have file system access in smart contracts which means you you have a smart contract then it it and it accesses that terabytes big file and reads a single chunk in there or even uh computes a big sum over all the entries in this this gigantic file. Of course, these smart contracts will not run directly on the blockchain. We know it doesn't scale, but the uh the trust promise will be the same as if they would run on the blockchain.

Uh so this was a bit abstract. Uh some more uh specific practical examples. Uh with Trit you can link multiple blockchains. So there's this Dogecoin Ethereum bridge project which uh tries to create a bridge not only from Dogecoin to Ethereum but also from Ethereum to Dogecoin. And the idea is that you can take you can take Doge Dogecoin and move it to the Ethereum blockchain where it will be a an independent token.

you can move it around as a token there and then also move it back destroying the token and uh yeah releasing or generating new new doge on dogecoin. Um for that you basically need a light client for the other network in the so for one network in the other network and the the light client for Dogecoin running on Ethereum will yeah as as I said so if you don't have a a gas limit you can just implement anything and verify the full uh Dogecoin blockchain on Ethereum. Um another project is uh so Golem. Golem is a project to um yeah pay for other people to do your computations and uh their white paper mentions true bit to actually verify that these computations were done correctly. And another example is live pier.

They are they want to uh create a video streaming platform where people are paid to encode the videos and they want to use troub to verify that the encoding was done correctly. Okay. Uh another very nice property of troub I want to mention is that it has so-called unanimous consensus. Um this means that okay perhaps I should first explain the general framework. So uh triit works in a way where you have a computation task you have a program to run someone runs the program offchain and uh puts the result on it and then people can rerun the same computation and check that it was done correctly if they want.

And the idea the and so this is similar to a blockchain where you have multiple miners who process all transactions and then verify each other. And uh on a blockchain if you have a disagreement there then you get a fork. And uh if you can convince over 50% of the hash power that your version is the correct one then you basically convince the whole network. Not exactly like that but roughly and for troubid it's different because you have to convince every single person. So uh as long as there is a so as long as there is a single honest person who checks the the computation and post on the blockchain that he or she disagrees and the person is actually right then uh this this uh it will not go through.

So the the person will get the their result. Yeah. So basically the there's only one transaction per questionable execution basically not on every computation I have to submit a transaction but only if there's one question and I want to pay it basically um I didn't understand the question sorry I run a transaction and um I'm saying that was done wrong someone was cheating Then I submit the transaction but I don't submit the transaction if everything runs fine and everybody agrees. Yes. Yes.

So only in the case of actually cheating. Yeah. Okay. And another question. You're probably going to get this.

How is that done? Is that through sampling or how's that? We'll get to that. Um yeah. So I so some of you have been here in an earlier talk about the same topic and uh this this first line was already in the the first talk but the second line is actually new.

So uh some months ago we we said okay a single single honest verifier suffices uh so that nobody can cheat but uh it turned out that this single honest verifier is not always there but uh yeah we added an economic uh incentive mechanism to actually ensure that this single honest poison is is also always there. Um and so there are other projects which do similar things uh like golden my exac and so but uh the difference to those project is that they focus mainly on uh performing the computations or outsourcing the computations but not uh on the fact that they are done correctly. And true bit on the other hand is yeah is is focusing mainly on uh on correctness and uh not on yeah reducing the costs or or something like that. So troub is really about scaling up uh what can be done inside a single transaction if you know. Yeah.

So if you don't have gas limit how do you uh solve the hawking problem? Okay. The then uh so it's Ethereum smart contracts but with an extremely with a very much higher gas limit. You're right. You're right.

So it has some concept of gas but it's much more relaxed than Ethereum. Okay. Um so yes uh this was the non-technical part just to scare everyone here. Uh yeah I hope it's still it was it was still all be understandable. Um so how do we do that?

Um yeah as we already said the main problem why we cannot scan computation is because everyone has to compute everything. So the solution is obviously uh build a system where not everyone has to complete everything. So I have a computational task posted on the blockchain and two or three people take it on and perform the computation and then post the result on the blockchain and uh the main point here is not we just take the the majority answer but the main point is if if we have any disagreement here then these people go to court and court here means blockchain. So we have the the smart contract judge which uh who finds out without error who gave the wrong answer. And yeah again the the simple solution here would be that the smart contract just reruns the full computation but that again doesn't scale.

So the the checking who was in error has to be magnitudes faster than actually running a computation. Okay. And how do we do that? We use a concept called the verification game. [Music] Um, so and the the key uh term is here is not sampling but binary search and we'll see how that works.

Yeah. In a minute. Um, so a computation in a uh same computation model always consists of some kind of steps. So we have a computation which starts at step one and ends at step 1 million. And every single step is quite small easy to follow.

Um and we have a proposer with a with an input a challenger with the same input but at the end they come up with two different outputs. That's their their disagreement. And um what they do is they rerun the whole computation. uh while taking a snapshot of memory at every single step computing a mer tree of that snapshot and storing the mer route. They do not submit the motor route.

They do not submit all the motor roots to the blockchain right away, but they store it. And uh this means yeah their their motor route at the beginning will be the same because they started in the same in a very fixed setting and it will be different in the end because their memory content their output is different. And uh then the smart contract the judge will come and say uh would take the the middle the step in in the middle here and ask them for the the local route of their state at that point in time and they might give the same answer. This means so this means that at some point here in this second half there has to be a single step at least one single step uh where we go from agreement to disagreement. So both parties were in agreement here but they are in in a disagreement here.

So at some point uh along the line here they has they have to move from agreement to disagreement. And that's just the point we we use we search using binary we try to find using binary search. So the smart contract uh asks for the the center position here and the parties again reply here they gave a different reply. So we continue the search in this area. Uh this goes on and on and at some point uh because the the size of this uh time interval always halves.

At some point we re we will reach a situation where we have one step where both parties are in agreement and the next step where the parties are in disagreement. And the good thing about that is that a smart contract can so a smart contract can just take start with the the situation here in this step and just recomputee a single step and check which is the correct result because uh yeah a single step is is easy to compute. We have we have some computational power on the blockchain but it's very limited and uh yeah a single step easily fits in this in this limit. Okay. Uh so uh this takes 20 rounds which is quite long I would say.

I mean it's still uh tiny uh compared to 1 million steps. That's what I said. It has to be magnitudes faster on chain than actually running the full computation. But still um yeah the good news is that these 20 rounds can be further reduced and furthermore the cheater is found with certainty. There's there's no there's yeah no way to to get around that and uh but because of that if you if you try to cheat you already know you will lose in that game if someone watches then uh why would you want to play the game?

So why would you want to cheat? So as long as you know that someone watches, you will probably not cheat, which means that this verification game is actually never played. But it has to be there and it has to be in code and correct uh for this whole mech mechanism to work. Yeah. So uh so if there's someone who watches then the verification game will not be played but still everything works out and the problem is um so everything works works perfectly all people uh nobody cheats everything works fine there's one honest verifier who verifies everything and but So the how the game works is that of course this is all deposit based.

So all participants put a deposit on on chain and if they are guilty of cheating then their deposit is destroyed and the people who discover that fact they get a reward. So the verifier will get a reward if they if they find an error but if everything works works fine then uh yeah they never find an error. So they will never get a reward. And this is actually a very fundamental problem because how do you as a verifier how do you prove to a system that you check the computation? You can you can at the end you can say oh yes yeah seven that's that's also the result I got but yeah I mean you knew the result beforehand so how can you yeah you can just just have copied that.

So um yeah over time the the verifier will lose interest because they are not paid in any way but have to do exactly the same work as the the main problem solvers. So they will uh will stop looking and as soon as the solvers notice that no one is looking anymore then they can cheat and the whole system breaks down. So uh we need a way to uh pay verifiers for their work. And uh the solution to that is uh something called forced errors. And the way it works is you basically inject an error into this whole process which can then be detected by the verifiers and then can they can be paid for that.

So um who pays them? Uh the system. So huh system. No no no. So uh okay perhaps I should have uh explained the whole setting a bit more.

Uh sorry about that. So uh if you want the true bit system to solve a task for you, you have to pay for that. So you have to pay yeah a a a fee. And this fee is in part paid out to the person who posts the solution to the task. And in part it is it is save in a uh in an account we call jackpot and if such a forced error occurs and a verifier finds the error then the verifier is paid from that jackpot.

And so yeah I mean of course it's a bit different. The solver uh cannot be punished because the solver had to inject this forced error. It's a it's a pseudo random but deterministic process and um the solver cannot uh kind of uh yeah choose to include or not include it. Okay. Is that clear how that works?

So genius. Wait for it. No because um yeah it has it has flaws. what you must what you must pseudo randomly. Uh so true randomness does not exist on the blockchain.

That's why we need pseudo randomness and it's kind of there are multiple factors that that go in and it's just a a process that can be verified by a smart contract. So uh the what is it? Which way? Yeah. So who injects the error?

Is it the um the proposer? So the solver. So yeah. Yeah. So there's the proposer who gives the task and the solver who solves the tasks and post the solution blockchain.

the solver know that he has to include in so it's some uh deterministic function uh taking into account I think the uh the block hash and perhaps also the hash of the solution. So so the and the idea is that the solver knows that this just happened. Okay, let's let's kind of skip to the next slide where uh we will find another problem. Um so the solver knows that this happened that so the solver is forced to inject a forced error and this condition is also verifiable by smart contracts on chain and if if the solver does not do inject the error then uh he or she will be punished and the problem is now so everyone who detects this error gets a reward and now the solver can of course uh notify verifiers about the fact that the error that the forced error just happened. So the in the ideal world the solver injects the error but does not tell anyone about that because we want the verifiers to actually re-execute everything.

So right. So okay perhaps um yeah um these forced errors. So the the the rewards for finding the forced errors are of course not for the forced errors. We pay the verifiers rewards at forced errors because that's where we can pay them. But the actual idea is that we want the verifiers to verify all other transactions too.

It's just so they they have to verify everything because such a forced error might happen in every single uh task and you only know that it happened after the fact basically. And so as a verifier you have to uh acquire that that information that a forced error happened. And the way we want the verifier to acquire that information is by just re-executing the task. Okay. And there's a second way that the they can acquire this information and that's by asking the solver, right?

Because the solver knows that the error happened because they had to inject the error. And uh of course on a on a smart contract blockchain, you have all sorts of uh weird uh bribery things which are possible. So it's yeah quite trivial to just add a mechanism where uh solvers are paid by verifiers to tell them this to to give them this information. Um yeah and the question is how do we yeah so so basically the verifier is only paid out when that is an error but that he verifies a correct sorry can you say the verifier is is pay out but he catches a has an error yes but when the comation is correct the the verifier verifies that theation is correct. Yeah, you can't as a verifier.

There's no way to prove that you reran the verifier gets the payoff. Yes. So, it's a it happens at at random more or less regular intervals. Yeah. So, so the the random random error is the way for the verifier to be payout mining.

Yeah. Exactly. Yeah. Can be compared to mining where you get a payout. Yeah, not with every single with every block but at at certain points of time which then shifts the motivation more question towards solving those injected errors.

So the people are there more motivated to check those actually and it might decrease their motivation to do other. Sure. So even if they don't know yet but might find a way. Yeah. as a verifier since you can only pay for forced errors or for for errors uh you want to only verify these tasks but there's no way to find out whether it kind so I mean the only way to find out is or there are two ways to find that out and one is rering the computation and the other is getting that information from the solver wouldn't the other way around be to randomly pay people for checking um the verifications even though you can't prove if they really did it.

So whoever we don't care who actually runs the verification as long as someone does. It's like a search dog. You have to uh put it fake rewards to keep you interested. Yeah. But I I I just question whether it increase it.

I mean it increase but mainly for the wrong motivation. So you want I just asked myself it's also possible to increase the motivation for the things where you say you can't you can't check on um you have to run everything to find the the rewards the errors force errors and it's exactly the same thing you do whether you just verify okay so Uh yeah. How do you prevent the solver from telling the verifiers that Yeah. Okay. Maybe rather than choosing the verifier.

So that would be kind of like determine how much information you need to validate that this is a true outcome or true. Yeah. I mean so on a blockchain you never know on a blockchain never on a blockchain nobody knows that you're fringe so you don't have a reputation system attached to the solvers and yeah it's difficult and also I mean so we want this to be to be tight also uh against kind of arbitrary bribery smart contracts and that's why just sampling the solvers uh is not not the best solution I think. But you're randomly changing the what did you say? Randomly changing the solvers.

Yeah. To clarify the basically as the same randomizer that puts the guys to put the errors errors making verification. So something I perhaps didn't say clear is that anyone can be a verifier and also you can from out you can you can step in as and challenging a computation from outside at any time and you're not so that's another model when you say uh you have to verify the computation but if you do that then you have to punish people when they do not verify the computation that's kind of a a tricky thing to do. Okay, but that's what we came up with as a solution. But one more question.

So basically every time I do a computation, I do have to submit a request from the blockchain I do and the solit the result. So this basically for each computation no matter how large it is one one two transactions. So this is meant for large computations. Yes. And the whole process takes multiple transactions.

Yes. Okay. Okay. So it's it's not scaling the amount of transaction computational transactions. It scales the the size of the transaction.

So it's it's so it takes a constant amount of uh transactions in a good case where we don't have to run the verification game but the uh the length of the computation uh can be canre increased compared to what we have earlier on the blockchain. But you think I cannot do more transactions, right? And I can only use the last. Yes. Trit true bit does not scale the number of transactions.

It scales the the amount of computation in transactions. It feels like with a bit of everything together. Okay. Uh this is how you prevent the solver from sharing the information about the forced error with the verifiers. And so so we don't prevent the solver from also challenging their own computation in case of forced error.

That's a good thing. So it's just the sol reward uh and we can factor that in uh with the regular rewards. So that's fine. Um but the idea is that uh the the reward will decrease dramatically uh the more challenges there are. So um these numbers can actually be improved but that's how it will it is written in the white paper.

So I will explain it like that. So if we only have one challenge, this this is usually just the solver challenging challenging him or herself. Uh the solver will get a reward of of 100. That's just some fixed number. And if there's another challenge, then the two challenges will both get 25 and in some 50.

So if the solver shares that information with someone, the solver's reward will decrease from 100 to 25. So that's not something you would like to do. And also uh if you are a a verifier and acquired that information by rerunning the computation yourself, you also don't want to share it because then yeah if if only you and the solver solver uh found that out then uh your reward decreases from 25 to 8 uh three. So yeah that's the way how you can solve this this information sharing problem. Okay, this is this this basically stands against whatever the computation is worth, right?

So if the computation moves a lot of money that might be or like could potentially so of course so uh yeah there's an this all runs on a blockchain and even the the blockchain has an upper limit of uh how much uh what do you want to do on the blockchain what what which value is attached to what you do. So if you if you put something on a blockchain which is worth more than uh the whole blockchain then an attacker can just attack the the blockchain and uh get this thing somehow. Yeah. Um two questions. this um the first one is not really um so it's connected but but it is not problem for for this um for the solution but another attack and can I I as a verifier not simply wait until someone challenges and then only run this particular computation because I'm quite sure that there's a problem in this particular computation and then get all without yes very good question um that's especially relevant for the solver because the solver immediately knows there's a forced error.

So you could just watch if the solver challenges or not and because of that uh you have to randomly make something called fake challenges. So it has to be some commit reveal mechanism where you first post something to the to the blockchain which looks like a challenge but then in the end turns out it's not a challenge. And then um so that solves that. But another problem which I see um for example just some random numbers if you have like a force error every 10 computations or whatever and each computation um requires quite a lot of work for the um for the solver. And so what he really would like to do to do is just post fake results.

and he earns a lot of money because he doesn't have to have his computing cluster run or whatever. And so what he what he could still do would say okay I I just um um share this information anyways and I for these false errors I don't get any money because you know I share the information and everyone can challenge and so on. So I don't get any money for the post errors but I um save all this money for the for the other transactions where I don't have to to run my computing cluster and because I always share the information about the cost error no one will ever um look at my other communications because they know if I didn't share information about a error there won't be an error so no one will challenge any of my other communications and I'm like so if there's a mismatch between whether you can earn on the post errors and money you can save by not having to run the other computations. the so this is the reward the verifiers get for so if you do it every 10 uh tasks we were more think about every 100 task but so this is the only reward the verifiers get for verifying all the transactions all the tasks until the last post error and the amount of work they put in is the same amount of work that the solver puts in so this so the the amount that is paid out here is extremely large. Okay.

So it's it's comparable to the sum of all the uh computation fees uh paid for the tasks until the last uh process. You you talking about running arbitrary code, right? Like running some light plant or maybe running some Eiffel software or something some crazy thing. And um but then at the same time you're talk you gave a couple examples where you there was the need for onchain combination for injecting the error as well as for the the combination of the last step between the the right result and wrong result and so but wouldn't that require that the onchain combination has to be running like code or python code or something? Uh so we're planning to implement this singlestep verification for a process for a architecture called LAI which is developed by Google for some networking processor and this architecture is is quite simple and Google wrote an LLVM back end for that architecture.

So you can compile C, C++ and Rust code into that uh into that back end and I'm not sure what Eiffel is written is a Eiffel is a language in the 90s I just speak. So yeah but so yeah anything you can where you have so if you have a uh yeah if you have something that runs on LVM then you can do it and even if you have an interpreter written in C or C++ then you can also do it. Um how about um having access to things like I have access to solidity like block number and block hash and and value like I don't have to these kind of computation right yeah I mean it's not part of a block so it doesn't really make a lot of sense and it's just so also this this binary search that only works for for pure functions so you have to uh include the full state in input and output. You can work on on swarm files as I said, but that requires that you actually uh have a proof that the file is available which is possible in swarm at least in the final version and that's why you can so you can you basically put the the the hash of the swarm file as an input and then you can read it during the process. So I also don't have any state and I cannot do any value trans.

So if you want to use state it has to be part of the but it's fine. Yeah you can take the the whole blockchain as input and run a single uh block on that. Yeah. Are there always multiple solvers for every um for every computation or is one solver sufficient? So yeah, this is something that we still have to work out in in experiments but it's yeah it depends on the reliability.

Um but perhaps one or two is there a strategy to um to wait what another sol competing solver gets us a result or resubmitting the same result is that possible strategy to cheat the system. Um, okay. Sorry. Yeah, it only works with so this this model we're currently present only works if there's one one solver. So you you post a task and then the solver commits to the task, runs the task and post the solution.

Um the others are verifiers basically but keep the same. Um how if if one um you said that um the ch Oh no no when you you said that um the two there are two solutions and then there's this binary search going comparing the two solutions. How um how is this done when there's only one solver and one solution? I know there's there's a solver and a verifier who are in disagreement. back there with a question or Yeah.

When did you release the white paper explaining this? Sorry. When did you release the white? I did. Uh two weeks ago, I guess.

Or that's why it's a technical white paper. I have to admit. Yeah. Might be a better idea just the right then ask you this question. But uh another attack that I um I would come up with and so um in principle uh you would have a situation where then there would be a solver and there will always be verifiers you know that's what we want and so um in the end it is um every time there's a cause error there won't be the only one challenge because the sol will will challenge and I don't know 1 2 3 4 5 six verifiers will will um challenge and and at some point you will reach an equilibrium Because if there are too many verifiers, no, they won't earn anything.

And if there are but if this number decreases, then they won't the earnings increase until there's some kind of equilibrium. And let's say this equilibrium is the the solver plus three verifiers just just for argument sake. Wouldn't it then make sense for the solver to just create four accounts and always um submit four challenge and three other challenges so everyone looking at that sees ah there are already enough verifiers it doesn't make sense for me to join in and then same problem as before. Yeah, that's that's called the scaring of verifiers attack. And uh so yeah, there there is a solution to that.

Uh and the idea is that you always have multiple parallel uh tasks and verifiers choose randomly between these tasks. So it's it's it's a bit difficult, but it's explained way. Yeah. Uh, by the way, I really like this. It's really cool.

Uh, what is the road map overall? Where are the road map? So, um, yes, we don't have a a full road map yet, but we're actually planning on implementing that and we're looking for for both funding and developers to do that. Uh, the yeah, the exact specifics are not clear yet. Um but yeah um yeah to wrap up so yeah I explained how true scales trusted computation with unanimous consensus.

So and the the only requirement is a a working trusted execution environment with limited capacity. So a blockchain and it can be scaled to more or less unlimited cap capacity and with unanimous consensus. Uh the website is tri.io And the technical white paper has a complicated link which can also be found on the website. Okay, thank you for ask.

Okay, um in terms of scalability like is that an either or scenario or can you have this like true where it run simultaneously as the other proposed solutions? Yeah, it's I mean it doesn't require hard fork. It's just another smart contract on Ethereum. Okay. And it it also has so the whole system does not require Ethereum uh specifically but just some smart contract uh blockchain system some trusted uh execution environment.

One more question. [Applause]