BITVM3: Are Garbled Circuits the Key to Scale? | Robin Linus - ZeroSync

Hi, I'm Robin Niners and I'm going to talk about BitVM today. And BitVM is a way to build better Bitcoin bridges. Yeah. Why at all do do we care about BitVM? Well, we want to bridge Bitcoin to other systems because first of all, the layer 1 doesn't scale very well.

I guess uh Vitilik just recently changed his mind on uh how well the Ethereum L1 changes if I'm correctly informed. I'm not quite sure if that's true but I think he thinks we can we can scale L1. Unfortunately in Bitcoin world we still think we cannot scale L1. So we would like to bridge Bitcoin to other systems like side chains, rollups or privacy protocols like CK coins and that would enable rapid innovation, cheap experimentation, scalability, privacy and all the stuff that is hard to introduce into the main layer because Bitcoin is already so oified. Unfortunately, we don't have a bitter league who can like wake up in the morning and be like in hard mode.

um we have to get find like decentralized consensus which is uh hard and it's getting harder every day and uh it's pretty much impossible at this point. So uh we have to work with what we have and previously the state-of-the-art for Bitcoin bridges was multisc bridges. So classical trust me bro model which is of course not so cool because uh yeah you're essentially giving your money to some people and uh you hope that they don't run away. Um a bit better model is overcolateralized bridges but um those bridges are very capital inefficient. So um they didn't find u much use in practice.

So the question arises how can we build better bitcoin bridges and in particular how can we build better bitcoin bridges without a consensus upgrade because that's pretty much not on the menu. And the solution to that or like the the the rough problem actually is um on the one hand we have Bitcoin. Do you see my Yeah. Okay. You see my cursor?

Um so on the one hand um we have Bitcoin and on the other hand there is some site system and we want to bridge the BTC asset to the side system. And this part is actually the easy part. The hard part is getting it back again. Because when you want to get it back, you have to prove to Bitcoin that you were actually entitled to take money out of the site system. And to do that, you have to prove the state of the site system to Bitcoin.

The trivial solution, which doesn't work, would be that you feed all the blocks of the site system into the into Bitcoin. But of course, that's that's impractical because um yeah, you would have to feed all the blocks of the site system into Bitcoin, which doesn't give you any scalability. So this is the hard part and the solution for that which probably guys in the Ethereum world are very familiar with is snarks. Snarks are these uh is is an amazing cryptographic compression technique that allows you to essentially compress infinite amount of data or infinite infinitely many blocks into a very succinct proof that you can easily provide to a chain and then convince that chain that you are allowed to take money out of a bridge. So snacks are the thing that we would like to have on Bitcoin.

However, yeah, it's it's it's not easy to verify them on on Bitcoin because the scripting language in Bitcoin is very very limited and that's why we came up with BitVM and BitVM is the solution and now we are in the third iteration which we called BitVM 3 and this is based on Gobble circuits and this makes it quite efficient. I give you a rough overview of how BitVM works. Um, as I said before, we want to build snarkverified BTC bridges. So, we actually want to have a snack verifier and Bitb is a snack verifier more or less. And no consensus changes are required for that.

And how it does it is uh it uses optimistic computation. Instead of actually verifying the snack, a snark is provided and if that snark is incorrect, then uh you can disprove it. And disproving something is is often much easier than to prove something. A very simple example for that is um if I give you uh two odd numbers or let's say I give you two even numbers and ask you to multiply them and you give me as a result an odd number then just look at the the fact that it's an odd number and can tell that it's wrong. I don't have to look at the at the entire number.

I don't have to redo the calculation to show that's incorrect. just showing that uh odd number shows that it cannot be the product of an even number of two even numbers. And that's uh kind of what makes this efficient like it's easier to disprove a faulty thing than to actually verify that something is fully correct. And um so we play this game between operators and challengers. Operators are the entities who run the bridge.

And challengers uh is essentially anyone who who who has like any stake in the site system and who wants the system to be secure. And it works such that the operator they can initiate a withdrawal and during withdrawal they assert to approve. They essentially commit and say this is my proof and if it's invalid then challenger challengers can slash them and if it's valid then just a timeout runs out and the operator can take money out of the bridge. This is the basic mechanism. So the operator provides a proof, people check it.

If it's invalid they slash them. Um otherwise nothing really happens. The operator can just take the money. And um the difference between BitVM 2 and Bitvium 3 is mainly that BitVM2 used onchain computation in Bitcoin script and that was extremely inefficient, very expensive. It cost lots of fees and it used like all kinds of non-standard transactions which means uh you cannot just broadcast them to the meool.

you had to go to miners directly and ask them to include your transactions in a block. And uh BitVM3 is vastly better in many regards in particular because it uses off-chain computation in garble circuits which is way way cheaper in terms of fees and it doesn't require any non-standard transactions. It's uh regular Bitcoin transactions that you can just submit to normal me pools. And um yeah to give you a comparison how inefficient BitVM2 was um the assert transaction where the operator asserted to approve was uh 2 megabytes and the disprove transaction where a challenger could disprove the proof was 4 megabytes. So in total in the unhappy path you had to be able uh to put like six megabytes of script on chain and that is of course extremely inefficient.

