ZK12: ZK on Bitcoin - Liam Eagen

Transcript

[Music] hi um yeah so uh I'm Liam um I work at alpen labs and we're building a Bitcoin rollup called strata um and uh yeah so I think usually when I talk about this stuff it's the opposite of how it is now where I'm talking to people who know about about Bitcoin but don't know anything about snarks whereas here I I assume most people know at least a little bit about snarks but maybe not about Bitcoin so um that's interesting and uh yeah I'll just kind of describe

the state of how to verify snarks kind of on bitcoin and uh what might be possible in the relatively near future um yeah so motivation this is just like an outline of everything um you may have heard of opcat a lot of drama about that we'll talk about uh and then some interesting future work that people are working on now with with things like functional encryption but uh yeah so why why care about verifying snarks on bitcoin right a natural question that a lot of people ask because we can already do it on ethereum and it's uh already complicated and even more so on bitcoin

um uh so why I bother right uh we also kind of can't really do it without some additional assumptions or a slightly different model than you you'd hope right what what we're probably used to from ethereum is you have a smart contract and it's verified by consensus and it verifies the snark and you know I mean that's maybe a little reductive but that's sort of what goes on with Bitcoin we can't do that for you know technical reasons that have to do with Bitcoin but I think it's an interesting problem for three well two reasons so uh the main one is building rollups that can use Bitcoin natively uh otherwise you have to bridge from one L1 to another and uh that is insecure or hard for other

reasons so if you can verify a snark directly on bitcoin you can build a kind of ZK rollup basically uh that uses Bitcoin as the gas token or you know for financial applications um um and this is interesting personally for adding like privacy and more programmability to bitcoin which currently doesn't doesn't exist uh at the base layer or you know in a way comparable to something like zcash um or ethereum so and then also it's fun it's it's sort of one of these things where you have lots of arbitrary constraints and so it's it's sort of fun to solve problems like that sometimes

although it's also good to take a break because it can be very frustra frustrating so um brief snark recap uh yeah succinct non-interactive arguments of knowledge we have some relation we want to you know for example uh prove that we know a witness W for some public inputs X such that x w is in the relation right we can prove we know W uh without revealing what it is um using a short proof that's much shorter than W and uh generated without interacting with the verifier so it's not probably new stuff but uh the reason why this talk is focused

on snarks on bitcoin is because general purpose smart contracts on bitcoin are also not possible but if we have the ability to verify snarks then we have the ability to verify arbitary smart contracts on bitcoin so it makes sense to Target snarks as like the main thing want to do because it implies everything else it's a universal verification primitive and so the techniques that I'll talk about are also applicable to other kinds of smart contracts but if we can do snarks then we can do everything so um yeah everybody's probably heard of Bitcoin right first decentralized cryptocurrency blockchain released by Satoshi Nakamoto in uh

2009 um mostly focused on payments Maybe you've heard of lightning Network payment channels but it's not uh focused on programmability or or privacy directly it's just sort of simple payments um you may not know but it does have a scripting language um which is very limited um fourth is a stack based language so it's just the op codes that push data onto a stack and manipulate it and uh it originally had more op codes than it does now um it was originally simple it is even simpler now um it used to be possible for example to do integer multiplication with an OP code it is not

anymore um most of the interesting op codes that we would want were disabled uh for weird historical reasons um for example like I said integer multiplication we can only do 32-bit addition and subtraction so for those of you that know how Groth 16 Works uh it involves uh large field multiplications which one would usually Implement with integer multiplication but instead we have to implement it using uh addition chains of addition so yeah um also all of the op codes that act on by strings were disabled except for the one that tells you how big a BTE

string is so you cannot for example concatenate by strings uh very very limited there are even more limitations um the stack that you work with can only have a th000 elements and each element can only be 32 bits which is not a lot um it can be larger but then you can't add them or subtract them so the only thing you could do is like verify that it's a valid signature or determine how large it is um a valid script can only have 4 million operations at the absolute maximum um probably slightly less than that depending on what they are but uh

