โพรโทคอลซิกมาและการระบุตัวตนแบบ Schnorr

โปรโตคอล Sigma มีข้อความ 3 ข้อความ: (1) การผูกมัด: ผู้พิสูจน์ส่งค่าผูกมัดของค่าสุ่ม (2) คำท้าทาย: ผู้ตรวจสอบส่งคำท้าทายแบบสุ่ม (3) คำตอบ: ผู้พิสูจน์ส่งคำตอบที่คำนวณจากคำท้าทายและความลับ ผู้ตรวจสอบจะยอมรับหรือปฏิเสธ

ผู้พิสูจน์รู้ความลับ x (กุญแจส่วนตัว) กุญแจสาธารณะ = g^x mod p (หรือจุด X = x*G บนเส้นโค้งวงรี) เป้าหมายคือพิสูจน์ว่ารู้ x โดยไม่เปิดเผย x นี่คือการพิสูจน์ความรู้เกี่ยวกับลอการิทึมไม่ต่อเนื่อง

(1) ผู้พิสูจน์เลือก r แบบสุ่ม แล้วส่งค่าผูกมัด R = r*G (2) ผู้ตรวจสอบส่งคำท้าทาย c (จำนวนเต็มแบบสุ่ม) (3) ผู้พิสูจน์ส่งคำตอบ s = r + c*x (4) ผู้ตรวจสอบตรวจสอบว่า s*G == R + c*X หากใช่ ก็ยอมรับ ผู้พิสูจน์รู้ x และสามารถคำนวณคำตอบ s ได้ก็ต่อเมื่อรู้ x

ความครบถ้วน: ผู้พิสูจน์ที่ซื่อสัตย์จะทำให้ s*G = r*G + c*x*G = R + c*X เป็นจริงเสมอ ความถูกต้อง: บันทึกการโต้ตอบสองรายการที่มี R เดียวกันแต่มีคำท้าทายต่างกัน c และ c' จะให้ค่า s และ s' ซึ่งสามารถใช้หา x = (s-s')/(c-c') ได้ ดังนั้นผู้โกงจึงไม่สามารถสร้างคำตอบที่ถูกต้องสองคำตอบสำหรับ R เดียวกัน

ตัวจำลอง (ไม่รู้ x): สุ่ม s และ c แล้วกำหนด R = s*G - c*X ชุดข้อมูล (R, c, s) นี้มีการแจกแจงเหมือนบันทึกการโต้ตอบที่ถูกต้อง ผู้ตรวจสอบไม่สามารถแยกแยะบันทึกการโต้ตอบจริงจากบันทึกที่จำลองขึ้นได้ ดังนั้น Schnorr จึงมีคุณสมบัติการไม่เปิดเผยความรู้ต่อผู้ตรวจสอบที่ซื่อสัตย์

ทำให้ Schnorr ไม่ต้องโต้ตอบ: แทนที่คำท้าทายของผู้ตรวจสอบด้วย c = Hash(R || message) ผู้พิสูจน์คำนวณ c เองแล้วส่งคำตอบ ผลลัพธ์คือการพิสูจน์ที่มีองค์ประกอบ 2 รายการ (R, s) ซึ่งทุกคนสามารถตรวจสอบได้ นี่คือรูปแบบลายเซ็น Schnorr

Sign(x, m): r ← สุ่ม; R = r*G; c = Hash(R||m); s = r + c*x ลายเซ็น = (R, s) ตรวจสอบ: s*G == R + Hash(R||m)*X มีขนาดกะทัดรัด (64 ไบต์สำหรับ P-256) ตรวจสอบเป็นชุดได้ และพิสูจน์ความปลอดภัยได้ใน ROM นำไปใช้ใน Bitcoin Taproot (BIP-340)

C = r*G + v*H โดย H เป็นตัวกำเนิดอิสระตัวที่สอง ใช้ผูกมัดค่า v ด้วยค่าสุ่ม r คุณสมบัติการผูกมัด: ไม่สามารถเปิดเผยให้เป็นค่า v อื่นได้ (ลอการิทึมไม่ต่อเนื่อง) คุณสมบัติการปกปิด: C มีการแจกแจงแบบสม่ำเสมอ ใช้ในการพิสูจน์ช่วงค่าที่อาศัย Schnorr และ Bulletproofs

พิสูจน์ว่ารู้ x1 AND x2 พร้อมกัน: เรียกใช้โปรโตคอล Schnorr สองชุดด้วยคำท้าทายเดียวกัน (แบ่งปันคำท้าทายผ่าน Fiat-Shamir) ผู้ตรวจสอบจะยอมรับก็ต่อเมื่อการพิสูจน์ย่อยทั้งสองรายการถูกต้อง ช่วยให้พิสูจน์ข้อความหลายรายการได้ภายในการโต้ตอบครั้งเดียว

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

ID แบบ Schnorr: หนังสือเดินทางอิเล็กทรอนิกส์ (โปรโตคอล PACE) ลายเซ็น Schnorr: Bitcoin Taproot, Monero (RingCT ใช้การพิสูจน์แบบ OR ของ Schnorr), Signal Protocol (การตกลงกุญแจ X3DH) การผูกมัดแบบ Pedersen: ธุรกรรมที่เป็นความลับ, Bulletproofs, การเข้ารหัสบันทึก Sapling ของ Zcash

ในโปรโตคอลการระบุตัวตนแบบ Schnorr ผู้ตรวจสอบตรวจสอบอะไรในขั้นตอนสุดท้าย?

โปรโตคอล Sigma: ผูกมัด-ท้าทาย-ตอบ Schnorr ใช้พิสูจน์ความรู้เกี่ยวกับลอการิทึมไม่ต่อเนื่อง Fiat-Shamir ทำให้ไม่ต้องโต้ตอบ (ลายเซ็น Schnorr) บทถัดไป: zk-SNARK สำหรับการพิสูจน์แบบไม่ต้องโต้ตอบที่กระชับ