Era baru ZK didorong oleh akselerasi perangkat keras

Cerita sejauh ini

Bukti tanpa pengetahuan (ZKP) menjadi semakin penting untuk sistem desentralisasi. ZK pertama kali muncul di mata publik karena keberhasilannya dalam proyek-proyek seperti ZCash, tetapi hari ini ZK dikenal sebagai solusi penskalaan untuk Ethereum.

Memanfaatkan ZK, Layer 2 (misalnya Scroll dan Polygon), juga dikenal sebagai Rollups, sedang mengembangkan zkEVM (zk Ethereum Virtual Machine). ZkEVM ini memproses sejumlah transaksi dan menghasilkan bukti kecil (dalam kilobyte). Pengesahan ini dapat digunakan untuk memverifikasi ke seluruh jaringan bahwa batch transaksi valid dan benar.

Namun, penggunaannya tidak berhenti di situ. ZK memungkinkan untuk berbagai aplikasi menarik.

Private Layer 1 – Mina, misalnya, menyembunyikan rincian transaksi dan data di blockchain-nya, memungkinkan pengguna untuk hanya membuktikan validitas transaksi mereka tanpa mengungkapkan secara spesifik transaksi itu sendiri. neptune.cash dan Aleo juga merupakan proyek yang sangat menarik.

Platform cloud terdesentralisasi - FedML dan together.xyz memungkinkan model pembelajaran mesin (ML) dilatih dengan cara yang terdesentralisasi, mengalihdayakan komputasi ke jaringan, dan memverifikasi kebenaran komputasi menggunakan ZKP. Druglike sedang membangun platform penemuan obat yang lebih terbuka menggunakan teknologi serupa.

** Penyimpanan Terdesentralisasi ** - Filecoin merevolusi penyimpanan cloud, dan ZK pada intinya, memungkinkan penyedia penyimpanan untuk membuktikan bahwa mereka telah menyimpan data yang tepat selama periode waktu tertentu.

GAME - Versi Darkforest yang lebih canggih mungkin muncul, yang membutuhkan bukti real-time. ZK juga dapat memperluas permainan untuk mengurangi kemungkinan kecurangan. Mungkin juga bekerja dengan platform cloud terdesentralisasi untuk memungkinkan game membayar hostingnya sendiri!

** Identitas ** - Otentikasi terdesentralisasi sekarang juga dimungkinkan melalui ZK. Di sekitar ide ini, sejumlah proyek menarik sedang dibangun. Misalnya, buku catatan dan zkemail (disarankan untuk dipelajari).

Dampak ZK dan sistem desentralisasi sangat besar, namun, perkembangan ceritanya tidak sempurna, dan masih banyak kendala dan tantangan saat ini. Proses termasuk menghasilkan bukti sangat intensif sumber daya dan membutuhkan banyak operasi matematika yang kompleks. Karena pengembang berusaha membangun protokol dan sistem yang lebih ambisius dan kompleks menggunakan teknologi ZK, baik untuk pembuatan bukti dan proses verifikasi, pengembang menuntut ukuran bukti yang lebih kecil, kinerja yang lebih cepat, dan pengoptimalan yang lebih baik.

Pada artikel ini, kita akan mengeksplorasi keadaan akselerasi perangkat keras saat ini dan bagaimana hal itu akan memainkan peran kunci dalam memajukan adopsi ZK.

** Snark vs Stark **

Ada dua teknik tanpa pengetahuan yang populer saat ini, zk-STARK dan zk-SNARK (kami telah mengabaikan Bulletproofs dalam artikel ini).

| | | | | --- | --- | --- | | zk-STARK | zk-SNARK | | | Kompleksitas - Prover | O(N * polilog(N)) | O(N * log(N)) | | Kompleksitas - Verifier | O(poli-log(N)) | O(1) | | Ukuran bukti | 45KB-200KB | ~ 288 byte | | 抗量子 | Ya (berdasarkan fungsi hash) | Tidak | | Pengaturan tepercaya | Tidak | Ya | | Tanpa Pengetahuan | Iya | Iya | | Interaktivitas | Interaktif atau non-interaktif | Non interaktif | | Dokumentasi Pengembang | Terbatas, tetapi berkembang Baik |

表1:Snark VS Stark

