a16z: Lasso+Jolt ใช้ระบบ SNARK ที่มีประสิทธิภาพมากขึ้นได้อย่างไร

ชื่อเดิม: คำถามที่พบบ่อยทางเทคนิคเกี่ยวกับ Lasso, Jolt และความก้าวหน้าล่าสุดในการออกแบบ SNARK

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

การรวบรวมต้นฉบับ: Luccy, BlockBeats

หมายเหตุบรรณาธิการ: เมื่อวันที่ 20 พฤศจิกายน Ben Diamond และ Jim Posen (DP) แห่ง Ulvetanna ตีพิมพ์รายงานที่ปรับปรุง IOP แบบพหุนามโดยอิงจากการตรวจสอบผลรวมและโครงการความมุ่งมั่น Ligero/Brakedown ที่ผสมผสานข้อพิสูจน์ที่เร็วขึ้นและการพิสูจน์ที่ใหญ่กว่า และบูรณาการเข้ากับผลรวมที่ตรวจสอบ SNARK เช่น Lasso หลังจากที่ Justin Thaler พันธมิตรด้านการวิจัยของ a16z ได้ทำการวิเคราะห์เทคโนโลยีเชิงลึก นักวิจัยหลายคนได้ตั้งคำถามเกี่ยวกับเนื้อหาของบทความ

การอ่านที่เกี่ยวข้อง: a16z: Lasso+Jolt มุมมองใหม่เกี่ยวกับความมุ่งมั่นอย่างรวดเร็ว

คำถามที่พบบ่อยนี้รวมคำถาม 13 ข้อเพื่อตอบคำถามต่างๆ รวมถึงประสิทธิภาพของ Jolt Prover เหตุผลที่ DP เลือกฟังก์ชันแฮช Keccak และ Grøstl และความปลอดภัยของแผนความมุ่งมั่นแบบแฮช นอกจากนี้ คำตอบนี้ยังครอบคลุมถึงความสัมพันธ์พื้นฐานระหว่าง Lasso และ Jolt ข้อได้เปรียบด้านประสิทธิภาพของการใช้รหัส Reed-Solomon ข้อดีของ Ligero/Brakedown เหนือ FRI และคำอธิบายเกี่ยวกับเศรษฐกิจองค์ประกอบของความมุ่งมั่นของ DP ที่มีต่อ GF [2]

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

คำถามที่ 1: เมื่อเทียบกับการดำเนินการดั้งเดิมของโปรแกรม RISC-V คุณคิดว่า Jolt prover จะเร็วแค่ไหนเมื่อ Jolt ถูกปรับใช้ใหม่เพื่อใช้สัญญา DP

A：มีการประมาณการคร่าวๆ และการเก็งกำไรไว้ที่นี่ ผู้พิสูจน์ Jolt คาดว่าแต่ละขั้นตอนของ CPU RISC-V จะส่งข้อมูลประมาณ 800 บิต โดยใช้ประเภทข้อมูล 32 บิตและส่วนขยายการคูณ สองสิ่งที่ควรทราบ: ประการแรก คำสั่ง RISC-V บางคำสั่งได้รับการจัดการผ่านคำสั่งหลอกหลายคำสั่ง ตัวอย่างเช่น คำสั่งการหารทำงานโดยให้ผู้พิสูจน์หาเศษที่เหลือและตรวจสอบทั้งผ่านการตรวจสอบการคูณ การบวก และอสมการ ประการที่สอง การประมาณตัวเลขนี้อาจปรับเปลี่ยนได้เล็กน้อยหลังจากที่เราแยกวิเคราะห์การสลายตัวของตารางค้นหาของ GF [2128]

การใช้แผนข้อผูกมัดของ DP และสมมติว่าการเรียกซ้ำจะไม่กลายเป็นปัญหาคอขวด ต้นทุนข้อผูกมัดหลักในการคำนวณขั้นตอน T จะเป็นดังนี้

ขั้นแรก FFT เพิ่มเติมจะถูกนำไปใช้กับข้อมูลทั้งหมดประมาณ 200 Tbyte แม่นยำยิ่งขึ้น เครื่องพิสูจน์ Ligero/Brakedown ดำเนินการ FFT อิสระ O(√T) ขนาด O(√T) (ซึ่งเกี่ยวข้องกับงานทั้งหมดน้อยกว่าและสามารถขนานได้ดีกว่า) กว่าการดำเนินการ O(√T) FFT อิสระที่มีความยาว A FFT เดียวของ โอ(ท)) ประการที่สอง ประมาณ 200 เทราไบต์ถูกแฮชโดยใช้ฟังก์ชันแฮชมาตรฐาน เช่น Keccak หรือ SHA 2

