"Dark Forest: Challenges and Constraints in ZK Gaming" - Brian Gu & Alan Luo

is dropped into the event chat as well okay thanks robin thank you all right so next up we have a talk um from uh both brian and alan um from the dark force team um dark force is um i mean i'll let them explain it properly because i won't do it justice but it is a a real-time rts built on aetherium inspired by the three-body problem series of books if you recognize the name the dark force is the second book in that series um and they're going to talk about challenges and constraints in zk gaming so brian allen i'll let you take it over from here and please welcome them to the stage thank you awesome thanks so much josh let's just get our screen share working first and then we'll go ahead and do a quick intro there we go cool are you guys able to see this okay i think it's awesome um nice yeah so first off uh thanks for having us just by way of brief introduction my name is brian i'm a sort of senior at mit studying math and i'm working on dark forest and i'm alan i'm a sort of sophomore at columbia studying cs and i'm also working at dark force cool cool so um like josh mentioned dark forest is a a real-time strategy game in a persistent universe built with zk snarks on ethereum uh and like you mentioned it's inspired by the three body trilogy um written by lewis susheen and translated by ken leo so um it's been a lot of fun to to work on this project and we're excited to share with you some of uh the challenges and constraints that we have found uh in building games on zero knowledge and on ethereum which is what we're going to be talking about today cool uh so first off for those of you who aren't familiar with dark forest um like we mentioned it's a persistent strategy game built with zk snarks on ethereum um the uh sort of experience of the game is one where you know players are exploring space they're conquering planets they're looking to build their kind of like galactic space empire um and uh last month we actually we ran our first semi-public play test dark force 0.3 um with about 300 beta players uh and broke robsten which was quite exciting so i think at peak the usage of the dark force core contract as far as gas usage goes was exceeding the entire ethereum main net combined so we have some things to say about scalability at the end and we're also obviously very excited for vitalik's talk on scalability later this evening for this reason um so just to give a quick uh almost like little demo of what dark force actually looks like oh one second i think my oops how do i oh click play no no i think okay here we go yes cool so this is a little uh uh just sort of demo video we just recorded on uh dark force v0.4 gameplay so dark force v 0.4 is the next version that we're actually releasing today so the first round of whitelist keys is going to go out later this evening but as you can see it's a space conquest game there are planets in a large universe you can make moves between these planets planets have resources your goal is sort of to explore and conquer space um and that's sort of the uh mo of the game yeah and if you're interested in checking out v0.4 you can go to zkga.