Seperti disebutkan di atas, ada perbedaan dan trade-off antara keduanya. Poin terpenting adalah bahwa penyiapan tepercaya dari sistem berbasis zk-SNARK bergantung pada setidaknya satu peserta jujur yang terlibat dalam proses penyiapan tepercaya dan kunci mereka dihancurkan di akhir proses. Dalam hal verifikasi on-chain, zk-SNARKs jauh lebih murah dalam hal biaya gas. Selain itu, bukti zk-SNARKs juga jauh lebih kecil, membuatnya lebih murah untuk disimpan secara on-chain.

Saat ini, zk-SNARKs lebih populer daripada zk-STARKs. Alasan yang paling mungkin adalah bahwa zk-SNARKs memiliki sejarah yang jauh lebih panjang. Alasan lain yang mungkin adalah bahwa Zcash, salah satu blockchain ZK pertama, menggunakan zk-SNARKs, sehingga sebagian besar alat pengembangan dan dokumentasi saat ini berputar di sekitar ekosistem zk-SNARK.

Cara membangun Aplikasi ZK

Pengembang mungkin memerlukan dua komponen untuk menyelesaikan pengembangan aplikasi ZK

Metode komputasi ekspresi ramah ZK (DSL atau pustaka tingkat rendah).

Sistem pengesahan yang mengimplementasikan dua fungsi: Buktikan dan Verifikasi.

DSL (bahasa khusus domain) dan pustaka tingkat rendah

Ketika datang ke DSL, ada banyak pilihan, seperti Circom, Halo2, Noir, dan banyak lagi. Circom mungkin yang paling populer saat ini.
Ketika datang ke perpustakaan tingkat rendah, contoh populer adalah Arkworks; Ada juga perpustakaan dalam pengembangan, seperti ICICLE, yang merupakan perpustakaan akselerasi CUDA.

DSL ini dirancang untuk menghasilkan sistem terbatas. Berbeda dengan program biasa, yang biasanya dievaluasi dalam bentuk x: = y * z, program yang sama dalam bentuk terbatas lebih mirip x-y * z = 0. Dengan mewakili program sebagai sistem kendala, kami menemukan bahwa operasi seperti penambahan atau perkalian dapat diwakili oleh satu kendala. Namun, operasi yang lebih kompleks, seperti operasi bit, dapat memerlukan ratusan kendala!

Akibatnya, menjadi rumit untuk mengimplementasikan beberapa fungsi hash sebagai program ramah ZK. Dalam zero-knowledge proofs, fungsi hash sering digunakan untuk memastikan integritas data dan / atau untuk memverifikasi properti spesifik data, tetapi karena banyaknya kendala operasi bit, beberapa fungsi hash sulit untuk beradaptasi dengan lingkungan zero-knowledge proofs. Kompleksitas ini dapat mempengaruhi efisiensi pembuatan bukti dan verifikasi, dan dengan demikian menjadi masalah yang perlu dipertimbangkan dan dipecahkan oleh pengembang ketika membangun aplikasi berbasis ZK

Akibatnya, menjadi rumit untuk mengimplementasikan beberapa fungsi hash agar ramah ZK.

Membuktikan

Sistem pembuktian dapat disamakan dengan perangkat lunak yang menyelesaikan dua tugas utama: menghasilkan bukti dan memverifikasi bukti. Sistem bukti biasanya menerima sirkuit, bukti, dan parameter publik / swasta sebagai input.

Dua sistem bukti yang paling populer adalah seri Groth16 dan PLONK (Plonk, HyperPlonk, UltraPlonk)

| | | | | | | | --- | --- | --- | --- | --- | --- | | | Pengaturan Tepercaya | Ukuran bukti | Kompleksitas Prover | Kompleksitas Verifikator | Fleksibilitas | | Groth16 | Khusus sirkuit | Kecil | Rendah | Rendah | Rendah | | Lonk | Universal | Besar | Tinggi | 常数 | Tinggi |

表2:Groth16 vs Plonk

Seperti yang ditunjukkan pada Tabel 2, Groth16 memerlukan proses penyiapan tepercaya, tetapi Groth16 memberi kami waktu bukti dan verifikasi yang lebih cepat, serta ukuran bukti yang konstan.