ตามเชิงประจักษ์ DP พบว่า FFT และการแฮชมีความเท่าเทียมกันโดยประมาณในเวลาพิสูจน์

เมื่อใช้ Keccak hashing การประมาณประมาณ 70 รอบ RISC-V ต่อไบต์บ่งชี้ว่าการดำเนินการเหล่านี้จะช้ากว่าการรันโปรแกรม RISC-V ที่ไม่ได้รับการพิสูจน์ประมาณ 30,000 เท่า กล่าวอีกนัยหนึ่ง เพื่อพิสูจน์ว่าเครื่องพิสูจน์ Jolt รันโปรแกรม RISC-V Ψ อย่างถูกต้อง ตัวพิสูจน์เอง (ใช้งานใน RISC-V) จะต้องมีรอบอย่างน้อย 20,000 เท่ามากกว่าตัวมันเอง

ต้นทุนข้อผูกมัดเหล่านี้ เร็ว เพียงพอที่จะแนะนำว่าคอขวดของตัวพิสูจน์อาจอยู่ในการดำเนินการโดเมนที่จำกัดซึ่งดำเนินการในโปรโตคอลการตรวจสอบทั้งหมด แม้ว่าจะอนุญาตให้มีการปรับให้เหมาะสมบนโดเมนคุณลักษณะขนาดเล็กก็ตาม ดังนั้น ในการประมาณการคร่าวๆ ฉันเดาว่าโปรแกรมพิสูจน์ Jolt (ใช้งานใน RISC-V) จะช้ากว่าการรันโปรแกรม RISC-V ประมาณ 50,000 เท่า

การคำนวณทั้งหมดค่อนข้างไร้สาระ: ไม่น่าเป็นไปได้ที่ตัวพิสูจน์เองจะถูกนำไปใช้ใน RISC-V เมื่อ Jolt ถูกปรับใช้ แต่มันให้แนวคิดทั่วไปเกี่ยวกับวิธีการประมาณต้นทุนของตัวพิสูจน์ zkVM

แม้ว่าการชะลอตัว 50,000 เท่าดูเหมือนจะใหญ่โต แต่ก็เร็วกว่าค่าใช้จ่าย 1 ล้านเท่าที่ฉันคาดการณ์ไว้ในแง่ดีเมื่อประมาณ 18 เดือนที่แล้วถึง 20 เท่า เหตุผลหลักสำหรับการปรับปรุงนี้คือข้อมูลสัญญาที่เล็กลงซึ่งปลดล็อคโดย Lasso และ Jolt (และขนาดที่เล็กกว่าของมูลค่าสัญญาแต่ละรายการ) ส่วนที่เหลือเกิดจากรูปแบบความมุ่งมั่นที่ดีขึ้น (เช่น ความสามารถที่ดีขึ้นในการใช้ฟังก์ชันแฮชที่รวดเร็ว และใช้ประโยชน์จากค่าความมุ่งมั่นขนาดเล็กใน SNARK ที่ใช้แฮช)

คำถามที่ 2: DP จัดเตรียม SNARK ที่รวดเร็วสำหรับ Keccak และ Grøstl เหตุใดจึงเลือกฟังก์ชันแฮชเหล่านี้ ฟังก์ชันแฮชอื่นใดที่เหมาะกับเทคนิคเหล่านี้? หมายเหตุ BlockBeats: Grøstl เป็นฟังก์ชันแฮชที่เข้ารหัส

A：Keccak/SHA 3 เป็นตัวเลือกที่ชัดเจนเนื่องจากเป็นจุดคอขวดที่สำคัญสำหรับมาตรฐาน NIST, การคอมไพล์ล่วงหน้าของ Ethereum และ zkEVM ประเภท 1 SHA 3 เป็นมาตรฐาน NIST อย่างเป็นทางการ และ Keccak เป็น Ethereum ที่คอมไพล์ล่วงหน้า โดยไม่ขึ้นกับต้นทุน SNARK