It's one and a half blocks full of Bitcoin script just uh for a single withdrawal in the unhappy path. In the happy path, it's okay, but the unhappy path was uh pretty inefficient. And now with Bitvium 3 and garbage circuits, we could improve that a lot because now the assert transaction is only 8 kilobytes and the disprove transaction is even smaller. It's only 200 bytes. So all in all we get roughly a thousandx improvement from bitvm 2 to bitvm 3 and this actually makes it pretty practical and the key idea behind conditional uh behind garbet circuits is conditional disclosure of secrets.

So I disclose a secret under a certain condition and this condition is going to be the snark is incorrect. So I disclose a secret if the snark is incorrect and then that secret is the fraud proof. It works such that during setup um we agree on some sort of black box. This is going to be the garbble circuit. And then afterwards um during withdrawal the operator they will provide a proof and then you can feed that proof into the black box and if it's incorrect then you learn a secret.

So exactly if the proof is incorrect you learn that secret and that makes the secret a fraud proof because you learn the secret only if the snack was invalid. Huh? If the snack snack was valid, then the blackbox doesn't give you anything, the timeout runs out and the operator can take the money. But if it's invalid, then you learn that secret and that secret will act as a fraud proof. And that's what the challenges will put on chain in the end.

And how do garbled circuits work? Well, to understand how garbled circuits work, um we first have to understand how a garbled gate works. Uh how many of you are familiar with like logic gates roughly and or x or you have heard about that? Okay cool. So this is an end gate.

It takes a and b. A is a bit b is a bit. So both of them are zero or one and the output c is also a bit. So I take two bits and if both of them are one then I'm going to output one. Otherwise I'm going to output zero.

Uh this is a basic end gate. And now how do we garble such an endgate? Well, we replace these values with secrets. Uh so you see everywhere where there was a zero there's or like in in the A column everywhere where there was a zero now we have a zero there. And where there was a one now we have A1 there.

And same for B and same for C. And these secrets they are unknown to the evaluator or to the challenger in the beginning. And the operator they going to provide some sort of input like they going to provide an assertion to a and b. So if they want to set a to zero they're going to reveal a zero and if they want to set let's say b to one they're going to reveal b1. Uh and during setup they also provide cipher texts.

So for each of these rows they provide a cipher text and this cipher text allows the evaluator to decrypt the corresponding output to the inputs. So let's say for example um yeah I guess I have to use this. So let's say for example the operator gave you a z and b1 then you use those as the key to decrypt c 0. So depending on which inputs the operator gave you, you will be able to decrypt the corresponding output. You will not be able to decrypt C1 if you don't have A1 and B1.

Does that make sense? So each row um gives you exactly one output. And um so during setup we just have to exchange these um cipher texts. And also I have to verify or like I have to prove to you that these cipher texts are actually correct. So if you know the correct inputs you're going to learn the correct outputs.

And these gates they are obviously composable because um the output is a label the input was a label. So you can just take the output of one gate and feed it as an input to the next gate. And this way you can compose large circuits and express essentially any kind of function. Does that make sense? He's nodding.

Okay. So, this is roughly how Gobblet circuits work. And um yeah, now we can compose these gates into large circuits. And once we provide an input to the circuit, we're going to learn some specific output. And since we can do that with any kind of circuit, we can do it in specific uh with a snack verifier circuit.

And then we have essentially universal computation because we can prove any kind of computation in the snark. And um yeah the such a snark verifier essentially looks like you have a verify function which we express in the circuit and the input is going to be a proof and then the output is going to be true or false. The snark is either valid or it's invalid. And as I said before if the snark is invalid I I'll go through the protocol step by step. So the bridge operator he published a snark proof which is going to be the the input to the circuit.

Then challengers can read that snark proof from the chain feed it into the gabble circuit and then if the snack is invalid they're going to learn the output label for false and this is the fraud proof and otherwise the operator just um can take the money after some while. And um now I've just said this is a black box but in fact um these black boxes um have quite some complexity. Um we yeah we went through quite an evolution in the last year. First we used Yao style garbage circuits. They are from like 1986.

So it's ancient technology more or less. Uh and the good thing about them they are very simple. They are basically the thing that I just explained. It's just hash functions and symmet symmetric crypto. So uh uh sorry symmetric um encryption.

So it's a very solid and um nothing fancy about it and we actually have an implementation of it. But the bad thing is that uh it requires on the order of a few hundred GB of circuit size. So uh that's quite inefficient and you need that for every operator and essentially for every deposit and the setup time for a single one is more than 30 minutes. So that's extremely inefficient and that's why people um started doing lots of research. First Liam Egan, the guy who was sitting here in the previous session, um he came up with um a scheme called Glock.

And the good thing about it is um it reduced the circuit size down to 100 megabytes or a few hundred megabytes. But the bad thing was um it made permission uh it made challenging permissioned. That means it's not that anyone can challenge um invalid proofs but only a specific set of people can provide counterproofs or fraud proofs and that is of course bad because you don't want to trust these people. Yeah. Do you you don't want to introduce a new trusted party.

