Policing Online Games: Digital Currency

One of the great myths in the game world is that there's nothing that can be done about cheating in networked games. Everyone assumes that because the player controls the hardware, the player can edit the code to add convenient "features". Hidden areas of a maze can become visible and average swords can gain ten hit points with a quick click.

I became intrigued with this area and decided to write Policing Online Games after hearing the same claim again and again. While everyone is right about the danger of a smart gamer with a hex editor, they're forgetting that technology and mathematics can provide efficient solutions that stop cheaters from even beginning. Enforcing rules, limiting cheaters, and keeping everyone playing fairly is still not simple, but it is far from impossible.

Some of the simplest solutions like Punkbusters do a good job of ensuring that the laziest cheaters can't load common mods from the Internet and dominate the field. Their software checks and rechecks each part of the code to make sure that people are running correct versions. Some of the better designed game programs now run these checks themselves to ensure that nothing goes wrong.

Even better solutions come from the world of cryptography where researchers have spent decades exploring clever ways to use mathematics to smooth over relationships between people who don't trust each other. While everyone is familar with encryption algorithms that scramble communications, many are unfamilar with some of the neater mechanisms for sharing control, enforcing rules and limiting power.

Some of the first and most exciting papers in the area tackled playing what the researchers called "Mental Poker", a term the authors used to describe poker played over a telephone wire. The Internet didn't exist in its present form in 1978 yet so they just considered how to deal cards over a phone line.

These mental poker algorithms let people shuffle and deal cards to each other across the Internet without trusting some server . The basic P2P requires more sophisticated mathematics than the standard poker web sites where the server deals the cards, but it is much more trustworthy. The lack of the server lets ad hoc games develop without any of the infrastructure required.

Better algorithms can shuffle more than cards. One algorithm can let someone on one side of the Internet, call her Alice, present someone on the other side, call him Bob, with a set of doors, boxes or containers. The magic of the equations lets Bob open one and only one box without letting Alice know what the box may be. This is a perfect tool for many of the distributed maze games.

All of the best solutions can help game companies by removing the need for a central server. Some of the massively multiplayer games fight cheating by making all decisions with central servers. This can be quite effective, but it requires a hefty hardware budget that must be paid by someone. Better mathematics can be much cheaper.

I wrote the book to explore what can and can't be done with some of the best algorithms in the area. It's a bit of evangalism that I hope will spur some game designers to implement the algorithms to stop cheating. It may also encourage some cryptographers to solve more of the problems faced by game designers. There's still much work to be done.

About the Excerpt

This chapter on creating digital cash and cash-like elements comes from deep in the book. It's Chapter 13. This means many of the basic details about encryption, digital signatures, and blind digital signatures have been introduced already. Still, many of the concepts can be understood with a bit of faith. Most of the terms are self-explanatory, but if you need more help, you can turn to Google or buy the book.

Most of the chapters in the book begin with a hypothetical story of the problem faced by some game company and then the chapter describes how to fix it. In this case, Never Board is trying to build a trustworthy bank for a board game like Monopoly. As anyone who's played the dead tree edition of the game knows, you can't always trust one person to be the banker. The digital cash algorithms described here can also be used in any world that needs to stop counterfeiting. An online world might want to limit the number of +30 uberswords for the same reason that a government might want to stop counterfeiting.

For more information about Policing Online Games, turn to the book's website http://www.wayner.org/books/pog/.

Chapter 13: Cash

The design team at Never Board Games knew they were in for trouble. They wanted to create virtual versions of classic board games, but they wanted to avoid having some trusted central server. Ideally, people would be able to link up with several of their friends without relying on Never Board's server farm to referee every game. This would keep Never Board's costs to a minimum and save them the trouble of maintaining a reliable server farm for 24 hours a day.

The problem was that all the founders were old schemers and corner-cutters. When they were kids, they were the kind who ran the bank in games like Monopoly just for the chance to ``make loans" when no one was watching. They faced a dilemma. On the one hand, they wanted to make a board game with a trustworthy bank; on the other hand, they didn't want to run it for everyone. The industry long insisted that companies must ``eat their own dog food." They needed to build a trustworthy bank that even they couldn't break.

