บทความเพื่อทำความเข้าใจข้อดีและข้อเสียของ FPGA และ GPU ช่วยเร่งการประมวลผลแบบ Zero-knowledge Proof

星球君的朋友们

Odaily资深作者

2023-06-06 03:30

บทความนี้มีประมาณ 2048 คำ การอ่านทั้งหมดใช้เวลาประมาณ 3 นาที

จากประสบการณ์ด้านวิศวกรรมที่ใช้งานจริง FPGA เป็นตัวเลือก แต่ปัจจุบัน GPU เป็นตัวเลือกที่คุ้ม

สรุปโดย AI

ขยาย

ผู้แต่งต้นฉบับ: Star Li

ที่มา: IOSG Ventures

เทคโนโลยี Zero-knowledge Proof ถูกนำมาใช้กันอย่างแพร่หลายมากขึ้นเรื่อยๆ เช่น การพิสูจน์ความเป็นส่วนตัว การพิสูจน์การคำนวณ การพิสูจน์ฉันทามติ และอื่นๆ ในขณะที่มองหาสถานการณ์การใช้งานที่มากขึ้นและดีขึ้น หลายคนค่อยๆ ค้นพบว่าการพิสูจน์ความรู้ที่ไม่มีศูนย์พิสูจน์ได้ว่าประสิทธิภาพเป็นคอขวด ทีมงาน Trapdoor Tech ได้ทำการวิจัยอย่างลึกซึ้งเกี่ยวกับเทคโนโลยีการพิสูจน์ว่าปราศจากความรู้มาตั้งแต่ปี 2019 และได้สำรวจโซลูชันการเร่งความเร็วที่พิสูจน์ด้วยความรู้เป็นศูนย์ที่มีประสิทธิภาพ GPU หรือ FPGA เป็นแพลตฟอร์มการเร่งความเร็วที่ค่อนข้างธรรมดาในตลาดปัจจุบัน บทความนี้เริ่มต้นด้วยการคำนวณ MSM และวิเคราะห์ข้อดีและข้อเสียของ FPGA และ GPU ที่เร่งการคำนวณการพิสูจน์ด้วยความรู้เป็นศูนย์

TL;DR

ZKP เป็นเทคโนโลยีที่มีแนวโน้มกว้างไกลสำหรับอนาคต แอปพลิเคชั่นจำนวนมากขึ้นเรื่อย ๆ กำลังใช้เทคโนโลยีการพิสูจน์ความรู้เป็นศูนย์ อย่างไรก็ตาม มีอัลกอริธึม ZKP มากมาย และโครงการต่างๆ ก็ใช้อัลกอริทึม ZKP ที่แตกต่างกัน ในขณะเดียวกัน ประสิทธิภาพการคำนวณของการพิสูจน์ ZKP นั้นค่อนข้างแย่ บทความนี้วิเคราะห์อัลกอริทึม MSM, อัลกอริทึมการเพิ่มจุดโค้งวงรี, อัลกอริทึมการคูณมอนต์โกเมอรี่ ฯลฯ โดยละเอียด และเปรียบเทียบความแตกต่างของประสิทธิภาพระหว่าง GPU และ FPGA ในการบวกจุดโค้ง BLS 12 _ 381 โดยทั่วไปแล้ว ในแง่ของการประมวลผลแบบพิสูจน์ ZKP GPU ระยะสั้นมีข้อได้เปรียบที่ชัดเจน ปริมาณงานสูง ประสิทธิภาพต้นทุนสูง ความสามารถในการโปรแกรม และอื่นๆ กล่าวโดยเปรียบเทียบ FPGA มีข้อดีบางประการในด้านการใช้พลังงาน ในระยะยาว อาจมีชิป FPGA ที่เหมาะสำหรับการคำนวณ ZKP หรือชิป ASIC ที่ปรับแต่งสำหรับ ZKP

อัลกอริทึม ZKP มีความซับซ้อน

ZKP เป็นคำทั่วไปสำหรับเทคโนโลยี Zero Knowledge Proof (Zero Knowledge Proof) ส่วนใหญ่มีสองประเภท: zk-SNARK และ zk-STARK อัลกอริธึมทั่วไปในปัจจุบันของ zk-SNARK คือ Groth 16, PLONK, PLOOKUP, Marlin และ Halo/Halo 2 การวนซ้ำของอัลกอริธึม zk-SNARK นั้นมี 2 ทิศทางหลัก: 1/จำเป็นต้องตั้งค่าที่เชื่อถือได้หรือไม่ 2/ประสิทธิภาพของโครงสร้างวงจร ข้อได้เปรียบของอัลกอริทึม zk-STARK คือไม่จำเป็นต้องมีการตั้งค่าที่เชื่อถือได้ แต่จำนวนการคำนวณการตรวจสอบจะเป็นแบบบันทึกเชิงเส้น

