Understanding Video Games text-book
The Digital Coin Model for Object Management in Multiplayer Online Games

Date posted: May 19, 2006
Updated: Oct 24, 2006

By Ken Griffith
Article footnotes inserted in []

I. INTRODUCTION

As massively multiplayer online games (MMOG’s) have grown in popularity and complexity over the past decade it has become increasingly difficult to create a game engine that is effectively bug-free with regard to object transfers inside the game. This has created a significant limitation on the advancement of online gaming practice because of the inherent danger of linking error-prone online game worlds to items of real world value such as money.

This paper proposes a novel software engineering model for MMOG’s that takes advantage of the processing power of player computers to distribute the heavy lifting away from the central database, while making it theoretically impossible for players to cheat.

The digital coin model takes advantage of cryptographic technologies and algorithms developed for real world digital cash. The concepts pioneered by financial cryptographers have unique applications for distributed multiplayer gaming environments.

Any MMOG can be viewed as a pyramid. The keystone (top) of the pyramid is the central database. One tier below is the game server layer. Depending on the size and popularity of the game there may be one, tens or hundreds of game servers located around the world that players log onto to play the game. Game servers may have their own local database in addition to the central database. The base of the pyramid is made up of the thousands, or hundreds of thousands of players and their home computers on which they run the game client software.

The chief difficulty for MMOG development is that the demands on the central game database increase exponentially with the number of players and the number of variables in the game world. Described as a ratio:

database_cost :: total_players * total_variables

Likewise, the likelihood for the activation of a bug with fatal economic implications is directly proportional to the number of players multiplied by total variables.

bug_activation_probability :: total_players * total_variables

Each player brings his own processor with him, often times more powerful than the game servers. If a fool-proof method could be devised to push as much computing as possible down to the client machine, while preventing them from cheating, then in theory, the complexity and size limits on MMOG’s can be increased. Effectively, this model trades the information intensive database for a slightly higher bandwidth requirement between the game server and client machines. The client machines can replace most of the central database.

The goal of the model described here is to simultaneously accomplish five objectives:

• Neutralize the economic harm of “dupe bugs” in a “convertible” MMOG
• Facilitate the error-free conservation of persistent objects.
• Push the majority of data processing down to the client machines.
• Prevent successful client cheating through the use of mathematical proofs and cryptographic methods
• Reduce the total processing load per player on the game servers and central database

II. THE DIGITAL COIN MODEL

For this model we will borrow from the digital coin models developed for various digital cash protocols.

A digital coin system farms data processing out to the client instead of the central database; but it uses cryptographic methods to detect and prevent cheating. The advantages of digital coins systems over centralized database systems are the fact that they more closely model the real-world economy where decisions are made by millions of individuals rather than one centralized “uber-mind”.

As we have pointed out above, MMOG networks have a tremendous amount of untapped processing power located at the client layer of the pyramid. Rather than having all game world information and transactions processed through the (relatively) tiny capstone database, or even host server layer, a digital coin system as proposed here will put the majority of the processing at the client level and use cryptographic methods to prevent cheating.