and probably most damningly it is not possible to share State between Bitcoin scripts so you can't make like a smart contract that has some kind of persistent State uh so looking kind of hopeless maybe at this point there's there's not a lot of like ways we could possibly do this because the Groth verification script is far far far larger than 4 million op codes remember each op code can be basically an addition so um and then one other thing I'll talk touch on which is like a Bitcoin thing um is is this concept of covenants so like I said you can't share State between Bitcoin scripts but

um you can restrict how a Bitcoin script is spent using a or a Bitcoin utx on I'm sorry using a script right so the script script would say check a signature and if you can satisfy the script then you can spend the money what you can't do is Place restrictions on the money after it has been spent so you can't encumber Bitcoin with future restrictions and conceptually this is sort of how you would make a smart contract in a utxo model or at least one way to do so where you have some money and you attach some sort of spending condition so it's like you can spend it if you have a valid snark and you want to be able to spend it into a new thing that has the same

restriction say so it carries forward but we can't do that so um and Covenants are very controversial in Bitcoin um there has been the situation has warmed towards them but they're not currently possible uh what we will do is simulate a covenant with a trusted setup of pre-signed transactions so basically rather than implementing this in consensus everybody gets together creates a state machine of transactions pre- signs them destroys their keys and that allows us to do a covenant or simulate a covenant okay so how can we verify snarks on bitcoin

with all of these restrictions there is an ongoing effort to implement uh Groth 16 with BN 254 in Bitcoin script I think currently it's between 1 and two billion op codes and that's just one giant script that does doesn't use more than a thousand stack elements um I guess it's worth noting that it it is not like fundamentally impossible it's just far far too large to meet the restrictions so um and like I said right we can't share data between scripts it won't fit in one script so what how do we how do we fix this so bit VM which is this uh protocol uh from Robin Linus um had had the

insight to use an OP istic protocol to split up the script so what does that mean you have your script you split it into pieces there's no way to get consensus to verify that you've executed all of the pieces correctly however you can do a simpler thing or maybe not simpler but simpler from the perspective of consensus where the prover asserts that they have executed each step of the script correctly and then a challenger can say either you executed One Step incorrectly one chunk or you failed to properly split the state so you didn't copy the state from one chunk to the next chunk

correctly and uh that is possible to check on bitcoin or rather you can prove that you did that incorrectly you can construct a fraud proof so that's basically what we're going to do with bitm we can slash if if the data between scripts is shared incorrectly uh if you look up bit VM and like try and read about it um it might be confusing because there are a bunch of different things that are all called bit VM the version I'm going to describe is the one that everybody uh not everybody but that Alpin and craa another bit VM rollup company and zero sync which is Robin's uh nonprofit um are all using it's called

bit vm2 but I'm probably not worth getting into all of that okay so in a nutshell how how does bit VM work there's a single prover who's designated in advance that will construct a snark that say a rollup State transition happened correctly or that the bridge should release some money we have assume we have a big Bitcoin script that is the snark verifier um and we split this script into a directed graph of chunks where each chunk has uh sort of

computation and some sort of precondition predicate okay so um if all of the functions are satisfied in the dag then the computation succeeded so imagine the computation just returns like true or false and this predicate here is is is used to pass input to the chunk non-deterministically um through this like local parameter it's a bit like PCD um yeah so each Edge in the dag is some data shared between the chunks and each node is going to perform some piece of the computation and all of this has to fit in one Bitcoin script remember 4

million op codes 1,000 stack elements um and so on uh and sort of crucial important right for the uh uh optimistic part of the protocol theover is going to be forced to sign all of the data shared between the chunks so either they will have signed some data that was like not what the chunk produced or one of the chunks will be Inc incorrectly uh executed or or they're honest um usually people write it with one input and output but that's not strictly speaking required um and sometimes it's venient to have multiple inputs and and

outputs okay so in when you initiate the bit VM protocol so you want to or I guess maybe I'm not going to talk about like how the bridge actually works or how how the like larger system works but conceptually the approver or the bridge operator will post a snark and they'll assert that it's correct and then anyone can challenge and say that no it is not correct then in the first round round the prover is forced to put uh or to sign the data for every Edge so every Edge in the dag they're going to sign this these ins and outs

um each node in the graph which is a computational step will have a slashing script and anyone can slash for a node if all the inputs and outputs signatures are valid so that means that theover did actually commit to the state that we're slashing them for the predicate is satisfied and uh the function was not executed correctly um so note if the prover is honest then this will hold and all of these will also hold so you won't be able to slash them so that's that's basically it that's that's the the trick

of bit VM um making it work with Bitcoin is the kind of messy part um yeah so each I I said sign right we're signing every Edge but uh you can't just do signature verification in Bitcoin script um so we have to use a kind of uh very very simple signature scheme um you may have heard of like Lamport signatures or also winternet signatur the reason why we use these in in bit VM is because you can verify them in Bitcoin script so what is a Lamport signature uh it's very very simple you

have two secrets and your public key is just a hash of the secrets a signature is just the associated secret um so you'll notice that this is like a onetime signature scheme right once I've signed a bit then like anybody could produce a uh or if I reveal both the secrets I suppose anybody could produce a signature but that's fine for our purposes because the Prov just signs each Edge once um and Bitcoin script does have operations for natively hashing values so um consequently right so this is a

signature by the way for one bit right B is a binary value so if you sign like you know many bits you're going to have to reveal many secrets and uh many optimizations that one might try to use for Lort signatures are not possible in Bitcoin script so you you sort of do actually reveal pre-images for like 128 hashes um it's not quite that bad because we could could use winternet which is slightly better but each of these secrets has to be cryptographically large so that you can't just guess it and the uh uh so just a sign like I I'm it's a significant blow up so anyway what we want to do is minimize the

amount of data that we have to sign uh to be as small as possible because we have to put all of these signatures on the blockchain um so what we can do is is Hash the data on the edges so we have this dag right and each Edge has data that's being transported between the chunks and so if you recall back before when I had the ins and we think of those as like hashes of the actual data and pass the real data through this local input parameter um however there is a significant tradeoff here with the stack so for a Bitcoin script all of the data passed to the script is passed via the stack and the stack can contain at most

a thousand elements so every time you want to increase the amount of information passed to a script you have to add more elements to the stack initially and that reduces the amount of Stack space you have for actually executing the function and the predicate so lots of complicated tradeoffs I mean if you were going to do something like you know an inversion it still probably makes sense to pass it through this local parameter but uh this is one sort of interesting way in which Bitcoin script differs from if we were say writing this in a circuit for a snark because there non-deterministically passing hints is

usually very cheap um here not so um yeah so if you're interested I mean you can check it out on the uh bit VM repo um it's improving you know much more than it was but it's still very large and complicated and uh definitely needs a lot more attention before anybody uses it for anything serious um okay so I that's basically the state-of-the-art of snark verification on bitcoin right now we would use bit vm2 in the manner I described with the optimistic protocol to verify a snark um but with a few modifications to

bitcoin script we can do a lot better so you recall I mentioned there were all these deactivated op codes like integer multip lication or string concatenation and if we had even a few of them things would be much much better than they are now so like for example right if we had op mul for 32-bit integer multiplication we wouldn't have to implement like Kat subba in in the same sort of like very very basic way we do with additions we we would be able to stop at a lower point in the tree where we just have like 16 bit values to multiply and that I I don't remember how

much it would save but it's almost all of the script has spent like multiplying values and hashing but multiplying values so that that translates into a massive savings yeah so integer multiplication would reduce script size the big one though is is opcat because you can Implement covenants with opcat um they were all originally enabled currently they require a softw you can't use them now so what is the softw workk uh a softw work is a consensus change that makes block validity strcture so you have uh the idea here is basically that if somebody adopts the soft Fork their consensus will not diverge from people who do not adopt the soft Fork this is in contrast

