ผู้เขียนบทความนี้ Dongze เป็นหุ้นส่วนขนาดเล็กจาก Ambi Technology Community ปัจจุบันเขากำลังศึกษาอยู่ที่ Stanford University และทิศทางการวิจัยของเขาคือการเข้ารหัส บทความชุดนี้มาจากบันทึกการศึกษาของผู้เขียนเกี่ยวกับหลักสูตร Stanford ที่มีชื่อเสียง "CS 251: Cryptocurrencies และเทคโนโลยี blockchain" ผู้สอนหลักสูตรคือ Dan Boneh ปรมาจารย์ด้านการเข้ารหัส
หลังจากบทความฉบับล่าสุดได้รับการตีพิมพ์ ฉันรู้สึกประหลาดใจมากที่เพื่อน ๆ หลายคนชอบหลังจากอ่านบทความนั้น งั้นมาต่อกันที่ตอนนี้เลย! คราวนี้มาโฟกัสที่ SNARK กัน
เชื่อว่าเพื่อนๆที่อ่านบทความที่แล้วคงจะงงกันเล็กน้อยว่าทำไมเราถึงสร้างหลักฐานสั้นๆ แล้วพิสูจน์ข้อความยาวๆ ได้ล่ะ? ฉันเคยสงสัยเหมือนกันก่อนเรียน และเคยคิดว่านี่คือ "เทคโนโลยีสีดำ" แต่ฉันเชื่อว่าหลังจากอ่านบทความนี้ คุณจะรู้วิธีควบคุม "เทคโนโลยีสีดำ" นี้
ชื่อระดับแรก
การสร้างสี่ขั้นตอนของ SNARK
ชื่อเรื่องรอง
ขั้นตอนแรก: กำหนดเขตข้อมูลจำกัด
ก่อนสร้าง เราต้องกำหนดเขตข้อมูลจำกัด (Finite Field) เสียก่อน ซึ่งสามารถบรรจุตัวเลขทั้งหมดที่เราต้องการคำนวณได้ ในแง่ของคนธรรมดา เราจำเป็นต้องเลือกจำนวน p ที่สูงมาก ตรวจสอบให้แน่ใจว่าจำนวนนี้มากกว่าจำนวนทั้งหมดในปัญหาที่เราต้องการแก้ไข
เพื่อน ๆ ที่ได้เรียนรู้เกี่ยวกับการเข้ารหัส RSA มาก่อนอาจคุ้นเคยกับแนวคิดนี้ เขตจำกัด คือการเพิ่มเพดานให้กับตัวเลขทั้งหมดของเราและกำหนดพื้นที่การคำนวณของระบบคณิตศาสตร์ทั้งหมด คล้ายกับใน คอมพิวเตอร์ ถ้าเราต้องการสร้างตัวแปรที่เก็บตัวเลขเราต้องคิดว่าเรา ต้องการ uint32_t (32 บิต) หรือเหมือนกับ uint64_t (64 บิต) ค่าทั้งหมดที่เกินเขตข้อมูลจำกัดจะล้นโดยตรงจากนั้นย้อนกลับและเริ่มต้นจาก 0
ในโลกของคณิตศาสตร์ จริงๆ แล้วมีสเปซการคำนวณหลายประเภทที่ตรงตามลักษณะนี้ ที่พบมากคือ โมดูโลจำนวนเต็มบวกและจำนวนเฉพาะจำนวนมาก (integer mod p) ที่ใช้ในอัลกอริทึม RSA การหาจำนวน p ที่กล่าวถึงข้างต้นเป็นจำนวนเฉพาะที่มีค่ามาก และเราสามารถใช้มันเพื่อสร้างปริภูมิการคำนวณได้
ชื่อเรื่องรอง
ขั้นตอนที่ 2: สร้างวงจรเลขคณิต
เมื่อเราพบพื้นที่ดิจิทัล สิ่งต่อไปที่เราต้องทำคือแสดงปัญหาที่เราต้องการพิสูจน์เพื่อแก้ไขด้วยวงจรการดำเนินการทางคณิตศาสตร์
วงจรการดำเนินการทางคณิตศาสตร์คืออะไร? มาดูวงจรลอจิกดั้งเดิมกันก่อน
รูปด้านบนอธิบายถึงวงจรเกท NAND (NAND) สิ่งที่เราพบได้ก็คือสัญญาณอินพุตสองชุดผ่านลอจิกเกตพื้นฐานสองตัวของ AND และ OR ตามลำดับ โดยไม่ทราบมากเกินไปเกี่ยวกับประโยชน์ของวงจร ลอจิกเกตพื้นฐาน เช่น AND และ OR เป็นหน่วยการสร้างพื้นฐานของวงจรลอจิก และเราสามารถใช้ลอจิกที่ซับซ้อนใดๆ ก็ได้โดยการประกบและซ้อนกัน
เช่นเดียวกับวงจรการดำเนินการทางคณิตศาสตร์ ยกเว้นว่าโมดูลพื้นฐานได้เปลี่ยนจากลอจิกเกตเป็นการดำเนินการทางคณิตศาสตร์ เนื่องจากการบวกและการคูณเป็นการดำเนินการทางคณิตศาสตร์พื้นฐานที่สุด โดยการบวกและการคูณ เราสามารถใช้วิธีการคำนวณอื่นๆ ได้เกือบทั้งหมด เราจึงสามารถเลือก "เกทการบวก" และ "เกทการคูณ" เป็นโมดูลพื้นฐานของวงจรการดำเนินการทางคณิตศาสตร์ของเรา เราสามารถสร้าง "วงจร" ของพหุนามเชิงซ้อนได้โดยการซ้อนเกทเลขคณิต
เพื่อให้เข้าใจเกทการทำงานได้ดีขึ้น ลองแปลงเกท NAND ข้างต้นจากวงจรลอจิกเป็นวงจรการดำเนินการทางคณิตศาสตร์ (สมมติว่า Inp0 และ Inp1 เหมือนกันกับวงจรลอจิกดั้งเดิม พวกเขายังคงป้อนสัญญาณลอจิก 1/0)
มาดูเกท AND ก่อน: AND นั้นง่ายมาก เพราะผลลัพธ์ของ AND จะเป็น 1 ก็ต่อเมื่อทั้ง Inp0 และ Inp1 เป็น 1 เราค้นพบอย่างรวดเร็วว่าประตูทวีคูณจะแทนที่เกท AND ได้อย่างสมบูรณ์แบบ: ผลลัพธ์ของการคูณจะเป็น 1 ต่อเมื่ออินพุตทั้งสองเป็น 1
หลังจากแก้ AND แล้ว เรามาแปลง NOT กัน: จริงๆ แล้ว NOT นั้นง่ายมาก เนื่องจากสัญญาณอินพุตสามารถเป็น 0 หรือ 1 เท่านั้น ตราบใดที่สัญญาณอินพุตถูกลบออกจาก 1 ผลลัพธ์จะตรงกันข้าม โปรดทราบว่ามีปัญหาเนื่องจากเรามีเพียงการบวกและการคูณ ดังนั้นหากเราจำเป็นต้องใช้การลบ เราต้องคูณสัญญาณอินพุตด้วยค่าคงที่ -1 ก่อน
หลังจากการแปลงดังกล่าว เราได้แปลงวงจรลอจิกเป็นวงจรลอจิกดิจิทัลเรียบร้อยแล้ว ในเวลาเดียวกัน เนื่องจากเรารู้วิธีสร้าง AND และ NO อยู่แล้ว เราจึงสามารถทำให้สองส่วนนี้เป็นโมดูลตามทฤษฎีและเชื่อมโยงตรรกะที่ซับซ้อนใดๆ เข้าด้วยกัน
เมื่อเห็นสิ่งนี้ คุณอาจรู้สึกว่าวงจรเลขคณิตนั้นง่ายมาก และการแปลงเป็นวงจรลอจิกก็ตรงไปตรงมามากเช่นกัน แต่ความจริงแล้ว เป็นเพราะเราสันนิษฐานว่าอินพุตของวงจรเลขคณิตเหมือนกับวงจรลอจิก นั่นคือ 0 หรือ 1 ในสถานการณ์จริง ค่าอินพุตของเกทการทำงานอาจมีขนาดใหญ่มาก (ขึ้นอยู่กับขนาดของตัวเลือกฟิลด์จำกัดของเรา) เราจึงต้องหาวิธีจำกัด การป้อนข้อมูลให้กับวงจรการทำงานของเราเพื่อให้ไม่เพียงทำหน้าที่เหมือนกับวงจรลอจิกเท่านั้น แต่ยังรับค่าอินพุตได้เฉพาะตัวเลขสองตัว [0,1] เท่านั้น
แต่จะใช้ประตูเลขคณิตเพื่อแสดงความสัมพันธ์ดังกล่าวได้อย่างไร? เนื่องจากวงจรการดำเนินการทางคณิตศาสตร์เป็นพหุนามเชิงซ้อน (เช่น วงจร NAND ในรูปด้านบนจะกลายเป็น Out = 1 - Inp0 * Inp1) เราจึงสามารถแปลงคำถามนี้: เราสามารถสร้างพหุนามได้หรือไม่เฉพาะเมื่ออินพุตตรงกับช่วงค่าของ [0,1] เท่านั้น เอาต์พุตจะออกมาเป็น 0 หรือไม่ในที่สุด เราพบว่ามีพหุนามที่สามารถตอบสนองความต้องการนี้:
สตริงนิพจน์ด้านบนหมายความว่าเฉพาะเมื่อจำนวน n อยู่ในช่วงนี้ พหุนามต่อไปนี้จะแสดงผลเป็น 0 กล่าวอีกนัยหนึ่ง เราสามารถเชื่อมต่อ Inp0 และ Inp1 ที่กล่าวถึงข้างต้นเข้ากับวงจรการทำงานที่แปลงจากพหุนามนี้ตราบใดที่ผลลัพธ์เอาต์พุตของวงจรการทำงานนี้เป็น 0 เราก็มั่นใจได้ว่าเอาต์พุตของวงจรการทำงาน NAND ข้างต้นนั้นถูกต้องเช่นกัน
บางคนอาจถามว่าพหุนามที่จำกัดค่าด้านบนจำกัดได้เพียงหนึ่งอินพุต แต่เรามีสองอินพุต จะจำกัดช่วงค่าพร้อมกันได้อย่างไร อันที่จริง คำตอบนั้นง่ายมาก แค่คัดลอกพหุนามที่เหมือนกันแล้วบวกทั้งสองเข้าด้วยกัน
ด้วยสองวงจรนี้ เราเพียงต้องแน่ใจว่าเอาต์พุตของวงจรจำกัดเป็น 0 จากนั้นวงจรเกท NAND จะทำงานตามปกติ
สิ่งหนึ่งที่ควรทราบก็คือ เนื่องจากลอจิกเกตของเราสร้างขึ้นจากเกตทางเลขคณิต เราจะพบว่าลอจิกการทำงานช้ามากชื่อเรื่องรอง
ขั้นตอนที่ 3: แปลงเป็นวงจรการดำเนินการทางคณิตศาสตร์ที่พิสูจน์ได้
เมื่อเรามีแนวคิดเกี่ยวกับวงจรคอมพิวเตอร์ดิจิทัล เราสามารถต่อโมดูลวงจรต่างๆ เข้าด้วยกันเพื่อสร้างวงจรคอมพิวเตอร์ที่สามารถใช้เป็นเครื่องพิสูจน์ได้
ขั้นแรกให้กำหนดวงจรการทำงานแบบดิจิตอล C(x,w) ที่สามารถใช้เป็นหลักฐานได้โครงสร้างเฉพาะมีดังนี้:
พูดง่ายๆ วงจร C นี้มีอินพุตสองชุด
เราเรียกอินพุตชุดแรกที่มีป้ายกำกับว่า xการป้อนข้อมูลสาธารณะซึ่งหมายความว่าทุกคนจะรู้ค่าของ x โดยทั่วไป x นี้จะแสดงลักษณะของปัญหาที่คุณต้องการพิสูจน์และตัวแปรสภาพแวดล้อมคงที่บางตัว
อินพุตชุดที่สองมีชื่อว่า w ซึ่งเราเรียกว่าข้อมูลลับหรือเรียกอีกอย่างว่าพยาน ข้อมูลชุดนี้เป็นคำตอบของฝ่ายที่ส่งหลักฐานจริง และมีเพียงฝ่ายที่ส่งหลักฐานเท่านั้นที่จะรู้ และไม่มีใครสามารถรับได้
เมื่อเรามีวงจร C เป้าหมายของเราคือพิสูจน์ว่า C(x, w) = 0. กล่าวอีกนัยหนึ่ง เนื่องจาก A และ B รู้ว่าเอาต์พุตของวงจรการดำเนินการทางคณิตศาสตร์ C เป็น 0 และอินพุตสาธารณะคือ x ดังนั้น A จำเป็นต้องพิสูจน์ว่าเธอรู้ค่าอินพุตส่วนตัว w ที่ประกอบเป็นเอาต์พุตนี้
หากเราแทนแนวคิดของ C(x, w) ลงในตัวอย่างเกท NAND ที่กล่าวถึงข้างต้น เราจะพบว่าเกท NAND เพียงอย่างเดียวไม่เพียงพอที่จะเป็นวงจรสำหรับการพิสูจน์ เราสามารถกำหนดปัญหาที่เราต้องการพิสูจน์ใหม่ได้:ถ้าเรารู้ว่าเอาต์พุตของเกท NAND เป็น 0 และหนึ่งในอินพุต Inp0 คือ 1A ต้องการพิสูจน์ว่าเธอรู้ค่าของอินพุตอื่น Inp1 ในกระบวนการพิสูจน์นี้ ไม่เพียงแต่ต้องแน่ใจว่าเอาต์พุตของเกท NAND นั้นถูกต้อง แต่ยังต้องแน่ใจว่าค่าอินพุตทั้งหมดอยู่ในช่วงที่เราตกลงกันไว้ล่วงหน้า
เรารวมโครงร่างที่กล่าวถึงข้างต้น เชื่อมต่อเอาต์พุตวงจร NAND และวงจรจำกัดค่าของเราเข้าด้วยกันเพื่อสร้างวงจรการทำงาน C, x คือ Inp0, w คือ Inp1 และเราจำกัดเอาต์พุตเป็น 0 จึงสร้างความเป็นส่วนตัวของเกท NAND อย่างสมบูรณ์ เข้าสู่ ระบบการรับรอง
เมื่อเราได้วงจรพิสูจน์ขั้นสุดท้าย C เราสามารถคำนวณความซับซ้อนของวงจรการทำงานนี้ได้
หากเราต้องการทราบว่าวงจรการทำงานแบบดิจิตอล C นั้นยากเพียงใด เราสามารถอธิบายความซับซ้อนของมันได้ด้วยจำนวนประตูการทำงานที่อยู่ในนั้น โดยทั่วไปเราจะใช้เพื่อแสดง เช่นเดียวกับวงจรพิสูจน์ NAND ที่กล่าวถึงข้างต้น ก็น่าจะประมาณ 10
ชื่อเรื่องรอง
ขั้นตอนที่ 4: ระบบพิสูจน์อักษรสั้นแบบไม่โต้ตอบ (SNARK)
เมื่อเราได้รับวงจรพิสูจน์ขั้นสุดท้าย C และ x และ w ที่สอดคล้องกันจนถึงขั้นตอนที่สาม การเตรียมการของเราก็ใกล้จะเสร็จแล้ว ส่วนที่เหลือ เราสามารถส่งมอบให้กับอัลกอริธึม SNARK เพื่อสร้างและตรวจสอบหลักฐานของเรา
อันดับแรก มาดูคำจำกัดความอย่างเป็นทางการของระบบการพิสูจน์แบบไม่โต้ตอบทั้งหมด
ระบบ SNARK มักจะประกอบด้วยอัลกอริธึมหลักสามอย่าง: ตั้งค่า พิสูจน์ และยืนยัน
สร้างการตั้งค่าอัลกอริทึม:
อัลกอริทึมการตั้งค่าจะนำวงจร C ที่เรากำหนดไว้เข้าสู่ชุดของการประมวลผลล่วงหน้า (การประมวลผลล่วงหน้า) และสร้างพารามิเตอร์สองชุด Sp เป็นพารามิเตอร์สำหรับผู้พิสูจน์ และ Sv สำหรับผู้ตรวจสอบ จุดประสงค์ของพารามิเตอร์เหล่านี้คือเพื่ออำนวยความสะดวกทั้งสองฝ่ายในการสร้างและตรวจสอบการพิสูจน์แบบสั้น โดยทั่วไป ความซับซ้อนของอัลกอริธึมการสร้างจะแปรผันตามความซับซ้อนของวงจร C, O(|C|)
อัลกอริทึมการพิสูจน์พิสูจน์:
ไม่จำเป็นต้องพูดถึงขั้นตอนวิธีการพิสูจน์ ผู้พิสูจน์ จะใช้อัลกอริทึมการพิสูจน์เพื่อสร้างหลักฐานแล้วส่งหลักฐานไปยังผู้ตรวจสอบ อัลกอริทึมการพิสูจน์จะใช้ข้อมูลเกือบทั้งหมดในการสร้างการพิสูจน์ใหม่: ข้อมูลที่ประมวลผลล่วงหน้า Sp, อินพุตสาธารณะ x และอินพุตส่วนตัว w การพิสูจน์ที่ได้นั้นมีความซับซ้อนของพื้นที่สั้นมาก: |Π| = O(log|C|)
อัลกอริทึมการยืนยัน ตรวจสอบ:
อัลกอริทึมการยืนยันยังตรงไปตรงมามาก ผู้ตรวจสอบ จะใช้อัลกอริทึมการยืนยันเพื่อตรวจสอบหลักฐานที่เราได้รับ อัลกอริทึมนี้จะส่งคืนค่า 1/0 ซึ่งแสดงว่าการตรวจสอบผ่านหรือไม่ ในกระบวนการตรวจสอบ นอกจากหลักฐานที่ได้รับจากอีกฝ่ายแล้ว เรายังจำเป็นต้องประมวลผลข้อมูลล่วงหน้าและอินพุตสาธารณะ x ความซับซ้อนในการตรวจสอบยังน้อยมาก โดยทั่วไปคือ O(|x| + log|C|)
ด้วยอัลกอริธึมทั้งสามนี้ เราสามารถใช้ไดอะแกรมง่ายๆ เพื่ออธิบายระบบการพิสูจน์ทั้งหมด
ชื่อระดับแรก
ตัวอย่าง: ช่วงอินพุตและเอาต์พุตของธุรกรรมส่วนตัว (Range Proof)
เพื่อนๆ ที่อ่านบทความที่แล้วคงจำได้ว่าหากเราต้องการทำธุรกรรมส่วนตัว (Confidential Transaction) เราต้องแนบหลักฐาน 3 ชุดท้ายการทำธุรกรรมดังนี้
กลุ่มแรกคือคำสัญญาของพีเดอร์สันพิสูจน์ความสัมพันธ์ทางคณิตศาสตร์ระหว่างอินพุตและเอาต์พุต
กลุ่มที่สองคือพิสูจน์ช่วงเวลาจำเป็นต้องพิสูจน์ว่าค่าของอินพุตและเอาต์พุตทั้งหมดอยู่ในช่วงของจำนวนเต็มบวก
กลุ่มที่สามคือหลักฐานการเป็นเจ้าของเพื่อพิสูจน์ว่าผู้ริเริ่มธุรกรรมมีโทเค็นจำนวนมากเป็นอินพุตจริงๆ
การปฏิบัติตามคำสัญญาของ Pederson ได้ถูกกล่าวถึงแล้วในบทความก่อนหน้านี้ ตอนนี้เราเข้าใจโครงสร้างสี่ขั้นตอนของการพิสูจน์แบบสั้นแล้ว เราสามารถดูรายละเอียดวิธีการนำไปใช้ได้พิสูจน์ช่วงเวลา。
ก่อนอื่นเราต้องหาวงจรคณิตศาสตร์ที่เหมาะสมเพื่ออธิบายสิ่งที่เราต้องการพิสูจน์ (เราใช้ฟิลด์จำกัดของจำนวนเต็มบวกโดยค่าเริ่มต้น และเลือกจำนวนเฉพาะ p ที่มากสำหรับโมดูโล)
ถ้าเรามีตัวเลข w และเราต้องการพิสูจน์ว่าตัวเลขนี้ไม่ใช่จำนวนลบ ก่อนอื่นเราสามารถพิสูจน์ได้ว่าตัวเลขนั้นต้องอยู่ในช่วงของจำนวนเต็มบวก เนื่องจากการพิจารณาว่าจำนวนเต็มบวกในระบบคอมพิวเตอร์โดยทั่วไปไม่เกิน 256 บิต เราสามารถลดปัญหาได้:พิสูจน์ว่าจำนวน w มีค่าระหว่าง 0-2^256(ตามเงื่อนไขนี้ จำนวนเฉพาะ p ที่เลือกโดยฟิลด์จำกัดต้องมากกว่า 2^256)
ตอนนี้เราได้กำหนดปัญหาที่จะแก้ไขแล้ว เราสามารถเริ่มคิดถึงวิธีแสดงความสัมพันธ์ของค่านี้ด้วยการบวกและการคูณ โปรดจำไว้ว่าในบทที่แล้ว เมื่อเราพูดถึงค่า n ระหว่าง 0 ถึง 1 เราใช้ n * (n - 1) = 0 เพื่อจำกัดช่วงค่านี้ในทำนองเดียวกัน หากเราต้องการให้ข้อจำกัดมีค่าระหว่าง 0 ถึง 5 เราสามารถจำกัดด้วยการคูณที่ยาวขึ้น:
เห็นแบบนี้แล้ว คุณอาจรู้วิธีจำกัดค่าของ w แล้ว: เราแค่ต้องใช้วิธีเดียวกันเพื่อขยายสมการนี้ และคูณไปเรื่อยๆ จาก (w - 1) ถึง (w - 2^{256}) ไม่ใช่แค่ ตกลง?
ฟังดูเหมือนง่าย แต่เพื่อนๆ ระวังจะพบว่าในวงจรสุดท้ายจะมีมี 2^256ประตูคูณ ด้วยการคูณจำนวนมากและไม่มีการเพิ่มเติม ความซับซ้อนของวงจรนี้จึงเป็นเรื่องทางดาราศาสตร์อยู่แล้ว แม้ว่าคุณจะเรียกใช้โปรแกรมติดตั้ง คุณอาจไม่รู้ว่าคุณกำลังจะเข้าสู่ปีวอก เราจึงบอกว่าวิธีการของข้อจำกัดนี้คือไม่สมจริง
มีวิธีใดที่จะจำกัดพื้นที่ของตัวเลขนี้ w? เราสามารถใช้โครงสร้างของเลขฐานสองอย่างชาญฉลาดเนื่องจากเราต้องการกำหนดว่า w เป็นจำนวนเต็มและมากกว่า 0 แต่น้อยกว่า 2^256 เราจึงทำได้ในรูปแบบเลขฐานสองแยก w ออกเป็น 256 บิต แล้วจำกัดแต่ละบิตแยกกันในกรณีนี้ ขนาดของวงจรที่เราได้รับสุดท้ายจะเป็นสัดส่วนกับจำนวนหลักเท่านั้น และจะไม่เกี่ยวข้องกับขีดจำกัดบนสูงสุดของตัวเลขนี้ ความซับซ้อนลดลงอย่างมากในทันที
มันประสบความสำเร็จได้อย่างไร? ก่อนอื่นเราแยก w ออกเป็น 256 บิต:
เนื่องจากแต่ละบิตเป็นเลขฐานสอง เราจำเป็นต้องจำกัดพื้นที่ค่าของแต่ละบิตเป็น 0 และ 1:
ข้อจำกัดนี้ต้องการ 256 สำเนา หนึ่งชุดสำหรับแต่ละบิต เมื่อเราเตรียมข้อจำกัดเหล่านี้แล้ว ในที่สุดเราก็ตรวจสอบให้แน่ใจว่าบิตทั้งหมดรวมกันสามารถกู้คืนเป็น w ดั้งเดิมได้:
เราต่อวงจรข้อจำกัด 256+1=257 ทั้งหมดที่กล่าวมาข้างต้นเข้าด้วยกันและรวมเข้าด้วยกันเป็นเอาต์พุตเดียว วงจรสุดท้ายที่สร้างขึ้นคือวงจร C ที่เราสามารถใช้เพื่อสร้างระบบพิสูจน์ หากเอาต์พุตของ C เป็น 0 ตัวเลขที่เป็นตัวแทนของอินพุตจะต้องเป็นไปตาม:
จำนวนนี้เป็นจำนวนเต็มบวกที่สามารถแสดงด้วยเลขฐานสอง 256 บิต
เลขฐานสอง 256 บิตนี้เป็นเลขฐานสองจริงๆ (รับได้เฉพาะค่า 0 หรือ 1 เท่านั้น)
ตัวเลขไบนารี 256 บิตทั้งหมดเหล่านี้สามารถนำมารวมกันเพื่อกู้คืนหมายเลขที่ป้อน
โดยใช้คุณลักษณะของเลขฐานสองอย่างชาญฉลาดชื่อระดับแรก
ตัวอย่าง: ความเป็นเจ้าของอินพุตธุรกรรมส่วนตัว
หลังจากแก้ไขการพิสูจน์ช่วงเวลาแล้ว เรามาดำเนินการพิสูจน์ชุดสุดท้ายของการทำธุรกรรมส่วนตัว: หลักฐานการเป็นเจ้าของ ซึ่งพิสูจน์ว่ามูลค่าอินพุตของธุรกรรมส่วนตัวนั้นสมเหตุสมผล
เพื่อนๆ ที่อ่านบทความที่แล้วน่าจะทราบกันดีว่าเราได้พูดถึงระบบการพิสูจน์ความเป็นเจ้าของธุรกรรมส่วนตัวไปแล้ว 2 ระบบ คือ
ทางออกแรกคือธุรกรรมสามารถอ้างอิงถึงผลลัพธ์ของธุรกรรมก่อนหน้าได้โดยตรง แต่สิ่งนี้จะนำมาซึ่งปัญหาไก่กับไข่: ความยากอยู่ที่วิธีสร้างธุรกรรมส่วนตัวรายการแรก วิธีที่สองคือการแนบหลักฐานใหม่เพิ่มเติมในแต่ละธุรกรรม เพื่อพิสูจน์ว่ายอดเงินในบัญชีของผู้ใช้ที่เริ่มต้นธุรกรรมมีเงินมากขนาดนั้นจริงๆ
ฉันต้องการเน้นแผนการพิสูจน์ที่สองคือการพิสูจน์ยอดเงินในบัญชีของผู้ริเริ่มธุรกรรมในสถานะโลก
ในหลาย ๆ สถานการณ์ของบล็อกเชน สถานะของทั้งโลกเป็นบัญชีแยกประเภทขนาดใหญ่ แต่ละบรรทัดของบัญชีแยกประเภทจะบันทึกยอดคงเหลือในบัญชีของผู้ใช้บางราย
เพื่อให้แสดงสถานะของโลกทั้งใบได้สะดวกยิ่งขึ้น เรามักจะใช้ Merkle tree เพื่อเปลี่ยนบัญชีแยกประเภทโลกขนาดใหญ่ให้เป็นชุดค่าแฮชของ Merkle ที่สั้นและเรียบร้อย เมื่อใดก็ตามที่ยอดเงินในบัญชีมีการเปลี่ยนแปลง แฮช Merkle นี้จะเปลี่ยนไป
ต้นไม้ Merkle เป็นต้นไม้ไบนารีจริง ๆ แต่ละโหนดจะต่อค่าของโหนดย่อยสองโหนดด้านล่างเข้าด้วยกันและคำนวณค่าแฮชที่สอดคล้องกันเป็นค่าของตัวเอง เพื่ออำนวยความสะดวกในการสร้าง Merkle tree ก่อนอื่นเราจะทำการคำนวณแฮชตามค่าสมดุลดั้งเดิมที่สุด แล้วจึงเก็บค่าแฮชไว้ที่ด้านล่างของ Merkle tree
เมื่อเราสร้าง Merkle tree ด้วยวิธีนี้ เราสามารถปฏิบัติต่อค่าแฮชของ Merkle เอาต์พุตเป็น aคำมั่นสัญญา: ตราบใดที่คำมั่นสัญญาไม่เปลี่ยนแปลง สถานะปัจจุบันของโลกจะต้องไม่เปลี่ยนแปลงในบล็อกเชน หากเราต้องการบันทึกสถานะของรายการข้อมูลขนาดยาว โดยทั่วไปเพื่อประหยัดพื้นที่ เราจะบันทึกข้อผูกมัดของ Merkle ของข้อมูลทั้งหมดบนเชน แทนที่จะเก็บข้อมูลเองในเชน
หลังจากที่เราตั้งปณิธานต่อสภาวะของโลกแล้ว คำถามตามมาก็คือถ้า A เป็นบัญชี 1 ในภาพด้านบน ตอนนี้มี 5 หยวน A พิสูจน์ให้ B เห็นได้อย่างไรว่าในสถานะทั้งโลก ยอดคงเหลือของเธอคือ 5 หยวนจริงๆ
วิธีการง่ายๆ คือ A สามารถส่งยอดคงเหลือของบัญชีทั้งหมดไปยัง B จากนั้น B จะทำการคำนวณภาระผูกพันของ Merkle ด้วยตัวเอง ตราบใดที่ภาระผูกพันที่คำนวณได้ของ B เท่ากับภาระผูกพันของรัฐโลกในปัจจุบัน และ A ยืนยันว่ายอดคงเหลือในบัญชีของเธอคือ 5 หยวนจริงๆ B ก็เชื่อได้ว่า A มีเงิน 5 หยวนจริงๆ
ดูเหมือนจะเป็นวิธีที่ดีมาก แต่ปัญหาของวิธีนี้จะเห็นได้ชัดในทันที มีผู้ใช้หลายร้อยล้านคนในโลกนี้ หาก A ต้องส่งยอดเงินฝากหลายร้อยล้านบรรทัดให้ B นับประสาอะไรกับ B ที่สามารถคำนวณข้อผูกมัดนี้ได้อย่างมีประสิทธิภาพ และวิธีการพิสูจน์ดังกล่าวจะเปิดเผยข้อมูลยอดคงเหลือของผู้ใช้ทุกคน และทุกคนไม่เต็มใจอย่างแน่นอน
แล้วจะพิสูจน์ได้อย่างไรว่ายอดเงินในบัญชี 1 เป็นของสถานะโลกปัจจุบัน? ในตอนนี้เราสามารถใช้ลักษณะของต้นเมิร์กเคิลเพื่อสร้างหลักฐานเมิร์กเคิลได้
หากเราสังเกตต้น Merkle ที่ถูกตัดอย่างละเอียดในรูปด้านบน เราจะพบว่าตราบเท่าที่เราพิสูจน์ได้ว่ายอดคงเหลือของบัญชี 1 สามารถสร้างข้อผูกพันของรัฐโลกสุดท้ายกับโหนดที่อยู่ติดกันในต้นไม้ Merkle เรายังสามารถพิสูจน์ความสมดุลของ บัญชี 1 เป็นของสถานะปัจจุบันของโลก
ทำอย่างไร? เริ่มจากยอดเงินในบัญชี 1ไปจนสุดทางขึ้นต้น Merkle
ด้วยยอดเงินในบัญชี 1 เราสามารถคำนวณ H1 ได้ หลังจากมี H1 เราพบว่าเราไม่จำเป็นต้องรู้ยอดคงเหลือในบัญชี 0 ตราบใดที่สามารถรวมค่าของ H0 เพื่อสร้าง H4 ในทำนองเดียวกัน ในที่สุดเราก็สามารถสร้างความมุ่งมั่นของ Merkle ของจุดยอด —— H6 โดยการรวมกับค่าของ H5 ในท้ายที่สุด เราจำเป็นต้องส่งเพียงสามสิ่งเพื่อดำเนินการพิสูจน์ Merkle นี้: ยอดเงินในบัญชี 1, H0 และ H5 ค่าแฮชที่เหลือทั้งหมดสามารถคำนวณได้ในระหว่างกระบวนการตรวจสอบ นี่คือข้อพิสูจน์ของ Merkle
เราสามารถลดปริมาณการพิสูจน์ได้อย่างมากผ่านการพิสูจน์ของ Merkle และเรายังสามารถรับประกันได้ว่ายอดคงเหลือของผู้ใช้รายอื่นในโลกจะไม่ถูกเปิดเผยในระหว่างกระบวนการพิสูจน์ การพิสูจน์ Merkle มีประโยชน์มากในการเข้ารหัส โดยต้องใช้ขนาด n เท่านั้นเพื่อพิสูจน์ว่ามีบางอย่างอยู่ในรายการความยาว N เรามักใช้การพิสูจน์ของ Merkle เพื่อพิสูจน์ว่าชุดข้อมูลเป็นของไฟล์ขนาดใหญ่ ผู้ใช้เป็นขององค์กรขนาดใหญ่ และอื่นๆ
หลังจากเข้าใจหลักการพิสูจน์ของ Merkle แล้ว เรามาดูวิธีพิสูจน์ว่า A สามารถพิสูจน์ยอดคงเหลือของเธอในธุรกรรมส่วนตัวได้อย่างไร
สาระสำคัญของการพิสูจน์ Merkle คือเราทำได้เริ่มจากค่าที่จะพิสูจน์ ค่าแฮชจะถูกคำนวณไปจนสุด และจะถูกรวมเข้ากับค่าแฮชของโหนดที่อยู่ติดกันอย่างต่อเนื่องแต่เราพบปัญหาที่ร้ายแรงมาก: แม้ว่าเราจะสามารถซ่อนความสมดุลของผู้อื่นในสถานะโลกได้ แต่เรายังคงคุณต้องเปิดเผยยอดเงินของคุณ(มิฉะนั้นจะไม่มีทางคำนวณค่าแฮชแรก H1 ได้) สิ่งนี้ตรงกันข้ามกับสาระสำคัญของธุรกรรมส่วนตัวของเรา!
ในเวลานี้คุณต้องใช้พลังของ SNARKชื่อเรื่องรอง
ขั้นตอนที่ 1: พิสูจน์แฮชยอดคงเหลือ
ในขั้นตอนแรก เราใช้ SNARK เพื่อพิสูจน์ว่ายอดคงเหลือของบัญชี 1 สามารถรับค่าแฮช H1 ได้หลังจากผ่านฟังก์ชันแฮช
เนื่องจากเราต้องการซ่อนยอดเงินในบัญชี 1 เราจึงแสดงตัวเลขนี้ด้วย w ก่อนที่จะใช้ SNARK เราจำเป็นต้องเปลี่ยนวิธีการอธิบายของปัญหาเพื่อให้สะดวกยิ่งขึ้นในการแสดงด้วยวงจรการดำเนินการทางคณิตศาสตร์:
สมมุติว่า A เองมีความลับ w = ยอดเงินในบัญชี 1. ทั้ง A และ B รู้ล่วงหน้าถึงค่าแฮช H1 ของยอดเงินในบัญชี 1 (เราสามารถแทนค่าด้วย x) เราสามารถสร้างวงจรการดำเนินการทางคณิตศาสตร์ C: Hash(w) - x = 0 ถ้า C(x, w) = 0 แล้ว Hash(w) = x
เพื่อให้การแสดงง่ายขึ้น เราใช้โมดูลนามธรรมเพื่อแสดงฟังก์ชันแฮชบนกราฟ ในทางปฏิบัติ โดยทั่วไปเราใช้ฟังก์ชันแฮช SHA256 หลังจากที่เราได้วงจรสุดท้าย C แล้ว เราจะใช้อัลกอริทึมการตั้งค่าเพื่อสร้างพารามิเตอร์ จากนั้นใช้อัลกอริทึมการพิสูจน์เพื่อสร้างการพิสูจน์แบบสั้น
ผ่านขั้นตอนนี้เราจะได้ x สาธารณะและหลักฐาน และค่าของ x นี้คือค่าแฮชของยอดเงินในบัญชี 1ชื่อเรื่องรอง
ขั้นตอนที่ 2: กรอกหลักฐาน Merkle จาก H1
ขั้นตอนก่อนหน้านี้ทำให้เราได้รับ H1 และยังเป็นการพิสูจน์ว่า H1 นั้นถูกสร้างขึ้นจากสถานะดั้งเดิมของโลกจริงๆ สิ่งที่เราต้องทำตอนนี้คือเริ่มจาก H1 และรวมกับ H0 และ H5 ที่อยู่ติดกันตามลำดับเพื่อสร้างความมุ่งมั่นของรัฐโลกใหม่ หากเราเปรียบเทียบข้อผูกมัดที่สร้างขึ้นกับข้อผูกมัดเก่าที่บันทึกไว้ในบล็อกเชน เราสามารถเชื่อได้ว่ายอดคงเหลือของบัญชี 1 นั้นอยู่ในสถานะโลกจริงๆ
โดยสรุป เราได้แบ่งหลักฐานการเป็นเจ้าของออกเป็นสองขั้นตอนขั้นตอนแรกคือการพิสูจน์ว่าความลับ w สามารถแปลงเป็น x ได้ด้วยฟังก์ชันแฮช จากนั้นพิสูจน์ว่า x สาธารณะเป็นของ Merkle tree ของรัฐทั้งโลกชื่อระดับแรก
สรุปธุรกรรมส่วนตัว
เมื่อเห็นสิ่งนี้ ทุกคนต้องมีความเข้าใจโดยทั่วไปว่าการทำธุรกรรมส่วนตัวเป็นอย่างไร ตอนนี้ให้ฉันสรุปสิ่งที่ A ต้องทำหากต้องการจ่ายเงินให้กับ B ในการทำธุรกรรมส่วนตัว
ก่อนอื่น A ต้องส่งไปยังเครือข่ายทั้งหมดส่งธุรกรรมส่วนตัวธุรกรรมนี้ประกอบด้วยผู้ริเริ่มและผู้รับเงินของธุรกรรม แต่ไม่มีปริมาณ จำนวนอินพุตและเอาต์พุตดั้งเดิมถูกแทนที่ด้วยอักขระที่อ่านไม่ออกไม่กี่สตริง
ภายใต้การทำธุรกรรมนี้ A จำเป็นต้องแนบข้อผูกมัดของ Pederson เพื่อพิสูจน์ว่าจำนวนอินพุตและเอาต์พุตรวมกันแล้วเท่ากัน
จากนั้น A ต้องต่อท้ายอีกหนึ่งรอบการพิสูจน์ช่วงเวลาสร้างโดย SNARK(Range Proof) ซึ่งพิสูจน์ว่าตัวเลขอินพุตและเอาต์พุตเป็นจำนวนเต็มบวกที่มากกว่า 0 ทั้งหมด
สุดท้าย A ต้องต่อท้าย Aหลักฐานการเป็นเจ้าของซึ่งพิสูจน์ได้ว่าเธอเป็นเจ้าของบัญชีที่มีเงินฝากอยู่จริงๆ หลักฐานการเป็นเจ้าของนี้แบ่งออกเป็นสองส่วน ส่วนแรกคือหลักฐานค่าแฮชที่สร้างโดย SNARK และอีกส่วนคือหลักฐานของ Merkle ซึ่งพิสูจน์ว่าค่าแฮชก่อนหน้านี้เป็นของสถานะของโลกจริงๆ
ชื่อระดับแรก
ยังมีต่อ
ด้วยเหตุผลเรื่องพื้นที่ ครั้งนี้ฉันจะหยุดที่นี่ ทุกคนน่าจะเคยเห็นสิ่งนี้และเข้าใจส่วน "การพิสูจน์" ของการพิสูจน์ความรู้เป็นศูนย์แล้ว คุณคงรู้ว่าวงจรการดำเนินการทางคณิตศาสตร์คืออะไร แล้วเราจะแปลงปัญหาในชีวิตจริงเป็นวงจรได้อย่างไร
เชื่อว่าหลายคนคงสงสัย แล้วอัลกอริทึมทั้ง 3 อย่าง Setup, Prove และ Verify ทำงานอย่างไร? ในฉบับหน้า เราจะมาเจาะลึกกันต่อเพื่อทำความเข้าใจเชิงลึกเกี่ยวกับหลักการเบื้องหลังระบบพิสูจน์ SNARK
อ่านเพิ่มเติม
ตามปกติ ส่วนหนึ่งของรายการเรื่องรออ่านจะระบุไว้ที่ส่วนท้ายของบทความ และเพื่อนๆ ที่สนใจสามารถเรียนรู้เพิ่มเติมเกี่ยวกับเรื่องนี้ได้:
IOS
Android