ผู้เขียน: Guo Yu

บทความนี้ได้รับการอัปเดตเป็น Github:https://github.com/

การแนะนำ:

ฉันคิดว่าบล็อกเชนแทบจะไม่ใช่ "เทคโนโลยี" มันเป็นเหมือนสนามที่ครอบคลุมทั้งหมด หรือพูดในเชิงเลื่อนลอยว่า blockchain เป็นเหมือนสิ่งมีชีวิตที่รวมเอาเทคโนโลยีทางทฤษฎีต่างๆ

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

Zero-knowledge Proof เป็นเทคโนโลยีสำคัญในการเชื่อมต่อข้อมูลออนเชนและการประมวลผลนอกเชน และยังเป็นวิธีที่สำคัญในการตระหนักถึงการปกป้องความเป็นส่วนตัวของข้อมูลออนเชน

พิสูจน์

"พิสูจน์"ในอดีตและปัจจุบัน

หลักฐานคืออะไร? หลายคนอาจจะเป็นเหมือนผม พอเห็น 2 คำนี้ก็อดไม่ได้ที่จะนึกถึงรูปทรงเรขาคณิตต่างๆ ที่คล้ายๆ สามเหลี่ยมในกระดาษข้อสอบ ม.ต้น เมื่ออาจารย์วาดเส้นเสริมอย่างมหัศจรรย์ กระบวนการพิสูจน์ก็ชัดเจนขึ้นทันที แล้วจะเสียใจว่าทำไมไม่คาดหวัง

กรีกโบราณ: "หลักฐาน" == "ความเข้าใจ"

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

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

การพิสูจน์ทางคณิตศาสตร์มักซ่อน "ข้อมูลเชิงลึก" ที่ลึกซึ้งไว้ ฉันเชื่อว่าหลายคนเคยอ่านเรื่องราวของ "ทฤษฎีบทสุดท้ายของแฟร์มาต์" [1] ฉันไม่สามารถเขียนลงไปได้" และต้องใช้ความเฉลียวฉลาดหลายชั่วอายุคนในการนำ Wiles ไปสู่ สูงสุด. เมื่อเร็ว ๆ นี้เช่น "Poincaré Conjecture", "Goldbach's Conjecture" ด้วยอายุเล็กน้อยและ Zhang Yitang นักวิทยาศาสตร์ชาวจีนที่ฉันชื่นชมมากได้ทำงานหนักเป็นเวลาสิบปีหลังจากศึกษาอย่างรอบคอบ "Goldston-Pintz -Yıldırım" และหลังจากการพิสูจน์ "ข้อมูลเชิงลึก" ของ "Bombieri-Friedlander-Iwaniec" ก็พิสูจน์ได้ว่า "ช่วงรอยต่อระหว่างจำนวนเฉพาะ" [2]

นับตั้งแต่เมืองไลบ์นิซในศตวรรษที่ 17 ผู้คนต่างใฝ่ฝันที่จะค้นหาวิธีการเชิงกลเพื่อพิสูจน์ให้สมบูรณ์โดยอัตโนมัติ แทนที่จะพึ่งพาแสงอัจฉริยะ

ต้นศตวรรษที่ 20: "การพิสูจน์" == "การให้เหตุผลเชิงสัญลักษณ์"

ในตอนท้ายของศตวรรษที่สิบเก้า Cantor, Boole, Frege, Hilbert, Russell, Browe, Gödel และอื่น ๆ ได้กำหนดระบบสัญลักษณ์ของตรรกะที่เป็นทางการ และ "การพิสูจน์" คือกระบวนการให้เหตุผลที่เขียนด้วยภาษาสัญลักษณ์ของตรรกะที่เป็นทางการ ตรรกะนั้นน่าเชื่อถือหรือไม่? ตรรกะนั้น "สอดคล้องกันในตัวเอง" หรือไม่? เหตุผลเชิงตรรกะนั้นถูกต้องหรือไม่สามารถพิสูจน์ได้หรือไม่? สิ่งนี้ทำให้นักคณิตศาสตร์/นักตรรกศาสตร์/นักวิทยาศาสตร์คอมพิวเตอร์คิดค้น (ค้นพบ) ระบบสัญลักษณ์ วากยสัมพันธ์เทียบกับความหมาย เชื่อถือได้เทียบกับสมบูรณ์ เรียกซ้ำกับไม่สิ้นสุด (สำหรับเรื่องราวที่ยอดเยี่ยมส่วนนี้ โปรดดูหนังสือ "Logic Engine" [3])