DP พิจารณา Grøstl เนื่องจากควรนำไปสู่การพิสูจน์ที่เร็วขึ้น ขณะเดียวกันก็รักษาข้อดีหลายประการของ Keccak ไว้ โดยเฉพาะอย่างยิ่ง Grøstl ยืนหยัดต่อการตรวจสอบการเข้ารหัสอย่างเข้มงวด แม้ว่าท้ายที่สุดแล้วจะไม่ถูกเลือก เนื่องจากเข้าถึงรอบสุดท้ายของการแข่งขัน SHA-3 ของ NIST และใช้ AES S-box ด้วยคำแนะนำการเร่งความเร็ว AES AES-NI Grøstl จึงทำงานได้เร็วกว่า Keccak บนชิป Intel

สุภาษิตของ DP ควรเร็วกว่าสำหรับ Grøstl มากกว่า Keccak เพราะโดยพื้นฐานแล้ว Grøstl ถูกกำหนดโดยกำเนิดบน GF [28] ซึ่งหมายความว่าสุภาษิตของ DP สามารถมอบองค์ประกอบโดเมนน้อยกว่า Keccak (ดูคำถามที่ 9 สำหรับรายละเอียดว่าสิ่งนี้มีประโยชน์ต่อผู้พิสูจน์อย่างไร) โดยรวมแล้ว Grøstl ควรเหมาะสมกับ SNARK (แบบเรียกซ้ำ) มากกว่า Keccak เนื่องจากเร็วกว่าทั้งบนตัวพิสูจน์และบนชิป

SNARK ของ DP ไม่มีส่วนเกี่ยวข้องกับ Keccak และ Grøstl เทคนิคเหล่านี้ควรนำไปใช้กับฟังก์ชันแฮชอื่นๆ มากมาย ตัวอย่างเช่น DP เชื่อว่า SHA 2 น่าจะดีพอๆ กับ Keccak แต่ยังไม่ได้ศึกษาโดยละเอียด

คำถามที่ 3: ฉันคิดว่า Lasso/Jolt เป็นโซลูชันที่มีความมุ่งมั่นโดยยึดตามเส้นโค้งรูปไข่ใช่หรือไม่

A：ไม่ Lasso และ Jolt ไม่ได้มีเป้าหมายเฉพาะที่แผนข้อผูกมัดแบบ Curve แต่ในกรณีไม่กี่เดือนที่ผ่านมา เมื่อเทียบกับงานครั้งก่อน ข้อดีของมันชัดเจนที่สุดเมื่อใช้ร่วมกับคำสัญญาแบบ Curve-based เนื่องจากข้อผูกพันแบบอิงเส้นโค้งจ่ายราคาสูงเป็นพิเศษเมื่อผู้พิสูจน์ต้องยอมรับองค์ประกอบโดเมนสุ่ม ดังนั้นความสามารถใหม่ของ Lasso/Jolt ในการหลีกเลี่ยงสิ่งนี้จึงมีประสิทธิภาพที่น่าสนใจที่สุดเมื่อข้อผูกมัดเหล่านี้ถูกใช้อย่างมีอิทธิพล

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

อย่างไรก็ตาม แม้จะใช้คำสัญญาแบบแฮช Lasso และ Jolt ก็ปรับปรุงงานก่อนหน้านี้ทั้งสองประการ ประการแรก DP แสดงให้เห็นว่าข้อผูกพันแบบแฮชสามารถได้รับประโยชน์จากการมีองค์ประกอบโดเมนขนาดเล็กเท่านั้นที่มุ่งมั่นอย่างแข็งแกร่งมากกว่าแนวทางที่รู้จักก่อนหน้านี้ ตัวอย่างเช่น ในขณะที่แผนข้อผูกมัดในปัจจุบันมีค่าใช้จ่ายในการพิสูจน์เหมือนกันสำหรับการยอมรับค่า 1 บิต เช่นเดียวกับค่า 32 บิต แต่แผนของ DP นั้นถูกกว่าเกือบ 32 เท่าในการยอมรับค่า 1 บิต ประการที่สอง Lasso และ Jolt ไม่เพียงแต่รับประกันว่าผู้พิสูจน์ยืนยันกับองค์ประกอบโดเมนขนาดเล็กเท่านั้น แต่ยังรับประกันว่าผู้พิสูจน์ยืนยันกับองค์ประกอบโดเมนน้อยกว่า SNARK ที่ไม่ตรวจสอบผลรวม ในความเป็นจริง ใน Jolt เราคำนวณความซับซ้อนบิตรวมขององค์ประกอบโดเมนที่สัญญาไว้ทั้งหมดอย่างรอบคอบ และยืนยันว่ามีขนาดเล็กกว่างานที่ทำใน zkVM ที่มีอยู่มาก

