¿Es posible implementar un juego seguro sin tener un árbitro confiable?

1

Los jugadores N juegan un información perfecta (el tipo de juego en el que todos saben los movimientos de todos) haciendo movimientos. por turno ( P1 , P2 , ... , Pn , P1 , ... , Pn , ... hasta que el juego termine). El juego tiene reglas específicas para cada jugador (si un jugador hace un movimiento en contra de las reglas, pierde automáticamente) y puede terminar solo si uno de los jugadores gana. Estoy tratando de averiguar si es posible implementar un juego seguro sin tener un árbitro confiable (en quien se pueda confiar). Por seguro quiero decir que ninguno de los jugadores podría hacer trampa y pasar desapercibido.

Estos son algunos de mis pensamientos al respecto:

Si ninguno de los jugadores hace trampa, entonces no se debe hacer nada: los jugadores simplemente se mueven y al final se anuncia al ganador. Pero si los jugadores pueden hacer trampa, cada siguiente jugador puede verificar que el jugador anterior no haya hecho trampa (es información perfecta y se conocen las reglas) y si el jugador anterior hizo trampa, perderá justo después de esto. Si los jugadores pueden comenzar a cooperar entre sí (el jugador 1 engañó y el jugador 2 decidió cooperar), todos los jugadores pueden verificar todos los movimientos anteriores y los jugadores que engañaron o cooperaron perderán.

Pero aquí hay un problema. Nada impide que un próximo jugador diga que el jugador anterior hizo trampa, incluso si no lo está. Por supuesto, los siguientes jugadores pueden verificar esto, pero si solo hay 2 jugadores en el juego, no funcionará.

Por otro lado, es posible tener un árbitro confiable que verifique cada movimiento. El jugador 1 hace un movimiento - se lo da al árbitro. Lo verifica y lo transmite a otros jugadores. Y así sucesivamente.

Entonces, ¿hay una manera de hacer un juego seguro sin el árbitro?

P.S.

  • si esto suena demasiado abstracto, piensa en esto como un juego de ajedrez. 2 jugadores, información perfecta, las reglas son las reglas del ajedrez, cómo moverse, los jugadores pueden hacer trampa haciendo movimientos ilegales
  • No estoy realmente seguro de que este sea un lugar correcto. Dudé entre matemáticas , seguridad y criptografía . Si estoy equivocado, muévalo a otro lugar.
pregunta Salvador Dali 29.06.2014 - 05:59
fuente

2 respuestas

3

Si todos tienen una copia completa del estado del juego en el momento T , y los movimientos permitidos pueden deducirse estrictamente de conocer el estado del juego, entonces es posible identificar las trampas sin un árbitro, aunque quién está haciendo trampa requiere que la mayoría de los jugadores sean honestos.

Todo el mundo comienza el juego con una copia completa del estado del juego (implícito en que es un juego de información perfecto), y hacer un movimiento implica transmitirlo a todos los demás jugadores.

La persona reclamante P1 engañada no es simplemente una cuestión de decirle a los otros jugadores que hicieron trampa. En cambio, una reclamación de engaño sería que el jugador P2 le diga a todos los demás jugadores "Dado el estado del juego S , el jugador P1 me dijo que hicieron Mueve M , lo que está en contra de las reglas ". Todos pueden verificar esto comparando S con su idea del estado del juego, comparando M con el movimiento que recibieron de P1 , y verificando que M esté en contra de las reglas.

En este punto, el problema principal es distinguir el engaño por P1 de mentir por P2 .

Puede eliminar la manipulación de movimientos haciendo que cada movimiento esté firmado criptográficamente por el jugador que lo realiza: si P2 se reclama, M tiene una firma que no se comprueba , están mintiendo (si P1 enviara un movimiento con una firma que no se verificó, P2 lo habría rechazado).

Sin embargo,

hay otra forma de hacer trampa: si P1 envía una serie consistente de movimientos legales, pero los movimientos enviados a P2 son diferentes de los movimientos enviados a todos los demás , puede dar a P2 una falsa idea del estado del juego e inducirlos a hacer una falsa afirmación de engaño. Si la mayoría de los jugadores son honestos, esto puede frustrarse al hacer que todos comparen el movimiento que creen que se acaba de hacer, pero si la mayoría está colaborando con P1 , pueden mentir a P2 sobre qué movimiento acaban de recibir. En este caso, no conozco ninguna forma de prevenirlo.

    
respondido por el Mark 29.06.2014 - 07:47
fuente
1