ในปี 1910 รัสเซลล์ได้ตีพิมพ์ผลงานชิ้นเอกของ Hong (zhuan) Huang (tou) เรื่อง "หลักการของคณิตศาสตร์" ในหนังสือ Russell และ Whitehead พยายาม "ทำให้เป็นรูปแบบ" คณิตศาสตร์อย่างสมบูรณ์ หากบรรลุเป้าหมายดังกล่าว ผลลัพธ์ทางคณิตศาสตร์ทั้งหมดจะถูกสร้างขึ้นบนรากฐานที่มั่นคงด้วยวิธีที่พิสูจน์แล้ว รูปภาพด้านล่างคือหน้าใน "หลักคณิตศาสตร์ (เล่ม 2)":

ในหมู่พวกเขา 110.643 เป็นประพจน์: "1+1=2" จากนั้นการพิสูจน์ทฤษฎีบทนี้จึงตามมา คุณอาจสงสัยว่า 1+1 ยังต้องการหลักฐานอีกหรือไม่? ใช่ ในหนังสือ Principles of Mathematics ตัวเลข 0, 1, 2, ... กำหนดไว้อย่างเคร่งครัด และต้องกำหนด "การบวก" "การคูณ" และ "เท่ากับ" อย่างเคร่งครัด จากนั้น ทุกขั้นตอนของความต้องการเหตุผล ที่จะชี้ให้เห็น หลักฐานหมายถึงอะไร? การพิสูจน์อาจยุ่งยากมาก แต่การให้เหตุผลทุกขั้นตอนนั้นเข้มงวดและถูกต้อง การพิสูจน์จำนวนมากในหนังสือเล่มนี้เป็นแบบกลไก ตามสัจพจน์และกฎการอนุมาน การสร้างการพิสูจน์แบบหนึ่งจะดำเนินการ การมองหาการพิสูจน์ดูเหมือนว่าจะถูกส่งต่อไปยังบุคคล จากนั้นเขาก็ค้นหาด้วยกลไกในชุดของสัจพจน์และ กฎอนุมานโดยไม่ต้องคิด

ดูเหมือนว่าผู้คนจะไม่ห่างไกลจาก "การพิสูจน์ทฤษฎีบทอัตโนมัติ"

น่าเสียดายที่ Gödel ได้พิสูจน์ "ทฤษฎีบทความไม่สมบูรณ์ของ Gödel" [4] ในปี 1931 และ Turing ได้พิสูจน์ความสามารถในการตัดสินใจไม่ได้ของปัญหาการหยุดชะงักของเครื่องจักร Turing ในปี 1936 [5] ผลลัพธ์เหล่านี้ยุติจินตนาการอายุหลายศตวรรษนี้ ไม่ว่าระบบความจริงจะได้รับการออกแบบมาอย่างแยบยลเพียงใด ก็ไม่สามารถจับความจริงทั้งหมดได้

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

1960: "พิสูจน์" == "ขั้นตอน"

ครึ่งศตวรรษต่อมา ในทศวรรษที่ 1960 นักลอจิสติกส์ Haskell Curry และ William Howard ได้ค้นพบ "การโต้ตอบทางเวทมนตร์" จำนวนมากอย่างต่อเนื่องใน "ระบบลอจิก" และ "ระบบคอมพิวเตอร์ - แคลคูลัสแลมบ์ดา" ซึ่งต่อมาถูกเรียกว่า "การโต้ตอบของเคอร์รี-ฮาวเวิร์ด" การค้นพบนี้ทำให้ทุกคนตระหนักในทันทีว่า "การเขียนโปรแกรม" และ "การเขียนหลักฐาน" เป็นแนวคิดที่เป็นอันหนึ่งอันเดียวกันอย่างแท้จริง ในอีก 50 ปีข้างหน้า การพัฒนาทฤษฎีและเทคโนโลยีที่เกี่ยวข้องทำให้การพิสูจน์ไม่ได้อยู่ในเอกสารฉบับร่างอีกต่อไป แต่สามารถแสดงออกได้ด้วยโปรแกรม การทำแผนที่แบบไอโซมอร์ฟิคนี้น่าสนใจมาก: ประเภทของโปรแกรมที่สอดคล้องกับทฤษฎีบทของการพิสูจน์ วัฏจักรสอดคล้องกับการเหนี่ยวนำ ... (แนะนำหนังสือที่นี่: "Software Foundation" (Software Foundations แปลเป็นภาษาจีน) [6]) . ในกรอบของนักสัญชาตญาณ การพิสูจน์หมายถึงการสร้างอัลกอริทึม และการสร้างอัลกอริทึมก็คือการเขียนโค้ดจริงๆ (สิ่งที่ตรงกันข้ามก็เป็นความจริงเช่นกัน อืม สิ่งที่เข้ารหัสโดย coder ไม่ใช่รหัส แต่เป็นการพิสูจน์ทางคณิตศาสตร์ :P)

ปัจจุบันในสาขาวิทยาการคอมพิวเตอร์การพิสูจน์ทฤษฎีต่างๆได้เปลี่ยนจากภาพร่างบนกระดาษเป็นรูปแบบของรหัส ภาษาโปรแกรม "พิสูจน์อักษร" ที่ได้รับความนิยมมากขึ้น ได้แก่ Coq, Isabelle, Agda เป็นต้น การใช้โปรแกรมเพื่อสร้างการพิสูจน์ การตรวจสอบความถูกต้องของการพิสูจน์สามารถทำได้โดยใช้โปรแกรม และแรงงานที่ทำซ้ำๆ จำนวนมากสามารถได้รับความช่วยเหลือจากโปรแกรม เช่นเดียวกับซอฟต์แวร์คอมพิวเตอร์ สิ่งก่อสร้างสำหรับการพิสูจน์ทฤษฎีทางคณิตศาสตร์กำลังถูกสร้างขึ้นทีละขั้นตอน ในเดือนธันวาคม พ.ศ. 2539 W. McCune ใช้เครื่องมือพิสูจน์ทฤษฎีบทอัตโนมัติ EQP เพื่อพิสูจน์การคาดเดาทางคณิตศาสตร์อายุ 63 ปี "Ronbins Conjecture" ต่อมา The New York Times ได้ตีพิมพ์บทความชื่อ "Computer Math Proof Shows Reasoning Power" [7] หารืออีกครั้งถึงความเป็นไปได้ว่าเครื่องจักรจะสามารถแทนที่ความคิดสร้างสรรค์ของมนุษย์ได้หรือไม่

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

ทศวรรษที่ 1980: "การพิสูจน์" == "ปฏิสัมพันธ์"

ในปี 1985 Jobs เพิ่งออกจาก Apple และ Dr. S. Goldwasser มาที่ MIT หลังจากสำเร็จการศึกษา และร่วมเขียนบทคลาสสิกกับ S. Micali และ Rackoff ที่สามารถบันทึกไว้ในพงศาวดารของวิทยาการคอมพิวเตอร์: "ความรู้ในอินเทอร์แอกทีฟ ระบบการพิสูจน์มีความซับซ้อน เพศ” [8]

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

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

ชื่อเรื่องรอง

หลักฐานการโต้ตอบ

อลิซ: ฉันอยากพิสูจน์ให้คุณเห็นว่าฉันมีคำตอบของสมการ w^3 - (w+1)^2 + 7 = 0 (คำตอบของสมการ: w=3)

บ๊อบ: โอเค ฉันกำลังฟังอยู่

อลิซ: แต่ฉันจะไม่บอกคุณว่า x เป็นเท่าไหร่ เว้นแต่คุณจะยินดีจ่าย