เท่าที่เกี่ยวข้องกับการประยุกต์ใช้อัลกอริทึม zk-SNARK/zk-STARK อัลกอริทึมการพิสูจน์ความรู้เป็นศูนย์ที่ใช้โดยโครงการต่างๆ ค่อนข้างกระจัดกระจาย ในการประยุกต์ใช้อัลกอริทึม zk-SNARK เนื่องจากอัลกอริทึม PLONK/Halo 2 เป็นสากล (ไม่จำเป็นต้องมีการตั้งค่าที่เชื่อถือได้) จึงอาจมีแอปพลิเคชันจำนวนมากขึ้นเรื่อยๆ

PLONK พิสูจน์จำนวนการคำนวณ

ใช้อัลกอริทึม PLONK เป็นตัวอย่าง วิเคราะห์จำนวนการคำนวณของการพิสูจน์ PLONK

จำนวนการคำนวณของส่วนพิสูจน์ PLONK ประกอบด้วยสี่ส่วน:

1/ MSM - การคูณหลายสเกลาร์ กลุ่มชายรักชายมักใช้ในการคำนวณพันธะพหุนาม

2/ NTT Computation - การแปลงโพลิโนเมียลระหว่างค่าจุดและการแสดงค่าสัมประสิทธิ์

3/ การคำนวณพหุนาม - การบวก การลบ การคูณและการหารพหุนาม การประเมินพหุนาม (Evaluation) เป็นต้น

4/ การสังเคราะห์วงจร - การสังเคราะห์วงจร การคำนวณส่วนนี้เกี่ยวข้องกับขนาด/ความซับซ้อนของวงจร

โดยทั่วไป จำนวนการคำนวณในส่วนของ Circuit Synthesize นั้นใช้วิจารณญาณและลอจิกลูปมากกว่า และระดับของความขนานค่อนข้างต่ำ ซึ่งเหมาะสำหรับการคำนวณ CPU มากกว่า โดยทั่วไปแล้ว การเร่งความเร็วที่พิสูจน์ด้วยความรู้เป็นศูนย์หมายถึงการเร่งการคำนวณของสามส่วนแรก ในหมู่พวกเขา จำนวนเงินที่คำนวณได้ของ MSM นั้นค่อนข้างใหญ่ที่สุด รองลงมาคือ NTT

What's MSM

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

ตัวอย่างเช่น กำหนดชุดของจุดบนเส้นโค้งวงรี:

Given a fixed set of Elliptic curve points from one specified curve:

[G_ 1, G_ 2, G_ 3, ..., G_n]

และค่าสัมประสิทธิ์สุ่ม:

and a randomly sampled finite field elements from specified scalar field:

[s_ 1, s_ 2, s_ 3, ..., s_n]

MSM is the calculation to get the Elliptic curve point Q:

Q = \sum_{i= 1 }^{n}s_i*G_i

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

ขั้นตอนการคำนวณของอัลกอริทึม Pippenger แบ่งออกเป็นสองขั้นตอน:

1/ สเกลาร์แยกเป็น Windows ถ้าสเกลาร์เป็น 256 บิต และหน้าต่างเป็น 8 บิต สเกลาร์ทั้งหมดจะถูกแบ่งออกเป็น 256/8 = 32 Windows หน้าต่างแต่ละชั้นใช้ "ที่เก็บข้อมูล" เพื่อจัดเก็บผลลัพธ์ระดับกลางชั่วคราว GW_x คือจุดสะสมผลลัพธ์ในหนึ่งเลเยอร์ การคำนวณ GW_x นั้นค่อนข้างง่ายเช่นกัน โดยจะข้าม Scalar แต่ละชั้นในชั้นเดียว และเพิ่ม G_x ที่สอดคล้องกันไปยังบิตของ Buckets ที่สอดคล้องกันตามค่าของชั้น Scalar เป็นดัชนี ในความเป็นจริง หลักการค่อนข้างง่าย ถ้าค่าสัมประสิทธิ์ของการบวกจุดสองจุดเท่ากัน ให้เพิ่มจุดสองจุดก่อน แล้วจึงเพิ่มสเกลาร์อีกครั้ง แทนที่จะเพิ่มจุดสองจุดสองครั้งก่อนที่จะเพิ่มสเกลาร์

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

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

