การวัดประสิทธิภาพ SNARK: ส่วนหน้า แบ็กเอนด์ และอนาคต

SNARK (อาร์กิวเมนต์ความรู้ที่ไม่โต้ตอบอย่างรวบรัด) เป็นแอปพลิเคชั่นการเข้ารหัสลับที่สำคัญในการค้นหาเบื้องต้นเพื่อขยายขนาดบล็อคเชน (เช่น โรลอัพ L2) และความเป็นส่วนตัว SNARKs ให้ใครบางคนพิสูจน์ให้ผู้ตรวจสอบที่ไม่น่าเชื่อถือ V (เช่น Ethereum blockchain) ที่พวกเขารู้ข้อมูลบางอย่าง (เช่น ชุดของธุรกรรมที่ถูกต้อง) วิธีที่ไร้เดียงสาในการพิสูจน์สิ่งนี้คือการส่งข้อมูลไปที่ Vซึ่งสามารถตรวจสอบความถูกต้องได้โดยตรง SNARK ทำได้เช่นเดียวกัน แต่ด้วยต้นทุนที่ดีกว่าเพื่อ V. โดยเฉพาะอย่างยิ่ง หลักฐาน SNARK ควรสั้นกว่าแบบไร้เดียงสาที่ประกอบด้วยข้อมูล (ดูรายละเอียดเพิ่มเติมที่ร่างหนังสือเรียนของฉัน หลักฐาน ข้อโต้แย้ง และความรู้ที่เป็นศูนย์. สำหรับข้อมูลเบื้องต้นเกี่ยวกับ SNARK โปรดดูที่ Sarah Meicklejohn's การเสนอ ที่ a16z crypto ซีรี่ส์วิจัยภาคฤดูร้อน.)

ค่าใช้จ่ายในการตรวจสอบสำหรับ SNARK อาจแตกต่างกันไป แต่มีความเข้าใจที่ดีและมักจะค่อนข้างดี ตัวอย่างเช่น, ลอนค หลักฐานค่าใช้จ่ายเกี่ยวกับ 290,000 แก๊ส เพื่อตรวจสอบบน Ethereum ในขณะที่การพิสูจน์ของ StarkWare มีค่าใช้จ่ายประมาณ 5 ล้านก๊าซ SNARK สามารถใช้งานได้ในการตั้งค่าที่หลากหลายแม้อยู่นอกบล็อคเชน — ตัวอย่างเช่น การใช้งานที่รวดเร็วแต่ไม่น่าเชื่อถือ เซิร์ฟเวอร์ และ ฮาร์ดแวร์. 

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

แต่ก่อนอื่น: วิธีใช้งาน SNARKs

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

โดยปกติ IR เป็นอินสแตนซ์ของความพอใจของวงจรบางประเภทที่เทียบเท่ากับ ψ. ซึ่งหมายความว่าวงจร C ใช้เป็นข้อมูลเข้า wเช่นเดียวกับอินพุตพิเศษบางอย่างที่มักเรียกว่า "คำแนะนำที่ไม่ได้กำหนดไว้" และรัน ψ on w. ข้อมูลคำแนะนำที่ใช้เพื่อช่วย C วิ่ง ψ, ในขณะที่รักษา C เล็ก. เช่น ทุกครั้ง ψ หารสองตัวเลข x และ y, ความฉลาด q และส่วนที่เหลือ r สามารถให้คำแนะนำแก่ Cและ C สามารถเช็คได้เลยว่า x = qy + r. เช็คนี้ถูกกว่าทำ C เรียกใช้อัลกอริทึมการหารเพื่อคำนวณ q และ r ตั้งแต่เริ่มต้น

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

อย่างที่เราจะได้เห็นกัน ค่าใช้จ่ายในการพิสูจน์ของแบ็กเอนด์ SNARK เพิ่มขึ้นด้วย C's ขนาด. การรักษา C ขนาดเล็กอาจเป็นสิ่งที่ท้าทาย เนื่องจากวงจรเป็นรูปแบบที่จำกัดมากในการแสดงการคำนวณ ประกอบด้วย ประตู, เชื่อมต่อโดย สายไฟ. แต่ละประตู g ถูกป้อนค่าบางอย่างและใช้ a มาก ฟังก์ชันอย่างง่ายสำหรับค่าเหล่านั้น ผลลัพธ์จะถูกป้อนเข้าประตู "ปลายน้ำ" ผ่านสายไฟที่เล็ดลอดออกมาจาก g.

ความสามารถในการปรับขนาด SNARK: จริงๆ แล้วต้องใช้เวลาเท่าไร?

คำถามสำคัญคือ ผู้พิสูจน์ SNARK ใช้เวลานานเท่าใด เมื่อเทียบกับการดำเนินการใหม่เพียงอย่างเดียว ψ บนข้อมูล? คำตอบคือ ค่าโสหุ้ยพิสูจน์ ของ SNARK เทียบกับ สอบพยานโดยตรง. นิพจน์หลังหมายถึงความจริงที่ว่าในการพิสูจน์ไร้เดียงสาซึ่ง P ส่ง w ไปยัง V, V การตรวจสอบ wความถูกต้องโดยการดำเนินการ ψ เกี่ยวกับมัน 

การแบ่งค่าใช้จ่ายของผู้พิสูจน์ออกเป็น "ค่าโสหุ้ยส่วนหน้า" และ "ค่าโสหุ้ยส่วนหลัง" จะเป็นประโยชน์ ถ้าจะประเมินวงจร C ประตูต่อประตูคือ F แพงกว่าวิ่งหลายเท่า ψจากนั้นเราบอกว่าค่าใช้จ่ายส่วนหน้าคือ F. หากใช้การพิสูจน์แบ็กเอนด์กับ C is B แพงกว่าการประเมินหลายเท่า C gate-by-gate แล้วเราว่า backend overhead คือ B. ค่าใช้จ่ายในการพิสูจน์ทั้งหมดคือ ผลิตภัณฑ์ F·B. ค่าโสหุ้ยแบบทวีคูณนี้สามารถเป็นกอบเป็นกำแม้ว่า F และ B เป็นรายบุคคลเจียมเนื้อเจียมตัว 

ในทางปฏิบัติ F และ B สามารถเป็นได้ทั้งประมาณ 1000 หรือใหญ่กว่า ซึ่งหมายความว่าค่าใช้จ่ายของผู้พิสูจน์ทั้งหมดที่เกี่ยวข้องกับการตรวจสอบพยานโดยตรงสามารถเป็น 1 ล้านถึง 10 ล้านหรือมากกว่า โปรแกรมที่ทำงานบนแล็ปท็อปเพียงหนึ่งวินาทีสามารถนำไปสู่การพิสูจน์ SNARK ได้อย่างง่ายดายซึ่งต้องใช้เวลาประมวลผลหลายสิบหรือหลายร้อยวัน (แบบเธรดเดียว) โชคดีที่งานนี้มักจะขนานกันได้ในขอบเขตที่แตกต่างกัน (ขึ้นอยู่กับ SNARK) 

โดยสรุป หากคุณต้องการใช้ SNARK ในแอปพลิเคชันในวันนี้ หนึ่งในสามสิ่งที่ต้องเป็นจริง:

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

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

การแยกส่วนหน้าและส่วนหลัง

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

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

แบ็กเอนด์ส่วนใหญ่สนับสนุนการวางนัยทั่วไปของวงจรเลขคณิตซึ่งมักเรียกว่าอินสแตนซ์ Rank-1 Constraint Satisfaction (R1CS) ยกเว้นที่โดดเด่นของ กรอธ16 และรุ่นก่อน SNARK เหล่านี้สามารถสร้างขึ้นเพื่อรองรับ IRs อื่น ๆ ได้เช่นกัน ตัวอย่างเช่น StarkWare ใช้สิ่งที่เรียกว่า Algebraic Intermediate Representation (AIR) ซึ่งคล้ายกับแนวคิดที่เรียกว่า เลขคณิตของ PlonKish ที่ PlonK และแบ็กเอนด์อื่นๆ รองรับ ความสามารถของแบ็กเอนด์บางส่วนในการรองรับ IR ทั่วไปมากขึ้น สามารถลดค่าใช้จ่ายของฟรอนต์เอนด์ที่สร้าง IR เหล่านั้นได้ 

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

แนวทางต่างๆ ของฟรอนท์เอนด์

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

วิธีส่วนหน้าที่เป็นที่นิยมวิธีหนึ่งคือการผลิตวงจรที่รัน CPU อย่างง่ายแบบทีละขั้นตอน หรือที่เรียกว่าเครื่องเสมือน (VM) นักออกแบบส่วนหน้าระบุชุดของ "การดำเนินการดั้งเดิม" ที่คล้ายคลึงกับคำสั่งการประกอบสำหรับโปรเซสเซอร์คอมพิวเตอร์จริง นักพัฒนาที่ต้องการใช้ฟรอนท์เอนด์จะเขียน "โปรแกรมตรวจสอบพยาน" โดยตรงในภาษาแอสเซมบลีหรือในภาษาระดับสูงเช่น Solidity และให้โปรแกรมของพวกเขาคอมไพล์เป็นโค้ดแอสเซมบลีโดยอัตโนมัติ 

ตัวอย่างเช่น StarkWare's ไคโร เป็นภาษาแอสเซมบลีที่จำกัดมาก ซึ่งคำสั่งแอสเซมบลีอนุญาตให้เพิ่มและคูณอย่างคร่าวๆ บนฟิลด์จำกัด การเรียกใช้ฟังก์ชัน และอ่านและเขียนไปยังหน่วยความจำที่ไม่เปลี่ยนรูป (เช่น เขียนครั้งเดียว) VM ของไคโรเป็นสถาปัตยกรรมแบบฟอนนอยมันน์ ซึ่งหมายความว่าวงจรที่สร้างขึ้นโดยส่วนหน้าจะใช้โปรแกรมไคโรเป็นข้อมูลสาธารณะและ "เรียกใช้" โปรแกรมกับพยาน ภาษาไคโรเป็นภาษาทัวริงสมบูรณ์ — แม้ว่าจะมีชุดคำสั่งที่จำกัด แต่ก็สามารถจำลองสถาปัตยกรรมมาตรฐานได้มากกว่า แม้ว่าการทำเช่นนั้นอาจมีราคาแพง ส่วนหน้าของไคโรเปลี่ยนโปรแกรมของไคโรที่ดำเนินการอยู่ T คำสั่งเบื้องต้นในสิ่งที่เรียกว่า “ดีกรี-2 อากาศด้วย T แถวและประมาณ 50 คอลัมน์” อะไร ตรงนี้หมายถึง ไม่สำคัญสำหรับโพสต์นี้ แต่เท่าที่เกี่ยวข้องกับผู้พิสูจน์ SNARK สิ่งนี้สอดคล้องกับวงจรที่มีระหว่าง 50 ถึง 100 ประตูสำหรับแต่ละ T ขั้นตอนของ CPU ไคโร 

RISC ศูนย์ ใช้แนวทางเดียวกันกับไคโร แต่ด้วยเครื่องเสมือนที่เรียกว่า สถาปัตยกรรม RISC-Vซึ่งเป็นสถาปัตยกรรมโอเพนซอร์ซที่มีระบบนิเวศซอฟต์แวร์ที่สมบูรณ์ซึ่งกำลังได้รับความนิยมเพิ่มขึ้น เนื่องจากเป็นชุดคำสั่งที่ง่ายมาก การออกแบบส่วนหน้า SNARK ที่มีประสิทธิภาพซึ่งสนับสนุนอาจใช้งานได้ค่อนข้างง่าย (อย่างน้อยก็สัมพันธ์กับสถาปัตยกรรมที่ซับซ้อน เช่น x86 หรือ ARM) ณ เดือนพฤษภาคม RISC Zero กำลังเปลี่ยนโปรแกรม การดำเนินงาน T คำแนะนำ RISC-V ดั้งเดิมใน AIRs องศา -5 ด้วย 3T แถวและ 160 คอลัมน์ ซึ่งสอดคล้องกับวงจรที่มีอย่างน้อย 500 ประตูต่อขั้นตอนของซีพียู RISC-V คาดว่าจะมีการปรับปรุงเพิ่มเติมในอนาคตอันใกล้นี้

โครงการ zkEVM ต่างๆ (เช่น zkSync 2.0, Scroll, zkEVM ของ Polygon) ทำให้เครื่องเสมือนเป็น (duh) Ethereum Virtual Machine กระบวนการในการเปลี่ยนทุกคำสั่ง EVM ให้เป็น "อุปกรณ์" ที่เทียบเท่ากัน (เช่น วงจรที่ปรับให้เหมาะสมการนำคำสั่งไปใช้) มีส่วนเกี่ยวข้องมากกว่าสถาปัตยกรรมไคโรและ RISC-V ที่เรียบง่ายกว่า ด้วยเหตุผลนี้และเหตุผลอื่นๆ, โครงการ zkEVM บางโครงการ ไม่ได้ใช้งานชุดคำสั่ง EVM โดยตรง แต่จะรวบรวมโปรแกรม Solidity ระดับสูงเป็นภาษาแอสเซมบลีอื่น ๆ ก่อนที่จะเปลี่ยนเป็นวงจร ผลการดำเนินงานจากโครงการเหล่านี้อยู่ระหว่างดำเนินการ

โครงการ “CPU emulator” เช่น RISC-V และ Cairo สร้างวงจรเดียวที่สามารถจัดการโปรแกรมทั้งหมดในภาษาแอสเซมบลีที่เกี่ยวข้อง แนวทางทางเลือกคือ "เหมือน ASIC" ซึ่งสร้างวงจรที่แตกต่างกันสำหรับโปรแกรมต่างๆ วิธีการแบบ ASIC นี้สามารถให้วงจรขนาดเล็กลงสำหรับบางโปรแกรม โดยเฉพาะอย่างยิ่งเมื่อคำสั่งการประกอบที่โปรแกรมดำเนินการในแต่ละขั้นตอนไม่ขึ้นอยู่กับอินพุตของโปรแกรม ตัวอย่างเช่น อาจหลีกเลี่ยงค่าใช้จ่ายส่วนหน้าทั้งหมดสำหรับโปรแกรมเส้นตรง เช่น การคูณเมทริกซ์ไร้เดียงสา แต่แนวทางของ ASIC ก็ดูมีข้อจำกัดอย่างมากเช่นกัน เท่าที่ฉันรู้ ไม่ทราบวิธีใช้เพื่อรองรับลูปโดยไม่มีขอบเขตการวนซ้ำที่กำหนดไว้ล่วงหน้า 

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

แบ็กเอนด์ SNARK บางรายการทำให้มีตัวเลือกฟิลด์ที่ยืดหยุ่นกว่าส่วนอื่นๆ ตัวอย่างเช่น หากแบ็กเอนด์ใช้กลุ่มการเข้ารหัส G, สนามของวงจรต้องตรงกับจำนวนขององค์ประกอบใน Gซึ่งสามารถจำกัดได้ นอกจากนี้ ไม่ใช่ทุกฟิลด์ที่รองรับอัลกอริธึม FFT ที่ใช้งานได้จริง 

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

บางโครงการได้เลือกที่จะทำงานในสาขาที่มีเลขคณิตเร็วเป็นพิเศษ ตัวอย่างเช่น, พลอนกี้2 และอื่น ๆ ใช้เขตข้อมูลของลักษณะ 2⁶⁴ - 2³² +1 เนื่องจากการคำนวณในช่องนี้สามารถดำเนินการได้เร็วกว่าในฟิลด์ที่มีโครงสร้างน้อยกว่าหลายเท่า อย่างไรก็ตาม การใช้คุณลักษณะเล็กๆ น้อยๆ ดังกล่าวอาจนำไปสู่ความท้าทายในการแสดงเลขคณิตจำนวนเต็มผ่านการดำเนินการภาคสนามอย่างมีประสิทธิภาพ (เช่น การคูณจำนวนเต็ม 32 บิตที่ไม่ได้ลงนามอาจให้ผลลัพธ์ที่มากกว่าคุณลักษณะของฟิลด์) 

 แต่ไม่ว่าอย่างไร สำหรับ SNARK ยอดนิยมทั้งหมดในปัจจุบัน เพื่อให้ได้ความปลอดภัย 128 บิต (โดยไม่ต้องเพิ่มค่าใช้จ่ายในการตรวจสอบ) พวกเขาต้องทำงานในพื้นที่ที่มีขนาดใหญ่กว่า 2¹²⁸. เท่าที่ฉันสามารถบอกได้ นี่หมายความว่าการดำเนินการแต่ละฟิลด์จะต้องมีการคูณด้วยเครื่องจักร 64 บิตอย่างน้อยสิบครั้ง และมีการเพิ่มเติมและการดำเนินการระดับบิตที่มากขึ้น ดังนั้น อย่างน้อยควรคำนึงถึงลำดับความสำคัญของค่าโสหุ้ยส่วนหน้าเป็นอย่างน้อย เนื่องจากความจำเป็นในวงจรที่ทำงานบนเขตข้อมูลที่มีขอบเขตจำกัด 

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

ปัญหาคอขวดของแบ็กเอนด์คืออะไร?

SNARKs สำหรับความเพียงพอของวงจรได้รับการออกแบบโดยรวมโปรโตคอลที่มีความปลอดภัยทางทฤษฎีที่เรียกว่า "พหุนาม IOP” ด้วยโปรโตคอลการเข้ารหัสที่เรียกว่า “โครงการพันธะสัญญาพหุนาม” ในกรณีส่วนใหญ่ คอขวดที่เป็นรูปธรรมสำหรับผู้พิสูจน์คือโครงการผูกมัดพหุนาม โดยเฉพาะอย่างยิ่ง SNARK เหล่านี้มีผู้พิสูจน์ที่เข้ารหัสลับในชื่อพหุนามหนึ่งตัวหรือมากกว่าซึ่งมีระดับ (อย่างน้อย) |C|, จำนวนเกทในวงจร C. 

ในทางกลับกัน คอขวดที่เป็นรูปธรรมภายในโครงการผูกมัดพหุนามจะขึ้นอยู่กับรูปแบบที่ใช้และขนาดวงจร แต่จะเป็นหนึ่งในสามการดำเนินการต่อไปนี้เสมอ: การคำนวณ FFT การยกกำลังในกลุ่มการเข้ารหัสหรือ Merkle-hashing. โดยทั่วไปแล้ว Merkle-hashing จะเป็นคอขวดก็ต่อเมื่อวงจรมีขนาดเล็กเท่านั้น ดังนั้นเราจะไม่พูดถึงเรื่องนี้เพิ่มเติม 

คำมั่นสัญญาพหุนามตามบันทึกที่ไม่ต่อเนื่อง

ในพันธะพหุนามตามความแข็งของปัญหาลอการิทึมที่ไม่ต่อเนื่องในกลุ่มการเข้ารหัส G (เคแซด, กระสุน, Doryและ Hyrax-กระทำ) ผู้พิสูจน์ต้องคำนวณ a Pedersen vector ข้อผูกพัน ถึงสัมประสิทธิ์ของพหุนาม สิ่งนี้เกี่ยวข้องกับการยกกำลังหลายตัวซึ่งมีขนาดเท่ากับดีกรีของพหุนาม ใน SNARK ระดับนี้โดยทั่วไปคือขนาด |C| ของวงจร C.

ทำอย่างไร้เดียงสา การทวีคูณของขนาด |C| ต้องการประมาณ 1.5·|C|·เข้าสู่ระบบ |G| ≈ 400·|C| การดำเนินงานกลุ่ม โดยที่ |G| หมายถึงจำนวนองค์ประกอบในกลุ่ม G. อย่างไรก็ตาม มีวิธีการที่เรียกว่าอัลกอริธึมของ Pippenger ซึ่งสามารถลดสิ่งนี้ได้โดยใช้ค่า log . คร่าวๆ |C|. สำหรับวงจรขนาดใหญ่ (เช่น |C- 225) บันทึกนี้ |C| แฟคเตอร์สามารถเป็น 25 หรือมากกว่านั้นได้อย่างชัดเจน นั่นคือ สำหรับวงจรขนาดใหญ่ เราคาดว่าพันธะเวคเตอร์ Pedersen อาจคำนวณได้น้อยกว่า 10 เล็กน้อย·|C| การดำเนินงานกลุ่ม การดำเนินการแต่ละกลุ่มมีแนวโน้มที่จะ (เหมือนสนามเบสบอลที่หยาบมาก) ประมาณ 10 เท่าช้ากว่าการดำเนินการในสนามแบบจำกัด SNARKs ที่ใช้พันธะพหุนามเหล่านี้มีราคาแพงสำหรับ P ราวๆ 100·|C| การดำเนินงานภาคสนาม 

น่าเสียดายที่ SNARK ที่มีอยู่มีค่าใช้จ่ายเพิ่มเติมนอกเหนือจากปัจจัย 100x ข้างต้น ตัวอย่างเช่น:

• สปาร์ตันต้องทำ ตัวพิสูจน์ของ Hyrax ซึ่งใช้พันธะพหุนามของ Hyrax |C|^½ เลขยกกำลังหลายตัวแต่ละขนาด |C|^½ทำให้การเร่งความเร็วจากอัลกอริธึมของ Pippenger อ่อนลงลงประมาณสองเท่า 
• In กรอธ16, P ต้องทำงานในกลุ่มที่เป็นมิตรกับการจับคู่ ซึ่งโดยทั่วไปแล้วการดำเนินการจะช้ากว่ากลุ่มที่ไม่เป็นมิตรกับการจับคู่อย่างน้อย 2 เท่า P ยังต้องทำการยกกำลังหลายตัว 3 ตัวแทนที่จะเป็น 1 เมื่อรวมเข้าด้วยกัน ส่งผลให้อย่างน้อยปัจจัยเพิ่มเติม-6 ช้าลงเมื่อเทียบกับ 100·|C| ประมาณการข้างต้น 
• ปลามาร์ลิน และ ลอนค ยังต้องอาศัยการจับคู่ และผู้พิสูจน์ต้องผูกมัดกับพหุนามมากกว่า 3 พหุนาม 
• สำหรับ SNARK ใด ๆ ที่ใช้ กระสุน (เช่น, รัศมี 2ซึ่งก็คือ PlonK คร่าวๆ แต่ด้วย Bulletproofs แทนที่จะเป็น KZG พหุนามที่ผูกมัด) ผู้พิสูจน์ต้องคำนวณลอการิทึมการยกกำลังหลายตัวในช่วง "เปิด" ของแผนการผูกมัด และสิ่งนี้จะลบการเร่งความเร็วของ Pippenger ส่วนใหญ่ 

โดยสรุป SNARK ที่รู้จักโดยใช้ข้อผูกมัดเวกเตอร์ Pedersen ดูเหมือนจะมีค่าใช้จ่ายส่วนหลังอย่างน้อย 200x และสูงถึง 1000x หรือมากกว่า 

คำมั่นสัญญาพหุนามอื่น ๆ

สำหรับ SNARKs ที่ใช้พันธะพหุนามอื่น ๆ (เช่น ฟรี และ Ligero-มุ่งมั่น) คอขวดคือผู้พิสูจน์จำเป็นต้องดำเนินการ FFT จำนวนมาก ตัวอย่างเช่น ใน AIR ระดับ 2 ที่ผลิตโดยไคโร (มี 51 คอลัมน์และ T หนึ่งแถวต่อหนึ่งขั้นตอนของ CPU ไคโร) ตัวพิสูจน์ที่ปรับใช้ของ StarkWare ทำอย่างน้อย 2 FFT ต่อคอลัมน์ โดยมีความยาวระหว่าง 16 ·T และ 32 ·T. ค่าคงที่ 16 และ 32 ขึ้นอยู่กับพารามิเตอร์ภายในของ FRI ที่กำหนดโดย StarkWare และสามารถลดลงได้ — แต่ด้วยต้นทุนการตรวจสอบที่เพิ่มขึ้น 

ในแง่ดี FFT ที่มีความยาว 32·T ใช้เวลาประมาณ 64·T·บันทึก(32T) การคูณภาคสนาม ซึ่งหมายความว่าแม้สำหรับค่าที่ค่อนข้างน้อยของ T (เช่น, T ≥ 2²⁰) จำนวนการดำเนินการภาคสนามต่อคอลัมน์อย่างน้อย 64·25·T= 1600·T. ดังนั้นค่าใช้จ่ายแบ็กเอนด์จึงดูเหมือนจะเป็นอย่างน้อยในหลักพัน นอกจากนี้ อาจเป็นไปได้ว่า FFT ขนาดใหญ่จะมีปัญหาคอขวดจากแบนด์วิดท์หน่วยความจำมากกว่าการดำเนินการภาคสนาม 

ในบางบริบท ค่าใช้จ่ายแบ็กเอนด์ของ SNARK ที่ดำเนินการ FFT ขนาดใหญ่สามารถลดลงได้ด้วยเทคนิคที่เรียกว่าการรวมการพิสูจน์ สำหรับโรลอัพ นี่หมายความว่า P (บริการยกเลิก) แบ่งธุรกรรมชุดใหญ่ออกเป็น 10 ชุดย่อย สำหรับชุดเล็กแต่ละชุด i, P สร้างหลักฐาน SNARK πi ของความถูกต้องของชุดงาน แต่ P ไม่ได้โพสต์หลักฐานเหล่านี้ไปยัง Ethereum เนื่องจากจะทำให้ต้นทุนก๊าซเพิ่มขึ้นเกือบ 10 เท่า แทนที่จะใช้ SNARK อีกครั้ง คราวนี้เพื่อสร้างหลักฐาน π กำหนดว่า P รู้ π₁ , ...,π₁₀. นั่นคือพยานว่า P การอ้างว่ารู้คือข้อพิสูจน์สิบประการ π₁,…,พาย₁₀และการตรวจสอบพยานโดยตรงจะใช้ขั้นตอนการตรวจสอบ SNARK กับหลักฐานแต่ละฉบับ บทพิสูจน์เดียวนี้ π ถูกโพสต์ไปยัง Ethereum 

ในพันธะพหุนามเช่น FRI และ Ligero-commit มีความตึงเครียดระหว่าง P เวลาและ V ค่าใช้จ่าย โดยที่พารามิเตอร์ภายในทำหน้าที่เป็นปุ่มที่สามารถแลกเปลี่ยนระหว่างกัน เนื่องจาก π₁ ,…,พาย₁₀ ไม่ได้โพสต์ไปยัง Ethereum ลูกบิดสามารถปรับได้ดังนั้นการพิสูจน์เหล่านี้ มีขนาดใหญ่และผลิตได้เร็วกว่า เฉพาะในโปรแกรมสุดท้ายของ SNARK เพื่อรวม π₁ ,…,พาย₁₀ เป็นหลักฐานชิ้นเดียว π, แผนความมุ่งมั่นจำเป็นต้องได้รับการกำหนดค่าเพื่อให้แน่ใจว่ามีการพิสูจน์ขนาดเล็กหรือไม่ 

StarkWare วางแผนที่จะปรับใช้การรวมการพิสูจน์ รำมะร่อ. นอกจากนี้ยังเป็นจุดสนใจของโครงการเช่น พลอนกี้2.

อะไรคือคอขวดอื่นๆ ของความสามารถในการปรับขนาด SNARK?

โพสต์นี้เน้นพิสูจน์ เวลาแต่ค่าใช้จ่ายในการพิสูจน์อื่นๆ อาจเป็นปัญหาคอขวดของความสามารถในการปรับขนาดได้ ตัวอย่างเช่น สำหรับแบ็กเอนด์ SNARK จำนวนมาก ผู้พิสูจน์ต้องจัดเก็บองค์ประกอบฟิลด์หลายรายการสำหรับแต่ละเกตใน Cและต้นทุนพื้นที่นี้อาจมีขนาดใหญ่ ตัวอย่างเช่น โปรแกรม ψ การทำงานในหนึ่งวินาทีบนแล็ปท็อปสามารถดำเนินการขั้นพื้นฐานได้นับพันล้านครั้งบนโปรเซสเซอร์ที่ทันสมัย อย่างที่เราได้เห็นแล้ว โดยทั่วไปแล้วเราควรคาดหวัง C ต้องใช้มากกว่า 100 ประตูต่อการดำเนินการดังกล่าว นี่หมายถึงประตู 100 แสนล้าน ซึ่งขึ้นอยู่กับ SNARK อาจหมายถึงพื้นที่นับสิบหรือหลายร้อยเทราไบต์สำหรับ P. 

อีกตัวอย่างหนึ่ง: SNARK ยอดนิยมมากมาย (เช่น ลอนค, ปลามาร์ลิน, กรอธ16) ต้องการ "พิธีการติดตั้งที่เชื่อถือได้" ที่ซับซ้อนเพื่อสร้าง "คีย์การพิสูจน์" ที่มีโครงสร้าง ซึ่งผู้พิสูจน์จะต้องเก็บไว้ เท่าที่ฉันรู้ พิธีที่ใหญ่ที่สุด สร้างคีย์การพิสูจน์ที่สามารถรองรับวงจรได้ประมาณ2²⁸≈250 ล้านประตู คีย์การพิสูจน์มีขนาดหลายสิบกิกะไบต์ 

ในบริบทที่การรวมการพิสูจน์เป็นไปได้ คอขวดเหล่านี้สามารถบรรเทาลงได้อย่างมาก 

มองไปข้างหน้า: โอกาสสำหรับ SNARKs ที่ปรับขนาดได้มากขึ้น

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

ฉันคิดว่าเราจะ - ถึงจุดหนึ่ง อันดับแรก แบ็กเอนด์ที่เร็วที่สุดในปัจจุบัน (เช่น สปาร์ตัน และ เบรกดาวน์และ SNARK อื่น ๆ ที่รวม โปรโตคอลตรวจสอบผลรวม ด้วยพันธะพหุนาม) มีหลักฐานจำนวนมาก — โดยทั่วไปแล้วจะเป็นสแควร์รูทในขนาดของวงจร — ดังนั้นผู้คนจึงไม่ได้ใช้มันจริงๆ ฉันคาดว่าขนาดการพิสูจน์และเวลาในการตรวจสอบจะลดลงอย่างมีความหมายในอนาคตอันใกล้ผ่านองค์ประกอบเชิงลึกหนึ่งที่มี SNARK ที่มีหลักฐานขนาดเล็ก คล้ายกับการรวมหลักฐาน หมายความว่าผู้พิสูจน์จะสร้างการพิสูจน์ SNARK ก่อน π ด้วย SNARK “พิสูจน์ได้รวดเร็ว พิสูจน์ได้ขนาดใหญ่” แต่ไม่ส่ง π ไปยัง V. ค่อนข้าง P จะใช้ SNARK พิสูจน์ขนาดเล็กเพื่อสร้างหลักฐาน π' ที่มันรู้ π, และส่ง π' ไปยัง V. สิ่งนี้สามารถกำจัดลำดับความสำคัญของค่าใช้จ่ายแบ็กเอนด์ของ SNARK ที่ได้รับความนิยมในปัจจุบัน 

ประการที่สอง การเร่งด้วยฮาร์ดแวร์สามารถช่วยได้ กฎทั่วไปที่หยาบมากคือ GPU สามารถซื้อการเร่งความเร็ว 10 เท่าบน CPU และ ASIC สามารถเพิ่มความเร็วได้ 10 เท่าสำหรับ GPU อย่างไรก็ตาม ฉันมีความกังวลสามประการในเรื่องนี้ ประการแรก FFT ขนาดใหญ่อาจมีปัญหาคอขวดโดยแบนด์วิดท์หน่วยความจำมากกว่าการดำเนินการภาคสนาม ดังนั้น SNARK ที่ดำเนินการ FFT ดังกล่าวอาจเห็นการเร่งความเร็วที่จำกัดจากฮาร์ดแวร์เฉพาะทาง ประการที่สอง ในขณะที่โพสต์นี้เน้นที่คอขวดของคำมั่นสัญญาพหุนาม SNARK จำนวนมากต้องการให้ผู้พิสูจน์ดำเนินการอื่น ๆ ที่มีราคาไม่แพงเพียงเล็กน้อยเท่านั้น การทำลายคอขวดของการผูกมัดพหุนาม (เช่น เร่งการยกกำลังหลายตัว ใน SNARK แบบแยกบันทึก) อาจทำให้การดำเนินการคอขวดแบบใหม่ไม่ได้ดีไปกว่าแบบเดิมมากนัก (ตัวอย่างเช่น SNARKs รวมทั้ง Groth16, Marlin และ PlonK ยังมีตัวพิสูจน์ที่ทำ FFTs นอกเหนือจากการยกกำลังหลายตัว) ในที่สุด ทุ่งนาและเส้นโค้งวงรีที่นำไปสู่ ​​SNARK ที่มีประสิทธิภาพที่สุดอาจยังคงพัฒนาต่อไปในบางครั้ง และอาจสร้างความท้าทายสำหรับการเร่งความเร็วของผู้พิสูจน์ตาม ASIC

ในส่วนหน้า เราอาจพบมากขึ้นว่าแนวทาง "ตัวจำลอง CPU" ของโครงการต่างๆ เช่น Cairo, RISC Zero, zkEVM และอื่นๆ ปรับขนาดได้ค่อนข้างดี (ในแง่ของประสิทธิภาพ) ด้วยความซับซ้อนของชุดคำสั่ง CPU อันที่จริงนี่คือความหวังของโครงการ zkEVM ต่างๆ ซึ่งอาจหมายความว่าในขณะที่ค่าใช้จ่ายส่วนหน้ายังคงมีลำดับความสำคัญสามระดับขึ้นไป ส่วนหน้าจัดการเพื่อรองรับ VM ที่ตรงกับสถาปัตยกรรม CPU จริงมากขึ้น ข้อกังวลในการตอบโต้คือส่วนหน้าอาจซับซ้อนและยากต่อการตรวจสอบ เนื่องจากอุปกรณ์ที่เข้ารหัสด้วยมือซึ่งใช้คำสั่งที่ซับซ้อนมากขึ้นมีเพิ่มมากขึ้น วิธีการตรวจสอบอย่างเป็นทางการมีแนวโน้มที่จะมีบทบาทสำคัญในการจัดการกับข้อกังวลนี้ 

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

***

จัสติน ทาเลอร์ is รองศาสตราจารย์ที่มหาวิทยาลัยจอร์จทาวน์ ก่อนร่วมงานกับจอร์จทาวน์ เขาใช้เวลาสองปีในฐานะนักวิทยาศาสตร์การวิจัยที่ Yahoo Labs ในนิวยอร์ก ก่อนหน้านั้นเขาเคยเป็นนักวิจัยที่ สถาบัน Simons สำหรับทฤษฎีคอมพิวเตอร์ ที่ UC Berkeley 

***

กิตติมศักดิ์: ฉันรู้สึกขอบคุณ เอเลน่า เบอร์เกอร์ สำหรับการเสนอหัวข้อของโพสต์นี้และเพื่อ อารสุอรุณ โจเซฟ บอนโนและ แซม แร็กส์เดล สำหรับความคิดเห็นที่เฉียบขาด ขอขอบคุณเป็นพิเศษกับบรรณาธิการของฉัน ซัลลิแวนทิม.

***

ความคิดเห็นที่แสดงในที่นี้เป็นความคิดเห็นของบุคลากร AH Capital Management, LLC (“a16z”) ที่ยกมาและไม่ใช่ความคิดเห็นของ a16z หรือบริษัทในเครือ ข้อมูลบางอย่างในที่นี้ได้รับมาจากแหล่งบุคคลที่สาม รวมถึงจากบริษัทพอร์ตโฟลิโอของกองทุนที่จัดการโดย a16z ในขณะที่นำมาจากแหล่งที่เชื่อว่าเชื่อถือได้ a16z ไม่ได้ตรวจสอบข้อมูลดังกล่าวอย่างอิสระและไม่รับรองความถูกต้องของข้อมูลหรือความเหมาะสมสำหรับสถานการณ์ที่กำหนด นอกจากนี้ เนื้อหานี้อาจรวมถึงโฆษณาของบุคคลที่สาม a16z ไม่ได้ตรวจทานโฆษณาดังกล่าวและไม่ได้รับรองเนื้อหาโฆษณาใด ๆ ที่อยู่ในนั้น

เนื้อหานี้จัดทำขึ้นเพื่อวัตถุประสงค์ในการให้ข้อมูลเท่านั้น และไม่ควรใช้เป็นคำแนะนำทางกฎหมาย ธุรกิจ การลงทุน หรือภาษี คุณควรปรึกษาที่ปรึกษาของคุณเองในเรื่องเหล่านั้น การอ้างอิงถึงหลักทรัพย์หรือสินทรัพย์ดิจิทัลใดๆ มีวัตถุประสงค์เพื่อเป็นตัวอย่างเท่านั้น และไม่ถือเป็นการแนะนำการลงทุนหรือข้อเสนอเพื่อให้บริการที่ปรึกษาการลงทุน นอกจากนี้ เนื้อหานี้ไม่ได้มุ่งไปที่หรือมีไว้สำหรับการใช้งานโดยนักลงทุนหรือนักลงทุนที่คาดหวัง และไม่อาจเชื่อถือได้ไม่ว่าในกรณีใดๆ เมื่อตัดสินใจลงทุนในกองทุนใดๆ ที่จัดการโดย a16z (การเสนอให้ลงทุนในกองทุน a16z จะกระทำโดยบันทึกเฉพาะบุคคล ข้อตกลงจองซื้อ และเอกสารที่เกี่ยวข้องอื่นๆ ของกองทุนดังกล่าว และควรอ่านให้ครบถ้วน) การลงทุนหรือบริษัทพอร์ตการลงทุนใดๆ ที่กล่าวถึง อ้างถึง หรือ ที่อธิบายไว้ไม่ได้เป็นตัวแทนของการลงทุนทั้งหมดในยานพาหนะที่จัดการโดย a16z และไม่สามารถรับประกันได้ว่าการลงทุนนั้นจะให้ผลกำไรหรือการลงทุนอื่น ๆ ในอนาคตจะมีลักษณะหรือผลลัพธ์ที่คล้ายคลึงกัน รายการการลงทุนที่ทำโดยกองทุนที่จัดการโดย Andreessen Horowitz (ไม่รวมการลงทุนที่ผู้ออกไม่อนุญาตให้ a16z เปิดเผยต่อสาธารณะและการลงทุนที่ไม่ได้ประกาศในสินทรัพย์ดิจิทัลที่ซื้อขายในตลาดหลักทรัพย์) มีอยู่ที่ https://a16z.com/investments /.

แผนภูมิและกราฟที่ให้ไว้ภายในมีวัตถุประสงค์เพื่อให้ข้อมูลเท่านั้น และไม่ควรใช้ในการตัดสินใจลงทุนใดๆ ผลการดำเนินงานในอดีตไม่ได้บ่งบอกถึงผลลัพธ์ในอนาคต เนื้อหาพูดตามวันที่ระบุเท่านั้น การคาดการณ์ การประมาณการ การคาดการณ์ เป้าหมาย โอกาส และ/หรือความคิดเห็นใดๆ ที่แสดงในเอกสารเหล่านี้อาจเปลี่ยนแปลงได้โดยไม่ต้องแจ้งให้ทราบและอาจแตกต่างหรือขัดแย้งกับความคิดเห็นที่แสดงโดยผู้อื่น โปรดดู https://a16z.com/disclosures สำหรับข้อมูลสำคัญเพิ่มเติม