zkSummit6: zkSNARKs for Hidden Information Blockchain Games - Brian Gu & Alan Luo - zkga.me

Transcript

[Music] so here we are this is actually the last talk on the main stage of zk6 and i'm so happy to invite brian goo and alan they're going to be talking they're both from zk game i think they're pretty well known in this community they're going to be talking about zk snarks for hidden information blockchain games so take it away awesome well thanks for having us anna and we're really happy to be here and and to share some new snark instructions we've been working on um so first off i guess by way of introduction uh i'm brian i am uh i work a little bit with the ethereum foundation and i also work on

dark force uh and other zk games um and i am currently on leave from a math degree at mit yep and i'm alan i've just been working with brian on dark force and other zika games and i'm also on leave from sodium cs cool so um just to get started here um to give some quick motivation before today we're going to be discussing a couple of zk constructions um we're first going to dive into uh why are zk snarks useful for blockchain gaming i think a lot of people here are really familiar with um you know the applications of zk snarks for privacy technology or scalability technology with things like you know various rollup solutions and anonymity solutions um but the thing that uh one thing that

we're really excited about is to see the use of zk snarts for decentralized games so to start off with some motivation um in order to understand why zk snarks are useful it's important to understand the distinction between the two types of games complete and incomplete information games complete information games are games like chess or checkers where basically everybody at all times knows the full state of the world so in chess i know where your pieces are you know where my pieces are there's no secrets on the other hand incomplete information games encompass all games where there's some notion of private or hidden state and where players might not at any given time know the full state of the world so for example poker is a hidden information game because i don't know

what your cards are you don't know what my cards are uh similarly a lot of strategy games like starcraft are incomplete information games as well and it's generally the case that um pretty much all of the most popular online multiplayer games are have some component of hidden information um simply because that extra primitive of information being a first-class resource um allows for a very rich sort of space of social dynamics or you know strategies to evolve um and that's sort of uh you know what we're interested in exploring with seaface marks so up until this point because of the nature of blockchains and other decentralized systems it's almost not been possible to really build incomplete information games

on blockchains the reason for this is that blockchains by design are systems where you know the data layer uh is often going to be like completely open or transparent obviously you know with some exceptions around blockchains that are specifically built around privacy um but you know anybody can inspect the full state of any contract on the evm at any time what this means is that uh you know without zk starts if we want to build if previously we wanted to build blockchain games we were sort of limited to the complete information games regime uh you know so this means that we can build games like cryptokitties or trading card games where everybody knows who owns what kitty and what all the properties of each kitty are um but you know we can't really lean into those more complex like social dynamics or strategy spaces that hidden information

is going to enable so you know our kind of theory here is that up until zk starts making hidden information possible we're sort of at like the tic-tac-toe level of blockchain gaming and you know there's obviously so much more that we can do here so one specific example of you know a game where information asymmetry is really critical is the genre of real-time strategy games where there's the notion of like the fog of war so in these games until i have explored the entirety of the map that we're both playing on i might not know where your base is you might not know where my base is i don't know what units or buildings you're constructing and vice versa um and this leads to a lot of really interesting sort of faints and deception and this sort of thing

many of you might also be familiar with games like um you know eve online these really big persistent mmo games um whether they're you know persistent strategy games or rpg games uh and eve online and games in this genre sort of have a very rich history about like uh players can engage in conditional coordination deception um emergent dynamics um all of these things are made possible with information and symmetry and finally uh you know in a large class of games in fact like most multiplayer online games there are some elements where privacy is sort of taken as a given um so you know i sort of i have an expectation of privacy in an rpg game like world of warcraft or you know runescape where i basically just

expect that my possessions and my bank account my inventory is you know it's not exposed to the whole world to see so um here it's not even like this is something that i just sort of take for granted and expect as a given um and i would it would be a little strange if there was a game such that like you could inspect other players bank accounts um so obviously all these mechanics that we've just described are tricky to do in blockchains because of the nature of you know blockchain as a data layer is open and transparent but fortunately with uk snarks which you know as many people know became viable for a lot of production applications in the last two years we can now actually impose a meaningful notion of hidden information on the blockchain so the way that we're going to do this