เมื่อ Lasso/Jolt เปิดตัวเมื่อไม่กี่เดือนก่อน อาการสะอึกทางเทคนิคอีกอย่างหนึ่งได้นำข้อผูกพันแบบอิงเส้นโค้งมาไว้ข้างหน้า: รูปแบบข้อผูกพันแบบแฮชเพียงแบบเดียวที่มีขนาดการพิสูจน์พหุนามล็อกพหุนาม FRI ใช้สำหรับพหุนามแบบตัวแปรเดียว Lasso/Jolt ใช้พหุนามแบบหลายเชิงเส้น . เป็นที่รู้กันว่าการแปลงหลายอย่างจะปรับ FRI ให้เข้ากับแผนการผูกมัดที่เหมาะสมสำหรับพหุนามหลายเส้น แต่การแปลงเหล่านี้เพิ่มค่าใช้จ่ายในแง่ของเวลาพิสูจน์ ขนาดการพิสูจน์ หรือทั้งสองอย่างที่เราพิจารณาว่าไม่เป็นที่ต้องการอย่างมาก ขณะนี้ BaseFold อนุญาตให้มีการคอมมิตแบบหลายเชิงเส้น โดยตรง ด้วยขนาดการพิสูจน์พหุนามบันทึก แม้ว่าการพิสูจน์ผลลัพธ์จะช้ากว่า Brakedowns และใหญ่กว่า FRIs

แผนข้อผูกมัด Ligero/Brakedown ต่างจาก FRI ที่ใช้โดยตรงกับพหุนามหลายเส้นและมีตัวพิสูจน์ที่รวดเร็วมาก แต่ก่อนหน้านี้ การใช้การเรียกซ้ำเพื่อลดขนาดการพิสูจน์เป็นเรื่องยาก เนื่องจากเครื่องมือตรวจสอบความถูกต้องดำเนินการแฮชจำนวนมาก ซึ่งทำให้การเรียกซ้ำมีราคาแพง งานของ DP จะลดต้นทุนของการเรียกซ้ำนี้ลงอย่างมากโดยการจัดหา SNARK ที่เร็วขึ้นสำหรับแฮช

คำถามที่ 4: คุณไม่ได้บอกว่า Curve-based Commitment Scheme นั้นเร็วกว่า Hash-Based Scheme (เมื่อมีการสัญญาเพียงค่าเล็กๆ เท่านั้น เช่น Lasso/Jolt)? สิ่งนี้ไม่ขัดแย้งกับการรับรอง SNARK ของ DP ของคุณใช่หรือไม่

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

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

อย่างไรก็ตาม DP จะเร่งการคอมมิตแบบแฮช ทำให้มีประสิทธิภาพมากขึ้นเมื่อใช้โดเมนที่มีคุณสมบัติ 2 และช่วยให้ผู้พิสูจน์ใช้ใช้ประโยชน์จากค่าคอมมิตขนาดเล็กได้ดีขึ้น เมื่อเปรียบเทียบกับรูปแบบแบบแฮชที่มีอยู่ เช่น FRI) เมื่อเปรียบเทียบ ดังนั้นความคาดหวังในปัจจุบันของฉันคือในโดเมนที่มีคุณสมบัติ 2 Ligero/Brakedown จะเป็นหนทางข้างหน้า เว้นแต่จะพิสูจน์เป็นอย่างอื่นด้วยคำจำกัดความเฉพาะที่บนโดเมนที่มีขอบเขตจำกัด

