ผู้เขียนต้นฉบับ:LambdaClass

การรวบรวมต้นฉบับ: mutourend; Yiping, IOSG Ventures

1. บทนำ

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

การพัฒนา zk-SNARK ได้เร่งตัวขึ้นอย่างมากนับตั้งแต่เปิดตัว Bitcoin และ Ethereum เนื่องจากความสามารถในการขยายขนาดผ่านการใช้การพิสูจน์ความรู้แบบศูนย์ (มักเรียกว่าการพิสูจน์ความถูกต้องสำหรับกรณีการใช้งานเฉพาะนี้) zk-SNARK มีบทบาทสำคัญในความสามารถในการปรับขนาดบล็อกเชน ดังที่ Ben-Sasson อธิบาย ในช่วงไม่กี่ปีที่ผ่านมาได้เห็นการระเบิดของ Cambrian ในการพิสูจน์การเข้ารหัส ระบบพิสูจน์อักษรแต่ละระบบมีข้อดีและข้อเสีย และได้รับการออกแบบโดยคำนึงถึงข้อดีข้อเสียเฉพาะ ความก้าวหน้าในด้านฮาร์ดแวร์ อัลกอริธึม การพิสูจน์ใหม่ และเครื่องมือยังคงปรับปรุงประสิทธิภาพอย่างต่อเนื่อง และนำไปสู่การสร้างระบบใหม่ ระบบเหล่านี้จำนวนมากมีการใช้งานอยู่แล้ว และเรายังคงก้าวข้ามขีดจำกัดต่อไป เราจะมีระบบพิสูจน์สากลที่ใช้ได้กับทุกการใช้งานหรือไม่ หรือจะมีหลายระบบที่เหมาะกับความต้องการที่แตกต่างกันหรือไม่ เราเชื่อว่าไม่น่าเป็นไปได้อย่างยิ่งที่ระบบพิสูจน์ระบบเดียวจะครอบงำระบบอื่นๆ ทั้งหมดด้วยเหตุผลหลายประการ:

1) ความหลากหลายของการใช้งาน

2) ข้อจำกัดประเภทต่างๆ (เกี่ยวกับหน่วยความจำ ระยะเวลาการตรวจสอบ ระยะเวลาการพิสูจน์)

3) ความต้องการความทนทาน (หากระบบพิสูจน์หนึ่งเสียหาย ก็แสดงว่ามีระบบพิสูจน์อื่น)

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

1) สมมติฐานด้านการเข้ารหัส: ฟังก์ชันแฮชที่ทนต่อการชนกัน ปัญหาลอการิทึมแบบไม่ต่อเนื่องบนเส้นโค้งวงรี ความรู้เรื่องเลขชี้กำลัง

2) การตั้งค่าที่โปร่งใสและเชื่อถือได้

3) ความยาวพิสูจน์: เส้นตรงและเส้นตรงเหนือ

4) เวลาตรวจสอบ: เวลาคงที่, ลอการิทึม, ซับลิเนียร์, เชิงเส้น

5）proof size。

6) ง่ายต่อการเรียกซ้ำ

7) โครงการเลขคณิต

8) พหุนามตัวแปรเดี่ยวกับพหุนามหลายตัวแปร

บทความนี้จะสำรวจต้นกำเนิดของ SNARK โครงสร้างพื้นฐานบางส่วน และการเพิ่มขึ้น (และลดลง) ของระบบพิสูจน์ที่แตกต่างกัน บทความนี้ไม่ได้มีวัตถุประสงค์เพื่อให้การวิเคราะห์ระบบการพิสูจน์อย่างละเอียดถี่ถ้วน ให้มุ่งความสนใจไปที่ผู้ที่มีผลกระทบต่อเราแทน แน่นอนว่า การพัฒนาเหล่านี้เกิดขึ้นได้จากผลงานและแนวคิดที่ยอดเยี่ยมของผู้บุกเบิกในสาขานั้นเท่านั้น

2. ความรู้พื้นฐาน

