È possibile implementare un gioco sicuro senza avere un arbitro affidabile?

1

N giocatori stanno giocando un informazione perfetta gioco (il tipo di gioco in cui tutti conoscono le mosse di tutti) facendo mosse per turno ( P1 , P2 , ... , Pn , P1 , ... , Pn , ... fino al termine del gioco). Il gioco ha regole specifiche per ogni giocatore (se un giocatore fa una mossa contro le regole - perde automaticamente) e può finire solo se uno dei giocatori vince. Sto cercando di capire se è possibile implementare un gioco sicuro senza avere un arbitro affidabile (di cui ci si può fidare). Con sicurezza intendo che nessuno dei giocatori sarebbe in grado di imbrogliare e di essere notificato.

Ecco alcuni dei miei pensieri al riguardo:

Se nessuno dei giocatori imbroglia, non dovrebbe fare nulla: i giocatori si limitano a muovere e alla fine il vincitore viene annunciato. Ma se i giocatori possono imbrogliare, ogni giocatore successivo può verificare che il giocatore precedente non ha ingannato (è un'informazione perfetta e le regole sono conosciute) e se il giocatore precedente ha ingannato - perderà subito dopo. Se i giocatori possono iniziare a cooperare l'uno con l'altro (il giocatore 1 ingannato e il giocatore 2 ha deciso di cooperare) ogni giocatore può verificare tutte le mosse precedenti e i giocatori che hanno tradito o cooperato perderanno.

Ma qui c'è un problema. Nulla impedisce a un giocatore successivo di dire che il giocatore precedente ha imbrogliato anche se non lo è. Naturalmente i prossimi giocatori possono controllare questo, ma se solo 2 giocatori sono in gioco non funzionerà.

D'altra parte è possibile avere un arbitro affidabile che verifica ogni mossa. Il giocatore 1 fa una mossa - la dà all'arbitro. Lo verifica e lo trasmette ad altri giocatori. E così via.

Quindi c'è un modo per fare un gioco sicuro senza l'arbitro?

P.S.

  • Se questo sembra troppo astratto, pensa a questo come a un gioco di scacchi. 2 giocatori, informazioni perfette, le regole sono le regole degli scacchi come muoversi, i giocatori possono imbrogliare facendo mossa illegale
  • Non sono proprio sicuro che questo sia un posto giusto. Ho esitato tra matematica , sicurezza e crittografia . Se ho torto, spostalo in un altro posto.
posta Salvador Dali 29.06.2014 - 05:59
fonte

2 risposte

3

Se tutti hanno una copia completa dello stato del gioco alla volta T e le mosse consentite possono essere dedotte rigorosamente dal conoscere lo stato del gioco, allora è possibile identificare l'imbroglio senza un arbitro, sebbene sia chi sta barando richiede che la maggior parte dei giocatori sia onesta.

Ognuno inizia il gioco con una copia completa dello stato del gioco (implicito in questo è un perfetto gioco di informazione), e fare una mossa implica trasmetterlo a tutti gli altri giocatori.

Reclutare la persona P1 ingannata non significa semplicemente dire agli altri giocatori che hanno imbrogliato. Invece, una rivendicazione di imbroglio sarebbe per il giocatore P2 per dire a tutti gli altri giocatori "Dato lo stato di gioco S , il giocatore P1 mi ha detto che hanno fatto sposta M , che è contro le regole ". Tutti possono verificare ciò confrontando S contro la loro idea di quale dovrebbe essere lo stato del gioco, confrontando M con la mossa ricevuta da P1 e verificando che M sia contro le regole.

A questo punto, il problema principale è distinguere l'imbroglio da P1 a mentire P2 .

Puoi eliminare la manomissione delle mosse facendo firmare crittograficamente ogni mossa dal giocatore che lo fa: se P2 ha affermato M ha una firma che non controlla , stanno mentendo (se P1 ha inviato una mossa con una firma che non ha controllato, P2 l'avrebbe respinta).

C'è un altro modo di barare, però: se P1 invia una serie coerente di mosse legali, ma le mosse inviate a P2 sono diverse dalle mosse inviate a tutti gli altri , può dare a P2 una falsa idea dello stato del gioco e indurli a fare una falsa dichiarazione di imbroglio. Se la maggioranza dei giocatori è onesta, questo può essere vanificato facendo confrontare tutti quelli che pensano siano stati fatti, ma se la maggioranza sta collaborando con P1 , possono mentire a P2 su quale movimento hanno appena ricevuto. In questo caso, non sono a conoscenza di alcun modo per impedirlo.

    
risposta data 29.06.2014 - 07:47
fonte
1

In breve, no, non puoi assolutamente vietare, o persino rilevare, barare il 100% delle volte, senza la presenza di una via di mezzo (un server imparziale). Il problema principale si presenta al cliente stesso. Il file binario potrebbe essere hackerato o modificato in un modo che sarebbe trasparente alla rete, consentendo in tal modo al cheat client di eseguire diversi atti maliziosamente. Dal momento che non c'è modo di verificare che un client non sia violato, ciò significa che tutti i tipi di scenari impossibili da rilevare potrebbero entrare in gioco.

Reclamo false false

Potrebbe tentare di fare false affermazioni di imbroglio nel tentativo di interrompere un turno perdente. In una partita di più di due, tutto ciò che deve accadere è avere un'affermazione che B ha imbrogliato a C, che potrebbe causare un consenso, costringendo B a smettere. Anche in una partita a due giocatori, il risultato sarebbe un loop cheat-counter-cheat, con il risultato che entrambi i client chiamano gli altri cheaters allo stesso tempo, forzando un draw o uno stato di gioco non valido.

AI Booster

Un client hacker potrebbe fornire una sorta di generatore di mosse AI assistito per aumentare le possibilità di vincita, prevedendo mosse di molte migliaia o milioni di mosse in anticipo, sfruttando tutti i tipi di algoritmi per aumentare le probabilità di vincita del giocatore. Questo è completamente inosservabile in un client cheat ben progettato, in quanto potrebbe impiegare timer di ritardo di ipotesi casuali o istruiti per dare l'apparenza del pensiero umano.

Forza stato di gioco non valido

Un cliente può falsificare quali mosse sono state effettivamente giocate, eventualmente forzare l'altra estremità in una posizione in cui non ha mosse legali e deve dichiararsi baro. Mentre questo sarebbe molto probabilmente evidente in un gioco ben noto come gli scacchi, un nuovo gioco con nuove regole a cui gli utenti non sono completamente a conoscenza potrebbe perdere alcune interazioni sottili, e il cliente potrebbe dipendere da altri giocatori che non hanno questa mossa. Potrebbe anche solo inviare mosse diverse a diversi client, tutti legali, fino a quando, a causa dello stato di gioco non valido, un altro client effettua una mossa non valida e viene dichiarato un imbroglione.

Difetti di exploit

Un client può sfruttare qualsiasi difetto nell'algoritmo "legal-checking" del motore di gioco. La maggior parte dei software di solito ha qualche bug in agguato, e qualsiasi bug di questo tipo può essere sfruttato per vincere una mossa cruciale o forzare una posizione perdente.

Clienti cooperativi

Due o più client su un singolo gioco potrebbero mantenere il proprio stato di gioco, mentre il client legittimo è escluso dallo stato di gioco effettivo. Questo potrebbe aiutare a sventare algoritmi richiesti a due bandiere per prevenire una singola affermazione falsa in una partita a più di due giocatori. Fintanto che i clienti cooperativi controllano almeno il 50% dello stato del gioco, non c'è davvero molto altro da fare per la situazione tranne che per il drop out.

Condizioni di gara

Un cliente modificato A potrebbe dire a B sulla mossa di C prima che C abbia la possibilità di fare quella mossa. Ciò sarebbe particolarmente vero se i client sono progettati per utilizzare un sistema stile token-ring, in cui il client passa lo stato di gioco al client successivo, specialmente se i client non solo verificano che un determinato stato di gioco sia valido, ma anche se il lo stato del gioco è valido rispetto allo stato del gioco precedente. L'unico modo per evitarlo sarebbe quello di assicurarsi che tutti i giocatori trasmettano il loro movimento su tutti gli altri nodi, quei nodi verificano in modo indipendente la mossa e l'origine del gioco proviene dal giocatore dal quale afferma di essere venuto.

IP Spoofing

Potrebbe essere possibile falsificare la mossa di un altro giocatore semplicemente spoofando il suo indirizzo IP. Ovviamente, questo non costituirà un problema per SSL, perché è progettato per impedire che tali comunicazioni si verifichino. Un protocollo di livello di trasporto debole potrebbe causare problemi.

    
risposta data 29.06.2014 - 17:42
fonte

Leggi altre domande sui tag