Technical solution - a distributed server

[Crossbreed]

Of course, if the node(s) performing the mean calculation are compromised, then you're in trouble. In general, this is like ECC; you have a certain tolerance for error - you can detect it, given the system working properly to a sufficient extent.

Mean-checking wouldn't be sufficient. Otherwise you'll just generate, say, a 0.25 if that's what you need to make Illidan drop his twin blades, and generate a 0.75 at whatever trash mob you're fighting next. Your mean will be just right, but "somehow" you'd end up getting all these cool legendaries and epics

And how do you pick the clients performing the checks and e.g. RNG?

Randomly. Or GeoIP and make sure they're a long way from the peer they check.

GeoIP probably not helpful, just log on with a VPN and you can have your rigged client's ip to be wherever you want it to be.

Randomly would indeed be the only way to go, but that's exactly the question: How do you ensure it is actually random? (see next point)

Obviously the client requiring this input shouldn't chose the providers, otherwise you can just have two clients collaborate on the whole cheating thing. So you need some neutral authority to assign these - which probably comes back to a central master server though?

One way is that the peer issues a request (just like someone issuing a chat message in game) and it propogrates through the network. Each peer receiving the message has a fractional chance of responding.

Then a collborating rigged client could just choose to set his chance of responding to 100% when a its time for legendary loot generation. Also, who checks that other clients were actually asked / received this message?

Maybe you could try finding some algorithm that deterministically maps a request to some other client handling it, i.e. when a player needs to determine loot for a boss, the system e.g. hashes a combination of that player's id with the mob's id with some id of the needed request ("Get Loot"), that hash is then deterministically transformed into a number from 1 to N where N is the number of connected clients, and whatever client number comes out handles the request?
I guess all clients would need to have perfectly synced information about who is online, but I assume even in a P2P network there has to be at least one actual static server who contains a list of all connected IPs?

Moreover, a missing object does not break the database, because the database is written to tolerate this. By tolerate I mean that the database does not break, or fail; the game of course with regard to whatever happens with that object cannot continue - so the object will for example, temporarily disappear from a users inventory, or a mob will vanish. But if we have 10,000 players, and a sufficient number of copies, then we might be looking at this happening say one per century. I suspect more mobs vanish due to OTHER bugs than this...

Most databases usually have constraints in their tables to ensure data doesn't get corrupted (e.g. foreign keys must actually exist and such). You could deactivate these constraints of course, but you may just end up running the risk of corrupting your data for good.

Simple example, but if the data fragment containing your character's structural information is just missing, who's to stop someone from creating a character with exactly the same name as yours - and what happens when your information is back online then?

But generally, yes agree, you could maybe cut it down a little further that way (though I'd expect realistic numbers to be closer to 50% than to 0.03% or so).

If 50% of 10,000 players have the whole database, then it's the same as 5,000 having 100% - i.e. you're arguing half of all players need a full copy of the database for the system to consistently be able to reach all objects. This is crazy. If you have say 1,000 players, and each has 100th of the database, you already have 10x over-duplication. If they each held 50% of the database, you'd have 500x over duplication. Amazon S3 runs on *3x*.

Correct me if wrong as I haven't read up on S3 much.
But I assume they replicate data 3 times on servers all of which are intended to be up and running 24/7, i.e. each individual server has an uptime of 99.99% or so? And replication just provides failure safety, in case one of the server crashes.. so you can up availability from 99.99% to 99.99999%?

That would of course be very much unlike peer clients, who are in fact offline most of the day and arbitratily choose to log in and out all the time.

A proper calculation would be much more complex of course, but just as a very back of the envelope thing:
If you say each player is online 10% of the day, and you have 10x duplication, then each of these groups containing a data fragment has a 0.9^10 = ca 34.86% chance of not being available (i.e. none of its holders are online). So the chance of all data fragments being available would be (1-0.9^10)^100 = 0,000000000000000024%.

[Winterflaw]

Of course, if the node(s) performing the mean calculation are compromised, then you're in trouble. In general, this is like ECC; you have a certain tolerance for error - you can detect it, given the system working properly to a sufficient extent.

Mean-checking wouldn't be sufficient. Otherwise you'll just generate, say, a 0.25 if that's what you need to make Illidan drop his twin blades, and generate a 0.75 at whatever trash mob you're fighting next. Your mean will be just right, but "somehow" you'd end up getting all these cool legendaries and epics

You would also compute standard deviation, compute over shorter periods of time (last second or two or n events), etc, etc. Going into exact implementation detail is unnecessary - in general, you can statistically analysize the output of a PRNG and see if it looks dodgy.

And how do you pick the clients performing the checks and e.g. RNG?

Randomly. Or GeoIP and make sure they're a long way from the peer they check.

GeoIP probably not helpful, just log on with a VPN and you can have your rigged client's ip to be wherever you want it to be.

WIth some thousands of nodes in the systems, you would need to control a reasonable fraction of clients to have a reasonable chance of controlling those which are chosen to be your validators.

One way is that the peer issues a request (just like someone issuing a chat message in game) and it propogrates through the network. Each peer receiving the message has a fractional chance of responding.

Then a collborating rigged client could just choose to set his chance of responding to 100% when a its time for legendary loot generation. Also, who checks that other clients were actually asked / received this message?

The decisions taken by a peer are only accepted by the system if they are confirmed by other validating peers. Peers can keep a history of the requests by a peer for validation peers, and so if we find a peer issuing decisions which are being validated by peers and there is no visibility of a request from that peer for validators, we know something is up.

If peers are rigged to be 100%, all those peers which are rigged will present themselves as validators, *and also the normal fraction of unrigged nodes will present themselves as well*.

I guess all clients would need to have perfectly synced information about who is online, but I assume even in a P2P network there has to be at least one actual static server who contains a list of all connected IPs?

I think once bootstrapped the Nost peer group would never be empty - there are too many players around the world. When a client connects, send it the IPs of a good number of currently connected clients - say a thousand. When the client next starts, it iterates through those IPs until it finds a node which is currently participating in the network, and then it joins the network.

If worst comes to worst and you can't connect, a web-site somewhere can publish a few IPs.

Simple example, but if the data fragment containing your character's structural information is just missing, who's to stop someone from creating a character with exactly the same name as yours - and what happens when your information is back online then?

All events are timestamped (with error bars); if two conflicting events occur, prolly the guy with the smaller error bars wins - you want to encourage good clocks). You then need to rollback the later event and everything which derived from it - fun!