โดยสรุป จนถึงทุกวันนี้ เหตุผลหลักว่าทำไมแผนข้อผูกมัดแบบแฮชโดยทั่วไปจึงถือว่าเร็วกว่าแบบแผนแบบโค้งก็คือ SNARK ที่ได้รับความนิยมอย่าง Plonk ต้องการให้ผู้พิสูจน์ยืนยันกับองค์ประกอบโดเมนสุ่มแทนที่จะเป็นองค์ประกอบโดเมนขนาดเล็ก ในขณะที่ ในกรณีนี้ โซลูชันสัญญาตามเส้นโค้งจะช้ามาก Lasso และ Jolt แสดงให้เห็นว่าผู้พิสูจน์ไม่จำเป็นต้องผูกมัดกับองค์ประกอบโดเมนสุ่ม ในกรณีนี้ การเปรียบเทียบจะมีความเหมาะสมยิ่งขึ้นเป็นอย่างน้อย จนถึงทุกวันนี้ โซลูชันแบบ Curve นั้นเร็วกว่าจริง ๆ แต่ด้วยการปรับปรุงของ DP สถานการณ์จะกลับกัน (ยกเว้นเมื่อกำหนดไว้ในโดเมนขนาดใหญ่)

คำถามที่ 5: คุณไม่ได้บอกว่าโครงการความมุ่งมั่นแบบแฮชมีความปลอดภัยน้อยกว่าใช่หรือไม่

A：ไม่มีอะไรที่ไม่ปลอดภัยโดยเนื้อแท้เกี่ยวกับแผนการผูกมัดแบบแฮช เช่น FRI หรือ Ligero/Brakedown อย่างไรก็ตาม โดยทั่วไปโปรเจ็กต์จะจัดลำดับความสำคัญของประสิทธิภาพมากกว่าความปลอดภัยโดยการปรับใช้ FRI บนการกำหนดค่าที่การโจมตีที่ทราบนั้นเกือบจะเป็นไปได้ และสมมติว่าการโจมตี FRI ที่ทราบเหล่านี้เกิดขึ้นได้อย่างเหมาะสมที่สุด

ข้อดีประการหนึ่งของโครงการข้อผูกมัด Ligero/Brakedown ก็คือ การคาดเดาหลักเกี่ยวกับ FRI กล่าวคือ ความปลอดภัยของการคาดเดาที่พารามิเตอร์ที่อยู่ติดกันนอกขอบเขตของ Johnson นั้นไม่เกี่ยวข้อง ดังนั้นผู้ออกแบบ SNARK จึงไม่มีแรงจูงใจที่จะใช้มันในการคาดเดาโดยอิงจากการรักษาความปลอดภัย .

ในทำนองเดียวกัน ฉันกังวลมานานแล้วเกี่ยวกับการใช้ฟังก์ชันแฮชที่ เป็นมิตรกับ SNARK อย่างเห็นได้ชัด (เช่น โพไซดอน) ในการปรับใช้ SNARK การรักษาความปลอดภัยของฟังก์ชันแฮชเหล่านี้ (แม้แต่ฟังก์ชันที่มีอายุยาวนานที่สุด) ได้รับการตรวจสอบน้อยกว่าฟังก์ชันแฮชมาตรฐานเช่น Keccak มาก

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

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

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

คำถามที่ 6: DP ใช้รหัส Reed-Solomon ในการดำเนินการตามโครงการข้อผูกมัดพหุนาม แต่ Brakedown สามารถใช้รหัสใดก็ได้ มันคุ้มค่าที่จะสำรวจโค้ดอื่น ๆ เพื่อให้ได้เปรียบด้านประสิทธิภาพที่เป็นไปได้หรือไม่?

A：ใช่.

คำถามที่ 7: Ligero/Brakedown มีประโยชน์ต่อผู้พิสูจน์มากกว่า FRI ในทางใดบ้าง

A：เวลาในการพิสูจน์ที่ดีขึ้นอย่างมากของ DP เมื่อยอมรับค่าที่น้อยมากนั้นเป็นเอกลักษณ์เฉพาะของ Ligero/Brakedown อย่างน้อยก็ในตอนนี้ นอกจากนี้: DP ไม่เพียงแต่ปรับปรุงเวลาของตัวพิสูจน์เมื่อยอมรับค่าเล็กๆ เท่านั้น แต่ยังปรับปรุงพื้นที่ของตัวพิสูจน์อีกด้วย นี่เป็นปัญหาคอขวดที่สำคัญ โดยเฉพาะอย่างยิ่งสำหรับ SNARK ที่ใช้แฮช ตัวอย่างเช่น ปัจจุบัน zkEVM ของ Polygon ต้องการพื้นที่มากกว่า 250 GB เพื่อพิสูจน์วงจรที่จัดการชุดธุรกรรมที่มีก๊าซประมาณ 10 ล้านครั้ง