me and we'll have contact info at the end as well so today we're going to be talking about uh challenges and constraints in building a fully decentralized persistent strategy game that is actually fun so you know as we all know ethereum as a computer is extremely slow but there's been a lot of excitement around blockchain gaming the last couple of years uh just especially given the potential of games to to uh you know really showcase the possibilities of technology so uh yeah our goal is to create a persistent universe almost like a you know infinitely moddable scriptable eve online sort of game uh with economic value at stake and all these sorts of things um again and you know have it built entirely crypto natively so uh there's no notion of like we're not just like periodically committing stuff to the chain we're not like having some system where some game assets happen to be like exitable nfts or something it's like the data layer of this application is on ethereum uh and anyone can interact with that programmatically however they like so the first challenge and the whole reason why dark force is built on zk snarks is that incomplete the notion of incomplete information is really hard to achieve on the blockchain so what does this actually mean well to understand what this means first we have to understand uh the difference between two classes of games complete information games and incomplete information games so uh for those who aren't familiar with the concept complete information games are games where all players know the full state of the universe so you can think of games like chess or checkers where basically you know i know where your pieces are you know where my pieces are there's no secrets anywhere on the board on the other hand uh incomplete information games are going to be games like poker or starcraft where there's some hidden information and not everybody knows you know everything that's you know going on in the game so i don't know your hand necessarily and you don't know my hand um or you know in a lot of strategy games there's the notion of a fog of war where you don't know where your opponent's base is until you've you know explored the map and found them so uh traditionally incomplete information games are often able to offer players a much richer space of possible strategies to execute um the reason being because when you have this asymmetry of information between different players it opens up uh strategies like deception or conditional coordination um you get to see like sort of these large-scale social dynamics or even like emergent player behaviors um so you know traditionally most pretty much all popular mmo massively multiplayer online games are going to be incomplete information games so you know you think about like we think about rts games we think about rpg games all these all these sorts of things um unfortunately if we're trying to build a multiplayer game on the blockchain well this is almost at odds with the affordances that the blockchain allows us in particular by design blockchains and decentralized systems are often systems whose data layers are completely open and transparent so you know the evm state is completely inspectable like everybody knows everybody else's balance i can you know look up your balance you can see my balance we can inspect the state of this contract and so it means that the notion of keeping private state on a blockchain or a decentralized system is actually quite tricky um you know if i if i want to like move a piece on this board or something like that naively it seems like i have to commit the starting location of the piece and the ending location of the piece and that's that's going to go onto the evm and everybody's going to be able to see where where i am so you know this means that the games that we've seen so far on blockchain are oftentimes you know we've got games like cryptokitties um so we've got these like trading card games where everybody knows for example who owns what kitty and what all the properties of each kitty are but we don't necessarily yet have games with meaningful notions of incomplete information or private state so how do we get information asymmetry on a blockchain well it turns out that with some zk snark technology that was made possible about 12 months ago we're now able to keep hidden information uh in gaps and you know use this to create uh some class of incomplete information games so you know how exactly does this work well let's suppose that we've got some incomplete information game where players are keeping you know a notion of private state so on the left-hand side of this diagram we've got this player who has some secret state s1 instead of committing their private state up to the network which would make it public what the player is going to do is they're going to commit a you know a commitment to their private state so for example a hash of their private state up to the network and they're also going to associate that with a proof a zero knowledge proof that that hash does indeed correspond to a valid private state so by submitting this zero knowledge proof on chain what they're essentially saying is you know here's a hash of my private state if you inspect this proof you can verify that this does not correspond to a private state where i've like given myself extra resources or cheated or anything like that so what happens when a player wants to make a state transition well if the player wants to transition from private state s1 to private state s2 what they're going to do is they're going to publish a commitment to their new private state so this would be c2 along with the zero knowledge proof that there is indeed a valid state transition between the private states underlying commitment c1 and commitment c2 so morally this zero knowledge proof is saying something like um you know for example in a chess-like game you might say something like i'm moving my knight from secret location a to secret location b i'm not going to tell you where a and b are but this zero knowledge proof does prove that the knight moved in an l shape it was a it was a valid move um so in this way the player is able to keep you know players are able to keep a meaningful notion of private state but zero knowledge proofs keep them honest and you know these proofs are going to keep them to you know playing consistently by the rules of the game so you know just to clarify like the information that players know they know their own local private states um but information that any you know public person just inspecting the network knows all they're going to be able to see is c1 and c2 and that s1 and s2 is entirely obfuscated all right so i'm going to talk a little bit about trying to actually build a game that's real time on ethereum and the constraints we have there so in particular uh there's kind of two large problems the first is that we can't really schedule any sort of cron job we can't really schedule anything that happens in the future so traditionally if i'm gonna play multiplayer game on a centralized server i can like queue some moves and then maybe my client disconnects and these moves are queued on the server which is gonna like modify the game state afterwards but if i make some moves in dark force and then close and then close the client then there's no way to actually ensure that these moves are going to be um are scheduled to happen at some point in the future and on top of this every time i submit a move to the each time i submit a move to the game it takes a few seconds um to confirm because of the ethereum block times so the first technique that we use to solve this is um we it's something that we call lazy updating so in particular we have some resources in the game which follows some sort of a growth curve and suppose that say i have like energy and i and at some point um at some point in time i have my energy at a certain value and over time this grows so for instance at t equals zero uh as a player i can move shifts from planet a to planet b and i can schedule them to arrive at uh time t equals 10. and then at time t equals 10 the number of shifts that i have on the planet is going to change however at this point i can't actually schedule a cron job for the state change so what i do is instead i cue the event or i cue the arrival of this event occurring on the planet then at t equals 15 after uh any other player makes the mutation on planet b i can retroactively apply the event as and i can kind of pop the stack and go through every event that's been queued so the other solution that we have is um that we're we basically try to design the game around longer time scales in order to circumvent the fact that it takes time for transactions to go through so in particular if we have transaction if if we have moves that take like on the order of 10 to 15 seconds then uh block time to three to 15 seconds meaningfully impacts experience but if our move times take from like 10 minutes like 2 hours then in this case the 3 to 15 seconds basically doesn't make a difference now we actually have a nice side effect from this which is that we not only wants to build something which is technically interesting we also want to build a project that can really like target not only people who are really interested in crypto but can target like general consumers uh basically we want to be able to like build a game that's really accessible and fun as well and games that have typically done a really good job of this are games like pokemon go or candy crush which in which you basically play for a little bit at a time and then you check back in a few hours later so the way that we kind of see this internally is that this is not so much of a restriction but it's more of a constraint that we want to lean into which is that if we build a game that occurs on longer time skills it might actually be better for targeting the kind of audience and getting the kind of players that we want um in particular if we build a game that's really apm sensitive where the number of moves you make and how quickly you make them like meaningfully impact how well you can play the game this is not only bad for ethereum but this is also really bad for casual players and our last solution for this problem is that we want to build meaningful client-side mechanics so because we have a lot of private state that's all held off-chain we can interact with the game in a way where we're only interacting with that private state so for instance planet locations are held as private state and this means that we can this is the weird thing with the screen recording box um wait one sec let me oh here we go here we go okay uh so in particular you can you can explore the universe and find new planet locations and all this happens off chain you don't actually need to interact with the blockchain at all so this means that players can play the game for stretches like 10 to 20 minutes at a time without ever actually needing to interact with the blockchain at all um so the other challenge that we have is we want to build a rich and meaningful universe but we have a constrained environment it's not only constrained by time but it's also constrained by compute and by storage um so the way that we approach this um is we basically lean a lot into procedural generation so procedural generation is a technique that's used a lot by games like minecraft where you basically set a some number of simple rules for the universe and you can use these rules to generate what the universe will look like so um the the picture here shows purlin noise which is this function that's often used and you can basically think of this heat map as being analogous to like mountains and hills in minecraft and this means that we can have like dense areas we can have hot areas we can have oceans we can maybe have areas where the planet uh density is changed or plants are more powerful um and we also and there's also a neat side effect of this which is that since since we need to roll this up into a snark this actually means that we can save some of the some of the compute from the contract because the contract doesn't actually need to be aware of the purlin function and only needs to be aware of whether or not the um of whether or not the proof is correct and uh this also so so we also lean into um this kind of generation on the on the client side as well because on the contract the contract is only aware of planets as being some sort of id with some sort of prop with some properties it doesn't actually have any knowledge of what these things look like so the way that we present this is that we deterministically from the hash of the planet use this to generate all the planet properties and this way people who are using the same client are going to be able to see the same planets um so the thing that this kind of kind of leans into and where this presents another constraint is the fact that dapps are all client agnostic so people can only people are using the same clients are they going to see the same planets but people can all bring their own clients and the problem here is that if we want it is that typically it's already very hard to design games and some games in the past like runescape have had problems where they design a centralized player experience for their server and they give people a client but then people start bringing their own clients and this can do things like show additional stats or maybe cue moves for you in an automated way and this is basically guaranteed to happen as long as we're writing games on ethereum so again we try to lean into this and we don't really see this as so much of a restriction but it's more of a constraint that we that we're able to lean into so it means that we want to lean into interoperability we want to link into interrupt where like where other contracts can be making calls on the dark forest client and the way that we do this is we build a really simple set of rules we say something like we we have a notion of distance and we have a notion of resources but we don't actually say what these resources necessarily mean and what this means is that someone could technically reskin the entire client they could write zk fantasy or they could write zk spaceman spiff and we can we we could write a different version of the client where instead of sending forces between planets we're sending gold between different like castles and those dragons and flying around and everything but at the contract level the contract is only aware that there's resources moving around it's not necessarily aware of the cosmetics or or of the specific or of exactly how the game looks like to the user yeah and to jump off this um this is not just something that necessarily exists on the cosmetic level but can also exist on the level of mechanics as well so you know even with our last game uh that lasted about a week we saw players you know writing like modding clients writing extra features um what we're really looking into is this idea of being a like very moddable boughtable like interoperable game from day one so things like you know i mean just as an example of of things that might happen with this in a traditional game if you wanted to if you as a game developer wanted to introduce a trade feature um where players can sort of exchange resources then what you might have to do is like on your canonical client you would write a trade button and then you'd write you know the trade server around and you know probably get that all the way to the data layer here all we have to do as developers is we define essentially the physics of the game universe and implement that as smart contracts someone else can come in and they can say something like well you know i want to i'm going to spin up an escrow smart contract that says you know anybody who deposits three ether into this contract i'm automatically going to send them some amount of like silver from my planet to theirs um and in this way you know you can you can get these sort of like coordination constructs that are happening on the uh at the contract level without any input um from from some centralized authority that's determining what the gameplay experience ought to be on the client uh on the client level what we're trying to look into now as well is you know with v0.4 we're introducing um an interactive terminal as as a first class feature in the game where basically anybody can write and share scripts that perform different automations for example you know sending uh forces programmatically between planets or anything like that and what we're really looking to do and what we're really excited about is the prospect of the game that is you know really built and designed uh by the community um and and just leans into the creativity of the player base uh in order to to really achieve its potential cool so the final challenge that uh we're just gonna briefly touch on is challenge of scalability um as mentioned uh our last play test which was a private beta with about 300 players um exceeded the total transaction volume of mainnet uh and and this you know especially with current gas prices this means that the game is currently unfeasible to be played on like ethereum eth1 l1 so you know what we're looking into here is we're looking at all sorts of different uh strategies for um potential like layer two solutions uh like i know that optimism they just um they just announced their test net and and there's a lot of great progress going on with zk roll up as well which we're super excited for um so roll up solutions in the long term uh and as of you know the current iteration of the v0.4 where we're actually going to be running this one on you know the l2 xdi stake network which has a token bridge to ethereum uh you know is essentially just another evm swap out the rpc endpoint and what this allows us to do is you know we can introduce the notion of economic value into assets in the game uh while keeping low gas costs uh security guarantees and centralization obviously aren't going to be as great but as a staging environment um you know this is this is a good way for us to be testing out what potentially the future might look like uh once there are these sort of off-chain l2 solutions for uh cheaper computation and storage cool so i guess the last thing that will mention is that uh dark force v 0.4 starts today uh we're sending out the first batch of invite keys tonight and uh there's a number of interesting things for those of you who have seen v0.