Correct me if wrong as I haven't read up on S3 much.
But I assume they replicate data 3 times on servers all of which are intended to be up and running 24/7, i.e. each individual server has an uptime of 99.99% or so? And replication just provides failure safety, in case one of the server crashes.. so you can up availability from 99.99% to 99.99999%?

Yup. 3x on 24/7 servers. It'd need to be a higher multiple, probably in proportion to the number of players on-line vs off-line. The principle works, just the numbers change. GIven that the daily increase in data is small, full replication on each node is even an option - it'd be like having a local blockchain.

A proper calculation would be much more complex of course, but just as a very back of the envelope thing:
If you say each player is online 10% of the day, and you have 10x duplication, then each of these groups containing a data fragment has a 0.9^10 = ca 34.86% chance of not being available (i.e. none of its holders are online). So the chance of all data fragments being available would be (1-0.9^10)^100 = 0,000000000000000024%.

If you have 10 duplicates, with 10% availability, then if they're on-line perfectly back-to-back you get exactly 100% coverage you need more duplicates. My feeling has been that in practise availability will roll around the world with daylight (people play in the evenings more) and so you'd prolly find *in each area where it's evening* you have a lot of overlap, i.e. the random distribution is *so* poorly matched to what would happen it gives the wrong answer.

Also, given 10k players, even 1000x still reduces the total data store on the peer by a factor of 10 and probably makes it a couple of gig tops.

Also also, it'd be nice to use Tor. Then you could run a few permanent servers, where-ever you like, on a .onion address. No one would be able to track them down for a C&D. Problem again is latency.

[wowmad]

.

[Crossbreed]

All events are timestamped (with error bars); if two conflicting events occur, prolly the guy with the smaller error bars wins - you want to encourage good clocks). You then need to rollback the later event and everything which derived from it - fun!

Hah, fun indeed. Imagine that newly created player plays for, say, 1-2 hours before somebody comes online who invalidates his actions (i.e. name already taken etc). By that time, that new player has probably caused a TON of changes in the DB, potentially even caused dependencies (e.g. traded with other players). Rolling back only these changes would probably be a huge nightmare.

Maybe you could come up with a system where each player only stores his own entries/db tables locally (what items do I own, what quests have I completed, etc.).

Now when a player has any transaction affecting these, e.g. assume he finds a new item:
A) He would send out his table file to other validating clients
B) These validating clients would hash the table before the transaction and cross check that hash with a stored value (see below)
C) Commit the transaction, re-hash the database/table file
D) Verify if that hash is equal to that the executing client (the one who found the item) propagates
E) If so, assume the transaction was valid; propagate only the hash value of the table to other clients.

So basically, the "P2P cloud" wouldn't need to store the entire database, but only hash values of each player's local databases.

