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

เรียบเรียงโดย: วิจัย DODO

ผู้แต่ง: ผู้ร่วมก่อตั้ง 0xAlpha @DeriProtocol

แนะนำสกุลเงิน

Zk-SNARK หรือการโต้แย้งความรู้แบบไม่โต้ตอบโดยสรุปแบบศูนย์ความรู้ ช่วยให้ผู้ตรวจสอบยืนยันได้ว่าผู้พิสูจน์มีความรู้บางอย่าง (เรียกว่าพยาน) ที่ตอบสนองความสัมพันธ์ที่เฉพาะเจาะจงโดยไม่เปิดเผยข้อมูลใดๆ เกี่ยวกับความรู้นั้นเอง

การสร้าง zk-SNARK สำหรับปัญหาเฉพาะเกี่ยวข้องกับสี่ขั้นตอนต่อไปนี้:

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

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

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

บทความนี้จะเป็นไปตามกฎสัญลักษณ์ต่อไปนี้:

เมทริกซ์: ตัวอักษรตัวพิมพ์ใหญ่ตัวหนา เช่น ก; เขียนในรูปแบบที่ชัดเจน \
เวกเตอร์: ตัวอักษรตัวพิมพ์เล็กพร้อมลูกศร เขียนในรูปแบบที่ชัดเจน [ ]; เวกเตอร์ทั้งหมดเป็นเวกเตอร์คอลัมน์โดยค่าเริ่มต้น \
สเกลาร์: แสดงด้วยตัวอักษรธรรมดา

ลองถามคำถามต่อไปนี้เป็นตัวอย่าง:

ฉ(x)=x^3+x^2+5 (1)

สมมติว่าอลิซต้องการพิสูจน์ว่าเธอรู้ความจริง เราจะอธิบายขั้นตอนทั้งหมดที่อลิซต้องทำเพื่อสร้าง zk-SNARK สำหรับการพิสูจน์ของเธอ
คำถามนี้อาจดูง่ายเกินไปเนื่องจากไม่เกี่ยวข้องกับโฟลว์การควบคุม (เช่น ถ้าเป็นอย่างนั้น) อย่างไรก็ตาม การแปลงฟังก์ชันที่มีโฟลว์ควบคุมเป็นนิพจน์ทางคณิตศาสตร์ไม่ใช่เรื่องยาก ตัวอย่างเช่น พิจารณาปัญหาต่อไปนี้ (หรือ “ฟังก์ชัน” ในภาษาการเขียนโปรแกรม):

ฉ(x, z):
ถ้า(z==1):
กลับ xxx+xx+5
อื่น:
กลับ xx+5

การเขียนปัญหานี้ใหม่ให้เป็นนิพจน์ทางคณิตศาสตร์ต่อไปนี้ (สมมติว่า z อยู่ใน (0,1)) จะไม่ซับซ้อนไปกว่าสมการ (1)

ฉ(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

ในบทความนี้ เราจะใช้สมการ (1) เป็นพื้นฐานในการอภิปรายต่อไป

ขั้นตอนที่ 1: วงจรเลขคณิต

สมการ (1) สามารถแบ่งออกเป็นการดำเนินการทางคณิตศาสตร์พื้นฐานได้ดังต่อไปนี้:

ซึ่งสอดคล้องกับวงจรเลขคณิตต่อไปนี้:

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

ขั้นตอนที่ 2: เมทริกซ์

ก่อนอื่น เรามานิยามเวกเตอร์ "พยาน" กันก่อนดังนี้:

โดยที่ y, s1, s2 และ s3 ถูกกำหนดไว้ในสมการ (2)
โดยปกติแล้ว สำหรับปัญหาเกี่ยวกับอินพุต m และเกตเลขคณิต n ตัว (เช่น ขั้นตอนกลาง n-1 และเอาต์พุตสุดท้าย) เวกเตอร์พยานนี้จะมีมิติ (m+n+1) ในกรณีของความเป็นจริง จำนวน n อาจมีขนาดใหญ่มาก ตัวอย่างเช่น สำหรับฟังก์ชันแฮช n มักจะอยู่ในหลักพัน

ต่อไป ให้เราสร้างเมทริกซ์ A,B,C จำนวน 3 ตัว(m+n+1) เพื่อให้เราสามารถเขียนสมการ (2) ใหม่ได้ดังต่อไปนี้:

สมการ (3) เป็นเพียงการแสดงสมการ (2) อีกแบบหนึ่ง โดยแต่ละเซต (ai, bi, ci) สอดคล้องกับเกตในวงจร เราสามารถเห็นสิ่งนี้ได้โดยการขยายสมการเมทริกซ์อย่างชัดเจน:

ดังนั้น LHS=RHS จึงเหมือนกับสมการ (2) ทุกประการ และแต่ละแถวของสมการเมทริกซ์สอดคล้องกับข้อจำกัดหลัก (เช่น ประตูเลขคณิตในวงจร)

เราข้ามขั้นตอนการสร้าง (A, B, C) ซึ่งจริงๆ แล้วค่อนข้างตรงไปตรงมา เราเพียงต้องแปลงพวกมันให้เป็นเมทริกซ์ตามข้อจำกัดหลักที่เกี่ยวข้องเพื่อกำหนดเนื้อหาของแต่ละแถวของ (A, B, C) นั่นคือ (ai, bi, ci) ยกตัวอย่างแถวแรก: เราจะเห็นได้ง่ายว่าในการทำให้ข้อจำกัดหลักอันแรก x คูณด้วย x เท่ากับ s1 เราจำเป็นต้องคูณ [0,1,0,0,0], [0, 1,0, 0,0] และ [0,0,0,1,0,0] โดยเวกเตอร์ s

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

ขั้นตอนที่ 3: พหุนาม

ตอนนี้ เรามาสร้างเมทริกซ์ PA n(n+m+*1) ซึ่งกำหนดชุดของพหุนามที่เกี่ยวข้องกับ z:

รับรองว่าฟังก์ชั่นรับค่าต่อไปนี้ที่ {1, 2, 3, 4} ตรงตามเงื่อนไข:

จากนั้นเราสามารถเขียน A ใหม่เป็น:

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

ในทำนองเดียวกัน เราสร้าง PB และ PC แยกกันสำหรับ B และ C จากนั้นเราก็สามารถเขียนสมการเมทริกซ์ใหม่ได้ดังต่อไปนี้:

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

ขั้นตอนที่ 3: จุดโค้งรูปไข่

เขียนสมการ (4) ใหม่เป็น:

โดยที่ i(z)=1 เป็นเพียงพหุนามดีกรีศูนย์เล็กน้อยใน z ที่ใช้ในการรวมสมการ - พจน์ทั้งหมดเป็นกำลังสอง ความจำเป็นของสิ่งนี้จะชัดเจนในไม่ช้า โปรดทราบว่าสมการนี้มีเพียงการบวกและการคูณพหุนามใน z เท่านั้น

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

ต่อไป เราจะอธิบายขั้นตอนการปฏิบัติโดยละเอียดยิ่งขึ้น

การเข้ารหัสแบบ Elliptic Curve

ทฤษฎีทั่วไปของเส้นโค้งรูปวงรีไปไกลเกินกว่าขอบเขตของบทความนี้ สำหรับวัตถุประสงค์ในที่นี้ เส้นโค้งวงรีถูกกำหนดให้เป็นการจับคู่จากสนามเฉพาะ Fp กับฟังก์ชัน E โดยที่ E รวมจุดในลักษณะที่ y^2=x^3+ax+b (เรียกว่าจุดเส้นโค้งวงรี หรือเรียกสั้น ๆ ว่า ECP) .

โปรดทราบว่าในขณะที่เราพูดคุยถึงเลขคณิตปกติจนถึงขณะนี้ เมื่อเปลี่ยนไปใช้สนามเฉพาะ การดำเนินการทางคณิตศาสตร์กับตัวเลขจะดำเนินการโดยใช้เลขคณิตแบบโมดูลาร์ ตัวอย่างเช่น a+b=a+b(mod p) โดยที่ p คือลำดับของ Fp

ในทางกลับกัน การเพิ่มจุดโค้งวงรีสองจุดมีการกำหนดไว้ดังที่แสดงด้านล่าง:

โดยเฉพาะอย่างยิ่ง การเพิ่ม P และ Q ของ ECP สองรายการ:

ค้นหาจุดตัดของเส้น PQ และเส้นโค้ง R แล้วกำหนดเป็น -(P+Q)
พลิกไปที่จุด "กระจกเงา" R' ของ R บนเส้นโค้ง
ดังนั้นเราจึงกำหนดการบวกของจุดเส้นโค้งวงรี P+Q=R':

โปรดทราบว่ากฎนี้ยังใช้กับกรณีพิเศษที่ใช้การเพิ่ม ECP หนึ่งรายการ ซึ่งในกรณีนี้จะใช้เส้นสัมผัสของจุดนั้น

ทีนี้ สมมติว่าเราสุ่มเลือกจุด G และจับคู่เลข 1 กับจุดนั้น ("การแมปเริ่มต้น" นี้ฟังดูไม่เป็นไปตามอำเภอใจเล็กน้อย เราจะหารือเรื่องนี้ในภายหลัง) และสำหรับ n ใดๆ ที่เป็นของ Fp เราจะกำหนดว่า:

E(N)=G+G+G+…..+G=G คูณด้วย n

มีการแสดงออกถึงการดำเนินการ กำหนดการดำเนินการ +G เป็น "เครื่องกำเนิดไฟฟ้า" ซึ่งแสดงเป็น g ดังนั้นคำจำกัดความข้างต้นจึงเทียบเท่ากับ:

หลังจากกำหนดการบวกแล้ว ความสัมพันธ์เชิงเส้นต่อไปนี้จะชัดเจน:

ดังนั้น ความสัมพันธ์เชิงเส้น (หรือข้อจำกัด) ใดๆ ใน Fp จะถูกเก็บรักษาไว้ในพื้นที่ที่เข้ารหัส B ผ่านการแมปนี้ ตัวอย่างเช่น สมการ l + m = n ใน Fp จะทำให้เกิด

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

แผนที่ไบลิเนียร์

สมมติว่า G1, G2 และ GT เป็นกลุ่มของลำดับเฉพาะ g ฟังก์ชันการจับคู่หรือแผนที่ไบลิเนียร์ มีการกำหนดไว้ดังนี้:

สตริงอ้างอิงทั่วไป

ทั้งหมดนี้เรียกว่า "กุญแจพิสูจน์" (PK) โปรดทราบว่าการแทนเวกเตอร์ภายใน E() ควรเข้าใจว่าเป็นเวกเตอร์ของจุดเส้นโค้งวงรี โดยที่แต่ละจุดจะถูกแมปจากองค์ประกอบเวกเตอร์ที่สอดคล้องกัน ดังนั้น เวกเตอร์ 11 ตัวนี้จึงประกอบด้วยจุดเส้นโค้งรูปไข่ 62 จุด (=42+63+63+63) ECP 62 รายการนี้จะมอบให้กับอลิซซึ่งเป็นผู้พิสูจน์อักษร ในสถานการณ์ทั่วไป สำหรับปัญหาเกี่ยวกับอินพุต m และข้อจำกัดหลัก n รายการ PK จะมี 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP

การคำนวณต่อไปนี้จะดำเนินการพร้อมกัน:

กระบวนการทั้งหมดเรียกว่า “รหัสยืนยัน” (VK) จุดเส้นโค้งวงรี (ECP) เพียง 7 จุดที่เกี่ยวข้องที่นี่ ซึ่งจำเป็นต้องจัดเตรียมให้กับผู้ตรวจสอบ ควรสังเกตว่าไม่ว่าปัญหาจะเกี่ยวข้องกับอินพุตและข้อจำกัดหลักจำนวนเท่าใด VK จะประกอบด้วย ECP 7 รายการเสมอ

นอกจากนี้ยังเป็นที่น่าสังเกตว่า "การตั้งค่าที่เชื่อถือได้" และกระบวนการสร้าง PK และ VK จะต้องดำเนินการเพียงครั้งเดียวสำหรับปัญหาเฉพาะ

การพิสูจน์และการตรวจสอบ

ขณะนี้มีกุญแจสาธารณะ (PK) อลิซจะคำนวณจุดโค้งวงรี (ECP) ต่อไปนี้:

เส้นโค้งวงรี 9 จุดเหล่านี้มีความสำคัญอย่างยิ่งต่อการโต้แย้งความรู้แบบไม่มีปฏิสัมพันธ์ที่กระชับความรู้เป็นศูนย์ (zk-SNARK)!

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

ตอนนี้ Alice นำเสนอหลักฐาน zk-SNARK ซึ่งในที่สุดก็นำเราไปสู่กระบวนการตรวจสอบ ซึ่งเกิดขึ้นในสามขั้นตอน

ขั้นแรก จำเป็นต้องยืนยันว่าจุดโค้งวงรี 8 จุดแรกนั้นเป็นการรวมเชิงเส้นของจุดเหล่านั้นในสตริงอ้างอิงทั่วไป

ข้อสงวนสิทธิ์：

1. บทความนี้พิมพ์ซ้ำจาก[chaincatcher] ลิขสิทธิ์ทั้งหมดเป็นของผู้เขียนต้นฉบับ [0xAlpha Co-founder @ DeriProtocol] หากมีการคัดค้านการพิมพ์ซ้ำนี้ โปรดติดต่อทีมงาน Gate Learn แล้วพวกเขาจะจัดการโดยเร็วที่สุด
2. การปฏิเสธความรับผิด: มุมมองและความคิดเห็นที่แสดงในบทความนี้เป็นเพียงของผู้เขียนเท่านั้น และไม่ถือเป็นคำแนะนำในการลงทุนใดๆ
3. การแปลบทความเป็นภาษาอื่นดำเนินการโดยทีมงาน Gate Learn เว้นแต่จะกล่าวถึง ห้ามคัดลอก แจกจ่าย หรือลอกเลียนแบบบทความที่แปลแล้ว