Digital currency is one of the trickier challenges for any game designer, if only because copying digital files is so easy. To a large extent, the problem is not much different from ensuring that players don't create or duplicate any suit of armor, mace, spell, book, or item of value in the game. Rampant counterfeiting of any object leads to inflation and the gradual erosion of value.

Cash, however, has some extra features that make it distinct from generic objects:

Privacy. Many games and parts of real life depend on financial privacy. Knowing the size of the bankroll of another player changes the dynamic of many games. While this secrecy is not an explicit feature of cash, it is often an important component.

Divisibility. There should be some reasonable way to make change. Paper bills and coins can't be physically split, but merchants often keep a supply of cash on hand to settle any transaction. The ideal digital coin can be divided into smaller parts or spent in fractional amounts.

Peer-to-Peer. In many smaller games, financial privacy depends upon transactions that don't require some central authority for processing. If one person can give money to another without informing the bank, then the bank won't know what's happening.

These features of regular cash are just as desirable in the virtual game world as in the real world. Unfortunately, they're often not as easy to duplicate without some complicated mathematics. In many cases, the features are available in a variety of different levels of sophistication, and the game designer can weigh the value of the feature against the cost of the complexity.

Serial Numbers and Signatures

Paper currency comes with two security features that can be used easily in the digital realm. Every bill comes with a unique serial number that can identify duplicates. This serial number is blessed by either an actual signature or a hard-to-duplicate production mechanism that effectively ensures that no one else could produce the bill. The two features combine to ensure that there will be a stable number of notes from a trusted source.

Basic digital bank notes consist of some data structure defining a bill and a digital signature from the bank blessing it. This data structure may contain many things, including:

Unique Serial Number. Only one copy of each bill should exist. If two appear, someone has been counterfeiting. Required.

Denomination. How much is the bill worth? Required.

Rightful holder. Who owns the bill? This can protect the owner's rights if the bank tries to disavow it. The rightful owner can treat it as proof of a contract between the bank and the owner. Optional.

Interest Rate. In some inflationary environments, a bank might choose to pay interest on the outstanding notes. This makes them more like Treasury Bills or corporate bonds and less like ordinary cash. Optional.

Creation Date. This can work with the interest rate to establish the value of the bill. A note paying 7% simple interest would be worth 1.07 times as much one year after the creation date.

Expiration Date. It is often a good practical idea to let notes expire after some time. Players with outstanding notes can turn them in for new ones. The cruft and bit rot can be swept away. This reduces the overhead for the bank because there's no need to keep track of which old bills are unspent. Optional.

Coupons. Marketing experts will surely find a way to make these digital notes be worth more at some places than others. Instead of offering a coupon for 10% off at some store, the bank might decree that its notes are worth 10% more at some store, but only through Saturday. This may be confusing, but there's no reason except simplicity why cash needs to be worth the same amount everywhere. Well, fairness is one reason. Amazon inadvertantly angered customers by offering random discounts to customers to find the "right" price. Optional.

Most implementations will use only the required fields for the data structure at the heart of the bill. The extra enhancements may only help stranger games. The important thing to realize is that the notes don't have to be limited. Game designers can add any functionality they need if they can spare the overhead.

Some digital cash systems use a different pair of public keys for each denomination. The $10 bills, for instance, would be signed with a different digital key than the $5 notes. Anyone who needed to trust a piece of currency would test it with the right key. If this is done, there's no need to include the denomination in the data structure of the bill, although some schemes use both.

Transactions

One of the simplest ways to create a relatively safe and secure world for digital cash is to audit every transaction. If every transfer must be approved, then duplications will be detected as soon as someone tries to spend one bill twice. The bank or exchange keeps track of who owns which bill. Someone transfers a note by telling the bank to change the ownership. If you're going to place all authority in one entity, there's no real need to create individual notes with digital signatures. A bank can simply keep a ledger or database with the accounts of all players.

Actually, minting notes by creating unique serial numbers and signing them may not offer the simplicity of a ledger, but it can offer more accountability. The banker can always change the values in the ledger for good or for bad and no one can challenge them.

If the individual notes contain the name of the rightful owner along with the denomination and the serial number, the banker can't delete money from someone's account. If a person keeps a copy of the bills, the bank can be held accountable.