Of course the issues could be that A) if these change frequently, there'd be a lot of traffic for storing updated hashes, B) each time a transaction is made, that client needs to upload his entire table to the validating clients. However, that might be mitigated by clever caching (e.g. similar to your suggestions, not the entire player base but only, say, 50 clients store hashes of a given player's DB, and pass them on to other clients before going offline; these could also cache the DB, so a requesting client wouldn't need to re-upload the entire thing for each request).

I think once bootstrapped the Nost peer group would never be empty - there are too many players around the world. When a client connects, send it the IPs of a good number of currently connected clients - say a thousand. When the client next starts, it iterates through those IPs until it finds a node which is currently participating in the network, and then it joins the network.

True - I think an issue would be keeping this info 100% synchronized with everyone though.

I.e. if you'd have an algorithm as described, that e.g. maps requests to clients handling that request based on a deterministic algorith which chooses amongst all connected clients, you'd have issues if client A knows 1328 connected clients, but client B only knows 1327 connected clients because it receives info about a new connection only 5ms later or so.

Having said that, that would just require a simple tracker server, simlar to torrent trackers. Not sure if these are really at risk from a copyright perspective - seeing what torrent trackers have been and still are used for, I'd guess these are alright from a legal standpoint.

You would also compute standard deviation, compute over shorter periods of time (last second or two or n events), etc, etc. Going into exact implementation detail is unnecessary - in general, you can statistically analysize the output of a PRNG and see if it looks dodgy.

If only a single deviation is enough to corrupt the system (i.e. does player XYZ get the twin blades, yes or no), I don't think any statistical analysis could catch a manipulation.

Having said that, maybe you choose an interim client in a similar approach as described previously (i.e. ensuring the RNG-requesting client doesn't have any say over who will handle the request). That interim client would anonymize the request and forward it to one of the RNG-node clients.
So the RNG node won't know what or who it will generate a number for, potentially sign it so the interim client cna't manipulate the result anymore (public/private key combo or sth similar), forward back to interim client, who then fwds back to requesting client. So the RNG couldn't manipulate as it would have no knowledge which request it serves. And if you only give RNG responsibility to a few nodes, they'd be responsible for generating a large enough quantity of numbers so you could add some statistical checks just as an extra layer of security.

Are you trying to think about all problems to not solve even 1? Please, you need to be focus on the solution and only after to solve the problems.

I'm not trying to be a drag here, but we're all loudly thinking about potential solutions to a given problem. Unfortunately, that also entails coming up with all the potential issues of any given idea, and analyzing if these can be overcome, or invalidate the idea.
I've been developing software for a long time, and I've made similar mistakes dozens and dozens of times - getting too excited about some idea without thinking it through properly, which often led to at some point encountering a complete roadblock, rendering all the work unusable. Sometimes throwing a way a ton of developing time.

[Winterflaw]

All events are timestamped (with error bars); if two conflicting events occur, prolly the guy with the smaller error bars wins - you want to encourage good clocks). You then need to rollback the later event and everything which derived from it - fun!

Hah, fun indeed. Imagine that newly created player plays for, say, 1-2 hours before somebody comes online who invalidates his actions (i.e. name already taken etc). By that time, that new player has probably caused a TON of changes in the DB, potentially even caused dependencies (e.g. traded with other players). Rolling back only these changes would probably be a huge nightmare.

Yup. I have in mind a dependency tree - like the blockchan - a permanent record of all events. When you have to undo *an* event, you can backtrack through the record and undo everything which evolves off of the event itself - events off events off events, etc.

A whole bunch of fun which would be avoided if you could assume all objects are always available. It would be much simpler to imagine a few dedicated servers here and there, so you could be certain an object will always be around - but I suspect that this, mmm, shortcut if you like, will affect a wide range of design decisions. After all, if we admit a dependency on those servers for one thing, why not depend on them fo a range of things?

That brings back to a multi-server server, rather than a decentralized server.

So you gotta bite the bullet, if you're going to bite the bullet.

You would also compute standard deviation, compute over shorter periods of time (last second or two or n events), etc, etc. Going into exact implementation detail is unnecessary - in general, you can statistically analysize the output of a PRNG and see if it looks dodgy.

If only a single deviation is enough to corrupt the system (i.e. does player XYZ get the twin blades, yes or no), I don't think any statistical analysis could catch a manipulation.

Consider though - large numbers of PRNG requests occur every second. They are anonymized. You have no idea which is for what, and they are being issued all over the system. So the peer doing the loot lookup would need to be compromised, and the peer producing the PRNG.