3 that we're introducing here um one thing is burner wallets so you know uh players in the previous game who would make thousands of moves over the course of a week would have to click that pesky little metamask confirm button like literally thousands of times uh burner with burner wallets and sort of an in-page um provider we're able to hopefully clean that up for a lot of people we're on the xdi stake network now so that allows us to test kind of small amounts of economic value while keeping gas costs low so shout out to igor and his team for for helping a ton of that um we've introduced kind of a you know interactive terminal so you can write little custom scripts and share automations and things like that and you know a big thing for us has been getting the purlin noise zk snark working um and that's actually like that is only possible because of the work of you know jordy and his team at ident three on on tools like circom and snark js and for continuing to make those more efficient um so something as heavy as parallel noise would certainly not work without the existence of tooling such that um and a number of other uh kind of you know fun little mechanical changes um and quality of life upgrades so if you're interested in following dark forest the game um you can subscribe to our mailing list and blog at blog.zkga.me uh we're also on twitter at darkforce underscore eath we love to ship posts about snarks and we have a telegram group for general discussion at zk under underscore forest and i think that's all for us we'll take questions now great thanks guys um yeah we'll see if there's any questions in the chat while we kind of wait for that to queue up um i've got one for you guys um i would love to know if there's any uh you know either gaming or zero knowledge related ideas that you have that you think would be good for hackers to work on uh adding online this month you know maybe you've got a side project idea that you haven't had time for yet uh you'd love to see someone ship in three weeks um if you've got any uh i'd love to hear about them oh yes so i think that there's definitely a lot of and we you know sort of juggle this around uh in some like late evening conversations oftentimes as well but you know the the potential for zk in gaming we think is really huge and a few things that we've sort of bounced around are things like you know if someone put together like zk battleship or something this is a hopefully fairly straightforward um kind of thing to build but it would be really great to just showcase the process of building that end to end you know putting together a tutorial or something um things like i mean you know there's constructions for like a zk really like slow motion agar.io uh that could be done um and within dark forest itself things like scripts or re-skins or you know interop contracts like you know you nest smart contracts can own planets now in dark force v 0.4 and building almost a nested game inside of the game which allows players to sort of dictate how like a planet resources allocated or something like that could be very cool and we're always really happy to chat about that with anybody who who might be interested um i know some folks the last game spun up things like custom miners or like other like hacked clients um our stuff's all open source so if folks are interested we're happy to share cool um how uh how fast are the keys going out for version 0.

