[MUD-Dev] Seamlessly Distributed Online Environments

[J C Lawrence]

On Thu, 11 Sep 2003 01:53:26 +0100 
Crosbie Fitch <crosbie at cyberspaceengineers.org> wrote:
> From: Draymoor (Philip Loguinov)

>> People connect to the central database, the city, and can wander
>> about. If they enter a building in that city, they automaticly
>> connect to the server that runs the node that is that building. They
>> then communicate with that server, obeying whatever rules the
>> server's writer decides to implement.

> Might I suggest that for this 'central database' you utilise a p2p
> service, like Gnutella say?

> You might also even consider letting this p2p service contain the
> content.

That would raise far more problems than it solved.  P2P doesn't actually
solve anything here except buzzword factor.

If you anonymously P2P distribute content then you need to be able to
verify that the retrieved content matches the name assigned to it.
Otherwise it would be trivially simple to poison the object space with
bogus content using the same names (cf Madonna's bogus MP3s).  

You can't use hash functions or CRCs in the obvious manner as a method
of verification as there's no control over the hash values not also
being poison values. So that leaves you pretty much with digital
signatures and having to also implement a PKI system to distribute the
keys, authenticate the keys, etc just to be able to verify that a given
data object really is what it says it is.  But don't forget to add in
the crypto overheads to each transfer transaction to verify that the
retrieved data is what it claims to be and you've passed the point of
negative return, and then the possibly endless chain of re-retrievals
for objects which don't match their signatures.

The other approach which is seemingly feasible here but mined with
problems is a forward chained hash approach. Assume that BlobA refers to
BlobB.  It doesn't really matter what the data items are, but for the
sake of simplicity assume that they are world file definitions or some
such.
 
  BlobA -> BlobB

Now BlobA not only contains the name of BlobB (so that it can be
retrieved by whatever method), but also a strong one-way function of
BlobB (eg MD5SUM).  Then, when BlobB is retrieved the MD5 can be
computed, compared to the retrieved data, and the item discard and a
different copy retrieved if they don't match.  Which means that the
latency required to retrieve a given item is non-deterministic and
potentially huge: you don't know how many copies you'll have to go thru
until you find the right one.

So you extend the P2P protocol to make the request not only name the
item but also state its hash, such that the serving system can return a
null set if its data nodes don't match.  Except that doesn't work
because we're talking P2P and the nodes are in the hands of the enemy
(they're clients), and we can't trust them to compute correct hashes,
let alone return an object with the hash value it claims it has.  Ergo
its a lazy optimisation function which the recipient node is going to
have to re-compute and verify anyway.  We gained nothing but more code
and more complexity.

The core assumption in forward chained hashes is that there is an
auditable backtrail of hash functions which can be traced back to some
known-good and trustworthy data set (eg on the vendor's CD or
distributed as part of the source package), and that the hash value for
an object is embedded in the object that refers to it so that it can be
properly verified. 

Without a known good seed for the first data node, your first data node
is also adopting an arbitrary and unknown forward chained hash mesh.
All bets are off from that point onward in terms of what you get.

And that still doesn't protect against versioning -- which, in a P2P
world, is going to happen as nobody is either ensuring uniqueness in the
global namespace[1].

I've got one world data file which points to the MinesOfMoria.  That's
right the MinesOfMoria that Bubba wrote.  But I've also got another
world data file which points to a MinesOfMoria object except that this
one has a different hash value.  

It turns out that when Bubba wrote CastleKrak it pointed to Boffo's
MinesOfMoria(1), which in turn pointed to the EvenForest.  However when
the ElvenForest was written Bernie didn't have Boffo's MinesOfMoria, he
had Bruce's.  They both have the same name, except they're fundamentally
different data files.

    CastleKrak -> MinesOfMoria(1) -> ElvenForest

    CastleKrak <- MinesOfMoria(2) <- ElvenForest

Now this is cute and fun for those cases where you actually want it, but
its as annoying as heck when you don't and you've no way of preventing
it.

So you add a reverse chain in as well.

If A points to B, B must also have a reverse pointer to A, and the two
hash values must correspond to the data items they reference.  More
computational load -- and it doesn't solve the problem.  Again, your
data is in the hands of the enemy.  There's nothing to say that the data
file can't have the proper references but then go and do something
entirely different at runtime.

So you have spaghetti.  Nodes point to other nodes and maybe you get
what you want, and maybe you won't.  You've some audit functionality to
help ensure that the mesh of pointers is logically consistent, but you
can't guarantee it, you can't effective;y detect many of the cases where
it isn't, so you hope the right things happen.

[1] Now if you add a central server, a key server, a maintainer of a
global namespace and registration system then the whole game changes.
You can only guarantee uniqueness, but you can provide authoritative
hash values and a centralized efficient indexing method to help ensure
that the first object you retrieve is the object you want with the hash
you want -- which is great all the way up to the point where somebody
starts paying for the bandwidth and system charges for the central node
and the /. crowd starts complaining that it really isn't true P2P any
more.

--
J C Lawrence                
---------(*)                Satan, oscillate my metallic sonatas. 
claw at kanga.nu               He lived as a devil, eh?		  
http://www.kanga.nu/~claw/  Evil is a name of a foeman, as I live.

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev