This is an excerpt from Peter Wayner's recently published book, Policing Online Games. This article examines the concept of digital cash and cash-like elements in games, and the security elements that should go into a digital cash model to defeat cheaters.
October 10, 2003
Author: by Peter Wayner
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.
Peer-to-Peer
In some environments, it doesn't make sense to place all the power and responsibility on a central server. Peer-to-peer networks can also trade bills, although they must take some extra precautions to prevent counterfeiting. Anyone can hand over a bag of bits to another player, but there's no simple way to prevent them from counterfeiting by handing over the same bits to other people.
The best approaches can only reduce the load on the central bank because there's no way to eliminate it. All of the notes must run through a central location to check for counterfeiting, and the security of the system is directly proportional to the time between checks. Banks may check only a fraction of the bills chosen at random, but they can't eliminate the check altogether.
A transaction in this scheme will look something like this:
Each bill consists of a data structure specifying the serial number (num) and the denomination (amount): B(num,amount).
Each bill carries with it a chain of digital signatures of each owner, beginning with the bank itself. If Sbank(B(num,amount)) represents the signature of the bank at the bill's birth, then this chain might look something like this:
This means that the bank created the note, gave it to Bob who gave it to Alice who is now the rightful owner.
The player spending the bill will add a new signature to the chain, giving up control of the bill and specifying the new owner. This is like endorsing a check.
The new owner accepts the bill and checks every digital signature in the chain. If they're valid, then the new owner closes the transaction.
The new owner checks for counterfeits by comparing the new bill's serial number will all the others owned by the player. This won't detect all counterfeits, but it will find some.
The notes grow each time they're spent in this scheme forming a chain of custody for the cash. Counterfeiting, if it happens, can be identified by looking at the chain of custody. If two bills with the same serial number appear, the counterfeiter can be identified by walking up the chain of custody to find the person who spent it twice.
The role of the bank depends upon the nature of the game. In the most extreme case, there's no need to look for counterfeiting because the game comes to a grand conclusion when everyone turns in their notes and their pieces, perhaps to claim a share of a purse. If there's one final judgement, then everyone can search for cheating at that point. There's no need for auditing along the way.
Often, waiting for the end of the game can be a mistake. Some games come with no ending. Others could be wrecked by some jerk counterfeiting like crazy.
Auditing can take any number of forms. Complete audits every n turns would require everyone to turn in their bills and receive new ones. This also saves overhead because the new replacements would not have a potentially long chain of digital signatures to be checked. The auditing will also clean house and add efficiency.
Another strategy is to recall bills selectively. Every so often, the bank will ask all bills with a serial number ending in, say, a 3 to be turned in. If this value is chosen at random, the cheaters won't be able to time their counterfeiting for maximal effect.
Making Change
Digital cash systems in peer-to-peer environments work more efficiently if the peers can split notes and make change. Requiring people to head to the bank to make change may help auditing, but it may be too onerous in any peer-to-peer environment.
Another solution lets users split the bills themselves. The simplest approach is to allow users to insert a message into the chain of digital signatures that says, in effect, "This bill has been split into n pieces and this is piece number i." Everyone who accepts the bill afterwards will treat it as being worth only 1/nth of the original denomination.
If n=10, then adding digits to the serial number is an efficient solution. A player with bill number 1045 would split into ten parts by creating new serial numbers 10450,10451,¼,10459.
Removing the Central Bank
There's no reason why there should be only one central bank for each game. While it may be efficient in some cases, it can be a bottleneck or an imposition on others. Some games may want to allow multiple banks or even allow each player to run their own bank.
In the most extreme case, each player also acts as their own bank. Instead of withdrawing cash from a central location, they simply mint it themselves. This temptation is not as dangerous as it sounds because players can place limits on each other.
For instance, if a board game begins by giving each player $100, then each player could begin with the right to issue 100 notes with serial numbers between 0 and 99. If someone notices a bill with a serial number outside of this range, then there's evidence of counterfeiting or at least inflationary spending.
Multiple banks do not change the transaction process. Each player still checks the validity of the chain of signatures and looks for potential duplicate serial numbers. In some sense, the issuer's name or number is just another part of the serial number for the bill.
Multiple Audits
Separating the auditors from the company is one tradition from the business world that can work here. There's no reason why the same person needs to maintain the bank and audit the transactions.
One simple solution is to allow any player to recall bills at any time. Well, subject to some rational limit. One player may ask all players to turn in a particular subset of bills at one time. Demanding all that end with the serial number `5' would pull in one tenth of the notes and uncover any cheating from that set.
The auditor can either return the notes to circulation or replace them with new notes drawn on a new bank. Having multiple players issue new notes will make things more confusing, but reduce the ability for individual players to create havoc. If another player may recall notes at any time, cheating can be discovered faster.
The downside of these multiple audits can be confusion. What happens to the status of a note if it isn't returned? It will not be valid, but what if this happened because of a software glitch or a communications failure? Is there a failsafe process? Adding all of the layers of audits discourages some cheating but certainly increases the complexity of the game.
Conclusion
Never Board Games created their own toolkit that lets one player's computer act as the bank for the system. The bank issues all of the notes at the beginning of the game and then lets players swap them as they need to. Auditing is only done by each player after a transaction and at the end of the game. Since many games created by Never Board end up with one person owning all the money and property, this is effectively the same thing.
This scheme also protects the privacy of players. If the bank does not scrutinize every transaction, then the bank can't know how much each person holds. People are free to cut side deals without telling the rest of the board how much cash they are trading.
Digital cash systems are just more specialized versions of the process for controlling the proliferation of objects. Every digital game must stop people from duplicating desirable objects, and cash is often the most desirable object. There's no reason why other objects can't be defined with the same system if the rules of physics apply. It may not make sense to split apart a suit of armor, but there's no reason why a flagon of beer can't be split into n different parts.
The schemes in this chapter offer a rudimentary form of privacy that may not be ideal in all cases. While a distributed mechanism doesn't let any one player pay too much attention to another, all the transactions are essentially in the clear. If you can see all of the bills, you can know who did business with whom. This can be a problem because people can pick up the data as the bills circulate.
Lessons
Cash is just another object that shouldn't be duplicated.
The most important parts of a digital cash object are the serial number and the value.
Digital currency may also include other values in the data structure like the rightful owner, the interest rate paid on the note, and the expiration date.
Everyone in the game wants to prevent others from cheating by spending the same bill twice.
One solution is to run every transaction through a central bank. This may stop cheating by ordinary players immediately, but it places plenty of power in the central bank. Power can corrupt.
One way to spread authority is to require each person to sign a bill over when spending it. This creates a chain of digital signatures showing who owned the bill at what time.
If two bills appear with the same serial number, the counterfeiter can be identified by looking at this chain of custody.
Auditing can occur at random times by requiring players to turn in all bills with certain classes of serial numbers.
Players can create change by attaching another note explaining that the bill was split into n parts and this is the ith part.
For more information about the book, an FAQ, an ordering form, and an errata page, go to http://www.wayner.org/books/pog
Read more about:
FeaturesYou May Also Like