Plonk menyediakan pengaturan generik yang melakukan fase pra-pemrosesan untuk sirkuit yang Anda jalankan setiap kali bukti dibuat. Meskipun mendukung banyak sirkuit, waktu verifikasi Plonk konstan.

Ada juga perbedaan antara keduanya dalam hal kendala. Groth16 tumbuh secara linear dalam hal ukuran kendala dan kurang fleksibel, sedangkan Plonk lebih fleksibel.

Secara keseluruhan, pahami bahwa kinerja terkait langsung dengan jumlah kendala dalam aplikasi ZK Anda. Semakin banyak kendala, semakin banyak operasi yang harus dihitung oleh prover.

Hambatan

Sistem bukti terdiri dari dua operasi matematika utama: multiscalar multiplication (MSM) dan fast Fourier transform (FFT). Hari ini kita akan mengeksplorasi sistem di mana keduanya ada, di mana MSM dapat mengambil sekitar 60% dari runtime, sementara FFT dapat mengambil sekitar 30%.

MSM membutuhkan banyak akses memori, yang dalam banyak kasus mengkonsumsi banyak memori pada mesin, sementara juga melakukan banyak operasi perkalian skalar.

Algoritma FFT sering membutuhkan penataan ulang data input ke dalam urutan tertentu untuk melakukan transformasi. Ini dapat memerlukan banyak pergerakan data dan dapat menjadi hambatan, terutama untuk ukuran input yang besar. Pemanfaatan cache juga bisa menjadi masalah jika pola akses memori tidak sesuai dengan hierarki cache.

**Dalam hal ini, akselerasi perangkat keras adalah satu-satunya cara untuk sepenuhnya mengoptimalkan kinerja ZKP. **

Akselerasi Perangkat Keras

Ketika datang ke akselerasi perangkat keras, ini mengingatkan kita tentang bagaimana ASIC dan GPU mendominasi penambangan Bitcoin dan Ethereum.

Sementara optimasi perangkat lunak sama pentingnya dan berharga, mereka memiliki keterbatasan. Optimalisasi perangkat keras, di sisi lain, dapat meningkatkan paralelisme dengan merancang FPGA dengan beberapa unit pemrosesan, seperti mengurangi sinkronisasi thread atau vektorisasi. Akses memori juga dapat dioptimalkan secara lebih efisien dengan meningkatkan hierarki memori dan pola akses.

Sekarang di ruang ZKP, tren utama tampaknya telah bergeser: GPU dan FPGA.

Dalam jangka pendek, GPU memiliki keunggulan dalam harga, terutama setelah ETH beralih ke proof-of-stake (POS), membuat sejumlah besar penambang GPU menganggur dan siaga. Selain itu, GPU memiliki keuntungan dari siklus pengembangan yang pendek dan memberi pengembang banyak paralelisme "plug-and-play".

Namun, FPGA harus mengejar ketinggalan, terutama ketika membandingkan faktor bentuk dan konsumsi daya. FPGA juga memberikan latensi yang lebih rendah untuk aliran data berkecepatan tinggi. Ketika beberapa FPGA dikelompokkan bersama, mereka memberikan kinerja yang lebih baik dibandingkan dengan kluster GPU.

GPU VS FPGA

GPU:

Waktu pengembangan: GPU memberikan waktu pengembangan yang cepat. Dokumentasi pengembang untuk kerangka kerja seperti CUDA dan OpenCL dikembangkan dengan baik dan populer.

Konsumsi daya: GPU sangat "haus daya". Bahkan ketika pengembang memanfaatkan paralelisme tingkat data dan paralelisme tingkat utas, GPU masih mengkonsumsi banyak daya.

** Ketersediaan **: GPU kelas konsumen murah dan tersedia saat ini.

FPGA:

Siklus pengembangan: FPGA memiliki siklus pengembangan yang lebih kompleks dan membutuhkan insinyur yang lebih khusus. FPGA memungkinkan teknisi mencapai banyak pengoptimalan "tingkat rendah" yang tidak dapat dilakukan GPU.

Latensi: FPGA memberikan latensi yang lebih rendah terutama saat memproses aliran data besar.

Biaya vs. Ketersediaan: FPGA lebih mahal daripada GPU dan tidak tersedia seperti GPU.

ZPRIZE

