การอ่าน เหตุใด Zk-SNARK จึงเป็นอาร์กิวเมนต์แห่งความรู้หากมีตัวแยกความรู้อยู่ ฉันรู้สึกสับสนกับคำสั่งแรกของ OP:
จากสิ่งที่ฉันรู้ การพิสูจน์การมีอยู่ของ Knowledge Extractor หมายถึงความสมบูรณ์
คำตอบมุ่งเน้นไปที่ความสมบูรณ์ไม่จำเป็นต้องสมบูรณ์แบบ แต่ดูเหมือนว่าเป็นการยืนยันโดยนัยโดยนัยโดยตัวแยก
ก่อนอื่น ให้ฉันระบุว่าเมื่อฉันอ่าน "ความสมบูรณ์" ฉันคิดว่าเป็นคุณสมบัติของ IP ที่ระบุว่าไม่มีกลยุทธ์ Prover ใดที่สามารถโน้มน้าวผู้ตรวจสอบสัญลักษณ์ที่ไม่ใช่ของภาษาด้วยความน่าจะเป็นมากกว่าเล็กน้อย... ซึ่งดูแตกต่างไปจากเดิมอย่างสิ้นเชิง "วัตถุ" มากกว่าเครื่องสกัด "ทำให้" พยานรั่วไหล ดังนั้นมันจึงเป็นเรื่องยากสำหรับฉันที่จะเข้าใจอย่างน้อยที่สุดก็ไร้เดียงสาเกี่ยวกับความหมายโดยนัยนั้น
อย่างไรก็ตามฉันเริ่มเชื่อเพราะแหล่งข้อมูลที่ฉันพบเช่น:
[...] คุณสมบัติความสมบูรณ์ถูกแทนที่ด้วยคุณสมบัติการสกัดความรู้ [...]
เมื่อพูดถึงการพิสูจน์ความถูกต้องของการพิสูจน์ความรู้ เรามีวิธีการที่เป็นทางการที่ดีมาก เช่นเดียวกับ Simulator ที่เราพูดถึงข้างต้น เราจำเป็นต้องแสดงให้เห็นถึงการมีอยู่ของอัลกอริทึมพิเศษ อัลกอริทึมนี้เรียกว่าตัวแยกความรู้ และทำสิ่งที่กล่าวอ้างทุกประการ ตัวแยกความรู้ (หรือเรียกสั้น ๆ ว่า “ตัวแยกข้อมูล”) คือตัวตรวจสอบประเภทพิเศษที่โต้ตอบกับผู้ตรวจสอบ และ “หากผู้ตรวจสอบพิสูจน์ได้สำเร็จ” ตัวแยกข้อมูลควรจะสามารถดึงข้อมูล ความลับดั้งเดิมของ Proverâ และนี่ตอบคำถามของเราด้านบน ในการพิสูจน์ความถูกต้องสำหรับการพิสูจน์ความรู้ เราต้องแสดงว่ามี Extractor อยู่สำหรับ Prover ทุกตัวที่เป็นไปได้
อย่างไรก็ตามในวรรค 4.5 "แล้วความสมบูรณ์ล่ะ" ของ ในการกำหนดหลักฐานความรู้ โดยที่ Bellare และ Goldreich จัดการกับสูตร PoK เมื่อเทียบกับสูตรก่อนหน้า (https://www.wisdom.weizmann.ac.il/~oded/PS/pok.ps) ฉันได้พบคำเหล่านี้:
เราทราบว่าคำนิยามของเราไม่มีข้อกำหนดสำหรับกรณีนี้ $x$ ไม่ได้อยู่ใน $L_R$. โดยเฉพาะอย่างยิ่ง ความสมบูรณ์ (กล่าวคือ การผูกมัดกับความสามารถของผู้พิสูจน์ในการชักนำให้ผู้ตรวจสอบยอมรับ $x$ ไม่ได้อยู่ใน $L_R$) ไม่จำเป็นต้องใช้. ดังนั้นจึงเป็นตัวตรวจสอบความรู้สำหรับ $R$ ไม่จำเป็นต้องกำหนดหลักฐานเชิงโต้ตอบของการเป็นสมาชิกใน $L_R$. สิ่งนี้ตรงกันข้ามกับคำจำกัดความก่อนหน้านี้ พวกเขามีเงื่อนไข "ความถูกต้อง" หมายถึงสภาพความสมบูรณ์เพื่อให้หลังเสมอ เรารู้สึกว่าการ "แยก" ความสมบูรณ์ออกจากความถูกต้องนั้นสมเหตุสมผลทั้งในเชิงแนวคิดและในแง่ของการใช้งานบางอย่าง
ยังไงก็ตาม มันเป็นมุมมองเดียวกันกับ "รากฐานของการเข้ารหัส" ของ Golderich ที่มีชื่อเสียงในหัวข้อ 4.7
ฉันสงสัยอีกครั้งเกี่ยวกับ: ตัวแยกความรู้ $=>$ ความสมบูรณ์
ใครช่วยระบุหลักฐานโดยนัยอย่างชัดเจนหรืออย่างน้อยก็บอกใบ้เกี่ยวกับเรื่องนี้ให้ฉันทราบ
หรือบางทีการมีอยู่ของ Knowledge Extractor ไม่ทางใดก็ทางหนึ่งโดยตัวมันเองหลีกเลี่ยงไม่ให้ผู้ตรวจสอบเชื่อใน "พยาน" ที่ผู้พิสูจน์ไม่รู้จักจริงๆ ดังนั้นจึงอาจถูกพิจารณาว่าเป็น "คุณสมบัติความสมบูรณ์" แม้ว่าจะมีลักษณะที่แตกต่างกันก็ตาม คน? (มุมมองนี้ดูเหมือนจะได้รับการยืนยันโดย Geoffroy Couteau ในการแลกเปลี่ยนคำถาม / คำตอบที่อ้างถึงเดิมเมื่อเขาเขียน:
ใช่ มีหลายมิติในรสชาติของความสมบูรณ์: ไม่ว่าคุณจะมี "ความสมบูรณ์ของการเป็นสมาชิก" หรือ "ความรู้ที่ถูกต้อง" ก็เป็นหนึ่งเดียว (ฉันมักจะพูดว่า 'ความสามารถในการสกัดความรู้' ในเอกสารของฉันเพื่อแยกความแตกต่างจากความสมบูรณ์ตามปกติ)
อย่างไรก็ตามหากเป็นกรณีนี้ฉันคาดหวังให้เขาแก้ไข "นัย" โดย OP)
ขออภัยที่ใช้คำไม่สุภาพ ฉันหวังว่าจะได้อธิบายข้อสงสัยของฉันในแบบที่เข้าใจได้
ความสามารถในการสกัดความรู้เป็นคุณสมบัติที่แข็งแกร่งกว่าความสมบูรณ์ ด้านล่างฉันจะร่างว่าทำไม ความสามารถในการสกัดความรู้ที่ไม่มีเงื่อนไข หมายถึง ความสมบูรณ์ทางสถิติ. ในแง่ที่ไม่เป็นทางการ ความสมบูรณ์ทางสถิติระบุว่า:
"หากข้อความไม่ถูกต้อง ผู้พิสูจน์ที่ประสงค์ร้ายจะมีโอกาสเล็กน้อยในการสร้างหลักฐานที่ยอมรับได้"
ในทางกลับกัน KE กล่าวว่า:
(*) "ใช้อัลกอริธึมการพิสูจน์ใดๆ (ที่อาจเป็นอันตราย) ที่สร้างการพิสูจน์ที่ยอมรับโดยมีความน่าจะเป็นที่ไม่สำคัญ จากนั้นจะมีตัวแยก (เวลาโพลิโนเมียลที่คาดไว้) ที่โต้ตอบกับผู้พิสูจน์นี้และกู้คืนพยาน ข้อความนี้เป็นความจริง".
ตามสูตรข้างต้น ควรค่อนข้างชัดเจนว่า KE หมายถึงความถูกต้อง: หาก KE รับประกันว่าจะหาพยานได้ว่าข้อความนั้นเป็นความจริง หมายความว่าข้อความนั้นโดยเฉพาะอย่างยิ่ง เป็น จริง. ในอีกแง่หนึ่ง (*) หมายถึง:
"หากมีอัลกอริธึมการพิสูจน์ (ที่อาจเป็นอันตราย) ที่สร้างการพิสูจน์ที่ยอมรับได้ด้วยความน่าจะเป็นที่ไม่สำคัญ ข้อความนั้นก็จำเป็นต้องเป็นความจริง"
การใช้คำตรงกันข้ามให้: "หากข้อความไม่ถูกต้อง ไม่มีอัลกอริธึมการพิสูจน์ใดที่สามารถสร้างหลักฐานที่ยอมรับได้ด้วยความน่าจะเป็นที่ไม่สำคัญ"
ซึ่งก็คือ ทางสถิติ ความสมบูรณ์ โปรดทราบว่าสิ่งนี้ไม่ได้ให้คุณ สมบูรณ์แบบ ความสมบูรณ์: สำหรับสิ่งนี้ คุณต้องมีรูปแบบการสกัดความรู้ที่ "แข็งแกร่งเป็นพิเศษ" ซึ่งจะรับประกันการสกัดพยานจากผู้พิสูจน์ใดๆ (ที่อาจเป็นอันตราย) ซึ่งแสดงหลักฐานที่ยอมรับด้วย ความน่าจะเป็นใดๆ $p>0$.
โปรดทราบว่ายังมีสถานการณ์ที่เราสามารถพิสูจน์ได้เฉพาะรูปแบบการคำนวณของ KE เช่น "เราสามารถแยกพยานจากเครื่องพิสูจน์ที่ประสบความสำเร็จที่มีขอบเขตพหุนามนี้ หรือเราสามารถใช้เครื่องพิสูจน์เพื่อแก้ปัญหาที่ยากนี้" ในกรณีนี้ KE การคำนวณหมายถึงความสมบูรณ์ในการคำนวณ
ขอขอบคุณ! ตอนนี้ร่างของคุณช่วยให้ฉันไม่หลงทางในรายละเอียดที่เป็นทางการของ FoC 4.7 อีกต่อไป และทำให้ฉันเข้าใจด้วย เมื่อความรู้มั่นคงหมายถึงความสมบูรณ์ พบในขณะเดียวกันและเป็นสิ่งที่ควรค่าแก่การอ้างถึงที่นี่ ฉันเดาว่า (นั่นคือเหตุผลที่ฉันเขียนสิ่งนี้เป็นคำตอบเช่นกัน)
ฉันคิดว่าความสับสนของฉันเกิดขึ้นก่อนอื่นโดยที่ฉันไม่ได้เป็นผู้เชี่ยวชาญในสาขานี้ ;-) และต่อมาจาก Goldreich กระตือรือร้นที่จะไม่กำหนดความถูกต้องของ KE สำหรับข้อความเท็จและการหักเงินต่อไปนี้เกี่ยวกับการไม่สามารถจัดการกับข้อความเท็จ กรณี (แม้แต่ หากร่างของคุณทำให้ฉันคิดว่า แม้ว่าไม่ได้กำหนดไว้ในกรณีนั้น ดูเหมือนว่าเป็นไปไม่ได้ที่ KE จะสามารถคืนพยานที่ไม่มีอยู่จริงของข้อความเท็จได้ ดังนั้น KE การส่งคืนพยานจึงแสดงว่าข้อความนั้นเป็นความจริง ดังนั้นลอจิกเชนของคุณจึงดูเหมือนใช้ได้ภายใต้ Goldreich's สมมติฐาน)
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