การพิสูจน์ความรู้เป็นศูนย์ไม่ใช่เรื่องใหม่ คำจำกัดความ รากฐาน ทฤษฎีบทที่สำคัญ และแม้แต่ระเบียบการที่สำคัญล้วนได้รับการพัฒนาตั้งแต่กลางทศวรรษ 1980 แนวคิดหลักและโปรโตคอลบางส่วนที่ใช้ในการสร้าง SNARK สมัยใหม่ถูกเสนอในปี 1990 (โปรโตคอล sumcheck) ก่อนที่ Bitcoin จะถือกำเนิดขึ้น (GKR ในปี 2550) ปัญหาหลักในการใช้งานเกี่ยวข้องกับการขาดกรณีการใช้งานที่แข็งแกร่ง (อินเทอร์เน็ตไม่ได้รับการพัฒนาในปี 1990) และพลังการประมวลผลที่จำเป็น

1) การพิสูจน์ความรู้เป็นศูนย์: ต้นกำเนิด (1985/1989)

สาขาการพิสูจน์ความรู้เป็นศูนย์ปรากฏในวรรณกรรมทางวิชาการพร้อมกับบทความ The Knowledge Complexity of Interactive Proof Systems โดย Goldwasser, Mikali และ Rackoff หากต้องการพูดคุยเกี่ยวกับต้นกำเนิด คุณสามารถชมวิดีโอ ZKP MOOC Lecture 1: Introduction and History of ZKP เดือนมกราคม 2023 บทความนี้แนะนำแนวคิดเรื่องความสมบูรณ์ ความน่าเชื่อถือ และความรู้เป็นศูนย์ และให้ความรู้เกี่ยวกับการสร้างกำลังสองและความไม่ตกค้างในกำลังสอง

2) โปรโตคอล Sumcheck (1992)

โปรโตคอล sumcheck ถูกเสนอโดย Lund, Fortnow, Karloff และ Nisan ในบทความเรื่อง Algebraic Methods for Interactive Proof Systems ปี 1992 มันเป็นหนึ่งในองค์ประกอบที่สำคัญที่สุดของการพิสูจน์เชิงโต้ตอบที่กระชับ ช่วยให้เราลดข้อกำหนดในการรวมพหุนามหลายตัวแปรให้เป็นการประเมินจุดที่เลือกแบบสุ่มเพียงครั้งเดียว

3）Goldwasser-Kalai-Rothblum (GKR) ( 2007)。

โปรโตคอล GKR (ดูเอกสาร Delegating Computation: Interactive Proofs for Muggles) เป็นโปรโตคอลเชิงโต้ตอบที่เครื่องพิสูจน์ทำงานเป็นเส้นตรงกับจำนวนประตูในวงจร และเครื่องตรวจสอบทำงานใต้เชิงเส้นด้วยขนาดของวงจร ในโปรโตคอล ผู้พิสูจน์และผู้ตรวจสอบบรรลุข้อตกลงเกี่ยวกับวงจรการทำงานของพัดลมในสองของสนามไฟไนต์ที่มีความลึก d dd โดยที่เลเยอร์ d dd สอดคล้องกับเลเยอร์อินพุต และเลเยอร์ 0 00 สอดคล้องกับเลเยอร์เอาท์พุต โปรโตคอลเริ่มต้นด้วยคำสั่งเกี่ยวกับเอาท์พุตของวงจร ซึ่งลดลงเป็นคำสั่งเกี่ยวกับค่าของเลเยอร์ก่อนหน้า การใช้การเรียกซ้ำสามารถแปลงเป็นการประกาศอินพุตของวงจรซึ่งสามารถตรวจสอบได้ง่าย การลดลงเหล่านี้ดำเนินการผ่านโปรโตคอล sumcheck

4）KZG polynomial commitment scheme ( 2010)。

Kate, Zaverucha และ Goldberg นำเสนอโครงการความมุ่งมั่นพหุนามโดยใช้กลุ่มการจับคู่แบบไบลิเนียร์ในปี 2010 ความมุ่งมั่นขนาดคงที่ต่อพหุนามและการประยุกต์ของพวกเขา ข้อผูกพันประกอบด้วยองค์ประกอบกลุ่มเดียว และคณะกรรมการเปิดข้อผูกพันอย่างมีประสิทธิภาพในการประเมินพหุนามที่ถูกต้อง นอกจากนี้ ด้วยเทคโนโลยีการจัดชุด ทำให้สามารถเปิดการประเมินได้หลายรายการ ความมุ่งมั่นของ KZG มอบหนึ่งในองค์ประกอบพื้นฐานสำหรับ SNARK ที่มีประสิทธิภาพหลายอย่าง เช่น Pinocchio, Groth 16 และ Plonk นอกจากนี้ยังเป็นแกนหลักของ EIP-4844 หากต้องการทำความเข้าใจเทคโนโลยีการจัดกลุ่มอย่างสังหรณ์ใจ โปรดดูที่สะพาน Mina ถึง Ethereum ZK

