Ill try to explain it better.

Alice and Bob are fighting for a gold coin. They contact some peers to watch and prevent cheating. Their peers chose a random number b and send it to Alice and Bob. Alice and Bob now have the same number b and can not change it because of the peers. Alice chooses a random number A and sends it to no one. Bob also chooses a random number B and sends it to no one. Then Alice computes i = b^A mod m (m is built into the program so there is no disagreement to its value) and sends i to Bob and all watching peers. Bob computes j = b^B mod m and sends it to Alice and the peers. At this point Alice cant change A without changing i because solving a discrete log is a hard problem. Same goes for Bob. Alice and Bob now compute s = b^(AB) mod m and send to all peers. They should not disagree. If they do then one is trying to cheat and no one gets the gold (or some other action takes place). Now and only now can Alice and Bob reveal the numbers A and B. They cannot be changed from there original value without detection. Every one computes w = hash(A,B) and then they will all know who the winner is.

I hope that made sense. If I'm wrong please point out my mistake.

Edit: s = b^(AB) mod m is computed without exchanging A and B.

Quote:Original post by mike25025
No one knows what the private numbers are (except the creator) untill after diffie-hellman. Because of that the other peer cant chose a number that will make him win.

But like you pointed out its not practical to diffie-hellman so it doesn't really matter how secure it is.

From what I gather, diffie-hellman arbitration would only be required when arbitration is in fact necessary. Not all items will have two users claiming to pick it up at the same time. If both clients are agreeing on a similar timing scale (e.g. keep semi-syncronous clocks, timestamping actions and the like with that), diffie-hellman would only occur when these timestamps are identical. In a scenario with a malicious party, their intent would be to either:

1) Break the rule(s) and move more than allowed by the logical timescale (combatted/countered by the verification of 3rd party peers as to modification legality)

or:

2) Follow the rule(s) but "bend" the actions taken in logical time (e.g. have no delay as the user moves his mouse, instead as soon as A is reached in logic-time proceed to B, even if the user delayed this movement). This would only be combatable by too-expert detection (e.g. "you can't get 100% hit ratio, all headshots" in the average FPS) and client-checksuming of some sort (e.g. punkbuster) - both nonpermanent solutions. This said, this only pushes the curve of what the player can do, rather than breaks it giving godlike powers. But, I think the big key in getting this conceptual P2P database working isn't in preventing hacks, it's in containment to the point where a hack would not ruin the experience for another player not alter the data by much, for it to remain relatively consistant (attempting to use more generic terminology).

One can also reduce the need for repeated lengthy arbitration is with a tit-for-tat mechanism - e.g. do a full contest to see who starts with the "favorable" position, then when fighting for items, alternate - e.g. if A wins the "favorable" position, the first item argued over is awarded to A, the second item argued over is awarded to B, third to A, fourth to B, and so forth. Expanding this to N > 2 would be tricky, but I believe doable.

[Edited by - MaulingMonkey on August 13, 2005 2:48:49 PM]

Quote:Original post by hplus0603

Quote:Not all items will have two users claiming to pick it up at the same time.

Most of the time, you don't even know that you have a second user wanting to claim the same object, because of latencies. You don't hear about it until after you've already taken the local action, unless you somehow vote for arbitration for each action.

You won't know immediately, this is true, but this is also a seperatable issue - you want an undoable "pick-up-into-inventory" action, which in a simple scheme could be solved by first tracking objects as "tenatively picked up". Once the data for all "local" clients comes in as moving in a manner which would make it impossible for them to arrive at the item before you (in logic-time), then that item can safely be moved into your confirmed inventory.

Quote:Anyway, what if the peer I contact to perform arbitration is, in fact, compromised, and running on the machine right next to me? With any voting system, as long as I can provide at least half of the voters, then I can rig the vote.

I was considering this earlier, there's a few solutions I can identify to deal with the problem of arbitration:

1) Trusted 3rd party (peer, server, etc) - if both parties can trust an external source to the generation of random numbers (such as explicitly set peers), that peer can be used (some websites do this for traditional pen and paper RPGs online, such as Irony Games' Dice Server. Here, the peers are the players and the website they both agree they can trust).

In a P2P setting, this would not be a guaranteed source of randomness in most cases - but two members belonging to a guild (following traditionalistic MMO guidelines) may decide they can trust other members of the guild, or maybe just their guild leader. This could help reduce bandwidth (they only need to check one peer), but admittedly dosn't work for the general case.

2) Psuedo-Random Number Generator - if both parties can agree on a RNG which produces identical results for both players given an initial seed, and agree upon when this RNG is used, and continue to use this single RNG for a set period (example: "the next 1000 uses"), although a malicious party may be able to affect the vote to some degree, they would not be able to dictate it. Precalculated random values agreed upon to be used would also work here.

3) Alternation - an initial semi-random value (the XOR of the public keys of the clients involved?) is used to start off the streak, then distribution occurs equally in order (A B A B A B ...)

4) Make it deterministic. If the clients reach it at the same "time", whoever's DEX attribute is higher gets it (they're a little faster). If those are the same, STR (whoever has a better grip on it). If those are the same, INT (whoever can figure out how to trick the other into letting go gets it). There will eventually be some loophole that you need third party arbitration for, but if it only avails itself in 1 out of a bazillion instances, the hackability of the third party arbitration won't be a major issue.

You can cascade most of these methods as well - if you share a mutual friend who's online, you can use him, failing that, a PRNG, failing being able to agree on an acceptable start for that, alternation, failing that, a nearly certain to resolve the dispute deterministic approach, failing that, peer vote.

Also, you can help stave off the situation where a malicious party controls +50% of the vote with geography limits - e.g. no more than 25% of the vote may come from a single class-B subnet.

Quote:Original post by hplus0603

Quote:Trusted 3rd party

Once you start following this thread to its logical conclusion (especially if you care about performance), you end up with an authoritative server solution, and it's not P2P anymore :-)

Well, the hybridization of F2F (friend to friend) and P2P networking strategies. The _easiest_, and least "expensive" method is of course an authoritative server. I put "expensive" in quotes because it's using the resources allready bought by the clients, rather than a central authority which would have to pay for all the hardware by it's lonesome (one of the many reasons for the low number of free mmos out there, I believe ;-)).

Is a trusted 3rd party a viable solution in all cases in a P2P Network? No, because a trusted 3rd party peer may not exist. Taking advantage of a mutually trusted peer when one is available would be an optimization point rather than a primary method of use.