[ /random/p2p-games ]

I came across this thread on reddit in which atoms118 asked the following question:


Decentralized computing / gaming?

Hello; I've recently become interested with the idea of decentralized virtual worlds, or in other words, video games. The idea is that, assuming there's no RNG involved, you have inputs (actual client input) and outputs (a specific set of important values, for example the positions of players, but NOT things that are purely graphical or have no effect over other people's gameplay, of course), so you should be able to actually calculate the state of the game (given the previous state).

Of course, there's a problem here; if you're working with something like an MMO, all that client input is going to use a lot of computing resources (bandwidth, CPU, memory), so just keeping track of everything is obviously not an option. We need a way for the network to reach a consensus on the current state of the game; for example, maybe you only keep client input from the last 3 hours, and input older than that is dropped, and instead a cached version of the world as it was 3 hours ago is used.

I can't imagine that I'm the first person to think of this; I'm sure somebody else has already made some attempts, and possibly, some libraries that could help achieve it. If anybody could help me find some such attempts or libraries that would be great!

Thank you for your time.


As it happens, I have a very deep interest in these topics myself, and I've been studying both the history of the field and its unsolved problems for some time. The competitive nature of games makes them an excellent way of modeling how people resolve conflict, hence the widespread adoption of game-theoretic frameworks in politics and economics.

A common solution when two parties cannot reach an agreement is to depend on a third party as a mediator, but mediators are not necessarily impartial, and in effect this can make the game even more complicated. Multiparty computation is a sub-field of cryptography which explores (among other things) methods through which multiple parties can reach agreement on a contested issue without having to rely on a trusted mediator.

As I see it, the techniques established within this field may offer methods through which we can organize more effectively without vesting power in positions which tend to corrupt those who hold them. Playing actual games with these types of algorithms is a nice way to experiment with different group dynamics in a low-stakes environment.

Structure

Though I've found a lot of resources about games and multiparty computation, I haven't found any comprehensive explorations of how all the components can fit together.

I'm sorry if this article comes off as too verbose. I've tried to avoid exploring any particular topic too deeply. If I get carried away, it's because I find these subjects very interesting.

I'll start with a little bit about myself, some useful definitions, and then start into some of the mechanics for building simple games on top of cryptographic protocols. That's followed by some worthwhile criticisms of decentralization as an ideology, and an exploration of some of the technical aspects beyond cryptography. Finally, some notes on game design in general, and some libraries which you might consider trying if you want to actually build a peer to peer game after understanding more of the principles.

My background

I grew up playing games. I remember watching my two older brothers play on our family's Atari 2600 from a very young age, and then playing games like Final Fantasy on our NES as I got slightly older.

As a teenager, some friends introduced me to Dungeons and Dragons which used themes and mechanics I recognized from years of console-based RPGs. From there I ended up pirating a large number of game manuals for other tabletop games, most of which I read but never played. I picked up a lot of what I know about statistics at this time, since such games are largely driven by probabilities. As a voracious reader, I liked the storytelling aspects of the games, but as a moody teen I disliked that they tended to elect a single player as an authoritative referee.

Years later, in 2011 when the events of the Arab spring were taking place, I started thinking a lot about peer-to-peer technologies. It seemed absurd to me that the majority of a crowd of people could have cell-phones (computers with radio functionality), and yet be unable to communicate with each other because someone in a distant location decided to disable their network infrastructure.

I looked into the concepts and current status of mesh networking technologies. The best option I knew of at the time was BATMAN-adv, but the communities that were using it admittedly relied heavily on trust. Mesh network nodes that relayed traffic could snoop on or modify anything that passed through them. Additionally, IP addresses within the network were assigned using a central registry, and relied on the honor system. Though that approach tends to work in the communities that adopt BATMAN, it wasn't a solution to what I saw as the problem.

In 2013 (shortly after the Snowden revelations) I learned about cjdns, which implements an encrypted IPv6 mesh network. Users assign their own IP addresses which are the product of a cryptographic hash of a cryptographic keypair. The system encrypts all traffic, routes around malicious or faulty nodes, and does not require any central authority or registry to function. I ended up writing documentation for the project and helped to organize community effors for a few years, learning a lot about privacy, network security, and cryptography along the way.

In 2015 I attended Battlemesh v8 in Maribor, Slovenia, where I helped represent the cjdns community. I traveled across Europe for a few weeks along with some of the developers from Protocol Labs, and later spent some time with Dominic Tarr who had already begun developing Secure Scuttlebutt.

Later in the year I moved from Canada to Paris, France, to work on CryptPad, an open-source suite of encrypted real-time collaborative tools. I'm still in Paris, and now I lead the project. I'm happy to say that the team recently won the Next Generation Internet award for Privacy and Trust-Enhanced technlogies for our work in developing and deploying a usable cryptosystem to a wide audience of users. We authored a peer-reviewed paper about its architecture, a late draft of which can be found here.

Until recently I hadn't worked explicitly on matching up my interests in games and cryptography, but doing so has afforded me an excellent excuse to learn about ciphers and cryptosystems for which I'd otherwise have no use. I've been meaning to write something about the topic for a while, and seeing that others were interested in it as well was sufficient motivation for me to start writing.

Some definitions

The properties of modern cryptography are defined mathematically, so when we discuss attributes of cryptographic methods and systems, it's important to understand their precise definitions in that context. The notions of fairness and trust are especially relevant.

You can find a definition of fairness in Hiroyuki Iida's paper On games and fairness.

...we conjecture that the game-theoretic value of a sophisticated two player game is a draw. To discuss the game-theoretic value the concept of fairness in a typical two player game is studied. Fairness comes from the equal or nearly equal winning ratio for White and Black. It implies that for the omniscient players the outcome of a game is a draw, if the game is fair.

For trust, you may refer to Ed Gerck's "Trust as Qualified Reliance on Information".

“trust is an open-loop control process of an entity’s response on matters of X”

or

“trust is to rely upon actions at a distance.”

On randomness

atoms118 stated in their question that they assume there's no random number generator. It's not a well-known fact that there are ways of achieving fair random numbers among members of a group who do not trust each other.

Commitment schemes are a general classification of protocols that allow for distant actors to simulate simultaneous action by committing to a value (via a hash function, authenticated symmetric encryption, or some other method), and revealing that value only once all other concerned parties have committed as well. Secure coin flipping can be acheived by committing to a value (heads or tails, true or false), and then XORing the revealed results together. The technique can be generalized for any number of participants, and any number of bits.

Interestingly, randomness in this manner achieves fair outcomes without relying on trust, since even a single honest participant in the protocol can ensure that the outcome is unpredictable even if every other participant colludes. Unfortunately, it's an interactive protocol, meaning that participants must remain online for as long as it takes to compute the shared outcome, or the results of the group computation must be delayed until all participants have completed both steps of the protocol.

Execution of such a protocol for every random number obviously can't scale to support the number of players you'd expect in an MMO, but there are tricks that can improve its efficiency. If you're playing with trusted friends against another team, a single member of your team can contribute a random number for your group for a particular computation. Optimizations based on identification of trust are very common in multiparty computation, as the protocols otherwise tend towards being either too expensive to execute or too fragile in the context of network interruptions.

Another trick is to commit not only to random numbers, but to the set of computations which you intend to perform. Parties can arrive at a fair random number, and seed a pseudo-random function with it, using as many bits of random data as are necessary to complete their computation. As long as the methods are deterministic, their results can be independently verified, making cheating detectable.

Like any cryptosystem, provably-fair schemes need to fit together just right in order to accomplish their stated goals. A scheme is not provably fair just because it uses a commitment protocol, as demonstrated by the MysteryBrand scam analyzed by Rafael R Pereira.

How you use fair randomness will depend very much on the type of game you are designing, but there's a lot of literature on the subject. If you pair fair randomness with procedural generation in its many forms, you'll find that you can extend the basic principle to great effect.

On decentralization

Before I get into other important aspects of decentralized/cryptographic game design, I think it's worthwhile to question the notion of decentralization a bit. I could rant about the matter in depth, but others already have, and have likely done a better job of it than I could given that it's not the primary purpose of this article. In particular I'd recommend reading Nathan Schneider's Decentralization: An Incomplete Ideology (which at the time of this article's writing is still considered a draft), and watching Sarah Friend's 2018 Radical Networks presentation Decentralization and its Discontents (Trigger Warning: youtube).

So, assuming you've read and watched those, I'll go ahead and ask:

What do you want to accomplish by decentralizing gaming?

Please don't assume that there is an obvious value in doing so, or that there's one obvious way in which you'd do it, there isn't. There are a multitude of different strategies for the design of decentralized systems, each with different possible motivations, ideologies, efficiency tradeoffs, and likely outcomes.

If you are designing a decentralized system, I think you ought to be able to describe in very clear terms what you're decentralizing. In other words, what is your goal? Under what conditions would you consider your system a success? Keep in mind, I ask this as someone who believes in the value of decentralization, but in a carefully qualified manner.

For example, if you were to design a cryptographic implementation of the game of battleship that could be played by two players, then you could implement that game to be played over bluetooth or some other medium implementing a local network. One potential use-case would be that of a family going on a long vacation, in which some adult wanted their children to remain occupied for the duration of a drive or flight. Such a game could be played on a smartphone or tablet, and thus wouldn't require carrying around a physical implementation of the game. The children could play it quietly so as not to bother other passengers who might be sleeping, and they wouldn't have to face each other. Importantly, since the game would ensure that they weren't cheating by changing the location of their ships mid-game, there might be fewer arguments between the children.

On the other hand, you could design the game in such a way that it required global consensus by running it on top of the Ethereum Blockchain. Such an implementation would indeed be decentralized, but it would also require an internet connection, an enormous amount of electricity (certainly compared to that of a bluetooth implementation), and every game would require that you spend cryptocurrency to play (unless you played via a test network). The qualities of a blockchain game may be suitable if you want to facillitate gambling, but that's not something I find personally appealing.

Delivering messages

So far I've talked about players participating in a game, or members of a group participating in a protocol. Either framing of a scheme ignores the mechanics of how those participating in a system actually communicate. A game could be built on a number of different strategies, but each has properties for which a game would need to account.

The three most common architectures that I would consider are distributed hash tables, mesh networks, and gossip protocols.

Distributed hash tables (DHTs) have many applications, though they've been most widely adopted for the purpose of distributing static content via torrents. When you download information from a DHT, you access components of the data from anyone else who already has it. As you gather more of it, you're able to share more of it with others. As such, DHTs are wildly effective for replicating data which many people want, since popular data ends up with many sources from which it can be downloaded. You may want to use a DHT for the purpose of storing and distributing game assets, though it may not be especially suitable for passing messages. Notable protocols or projects using DHTs include IPFS, DAT, and GitTorrent.

On the other hand, a mesh network deals with routing messages between nodes, and not with storing information. Ideally, it chooses paths through a complex topology of connections on the basis of their overall speed, throughput, reliability, or cost. A meshnet is a good option for the fast delivery of messages in a p2p context, but a mesh will generally perform suboptimally compared to a centrally managed network.

The two most interesting mesh networking protocols that I'm aware of are cjdns, which I already mentioned, and Yggdrasil, which is being developed by a number of people who I know through the cjdns community. I mention these two protocols in particular because of their ability to function as an overlay network, since you'll probably assume the user has network access already, and you just want to facillitate communication that's relevant to the game.

Finally, gossip protocols are an excellent option when you care that data becomes available eventually. Borrowing the term from sociology, gossip networks store information, and opportunistically spread it to people who might care about it. Unlike torrents which are concerned with distributing static datasets, gossip protocols are excellent for distributing updates about subjects or topics. Secure Scuttlebutt uses a gossip protocol to distribute information about mutual friends. Though participants in a gossip network can certainly use the architecture to synchronize global state, it's particularly effective for groups that want to synchronize mutually interesting information such as in a social group.

There is not always a clear line between these different architectures. Older versions of cjdns distributed routing information using a dynamic DHT. Most people who use secure scuttlebutt do have consistent access to the internet, so in practice its routing protocol is not that different from a meshnet.

It's important to understand that in every case, there are aspects of the network topology which are somewhat centralized. SSB relies on pubs to facillitate the exchange of information between friends who don't have a public IP address. Cjdns and Yggdrasil can similarly route over the existing internet, and in such cases also require a node with a public IP address to facillitate the exchange. BitTorrent relies upon websites or other services distributing torrent files, or at the very least upon centralized introducers to make sure that the disparate nodes of the DHT can find each other initially, after which they can connect in a truly p2p fashion.

WebRTC implements real-time communication between clients in the context of the web, but assumes that an introducer will help them find each other. Successful services which use WebRTC tend to provide code for falling back to client-server models for relaying messages between unreachable clients when they are behind a restrictive firewall or NAT.

It's unfortunately true that if you want to build a p2p game, you're most likely going to have to think hard about the problem of connectivity between players, and it's at this point that you'll probably have to compromise with regards to how decentralized you want to be.

Tracking game state

Assuming you've solved the problems related to players in a game being able to reach each other, you will have to think about how they track state.

A simple solution is to play very simple games. If the nature of your game is episodic, which is to say that none of the events from one session need to be consistent with those of another, then you won't have trouble scaling. Players of Tic-Tac-Toe don't need to remember the details of every game they've played, though they may want to keep track of victories between particular players. You can optimize here by considering who actually cares about what information.

In a more complex case, there may be more state to track, but there will still be a lot of information which need not be tracked. In World of Warcraft, groups of players enter dungeons, at which point they stop tracking the rest of the game world. Likewise, the rest of the game world won't care about what happens in the dungeon, except that one-time-use items expended in the dungeon should not be reusable at a later time, and that loot won by completing the dungeon should be eligible for reuse at a later time. The rest of the details can be discarded.

The category of techniques related to identifying which players care about which information and selectively distributing it is referred to as interest management in this 2003 paper about scalable MMOGs.

The Kappa architecture is an increasingly common pattern, in which events are streamed to clients nodes that process the events. The global state at any time is computable by replaying modifications to the starting state, in order. These events can be stored in append-only logs, however, the natural side-effect of this design choice is that the set of data only ever gets larger. This methodology is employed within CryptPad and SSB. The general principle of aggregating state from ordered events is also the primary mechanism behind blockchains.

In CryptPad, it would be untenable if users required the entire history of the document in order to view its latest state. We mitigate the issue by using periodic checkpoints. Every so many messages (each of which is an encrypted patch) one of the editors creates a checkpoint, a special kind of patch which removes and reinserts the content of the entire document. Only the two latest checkpoints are required to accurately reconstruct the most recent state of the document, though this is clearly less efficient than a centralized authority providing a checkpoint of the document on-demand.

For a different way to accomplish the same goal, you may see Aether, a p2p project which implements a reddit-like forum in which content older than 6 months is discarded.

Game design

Given that a lot of p2p systems work very well with lots of participants, but suboptimally with only a few, adoption is particularly important. While it may be tempting to get caught up in the mechanics of your system's cryptography or data replication layer, it's important not to lose sight of what makes people actually want to play it. Mark Rosewater, the head designer for Magic: the Gathering wrote the article Ten things every game needs, which I'd recommend reading.

While I don't exactly consider it to be a game, I'd be remiss if I didn't mention Cryptokitties, which has arguably been one of, if not the most successful application of the Ethereum blockchain. Since the "game" consists of only two mechanics (ownership of your cryptokitty and breeding new cryptokitties), it seems relatively obvious that the appeal has something to do with the cuteness of the digital property. Game developer Jenny Jiao Hsia's presentation Put a face on it: The aesthetics of cuteness in game design is worth watching for insight into how you might increase the appeal of an otherwise very technical game.

A few considerations

In trying to balance between the playability of your system and its technical implementation, you may want to ask yourself the following questions:

  • How many players should be able to play your game at a time?
  • How quickly must the result of a computation be returned to the person who requested it?
  • How many players are required to know the result of any given computation?
  • What global state, if any, is required?
  • In cases where global state is required, how quickly must the majority of the players come to consensus on that state?
  • Is the game structured in such a way that some players may/must trust each other?
  • Is some level of trust between players acceptable?
  • Can collusion between players be made into a game mechanic?
  • Under what circumstances will players play the game? Over the internet? Via a local network? Over a very long time such as via a sneakernet?
  • Must one player's action wait for the outcome of anothers?
  • Is the game turn-based, or real-time?
  • In a turn-based game, how would you handle it if a player stops playing on their turn?

The more flexibility you can afford when answering one question, the more room you'll have to optimize for other aspects of the game. Getting the pieces of the puzzle to fit together in a way that people will want to use is likely to be a difficult process. If you're using cryptography or implementing multi-stage protocols that call out over a network, the game is most likely going to be significantly slower than a similar game implemented using beefy servers, especially if some of the players are using mobile or otherwise low-powered devices

One way around all the problems that arise when designing such a system is to simply admit to yourself and others if you're not building it because you want it to be adopted, but because you want to learn. Personally I think it's usually worthwhile to explore systems development for personal education, but it's best to be honest with yourself and others if that's the case. I have no reason to believe that World of Warcraft or Fortnite will be displaced by a p2p alternative any time soon, but that's fine by me as long as I enjoy the design process.

Alternative paradigms

Though it's certainly interesting to eliminate the need for an authority from games which traditionally require one, there are many games which are by their nature well suited towards adaptation for a p2p context. Correspondence chess has been played for centuries. Many other games have been adapted to be played by mail as well. Some of these games could certainly be modified such that they require less trust, but the fact that people have played them remotely without such techniques attests to the validity of their approaches.

In the realm of tabletop roleplaying games, there are a number of rulesets from which a designer might draw inspiration.

One particular game that I find very interesting, but which might not be easy to automate, is Ben Robbins' Microscope. Which is played entirely without an authority. Players take turns on which they make choices which are necessarily limited in scope, but for which they otherwise have complete control. The goal is to fill in the history of a story by defining and elaborating on an ordered progression of fictional historical periods.

This reddit thread mentions many games that are played without relying on a game-master.

You might also consider somewhat traditional games that use mechanics other than randomness. Amber diceless is played using a game-master and multiple players. Players begin the game with an equal number of points, and bid in an all-pay auction for supremacy in a number of attributes. In situations where a particular attribute is required, the player with the highest value is guaranteed to win that confrontation. The game is played by forming alliances and maneuvering other players into positions where the deciding attribute is in your character's favour.

You might consider implementing other types of auctions, such as a unique bid, dollar, or penny auction. You could implement an entirely public auction with an automated process, relying on commitment protocols if necessary, but there are actually algorithms for fairly and securely implementing sealed-bid auctions. Interestingly enough, these algorithms have been deployed in actual systems for the purpose of negotiating the price of sugar-beet crops. Supposing you wanted to check at any given time which player had a greater value, you might use one of the protocols proposed as a solution to Yao's Millionaires problem.

Libraries

When it comes to basic block and stream ciphers that you'd use for message encryption, most modern languages offer quality implementations. More exotic cryptographic primitives are typically harder to find in the language of your choice. Beyond that, if your game requires a combination of multiple primitives, finding correct and secure implementations that work together well will pose an additional challenge.

SCAPI is written in Java, and offers a composable suite of primitives along with some tools to facillitate the design of multiparty protocols over a network. It's written by highly qualified cryptographers, and it should run on all sorts of architectures due to being written in Java.

I've been working on a similar framework of primitives and helpers in Javascript, called cryptomancy though it's just a hobby project. It's composed of a variety of modules, each implementing some class of primitives, like this cryptographic accumulator, this commutative cipher, or these procedures which consume various flavours of entropy.

Unlike the authors of SCAPI, I'm rather unqualified to produce secure cryptographic primitives. I wouldn't recommend using this suite for anything that requires any semblance of real security, but I've tried to make the implementations easy to understand, so it might serve as a decent set of examples to understand some of the principles of multiparty computation.

My primary goals in writing cryptomancy are to learn about the ciphers and protocols involved in multiparty computation, to provide reasons for more qualified cryptographers to implement fast and secure cryptographic libraries in Javascript, and to drive adoption of these schemes for the broader public by putting them in the browser where they're most widely available.

You probably have your own opinions about programming languages, and I won't try to change them, but as far as I know the options here are fairly limited.

Conclusion

I've tried to assemble an interdisciplinary summary of a very complex topic, and it ended up being much longer than I'd initially hoped. Cryptography as a field is most commonly associated with privacy or security, but it's just as well suited to guaranteeing fairness. At the very least I hope that I've helped to raise awareness about its more obscure applications.

Most cryptographic tools are famously difficult to use, so I think the industry could certainly benefit from a greater diversty of attempts to make it cute or fun. Insight could come from anywhere, and so I hope that anyone working on design issues in this space does so in the open where the public can benefit from their effort.

As I said at the start, my interest in multiparty computation is closely related to my political views, and I hope that others consider the implications of the principles of game design in more general terms. It's hard to avoid conflict, but perhaps our differing motivations can be navigated without resorting to coercion. Perhaps we can build systems that actually motivate more people to take an interest in their outcomes, and participate in deciding how to proceed.

-- ansuz
2019-01-20