การเพิ่มจุดเส้นโค้งวงรี (จุดเพิ่ม)

คุณสามารถดูอัลกอริทึมต่างๆ สำหรับการบวกจุดบนเส้นโค้งวงรีด้วยแบบฟอร์ม "ไวเออร์สตราสสั้น" ได้จากเว็บไซต์นี้

http://www.hyperelliptic.org/EFD/g 1 p/auto-shortw-jacobian-0.html#addition-madd-2007-bl

สมมติว่าพิกัดเชิงโครงของจุดทั้งสองคือ (x 1, y 1, z 1) และ (x 2, y 2, z 2) ตามลำดับ ผลลัพธ์ของการบวกจุด (x 3, y 3) สามารถคำนวณได้โดย ตามสูตรการคำนวณ , z 3).

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

BN 256 - 256 bits
BLS 12 _ 381 - 381 bits
BLS 12 _ 377 - 377 bits
โปรดทราบว่าการดำเนินการจำนวนเต็มเหล่านี้เป็นการดำเนินการบนฟิลด์โมดูโล การบวกแบบแยกส่วน/การลบแบบโมดูลัสนั้นค่อนข้างง่าย โดยเน้นที่หลักการและการดำเนินการของการคูณแบบแยกส่วน

การคูณแบบแยกส่วน

กำหนดสองค่าเหนือฟิลด์โมดูโล: x และ y การคำนวณการคูณแบบแยกส่วนหมายถึง x*y mod p โปรดทราบว่าความกว้างบิตของจำนวนเต็มเหล่านี้คือความกว้างบิตของเส้นโค้งวงรี อัลกอริทึมคลาสสิกสำหรับการคูณแบบโมดูลาร์คือการคูณมอนต์โกเมอรี่ ก่อนดำเนินการคูณมอนต์โกเมอรี่ ตัวคูณจำเป็นต้องแปลงเป็นตัวแทนมอนต์โกเมอรี:

สูตรการคำนวณการคูณมอนต์โกเมอรี่มีดังนี้:

มีอัลกอริธึมการปรับใช้การคูณของมอนต์โกเมอรี่มากมาย: CIOS (การสแกนโอเปอเรเตอร์แบบบูรณาการแบบหยาบ), FIOS (การสแกนโอเปอเรเตอร์แบบบูรณาการแบบละเอียด) และ FIPS (การสแกนผลิตภัณฑ์แบบผสานรวมแบบละเอียด) เป็นต้น บทความนี้ไม่ได้แนะนำรายละเอียดของการใช้งานอัลกอริทึมแบบต่างๆ ในเชิงลึก และผู้อ่านที่สนใจสามารถค้นคว้าได้เอง

เพื่อเปรียบเทียบความแตกต่างของประสิทธิภาพระหว่าง FPGA และ GPU ให้เลือกวิธีการใช้งานอัลกอริทึมพื้นฐานที่สุด:

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

สังเกตและคิด

ภายใต้การออกแบบ FPGA ดังกล่าว สามารถประมาณได้ว่า VU 9 P ทั้งหมดสามารถให้ทรูพุตที่ BLS 12 _ 381 จุดโค้งวงรี การเพิ่มจุด (วิธี add_mix) ต้องการการคูณแบบโมดูลาร์ประมาณ 12 ครั้ง นาฬิการะบบของ FPGA คือ 450M

ภายใต้อัลกอริธึมการคูณแบบโมดูลาร์/การบวกแบบโมดูลาร์เดียวกัน โดยใช้อัลกอริธึมการเพิ่มจุดแบบเดียวกัน ค่า Troughput แบบพอยต์บวกของ Nvidia 3090 (พิจารณาจากปัจจัยการส่งข้อมูล) เกิน 500 M/s แน่นอน การคำนวณทั้งหมดเกี่ยวข้องกับอัลกอริทึมที่หลากหลาย อัลกอริทึมบางอย่างอาจเหมาะสำหรับ FPGA และอัลกอริทึมบางอย่างเหมาะสำหรับ GPU เหตุผลที่ใช้การเปรียบเทียบอัลกอริทึมเดียวกันคือเพื่อเปรียบเทียบความสามารถในการประมวลผลหลักของ FPGA และ GPU

สรุป

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

ZKP

เทคโนโลยี

ยินดีต้อนรับเข้าร่วมชุมชนทางการของ Odaily