Saat ini, ketika datang ke hambatan optimasi perangkat keras dan ZKP, ada persaingan yang tidak dapat dihindari - ZPRIZE

ZPrize adalah salah satu inisiatif terpenting di bidang ZK saat ini. ZPrize adalah kompetisi yang mendorong tim untuk mengembangkan akselerasi perangkat keras untuk hambatan utama ZKP (misalnya, MSM, NTT, Poseidon, dll.) pada berbagai platform (misalnya, FPGA, GPU, perangkat seluler, dan browser) berdasarkan latensi, throughput, dan efisiensi.

Hasilnya sangat menarik. Misalnya, peningkatan GPU sangat besar:

MSM pada 2^26 telah meningkat sebesar 131% dari 5,86 detik menjadi 2,52 detik. Di sisi lain, solusi FPGA cenderung tidak memiliki tolok ukur dibandingkan dengan hasil GPU, yang memiliki tolok ukur sebelumnya untuk dibandingkan, dan sebagian besar solusi FPGA bersumber terbuka untuk pertama kalinya dengan algoritme yang diharapkan dapat meningkat di masa mendatang.

Hasil ini menunjukkan arah bahwa sebagian besar pengembang merasa nyaman dalam mengembangkan solusi akselerasi perangkat keras mereka. Banyak tim bersaing untuk kategori GPU, tetapi hanya sebagian kecil yang bersaing untuk kategori FPGA. Saya tidak yakin apakah itu karena kurangnya pengalaman saat mengembangkan untuk FPGA, atau apakah sebagian besar perusahaan/tim FPGA memilih untuk mengembangkan secara diam-diam untuk menjual solusi mereka secara komersial.

ZPrize telah memberikan beberapa penelitian yang sangat menarik kepada masyarakat. Semakin banyak putaran ZPrize dimulai, kita akan melihat semakin banyak solusi dan masalah menarik muncul.

** Contoh praktis akselerasi perangkat keras **

Mengambil Groth16 sebagai contoh, jika kita memeriksa implementasi rapidsnark untuk Groth16, kita dapat mengamati bahwa dua operasi utama dilakukan: FFT (Fast Fourier Transform) dan MSM (Multiscalar Multiplication); Kedua operasi dasar ini umum di banyak sistem pembuktian. Waktu eksekusi mereka berhubungan langsung dengan jumlah kendala di sirkuit. Secara alami, jumlah kendala meningkat karena sirkuit yang lebih kompleks ditulis.

Untuk mengetahui seberapa intensif operasi FFT dan MSM, kita dapat melihat tolok ukur Ingonyama dari sirkuit Groth16 (proses Vanilla C2 Filecoin dilakukan pada sektor 32GB), dan hasilnya adalah sebagai berikut

Seperti yang ditunjukkan pada gambar di atas, MSM (Multiscalar Multiplication) dapat memakan waktu dan hambatan kinerja yang serius bagi banyak provers, menjadikan MSM salah satu operator kriptografi terpenting yang perlu dipercepat.

Jadi berapa banyak perhitungan yang ditempati MSM untuk prover dalam sistem bukti ZK lainnya? Ini ditunjukkan pada gambar di bawah ini

Di Plonk, MSM menyumbang lebih dari 85% overhead, seperti yang ditunjukkan dalam makalah terbaru Ingonyama, Pipe MSM. **

Jadi bagaimana seharusnya akselerasi perangkat keras mempercepat MSM? **

MSM

Sebelum kita berbicara tentang bagaimana mempercepat MSM, kita perlu memahami apa itu MSM

Multi-Skalar Perkalian (MSM) adalah algoritma untuk menghitung jumlah beberapa perkalian skalar dalam bentuk berikut

** di mana G adalah titik dalam kelompok kurva eliptik, a adalah skalar, dan hasil MSM juga akan menjadi titik kurva eliptik **

Kita dapat menguraikan MSM menjadi dua sub-komponen utama:

Perkalian Modular

Penambahan Titik Kurva Elips

Mari kita ambil Affine(x,y) sebagai contoh untuk melakukan operasi P+Q yang naif.

Ketika kita ingin menghitung P + Q = R, kita perlu menghitung nilai k, dengan absis k dan P, Q