4 and this is a question from the chat uh they're going out quickly or you're trickling them out how does that work yeah we're going to be trickling them out over the the next couple of days um usually in the first few days we you know we we start with a little bit of a slower onboarding just to make sure that there's no you know we can fix any like critical issues that come up um but uh we're hoping to get keys out to a substantial subset of the wait list for this game you know in the next half week to one week got it um a question from our team um what was the inspiration for combining these elements into this game i mean obviously it's named after the dark force trilogy but you know was that the inspiration or was there something else and you kind of figured out the name afterwards um yeah i guess so the original idea for dark force came from like i think we um you know it was back in like summer of 2019 and i think that a lot of these zk tools had for the first time just become viable so in particular uh jordi had just published a few months ago um what was called websnark at the time which made it feasible to generate zk proofs in browser um around the same time uh you know we happened to read the three body trilogy and you know a couple days later there's this idea of like oh wait a second like you know we could make a cryptographic dark forest um dark force is the second book in the trilogy and for those of you who are familiar um there's there's sort of this thought experiment around you know civilizations like discovering each other in the universe and sort of the the interesting dynamics of information asymmetry there um and it was just kind of like oh yeah you could you could do this with zero knowledge proofs um so that was a really fortunate coincidence that we happened to stumble on both of those around the same time yeah and some of the stuff in terms of like game mechanics and cosmetics are like these aren't necessarily the only ways to do this but like given from where the ideas came from and given the constraints they're either one of the only or one of the easiest or one of the most obvious ways to do these things so in particular like procedurally generated planets well it's like well we have the notion of like information asymmetry being important and this is where we have this like metaphor of like space space combat because you like don't want to reveal your location to other civilizations and then we have the notion of like well we need to use like like we have to use some sort of random generation that's and this kind of just like led to like planets being the kind of like main cosmetic thing so a lot of it like came out of the just came from the set of constraints and even for game mechanics like we're constrained to the set of game mechanics that are still like good and non-degenerate in a world where there's going to be lots of bots so a lot of the things just kind of like fell into place as they are now and we're still experimenting but like given the set of constraints um there's only so many ways to build the first version of dark forest all right okay another other question from the chat do the game mechanics in their current form favor those willing to spend tons of money i assume that it does and is that intentional so they favor those willing to spend a lot of money only a little bit in the sense that you're like it's always strictly better to make more moves rather than make less moves but this also depends on what our scoring function is because in the current version of the game um like we're gonna like or in the last playtest we distributed prizes based on just like the top players and therefore you had some you have some consideration for like well if i want to maximize the chance that i get the largest um prize then i want to be spending the most money but these in the future these incentives aren't super clear because ideally we want to build a version of this game where the planets themselves and the in-game assets actually have economic value so in this case the game you're playing that internally is like wait is the amount of money i'm spending actually going to increase that the economic value of my empire and in this case it's actually not so clear anymore whether or not it's beneficial to be spending all these moves in particular we've um this is a constraint that we're aware of and there's always going to be whales who spend a lot of money and there's always going to be people who write bots so this is why we kind of take this like physics based approach um and why like from the very beginning of the design we're trying our best to like make our system robust to this so for instance we have like a sort of exponential scaling and planet rarities and also in planet strength and this means that once you have like a level four planet you basically shouldn't care at all about level two or level one planets anymore because they're just so much weaker that it just like doesn't add anything to your empire um so this is a consideration and hopefully this is not going to be a problem it might be a problem right now but we're hoping i mean part of this is play testing as well but we're hoping that we'll be able to build something which is robust to this in in the future okay and if you guys have time to actually talk more questions too so i'm just going to keep going um so another question besides games um you know what are other use cases uh for zero knowledge tech uh that you're most excited about so for example like uh eny uh has this system that uses uh zero knowledge tech for like an enterprise context are there other applications there that you think are particularly interesting or promising yeah i i think like you know one of the things that we feel most like clearly as a pain point is all the scalability stuff so um once you know zk roll ups become more accessible and and production ready like we want to be hopping on that train as as soon as that stuff is feasible so zk um zktech for scalability is huge um i think like privacy obviously is a massive one as well i mean i guess it's a little bit of a basic answer since scalability and privacy are sort of the go-to's but um yeah scalability privacy and gaming are where we sort of think about for the immediate uses of zk there's one answer which is not so much directly answering this question but it might be interesting just in the vein of like other things that that that that's cool about this and i guess this is also not even like a native block chain thing either but one thing that or sorry i'm native to zk the blockchain general but like one thing that's interesting is like because we have access to interop um one thing you could do and brian mentioned this is you could have like infinite worlds within each planet so the thing we think about here is like well you can provide like an interface and this is some sort of like metaverse where you can have like each planet is like proxy by some sort of other contract and the reason why this is interesting outside the scope of just gaming is because like like this would be kind of a prototype for what like a real world in the sense that like people care about things that are meaningful and are like connected by space so you can have like a like so the really bad example is you could have a virtual meeting space on some planet and because we have like like because information is a first-class resource and because like locality is enforced by the contract and it takes time to move to places well then this is like a meaningful proto version of like a metaverse um and maybe dark force is not the one who actually builds this but maybe it's the one that proves out this concept cool okay um and one more question so um we had someone ask you know how did you guys first get interested in ethereum you know what was the path i mean if it's a long story we can get the short version but what was the path that led you to working on this for sure yeah um so this is actually really interesting to me because um i uh have done some work with the ef on thinking about how to get more like university students interested in ethereum but um like for me personally uh you know a mentor of mine was you know he joined the ethereum foundation in 2017 2018 um you know we interacted through some other like tech and and math related things and you know he was sort of like you got to check this ethereum thing out it's awesome like you know people are doing some amazing stuff um so i started going to a few conferences and workshops um and you know eventually it got to the point where i was like oh wait like you know there's a meaningful thing that i'd actually be really interested in building um and so but it was really like my entry point was one specific you know person who who basically was like a real evangelist uh for crypto um and then i guess yeah i have a similar story here except it's like one order of separation in which the for me the evangelist was brian where it was like i was just like i i was i met him at some like event for college students and we were just like i was just working on some random apps and brian gave this like a kind of small presentation on ethereum and i was like whoa this is really cool and also mentioned that he was working on this game called dark force it just it just happens that i really like games and for me what's like really cool about this is that like it's pretty rare that you see um like like nowadays in gaming like people tend to just like take the same ideas and just like they just turn out sequels over and over again each year it's pretty rare that you see a technology which like forces first principles and new kinds of thinking so what i really like about ethereum here is that like because of the constraints the constraints actually force you to design games in new ways in particular i've always liked the idea of like infinite like worlds but there's always been a problem in games like minecraft and no man's sky where the worlds don't really have any meaning you have these like best infinite worlds but in practice they're all the same in practice like someone could have given you a bucket of like 100 worlds and you wouldn't really care but on ethereum because of all sorts of things animal scarcity yeah like so there's credible scarcity there's true ownership and there's like there's all sorts of other things there's much more of a realness and meaningfulness to these like procedural infinite assets so for me this is actually the thing that drew me into ethereum was like i saw cryptokitties and i was like whoa this is really awesome and really cool that's something i'm into but it could also be so much more and that's kind of the angle i come in from this yeah yeah and then we have we have um two other teammates actually who are uh not here today but you know uh scott and robert they're also college students we all met at the same event um like a hacker house sort of thing called hack lodge um and i believe that you know scott was actually into ethereum before any of us um and the way that he made his way into crypto was by buying some like dogecoin many years ago and then realizing like oh wait what's going on with this um and and robert's similar to alan um you know so yeah i mean we think a lot about like what can we do to bring in more students in university into the ethereum ecosystem yeah that's great guys yeah i think those are the most two coin pads like me knowing someone great who says hey this is cool or buying dogecoin and realizing that you should know something about it uh if you're going to own it yeah thanks guys that was that was an awesome talk really excited to see what comes next for dark force uh and thank you for being with us