So uh we were quite um it was not quite satisfying. So Liam kept on doing more research and then he came up with the AGO scheme. together with Ying Tong and they reduced the garbage circuit size down to 32 megabytes and now it's permissionless again and this is essentially the state-of-the-art. This is um how we can build very efficient bridges right now. The only drawback is that um the onchain footprint is slightly larger but um since the onchain footprint is already so small it doesn't matter that it's a bit larger.

Um and then there is another scheme called BAPE which is based on the AOMAC. Um they are combining the AOMAC with linear witness encryption. And um the good thing about it it's um only yeah it has quite small circuit size and also the construction is arguably pretty simple. That's that's the nice thing about it. However, the problem is um it's also permissioned.

So it's not very cool for our use case. like uh it is good for like two-party protocols but it's not very very well suited for bridges and there are a few historical fun facts um I had already worked on garble circuits back in 2022 before the creation of bitv1 but I didn't make the connection that we can actually use garble circuits and uh even Liam Egan also has mentioned um garble circuits before the creation of bitvm and then it took like until 200 yeah 25 where and uh Jeremy Ruben garbble circuit built me and told me hey man this is actually a replacement for bitvm2 and he said like I don't know two three sentences to me and it was immediately clear that bitvm2 is completely obsolete uh and the fun thing is we just had completed the implementation and had signed an expensive contract for an audit and uh yeah then he said two three sentences to me and uh it became all obsolete but yeah that's research um and another fun thing is bitm was already possible back in 2017. And in contrast, BitVM one and two was not. And it's kind of funny that we had to take that detour to like first build this monster BitVM1 and then this even crazier monster bitv2 to then figure out the the the simple solution which was already possible since 8 years. And that makes you kind of wonder what other hidden gems are lurking there and hiding in plain sight that we just have not discovered yet.

Um, now to give you an overview of how this works in practice. Um, oh yeah, first the guarantees. It's it's still kind of like a federation, but um, it's way better because a single me a single honest member suffice. Uh, you can have a thousand cosigners and a thousand bridge operators. And the guarantees are that if any of these co-signers is honest, then nobody can steal money from the bridge.

And if any of the uh operators is live then uh every every withdrawal will eventually um succeed. And of course um if if you have a high stake in the site system you can become a member yourself and then it's fully trustless from your perspective because you can trust yourself. So uh these uh then the security guarantees become quite strong. And uh how do these graphs look like? Um in Ethereum you have this nice programming language Solidity that everyone loves.

In uh Bitcoin we don't have that at all unfortunately. Uh what we have is just plain old simple transactions and we have to express everything in transactions and we essentially express contracts in graphs of transactions and um this is going to be or like now I'm going to show you the um bridge graph for for simple Bitcoin bridges. So we have Alice and she wants to deposit 10 BTC. Then uh she asks this uh she she she sends the money to this signing committee like it's an no anovven multisc. So all of them have to sign and they going to pre-sign a withdraw transaction for the operator and they do this essentially for every operator and this signature just um it commits to its own output but it also commits to this other to this green output here and that means the withdrawal transaction is spendable only in conjunction with that green output.

So where does that green output come from? The green output comes from this kickoff transaction. In that kickoff transaction, the operator has to assert to a snark proof. They provide a snark proof and they can only ever spend the withdrawal transaction if they previously executed that kickoff transaction. And then they get this connector and this is going to be time locked such that it takes a week for them to to execute the withdrawal transaction.

So essentially at this point it means they put the kickoff transaction on chain then they have to wait a week and then they can execute the withdrawal transaction. So where does the optimistic computation come into play? Well they have asserted to that snark proof and during setup we have um set up some some some garbled circuit. So anyone can read that snark proof from the kickoff transaction and then uh execute or like um verify the snack proof in the garbble circuit and if it's incorrect then they learn this false label which is going to be a fraud proof which allows them to execute the disprove transaction spending that connector and essentially rendering this withdrawal transaction obsolete. Okay.

Uh he says it's time to wrap it up. So this is roughly how the bridge contract works. rough idea. Um, the withdrawal transaction is spendable only in conjunction with that connector. And if you're lying, you will lose that connector, rendering your withdrawal transaction obsolete, and you cannot spend the withdrawal transaction anymore.

Outlook in summary, Outlook, um, they still have some some drawbacks. First of all, this covenant emulation like thisvent thing that I showed you here, um, this is pretty annoying and it would be great to have covenants. Um there are few um covenant op codes that people are talking about and it would be great if any of them would get activated but in the long term it would be way better to actually have a native snack verifier on bitcoin. Um and that would be possible if we had something like big inter arithmetic great great script restoration or simplicity. Quick summary bitv enables better bitcoin bridges and this is good for bitcoin scalability privacy and also programmability.

uh bitvm3 is based on garble circuits. It enables off-chain computation. It's a thousandx improvement um in onchain cost over bitvm2. Now the argo scheme gives another thousandx improvement in off-chain cost and um snark verification is now fully practical on bitcoin and the ago bridge launches soon in two weeks tm um yeah and ideally we would have software soft forks for um making this like nice. That's it.

I'm gonna skip over this and we're done. Thanks,