is you know suppose we have a game where a player wants to keep some state private so let's say that they have some private state s1 their inventory or their card hand or whatever else that they want hidden from the network but they still want to be able to adhere to the rules of the game provably in you know moving around and taking actions so our construction here is you know we're the high level idea is that instead of committing their private state up to the to the network they're going to commit a you know hash or a commitment to their private state uh along with a zero knowledge proof that that does indeed correspond to a validly formed private state so this proves that like i'm not giving myself extra resources in my card hand or you know anything like that now whenever

a player wants to make a state transition what they're going to do is they're going to upload the commitment to their new private state so you know a hash of like the object the structured object of their private state and a zero knowledge proof that there is a valid state transition from you know the first uh private state to the second private state so this proof basically says something like um i'm going to move my knight from secret location a to secret location b i'm not going to tell you what either of these locations are um however this proof proves that i did move the knight in a valid l shape and i didn't cheat by like teleporting it across the map uh and using this construction we're basically able to or using this high level idea we're able to sort of engage

in a much richer and more dynamic space of games that can be built on decentralized systems um so now what me and alan are going to do is we're going to talk through three constructions of uh basically using zk starts for game mechanics um in some previous talks we've discussed uh you know one or two of them um but there's a third one card drawing which we haven't talked about before and we also at the end of this presentation um we'll be demoing a game that we've been building with some of these mechanics um it's a small kind of proof of concept turn-based strategy game uh and you know the uh one of the exciting things uh that we have lined up for you guys is in the gather town after party after this session um there's a little easter egg in the

gather room where if you go to if you find like a certain entrance then you'll actually be able to play this game for yourself as well with the other participants in the after party cool so the first construction that many of you might be familiar with is you know the idea of the cryptographic fog of war as we mentioned a fog of war is basically a mechanic in a lot of strategy games which prevents players from having vision of what each other is doing until they've you know explored an area or like discover the opponent's face or things like that um this is hard to do in a decent decentralized setting of course because um you know if i'm just straight up uploading my location or my coordinates to a smart contract then that might be inspectable to you

so you know our game dark forest uh uses a cryptographic fog of war where we essentially enforce location hiding with dk starts so essentially players are going to initialize into this know large infinite world and rather than uploading their coordinates you know x y directly to the blockchain they're going to upload hashes or commitments to their coordinates along with zero knowledge proofs um whenever you want to move between two locations in dark force you're going to upload a proof that uh you know like we said with the example of like the secret knight previously um you're going to submit a proof that basically says i'm sending forces from a to b i'm not going to tell you where a and b are but the zero knowledge proof proves that this was a valid move an interesting corollary of this is that

in order to explore the universe uh you actually have to do something akin to proof of work so you know suppose that i initialize that coordinates 5 comma 20 and alan initializes at 3 comma 8 in some world we both upload hashes of our respective locations to the blockchain and to anybody inspecting the network and to each other these basically look like gibberish however if i want to find points of interest that are close to me what i have to do is i just the best thing i can do is start brute forcing uh computing hashes closely so you know i'll hash like 6 comma 20 and 4 comma 21 5 comma 19 and you know eventually if i do this enough i'm going to get to 3 comma 8 and when i hash 3 comma 8 i'm going to get some string and i'll be able to look

on the blockchain and be like oh alan has already committed to and uploaded the stream so now i know that alan is this specific distance away from me um you know and this mechanic in dark forest is basically in order to explore space and find other players you literally have to like mine space um by setting your your cpu to complete a bunch of patches uh for those who are a little bit more interested in the details um we have some versions of our circuits uh in our open source repo um and the construction is basically is more or less what you expect you upload two hashes and a proof that the pre-images of these hashes are within a certain euclidean distance of each other um yeah so this is the core mechanic

behind dark forest which i know some people have heard of uh we've run two private beta rounds with 1k players total um and just to demonstrate like how important incomplete information is on a blockchain game like just with this simple mechanic um we had players uh you know just very excited about this game um i think over the course of our playtest we had about 200 billion gas used and saw about 250k transactions over the course of a week and broke both roxton and the x9 networks so um yeah super excited to explore this mechanic more um the second construction that we're going to be talking about is essentially using zk starks to do private random card drawing so the central problem here is basically