Dapatkan koordinat R. Proses perhitungannya adalah seperti di atas, dalam proses ini kita melakukan 2 kali perkalian, 1 operasi kuadrat, 1 operasi terbalik, dan beberapa kali operasi penjumlahan dan pengurangan. Perlu dicatat bahwa operasi di atas dilakukan di bidang terbatas, yaitu di bawah mod P. Pada kenyataannya, P akan sangat besar. **

Biaya operasi di atas adalah untuk menemukan perkalian >> terbalik ** **> dua jari kuadrat, dan biaya penambahan dan pengurangan dapat diabaikan.

Jadi kami ingin menghindari invers sebanyak mungkin, karena biaya inversi tunggal setidaknya seratus kali lipat perkalian. Kita dapat melakukan ini dengan memperluas sistem koordinat, tetapi dengan biaya meningkatkan jumlah perkalian dalam proses, seperti koordinat Jacobian: XYZ += XYZ, dan mengalikan lebih dari 10 kali, tergantung pada algoritma penjumlahan. **

GPU VS FPGA Accelerated MSM

Bagian ini membandingkan dua implementasi MSM terkemuka, PipeMSM dan Sppark, di mana PipeMSM diimplementasikan pada FPGA dan Sppark diimplementasikan pada GPU.

Sppark dan PipeMSM menggunakan algoritma Pippenger yang canggih untuk mengimplementasikan MSM, juga dikenal sebagai algoritma bucket; **

Sppark diimplementasikan menggunakan CUDA; Versi mereka sangat paralelisme dan telah mencapai hasil yang mengesankan saat berjalan pada GPU terbaru.

Namun, PipeMSM tidak hanya mengoptimalkan algoritma, tetapi juga menyediakan optimasi untuk primitif matematika Perkalian Modular dan Penambahan EC. PipeMSM menangani seluruh "tumpukan MSM", menerapkan serangkaian trik matematika dan pengoptimalan yang bertujuan membuat MSM lebih cocok untuk perangkat keras, dan merancang desain perangkat keras yang dirancang untuk mengurangi latensi dengan fokus pada paralelisasi.

Mari kita rekap singkat implementasi PipeMSM.

Latensi Rendah
PipeMSM dirancang untuk memberikan latensi rendah saat menjalankan beberapa MSM pada sejumlah besar input. GPU tidak menawarkan latensi rendah deterministik karena penskalaan frekuensi dinamis, dan GPU menyesuaikan kecepatan clock berdasarkan beban kerja.

Namun berkat desain perangkat keras yang dioptimalkan, implementasi FPGA dapat memberikan performa dan latensi deterministik untuk beban kerja tertentu.

Implementasi Penambahan EC

Penambahan Titik Kurva Elips (Penambahan EC) diimplementasikan sebagai rumus latensi rendah, sangat paralel, dan lengkap (lengkap berarti menghitung dengan benar jumlah dua titik dalam kelompok kurva elips). Penambahan titik kurva elips digunakan secara pipelined dalam modul penambahan EC untuk mengurangi latensi.

Kami memilih untuk mewakili koordinat sebagai koordinat proyektif, dan pada algoritma penjumlahan kami menggunakan rumus penjumlahan titik kurva eliptik lengkap. Keuntungan utamanya adalah kita ** tidak harus berurusan dengan kasus tepi **. Formula lengkap;

Kami menerapkan rumus penjumlahan ini secara pipelined dan paralel, dan rangkaian penambah kurva eliptik FPGA kami hanya membutuhkan 12 perkalian, 17 jumlah penambahan, dan rumus ini dijalankan. Rumus asli membutuhkan 15 perkalian modulo dan 13 penambahan. Desain FPGA adalah sebagai berikut

Multi mod

Kami memanfaatkan algoritma Barrett Reduction dan Karatsuba.

Barrett Reduction adalah algoritma yang secara efisien menghitung r≡ab mod p (di mana p tetap). Barrett Reduction mencoba untuk menggantikan divisi (operasi mahal) dengan perkiraan divisi. Toleransi kesalahan dapat dipilih untuk menggambarkan kisaran di mana kita mencari hasil yang benar. Kami menemukan bahwa toleransi kesalahan yang besar memungkinkan penggunaan konstanta reduksi yang lebih kecil; Ini mengurangi ukuran nilai antara yang digunakan dalam operasi reduksi modulo, yang mengurangi jumlah perkalian yang diperlukan untuk menghitung hasil akhir.

