   Cryptographically secure p2p network?
  Hi all,I've thought up a new network protocol for my game. First off, the reasons I'm posting this is to get feedback on the design (what do you think of it?) and to have more people look at it (does it work in a cryptographically safe sense, and do the conjectures I pose hold?).The ideas behind my design are the following:- Anybody can join with the base minimal executable.- No single computer can cause the network to fail.- Games can be played between anybody on the earth without fail- Cheating is impossible- People have a player profile- Distribution of the game is done user-to-user.- People can find other people at random- People can recommend others and keep track of who their friends areAnd that set of requirements without a server (as in, client-server game setup). A basic server will provide:- The base executable (3d rendering, physics, audio, input, networking and p2p base)- The game definition file (somewhat like a torrent file)Running the base executable makes your computer join a network of computers, running in peer-to-peer mode. Before joining your computer generates a new public/private key pair. Each connection is encrypted&authenticated by the handshake. It is based on Diffie-Hellman with public key exchange (authenticated) and the requirement that the receiving end needs to keep no records until the connection is fully established:Client A sends a connect request to server B.Server B sends its public key to client AClient A thinks up a random number a and sends g^a mod n, plus its public key, encrypted with B's public key, to server B.Server B decrypts message from client A, thinks up a random number b and sends g^b mod n encrypted with A's public key to client A. It calculates (g^a)^b and takes a hash of that to use as link key.Client A decrypts message from server B, calculates (g^b)^a, takes a hash of that to use as link key.Server B only has the right link key if the decryption was successful, which authenticates it as the owner of the private key B. Client A can only have the link key if the decryption was successful, which authenticates it as the owner of private key A. Nobody other than these two computers can read the data on the link, due to the base of Diffie-Hellman, not even if both the private keys leak after this moment.So, each computer you're connected to has the private key to a public key that you know of. That allows a person to be identified by his public key. Figuring out who it is in real life, if relevant, is out of scope. Every player allows others to download files from him. All files are identical to all users (the game content files, for instance) except for one - player.profile. That file, signed with the users' private key, describes the person as they see themselves, including a profile picture (with any data basically). You can tag a public key as somebody you know before and anybody you interact with knowingly is saved anyway, including a short history of what kind of interaction. You can publish a note about somebody else on the p2p network indicating your opinion (signed with your private key) about somebody else. So, to summarize in the middle, these requirements are met (I think):- Anybody can join with the base minimal executable.- No single computer can cause the network to fail. (p2p network protocol)- People have a player profile- People can find other people at random (p2p network chat)- People can recommend others and keep track of who their friends are- Distribution of the game is done user-to-user.The following two remain:- Cheating is impossibleThe game, when started, communicates by network by sending an input delta packet, which indicates during which game cycle which buttons were pressed. These are sent to all other clients. Once a second (every 60 frames) a hash is calculated over the physics state. The physics engine is deterministic, the input given is deterministic which means that if the hashes don't match, somebody's lying about the game state. Game ends.This opens up a loophole though, how old can the update be? How many cycles in the past should I still apply it? For that, the second item comes in:- Games can be played between anybody on the earth without failThat only holds if you can survive the max RTT around the world for one game update packet, plus some 40% or so for certainty. 20000 km at about 200000km/s (speed of light in metal) is 0.1 second for a message. That's 6 game cycles. Allowing 9 is sufficient for this to work, even with a little packet loss. It does mean that a ping of over 150 single-trip (or 300 round-trip) will end the game immediately.So...What do you think of it?Does it work in a cryptographically safe sense, and do the conjectures I pose hold?   
