สำรับไพ่ที่ยุติธรรมที่พิสูจน์ได้ซึ่งลูกค้าและเซิร์ฟเวอร์ใช้

สมมติว่าเซิร์ฟเวอร์เล่นเกมแบล็คแจ็คกับลูกค้า และไพ่จะถูกสับและแจกโดยเซิร์ฟเวอร์ การสับไพ่เองอาจหรือไม่ยุติธรรมก็ได้ แต่สิ่งที่ต้องแสดงให้เห็นก็คือไพ่ที่แจกจะไม่ถูกเปลี่ยนแปลงในระหว่างการเล่นเกม กล่าวคือ: หลังจากเริ่มมือ ไพ่ในสำรับไม่ได้แอบมี การสั่งซื้อเปลี่ยนแปลงโดยเซิร์ฟเวอร์

ฉันกำลังคิดวิธีแก้ปัญหาต่อไปนี้โดยใช้การเข้ารหัสและต้องการได้รับข้อเสนอแนะว่าระบบการผลิตจะยอมรับได้หรือไม่ ถ้าไม่ใช่ เพราะเหตุใด:

ขั้นตอนที่ 1) เซิร์ฟเวอร์จะสับสำรับไพ่อย่างลับๆ โดยเรียงลำดับดังนี้ (เราไม่ใส่ไพ่เพื่อความง่าย): [3, 9, 2, ..., A]

จากนั้นจะสร้างข้อความต่อไปนี้ M:
M = "สับไพ่: [3, 9, 2, ..., A] เลขสุ่ม: A96A...QT3"

หมายเลขสุ่มคือหมายเลขสุ่มที่เซิร์ฟเวอร์สร้างขึ้นภายในและเก็บเป็นความลับจนกว่าเกมจะจบลง ความยาวจะยาวพอที่จะป้องกันไม่ให้แฮชถูกแฮ็กโดยไคลเอนต์โดยใช้กำลังเดรัจฉาน (สมมติว่ามีความยาว 512 อักขระ)

ตอนนี้เซิร์ฟเวอร์จะแฮช M โดยใช้ sha-256 หรืออัลกอริธึมการแฮชที่เชื่อถือได้อื่นๆ เช่น: hash(M)

ขั้นตอนที่ 2) ก่อนเริ่มเกม เซิร์ฟเวอร์จะส่งแฮช (M) นี้ไปยังไคลเอนต์ ซึ่งไคลเอ็นต์เก็บไว้ ลูกค้าไม่มีทางรู้ M จากสิ่งที่ฉันรวบรวมได้

ขั้นตอนที่ 3) เกมเริ่มต้นขึ้น ไพ่จะถูกแจกตามลำดับการสับ ผู้เล่นทำการตัดสินใจ และเกมจะจบลงในที่สุด

ขั้นตอนที่ 4) ลูกค้าต้องการทราบว่าเกมมีความยุติธรรม กล่าวคือ เซิร์ฟเวอร์ไม่ได้โกงโดยการเปลี่ยนไพ่ระหว่างมือ ขณะนี้เซิร์ฟเวอร์ส่งข้อความ "M" ไปยังไคลเอนต์ในรูปแบบข้อความธรรมดาเพื่อแสดงสิ่งนี้

ขั้นตอนที่ 5) ไคลเอนต์เรียกใช้แฮช (M) และดูว่าตรงกับแฮช (M) ที่ได้รับในขั้นตอนที่ 1

นี่เป็นวิธีที่ยุติธรรมหรือไม่ในการพิสูจน์ว่าเกมมีความยุติธรรม โดยที่ไคลเอนต์หรือเซิร์ฟเวอร์ไม่สามารถโกงได้ ยกเว้นความเป็นไปได้ที่การสับเปลี่ยนนั้นไม่ได้เป็นการสุ่ม หากเซิร์ฟเวอร์ต้องเปลี่ยนไพ่จากการสับไพ่ดั้งเดิมในระหว่างมือ ลูกค้าจะเห็นสิ่งนี้ในขั้นตอนที่ 5 (การจัดลำดับจะแตกต่างอย่างชัดเจนกับลูกค้า หรือแฮชของข้อความที่ส่งในขั้นตอนที่ 4 จะต่างกับที่ส่งมาในขั้นตอนที่ 2) นอกจากนี้ แฮชเดียวจะถูกส่งต่อมือ ดังนั้นเซิร์ฟเวอร์จึงไม่สามารถสร้างแฮชจำนวนมากและส่งแยกกัน จากนั้นเลือกแฮชที่ดีที่สุดระหว่างมือ