บ๊อบ: ใช่ แต่คุณต้องพิสูจน์ว่าคุณมีคำตอบของสมการก่อน แล้วผมจะจ่ายเงินให้คุณ

อลิซ: @#$%^& (เทคโนโลยีสีดำ)

บ๊อบ: ?????? (เทคโนโลยีสีดำ)

อลิซ: &*#$@! (เทคโนโลยีสีดำ)

บ๊อบ: ?????? (เทคโนโลยีสีดำ)

...... (ต่อที่เทคโนโลยีสีดำ)

อลิซ: โอเค มันจบแล้ว

Bob: อืม คุณมีคำตอบของสมการนี้แล้ว แต่ถ้าผมจ่ายเงิน คุณจะบอกคำตอบผมไหม

อลิซ: หยุดพูดไร้สาระแล้วจ่าย!

ตัวอย่างข้างต้นเป็น "หลักฐานเชิงโต้ตอบ" สมมติว่าอลิซรู้คำตอบของสมการ f(w) = 0 อลิซจะโน้มน้าวบ็อบได้อย่างไรว่าเธอรู้ w อลิซบอกข้อมูลมากมายกับบ็อบใน "เวทีเทคโนโลยีสีดำ" คำถามสำคัญคือ Bob เดาได้ไหมว่า w คืออะไรจากข้อมูลจำนวนมากที่อลิซพูด หรือเขาสามารถวิเคราะห์เงื่อนงำเกี่ยวกับ w ได้หรือไม่ หาก Bob มีความสามารถนี้ Bob อาจไม่จำเป็นต้องจ่ายเงิน เพราะเขาได้รับข้อมูลที่มีค่านี้แล้ว

โปรดทราบว่าหากบทสนทนาระหว่างอลิซกับบ็อบเป็น "ความรู้เป็นศูนย์" บ็อบจะไม่สามารถรับข้อมูลอื่นใดเกี่ยวกับ w ยกเว้นว่า w เป็นคำตอบของ f(w)=0 นี่เป็นสิ่งสำคัญมาก อยู่ในความสนใจของอลิซ

ตอนนี้ทบทวนคำว่า "Zero-Knowledge Proof" ซึ่งเรียกว่า "Zero-Knowledge Proof" ในภาษาอังกฤษ คำนี้มีสามส่วนสำคัญ:

• ศูนย์

• พิสูจน์

• พิสูจน์

คุณอาจมีความรู้สึกเล็กน้อยลองตีความ:

• ศูนย์: อลิซรั่วไหลความรู้ "ศูนย์" เกี่ยวกับ w นั่นคือไม่มีความรู้ใดรั่วไหล

• เกร็ดความรู้ ในที่นี้หมายถึงว.

• ข้อพิสูจน์: มันคือ "ส่วนเทคโนโลยีสีดำ" ในการสนทนาระหว่างอลิซกับบ็อบ

ชื่อเรื่องรอง

การพิสูจน์ความรู้เป็นศูนย์มีประโยชน์อย่างไร

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

เทคโนโลยี Zero-knowledge Proof สามารถแก้ปัญหาความน่าเชื่อถือของข้อมูลและคอมพิวเตอร์ได้!

Zhang San บอกว่าเขามีเงิน 100 หยวน Li Si บอกว่าเขาเรียนจบจากมหาวิทยาลัยปักกิ่ง และ Wang Wu บอกว่าเขาจะกินข้าวกลางวันกับ Ba Feite พูดเปล่าโดยไม่มีหลักฐาน แสดงหลักฐานให้ฉันเห็น

ดังนั้น "การพิสูจน์ด้วยความรู้เป็นศูนย์" จะแก้ปัญหาความเชื่อถือของข้อมูลได้อย่างไร ในบทความก่อนหน้านี้ "zkPoD: Blockchain, Zero-Knowledge Proof and Formal Verification, Realizing Fair Transaction without Intermediaries and Zero Trust" [9] ฉันได้กล่าวถึงแนวคิด "การจำลอง":

เทคโนโลยีการพิสูจน์ความรู้ที่ไม่มีความรู้สามารถ "จำลอง" บุคคลที่สามเพื่อให้แน่ใจว่าการยืนยันบางอย่างนั้นน่าเชื่อถือ