3. SNARK ที่ใช้งานได้จริงโดยใช้เส้นโค้งรูปไข่

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

1) มีผู้พิสูจน์ที่มีประสิทธิภาพมากขึ้น

2) ลดปริมาณการประมวลผลล่วงหน้า

3) มีการตั้งค่าทั่วไปมากกว่าเฉพาะวงจร

4) หลีกเลี่ยงการใช้การตั้งค่าที่เชื่อถือได้

5) พัฒนาวิธีการอธิบายวงจรโดยใช้ภาษาระดับสูงแทนการเขียนข้อจำกัดพหุนามด้วยตนเอง

ในปัจจุบัน โซลูชัน SNARK ที่ใช้งานได้จริงโดยใช้เส้นโค้งรูปไข่คือ:

1）Pinocchio ( 2013)

2）Groth 16 ( 2016)

3）Bulletproofs & IPA ( 2016)

4）Sonic, Marlin, and Plonk ( 2019)

5）Lookups ( 2018/2020)

6）Spartan ( 2019)

7）HyperPlonk ( 2022)

8）Folding schemes ( 2008/2021)

3.1 Pinocchio ( 2013)

Pinocchio (ดูเอกสาร Pinocchio: Nearly Practical Verifiable Computation) เป็น zk-SNARK ที่ใช้งานได้จริงและใช้งานได้จริงครั้งแรก SNARK ขึ้นอยู่กับโปรแกรมเลขคณิตกำลังสอง (QAP) ขนาดการพิสูจน์เริ่มต้นคือ 288 ไบต์ ห่วงโซ่เครื่องมือของ Pinocchio มีคอมไพเลอร์ตั้งแต่โค้ด C ไปจนถึงวงจรเลขคณิต และแปลงเป็น QAP เพิ่มเติม โปรโตคอลต้องการตัวตรวจสอบเพื่อสร้างคีย์เฉพาะวงจร ใช้การจับคู่เส้นโค้งวงรีเพื่อตรวจสอบสมการ เส้นกำกับของการสร้างการพิสูจน์และการตั้งค่าคีย์จะเป็นเชิงเส้นกำกับกับขนาดของการคำนวณ และความยาวของการตรวจสอบจะเป็นเส้นตรงกับขนาดของอินพุตและเอาต์พุตสาธารณะ

3.2 Groth 16 ( 2016)

เอกสารของ Groth ในปี 2016 เรื่อง On the Size of Matching-based Non-interactive Arguments ได้แนะนำข้อโต้แย้งความรู้ใหม่ที่ปรับปรุงประสิทธิภาพของปัญหาที่อธิบายโดย R 1 CS มีขนาดการพิสูจน์น้อยที่สุด (มีเพียงสามองค์ประกอบกลุ่ม) และการตรวจสอบที่รวดเร็วที่เกี่ยวข้องกับการจับคู่สามรายการ นอกจากนี้ยังเกี่ยวข้องกับขั้นตอนการประมวลผลล่วงหน้าของการได้รับสตริงการอ้างอิงที่มีโครงสร้าง ข้อเสียเปรียบหลักคือแต่ละโปรแกรมที่จะได้รับการรับรองต้องมีการตั้งค่าที่เชื่อถือได้ที่แตกต่างกัน ซึ่งไม่สะดวก Groth 16 ถูกใช้ใน ZCash สำหรับรายละเอียด โปรดดูที่บล็อก ภาพรวมของระบบพิสูจน์ Groth 16

3.3 Bulletproofs & IPA ( 2016)

