How To Hallucinate A Server by gubsheep | Devcon SEA

[Music] thank you [Music] Sam awesome thank you Sam for introducing the morning sessions uh hello Devcon I am gub sheep and I'm here to talk to you about hallucinated servers thank you for joining us on this morning I know it's not easy to make the uh first morning talk of the day so I appreciate everybody for making it out here um by way of introduction I'm gub sheep I'm one of the co-founders of zerx Park uh in particular I work on a lot of Applied cryptography projects from research to production and today I'm going to be talking to you about frog Zone which is a game that you might have seen downstairs if you swung by the Frog crypto Community Hub so downstairs at the Frog Community Hub we have two tables of four machines each you can log into one of these machines using your zoo pass by scanning a QR code and you'll be dropped into this very simple frog game that I'm going to describe now so this is a screenshot from the game essentially frog zone is a four player game where you control one of four frogs on a 32x 32 grid so there's a 32x32 grid there's a map there's some items there's some monsters um you can attack the monsters you can pick up the items you're trying to explore the map you can only see the 5x5 are area around you and in a time limit of 5 minutes you're trying to make it up north uh to the ice biome to find and slay the dragon and this is a Cooperative game so even though you don't know where the other players are all of you are going to have to collectively come together to figure out um the right path to get up there and then use your combined items to uh finish off the dragon so as you can see you know my Frog's moving around um I just uh destroyed some enemy here here I can see there's a wooden sword I can go over to the wooden sword and pick it up um and if I do that uh I should see my attack stat up there increase so you can see you know frogs have frogs have lives they have different stats let's just watch that happen real quick and as you can see the rest of the game is shrouded in this fog of War right so I can only see the 5x5 area around me um and in short you know it's a pretty simple game right there's a very very limited set of mechanics um in terms of you know the game in numbers the total size of the game is about a total of 150 bytes that's the entire state of the game the front desn't is built and react in phaser the source code for the backend is about 500 or so lines of C++ not including boilerplate that might be something like half of that um and it took a about a month for a team of of devs and collaborators from gaus labs and xerx park and psse to build this together so um why am i showing you this why am i showing you this incredibly simple game that uh you know a a kid could have probably built as their first programming project well essentially the interesting thing about this game is that the back end of the game is running entirely inside of fully homomorphic encryption and to our knowledge this is the first time a multi-user application with a backend that is running inside of FHA has actually been built so that means that all of the state of this game is encrypted using FHA and all player actions and everything happening inside of the game is happening inside of f H thank you so one question you might ask is why bother running this inside of FHA right FHA is super expensive well one thread that we've been pulling at in the last year is this idea that Technologies like fhe can enable us to run what we think about as hallucinated servers so let me describe what I mean by that today if a group of us wanted to come together and to build some sort of application that all of us might use like let's say a social network for Devcon attendees the way we would do that today is that we would have someone rent out an AWS server write some sort of backend code and then deploy that backend code to the web server and then each of us would you know using our computer or using our browser or client or whatever else talk to this backend server making API requests to to you know update and retrieve the state of the application now using Technologies like programmable cryptography another way we can imagine doing this sort of thing opens up so we can imagine in a world with programmable cryptography that rather than there existing a specific physical server with a physical footprint that's running all of the computations of the application instead every participant of the application might store Something Like A cryptographic Shard of the overall State and using Technologies like multi-party computation or fully homomorphic encryption we could cryptographically simulate the execution of this virtual machine using things like ZK proofs or FHA to advance the state of this arbitrary computation one step at a time ensuring its consistency ensuring that everybody is only you know having access to the data that they're supposed to be able to um while doing so in a in a decentralized multiparty way without needing to rely on a physical server anywhere that actually is the source of Truth for the system so you know this this sort of opens up a lot of interesting questions what if our Digital Services ran as these distributed hallucinated computations between just the relevant parties we could imagine having this abstraction for a server where instead of you know servers run by Zuck we have a server made of math that's perfectly secure privacy preserving verifiable interoperable with every other service built in this way Etc of course right now we're very early on our journey so in terms of the game in numbers in order to run this extraordinarily simple game 150 bytes of State with four frogs on a 32x32 grid uh we are using nine machines to coordinate a variety of different MPCs together so we have four MacBooks downstairs and then we also have five 192 core AWS machines in the cloud costing us about $200 an hour to run this game every binary gate involved in the execution of any operation takes about 10 milliseconds to evaluate which is about a 1 billion times overhead on top of ordinary computation and for every bit of plain text state in this game this bit will blow up to about 3,000 bits actually I think this might be 3,000 bytes of Cipher text I need to check on that but it's a huge overhead so the way that I think about what's going on is it's sort of like you know we've built almost this particle accelerator and spent enormous amount of resources just so that we can suspend in the middle of The cryptographic Ether for a brief instant something that looks like the higs bow Zone and we can we can sort of hold that stably um and in short we have built what I believe is the slowest and worst performing game in the history of computing okay so how does it work let's dig in a little bit to what's going on under the hood so like I mentioned there's about nine machines that are concurrently performing various things together uh in order to hallucinate the state of frog zone five of those machines are C 6A 48x large AWS machines they have 192 cores each 384 gbt of memory and then we've got our four MacBooks which are our local clients that are involved in the decryption MPC so whenever a player wants to make a move uh you know move their frog up down left or right or attack a monster or pick up an item they're going to send the encryption of that intent of that request to one of these five servers that server is then going to share that encrypted request with all the other servers and each of them is basically going to keep a replica of the fully encrypted state of the game so that move is then going to be you know uh shared with between all of these massive servers and then execute it inside of FHA to update the state now in order to retrieve the latest state of the game and in particular that 5x5 area around you each of the client machines is going to be talking to a dedicated server that will handle the request of executing a view function on the overall State and then returning the result of that view function in encryption to the players so we need five servers here because all of these operations are enormously expensive we're using these machines to distribute the load of both executing in FHA all of the player actions as well as executing the view functions over the state to return back to the players finally because the state is returned back to the players in encryption no single player has the decryption key for the whole game in fact you know no single party in this whole system has the blanket ability to decrypt and read state so the four clients each contain a decryption key Shard and they have to coordinate using a simple multi-party computation in order to decrypt any individual piece of state so I'm going to send out requests that's kind of that big box that that switch in the middle of the four clients for those who have seen the machines downstairs that is helping to coordinate the the peer-to-peer networking that needs to happen for these machines to talk to each other okay so what's going on with the servers here I've described the the idea that a hallucinated server would not need a physical machine that's actually the source of Truth for the application State and yet I just showed you a diagram where there's a fleet of five machines well it turns out that in this case the servers aren't theoretically necessary what they're doing is they're performing a deterministic operation that involves no secret data so they're basically just these you know cattle which you can delegate computation to um they're performing these operations on top of encrypted data using a deterministic FHA scheme uh theoretically we could run all these computations on the local machines and just have them cross check each other but for performance reasons based off of where fhe um is today with the libraries we're using Phantom Zone we need to you know sort of add some additional computation power in addition to the four client machines that we have so that's all that those servers are doing um I want to talk now about some tricks that we use to get a game working in such a constrained environment so building out this game with the other collaborators has been a really interesting exercise it kind of reminds me of what I've read about game development really really early on you know with the first uh personal computer games in the 90s or even earlier than that arcade machines in a lot of these settings game developers were working with very limited constraint sets and for me also this kind of reminds me of the early days of building blockchain based game so about five years ago I worked on a game called Dark Forest and this was before l2s um this was before there was widespread kind of tool chain support for ZK snarks and you end up having to do a lot of interesting little hacks to even get something so simple working so going back to our constraints we have about the ability to work with maybe 200 bytes of plain text State we have a 1 billion x computation overhead uh we have an overhead that's somewhere in the thousands in terms of how big Cipher texts are which have implications about how much State you can be transmitting over the network especially here at a conference where tons of people are using bandwidth to find frogs or you know access their ticket things like that um and one thing that we wanted to hold ourselves to was we wanted to keep each player action operating under one second so every action that a player can take should execute in about one second and that means that if all four players are constantly making actions then players can be rate limited to performing an action once every about four seconds or so um so we want to be able to squeeze the most gameplay out of our constraints and uh you know we can start by even looking at how do we represent player actions so all of those different actions that you can see in the game whether that's uh picking up an item or moving to a square or attempting to move onto a square you're you're not allowed to move to or attacking a monster all of those are simply serialized as two encrypted bits that represent a direction and under the hood what the fhe circuit is going to do is it's essentially going to execute all of these possibilities for what you're moving on to or what you're attacking Etc it's going to execute all of that simultaneously so what that means is the fhe circuit is going to take in the approximately 200 bytes of game State as well as two encrypted bits that represent your direction and it's going to check for example for each of the tiles that you should not be allowed to move on to we'll do an equality check between each of those pairs of coordinates and if any one of those equality checks turns up true then I'm going to return your new coordinate as equal to your current coordinate and not equal to the the coordinate that would be computed by incrementing your X or Y position similarly with an item we're going to simultaneously check for every item is the coordinate you're trying to move to uh you know that that result of applying the direction on top of your original coordinate is that coordinate equal to each coordinate of all of the items and if any of the items turn up yes then we're going to prevent you or we're going to cause you to update your internal state to reflect the item upgrade that that item might give and we're going to mark that item as consumed and then we're going to refresh the entire state so uh we basic Al have to figure out some strategy for factoring out the state into these different pieces and then running these checks efficiently over all of these different uh State coordinate pairs another thing that we have to be very aware of is the data constraints so um we don't want when when we're returning back something from the hallucinated server to a player for the decryption phase um we don't want to have to return a bunch of custom fields for all of different kinds of entities that could live on a tile in particular because the computation that is returning what should be on each tile lives an encryption whoever is making that return statement cannot know what's on each of those tiles so we would have to you one naive way you could imagine implementing this you could imagine implementing a big checklist that contains all of the items and all the monsters and all of the Just all the entities and for every single one of the 25 tiles it would it would return an encrypted bit for each checkbox in the checklist of whether that particular entity is at that particular tile and because that bid is encrypted the server whoever is running the FHA that could be a local client would not know anything about what actually lives there um that's too expensive given the cipher text blowup so what we do is we have a 32bit format uh or it might be 40 actually um for what is actually being returned for any given entity so we'll do some computation the circuit it will result in 32 bits depending on what those bits are after the decryption phase that will tell you how to interpret these 32 bits so the first bite tells you you know various types of metadata The Entity type the ID knowing the entity type tells you how to interpret the the remaining three bytes um for the second bite if it's a player or a monster that represents the hit points if it's an item it represents the uh additional upgrade to your hit points um for example the fourth bite if it's a player that represents score if it's an item or a monster that represents how many points you get for picking up the item or points for defeating the monster and in this way we can we can make sure that every tile that's being returned is simply this uh 32bit thing without needing to special case for every single type of entity moving Monsters uh was a fun one as well so basically you've got these four frogs that are moving around in the universe each of them can see a 5x5 square around them but there's also a bunch of stuff going on in between each of the players viewports so monsters are actually these autonomous agents that are moving around in side of the global fog of War there's some notion of global private state state that is being executed on consistently but which nobody in the game neither players nor any of the delegated computation servers know what's happening so um in order to do that well this is very expensive because for every monster we want to try to move we again have to do that check of is that monster moving to uh on a collision course with any of the the boundary cells so in order to make it feel like there's a bunch of monsters and they're moving in a reasonably uh performant way what we have is we've just got these different kinds of monsters one of them one of the kinds of monsters is immobile so we just never have to do this another kind of monster we do have to do all of those Collision checks and then a final kind of monster the bat here it's a flying monster so you don't have to do the Collision checks which you know speeds up things a lot on our end and still make sense in the context of the game there is a story about Randomness here as well so whether it's the initial conditions of the game or how the monsters are moving you don't want any particular participant to know that but you want that to be able to happen in a way that is correct and consistent with the execution of the program so at every stage and at the beginning of the game players are going to submit they're going to randomly generate some Randomness locally encrypt that and send that up to the server the server is keeping an encryption of a global random State and every time it receives a request it can mix that in and then it will use that Randomness to seed various actions on NPCs or or whatever else so the direction that the NPC's move is determined by by this random State okay so that's the current state of things you can try the game out downstairs just as a warning it's very slow and very clunky and very brittle I would not exactly call it a good gameplay experience um but you can play it and you can try to slay the dragon um so another question to ask is Where Do We Go From Here Right Now that we've demonstrated that it is in principle possible to build an application in this way what might we want well one thing that has become really clear is we might want more performance whether that means you know adding a fleet of 10x more servers or whether that means improving the underlying FHA protocols or the libraries that Implement them so with 10x more compute we would be able to run this actually as a local computation between the four machines without requiring these delegated servers to help us perform these untrusted FHA operations we could imagine procedurally generating the map itself so imagine that rather than a fixed hardcoded map that is plugged in at the beginning of the game in encryption all of the players submit their Randomness and we use an algorithm like pein noise to generate a new map every single time that truly no one not the developers nor the delegated servers nor the players would know another thing that's going on here is that in the process of building this we realized that fhe as a technology is limited in certain ways so I previously described how in order to make any operation on the game you would have to feed the entire previous game state in plus the mutation that you want to do on top of it and run a state transition function over the entire thing in fhe well that's not really how we think about programs today we usually think about programs in terms of memory access I can access such and such array element I can update it I can read I can write to this um and that ends up being much faster because I don't need to carry the entire state with me on every operation there's active theoretical work being done on FHA protocols and MPC protocols that might fit more naturally with the the program the memory model one thing that's been really annoying especially with a conference Wi-Fi is the decryption stage that must occur between all four of the parties using Technologies like obfuscation and functional encryption which we uh discussed earlier this week you would be able to make it so that the view functions so long as you're calling the correct view view function can return to you the appropriate state that you want decrypted so without a need for this kind of group decryption so that makes the hallucinated server behave at that point almost identically to a server um we want verifiability so whatever machines are executing the computation the FHA computation right now they can't learn anything about the computation but they uh can execute whatever function they want they'll just they could be executing some nonsense and then finally you might want something like a data availability layer you know if you want to add in properties like censorship resistance or search in forms of consensus perhaps you want to treat frog Zone as something like a rollup so that's an interesting direction as well um there's a few sort of conceptual or philosophical questions that arise as well right right like is this an autonomous world you know somehow the bat that's flying around an encryption that nobody knows where it is it has a kind of autonomy that is a different sort of autonomy from the kind that we get from blockchains and smart contracts but it does feel like a new dimension so what is you know what is the subjective experience of being a bat that lives in frog Zone that lives inside of encryption you know maybe this is how we're going to do mind upload technology in the future I I certainly wouldn't wouldn't want to upload my brain into the cloud in PL text but I might do it if if it's encrypted or OB fiscated so that's all for this talk I just want to shout out um a number of contributors who have made this possible this was a joint effort uh it was built on top of Phantom Zone which is developed by gaus Labs a bunch of folks from psse helped enormously in Runing the circuits Han edu and CC soan and Maran helped to build out the front end um and a bunch of zerox Parkers as well helped with the deployment of this um so that's all I've got for this talk you can scan this QR Code by the way for a froggy surprise for those of you who have been playing the Frog crypto zoo pass based ZK based game uh this will give you access to something special but thank you all for coming to this talk and we'll take questions now thank you thank you gub sheep we do have a few minutes for questions I think it's going to come up on the screen if not I can read them um can you elaborate more on The cryptographic Primitives you used got into a bit curious if it's lates to achieve the fhe yeah so one thing that that's actually been really interesting about exploring this whole fhe world is that a lot of our old friends from ZK come up again so for example one of the operations that folks might be familiar with that we have to optimize a lot during you know ZK programming is fast fora transforms and various kinds of polinomial operations these things also come up in various FHA schemes and we suspect that maybe could be accelerated even with similar methods um fhe schemes also rely on some cryptography we don't see as much in ZK such as lates um and uh we might have different strategies for approaching those but this is very much an open kind of question I don't think that what we're using right now for uh necessarily Phantom Zone or frog Zone today is going to be what we use in perpetuity um but yeah there's a lot of kind of these early exploration directions awesome looks like some folks are curious what is the most powerful use case you've imagined with this with this Tech stack yeah so I mean one one exercise you can kind of run is like what if you take the most ridiculous technology that exists today and just mash it all together um I like to think about this idea of a cryptomed which is what I think of as cryptography's equivalent of AGI so imagine that you had perfect obfuscation it was running on a blockchain that had enormous data availability guarantees and band with um what you would get is basically like a truly self- Sovereign program that's made out of math that's can never be taken down is always executing properly you can never open up the program to inspect its internal State except as it is allowed to run if you add in things like Quantum one shot signatures that program might have things that can only be executed once so it really feels like a physical program and then you might think what happens if you put an AG what if you run an AGI inside of that well now you have this essentially autonomous being made of pure information that has first class citizenship with reality in the same way that you or I do or any you know living thinking brain so I don't know the speculation here can get pretty crazy love it um looks like people are curious about code repos about Library usage yeah if you go to github.com zerx parkrogers and we'll get you set up awesome another round of applause