Score:1

เหตุใด Zk-SNARK จึงเป็นอาร์กิวเมนต์แห่งความรู้หากมีตัวแยกความรู้อยู่

ธง in

จากสิ่งที่ฉันรู้ การพิสูจน์การมีอยู่ของ Knowledge Extractor หมายถึงความสมบูรณ์
เหตุใดใน zk-SNARKs (และที่คล้ายกัน) เราจึงพูดถึง Arguments of Knowledge โดยที่คุณสมบัติความสมบูรณ์เป็นเพียงการคำนวณเท่านั้น (หรือที่รู้จักกันว่าปลอดภัยจาก Provers ที่มีขอบเขตการคำนวณเท่านั้น) หากมีตัวแยกความรู้ด้วย ฉันพลาดอะไรไปรึเปล่า? บางทีตัวแยกความรู้สามารถพิสูจน์ได้ใน "ระดับ" ของความปลอดภัยที่แตกต่างกัน (การคำนวณ สถิติ และสมบูรณ์แบบ) ฉันไม่เคยเห็นสิ่งนั้นมาจนถึงตอนนี้ และฉันมักจะเห็น Knowledge Extractors เป็นสิ่งที่แตกต่างในการพิสูจน์ และไม่ได้เชื่อมโยงโดยตรงกับคุณสมบัติความสมบูรณ์ ดังนั้นฉันจึงไม่สามารถหาคำตอบได้

Vadym Fedyukovych avatar
in flag
"ในการระบุหลักฐานความรู้" โดย Bellare และ Goldreich: เพื่อตั้งชื่อว่า "หลักฐานความรู้" ควรนำเสนออัลกอริทึม "แยก" ที่ชัดเจน
Score:1
ธง cn

ความถูกต้องของความรู้สามารถคำนวณหรือสถิติได้ มีตัวอย่างคลาสสิกบางตัวอย่าง ถ้าคุณต้องการภาพประกอบ: โปรโตคอล Sigma สำหรับการเปิดที่ถูกต้องของโครงการข้อผูกพัน Damgard-Fujisaki (ตัวแปรของ Pedersen เหนือกลุ่มของคำสั่งที่ซ่อนอยู่) เป็นเสียงความรู้ภายใต้สมมติฐาน RSA (ดู ที่นี่). ตามสัญชาตญาณ เมื่อคุณทำการพิสูจน์ หมายความว่าตัวแยกข้อมูลของคุณจะทำงานก็ต่อเมื่อตรงตามเงื่อนไขบางอย่าง และคุณสามารถแสดงว่าเงื่อนไขนี้จะต้องเป็นไปตามนั้นเสมอ แต่ก็ต่อเมื่อตัวพิสูจน์ที่เป็นอันตรายไม่สามารถทำลายปัญหาหนักๆ บางอย่างได้

SNARK เป็นสัตว์แปลกหน้า: ในที่นี้ การมีอยู่ของตัวสกัดที่มีประสิทธิภาพนั้นเป็นเพียงข้อสันนิษฐาน

ดังนั้นหากคุณพิสูจน์ได้ โดยไม่มีเงื่อนไข มีเครื่องสกัดก็หมายถึงความสมบูรณ์แข็งแรง แต่ถ้าคุณพิสูจน์ได้ว่า "มีตัวแยกหรือเราสามารถแยกปัญหายากๆ X ได้" หรือหากตัวแยกมีอยู่จริงเป็นส่วนหนึ่งของข้อสันนิษฐาน คุณก็จะไม่ได้รับความสมบูรณ์ที่สมบูรณ์แบบเป็นผลจากการคำนวณเท่านั้น

in flag
ขอบคุณมากจอฟฟรอย! ดังนั้น ถ้าฉันเข้าใจดีแล้ว ความสมบูรณ์ นอกเหนือจากคำจำกัดความแล้ว ยังสามารถจัดประเภทได้หลากหลายวิธีหากมีตัวสกัดอยู่ และขึ้นอยู่กับสมมติฐานที่ตั้งไว้สำหรับการมีอยู่ของมัน สิ่งเหล่านี้สามารถคำนวณหรือสถิติได้ (หรือในที่สุดก็สมบูรณ์แบบหากได้รับการพิสูจน์โดยไม่มีเงื่อนไข) เมื่อพูดถึง SNARKS เราถือว่ามีตัวแยกสำหรับอาร์กิวเมนต์ และนั่นทำให้คุณสมบัติ soundness เป็นเสียงเชิงคำนวณด้วย หมายความว่าตัวแยกมีอยู่เฉพาะในกรณีที่ Prover มีขอบเขตทางการคำนวณ
Geoffroy Couteau avatar
cn flag
ใช่ มีหลายมิติในรสชาติของความสมบูรณ์: ไม่ว่าคุณจะมี "ความสมบูรณ์ของการเป็นสมาชิก" หรือ "ความรู้ที่ถูกต้อง" ก็เป็นหนึ่งเดียว (ฉันมักจะพูดว่า 'ความสามารถในการสกัดความรู้" ในเอกสารของฉันเพื่อแยกความแตกต่างจากความสมบูรณ์ตามปกติ) และคุณมีการคำนวณทางคอมพิวเตอร์หรือไม่ หรือสถิติเป็นอีกมิติหนึ่ง และใช่ สมมติฐานใน SNARKs โดยพื้นฐานแล้วบอกว่า "ถ้าผู้พิสูจน์มีขอบเขตและทำการพิสูจน์สำเร็จ

โพสต์คำตอบ

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