Di kotak biru di bawah ini, kita dapat melihat bahwa karena toleransi kesalahan yang tinggi, kita harus melakukan beberapa pemeriksaan untuk menemukan hasil yang akurat.

Singkatnya, algoritma Karatsuba digunakan untuk mengoptimalkan perkalian yang kita lakukan di Barrett Reduction. Algoritma Karatsuba menyederhanakan perkalian dua digit n menjadi perkalian tiga digit n/2; Perkalian ini dapat menyederhanakan jumlah digit menjadi cukup sempit untuk langsung dihitung oleh perangkat keras. Detail dapat dibaca di makalah Ingo: Pipe MSM

Dengan menggunakan operator di atas, kami telah mengembangkan implementasi MSM latensi rendah dan sangat paralel.

Ide intinya adalah bahwa alih-alih menghitung seluruh MSM sekaligus, setiap potongan dilewatkan ke adder EC secara paralel. Hasil penambah EC diakumulasikan ke dalam MSM akhir.

Hasil Akhir ****

Diagram di atas menunjukkan perbandingan antara Sppark dan PipeMSM.

Yang paling menonjol adalah penghematan energi signifikan yang ditawarkan oleh FPGA, yang bisa sangat penting untuk operasi pembangkitan bukti skala besar di masa depan. Perlu dicatat bahwa implementasi kami telah dibuat prototipe dan dibandingkan dengan @125MHz, dan meningkatkan kecepatan clock ke @500MHz dapat meningkatkan waktu komputasi sebesar 4x atau lebih.

Keuntungan lain menggunakan FPGA kami adalah dapat dipasang di server sasis kecil karena mengkonsumsi lebih sedikit energi dan menghasilkan lebih sedikit panas.

Kami berada di tahap awal rekayasa FPGA untuk ZKP dan harus mengharapkan peningkatan lebih lanjut dalam algoritma. Selain itu, FPGA menghitung MSM saat CPU idle, dan dimungkinkan untuk mencapai waktu yang lebih cepat dengan menggunakan FPGA dalam kombinasi dengan sumber daya sistem (CPU/GPU).

Ringkasan

ZKP telah menjadi teknologi kunci untuk sistem terdistribusi.

Penerapan ZKP akan jauh melampaui hanya memperluas tingkat Ethereum, memungkinkan outsourcing komputasi kepada pihak ketiga yang tidak dipercaya, memungkinkan pengembangan sistem yang sebelumnya tidak mungkin, seperti komputasi awan terdistribusi, sistem identitas, dan banyak lagi.

Secara tradisional, pengoptimalan ZKP berfokus pada peningkatan tingkat perangkat lunak, tetapi seiring dengan meningkatnya permintaan akan kinerja yang lebih unggul, kita akan melihat solusi akselerasi yang lebih canggih yang melibatkan perangkat keras dan perangkat lunak.

Saat ini, solusi akselerasi yang kami lihat terutama menggunakan GPU, karena waktu pengembangan menggunakan CUDA singkat, dan GPU konsumen saat ini sangat murah dan berlimpah. GPU juga menawarkan kinerja yang luar biasa. Jadi GPU tidak mungkin menghilang dari ruang ini dalam waktu dekat.

Saat tim pengembangan yang lebih kompleks memasuki ruang, kemungkinan kita akan melihat FPGA memimpin dalam hal efisiensi daya dan kinerja. Dibandingkan dengan GPU, FPGA menawarkan lebih banyak penyesuaian tingkat rendah serta lebih banyak opsi konfigurasi. FPGA menawarkan kecepatan dan fleksibilitas pengembangan yang lebih cepat daripada ASIC. Dengan pesatnya perkembangan dunia ZKP, FPGA dapat di-reflash dengan berbagai program untuk mengakomodasi berbagai sistem dan memperbarui solusi.

Namun, untuk menghasilkan bukti mendekati real-time, mungkin perlu untuk menggabungkan konfigurasi GPU / FPGA / ASIC tergantung pada sistem yang kami hasilkan buktinya.

ZPU juga cenderung berkembang untuk memberikan solusi yang sangat efisien untuk generator bukti skala besar dan perangkat berdaya rendah (lihat artikel sebelumnya untuk detailnya).