Binary GKR: ระบบพิสูจน์ความรู้เป็นศูนย์ใหม่ที่ทำลายสถิติความเร็วของการพิสูจน์ Keccak

ผู้แต่งต้นฉบับ: เหว่ยเคิง เฉิน

ใน Ethereum Virtual Machine (EVM) ฟังก์ชันแฮช Keccak ถูกใช้กันอย่างแพร่หลายในการสร้างและตรวจยืนยันสเตตทรี (Merkle Patricia Trees) โดยคิดเป็นค่าใช้จ่ายทางการคำนวณหลักในการพิสูจน์ความรู้เป็นศูนย์ วิธีการพิสูจน์อย่างมีประสิทธิภาพว่า Keccak เป็นปัญหาทางเทคนิคที่ยังไม่ได้รับการแก้ไขมายาวนานในสาขาการพิสูจน์ความรู้เป็นศูนย์

เพื่อรับมือกับความท้าทายนี้ ทีมงาน Polyhedra ได้เปิดตัว Binary GKR ซึ่งเป็นระบบพิสูจน์ประสิทธิภาพสูงที่ออกแบบมาสำหรับ Keccak และการดำเนินการแบบไบนารีอื่นๆ

ความคืบหน้าหลัก: ความเร็วการป้องกัน Keccak เพิ่มขึ้น 5.7 เท่า

Binary GKR ประสบความสำเร็จในการพิสูจน์ความรู้เป็นศูนย์แบบ Keccak ที่เร็วที่สุดจนถึงปัจจุบัน ซึ่งเร็วกว่าโซลูชันที่ดีที่สุดของระบบพิสูจน์ไบนารี FRI-Binius ที่มีอยู่เดิมถึง 5.7 เท่า ความก้าวหน้าครั้งนี้ไม่เพียงแต่มีความสำคัญเชิงทฤษฎีเท่านั้น แต่ยังเปิดโอกาสใหม่ๆ สำหรับการใช้งานในทางปฏิบัติอีกด้วย

แนวโน้มการใช้งาน: “รถข้างเร่งความเร็วสากล” ของ zkEVM

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

Polyhedra จะยังคงส่งเสริมการผลิตและกระบวนการโอเพ่นซอร์สของ Binary GKR ต่อไป ทำให้สามารถอัปเกรดสถาปัตยกรรม zk ใน Ethereum และระบบนิเวศน์ที่กว้างขึ้นได้

Keccak: จอกศักดิ์สิทธิ์แห่งความรู้ระดับศูนย์ Ethereum

Ethereum กำลังพัฒนาไปเรื่อย ๆ ไปสู่เลเยอร์ 1 ที่เป็นหลักฐานความรู้เป็นศูนย์ โครงการ Ethproofs ซึ่งประกอบด้วยทีมงาน 21 ทีมและครอบคลุมการใช้งาน ZK(E)VM จำนวน 22 รายการ กำลังพยายามพิสูจน์บล็อคในประวัติศาสตร์ของ Ethereum ให้สมบูรณ์ ซึ่งถือเป็นการก้าวไปข้างหน้าอีกก้าวสำคัญ

บน เว็บไซต์อย่างเป็นทางการของ Ethproofs คุณสามารถดูความคืบหน้าของหลายทีมได้แบบเรียลไทม์: โปรเจ็กต์ต่างๆ เช่น ZkCloud, Succinct, Snarkify และ ZKM ได้เริ่มส่ง ZK proofs สำหรับบล็อคล่าสุดอย่างต่อเนื่อง เป้าหมายสูงสุดของแนวโน้มนี้คือการสร้าง Ethereum ให้เป็นเลเยอร์การดำเนินการที่ขับเคลื่อนโดยการพิสูจน์ความรู้เป็นศูนย์ ในขณะที่เลเยอร์ฉันทามติจำเป็นต้องทำเฉพาะงานเบาๆ เช่น การเสนอรายการธุรกรรมเท่านั้น

ความท้าทายที่ใหญ่ที่สุดที่สถาปัตยกรรม zkEVM เผชิญ: คอขวดประสิทธิภาพการพิสูจน์ของ Keccak

ปัจจุบันมีโครงการ zkRollup ที่เข้ากันได้กับ Ethereum หลายโครงการ (เช่น Polygon, Taiko และ Scroll) ที่พยายามนำ zkEVM มาใช้ อย่างไรก็ตาม การดำเนินการบางอย่างใน EVM แบบดั้งเดิมที่มีประสิทธิภาพบน CPU จะมีราคาแพงในระบบที่พิสูจน์ความรู้เป็นศูนย์ ปัญหาสำคัญด้านประสิทธิภาพคือฟังก์ชันแฮช Keccak

Keccak ถูกนำมาใช้กันอย่างแพร่หลายในการสร้าง Merkle Patricia Tree ของ Ethereum ซึ่งบันทึกสถานะของโซ่ทั้งหมดในรูปแบบแฮช อย่างไรก็ตาม การดำเนินการพื้นฐานของ Keccak ขึ้นอยู่กับการดำเนินการระดับบิต ซึ่งเข้ากันไม่ได้กับโมเดลการดำเนินการฟิลด์หลักที่ใช้โดยระบบ ZK ส่วนใหญ่ ส่งผลให้ประสิทธิภาพลดลงอย่างมาก

เพื่อช่วยให้เข้าใจว่าเหตุใดฟังก์ชันแฮช Keccak จึงเป็นคอลเลกชันของ "การดำเนินการบิต" โดยพื้นฐานแล้ว เราจะแสดงการดำเนินการหลัก 5 ประการอย่างคร่าวๆ ได้แก่ θ (ธีตา) ρ (โร) π (ไพ) χ (ไค) และ ι (ไอโอตา) การดำเนินการเหล่านี้ใช้กับโครงสร้างเมทริกซ์ 5 × 5 โดยที่แต่ละเซลล์เป็นจำนวนเต็ม 64 บิต ซึ่งเราเรียกว่า "คำ" เมทริกซ์ทั้งหมดประกอบด้วย 5 แถวและ 5 คอลัมน์

• θ (ธีตา) : ขั้นแรก คำนวณค่า พาริตี้ ของแต่ละคอลัมน์ จากนั้นจึงกำหนดค่าพาริตี้โดยเฉพาะกับคอลัมน์ที่อยู่ติดกันทางด้านซ้าย ในเวลาเดียวกัน คอลัมน์ที่อยู่ติดกันทางด้านขวาจะหมุนไปทางซ้าย จากนั้นจึงหมุนแบบพิเศษ กระบวนการนี้เกี่ยวข้องกับการดำเนินการไบนารีพื้นฐานเช่น "XOR" และ "การหมุนซ้าย"

• ρ (โร) : หมุนแต่ละคำในเมทริกซ์ไปทางซ้ายทีละบิต ระยะการหมุนของแต่ละคำแตกต่างกัน แต่ทั้งหมดเป็นค่าคงที่ที่ตั้งไว้ล่วงหน้า ขั้นตอนนี้ประกอบด้วยการดำเนินการ "มือซ้าย" ทั้งหมด

• π (Pi) : จัดเรียงคำในเมทริกซ์ตามรูปแบบคงที่ เนื่องจากกระบวนการนี้เป็นเพียงการสับเปลี่ยนตำแหน่ง จึงมักถือว่าเป็น "การดำเนินการต้นทุนเป็นศูนย์" ในการพิสูจน์ความรู้เป็นศูนย์

• χ (Chi) ดำเนินการรวมบิตตามแต่ละแถว และแต่ละคำจะถูกรวมกับสองคำที่อยู่ติดกันทางซ้ายและขวาในแถว การดำเนินการดังกล่าวรวมถึง "พิเศษหรือ" "การปฏิเสธ" และ "และ"

• ι (ไอโอตา): ดำเนินการ XOR กับคำแรกในเมทริกซ์ด้วยค่าคงที่คงที่ ซึ่งเกี่ยวข้องกับการดำเนินการ "XOR" เท่านั้น

ความท้าทายหลักในการนำ Keccak ไปใช้ในการพิสูจน์ความรู้เป็นศูนย์คือวิธีการแสดงการดำเนินการระดับบิตเหล่านี้อย่างมีประสิทธิภาพ โดยเฉพาะอย่างยิ่งเมื่อการดำเนินการแต่ละอย่างดำเนินการกับค่าจำนวนเต็ม 64 บิต นี่คือสาเหตุที่เราเรียกว่า Keccak-1600 เนื่องจากพื้นที่สถานะสำหรับแต่ละรอบคือ 5 × 5 × 64 = 1,600 บิต ขั้นตอนการดำเนินการนี้ต้องทำซ้ำ 24 ครั้ง

ต่อไปนี้ เราจะทบทวนความพยายามก่อนหน้านี้บางส่วนในการใช้ Keccak อย่างรวดเร็ว

ความพยายามครั้งที่ 1: ระบบพิสูจน์ที่อิงตาม Groth 16 หรือ R 1 CS อื่นๆ

ในปัจจุบัน วิธีที่นิยมและตรงที่สุดคือการใช้ Groth 16 หรือระบบพิสูจน์ R 1 CS (Rank-1 Constraint System) อื่นๆ ในการใช้งาน Keccak เพื่อแสดงการดำเนินการตามบิตใน Groth 16 เราแสดงแต่ละบิตเป็น 0 หรือ 1 และจำลองการดำเนินการเชิงตรรกะต่อไปนี้ผ่านความสัมพันธ์ทางคณิตศาสตร์:

• เอกสิทธิ์หรือ: ใช้การแสดงออก a + b − 2 ab

• การปฏิเสธ: ใช้การแสดงออก 1 − a (โดยปกติสามารถรวมเข้ากับข้อจำกัดอื่นๆ ได้อย่างอิสระ)

• และ: ใช้นิพจน์ a × b

อย่างไรก็ตาม การดำเนินการ เช่น การหมุนซ้าย และการดำเนินการเรียงสับเปลี่ยนอื่นๆ มักถือว่าเป็นการดำเนินการที่ไม่มีค่าใช้จ่ายในสภาพแวดล้อม ZK และไม่จำเป็นต้องมีข้อจำกัดเพิ่มเติม

ตามการคำนวณ จำนวนข้อจำกัดในแต่ละรอบของ Keccak มีดังนี้:

• การดำเนินการธีตาสร้างข้อจำกัดประมาณ 4,480 ข้อ

• การดำเนินการ ρ และ π คือ "ต้นทุนเป็นศูนย์"

• การดำเนินการ χ จะสร้างข้อจำกัดประมาณ 3,200 ข้อ

• การดำเนินการสร้างข้อจำกัดประมาณ 64 ข้อ

ดังนั้น Keccak-1600 แบบเต็ม (24 รอบ) จะส่งผลให้มีข้อจำกัด 185,856 ใน Groth 16

ตามข้อมูลในไลบรารี ICICLE ของ Ingonyama ต้องใช้เวลาราว 30-40 มิลลิวินาทีในการสร้างหลักฐาน Keccak ZK บน GPU Nvidia 4090 และราว 450 มิลลิวินาทีบน CPU หากจำเป็นต้องพิสูจน์การทำงานของ 8192 Keccak GPU จะใช้เวลาอย่างน้อย 250 ถึง 300 วินาที ขณะที่ CPU อาจใช้เวลาเกือบหนึ่งชั่วโมง

ความพยายามที่ 2: ระบบพิสูจน์ตามการค้นหา

การเพิ่มประสิทธิภาพที่ทันสมัยมากขึ้นคือการประมวลผลข้อมูลเป็นชุด (เช่น กลุ่มที่มี 4 หรือ 8 บิต) และดำเนินการบิตทั้งหมดผ่านตารางค้นหา กล่าวอีกนัยหนึ่ง จำนวนเต็ม 64 บิตแต่ละจำนวนจะถูกแบ่งออกเป็นบล็อกเล็กๆ หลายบล็อก (เช่น ชิ้นขนาด 8 บิต จำนวน 8 ชิ้น) จากนั้นจึงใช้ตารางค้นหาเพื่อดำเนินการเชิงตรรกะ

โดยเฉพาะอย่างยิ่งมีตารางค้นหาต่อไปนี้:

ตารางค้นหา XOR: ตารางค้นหาขนาด 2 ⁸ × 2 ⁸ ที่ใช้ในการคำนวณค่า XOR ของชิ้นส่วนขนาด 8 บิตจำนวน 2 ชิ้น วิธีนี้ช่วยให้สามารถดำเนินการ XOR แบบ 8 บิตได้โดยมีข้อจำกัดเพียงข้อเดียวแทนที่จะเป็นข้อจำกัด 8 ข้อแบบเดิม

ตารางค้นหาการดำเนินการ AND: เป็นตารางค้นหาขนาด 2 ⁸ × 2 ⁸ ซึ่งใช้สำหรับการดำเนินการ AND แบบบิตต่อชิ้นขนาด 8 บิตจำนวน 2 ชิ้น ผลของข้อจำกัดในการบันทึกนั้นคล้ายกับ XOR

ตารางค้นหาแบบหมุนซ้าย: เพื่อจัดการกับการดำเนินการหมุนซ้ายที่เกิดขึ้นบ่อยครั้งใน Keccak จึงมีการนำตารางค้นหาหลายตารางมาใช้ โดยเฉพาะ: ตารางค้นหา 7 ตารางที่มีขนาด 2⁸ ซึ่งสอดคล้องกับระยะทางการหมุน 8k+1, 8k+2 เป็นต้น (โดยที่ k เป็นจำนวนเต็มที่ไม่เป็นลบ) เมื่อเทียบกับความพยายามครั้งที่ 1 ซึ่งไม่จัดการการหมุนเลย แนวทางนี้จะเพิ่มค่าใช้จ่ายเพิ่มเติมประมาณ 192 ข้อจำกัดเพิ่มเติมต่อรอบ อย่างไรก็ตาม หากเปรียบเทียบกับชิ้นส่วนอื่นๆ แล้ว ต้นทุนนี้ยังถือว่าค่อนข้างน้อย

ในการใช้งานระบบนี้ เราจะไม่ใช้ Groth 16 อีกต่อไป แต่จะเหมาะสำหรับการใช้ระบบพิสูจน์โดเมนขนาดเล็ก เช่น Stwo และ Plonky 3 ซึ่งรองรับตารางค้นหาได้ครบถ้วนยิ่งขึ้น ภายใต้โครงการนี้ การดำเนินการ Keccak แต่ละครั้งที่สมบูรณ์จะต้องมีข้อจำกัดประมาณ 27,264 ข้อ และเมื่อรวมกับการเรียกตารางการค้นหา จำนวนข้อจำกัดทั้งหมดก็จะลดลงอย่างมาก ซึ่งถือเป็นการเพิ่มประสิทธิภาพที่สำคัญเมื่อเทียบกับ Groth 16

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

ความพยายามครั้งที่ 3: Binius

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

นี่คือเหตุผลว่าทำไมเคคจักถึงได้รับการขนานนามว่า “จอกศักดิ์สิทธิ์แห่งความรู้เป็นศูนย์” เมื่อเปรียบเทียบ ฟังก์ชันแฮชในช่วงแรกๆ เช่น SHA-256 และ Blake 2/3 ก็ยังต้องอาศัยการดำเนินการตามบิต เช่น XOR และ AND เช่นกัน แต่จุดคอขวดด้านประสิทธิภาพที่ใหญ่ที่สุดมาจากการบวกจำนวนเต็ม การบวกจำนวนเต็มมักจะได้รับการปรับให้เหมาะสมในระบบพิสูจน์โดยการแยกการบวกออกเป็นกลุ่มขนาด 4 บิตหลายๆ กลุ่ม ซึ่งจะช่วยปรับปรุงประสิทธิภาพได้อย่างมาก แต่ Keccak ไม่เกี่ยวข้องกับการบวกจำนวนเต็ม ดังนั้นกลยุทธ์การเพิ่มประสิทธิภาพเหล่านี้จึงล้มเหลวในกรณีนี้

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

ใน Binius Keccak แสดงเป็นการดำเนินการบนฟิลด์จำกัด 𝐹₂ ซึ่งเป็นฟิลด์ไบนารี เนื่องจาก XOR เป็นเพียงส่วนเพิ่มเติมใน 𝐹₂ ค่าใช้จ่ายที่เกี่ยวข้องจึงแทบจะถูกกำจัดออกไปหมด กระบวนการโดยรวมมีโครงสร้างเป็นชุดการดำเนินการพหุนาม และการดำเนินการหมุนบิตยังสามารถนำไปใช้งานได้อย่างง่ายดายในแบบจำลองการประมวลผลแบบบิตต่อบิต ปรากฏว่าต้นทุนส่วนใหญ่จะกระจุกตัวอยู่ในเกต AND ที่ปรากฏในขั้นตอน x

การทดสอบประสิทธิภาพของ Binius แสดงให้เห็นว่าใช้เวลาเพียงประมาณ 12.35 วินาทีในการพิสูจน์การดำเนินการ Keccak จำนวน 8,192 รายการ ซึ่งดีกว่า Groth 16 (ความพยายามครั้งที่ 1) และวิธีตารางค้นหา (ความพยายามครั้งที่ 2) มาก

บินิอุสคือจุดจบหรือเปล่า? จริงๆแล้วมันไม่ได้เป็นเช่นนั้น เราพบว่าการลบความซ้ำซ้อนบางส่วนออกจากหลักฐาน Keccak ทำให้สามารถปรับปรุงประสิทธิภาพได้อีกประมาณห้าเท่าเมื่อเทียบกับการใช้งาน Binius ในปัจจุบัน

Polyhedra เปิดตัว Binary GKR: ระบบพิสูจน์ไบนารีที่ปรับให้เหมาะสมสำหรับ Keccak

ทีมงาน Polyhedra กำลังสร้างระบบพิสูจน์ใหม่ - Binary GKR (ดู: ePrint 2025/717 ) ซึ่งเป็นกรอบงานโดยเฉพาะสำหรับการพิสูจน์การดำเนินการไบนารีที่มีประสิทธิภาพ เหมาะอย่างยิ่งสำหรับฟังก์ชันเช่น Keccak ที่เน้นที่การดำเนินการบิต ข้อได้เปรียบหลักของ Binary GKR มาจากนวัตกรรมทางเทคโนโลยีที่สำคัญสามประการดังต่อไปนี้:

1. เพิ่มประสิทธิภาพการคำนวณซ้ำตามโปรโตคอล GKR

เราเลือกที่จะใช้โปรโตคอล GKR (Goldwasser–Kalai–Rothblum) เป็นพื้นฐานสำหรับการออกแบบ Binary GKR เนื่องจากสามารถลดภาระงานซ้ำซ้อนที่เกิดจากการประมวลผลการคำนวณซ้ำๆ ได้อย่างมีประสิทธิภาพ

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

ที่สำคัญกว่านั้น อัลกอริทึม Keccak เองก็สามารถทำซ้ำได้สูง:

• มันดำเนินการบูลีนแบบเดียวกันซ้ำแล้วซ้ำเล่าบนเมทริกซ์สถานะ 5 × 5

• กระบวนการทั้งหมดประกอบด้วย 24 รอบที่มีขั้นตอนที่เกือบจะเหมือนกัน

• โครงสร้างของแต่ละรอบจะเหมือนกัน ต่างกันเพียงสถานะอินพุตเท่านั้น

ลักษณะดังกล่าวทำให้ Keccak เป็น "อะแดปเตอร์ตามธรรมชาติ" สำหรับโปรโตคอล GKR:

• เครื่องตรวจสอบมีต้นทุนต่ำและเหมาะสำหรับสถานการณ์การตรวจสอบความถี่สูง

• Prover สามารถใช้ประโยชน์จากการทำซ้ำทางโครงสร้างได้อย่างเต็มที่ นำเส้นทางการคำนวณกลับมาใช้ใหม่ และลดความซับซ้อนของภาระในการพิสูจน์ลงอย่างมาก

• เมื่อเปรียบเทียบกับระบบป้องกันทั่วไปแบบดั้งเดิมแล้ว ระบบนี้จะมีข้อได้เปรียบด้านประสิทธิภาพที่สำคัญในสถานการณ์ Keccak แบบแบตช์

2. ความมุ่งมั่นของพหุนามที่อิงตามฟิลด์ไบนารี

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

3. ตารางคำนวณล่วงหน้าสำหรับการดำเนินการแบบไบนารี

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

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

บทความนี้จะเน้นที่การเพิ่มประสิทธิภาพทางเทคนิคประการที่สามที่กล่าวไว้ข้างต้น: ตารางคำนวณล่วงหน้าสำหรับการดำเนินการไบนารี

การบรรจุบิตลงในพหุนาม

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

การประเมินความสัมพันธ์แบบไบนารีอย่างมีประสิทธิภาพมากขึ้น

เมื่อเทียบกับ GKR แบบดั้งเดิมแล้ว Binary GKR จะทำให้มีพื้นที่การเพิ่มประสิทธิภาพใหม่

ตารางการประมวลผลล่วงหน้านี้มีขนาดเล็กมาก โดยการตั้งค่าพารามิเตอร์อย่างเหมาะสม เราสามารถรักษาขนาดตารางให้อยู่ที่ประมาณ 15 MB ได้ ขนาดนี้พอดีกับแคช L3 ของ CPU ช่วยให้การดำเนินการค้นหาตารางมีประสิทธิภาพมาก

เทคนิคนี้สามารถนำไปใช้ได้กับการดำเนินการแบบไบนารีเกือบทั้งหมด และเป็นหัวใจสำคัญของการปรับปรุงประสิทธิภาพในการสร้าง GKR แบบไบนารี

การดำเนินการและการประเมินผล

เราได้นำระบบ SNARK มาใช้ใน Rust โดยอิงตามระบบนิเวศ Arkworks และดำเนินการประเมินประสิทธิภาพอย่างครอบคลุมกับวงจรบูลีนแบบสุ่มที่มีขนาดต่างกัน

นอกเหนือจากวงจรบูลีนแบบสุ่มแล้ว เรายังมุ่งเน้นไปที่ "จอกศักดิ์สิทธิ์" ของการพิสูจน์ความรู้เป็นศูนย์ - Keccak อีกด้วย เราเปรียบเทียบประสิทธิภาพของวิธีการที่เสนอกับ Binius บนการพิสูจน์ Keccak ทั้งสองขึ้นอยู่กับการดำเนินการโดเมนไบนารี

ในการประมวลผลการเรียก 8192 Keccak Binius จะใช้เวลา 12.35 วินาทีในการสร้างการพิสูจน์ ในขณะที่วิธีของเราใช้เวลาเพียง 2.18 วินาทีเท่านั้น ในเวลาเดียวกัน ด้วยโครงสร้างที่กระชับของ Keccak ทำให้เวลาการตรวจสอบของเราสั้นลงเหลือเพียง 0.035 วินาทีเท่านั้น ในแง่ของค่าใช้จ่ายในการสื่อสาร ขนาดหลักฐานของเราคือ 1.052 MB

บทสรุป

บทความนี้เสนอความคืบหน้าล่าสุดของทีม Polyhedra ในสาขาการพิสูจน์ความรู้เป็นศูนย์ โดยมุ่งเน้นไปที่การเพิ่มประสิทธิภาพสำหรับฟังก์ชันไบนารีเช่น Keccak ความสำเร็จนี้สามารถใช้เป็น "โมดูลเสริม" ที่มีประสิทธิภาพสำหรับการสร้าง zkEVM ประเภทต่างๆ

เราวางแผนที่จะรวม Binary GKR เข้าในระบบ zkEVM เช่น RISC Zero และ SP 1 เพื่อตรวจยืนยันบทบาทเพิ่มเติมในการบรรเทาปัญหาคอขวดด้านประสิทธิภาพของ Keccak เป้าหมายสูงสุดคือการเร่งความก้าวหน้าของ Ethereum ในทิศทาง SNARKization เต็มรูปแบบของเลเยอร์ 1 โดยไม่ทำลายสถาปัตยกรรม EVM ที่มีอยู่

ลิงค์ต้นฉบับ: https://blog.polyhedra.network/binary-gkr/