สัญชาตญาณ ZKP: ถ้ำอาลีบาบา

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

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

ผู้พิสูจน์ที่โกง (ซึ่งไม่รู้ความลับ) ไม่สามารถโน้มน้าวผู้ตรวจสอบได้ ยกเว้นด้วยความน่าจะเป็นที่เล็กน้อยมาก การโต้ตอบแต่ละรอบจะลดความน่าจะเป็นในการโกงลง หลังจาก k รอบ ผู้โกงจะมีโอกาสสำเร็จไม่เกิน 2^{-k}

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

ถ้ำแห่งหนึ่งมีทางเดินเป็นวงแหวนและมีประตูวิเศษอยู่ตรงกลาง ผู้พิสูจน์ (Alice) อ้างว่าตนรู้รหัสผ่าน ผู้ตรวจสอบ (Bob) รออยู่ด้านนอก Alice เข้าไปแล้วเลือกไปทางซ้ายหรือขวา Bob ตะโกนบอกว่าต้องการให้เธอออกทางด้านใด หาก Alice รู้รหัสผ่าน เธอจะออกมาได้ถูกด้านเสมอ ความน่าจะเป็นที่ผู้โกงจะตอบถูกในแต่ละรอบคือ 1/2

หลังจาก 20 รอบ ผู้โกงจะสำเร็จด้วยความน่าจะเป็น 2^{-20} ≈ 1 ในล้าน ส่วน Alice ซึ่งรู้รหัสผ่านจะสำเร็จทุกครั้ง Bob ไม่เคยเรียนรู้รหัสผ่าน เขาเพียงเห็น Alice ออกมาจากด้านที่ร้องขอ นี่คือการไม่เปิดเผยความรู้

ZKP แบบโต้ตอบต้องมีการสื่อสารไปกลับระหว่างผู้พิสูจน์กับผู้ตรวจสอบ ส่วน ZKP แบบไม่โต้ตอบ (NIZK) ใช้การแปลง Fiat-Shamir โดยแทนที่ความท้าทายสุ่มจากผู้ตรวจสอบด้วยแฮชของคำมั่นสัญญา (แฮช = ออราเคิลสุ่ม) ผลลัพธ์คือสตริงการพิสูจน์เดียวที่ทุกคนสามารถตรวจสอบได้

ZKP จะเป็นการพิสูจน์ความรู้ (PoK) หากกลยุทธ์ของผู้พิสูจน์แสดงเป็นนัยว่าสามารถดึงความลับออกมาได้ แนวคิดนี้เข้มแข็งกว่าการพิสูจน์เพียงว่าข้อความหนึ่งเป็นจริง ลายเซ็น ECDSA และ Schnorr คือการพิสูจน์ความรู้คีย์ส่วนตัวแบบไม่โต้ตอบ

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

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

โปรโตคอลถ้ำประกอบด้วย 3 ขั้นตอน: การผูกมัด → คำท้าทาย → คำตอบ โดยเรียกอย่างเป็นทางการว่าโปรโตคอล Sigma ZKP ที่ใช้งานจริงส่วนใหญ่ เช่น Schnorr, Pedersen และ Fiat-Shamir เป็นโปรโตคอล Sigma หรือเป็นการประกอบโปรโตคอลเหล่านี้เข้าด้วยกัน ชื่อนี้มาจากรูปร่าง Σ ของแผนภาพลำดับการส่งข้อความ

หลังจากโต้ตอบกี่รอบในโปรโตคอลถ้ำของ Ali Baba ความน่าจะเป็นที่ผู้โกงจะประสบความสำเร็จจึงต่ำกว่า 1/1000?

ZKP ใช้พิสูจน์ว่ารู้ความลับโดยไม่เปิดเผยความลับนั้น คุณสมบัติ 3 ประการ ได้แก่ ความครบถ้วน ความถูกต้อง และการไม่เปิดเผยความรู้ โปรโตคอลถ้ำของ Ali Baba แสดงให้เห็น ZKP แบบโต้ตอบ บทถัดไป: โปรโตคอล Sigma และการระบุตัวตนแบบ Schnorr