กล่าวอีกนัยหนึ่ง เมื่อเราได้รับข้อมูลที่เข้ารหัส ก็จะมีหลักฐานที่ไม่มีความรู้ ข้อพิสูจน์ที่ไม่มีความรู้นี้กล่าวว่า "การยืนยัน X เกี่ยวกับข้อมูลนั้นเป็นความจริง" ซึ่งเทียบเท่ากับทูตสวรรค์กระซิบข้างหูของเราว่า "การยืนยัน X เกี่ยวกับข้อมูลนั้นเป็นความจริง"!

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

การใช้หลักฐานที่ไม่มีความรู้บางอย่าง:

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

• การบีบอัดคอมพิวเตอร์และการขยายบล็อกเชน: ในบรรดาเทคโนโลยีการขยายบล็อกเชนจำนวนมาก การใช้เทคโนโลยี zkSNARK ของ Vitalik สามารถปรับปรุงประสิทธิภาพหลายสิบเท่าให้กับเฟรมเวิร์ก Ethereum ที่มีอยู่ เนื่องจากการพิสูจน์การคำนวณจึงไม่จำเป็นต้องทำการคำนวณเดิมซ้ำหลายๆ ครั้ง ในสถาปัตยกรรมบล็อกเชนแบบดั้งเดิม การคำนวณแบบเดียวกันจะถูกทำซ้ำหลายครั้ง เช่น การตรวจสอบลายเซ็น การตรวจสอบความถูกต้องของธุรกรรม และการตรวจสอบสัญญาอัจฉริยะ การดำเนินการ เป็นต้น กระบวนการคำนวณเหล่านี้สามารถบีบอัดได้ด้วยเทคโนโลยีการพิสูจน์ความรู้เป็นศูนย์

• การเข้ารหัสการสื่อสารแบบ end-to-end: ผู้ใช้สามารถส่งข้อความถึงกันแต่ไม่จำเป็นต้องกังวลว่าเซิร์ฟเวอร์จะได้รับบันทึกข้อความทั้งหมด พร้อมกันนั้น ข้อความยังสามารถสร้างหลักฐานที่ไม่มีความรู้ที่สอดคล้องกันตาม ข้อกำหนดของเซิร์ฟเวอร์ เช่น แหล่งที่มาของข้อความและวัตถุประสงค์ในการส่งขึ้นฝั่ง

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

• พื้นที่เก็บข้อมูลแบบกระจายอำนาจ: เซิร์ฟเวอร์สามารถพิสูจน์ให้ผู้ใช้เห็นว่าข้อมูลของพวกเขาถูกเก็บไว้อย่างเหมาะสมและไม่เปิดเผยเนื้อหาใดๆ ของข้อมูล

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

• สร้างโปรโตคอลการทำธุรกรรมที่ยุติธรรมอย่างสมบูรณ์สำหรับสินค้าดิจิทัลออนไลน์ [9]

• ชื่อเรื่องรอง

ตัวอย่าง: ทำแผนที่ปัญหาการระบายสีสามสี

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

มาออกแบบโปรโตคอลการโต้ตอบกัน:

• "ผู้รับรอง" อลิซ

• "ผู้ตรวจสอบ" บ๊อบ

อลิซมีคำตอบสำหรับแผนที่สามสีอยู่ในมือ ดูภาพด้านล่าง กราฟนี้มีทั้งหมด 6 จุดและ 9 ขอบ

ตอนนี้อลิซต้องการพิสูจน์ให้บ็อบเห็นว่าเธอมีคำตอบ แต่เธอไม่ต้องการให้บ็อบรู้คำตอบ อลิซกำลังจะทำอะไร?

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

ดูภาพด้านล่าง ขณะนี้ Bob กำลังจะย้าย (ดูภาพด้านล่าง) เขาต้องการเลือก "ด้าน" โดยสุ่ม โปรดทราบว่าเป็นการสุ่มและ Alice จะไม่ปล่อยให้ตัวเลขสุ่มที่ทำนายไว้ใน ก้าวหน้า.