to a hard Fork which would make the validity criteria looser um it these are really really hard to do so it's probably you know don't don't count on at anytime soon but they have happened in the past um one interesting cultural difference between Bitcoin and many other crypto projects is this extreme resistance to ever doing anything new um but yeah so opcat op mul and then this great script restoration so opcat concatenates two elements on the stack it enables a lot of functionality like I mentioned it

enables covenants um it also enables verifying Merkel trees kind of the obvious way um and there is an effort from um a group group with starkware and uh W King and others to implement a stark verifier directly in Bitcoin script using opcat so this is in contrast to the bit VM approach you just basically write the Stark verifier using opcat um you do still have to emulate integer multiplication in the really slow way but it works and and and there I don't remember what the size is but it's quite a bit uh smaller than the the bit VM approach um but it's not possible now so

I also mentioned M because not enough people talk about adding M back um it would make the Cat Stark verifier even smaller um it's a dominant cost in both approaches uh it does not enable covenants so it shouldn't be controversial but not enough people are talking about it and finally the great script restoration is basically this new proposal to add all the op codes back um lots of new OP codes variable cost model it implies the other ones but it's sort of more prone to bike shedding which is one of the failure modes of these things um yeah and then just wrapping up uh lots of work to be done on both

approaches uh one thing I want to mention at the end because there was a paper that came out like yesterday about this but I I don't remember what it's called um using uh functional encryption uh or indistinguishability ication to add um smart contracts to bitcoin so uh I will not describe how this works but it's a really interesting approach that I think merits a lot more um investigation uh yeah so that's it thanks [Music] [Applause] [Music] thanks Liam uh before we jump to question remember there is some merch

from the submit feel free to take it there is a a bit a bit left but it's going to go so yeah don't forget to take your T-shirt if you did not this being said uh time for questions are there any question from the audience for Liam about ZK on bitcoin yeah yeah I'll ask uh what What's the name of the paper you just talked about ah yes I'll look at up I the or or something to search for it yeah I think it's called Bitcoin pipes but I'm not sure thank you yeah Bitcoin pipes from M karov um thanks for the presentation

question on um so the GR 16 verifier you implement via bit VM is it tied to the Circuit or is it really a generic R 16 verifier and I can supply the verification key as input um tied to the Groth circuit yeah to whatever circuit I'm uh no no it's just um like three Miller Loops basically okay yeah thanks uh how many steps does it take for the graph 16 Uh current implementation uh the number of splits that you mentioned how many splits are there yeah for verifying a gr 16 currently that's a great question um I I

don't know that there's a currently I'm not sure what it is right now that is a big part of the effort and one of the drawbacks of the current approach is that like there's like logical places where it makes sense to split it usually at the boundaries of some like higher order operation but I think that that is proving to be more challenging than people expected I think it's roughly on the order of a thousand maybe 2,000 something like that or you can actually figure out the minimum just by dividing by the you know 4 million but there's like overhead from the hashing of the inputs and outputs so yeah thousands yes

um so a 16 I think um is around maybe 3 point something gigabytes right of of script the script size yeah 2.9 gabes I think something I'm not sure what it is but that sounds plausible yeah and then so what we what we're trying to do with the chunking is we need to get it down to under four megabyte chunks right to to fit into one Bitcoin block um what I still don't understand is how how do the signatures where do the signatures come into play here like the is that the task is to go to 4 megabytes and what is the signatures the signatures on the the edges that I meant like the Lampo signatures right so like the one way that uh a cheating prb would operate is they pretend like a script had some

output State S Prime when it really had output State s so you have to force the Prov to put something on chain that lets you measure whether they've equivocated that's concept what the signatures do so the script will like compute the correct value and then you check that it's not that uh you sign each Edge once so you sign the edge that commits to its value and then if it's wrong then where like the data is coming from it will produce the wrong value got it any other

questions anyone okay I think that's it so we're going to take a onour break for lunch and we'll see you after that thank you Liam