how can we draw cards in a way that is private uh while also um you know doing this in a trustless way so um first off you know if i want a game where i have a private card hand uh then there's the problem which is basically like how do i know that when you're drawing you're not cheating and you're not like biasing somehow the the like randomness that allows you to draw a card or you're not properly like integrating that card into your hand um we basically like to be able to have private hands that we can trustlessly verify that you know each of us is committed to a valid hand there's been a lot of thought put into this problem uh specifically using commit reveal sorts of techniques or basically you know i'll like

pre-commit to the hash of a card that i'm drawing and then later there's like some challenge period and you know maybe i have to like reveal the card um and uh these um we're interested in using snarks for this problem however because the commit reveals themes are often quite limited um so there's a couple downsides to using commit reveal for card drawing um one downside is that these schemes also require multiple back and forth so like you know every time i draw a card or make some modification i guess submit a pre-commit and then i have to something to commit and then eventually there's a reveal and there's multiple back and forth which is really annoying when you're working with metamask and you have to like confirm every transaction the second limitation is that verifying the integrity of a long chain of commitments and private state transitions is

annoying and it's going to scale with like the number of private state transitions you make so if i make a bunch of private operations on my card hand and eventually play a card am i going to have to like upload the entire chain of of hand state transitions um and if so that's uh it's gonna start being quite expensive and the last thing is that commit reveal only works for uh games that have hidden state but are eventually complete information um so in a persistent universe like dark forest uh or you know like you can imagine an rpg um for a lot of uh you know like there are going to be many cases where you might never reveal the information underlying your like planet's location or things like this

and so commit reveal is not really going to be able to help you out in these sorts of paradigms reveal only is helpful in like you know regimes where in poker eventually there's a showdown and we have to show we have to choose to show our cards or else be full um so what we're going to do here is we're just going to present a quick construction for uh how to draw and discard a little bit more conveniently using zk snarks um so the idea here is that at any given time i'm going to have a hand of let's say like three cards so blue red and green in this example and what i'm going to do is i'm going to commit myself to these three cards by uploading the hash of them up to the blockchain so suppose that i want to draw a card

and i want to like draw a card integrate it into my hand and then you know like replace and discard one of the cards that's already in my hand how do we do this in zero knowledge without having to do a commit reveal scheme that goes back and forth a bunch so the first sub problem here is how do we randomly generate a drawn card um in a way that's unbiasable by both me and the other players and the way that we're going to do this is essentially we are going to uh like integrate some randomness that the opponents provided at the end of their turn um as well as a privacy that i've pre-committed to at the start of the game uh and we're going to hash those together to get our drawn card and what we're going to do is rather than doing

some sort of like pre-commit and reveal scheme we're going to prove that we've done this properly with the correct private seed inside of a zero knowledge proof so we're basically able to say like hey here's like essentially the hash of a drawn card and here's the zero knowledge proof that uh this card was indeed the hash of you know my privacy that i've pre-committed to that you don't know um as well as some like public randomness that you've provided me so this is sort of like a randow like uh uh strategy here once we've drawn a card uh what we eventually want to end up with is we want to end up with a new hand where two of the cards in this hand are the same as two of the cards in my previous hand and the third card is the drawn card

swapped out for one of my three cards um so essentially what we want to be doing is we want to take these four cards you know my three initial cards in my drawing card and we want to permute them um and we want to get out you know three cards that i'm going to keep as my new hand and one discarded card so um how are we going to do this well essentially what this reduces down to is we need to have a zk snark for permutations um so we need to be able to prove inside of a zk's mark that these four cards uh these two sets of four cards are indeed a permutation of each other um and so how are we going to do that uh well the basic idea here is that um you know one thing that we can do

