Zero-knowledge กระชับ และไม่มีการโต้ตอบ ARguments of Knowledge (zk-SNARKs) เป็นการเข้ารหัสลับแบบดั้งเดิมที่ทรงพลังซึ่งช่วยให้ฝ่ายหนึ่งซึ่งเป็นผู้พิสูจน์ สามารถโน้มน้าวอีกฝ่ายหนึ่งซึ่งเป็นผู้ตรวจสอบได้ว่าข้อความที่ให้มานั้นเป็นจริงโดยไม่ต้องเปิดเผยสิ่งอื่นใดนอกจาก ความถูกต้องของคำสั่ง พวกเขาได้รับความสนใจอย่างกว้างขวางเนื่องจากแอปพลิเคชันของพวกเขาในการคำนวณส่วนตัวที่ตรวจสอบได้ ให้การพิสูจน์ความถูกต้องของการทำงานของโปรแกรมคอมพิวเตอร์ และช่วยปรับขนาดบล็อคเชน เราคิดว่า SNARK จะมีผลกระทบอย่างมีนัยสำคัญในการกำหนดรูปแบบโลกของเรา ดังที่เราอธิบายไว้ใน โพสต์ ของเรา SNARK ทำหน้าที่เป็นตัวกลางสำหรับระบบการพิสูจน์ประเภทต่างๆ โดยใช้แผนข้อผูกมัดพหุนาม (PCS), รูปแบบการคำนวณทางคณิตศาสตร์, การพิสูจน์แบบโต้ตอบของออราเคิล (IOP) หรือการพิสูจน์ที่ตรวจสอบได้อย่างน่าจะเป็น (PCP) อย่างไรก็ตาม แนวคิดและแนวคิดพื้นฐานมีมาตั้งแต่กลางทศวรรษ 1980 การพัฒนาเร่งตัวขึ้นอย่างมากหลังจากการแนะนำ Bitcoin และ Ethereum ซึ่งพิสูจน์แล้วว่าเป็นกรณีการใช้งานที่น่าตื่นเต้นและทรงพลัง เนื่องจากคุณสามารถปรับขนาดได้โดยใช้ Zero-Knowledge Proofs (โดยทั่วไปเรียกว่า Validity Proofs สำหรับกรณีการใช้งานเฉพาะนี้) SNARK เป็นเครื่องมือสำคัญสำหรับการขยายขนาดของบล็อกเชน ดังที่ Ben-Sasson อธิบาย ในช่วงไม่กี่ปีที่ผ่านมาได้เห็น การพิสูจน์การเข้ารหัสแบบ Cambrian มากมาย ระบบพิสูจน์อักษรแต่ละระบบมีข้อดีและข้อเสีย และได้รับการออกแบบโดยคำนึงถึงข้อดีข้อเสียบางประการเป็นหลัก ความก้าวหน้าในด้านฮาร์ดแวร์ อัลกอริธึมที่ดีขึ้น อาร์กิวเมนต์ใหม่ และอุปกรณ์ต่างๆ ส่งผลให้ประสิทธิภาพดีขึ้นและการกำเนิดของระบบใหม่ หลายอย่างถูกนำมาใช้ในการผลิต และเรายังคงก้าวข้ามขีดจำกัดต่อไป เราจะมีระบบพิสูจน์ทั่วไปสำหรับทุกการใช้งานหรือหลายระบบที่เหมาะกับความต้องการที่แตกต่างกันหรือไม่? เราคิดว่าไม่น่าจะเป็นไปได้ที่ระบบการพิสูจน์ระบบเดียวจะควบคุมระบบทั้งหมดได้เนื่องจาก:

1. ความหลากหลายของแอพพลิเคชั่น
2. ประเภทของข้อจำกัดที่เรามี (เกี่ยวกับหน่วยความจำ เวลาในการตรวจสอบ และเวลาในการพิสูจน์)
3. ความต้องการความทนทาน (หากระบบพิสูจน์หนึ่งเสียหาย เราก็ยังมีระบบอื่นอยู่)

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

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

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

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

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

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

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

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

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

โกลด์วาสเซอร์-คาไล-ร็อธบลุม (จีเคอาร์) (2007)

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

โครงการความมุ่งมั่นพหุนาม KZG (2010)

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

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

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

1. มีข้อพิสูจน์ที่มีประสิทธิภาพมากขึ้น
2. ลดปริมาณการประมวลผลล่วงหน้า
3. มีการตั้งค่าแบบสากลมากกว่าการตั้งค่าเฉพาะวงจร
4. หลีกเลี่ยงการตั้งค่าที่เชื่อถือได้
5. การพัฒนาวิธีอธิบายวงจรโดยใช้ภาษาระดับสูง แทนที่จะเขียนข้อจำกัดพหุนามด้วยตนเอง

พินอคคิโอ (2013)

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

กรอธ 16 (2016)

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

กันกระสุนและ IPA (2016)

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

โซนิค มาร์ลิน และพลองค์ (2019)

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

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

การค้นหา (2018/2020)

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

สปาร์ตัน (2019)

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

ไฮเปอร์แพลงค์ (2022)

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

แบบแผนการพับ (2008/2021)

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

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

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

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

ไทนี่แรม (2013)

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

สตาร์คส์ (2018)

STARK ได้รับการแนะนำโดย Ben Sasson และคณะ ในปี 2561 พวกเขาบรรลุ O(log2n)(log2⁡)

ขนาดการพิสูจน์ที่มีตัวพิสูจน์และผู้ตรวจสอบที่รวดเร็ว ไม่ต้องการการตั้งค่าที่เชื่อถือได้ และคาดเดาได้ว่ามีความปลอดภัยหลังควอนตัม ถูกใช้ครั้งแรกโดย Starkware/Starknet ร่วมกับ Cairo vm การแนะนำที่สำคัญ ได้แก่ การแสดงพีชคณิตระดับกลาง (AIR) และ โปรโตคอล FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) นอกจากนี้ยังใช้โดยโปรเจ็กต์อื่น ๆ (Polygon Miden, Risc0, Winterfell, Neptune) หรือได้เห็นการดัดแปลงส่วนประกอบบางอย่าง (Boojum ของ zkSync, Plonky2, Starky)

ลิเกโร (2017)

Ligero นำเสนอระบบพิสูจน์อักษรที่สามารถบรรลุผลการพิสูจน์ที่มีขนาดเป็น

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

การพัฒนาใหม่บางอย่าง

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

แผนข้อผูกพันพหุนามใหม่ (2023)

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

ระบบข้อจำกัดที่ปรับแต่งได้ (2023)

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

บทสรุป

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

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

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