Quote:What do you think of it?The same I think about this.It is solving a problem that doesn't exist in a way that doesn't work.It's geeky, but has no value or merit to would-be users. Without exception, there is no distributed service that would work in real world. Feel free to point one out. No, "torrents" are not distributed, they rely on ratings/filterings provided by TPB (and half-a-dozen others) to filter out the spam, malicious uploads and low quality content, as well as trusted labels of release groups to seed scene releases and establish them as primary sources. This lack of centralized authority was what killed all other P2P protocols.At very best, P2P angle can supplement an existing centralized service (apt repository, Blizzard downloader), but can never serve as central backbone.Trusted P2P is same as cold fusion, flying cars, Linux on desktop, ... It's has been only 2 years away for many decades.How do I play Halo on this thing? How do I show my Mass Effect Insane Difficulty Achievement? How do I show my level 33 Human Wizard's gear in Stranglethorn? And why is this better than my iArmory App?If you want to see the fidelity of "secure" P2P network, download Tor. One update per 5 seconds will just barely work if connected to a good node and not some DSL in some bedroom, downloading anything larger than a couple of hundred kilobytes is a pipedream. And it also isn't secure, since exit nodes are inevitably unencrypted - in proposed system this problem remains with content producers.   ;Quote:Original post by AntheusQuote:What do you think of it?The same I think about this.I did notice they had similar basics. Nonetheless, I've started this idea over a few hours ago - I'm not trying to repeat their idea.Quote:It is solving a problem that doesn't exist in a way that doesn't work.Their method could be sound. That article holds less detail than a single-pixel photograph.Quote:No, "torrents" are not distributed, they rely on ratings/filterings provided by TPB (and half-a-dozen others) to filter out the spam, malicious uploads and low quality content, as well as trusted labels of release groups to seed scene releases and establish them as primary sources. This lack of centralized authority was what killed all other P2P protocols.And there's no indication above that I'm going to distribute my own game as "just a torrent somewhere". The thing is just about the network basics & integrity of users toward each other. In the same basis, given that you know which game (torrent) you want to download, there's no reason why it couldn't be distributed. The basics behind p2p is to have a chat network akin to IRC but without default set servers. The basic thing that I want to have working first (in theory, at the very least) is a simple 4-player game. One guy in the America, one in Australia, one in Asia and one in Europe. They should be able to play the game & know that none of them is cheating.Quote:At very best, P2P angle can supplement an existing centralized service (apt repository, Blizzard downloader), but can never serve as central backbone.I think you mean "source" instead of backbone. BitTorrent has a source for valid torrents and a backbone for the bulk of the data transfer, in the same way that a human has a brain and a backbone - the brain does the smarts, the backbone does the lifting.Quote:Trusted P2P is same as cold fusion, flying cars, Linux on desktop, ... It's has been only 2 years away for many decades.Cold fusion and flying cars haven't been two years away ever. The best guesstimate that I've seen so far is 20 for both - which is researcher for "we have conclusively proven it possible, but not with anything we have available". Linux on the desktop can't have been two years away for many decades as it's only been around for two, and not even complete enough to use as a geek for half of that. On the subject of Linux on the desktop, half the desktops at my work place use Linux as it's easier to use; the other half (most of them at least) are required to use applications that don't run on Linux.Quote:How do I play Halo on this thing?Given no cooperation from Bungie, I expect you won't.Quote:How do I show my Mass Effect Insane Difficulty Achievement?By including your Achievement file that includes your public key that was signed with the private key of the game creator?Quote:How do I show my level 33 Human Wizard's gear in Stranglethorn?I don't even get this one. Quote:And why is this better than my iArmory App?Again, what's that? I get the feeling I'm aiming for a different demographic than the one I think you are assuming.Quote:If you want to see the fidelity of "secure" P2P network, download Tor. One update per 5 seconds will just barely work if connected to a good node and not some DSL in some bedroom, downloading anything larger than a couple of hundred kilobytes is a pipedream. And it also isn't secure, since exit nodes are inevitably unencrypted - in proposed system this problem remains with content producers.The goal is to make it "secure" in that it's in the users best interest to keep it as designed. Uesrs don't gain much by sharing their private key and do stand to lose everything online for that. I'm thankful for your quick reply. I get the feeling that you're trying to argue that the idea is futile, which isn't something I'm open for discussing. Let's first get the technical feasibility and basics out of the way, we'll talk about the reasonableness of what I'm trying to achieve in total after that.   ;Quote:Original post by dascandyI get the feeling that you're trying to argue that the idea is futile, which isn't something I'm open for discussing. Let's first get the technical feasibility and basics out of the wayIt can be implemented. In same way that bubble sort can be implemented in place of quick sort. However, matchmaking and related tasks are heavily patented, so this service might not be available without proper licensing in US and EU, and due to decentralized nature it would not be permitted in China.But whatever the implementation, it will be inferior in every way to any existing platform (X-Box Live, Steam, Blizzard account, Facebook, ...).Which problem does it solve that is inadequately catered to right now?Distribution, reliability, hosting, search, profiles, matchmaking and cheating are not problems in any of the above platforms.   ;Quote:Original post by AntheusQuote:Original post by dascandyI get the feeling that you're trying to argue that the idea is futile, which isn't something I'm open for discussing. Let's first get the technical feasibility and basics out of the wayIt can be implemented. In same way that bubble sort can be implemented in place of quick sort.You know that whether or not it's implementable isn't the question. I didn't come here with my ideas to get insulted and I hope that this isn't your default response.Quote:But whatever the implementation, it will be inferior in every way to any existing platform (X-Box Live, Steam, Blizzard account, Facebook, ...).... when judged by how well they do what they are good at. In much the same way that Linux is a poor Windows for most people, and will most likely always remain.Quote:Which problem does it solve that is inadequately catered to right now?Distribution, reliability, hosting, search, profiles, matchmaking and cheating are not problems in any of the above platforms.The ability to play a game that I've paid for without being required to use a server they provide. The right as a user to play on a local LAN without internet connectivity. The ability to make a back up of a game and expect it to work. The accessibility for indie game developers to create a game and have it published. The ability to run on any platform you dare to compile the code for. The ability to make a DRM-free game that is still securely spread as far as is possible given the above items.As far as I know none of these platforms provide that. It also provides network play to my current project which doesn't have network support yet.   ;Quote:Original post by AntheusTrusted P2P is same as cold fusion, flying cars, Linux on desktop, ...In a strange twist of fate, warm fusion and Steam on Linux are both announced a short-term reality. I'm still holding out for flying car reports to see if I can make it 3 out of 3. Although there was a flying Ford Pinto a few decades ago, sadly it crashed leaving very few flying cars - and certainly no commercially viable ones - today.;  How does a player join? They must sync with the current state in order to run the simulation deterministically. They must get that state from other players. Presumably they only need a subset of the state, based on players geographically (in game, not IRL) close to them. A bunch of cheaters can join (or one with lots of bots) can join, congregate and broadcast non-canon state to new users.Unless every client will have the entire game world in memory, and run the simulation on every player in it, then you cannot compare hashes of the state between two players. Two players would have to agree on some subset to compare, but which?Quote:These are sent to all other clients. Once a second (every 60 frames) a hash is calculated over the physics state. The physics engine is deterministic, the input given is deterministic which means that if the hashes don't match, somebody's lying about the game state. Game ends.For who? With a custom client I can DOS other players by communicating different inputs to each of them and watch them accuse each other of cheating. I can echo back the hash packets I see from other players to themselves so they think I'm a good player.There is no authorative list of clients, so I can generate a couple of thousand keys and get them to sign me glowing references about how great I am. When I join, is there anything to stop me from saying I'm a level 9999 titan?That is just a couple of seconds of thinking. There are far more attacks possible I imagine.The problem is classic, you have no real trust model. Without some central authority, trust is really hard. You need to expose your mplicit assumptions, such as that there is some authorative view of the world, or even a subset thereof, somewhere (how would a new player get such a thing from your system?). Cryptography is the easy part here.   ;Quote:Original post by rip-offHow does a player join? They must sync with the current state in order to run the simulation deterministically. I'm only aiming for non-MMO games. That means that all players must be present on game start and, if they join later on (if I support that) the game may freeze for a second for them to join.Quote:They must get that state from other players. Presumably they only need a subset of the state, based on players geographically (in game, not IRL) close to them. As it's a non-massive game they do have to keep all state for all players (according to the same game rules) so they do have a full state, but for much fewer people.Quote:A bunch of cheaters can join (or one with lots of bots) can join, congregate and broadcast non-canon state to new users.That's true and that's why I'm hesitant to support later joiners. Quote:Unless every client will have the entire game world in memory, and run the simulation on every player in it, then you cannot compare hashes of the state between two players.That's mostly true - they only need to agree on the subset of the game world to keep in memory. Quote:For who? With a custom client I can DOS other players by communicating different inputs to each of them and watch them accuse each other of cheating. There's no accusing of cheating. The only thing that happens is that the running game is either exited or somehow resolved (if possible) to a coherent state. If the game desyncs you can do an N-to-N broadcast of the deltas of that second and see which player you have to leave out to make it sync again, and then add a local note saying "this player suspected of having a hacked game executable".Quote:I can echo back the hash packets I see from other players to themselves so they think I'm a good player.Now that's a good point. That's the reason I posted this online. I'll take a few minutes to think about that... :-)Quote:There is no authorative list of clients, so I can generate a couple of thousand keys and get them to sign me glowing references about how great I am.If you keep those thousand clients online, yes, you would have a thousand glowing references from "people" that nobody's every played against, talked to or met. In much the same way as random matches online nowadays could match you up against a complete butthole, or some random other person that doesn't align with you.Quote:When I join, is there anything to stop me from saying I'm a level 9999 titan?I haven't thought about any games allowing you to keep state between games, so there's no saying your X, Y or Z other than the color you'll be playing.Quote:That is just a couple of seconds of thinking. There are far more attacks possible I imagine.Given the constraints that I forgot to mention (my mind forgets to give you the details that I assume - and since I assume them I forget to give them to you), this should be a lot smaller now. Thanks for thinking along!Quote:The problem is classic, you have no real trust model. Without some central authority, trust is really hard. I'm thinking of a trust model not unlike Geocities, Facebook or LinkedIn. There's *nothing* stopping you from pretending to be your own country of people adoring you, other than that unless you make that true, nobody will have a link they trust to you that says you're great. In much the same way that a typical "US-book" sold here (europe) has a hundred glowing reviews from loads of people and magazines I've never heard of - and I therefore don't care, and just look at whether the book contains what I need. People play games together, that's the basis of the system. People that play a fair game, that act nice to one another and that help you out when you're about to get shot are the people you'd give a glowing review and probably likewise. You can trust those that they trust; for people you don't know ask your friend list for whether they know them & what they know. Unknown people remain that - unknown, until you try out a game. If you then play a game with somebody who has a thousand glowing reviews and find that they're rude, mark them as being rude and your review will be read as more important than those 1000 glowing ones.Quote:You need to expose your mplicit assumptions, such as that there is some authorative view of the world, or even a subset thereof, somewhere (how would a new player get such a thing from your system?). Cryptography is the easy part here.I think I can't answer this bit other than by saying that it's not a massive world - it's a very limited one in which the simulation will encompass 16 players tops, where simulating one is for a modern computer fairly trivial.   ;  I don't know where I decided it was a MMO style game. Maybe it was that talk of playing with people all around the world =)With a small pool of players who all start at the same time, that is certainly a different situation. Basically, as long as the majority aren't cheating, you have some hope.But your requirement that "cheating is impossible" is a tricky one. In a P2P system, the client knows everything, so wallhacks or aimhacks or other client-side advantages are quite easy to do. But it should be possible to architect the system such that corruption of the game state by a malicious minority is not possible, or is at least detected and these players can be ejected. The challenge is can you do it without impacting the performance and latency of the game.   ;Quote: Running the base executable makes your computer join a network of computersHow?Once that question is adequately answered, you'll have a pretty good view of what the weaknesses of this approach is.I think that the reason Antheus is annoyed is that this idea has been coming up for 20 years. People who ought to know better have been drawn in by it. Small-scale, feasible projects have been starved while attention has chased a P2P grail that simply doesn't exist.The current state of the art when it comes to P2P gaming (on MMO scale) is probably the VAST research project, and even there, they pretty much realize that it can't actually work without a little bit of trusted server involvement.