En resumen, no, no puedes prohibir absolutamente, o incluso detectar, hacer trampa el 100% del tiempo, sin la presencia de un término medio (un servidor imparcial). El principal problema se reduce al propio cliente. El binario podría ser hackeado o modificado de una manera que sería transparente a la red, permitiendo así que el cliente tramposo realice varios actos maliciosamente. Dado que no hay forma de verificar que un cliente no sea pirateado, eso significa que pueden entrar en juego todo tipo de escenarios imposibles de detectar.

Reclamo de engaño falso

Podría tratar de hacer declaraciones falsas de engaño en un intento de abortar una ronda perdida. En un juego de más de dos, todo lo que tiene que suceder es tener una afirmación de que B engañó a C, lo que podría causar un consenso, lo que obligó a B a renunciar. Incluso en un juego de dos jugadores, el resultado sería un bucle de trampa-contra-trampa, lo que resultaría en que ambos clientes llamen a los otros tramposos al mismo tiempo, forzando un empate o un estado de juego no válido.

AI Booster

Un cliente pirateado podría proporcionar algún tipo de generador de movimiento asistido por IA para aumentar las posibilidades de ganar, pronosticando muchos miles o millones de movimientos por adelantado, aprovechando todo tipo de algoritmos para mejorar las probabilidades de ganar del jugador. Esto es completamente indetectable en un cliente de trucos bien diseñado, ya que podría emplear temporizadores de retardo de suposición aleatorios o informados para dar la apariencia de pensamiento humano.

Forzar estado de juego no válido

Un cliente podría falsificar qué movimientos se estaban jugando realmente, posiblemente forzando al otro extremo a una posición en la que no tiene movimientos legales y debe declararse tramposo. Si bien esto es muy probable que sea obvio en un juego conocido como el ajedrez, un juego nuevo con nuevas reglas con las que los usuarios no están completamente familiarizados podría pasar por alto alguna interacción sutil, y el cliente podría depender de la falta de movimientos de otros jugadores. También podría enviar diferentes movimientos a diferentes clientes, todos ellos legales, hasta que, debido al estado de juego no válido, otro cliente realice un movimiento no válido y se declare tramposo.

Fallas de explotación

Un cliente podría explotar cualquier falla en el algoritmo de "verificación legal" del motor del juego. La mayoría del software suele tener algunos errores, y cualquier error de este tipo podría explotarse para ganar un movimiento crucial o forzar una posición perdedora.

Clientes cooperativos

Dos o más clientes en un solo juego podrían mantener su propio estado de juego, mientras que el cliente legítimo se queda fuera del estado real del juego. Esto podría ayudar a frustrar los algoritmos requeridos por dos banderas para evitar un solo reclamo falso en un juego de más de dos jugadores. Mientras los clientes de la cooperativa controlen al menos el 50% del estado del juego, realmente no hay mucho que nadie más pueda hacer con respecto a la situación, excepto abandonar.

Condiciones de carrera

Un cliente modificado A podría decirle a B sobre el movimiento de C antes de que C tenga la oportunidad de hacer ese movimiento. Esto sería especialmente cierto si los clientes están diseñados para usar un sistema de estilo token-ring, donde el cliente pasa el estado del juego al siguiente cliente, especialmente si los clientes no solo verifican que un estado determinado del juego sea válido, sino también si el El estado del juego es válido en comparación con el estado del juego anterior. La única forma de evitar esto sería asegurarse de que todos los jugadores transmitan su movimiento a todos los demás nodos, esos nodos verifican de forma independiente el movimiento y el origen de la jugada proviene del jugador del que dice haber venido.

IP Spoofing

Podría ser posible falsificar el movimiento de otro jugador simplemente falsificando su dirección IP. Por supuesto, esto no será un problema para SSL, porque está diseñado para evitar que se produzcan dichas comunicaciones. Un protocolo de capa de transporte débil podría causar problemas.

    
respondido por el phyrfox 29.06.2014 - 17:42
fuente

Lea otras preguntas en las etiquetas