สมมติว่าบ๊อบหยิบขอบด้านล่างและบอกอลิซ

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

ไม่เป็นไร Bob สามารถขอให้ Alice ทำอีกครั้งได้ ดูภาพด้านล่าง

อลิซเปลี่ยนสีอีกครั้ง เปลี่ยนสีน้ำเงินเป็นสีม่วง สีเขียวเป็นสีน้ำตาล สีส้มเป็นสีเทา แล้วปิดจุดทั้งหมดด้วยกระดาษ จากนั้น Bob จะเลือกอีกขอบหนึ่ง เช่น ในภาพด้านบน เขาเลือกขอบแนวตั้ง แล้วขอให้ Alice เปิดกระดาษให้ดู ถ้า Bob พบว่าจุดยอดทั้งสองด้านของขอบนี้มีสีต่างกัน จากนั้นเวลาของบ็อบจะสะดุดเล็กน้อย บางทีอลิซอาจมีคำตอบสำหรับการระบายสีนี้จริงๆ อย่างไรก็ตาม สองครั้งยังคงไม่เพียงพอ และ Bob ต้องการทำอีกสองสามครั้ง

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

โดยที่ |E| คือจำนวนขอบทั้งหมดในกราฟ ถ้า n มากเพียงพอ ความน่าจะเป็น Pr นี้จะกลายเป็นน้อยมากและกลายเป็น "ไม่มีนัยสำคัญ"

ชื่อเรื่องรอง

ข้อมูลเทียบกับความรู้

• ข้อมูล「ข้อมูล」

• ความรู้ "ความรู้"

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

ถ้าอลิซบอกบ็อบว่าเลข 2^2^41-1 เป็นจำนวนเฉพาะ เห็นได้ชัดว่านี่คือ "ความรู้" เพราะมันต้องใช้พลังในการคำนวณมากในการหาว่าตัวเลขนั้นเป็นจำนวนเฉพาะหรือไม่

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

เราสามารถลองกำหนดได้ว่าหาก "ข้อมูล" ที่ Bob ได้รับระหว่างกระบวนการโต้ตอบสามารถช่วยปรับปรุงความสามารถของ Bob ในการถอดรหัสความลับของ Alice ได้โดยตรง เราจะบอกว่า Bob "ได้รับความรู้" จะเห็นได้ว่าคำจำกัดความของคำว่าความรู้นั้นเกี่ยวข้องกับพลังในการคำนวณของ Bob หากข้อมูลไม่เพิ่มพลังในการคำนวณของ Bob ก็จะไม่สามารถเรียกข้อมูลนั้นว่า "ความรู้" ได้ ตัวอย่างเช่น ในระหว่างการโต้ตอบระหว่างอลิซกับบ็อบ อลิซพลิกเหรียญทุกครั้ง แล้วบอกผลลัพธ์ให้บ็อบทราบ จากมุมมองของข้อมูล ข้อมูลที่บ็อบได้รับเป็นเพียง "เหตุการณ์" แต่บ็อบไม่ได้รับ "ความรู้ใดๆ" "เพราะบ๊อบสนิท คุณพลิกเหรียญได้เอง

คำพูดต่อไปนี้เป็นบทสรุปในหนังสือ "Foundations of Cryptography - Basic Tools" [10]

• "ความรู้" เกี่ยวข้องกับ "ความยากในการคำนวณ" แต่ "ข้อมูล" ไม่ใช่

• "ความรู้" เกี่ยวข้องกับสิ่งที่เปิดเผยต่อสาธารณชน ในขณะที่ "ข้อมูล" เกี่ยวข้องกับสิ่งที่เปิดเผยต่อสาธารณะบางส่วนเป็นหลัก

ชื่อเรื่องรอง

การคำนวณที่ตรวจสอบได้และปัญหาความพอใจของวงจร