จุดอ่อนประการหนึ่งของ KZG PCS คือต้องมีการตั้งค่าที่เชื่อถือได้ ในรายงานข้อโต้แย้งความรู้เป็นศูนย์ที่มีประสิทธิภาพปี 2016 สำหรับวงจรเลขคณิตในเอกสารการตั้งค่าบันทึกแบบไม่ต่อเนื่องโดย Bootle และคณะ ได้มีการนำระบบอาร์กิวเมนต์ความรู้เป็นศูนย์ที่มีประสิทธิภาพสำหรับการเปิดข้อผูกพันของ Pedersen ที่ตอบสนองความสัมพันธ์ของผลิตภัณฑ์ภายใน ระบบพิสูจน์ผลิตภัณฑ์ภายในมีเครื่องพิสูจน์เชิงเส้น พร้อมการสื่อสารและการโต้ตอบแบบลอการิทึม แต่มีการตรวจสอบระยะเวลาเชิงเส้น นอกจากนี้ยังพัฒนาแผนข้อผูกพันพหุนามที่ไม่จำเป็นต้องมีการตั้งค่าที่เชื่อถือได้ ทั้ง Halo 2 และ Kimchi นำแนวคิดในการใช้ IPA PCS มาใช้

3.4 Sonic, Marlin, and Plonk ( 2019)

Sonic, Plonk และ Marlin แก้ปัญหาการตั้งค่าความน่าเชื่อถือสำหรับแต่ละโปรแกรมใน Groth 16 โดยการแนะนำสตริงอ้างอิงที่มีโครงสร้างทั่วไปและอัปเดตได้ Marlin จัดเตรียมระบบพิสูจน์อักษรโดยใช้ R 1 CS ซึ่งเป็นแกนหลักของ Aleo

Plonk แนะนำรูปแบบเลขคณิตใหม่ (ภายหลังเรียกว่า Plonkish) และใช้การตรวจสอบผลิตภัณฑ์หลักสำหรับข้อจำกัดในการคัดลอก Plonkish ยังอนุญาตให้มีการนำประตูแบบพิเศษมาใช้เพื่อการทำงานบางอย่าง ซึ่งเรียกว่าประตูแบบสั่งทำพิเศษ หลายโครงการได้ปรับแต่งเวอร์ชันของ Plonk รวมถึง Aztec, ZK-Sync, Polygon ZKEVM, Minas Kimchi, Plonky 2, Halo 2 และ Scroll ดูบล็อก ทุกสิ่งที่คุณอยากรู้เกี่ยวกับ Plonk

3.5 Lookups ( 2018/2020)

Gabizon และ Williamson เปิดตัว plookups ในปี 2020 โดยใช้การตรวจสอบผลิตภัณฑ์ครั้งใหญ่เพื่อพิสูจน์ว่ามีค่าอยู่ในตารางของค่าที่คำนวณไว้ล่วงหน้า แม้ว่าอาร์กิวเมนต์การค้นหาจะถูกเสนอก่อนหน้านี้ใน Arya แต่การสร้างอาร์กิวเมนต์นั้นจำเป็นต้องกำหนดความหลากหลายของการค้นหา ซึ่งมีประสิทธิภาพน้อยกว่า เอกสาร PlonkUp แสดงวิธีแนะนำอาร์กิวเมนต์ plookup ใน Plonk ปัญหาของอาร์กิวเมนต์การค้นหาเหล่านี้คือบังคับให้ผู้พิสูจน์ต้องจ่ายเงินสำหรับทั้งตาราง โดยไม่คำนึงถึงจำนวนการค้นหา ซึ่งหมายความว่าค่าใช้จ่ายของตารางขนาดใหญ่นั้นค่อนข้างมาก และได้ใช้ความพยายามอย่างมากในการลดต้นทุนของตัวพิสูจน์ให้เหลือเท่ากับจำนวนการค้นหาที่ใช้