fairly efficiently inside of a stark is we can constrain symmetric polynomials and the a sub i and the b sub i to be equal so you know if we want a snark that proves um these a sub i and these b sub i are indeed the same set i can constrain their sums to be equal uh the sums of their pairwise products to be equal and their product to be equal um and this is equivalent to showing that the two polynomials with roots a sub and b sub i are identical which is going to give us that these are indeed a permutation um so we like this construction a lot we think it's quite cute um and you know there's improvements that you can make here as well uh so like the symmetric sums thing takes you know requires like exponential number of constraints in the number of cards that you're

essentially trying to make these proofs on um but you can evaluate the polynomial at a point and do like a fiat chamier thing to pick the point that you're evaluating at in order to essentially prove permutations in linear number of constraints which uh is super useful so now that we have this permutation start we can combine it with that like kind of random technique uh to essentially get private random card drawing um and that is one of the mechanics that actually our um demo game that we're going to be showcasing later involves um and we think that you know this is a really interesting mechanic to us because it really opens up a lot of potential applications like the most obvious one is um you know now with this kind of primitive we can build

card games like you know a truly decentralized hearthstone or other tcgs and ccgs um you know you basically you take your deck and you take your hand and you sort of roll them up into a snart um and then you know like we discussed before uh people have an expectation of privacy around their inventories in a lot of mmo games um and with this construction we can do a similar sort of thing with with rpg inventory so you know i'm carrying around some swords and stuff um some runes and rather than committing all of those uh item ids up to the blockchain i'm going to commit zero knowledge proofs um and whenever i make state transitions like i swap out a sword or something or i craft two items together i'm gonna submit zero knowledge proofs that my inventory has been uh honestly altered um so yeah we'll be

we'll be showing an example of this uh in our game that is going to show at the end of the presentation yeah so the last construction that i'm going to talk a bit about is uh trying to generate random and infinite meaningful worlds and starts so the kind of motivation here is that like there's been a wave of games in recent years of minecraft being the most famous example where we generate these like infinite sandboxes that worlds can interact with and create in and kind of the key here is that rather than defining the bounds of the world explicitly the world is generated as you go so you define a simple set of rules that allows you to essentially generate like just infinite landscapes and um this doesn't mean that there's like no sense of content that we put

into the game it's not entirely random because i still know that like oh well there's like oceans and there's hills and there's deserts and there's tundras and they interact in these meaningful ways and i expect that i don't find like a desert next to a tundra and all these other things um so it means that we can generate these like infinite and meaningful worlds so the most important algorithm and also the most famous that's used in these games is purlin noise and uh kind of the cool thing about perlin noise is that it's basically all multiplication and addition so it's really easy to put into a snark um and basically the like the the contrast that pearl noise makes is that it's gonna give you something which like on a local scale is smooth but globally it's kind of random and this is exactly

the this is basically the property that we need in order to make really good pro um in order to generate very large meaningful worlds so uh because it's very easy to put this into snark we can kind of uh use purlin noise as a kind of roll-up so for example the problem if if if you imagine trying to build uh minecraft on the blockchain naively well you can try to store the entire world on a chain but this is just not possible because the world's infinite and you're ready you're and you're very constrained in terms of storage so minecraft world is like hundreds of blocks tall and it's infinite blocks in any direction the other thing you could try to do is you could try to uh store the you you could try to put the purlin algorithm on

on uh on chain so you could try to make it so that whenever you like explore a new tile then the contract itself is going to generate the tile that's there but this is also really really expensive because you're constrained by compute so by putting uh the world generation into a snark we're neither constrained by a compute nor by the storage because once the stock is uploaded then you have a commitment that you're able to use a constant proving time and every time you want to interact with a new tile all you need to do is go through that constant proving time so this is actually what we did in the last round of dark forest and this happens on two levels first of all um it's already the case that we only need to store the planets that exist

so we don't need to like if a tile does not have a planet it just like doesn't exist on the contract at all and it's also the case that we don't need to compute the purlin um the purlin values of each planet in the on on the contract because we can co we can we can compute them off chain and just store whether or not this planet is like in deep space and has more rare resources or something so as an example of how this might work supposed to have this like infinite world here and just to give a visual for the kind of thing that uh that zk unlocks here suppose that the player only wants to interact with a small number of points of interest well this means that like they're able to see and generate the entire world but only the points of interest actually