เมื่อดูปัญหาสามสีในแผนที่ด้านบน คุณรู้สึกว่านี่เป็นเพียงปัญหาทางวิชาการ จะเกี่ยวข้องกับปัญหาจริงได้อย่างไร? ปัญหาแผนที่สามสีเป็นปัญหา NP-Complete ซึ่งเป็นคำศัพท์ใน "ทฤษฎีการคำนวณ" อีกอันหนึ่งเรียกว่า "ปัญหาที่น่าพอใจของวงจร" ก็เป็นปัญหา NP-Complete เช่นกัน NP-Complete เป็นปัญหาประเภทหนึ่ง กระบวนการแก้ปัญหานั้นยากที่จะทำให้เสร็จในเวลาพหุนาม นั่นคือ "แก้ไขได้ยาก" แต่กระบวนการตรวจสอบวิธีแก้ปัญหาสามารถทำได้ในเวลาพหุนาม นั่นคือ "ตรวจสอบง่าย ".

แล้ววงจรคืออะไร? ต่อไปนี้เป็น "วงจรเลขคณิต" ที่แตกต่างกันสามแบบ:

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

สิ่งนี้หมายความว่า? มาลองแก้ปัญหาการปกป้องความเป็นส่วนตัวของข้อมูลด้วยการรวม "การพิสูจน์ที่ไม่มีความรู้" และ "ปัญหาความพึงพอใจของวงจร"

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

ทำอย่างไรให้ Bob เชื่อว่าผลลัพธ์ของการรันโค้ด P ต้องเป็น y โดยไม่ต้องรันโค้ด

นี่คือเวลาคิด ทุกคนคิดได้ห้านาที...

(ห้านาทีต่อมา……)

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

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

ด้วยวิธีนี้ Bob สามารถตรวจสอบได้ว่าการพิสูจน์บนกระดาษแผ่นนี้ถูกต้องหรือไม่โดยไม่ต้องคำนวณวงจรใหม่ กระบวนการ ตรวจสอบนั้นง่ายมาก:

บ๊อบตรวจสอบในทางกลับกันว่าอินพุตและเอาต์พุตของแต่ละเกทสามารถตอบสนองสมการการบวกหรือสมการการคูณได้หรือไม่

ตัวอย่างเช่น เกตหมายเลข 1 เป็นเกตเพิ่มเติม อินพุต 2 อินพุตคือ 3, 4 และเอาต์พุตคือ 7 ดังนั้นจึงเป็นเรื่องง่ายที่จะรู้ว่าการคำนวณของเกตนี้ถูกต้อง เมื่อ Bob ตรวจสอบประตูทุกบานแล้ว เขามั่นใจได้ว่า:

อลิซคิดเลขตามจริง ไม่ได้โกง

เนื้อหาในบทความนี้เป็นการเฉลย "เฉลย" ที่ "ตอบโจทย์" วงจรเลขคณิต P.

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

สำหรับอลิซ ถ้าบ็อบยืนยันด้วยวิธีนี้ เธอไม่มีทางโกงแน่นอน แต่วิธีนี้มีข้อเสียอย่างเห็นได้ชัด:

• ข้อเสีย 1: ถ้าวงจรมีขนาดค่อนข้างใหญ่ การพิสูจน์จะใหญ่มาก และภาระงานสำหรับ Bob ในการตรวจสอบการพิสูจน์ก็มากเช่นกัน

• ข้อเสียเปรียบ 2: ในระหว่างกระบวนการตรวจสอบ Bob รู้รายละเอียดทั้งหมดของการทำงานของวงจร รวมทั้งอินพุต

• เทคโนโลยีสีดำ

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

เดี๋ยวก่อน นี่มันปัญหา หลังจากที่ Bob ได้รับรายละเอียดภายในของการทำงานของวงจรทั้งหมดแล้ว เขาไม่รู้รหัสผ่านเหรอ? ใช่ เห็นได้ชัดว่าอลิซไม่สามารถทำเช่นนั้นได้ แล้วอลิซจะทำอย่างไร?

คำตอบคือ มีหลายวิธี ผู้อ่านที่ชื่นชอบเทคโนโลยีบล็อกเชนส่วนใหญ่คุ้นเคยกับ zkSNARK[11], zkSTARK[12], BulletProof[13] และเทคโนโลยีที่ค่อนข้างเล็กบางอย่างซึ่งทั้งหมดนี้สามารถช่วยอลิซทำมันได้ มาถึง:

ในแบบที่ไม่มีความรู้ อลิซพิสูจน์ให้บ็อบเห็นว่าเธอคำนวณวงจรและใช้ข้อมูลที่เป็นความลับของเธอ

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

"โปรโตคอลการพิสูจน์ความพึงพอใจของวงจร Zero-knowledge" มอบเทคโนโลยีที่ตรงที่สุดเพื่อปกป้องความเป็นส่วนตัว/ข้อมูลที่ละเอียดอ่อน

เขียนในตอนท้าย

เขียนในตอนท้าย

ไม่ว่าจะเป็นทฤษฎีบทเลขละเอียด ปัญหาแผนที่สามสี หรือปัญหาความพอใจของวงจร อะไรคือจุดประสงค์ของการพิสูจน์การมีอยู่? การพิสูจน์ทั้งหมดมี "ความไม่สมมาตร" ระหว่าง "การพิสูจน์" และ "การยืนยัน" การพิสูจน์อาจเป็นกิจกรรมที่ต้องใช้การคำนวณหรือใช้จิตใจมาก ไม่ว่าจะเป็น "ทฤษฎีบทสุดท้ายของแฟร์มาต์" ที่ใช้เวลาหลายร้อยปี หรือหลักฐาน POW ใน Bitcoin การพิสูจน์เหล่านี้ควบแน่นพลังงานที่ใช้ในกระบวนการค้นหาข้อพิสูจน์ พลังงาน กระบวนการพิสูจน์อาจซับซ้อนเกินจริง บางครั้งต้องใช้อัจฉริยะในการพิสูจน์ และกระบวนการตรวจสอบต้อง (หรือควร) เป็นกิจกรรมที่เรียบง่าย เชิงกล และยุติได้ในเวลาที่ถูกต้อง (โพลิโนเมียล) ในแง่หนึ่ง ความไม่สมดุลนี้แสดงถึงความสำคัญของการพิสูจน์และแสดงให้เห็นถึงคุณค่าของการพิสูจน์ที่ไม่มีความรู้

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

อ้างอิง

อ้างอิง

• [1] Simon นักร้อง Xue Mi ทฤษฎีบทสุดท้ายของแฟร์มาต์: ความลึกลับที่ทำให้นักปราชญ์ของโลกงงงวยเป็นเวลา 358 ปี [M] สำนักพิมพ์ Shanghai Translation Publishing House, 1998

• [2]  Alec Wilkinson. The Pursuit of Beauty: Yitang Zhang solves a pure-math mystery. The New Yorker. Feb. 2015.

• [3] Martin, Davis, Zhang Butian. The Engine of Logic [M]. Hunan Science and Technology Press, 2012.

• [4] Raymond Smullyan. Gödel's Incompleteness Theorems, Oxford Univ.Press. 1991.

• [5] Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem." Proceedings of the London mathematical society 2.1 (1937): 230-265.

• [6] Pierce, Benjamin C., et al. "Software foundations."การแปลภาษาจีน:<https://github.com/Coq-zh/SF-zh

• [7] Kolata, Gina. "Computer math proof shows reasoning power." Math Horizons 4.3 (1997): 22-25.

• [8] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.

• [9] zkPoD: Blockchain, การพิสูจน์ด้วยความรู้เป็นศูนย์และการตรวจสอบอย่างเป็นทางการ, การทำธุรกรรมที่ยุติธรรมโดยปราศจากตัวกลางและความไว้วางใจเป็นศูนย์ Ambi Lab. 2019

• [10] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

• [11] Gennaro, Rosario, et al. "Quadratic span programs and succinct NIZKs without PCPs." AnnualInternational Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin, Heidelberg, 2013.

• [12] Ben-Sasson, Eli, et al. "Scalable, transparent, and post-quantum secure computational integrity." IACR Cryptology ePrint Archive 2018 (2018): 46.

• [13] Bünz, Benedikt, et al. "Bulletproofs: Short proofs for confidential transactions and more." 2018IEEE Symposium on Security and Privacy (SP). IEEE, 2018.