Bisakah agen musuh melempar koin?

9

Saya sedang berpikir tentang permainan peer-to-peer dengan mempertimbangkan koin sederhana permainan melempar.

Anda membuka versi P2PCoinFlipping Beta 2.3 Anda dan menampilkan daftar server nama pemain. Setelah memilih server terdekat, papan skor pemain paling beruntung muncul. Anda memilih pemain peringkat tertinggi dan permainan dimulai. Sejak Anda memulai pertempuran, pemain lawan memilih sisi koin, kepala, dan Anda diberikan ekor. Sebuah grafik kecil yang bagus muncul menampilkan koin jatuh akhirnya mendarat di kepala. Sayang sekali, kamu kalah.

Tapi bagaimana Anda tahu hasilnya adil?

Jika hasilnya dipilih di komputer Anda, Anda dapat mengedit program untuk memilih untuk menang dan hal yang sama berlaku untuk lawan. Gim ini tidak deterministik sehingga Anda tidak bisa memvalidasi hasilnya.

Apakah mungkin untuk memiliki beberapa agen permusuhan independen yang setuju pada peristiwa yang tidak deterministik?

AnnanFay
sumber
Meskipun tidak menjawab pertanyaan, ini sebabnya multiplayer berbasis server bagus - biarkan server menjadi arbiter. Ide yang menarik adalah mengandalkan layanan pihak ketiga sebagai sirip koin. Bisakah seseorang misalnya menggunakan generator GUID online (seperti guidgenerator.com ) sebagai dasar untuk suatu sistem?
Tim Holt

Jawaban:

6

Prosedur ini akan melakukan pekerjaan:

  1. masing-masing dari dua rekan menghasilkan angka acak.
  2. setiap rekan membuat hash asin dari nomornya dan mengirimkannya ke rekan lainnya.
  3. salah satu rekan menolak permintaan jika mendapat hash yang sama dengan yang dikirim.
  4. setelah kedua rekan mengkonfirmasi penerimaan hash masing-masing, masing-masing kemudian mengirimkan yang lain nomor acak yang sebenarnya.
  5. masing-masing rekan memverifikasi bahwa hash yang dikirim oleh yang lain sebenarnya adalah hash dari nomor acak. tolak pertukaran.
  6. hasil flip koin adalah XOR dari bit paling signifikan dari setiap angka, yaitu

    (a & 1) ^ (b & 1)

Solusi alternatif:

  1. Masing-masing dari dua rekan memutuskan di antara mereka untuk memutuskan siapa yang harus pergi dulu. Sebut mereka A dan B, hanya untuk menjadi asli.
  2. Peer A menghasilkan nomor acaknya, membuat hash asin darinya dan mengirimkan hash ke rekan B.
  3. B menghasilkan nomor acaknya dan mengirimkannya ke A.
  4. A mengirimkan nomor acaknya ke B.
  5. B memverifikasi bahwa hash asin adalah hash dari nomor yang diterimanya.
  6. hasil dari flip koin adalah XOR dari bit paling signifikan dari setiap angka, seperti di atas.

Saya telah mengajukan pertanyaan ini di situs kriptografi dan menetapkan bahwa ini cukup aman. Rupanya ini adalah variasi pada skema Komitmen .

Michael Slade
sumber
1
Protokol ini seperti dijelaskan rentan terhadap serangan replay, di mana satu rekan hanya menggemakan kembali pesan rekan lain untuk memaksa hasilnya menjadi 0. Namun, ada beberapa modifikasi sederhana yang dapat dilakukan untuk mencegah serangan ini.
Ilmari Karonen
Versi ini harus baik-baik saja.
Michael Slade
Bagaimana ini menghentikan rekan hanya memilih nomor daripada menghasilkannya secara acak?
Kylotan
@ Silyl: Tidak, tapi selama setidaknya salah satu dari rekan-rekan memilih secara acak, hasilnya akan acak.
Ilmari Karonen
2
Seorang rekan tidak mendapatkan apa-apa bahkan dari memilih 0 sepanjang waktu, karena dengan demikian ini memberikan keuntungan kepada rekan kerja lainnya. Hasil akhir tergantung sama pada jumlah yang disumbangkan oleh kedua rekan.
Michael Slade
2

Ternyata agen lawan tidak hanya bisa melempar koin, tetapi agen musuh juga bisa bermain poker .

Yang mengatakan, itu cenderung sangat mahal secara komputasi, dan cukup sulit untuk mendapatkan yang benar. Mungkin tidak sebanding dengan upaya implementasi. Lihatlah berapa banyak protokol multi-pemain yang sangat rentan terhadap server jahat (yaitu: semua yang saya sadari), dan seberapa populernya protokol tersebut, dan sepertinya itu bukan penggunaan waktu yang praktis.

StarCraft II adalah contoh yang bagus. Ini adalah permainan di mana kepramukaan sangat penting, dan mengetahui apa yang dilakukan musuh dapat memberikan keuntungan yang fenomenal, dan hadiah lima digit atau lebih besar secara teratur bergantung pada hasilnya. . . namun kedua komputer memiliki seluruh kondisi permainan yang disimpan setiap saat! Itu sepele untuk menulis sebuah program yang memungkinkan Anda menonton lawan secara langsung dan mendapatkan kaki besar pada mereka.

Ternyata, tidak ada pesaing serius yang menggunakan program ini. Terlalu mudah dideteksi ("hei, Jim, bagaimana Anda selalu tahu apa yang saya bangun saat saya membangunnya?") Dan tidak sepadan dengan masalahnya.

Yang mengatakan, jika Anda ingin info lebih lanjut, Anda akan ingin melihat ke dalam kriptografi secara detail - ini tidak benar-benar dalam bidang pengembangan game.

ZorbaTHut
sumber