เพื่อขยาย คำตอบของ knaccเป็นไปได้ที่จะใช้แผนการผูกมัดเพื่อพิสูจน์ (จนถึงจุดหนึ่ง) ว่าเซิร์ฟเวอร์ไม่ได้โกงระหว่างการสุ่ม เช่น แบบนี้:

1. เซิร์ฟเวอร์เลือกหมายเลข 128 บิตแบบสุ่ม $x$ และปัจจัยที่ทำให้ไม่เห็น 128 บิต $r_x$และส่งความมุ่งมั่น $c_x = H(x \,||\, r_x)$ ให้กับลูกค้า
2. ลูกค้าเลือกหมายเลข 128 บิตแบบสุ่ม $y$ และส่งไปยังเซิร์ฟเวอร์ (ไม่จำเป็นต้องมีข้อผูกมัดที่นี่)
3. แฮชเซิร์ฟเวอร์ $x$ และ $y$ ร่วมกันเพื่อรับเมล็ดพันธุ์ 128 บิต $s = H(x \,||\, y)$.
4. เซิร์ฟเวอร์ใช้ $s$ เป็นตัวตั้งต้นของ PRNG ที่กำหนดขึ้น และใช้เอาต์พุต PRNG เพื่อสับไพ่ตามกำหนด
5. เกมนี้เล่นกับเด็คสับ
6. ในตอนท้ายของเกมเซิร์ฟเวอร์จะเปิดเผย $x$ และ $r_x$ทำให้ไคลเอนต์สามารถตรวจสอบได้ว่าเด็คถูกสับอย่างถูกต้อง (และไม่ถูกแก้ไขหลังจากสับแล้ว)

โปรดทราบว่าเซิร์ฟเวอร์ สามารถ ยังคงโกงตามแฟชั่นโดยการตรวจสอบสำรับที่สับหลังจากขั้นตอนที่ 4 และยกเลิกเกม (เช่นแสร้งทำเป็นว่าการเชื่อมต่อหลุด) หากไม่ชอบเด็ค ดังนั้นไคลเอนต์ควรสงสัยเซิร์ฟเวอร์ที่หยุดการเชื่อมต่อระหว่างขั้นตอนที่ 2 และ 5 บ่อยครั้ง หรือแม้กระทั่งระหว่างเกมในขั้นตอนที่ 5 ตามหลักแล้ว ควรมีวิธีที่ไคลเอ็นต์สามารถขอให้เซิร์ฟเวอร์ดำเนินการต่อเกมที่ถูกขัดจังหวะ ณ จุดใดก็ได้ และลูกค้าควรจะเป็น มาก สงสัยเซิร์ฟเวอร์ที่ปฏิเสธที่จะทำเช่นนั้น

(การใช้กลไกการดำเนินการต่ออย่างปลอดภัยในลักษณะที่ใช้งานได้แม้ว่าเซิร์ฟเวอร์จะล่มและลืมสถานะเกมดูเหมือนจะทำได้ แต่อาจอยู่นอกขอบเขตของคำตอบนี้ ถามคำถามใหม่หากคุณสนใจ)

โปรดทราบว่าค่าที่ทำให้ไม่เห็น $r_x$ ไม่จำเป็นจริง ๆ ที่นี่ตั้งแต่ $x$ ตัวมันเองมีเอนโทรปีเพียงพอแล้วที่จะทำให้การบังคับอย่างดุร้ายเป็นไปไม่ได้ ในความเป็นจริงมันอาจจะปลอดภัยกว่าเล็กน้อยที่จะละเว้น $r_x$ และเพียงแค่ทำ $x$ ตัวเอง 256 แทนที่จะเป็น 128 บิตยาว

ความยาวบิตของ $y$ และ $s$ สามารถเพิ่มได้หากต้องการ 128 บิตเป็นเพียงขั้นต่ำที่ปลอดภัยและใช้งานได้จริง ไม่มีประโยชน์ที่จะทำ $s$ ยาวกว่าความยาวรวมกันของ $x$ และ $y$ กันก็ตาม