Haböck เปิดตัว LogUp ซึ่งใช้อนุพันธ์ลอการิทึมเพื่อแปลงการตรวจสอบผลิตภัณฑ์เป็นผลรวมของส่วนกลับ LogUp มีความสำคัญอย่างยิ่งต่อประสิทธิภาพของ Polygon plonky 2 ZKEVM (เกินขีดจำกัด: การผลักดันขอบเขตของ ZK-EVM) ซึ่งจำเป็นต้องแยกทั้งตารางออกเป็นโมดูล STARK หลายโมดูล โมดูลจะต้องมีการเชื่อมโยงอย่างถูกต้อง และจำเป็นต้องมีการค้นหาข้ามตารางเพื่อบังคับใช้การดำเนินการนี้ การเปิดตัว LogUp-GKR ใช้ประโยชน์จากโปรโตคอล GKR เพื่อปรับปรุงประสิทธิภาพของ LogUp Caulk เป็นอาร์กิวเมนต์การค้นหาตัวแรกที่เวลาพิสูจน์มีความสัมพันธ์ใต้เชิงเส้นกับขนาดตาราง เวลาประมวลผลล่วงหน้าคือ O (N log N) และหน่วยเก็บข้อมูลคือ O (N) โดยที่ N คือขนาดตาราง โซลูชันอื่นๆ หลายอย่างตามมา เช่น Baloo, flookup, cq และ caulk+ Lasso เสนอการปรับปรุงหลายประการเพื่อหลีกเลี่ยงการคอมมิตตารางเมื่อมีโครงสร้างที่กำหนด นอกจากนี้ เครื่องพิสูจน์ของ Lasso จะจ่ายเฉพาะรายการตารางที่เข้าถึงได้โดยการดำเนินการค้นหาเท่านั้น Jolt ใช้ Lasso เพื่อพิสูจน์การทำงานของเครื่องเสมือนผ่านการค้นหา

3.6 Spartan ( 2019)

Spartan จัดเตรียม IOP สำหรับวงจรที่อธิบายโดยใช้ R 1 CS โดยใช้ประโยชน์จากคุณสมบัติของพหุนามหลายตัวแปรและโปรโตคอล sumcheck การใช้แผนข้อผูกมัดพหุนามที่เหมาะสม จะสร้าง SNARK โปร่งใสพร้อมตัวพิสูจน์ระยะเวลาเชิงเส้น

3.7 HyperPlonk ( 2022)

HyperPlonk สร้างขึ้นจากแนวคิดของ Plonk โดยใช้พหุนามหลายตัวแปร มันไม่ได้ขึ้นอยู่กับผลหารในการตรวจสอบการบังคับใช้ข้อจำกัด แต่อาศัยโปรโตคอล sumcheck นอกจากนี้ยังรองรับข้อจำกัดในระดับสูงโดยไม่กระทบต่อเวลาการทำงานของผู้พิสูจน์ เนื่องจากต้องใช้พหุนามหลายตัวแปร จึงไม่จำเป็นต้องดำเนินการ FFT และเวลาทำงานของตัวพิสูจน์จะปรับขนาดเป็นเส้นตรงกับขนาดของวงจร HyperPlonk ขอแนะนำ IOP การเรียงสับเปลี่ยนแบบใหม่ที่เหมาะสำหรับโดเมนขนาดเล็กและโปรโตคอลการเปิดแบบแบตช์ที่ใช้ผลรวมเช็ค ซึ่งจะช่วยลดภาระงานของตัวพิสูจน์ ขนาดการพิสูจน์ และเวลาของผู้ตรวจสอบ

3.8 Folding schemes ( 2008/2021)

Nova แนะนำแนวคิดของโครงร่างการพับซึ่งเป็นวิธีการใหม่ในการใช้การคำนวณแบบตรวจสอบได้ส่วนเพิ่ม (IVC) แนวคิดของ IVC สามารถย้อนกลับไปถึง Valiant ซึ่งแสดงวิธีรวมการพิสูจน์ความยาว 2 รายการ k kk ให้เป็นหลักฐานเดียวเรื่องความยาว k kk แนวคิดก็คือว่าการพิสูจน์แบบเรียกซ้ำสามารถใช้เพื่อพิสูจน์ว่าการดำเนินการจากขั้นตอน i ii ถึงขั้นตอน i + 1 i+ 1 i+ 1 นั้นถูกต้อง และเพื่อตรวจสอบการเปลี่ยนแปลงจากขั้นตอน i − 1 i-1 i− 1 ไปยังขั้นตอน i ii ถูกต้อง จึงเป็นการพิสูจน์กรณีของการคำนวณระยะยาว