Ligero/Brakedown มอบความยืดหยุ่นที่มากขึ้นในการใช้รหัสแก้ไขข้อผิดพลาด ในความเป็นจริง การปรับปรุงหลายอย่างของ DP ในการยอมรับค่าเล็กๆ สามารถทำได้ง่ายๆ โดยใช้โค้ดการต่อข้อมูลภายใน Ligero/Brakedown

เมื่อใช้รหัส Reed-Solomon ตัวพิสูจน์ Ligero/Brakedown จะดำเนินการ FFT ขนาดเล็กจำนวนมาก แทนที่จะเป็น FFT ขนาดใหญ่อันเดียว ซึ่งช่วยประหยัดเวลาในการทำงาน FFT ได้สองเท่า และเหมาะสำหรับการขนานกันมากกว่า

ในระดับเทคนิค FRI ยังกำหนดให้ทำทั้ง FFT และ IFFT ด้วย (ในทางเทคนิคแล้ว นี่เป็นเพราะว่า FRI จำเป็นต้องประเมินพหุนามที่กำหนดในหลายจุดจริงๆ) ผู้พิสูจน์ Ligero/Brakedown สามารถข้าม IFFT ได้ (ในระดับเทคนิค การข้าม IFFT เกิดจากความยืดหยุ่นที่เหนือกว่าของ Ligero/Brakedown ในการเลือกรหัสแก้ไขข้อผิดพลาด) หากคุณใช้ ปัจจัยเงินเฟ้อรีด-โซโลมอน เป็น 2 (ซึ่งเป็นปัจจัยเงินเฟ้อที่ช่วยปรับเวลาของผู้พิสูจน์ให้เหมาะสม) จะช่วยประหยัดเวลาของผู้พิสูจน์ได้อีก 33%

การพิสูจน์เชิงประเมินของ Ligero/Brakedown ไม่จำเป็นต้องให้ผู้พิสูจน์ทำ Merkle hashing เพิ่มเติม แต่ FRI ต้องการ แม้ว่าการเรียกร้อง FRI ส่วนใหญ่จะตัดจำหน่ายค่าใช้จ่ายในการประเมินการพิสูจน์มากกว่าพหุนามที่มุ่งมั่นหลายตัว

คำถามที่ 8: คุณช่วยสรุปวิธีที่ DP รับรองได้อย่างไรว่าองค์ประกอบ GF[2] ที่คอมมิตมีราคาถูกกว่าองค์ประกอบ GF[2^2] ที่คอมมิต ซึ่งราคาถูกกว่าองค์ประกอบ GF[2^4] ที่คอมมิต และอื่นๆ

A：เวลาที่ผู้พิสูจน์ใช้ในการยอมรับค่าจำนวนมากโดยใช้รูปแบบความมุ่งมั่นของ DP นั้นขึ้นอยู่กับจำนวนบิตทั้งหมดที่จำเป็นในการระบุค่าโดยประมาณเท่านั้น โดยที่บิต b ใช้เพื่อระบุค่าระหว่าง 0 ถึง 2b ค่าใช้จ่ายตัวพิสูจน์เพิ่มเติมใน SNARK ของ DP จะเพิ่มขึ้นตามจำนวนองค์ประกอบฟิลด์ที่ใช้ในการเข้ารหัสบิตเหล่านั้น (ดูรายละเอียด #9 ด้านล่าง) นี่คือวิธีที่ DP บรรลุเป้าหมายนี้

รูปแบบความมุ่งมั่นพหุนามของ Brakedown เข้ารหัสเวกเตอร์ย่อยของค่าที่จะกระทำโดยใช้รหัสแก้ไขข้อผิดพลาดที่จำเป็น สมมติว่าค่าต่างๆ ที่จะคอมมิตอยู่ใน GF[2] แต่เราต้องการให้การเข้ารหัสทำงานบนโดเมนที่ใหญ่กว่า GF[2^16] มีเหตุผลทางเทคนิคมากมายว่าทำไมเราถึงต้องการทำเช่นนี้ จริงๆ แล้วจำเป็นหากเราต้องการใช้การเข้ารหัสกับเวกเตอร์ที่มีความยาวไม่เกิน 216

เพื่อให้บรรลุเป้าหมายนี้ เราสามารถใช้การต่อโค้ดเข้าด้วยกัน ซึ่งเกี่ยวข้องกับการแบ่งค่า GF[ 2 ] ทั้งหมดออกเป็นส่วนๆ ขนาด 16 และ บรรจุ แต่ละส่วนของค่า 16 GF[ 2 ] ลงใน GF เดียว[ 2 ] ^ 16 ] องค์ประกอบฟิลด์ วิธีนี้จะช่วยลดจำนวนองค์ประกอบฟิลด์ที่ต้องกระทำโดยปัจจัย 16 จากนั้นเราสามารถใช้โค้ดแก้ไขข้อผิดพลาดใดๆ ที่ทำงานบนฟิลด์ GF[2^16] ซึ่งเรียกว่า โค้ดต่างประเทศ แต่ละสัญลักษณ์ของโค้ดเวิร์ดที่ได้นั้นสามารถ แตกไฟล์ ออกเป็นสิบหกองค์ประกอบ GF[2] และผลลัพธ์จะถูกเข้ารหัสโดยใช้ โค้ดภายใน ที่กำหนดใน GF[2]

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

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

