Les agents adversaires peuvent-ils lancer des pièces?

9

Je pensais aux jeux peer-to-peer en envisageant un simple jeu de lancer de pièces.

Vous ouvrez votre version de P2PCoinFlipping Beta 2.3 et il affiche une liste de serveurs de noms de joueurs. Après avoir choisi le serveur le plus proche, un tableau de bord des joueurs les plus chanceux apparaît. Vous choisissez le joueur le mieux classé et le jeu commence. Depuis que vous avez commencé la bataille, le joueur adverse choisit le côté de la pièce, les têtes et vous êtes affecté à la queue. Un joli petit graphique apparaît, montrant une pièce tombante qui finit par atterrir sur les têtes. Dommage, vous perdez.

Mais comment savez-vous que le résultat est juste?

Si le résultat est choisi sur votre ordinateur, vous pouvez modifier le programme pour choisir de gagner et la même chose s'applique à l'adversaire. Le jeu n'est pas déterministe, vous ne pouvez donc pas sembler valider le résultat.

Est-il possible que plusieurs agents contradictoires indépendants s'entendent sur un événement non déterministe?

random peer-to-peer AnnanFay
la source
Bien qu'il ne réponde pas à la question, c'est pourquoi le multijoueur sur serveur est bon - laissez le serveur être l'arbitre. Une idée intéressante serait de s'appuyer sur un service tiers comme lanceur de pièces. Pourrait-on par exemple utiliser un générateur de GUID en ligne (comme guidgenerator.com ) comme base d'un système?
Tim Holt

Réponses:

6

Cette procédure fera le travail:

  1. chacun des deux pairs génère un nombre aléatoire.
  2. chaque homologue crée un hachage salé de son numéro et l'envoie à l'autre homologue.
  3. l'un ou l'autre pair rejette la demande s'il a le même hachage qu'il a envoyé.
  4. une fois que les deux pairs ont confirmé la réception des hachages de l'autre, chacun envoie ensuite à l'autre son nombre aléatoire réel.
  5. chaque pair vérifie que le hachage envoyé par l'autre est bien un hachage du nombre aléatoire. rejeter l'échange.

  6. le résultat du lancer de pièce est le OU exclusif du bit le moins significatif de chaque nombre, c'est-à-dire

    (a & 1) ^ (b & 1)

Une solution alternative:

  1. Chacun des deux pairs décide entre eux pour décider qui doit aller en premier. Appelons-les A et B, juste pour être originaux.
  2. Le pair A génère son nombre aléatoire, crée un hachage salé et envoie le hachage au pair B.
  3. B génère son nombre aléatoire et l'envoie à A.
  4. A envoie son nombre aléatoire à B.
  5. B vérifie que le hachage salé est le hachage du numéro qu'il a reçu.
  6. le résultat du lancer de pièce est le OU exclusif du bit le moins significatif de chaque nombre, comme ci-dessus.

J'ai posé cette question sur le site de cryptographie et j'ai établi qu'il est assez sécurisé. Apparemment, il s'agit d'une variante du plan d'engagement .

Michael Slade
la source
1
Ce protocole, comme décrit, est vulnérable à une attaque de relecture, où un pair fait simplement écho aux messages de l'autre pair pour forcer le résultat à 0. Il existe cependant plusieurs modifications simples qui peuvent être apportées pour empêcher cette attaque.
Ilmari Karonen
Cette version devrait être bien.
Michael Slade
Comment cela empêche-t-il un pair de simplement choisir un nombre plutôt que de le générer au hasard?
Kylotan
@Kylotan: Ce n'est pas le cas, mais tant qu'au moins un des pairs choisit au hasard, le résultat sera aléatoire.
Ilmari Karonen
2
Un pair n'a rien à gagner même en choisissant 0 tout le temps, car cela donne l'avantage à l'autre pair. Le résultat final dépend également des chiffres fournis par les deux pairs.
Michael Slade
2

Il s'avère que non seulement les agents adversaires peuvent lancer des pièces, mais que les agents adversaires peuvent jouer au poker .

Cela dit, cela a tendance à être extrêmement coûteux en calcul et assez difficile à bien faire. Cela ne vaut probablement pas l'effort de mise en œuvre. Regardez combien de protocoles multijoueurs sont hilarement vulnérables à un serveur malveillant (à savoir: tous ceux que je connais), et leur popularité, et cela ne semble tout simplement pas être une utilisation pratique du temps.

StarCraft II en est un bon exemple. C'est un jeu où le dépistage est essentiel, et savoir ce que fait l'ennemi peut donner un avantage phénoménal, et des prix à cinq chiffres ou plus reposent régulièrement sur les résultats. . . et pourtant, les deux ordinateurs ont la totalité de l'état du jeu stockée à tout moment! Il est trivial d'écrire un programme qui vous permet de regarder directement l'adversaire et de vous énerver.

Il s'avère qu'aucun des concurrents sérieux n'utilise ces programmes. C'est trop facile à détecter ("hé, Jim, comment savez-vous toujours ce que je construis au moment où je le construis?") Et ça ne vaut pas la peine.

Cela dit, si vous voulez plus d'informations, vous voudrez vous pencher sur la cryptographie en détail - ce n'est pas vraiment dans le domaine du développement de jeux.

ZorbaTHut
la source