Nova สามารถจัดการกับการคำนวณแบบสม่ำเสมอได้เป็นอย่างดี ต่อมาด้วยการเปิดตัว Supernova ก็ได้ขยายออกไปเพื่อรองรับวงจรประเภทต่างๆ Nova ใช้ R 1 CS เวอร์ชันผ่อนคลายและทำงานบนเส้นโค้งรูปไข่ที่เป็นมิตร การใช้ IVC โดยใช้วงจรเส้นโค้งที่เป็นมิตร (เช่น เส้นพาสต้า) ยังใช้ใน Pickles ซึ่งเป็นโมดูลฐานหลักของ Mina เพื่อให้ได้สถานะที่กระชับ อย่างไรก็ตาม แนวคิดในการพับนั้นแตกต่างจากการตรวจสอบ SNARK แบบเรียกซ้ำ แนวคิดของการสะสมนั้นมีความเกี่ยวข้องอย่างลึกซึ้งกับแนวคิดของการพิสูจน์การแบทช์ Halo แนะนำแนวคิดของการสะสมเป็นทางเลือกแทนชุดการพิสูจน์แบบเรียกซ้ำ Protostar นำเสนอโซลูชัน IVC ที่ไม่สม่ำเสมอสำหรับ Plonk ซึ่งรองรับเกตระดับสูงและการค้นหาเวกเตอร์

4. SNARK ที่ใช้ฟังก์ชันแฮชที่ป้องกันการชนกัน

ในช่วงเวลาเดียวกับที่พินอคคิโอได้รับการพัฒนา มีแนวคิดบางประการในการสร้างโครงร่างวงจร/เลขคณิตที่สามารถพิสูจน์ความถูกต้องของการทำงานของเครื่องเสมือนได้ แม้ว่าการคำนวณทางคณิตศาสตร์ของการพัฒนาเครื่องเสมือนอาจซับซ้อนกว่าหรือมีประสิทธิภาพน้อยกว่าการเขียนวงจรเฉพาะสำหรับบางโปรแกรม แต่ก็มีข้อได้เปรียบที่โปรแกรมใดๆ ไม่ว่าจะซับซ้อนเพียงใดก็ตาม สามารถพิสูจน์ได้ด้วยการสาธิตว่าโปรแกรมทำงานอย่างถูกต้องในเครื่องเสมือน แนวคิดใน TinyRAM ได้รับการปรับปรุงในภายหลังด้วยการออกแบบของ Cairo vm และเครื่องเสมือนที่ตามมา เช่น zk-evms หรือ universal zkvms การใช้ฟังก์ชันแฮชที่ป้องกันการชนกันช่วยลดความจำเป็นในการตั้งค่าที่เชื่อถือได้หรือการใช้เลขคณิตแบบวงรี แต่ต้องเสียค่าใช้จ่ายในการพิสูจน์ที่นานกว่า

1）TinyRAM ( 2013)

ใน SNARK สำหรับ C นั้น SNARK ที่ใช้ PCP ได้รับการพัฒนาเพื่อพิสูจน์ความถูกต้องของการทำงานของโปรแกรม C ที่คอมไพล์เป็น TinyRAM (คอมพิวเตอร์ชุดคำสั่งที่ลดลง) คอมพิวเตอร์ใช้สถาปัตยกรรม Harvard พร้อมด้วยหน่วยความจำเข้าถึงโดยสุ่มที่สามารถระบุตำแหน่งได้ระดับไบต์ การใช้ประโยชน์จากการไม่กำหนดขนาด ขนาดของวงจรจะปรับขนาดเสมือนกับขนาดการคำนวณ ช่วยให้สามารถจัดการลูปที่เกี่ยวข้องกับข้อมูล โฟลว์การควบคุม และการเข้าถึงหน่วยความจำได้ตามอำเภอใจ

2）STARKs ( 2018)

STARK ได้รับการเสนอโดย Ben Sasson และคณะในปี 2018 ขนาดการพิสูจน์ที่ใช้คือ O(log 2 n) มีผู้พิสูจน์และผู้ตรวจสอบที่รวดเร็ว ไม่ต้องการการตั้งค่าที่เชื่อถือได้ และถือว่าปลอดภัยหลังควอนตัม ถูกใช้ครั้งแรกโดย Starkware/Starknet กับเครื่องเสมือนของไคโร ส่วนประกอบที่สำคัญได้แก่:

• การเป็นตัวแทนระดับกลางเกี่ยวกับพีชคณิต (AIR)

• และโปรโตคอล FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity)