Developers have created numerous digital coin protocols for “digital cash”. [http://fiddle.visc.vt.edu/courses/ee4984/Projects1995/harltran.html]. Digital cash systems use mathematical constructs to represent and transmit values in a secure manner over an insecure network [J. Orlin Grabbe, The Mathematical Ideas Behind Digital Cash, http://www.aci.net/kalliste/dcintro.htm]. Several aspects of these models can be useful to MMOG’s [In particular the “Randomat” coin system by AGS Encryption Systems eliminates the use of a central database for coin validation. This has the potential to be extremely useful for MMOG’s using a digital coin model. URL: http://www.agsencryptions.com/randomat/index.htm], while others such as “anonymity” are irrelevant or counterproductive for this application. The purpose of this paper is to demonstrate the validity of a general digital coin model for MMOG’s rather than a specific coin algorithm.

Digital coins will be used to represent three kinds of objects in this scheme:

• Inventory objects (persistent and non-persistent)
• Character attributes (strength, intelligence, hit points, mana, energy, etc)
• Character & environmental affects (attacks, spells, etc)

A digital coin consists of four elements: the coin number, data, time-stamp, and digital signature. The digital signature will be a function of the particular digital coin algorithm chosen, so suffice it to say here that a digital signature must be non-repudiable.

Coin number – The coin number will be a random binary number generated each time a coin is made. The key space for the digital coin number should be large enough that the probability of a collision is one order of magnitude less than one in the total number of coins generated in the time period of the coin life. For example, if there are expected to be 10 million transactions with coins that persist for a year, then the coin-space should be large enough that the chance of a collision is less than 1/100,000,000.

Data – The data will include an object-class/type and values. The values will represent the attributes of the character, action or object.

Expiration-Date – The spent coins will be recorded in a spent-coin table. Only the expiration-date and the coin number will be recorded in this table. The database will purge expired coins on a daily basis to keep the database size and performance within reasonable bounds.

Digital Signature – The game server that creates a given coin will append a digital signature of the coin number, data, and expiration-date. A digital signature consists of a public key signature of the message digest such as SHA1 or MD5.

The Network Structure

The game network will consist of three levels as described above.

Database

The central database will keep track of spent object coins, as well as the positions of characters within the game world, and the server to which each character is connected.

Host Servers

Host servers will process the results of player actions on players attached to that server and update the central database and other game servers with relevant player actions, player positions and object coin spends. Host servers will also handle transactions of player attribute coins (hit points, etc) and keep a local spent coin database for attribute coins of players on that server.

Client Machines

The client machine will keep both object and attribute coins belonging to that particular player. Clients will be able to backup player inventory and attributes on a backup server, which will normally happen during logout, but can be done at certain times during the game. Backups protect against hard-drive crash on the client machine, not against death in the game. Backups provide no ability for the player to revert to an earlier “game state” because any spent coins are permanently unusable.

The Scheme

This model uses several implementations of the same digital coin scheme at different levels in order to minimize the amount of data actually stored in the central and game server databases. The idea is to use digital coins to make client machines keep track of and process their own data as much as possible, while preventing cheating. Effectively we want to turn the client machine into a personal database for each client. Instead of searching for client data in a database, the client actually delivers the data when it is needed.

Rather than pulling data from a database, the client pushes the data to the host server along with the transaction instruction. In theory this eliminates one half of the average transaction (the database query). The client software is written to provide the data when it is needed without being asked. Rather than maintaining a central database with a record for every variable for every player, we store the variable data on the client machine as a coin that has been digitally signed by the private key of the game server.

The effect of this model is to replace the majority of database search operations with cryptographic signature validations. This will greatly reduce the central database load per variable per player as well as simplifying the database schema and operations.

The scheme uses coins to represent several different types of objects and actions in the game including:

• Objects (conserved and non-conserved)
• Variable Character Attributes (hit points, mana, energy, etc)
• Fixed Character Attributes (speed, attack range, strength, intelligence, etc.)
• Affects (X damage points of type Y on character Z)
• Modifications (+/- X points of attribute Y for character Z)

The scheme described here consists of five basic functions: Mint, Transfer, Use, Affect & Effect. (Though certainly other arrangements could be used as well.)

The Mint Function

The Mint creates new coins according to certain rules. Conserved objects may only be created under very limited conditions (such as transfers), while non-conserved objects can be created by numerous regeneration events in the game. When an object is transferred, the old coin is “spent” by the Transfer function, and then the Transfer function will call the “mint” to create a new coin for the new recipient. The mint may use different signing keys for different types of coins, allowing key length to be determined by the value of the object the coin represents [A general rule of thumb for financial cryptography is that the cost of cracking the cipher that protects a given piece of data should be one order of magnitude greater than the maximum economic value of the data after three more iterations of Moore’s Law (processing costs falls by ½ every 18 month). Example, if a digital coin can represent something worth up to $100 today, then the cipher used to encrypt the coin should require at least 10 * $100 * 2^3 worth of resources to crack ($8,000). The simple form of the formula is Costcrack = 80 * $Max_Data_Value. This provides reasonable protection for up to four and a half years. This formula can be used in turn to determine the proper key length for the cipher. This method allows the discovery of the best compromise of security and processing cost.]. Each game server will have its own mint and unique signing keys. In this scheme the mere possession of an unspent coin is sufficient to prove ownership. Encryption is used to protect coins from theft by cheaters. This way the database doesn’t have to keep track of who owns what.

When creating a coin the mint will follow these steps:

1. Validate the rules for creating this coin.
2. Generate a random coin number in the “coinspace”.
3. Append the data values and expiration-date.
4. Create a digital signature of the coin_number, data, and expiration_date and append it to the coin.
5. Encrypt the new coin to either the session key or Public key of the new owner. (Symmetric key ciphers such as IDEA and BLOWFISH use less processing power than Public Key Ciphers such as RSA.)
6. Transmit the encrypted coin to the recipient.

Alternatively, the client machine may generate the entire coin except for the digital signature. The Mint merely validates the values before signing the coin. The goal is to push processing down to the client.

The Transfer Function

This function handles the exchange relationships between objects. When a character transfers or uses a coin the Transfer Function first checks the coin number for double-spending. If it passes, then the Transfer function determines the result of the “spend” based on the rules of exchange. After calculating the new values and recipient, Transfer will pass the values to the appropriate Mint Function for a new coin to be minted and transmitted to the recipient.

When an inventory object is passed from one character to another the data for the new coin is identical to the data on the old coin.

The Use Function

In many cases one type of object coin might be exchanged for a different type of coin or operation. This operation has cases where the original object is consumed, and other cases where it is not. For example, when using a perishable item, such as a “healing potion” the coin for the potion object would be “spent” in exchange for a certain number of hit points that would result in the generation of a new “hit point coin” for the character. The healing potion object is consumed with use. A set of scissors, on the other hand, is not consumed when used to cut something. Some “uses” of objects might generate an AFFECT coin toward another object or character.

The Affect Function

Certain events in the game will “affect” characters or objects. This can be hostile (attacks) or friendly (healing). Causes of affects would include characters in battle, spell castings and using certain items as well as environmental events like falling off of a ledge and striking the ground.

This scheme uses classic RPG rules to handle “affects” and their “effects” on a given target but breaks the calculation into as two transactions: the AFFECT and the EFFECT [“Affect” is an action. “Effect” is the result of an action].

The affect is generated as a “coin” by the client machine of the AFFECTER character, or the game server that controls a given NPC. The AFFECT COIN includes the following values:

• Coin Number (random)
• Affect Type (blunt, pierce, hot, cold, fast, slow, etc.)
• Affecter_ID (the unique identifier of the attacker)
• Affecter_Address (address of the attacker’s host)
• Target_ID (the identifier of the target)
• Target_Address (address of the target’s host)

The following method of generating “affect coins” pushes the work down to the client.

A. The client generates a random coin number and sends it to the host server as a request for a random seed.

B. The host produces a random seed number, cryptographically [Guru David Chaum discovered that some signatures have the property of being “commutative” with the blinding functions. http://www.cs.utk.edu/~ffowler/cns-html/append.html] blinds it [The reason for blinding the seed is to prevent cracked clients from discarding “bad” seeds, and only keeping the “good” ones], and sends it back to the client.

C. The client then applies the proper formula to the blinded random seed to generate an affect coin for the desired affect (attack, cast spell, whatever).

D. The client machine (or game server for an NPC) will submit the affect coin and its character attribute coin to its host game server.

E. The host server will randomly check a certain percentage of the coins to make sure that the client did not cheat. By only checking one in ten coins, the host server is statistically guaranteed to catch a cheating client within a certain number of rounds. This method reduces the processing resources for handling battles by roughly 90%.

The tested coins will be subjected to the following procedure:
1. Check the signature on the client’s attribute coin.
2. Check the attribute coin for double spend.
3. Compute the attack results based on the client’s attributes, the random seed, and the other effects.
4. Compare the correct results to the coin the client submitted.

F. After receiving (and in some cases testing) the coin the host game server will complete the following steps:

1. Check the affecter’s attribute coin for double spend.
2. Un-blind the resultant affect value.
3. Apply any relevant negative attribute affects (negative buffs) [The client can of course be trusted to apply positive buffs to itself. But it cannot be trusted to apply negative effects].
4. Append the affect value to the affect coin
5. Append a digital signature to the affect coin.
6. Send the completed affect coin to the target’s host server.

The completed affect coin will contain these values:

• Coin Number (random)
• Affect Type (blunt, pierce, hot, cold, etc.)
• Affecter_ID (the unique identifier of the attacker)
• Affecter_Address (address of the attacker’s host)
• Target_ID (the identifier of the target)
• Target_Address (address of the target’s host)
• Affect Value(s)
• Game-Time-Stamp (used to synchronize game servers and calculate certain affect attributes)
• Affecter’s Host Server Signature

The Effect Function

Upon receiving an AFFECT COIN the target’s host server will complete the following steps:

1. Check the expiration date on the coin.
2. Check the coin for double spending (to prevent a cheat from resending the same attack over and over).
3. Record the coin number as spent.
4. Check the digital signature on the coin.
5. Notify the target’s client of the affect, the affecter, and affecter’s address (so it knows who affected it).
6. Query the target for its attribute coin and hit point coin.
7. Apply the attribute modifications to the affect value(s) to get the EFFECT value(s).
8. Spend the old hit point coin by entering its number in the spend coin database.
9. Generate a new hit point coin reflecting the effects of the attack damage.
10. Encrypt the new hit point coin and send it to the target client.

Four Classes of Coins and Their Longevity

The basic classes of coins for this scheme are “inventory objects”, “character attributes”, and “affects” and “modifiers.” Because the duration of coins varies greatly between classes, each class will have its own spent coin table in either the central database, or the game server’s local database.

The duration of the coin and its frequency will determine the size of the “key space” needed to allow random coin numbers without collisions. In order to have the smallest possible key space coins are given expiration dates relative to their maximum possible duration in the game. When choosing the duration of a given class of coin the developer should choose a value that is long enough to make double spending of the coin after the expiration date impossible or meaningless.

In order to ensure efficient database operation, expired coins should be purged from the database with a periodicity (1/frequency) that is the same or one order of magnitude lower than the duration of that coin class. Expired spent coins are constantly cleaned out of the database because they cannot be double-spent after the expiration date.

Inventory Objects

Inventory objects may persist and be used by players for long periods of time, even years. Inventory objects and transfers in the game happen at a much lower frequency (two orders of magnitude lower) than affects (attack rounds) and modifications to character attributes. Therefore the expiration date on these coins may be 1-2 years. It can be set to a shorter duration by adding a function to the client that automatically updates unspent inventory coins that are nearing their expiration date. If a player doesn’t log on to a game server for a period greater than the inventory coin duration then his inventory coins will all be lost. Therefore the duration of inventory objects and character base attributes must be set to a reasonably long period in order to not to penalize “occasional” players.

Character Attributes

Since character attributes change often during play, it might be good to set two kinds of character attribute coins – long term (generated when the player logs off to allow several months before his next login) and short term (generated when the player logs on and changed frequently during game play).

When a player logs on to the game system (or regenerates from character death) an initialization process will take place that generates the player’s base attribute coin from the character coin and inventory item effects. Because inventory items can affect the base attributes, the coin must be recalculated every time a character gains, loses or uses an inventory item.

Affects

Affect coins will be generated with high frequency but they have a very short lifespan, so the expiration stamp on affect coins can be set to a couple of minutes.

Modifiers

In most MMOG’s there are various kinds of “buffs” or “power-ups” that confer temporary performance bonuses or penalties to a character. Going with the principle of pushing data processing to the client, we can represent positive modifiers with a coin that is sent to the client. The client machine can be trusted to include the effect of a positive modifier because it is always to the benefit of the player. Negative modifiers might be handled as short-term coins stored by the host server of the target character. Negative modifiers would be applied by the host server whenever an affect or effect is processed for that character.

Handling Inventory and Character Attributes

There are two problems with using a digital coin system for inventory management: involuntary transfers and catastrophic data loss on client machines. Each will be treated separately here.

Involuntary Inventory Transfers

There are some cases in most games where involuntary inventory transfers must occur. Examples would include character death, pick-pocketing, etc. If the only copies of the inventory object coins are stored on the client machine, then involuntary transfers are not reliable because the client cannot be trusted to honestly present ALL of its inventory coins.

The client software might be designed to comply with involuntary transfer requests, but a cracker could modify the code so that his client only offers up low value items to involuntary transfer requests. It is impossible for the game server to independently determine ALL of the inventory coins in possession of the client.

In order to solve this problem, the host server must keep an index of the unspent inventory coin numbers possessed by each client during play. This list would only be used for involuntary transfers. While this goes against the principle of trying to minimize the storage of player info on the host or central database, it is unavoidable.

When the player character is subjected to an involuntary inventory transfer, the game server can pick coin numbers from the list and subpoena the client for the entire coin that goes with that number. The digital signature on the coin allows authentication. If the client cheats and refuses to produce the coin or produces an adulterated coin there are several possible “punishments” that can be used to make this behavior uneconomical. Two possibilities are to mark the coin number as spent, thus making the item unusable to the cheating client. Another would be to fine or disable the cheater’s main player account. In either case the cost of cheating should always be higher than the possible gain from a successful cheat. (Gamblers don’t play games where the player loses 100% of the time.)

Catastrophic Client Data Loss

A second problem for the digital coin model for MMOG’s with real money economies is that if all object coins are stored on the client machine, then a hard drive failure or other catastrophe can result in the permanent loss of real value. To reduce the chances of this the game developer might add a backup server to the network so that when a player logs off an encrypted backup copy of the client’s inventory and character coins is stored on the backup server. The player might also be given the option to make a backup periodically during game play. This feature could even be automated to make it invisible to the player.

Backups would only need to be recovered if the client lost his data. Old backups with coins that have already been spent by the player would not have any value because the coin numbers would be listed as “spent” in the database.

Additional Methods

Toward the goal of pushing data processing to the client machine, developers might take advantage of zero knowledge proofs [See Bennett Yee’s summary of Zero Knowledge Proofs: http://www.cs.ucsd.edu/users/bsy/ZKP.html] in order to allow a client to prove that he has a given item/coin without having to actually spend it. This can be useful for object coins that produce modifications to character attributes as a function of possession, or that can be “used” without being consumed.

Any method that allows the client to store and process game state data but prevents cheating is useful toward this goal. Likewise, any method that can provide proof of ownership without requiring the transmission of an entire coin, saves bandwidth. There are a number of Zero Knowledge Proof Algorithms that have been developed for the purposes of financial cryptography [For an in depth treatment of Zero Knowledge Proofs see: http://www.cis.upenn.edu/~jaing/papers/znp.pdf].

Another method for pushing processing power to the client machine is to allow the client to actually generate its own attribute and hit point coins and submit the coin to the host server to be signed. The host randomly double-checks the calculations on a certain percentage of the coins.

For high-value long-lived coins such as persistent objects, the client cannot be trusted at all. But the bulk of the data processing is spent on low value repetitive operations such as attacks (affects) and changes to character attributes. These low value transactions could be farmed out to the client machine so that only the random numbers are provided by the host server. The client machine takes the random number and generates the affect coin, or the new attribute coin and then submits it to the host to be signed.

Since these coins are generated and spent several times per minute and the individual transaction has negligible economic value, the host server need only double-check the calculation on a small percentage of the transactions. If the client has been cracked so that it tries to cheat, the cheat will be detected within ten to twenty iterations. Since multiple iterations of affect coins and attribute changes occur in the time span of a minute, the cracker can be assured that his cracked client will probably be detected within a few minutes of play, and absolutely within an hour, thus negating any value to be obtained by doing such a thing. Again, the penalties for cheating should always outweigh the potential gain.

Analysis

The advantage of using this type of scheme for handling characters, objects and affects in an MMOG is that it allows each game server to only be concerned with calculating affects and effects for its own hosted clients. We reduce the data recorded in the central database to spent coin numbers and the positions of character and objects. This greatly simplifies the process of connecting multiple game servers for one game world. NPC’s, like players, would be hosted on a particular game servers.

This scheme is only cost effective if the total increase in required bandwidth costs less than the database operations that have been eliminated. As mentioned before the central premise of the model is to push as much data-processing to the client, while minimizing the bandwidth of the data transferred from the client to the host server.

While this model will require building a completely new game engine from the ground up, according to Metcalfe’s Law the long-term benefits should be proportional to the square of the number of additional users on the system. So if this system allows the efficient construction and management of larger online game worlds with more players then the benefits should exponentially outweigh the costs.

Contact

Ken Griffith can be contacted at the following email address:

griffith@goldeconomy.com

Share and Enjoy:These icons link to social bookmarking sites where readers can share and discover new web pages.
  • del.icio.us
  • digg
  • Shadows

RSS feed for this page
since June 2007

RSS feed | Trackback URI

Comments »

No comments yet.

Name (required)
E-mail (required - never shown publicly)
URI
Your Comment (smaller size | larger size)
You may use <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> in your comment.