Os agentes adversários podem jogar moedas?

9

Eu estava pensando em jogos ponto a ponto, considerando um simples jogo de lançamento de moedas.

Você abre sua versão do P2PCoinFlipping Beta 2.3 e ele exibe uma lista de servidores de nomes de jogadores. Depois de escolher o servidor mais próximo, um placar dos jogadores mais sortudos aparece. Você escolhe o jogador com a classificação mais alta e o jogo começa. Desde que você começou a batalha, o jogador adversário escolhe o lado da moeda, as cabeças e as caudas. Um belo pequeno gráfico aparece exibindo uma moeda caindo eventualmente caindo sobre as cabeças. Pena que você perde.

Mas como você sabe que o resultado é justo?

Se o resultado for escolhido no seu computador, você pode editar o programa para escolher vencer e o mesmo se aplica ao oponente. O jogo não é determinístico, então você não consegue validar o resultado.

É possível que vários agentes adversários independentes concordem com um evento não determinístico?

AnnanFay
fonte
Apesar de não responder à pergunta, é por isso que o multiplayer baseado em servidor é bom - deixe o servidor ser o árbitro. Uma idéia interessante seria contar com algum serviço de terceiros como lançador de moedas. Alguém poderia, por exemplo, usar um gerador de GUID on-line (como guidgenerator.com ) como base para um sistema?
Tim Holt

Respostas:

6

Este procedimento fará o trabalho:

  1. cada um dos dois pares gera um número aleatório.
  2. cada ponto cria um hash salgado de seu número e o envia para o outro ponto.
  3. qualquer um dos pares rejeita a solicitação se obtiver o mesmo hash enviado.
  4. uma vez que os dois pares confirmam a recepção dos hashes um do outro, cada um envia ao outro seu número aleatório real.
  5. cada par verifica se o hash enviado pelo outro é realmente um hash do número aleatório. rejeitar a troca.
  6. o resultado do lançamento da moeda é o XOR do bit menos significativo de cada número, ou seja,

    (a & 1) ^ (b & 1)

Uma solução alternativa:

  1. Cada um dos dois pares decide entre eles decidir quem deve ir primeiro. Vamos chamá-los de A e B, apenas para serem originais.
  2. O ponto A gera seu número aleatório, cria um hash salgado e envia o hash para o ponto B.
  3. B gera seu número aleatório e o envia para A.
  4. A envia seu número aleatório para B.
  5. B verifica se o hash salgado é o hash do número recebido.
  6. o resultado do lançamento da moeda é o XOR do bit menos significativo de cada número, como acima.

Fiz essa pergunta no site de criptografia e estabeleci que é bastante seguro. Aparentemente, essa é uma variação do esquema de compromisso .

Michael Slade
fonte
11
Esse protocolo, conforme descrito, é vulnerável a um ataque de repetição, no qual um ponto apenas repete as mensagens do outro ponto para forçar o resultado a zero. Existem várias modificações simples que podem ser feitas para impedir esse ataque.
Ilmari Karonen
Esta versão deve estar bem.
Michael Slade
Como isso impede que um colega simplesmente escolha um número em vez de gerá-lo aleatoriamente?
Kylotan
@Kylotan: Não, mas enquanto pelo menos um dos colegas escolher aleatoriamente, o resultado será aleatório.
Ilmari Karonen
2
Um par não tem nada a ganhar com a escolha 0 o tempo todo, porque isso dá ao outro par a vantagem. O resultado final depende igualmente dos números contribuídos por ambos os pares.
Michael Slade
2

Acontece que não apenas os agentes adversários podem jogar moedas, mas os agentes adversários podem jogar pôquer .

Dito isto, tende a ser extremamente caro em termos de computação e bastante difícil de acertar. Provavelmente não vale a pena o esforço de implementação. Veja quantos protocolos multiplayer são hilariamente vulneráveis ​​a um servidor mal-intencionado (a saber: todos eles que eu conheço) e quão populares eles ainda são, e isso simplesmente não parece um uso prático do tempo.

StarCraft II é um bom exemplo. É um jogo em que o escotismo é fundamental, e saber o que o inimigo está fazendo pode dar uma vantagem fenomenal, e prêmios de cinco dígitos ou mais regularmente se baseiam nos resultados. . . e, no entanto, ambos os computadores têm todo o estado do jogo armazenado o tempo todo! É trivial escrever um programa que permita assistir diretamente ao oponente e obter uma grande vantagem sobre ele.

Acontece que nenhum dos concorrentes sérios usa esses programas. É muito fácil de detectar ("ei, Jim, como você sempre sabe o que estou construindo no instante em que estou construindo?") E simplesmente não vale a pena.

Dito isto, se você quiser obter mais informações, deverá analisar detalhadamente a criptografia - isso não está realmente no domínio do desenvolvimento de jogos.

ZorbaTHut
fonte