exist on the contract so here this is um visualize these with these red squares and you can see that like only a tiny fraction of the world actually stored on chain so suppose that the player only needs to interact with like one in every ten thousand squares this means that we're able to essentially like cut our computation by ten thousand times so between these three constructions um with like especially with like private state and uh and with the purlin noise we think that because these mechanics are so essential to building large meaningful social interactions uh especially in modern gaming um this this is going to allow us to use uk to unlock meaningful dynamics and more importantly it's also going to let us

bring blockchain game to the mainstream cool so before we move on to our quick game demo and before we show people how to get to that and gather if you're interested in following our progress on dark force and other zk games you can follow us at dark force underscore eat on twitter we also keep a blog where we post like zkn gaming related content at blog.ckga.me and we have a telegram group for general discussion at zk underscore forest um so yeah now what we're going to do is we're going to shift gears and do a quick demo in the next like two three minutes of uh the game that we have built using zk stark's uh and private card drawing and private locations so uh for eath online and for this conference we put together a game called boat fight

which is zk naval warfare um and what we're gonna do here is uh we've basically set up a space in the gather after party where um if you walk down to the ocean and you find like the secret portal squares um you can enter a space where you can you can also play this game as well so uh i guess me and alan will just go ahead and do a quick demo of how boat fight works and what zk starks are actually doing here so right now um you know this is the boat fight landing page if you want instructions you can you know click the help tab uh and like as far as um you know if you want to inspect any of the transactions that are actually going on where snarks are being submitted up to the x die

chain you can you know look here as well um so what i'm going to do is i'm going to join this game as alice and then i'm going to join this game as bob oh did you just you might run into the race conditions okay here we go all right so i just joined the game as ellis and bob is joining the game as well yeah and it's running on as with all things blockchain might take a little bit of time to load yeah actually let me do a research but i think it might have the game id problem here okay so

um boat fight is basically a two-player turn-based strategy game where uh your objective is to destroy the opposing player's boat uh which is located at the opposite edge of the map the map is a very simple you know five by seven piled grid um and the way that you're going to do that is basically uh by playing ships onto the board cool so uh every turn what i can do is i can place some number of ships onto the board i can move my ships around and i can use them to attack enemy ships the catch here is that some of the ships are cloaked and they move around in zero knowledge so for example the submarine is a unit uh that essentially like travels

underwater um is committed to the blockchain uh like its location is committed to the blockchain uh but not actually known by the other player and uh the other players basically just like not going to see where my submarine is so i've just placed the boat down um and i've ended my turn uh and so now it's allenster uh the other place where zk snarks are used in this game is essentially uh we also have besides ships a card drawing mechanic so uh every turn you're able to draw one card into your hand of three cards just like we showed in the example construction and these cards do things like you know deal x amount of damage to an opposing ship of my choice or like heal my ship for some amount

of uh um you know hp and the idea here is that basically i do not know what allen's hand is like you know he has no idea that i have this dl2 damage card in my hand i don't know what he has in his hand um and what i'm gonna be able to do is i'm going to be able to play these cards uh and they're gonna that's gonna be like a surprise to him because all of that stuff is happening inside of a zk snark so you know let's say i you know i'm gonna attack with my missile i'm gonna move my ship and i'm gonna end my turn um and so yeah this is basically how gameplay works uh you're gonna summon ships you're gonna summon submarines you play cards um and over time you're basically trying to get your opponent's boat down to zero hp so

uh if you're curious about the game again check out the gather room um walk towards the ocean at the south side of the map and like look for a secret portal square and we'll be hanging out in the room as well to sort of guide people through uh playing zk boat fight so i think that's pretty much it cool and if you want to come on okay yeah well so now now you know our secret we've been kind of working quietly on this part of the event this is sort of to round it off so i will share i guess we'll share the link again to gather dot town in the in the chat i do have an outro talk but feel free to bounce whenever you want to um and as brian mentioned the trick is you have to

walk towards the ocean so you maybe want to explore the map get to know what that means and then yeah walk into the sea to start trying this cool all right um yeah i guess then i will shut this talk down and i'll do a quick outro and i will see you all running around in gather dot town thanks again brian and alan