STARK ยังถูกใช้โดยโปรเจ็กต์อื่น ๆ (Polygon Miden, Risc 0, Winterfell, Neptune) หรือการดัดแปลงบางส่วน (Boojum ของ ZK-Sync, Plonky 2, Starky)

3）Ligero ( 2017)

• Ligero นำเสนอระบบพิสูจน์อักษรซึ่งมีขนาดพิสูจน์เป็น O(root n) โดยที่ n คือขนาดวงจร โดยจะจัดเรียงสัมประสิทธิ์พหุนามเป็นรูปแบบเมทริกซ์และใช้โค้ดเชิงเส้น

• Brakedown สร้างขึ้นจาก Ligero และแนะนำแนวคิดเกี่ยวกับแผนการผูกมัดพหุนามที่ไม่ขึ้นกับโดเมน

5. การพัฒนาใหม่ใน ZKP

การใช้ระบบพิสูจน์ที่แตกต่างกันในการผลิตแสดงให้เห็นถึงข้อดีของแต่ละแนวทางและนำไปสู่การพัฒนาใหม่ๆ ตัวอย่างเช่น เลขคณิตของ Plonkish มอบวิธีง่ายๆ ในการรวมเกตที่กำหนดเองและอาร์กิวเมนต์การค้นหา FRI แสดงให้เห็นประสิทธิภาพที่ยอดเยี่ยมในฐานะ PCS เหนือกว่า Plonky ในทำนองเดียวกัน การใช้การตรวจสอบผลิตภัณฑ์ครั้งใหญ่ใน AIR (ส่งผลให้ AIR แบบสุ่มพร้อมการประมวลผลล่วงหน้า) ช่วยปรับปรุงประสิทธิภาพและลดความซับซ้อนของข้อโต้แย้งในการเข้าถึงหน่วยความจำ คำสัญญาที่ใช้ฟังก์ชันแฮชได้รับความนิยม - ขึ้นอยู่กับความเร็วของฟังก์ชันแฮชในฮาร์ดแวร์หรือการแนะนำฟังก์ชันแฮชที่เป็นมิตรกับ SNARK ใหม่

1) โครงการความมุ่งมั่นพหุนามใหม่ (2023)

ด้วยการเกิดขึ้นของ SNARK ที่มีประสิทธิภาพโดยอิงจากพหุนามหลายตัวแปร (เช่น Spartan หรือ HyperPlonk) จึงมีความสนใจเพิ่มขึ้นในแผนพันธสัญญาใหม่ที่เหมาะสมสำหรับพหุนามดังกล่าว Binius, Zeromorph และ Basefold ต่างก็เสนอรูปแบบใหม่ที่เกี่ยวข้องกับพหุนามหลายเส้นโดยเฉพาะ Binius มีข้อดีคือไม่มีโอเวอร์เฮดในการแสดงประเภทข้อมูล (ในขณะที่ระบบพิสูจน์หลายแห่งใช้องค์ประกอบฟิลด์อย่างน้อย 32 บิตเพื่อแสดงบิตเดียว) และทำงานบนฟิลด์ไบนารี ความมุ่งมั่นของ Binius ขึ้นอยู่กับการเบรกดาวน์และได้รับการออกแบบมาให้ไม่เชื่อเรื่องโดเมน Basefold ทำให้ FRI เป็นโค้ดที่นอกเหนือจาก Reed-Solomon ส่งผลให้ PCS ไม่ขึ้นกับโดเมน

2）Customizable Constraint Systems（CCS） ( 2023)

CCS สรุป R 1 CS โดยจับ R 1 CS, Plonkish และ AIR เลขคณิตพร้อมกันโดยไม่มีค่าใช้จ่ายใดๆ การรวม CCS กับ Spartan IOP ทำให้เกิด SuperSpartan ซึ่งรองรับข้อจำกัดระดับสูง โดยไม่ต้องให้ผู้พิสูจน์ต้องเสียค่าใช้จ่ายในการเข้ารหัสที่ปรับขนาดตามระดับของข้อจำกัด โดยเฉพาะอย่างยิ่ง SuperSpartan สร้าง SNARK สำหรับ AIR พร้อมด้วยเครื่องพิสูจน์เวลาเชิงเส้น

6 บทสรุป

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

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