คำถามที่ 9: เนื่องจากรูปแบบความมุ่งมั่นของ DP ทำให้การคอมมิตค่าใน { 0, 1 } มีราคาถูกมาก ทำไมไม่ลองให้ผู้พิสูจน์ยืนยันในการสลายตัวระดับบิตของค่าทั้งหมดที่ปรากฏในการคำนวณดูล่ะ นั่นคือ ทำไมไม่ใช้การคำนวณทั้งหมดโดยใช้วงจรบูลีน และปล่อยให้ SNARK กำหนดองค์ประกอบฟิลด์ สมบูรณ์ ให้กับแต่ละอินพุตบิตและเกตในวงจร

A：ใน SNARK สำหรับ Keccak นั้น DP ให้ผู้พิสูจน์ยืนยันเฉพาะค่าใน { 0, 1 } เท่านั้น แต่นี่ไม่ใช่ความคิดที่ดีเสมอไปในกรณีทั่วไป

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

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

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

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

คำถามที่ 1 0: อะไรคือข้อดีเฉพาะของ DP ที่ใช้ฟิลด์ที่มีลักษณะเฉพาะ 2?

A：มีมากมาย นี่คือตัวอย่างบางส่วน

DP ใช้ประโยชน์จากการก่อสร้างสนามทาวเวอร์อย่างกว้างขวาง ในบริบทของช่องที่มีลักษณะเฉพาะ 2 สิ่งนี้หมายถึงการสร้าง GF[22] เป็นส่วนขยายกำลังสองของ GF[2] จากนั้นสร้าง GF[24] เป็นส่วนขยายกำลังสองของ GF[4] จากนั้นจึงสร้าง GF[28 ] เป็นส่วนขยายกำลังสองของ GF[ 24 ] และอื่นๆ โดยเฉพาะอย่างยิ่งสำหรับลักษณะเฉพาะที่สอง เป็นที่รู้กันว่ามีการก่อสร้างหอคอยที่มีประสิทธิภาพมาก

โปรโตคอลการตรวจสอบผลรวมจะคำนวณ ∑x∈ 0, 1 ^ng(x) สำหรับพหุนามหลายตัวแปร g ขนาดของไฮเปอร์คิวบ์บูลีน { 0, 1 }n (และคิวบ์ย่อยของมัน) มีค่าเท่ากับ 2 ดังนั้นฟิลด์ย่อยจึงอยู่ในแนวเดียวกับคิวบ์ย่อยอย่างดี DP ใช้ประโยชน์จากสิ่งนี้และทำให้ง่ายต่อการบรรจุองค์ประกอบฟิลด์ขนาดเล็กจำนวนมากให้เป็นองค์ประกอบเดียวของฟิลด์ขยายที่ใหญ่กว่า

ปัจจุบัน DP ใช้การเข้ารหัส Reed-Solomon ในโครงการความมุ่งมั่นพหุนาม Ligero/Brakedown การเข้ารหัสรีด-โซโลมอนที่มีประสิทธิภาพต้องใช้ FFT แบบเสริม ซึ่งมีประสิทธิภาพมากในฟิลด์ที่มีคุณลักษณะสองประการ แต่ไม่ดีนักในฟิลด์อื่น อย่างไรก็ตาม การใช้การเข้ารหัสอื่นๆ สามารถหลีกเลี่ยงความจำเป็นในการใช้ FFT ได้อย่างสมบูรณ์

