[MUD-Dev] Trusting the Client (Re: Laws of Online World Design)

[mark at erdos.Stanford.EDU]

Raph Koster writes:
> BTW, I have noticed nobody has quarreled with any of the laws yet. Are
> they all that acceptable? And is this endeavor useful? (I am finding it
> so, but wonder about everyone else).

I'd like to share a few ideas about this "law":
  Never trust the client.
   Never put anything on the client. The client is in the hands of the
   enemy. Never ever ever forget this.

While I agree the sentiment is a good one, I believe there is more leeway
here than one might think.  A more restricted law might be: "Never put
anything you desire to be secret on the client."

Now, while the server has no control over what the client (or 
pseudo-client) actually _does_, it certainly has control over what changes
it allows the client to make on the server state.  I believe this can
be taken advantage of in the following way.

Consider a simple scenario: Bubba enters a room containing a monster,
Boffo.  Bubba attacks Boffo and slays him in one hit, takes his gold,
and exits the room.

1. When Bubba enters the room, the entire room state (including Boffo)
   is downloaded to his client, along with a random number seed.

2. The game procedes as "normal", but with all computation done on the client.
   Every command Bubba enters is logged.

3. When Bubba leaves the room, the room state (and Bubba's updated state)
   is sent back to the server.  Since the game is deterministic (given
   the random number seed and the "inputs"--- Bubba's commands), the
   server can "audit" the new state by replaying the events and see if the 
   original algorithm has been followed.

A more "trusting" version of this scheme might merely check certain
invariants: no more total gold at the end of the client session than
before, etc.

Benefits:
  -- Possibly less server traffic (or at least "batch" traffic, with less
     overhead.)
  -- Better response time for Bubba's player

Drawbacks:
  -- Greater incoming traffic to the server, even if less outgoing traffic.

Limitations:
  -- No algorithms or statistics can be hidden.  Only "perfect-information"
     games can take advantage of such a strategy.  The user is restricted
     to doing as well as _possible_, but no better.  (Although the user can 
     "roll back time" and try multiple approaches to a problem, this is no
     "bigger" than giving him the algorithm, and can be alleviated by
     timeouts.)
  -- Difficult to scale to multiple interacting clients.

Are the limitations sufficient to scrap such an approach entirely?  Or
are there games for which auditing is sufficient to restrain cheaters?
I think the latter (see below).

This idea is motiviated partially by "Byzantine agreement" protocols
where transactions are kept consistent even in the presence of
multiple compromised servers, and also by the desire to make 
serverless games--- where you _must_ put everything on the client.
For example, in distributed "MazeWar", it's pretty much impossible to 
prevent the client from showing the locations of all the other players,
but it's not impossible to determine that another client is cheating
(by "teleporting", firing before his missile hits anything, increasing
his score without a kill, etc.)

Mark Gritter
mgritter at cs.stanford.edu
Tirn Aill MUD: www.tirnaill.org