Having said that, maybe you choose an interim client in a similar approach as described previously (i.e. ensuring the RNG-requesting client doesn't have any say over who will handle the request). That interim client would anonymize the request and forward it to one of the RNG-node clients.

Which is every node, please! aim for symmetry.

So the RNG node won't know what or who it will generate a number for, potentially sign it so the interim client cna't manipulate the result anymore (public/private key combo or sth similar), forward back to interim client, who then fwds back to requesting client. So the RNG couldn't manipulate as it would have no knowledge which request it serves. And if you only give RNG responsibility to a few nodes, they'd be responsible for generating a large enough quantity of numbers so you could add some statistical checks just as an extra layer of security.

In the overall design, the cost of assigning a few nodes a particular job is high. It complicates reasoning. You have to start to think about performance - do I have enough nodes for this job - and then assigning new nodes to enter or leave the group as necessary, stuff like that. It's simpler just to think *this request can go to any node in the system*.

Are you trying to think about all problems to not solve even 1? Please, you need to be focus on the solution and only after to solve the problems.

You didn't say that

I'm not trying to be a drag here, but we're all loudly thinking about potential solutions to a given problem. Unfortunately, that also entails coming up with all the potential issues of any given idea, and analyzing if these can be overcome, or invalidate the idea.
I've been developing software for a long time, and I've made similar mistakes dozens and dozens of times - getting too excited about some idea without thinking it through properly, which often led to at some point encountering a complete roadblock, rendering all the work unusable. Sometimes throwing a way a ton of developing time.

Yup.

The main big issue to me ATM is whom is computing what.

We could assume so to begin with (spherical cow) we have a full copy of the DB on each peer, that we have to sync that database on game start - but if you play each day, that'd be okay. Five mins downloading or something at the beginning. Finding a peer to connect to isn't really a biggie, so we ignore that.

But - okay - so we assume each peer has the lot, just to remove that problem. This also means we can be sure we always have every object.

Now, how do we decide whom is computing what? and in a timely manner, so we don't have a latency issue.

Here I'm largely clueless, because I don't know what has to be computed. Don't know the server.

[Winterflaw]

As an aside, someone has solved something like this - there's a fully decentralized chat client out there, I think also it runs over Tor.

[Asc]

Only read first pages ,BUT


I AM with YOU GUYS


P.S.: Only worrying about instability of ping

[Crossbreed]

Which is every node, please! aim for symmetry.

Fair enough; if you can ensure requests are anonymized correctly, that should be enough.

As an aside, someone has solved something like this - there's a fully decentralized chat client out there, I think also it runs over Tor.

TorChat? I don't know much about that, so can't say too much there. But I assume that will need an initial connection as well, if only to the tor network.
Similar to DHT networks in the torrent world; you can decentralize 99.999%, but you will always need to have some known starting node as you can't just generate a trillion IPs and query all of them if any actually listenes to your service. But again, that works fine for torrents and I suppose the TOR network as well, so shouldn't be much of a legal point of concern.

Now, how do we decide whom is computing what? and in a timely manner, so we don't have a latency issue.

They only idea I could think of at the moment is the one mentioned earlier; where you'd have a reproducible signature of each request (as in, player ID + request ID + whatever needed metadata) and have a deterministic algorithm that maps this signature to a number, which eventually determines the validating client.
Which indeed would be easiest if you had a tracker. Without one, i.e. with a DHT-like structure, maybe you could use that signature as the seed of a RNG, and produce a sequence of numbers mapping to all of the known accounts until you eventually get one that is currently logged in and online, but that raises a lot of concerns again in terms of traceability and data synchronization (maybe solveable, but probably difficult).

[Winterflaw]

The key issue is that most data synchronization problems are solveable given plenty of *time*.

The problem is solving them in less than say 200 or 300 milliseconds.

Also, what's involved in sync when a peer joins the network? if we say all peers hold the database, the peer needs to check the latest-updated timestamp on all objects. Obviously we can't connect from one peer to every peer in the network in a timely manner, so a la eDonkey, we need to cascade the request outwards - every peer passes the request on to two other peers, peers ignore requests they've seen twice.

The request contains the timestamp of the latest update in the joining peers database, and so the peer will get back a list of nodes containing updated objects. Then you gots to go get them... in fact, what's needed is that the *normal* mechanism for staying up to date works *regardless of the difference in time*, and so joining is no different to being in in the first place.

Blah. I'm talking empty rubbish. Can't say anything meaingful without knowing the server code base.

[Winterflaw]

They only idea I could think of at the moment is the one mentioned earlier; where you'd have a reproducible signature of each request (as in, player ID + request ID + whatever needed metadata) and have a deterministic algorithm that maps this signature to a number, which eventually determines the validating client.

You can reprobe to get mutliple possible validators - add a large prime to the hash result each time to reprobe - so you can get all the nodes which are responsible for a given object.

Then, yeah, you gotta find out the IP of those nodes. Most people are on DHCP, so their IP will only be known once they join the network. So someone joining will only really be joined once other peers know they're there, to send them requests.