ฟิลด์ที่มีคุณสมบัติสองได้รับการจัดการอย่างดีในฮาร์ดแวร์จริง คอมพิวเตอร์ในโลกแห่งความเป็นจริงนั้นใช้ชนิดข้อมูลขนาดยกกำลังสอง คุณสามารถจัดวางข้อมูลที่ใหญ่ที่สุดได้อย่างสมบูรณ์แบบในรีจิสเตอร์ บรรทัดแคช ฯลฯ โดยไม่ต้องเติมช่องว่าง Intel ยังสร้างคำสั่งดั้งเดิมของชิปไว้ด้วย (คำสั่ง Galois Field New Instructions [GFNI]) เพื่อการคำนวณที่รวดเร็วเป็นพิเศษใน GF [28] เมื่อใช้การก่อสร้างแบบทาวเวอร์ สามารถใช้คำนวณ GF[2k] ที่เร็วมากได้ แม้แต่สำหรับ k > 8 ก็ตาม

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

A：ใช่ เกณฑ์การเรียกซ้ำ สำหรับ SNARK ที่ใช้ข้อผูกมัด Ligero/Brakedown นั้นค่อนข้างสูง ขีดจำกัดแบบเรียกซ้ำหมายถึงขนาดของการพิสูจน์ โดยที่ไม่สามารถสร้างการพิสูจน์ที่สั้นกว่านี้ได้โดยการใช้ SNARK ที่ใช้ Brakedown/Ligero แบบเรียกซ้ำกับตัวตรวจสอบ ฉันคาดว่าเกณฑ์การเรียกซ้ำจะอยู่ที่ไม่กี่ MB

หากคุณต้องการได้หลักฐานที่มีขนาดเล็กลง ฉันคิดว่าสามารถทำได้โดยการรวม SNARK เข้ากับหลักฐานที่มีขนาดเล็กกว่าอื่นๆ โปรดดูรายละเอียดในไตรมาสที่ 1 2 หากสมมติฐานนี้ผิดพลาด ไม่ควรมองว่าเป็นความล้มเหลวของ Binius แต่เป็นข้อกล่าวหาต่อความสามารถในการปรับขนาดของ SNARK ที่ได้รับความนิยมในปัจจุบัน เราจะพูดได้อย่างไรว่าสามารถปรับขนาดได้หากไม่สามารถพิสูจน์ได้ว่าข้อมูลจำนวนไม่กี่ MB ถูกแฮชในระยะเวลาที่เหมาะสม

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

คำถามที่ 1 2: สมมติว่าคุณต้องการรวมแผนความมุ่งมั่นของ DP เข้ากับ SNARK ที่ใช้เส้นโค้งรูปไข่ (เช่น Plonk หรือ Groth 16) เพื่อลดต้นทุนของผู้ตรวจสอบก่อนที่จะเผยแพร่การพิสูจน์บนห่วงโซ่ สิ่งนี้ไม่ต้องการการพิสูจน์ว่าเกี่ยวข้องกับเลขคณิตฟิลด์ ที่ไม่ใช่ท้องถิ่น หรือไม่ เนื่องจากตัวตรวจสอบของ DP ทำงานบน GF[2^128] ในขณะที่ SNARK แบบอิงเส้นโค้งใช้ฟิลด์ลำดับเฉพาะขนาดใหญ่

A：ใช่ นี่เป็นความท้าทายที่อาจเกิดขึ้น แต่ฉันเชื่อว่าจะสามารถพบวิธีแก้ปัญหาได้

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

สิ่งนี้ไม่ได้ขจัดปัญหาของเลขคณิตฟิลด์ที่ไม่ใช่เฉพาะที่ แต่สามารถบรรเทาได้มาก เนื่องจากสำหรับพหุนามที่มีขนาดใหญ่เพียงพอ เครื่องมือตรวจสอบ FRI จะดำเนินการทั้งหมดน้อยลง โดยเฉพาะอย่างยิ่งการดำเนินการภาคสนามน้อยกว่าที่เครื่องมือตรวจสอบ Ligero/Brakedown ดำเนินการ .

คำถามที่ 1 3: SNARK ที่ใช้ความมุ่งมั่นของ DP สามารถใช้ร่วมกับแผนการพับเช่น Nova ได้หรือไม่

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

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

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

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

ลิงค์เดิม