Artikel ini menganalisis algoritme MSM, algoritme penambahan titik kurva eliptik, algoritme perkalian Montgomery, dll. secara mendetail, dan membandingkan perbedaan kinerja antara GPU dan FPGA dalam penambahan titik kurva BLS12_381.
Ditulis oleh: Bintang Li
Teknologi bukti tanpa pengetahuan semakin banyak digunakan, seperti bukti privasi, bukti perhitungan, bukti konsensus, dan sebagainya. Sambil mencari skenario aplikasi yang lebih banyak dan lebih baik, banyak orang secara bertahap menemukan bahwa bukti tanpa pengetahuan membuktikan bahwa kinerja adalah hambatan. Tim Trapdoor Tech telah meneliti secara mendalam teknologi bukti tanpa pengetahuan sejak 2019, dan telah mengeksplorasi solusi percepatan bukti tanpa pengetahuan yang efisien. GPU atau FPGA adalah platform akselerasi yang relatif umum saat ini di pasaran. Artikel ini dimulai dengan perhitungan MSM, dan menganalisis kelebihan dan kekurangan FPGA dan GPU yang dipercepat perhitungan bukti tanpa pengetahuan.
##TL;DR
ZKP adalah teknologi dengan prospek masa depan yang luas. Semakin banyak aplikasi yang mengadopsi teknologi bukti tanpa pengetahuan. Namun, ada banyak algoritma ZKP, dan berbagai proyek menggunakan algoritma ZKP yang berbeda. Pada saat yang sama, kinerja komputasi bukti ZKP relatif buruk. Makalah ini menganalisis algoritme MSM, algoritme penambahan titik kurva eliptik, algoritme perkalian Montgomery, dll. Secara detail, dan membandingkan perbedaan kinerja antara GPU dan FPGA dalam penambahan titik kurva BLS12_381. Secara umum, dalam hal komputasi bukti ZKP, GPU jangka pendek memiliki keunggulan yang jelas, throughput tinggi, kinerja biaya tinggi, programabilitas, dan sebagainya. Secara relatif, FPGA memiliki keunggulan tertentu dalam konsumsi daya. Dalam jangka panjang, mungkin ada chip FPGA yang cocok untuk perhitungan ZKP, atau chip ASIC yang disesuaikan untuk ZKP.
Kompleks algoritma ZKP
ZKP adalah istilah umum untuk teknologi Zero Knowledge Proof (Zero Knowledge Proof). Terutama ada dua klasifikasi: zk-SNARK dan zk-STARK. Algoritme umum zk-SNARK saat ini adalah Groth16, PLONK, PLOOKUP, Marlin dan Halo/Halo2. Iterasi algoritme zk-SNARK terutama sepanjang dua arah: 1/apakah diperlukan penyiapan tepercaya 2/kinerja struktur sirkuit. Keuntungan dari algoritme zk-STARK adalah tidak diperlukan pengaturan tepercaya, tetapi jumlah perhitungan verifikasi adalah log-linear.
Sejauh penerapan algoritme zk-SNARK/zk-STARK, algoritme pembuktian tanpa pengetahuan yang digunakan oleh berbagai proyek relatif tersebar. Dalam penerapan algoritme zk-SNARK, karena algoritme PLONK/Halo2 bersifat universal (tidak perlu penyetelan tepercaya), mungkin semakin banyak aplikasi.
PLONK membuktikan jumlah komputasi
Mengambil algoritma PLONK sebagai contoh, menganalisis jumlah perhitungan bukti PLONK.
Besaran perhitungan bagian bukti PLONK terdiri dari empat bagian:
1/ MSM - Perkalian Skalar Berganda. MSM sering digunakan untuk menghitung komitmen polinomial.
2/ Komputasi NTT - Konversi polinomial antara nilai titik dan representasi koefisien.
3/ Perhitungan polinomial - penjumlahan, pengurangan, perkalian, dan pembagian polinomial. Evaluasi polinomial (uasi) dan seterusnya.
4/ Sintesis Sirkuit - sintesis sirkuit. Perhitungan bagian ini terkait dengan skala/kompleksitas rangkaian.
Secara umum, jumlah kalkulasi di bagian Circuit Synthesize lebih bersifat penilaian dan logika loop, dan tingkat paralelismenya relatif rendah, yang lebih cocok untuk kalkulasi CPU. Secara umum, percepatan bukti tanpa pengetahuan umumnya mengacu pada percepatan perhitungan dari tiga bagian pertama. Diantaranya, jumlah perhitungan LSL relatif paling besar, diikuti NTT.
Apa itu MSM
MSM (Perkalian Skalar Berganda) mengacu pada serangkaian titik dan skalar tertentu pada kurva eliptik, dan menghitung titik yang sesuai dengan hasil penjumlahan titik-titik ini.
Misalnya, diberikan serangkaian titik pada kurva eliptik:
Diberikan satu set tetap titik kurva Elliptic dari satu kurva tertentu:
[G_1, G_2, G_3, ..., G_n]
dan koefisien acak:
dan elemen bidang terbatas sampel acak dari bidang skalar tertentu:
[s_1, s_2, s_3, ..., s_n]
MSM adalah perhitungan untuk mendapatkan titik kurva Elliptic Q:
Q = \sum_{i=1}^{n}s_i*G_i
Industri umumnya mengadopsi algoritma Pippenger untuk mengoptimalkan perhitungan MSM. Perhatikan lebih dekat diagram skematik dari proses algoritma Pippenger:
Proses perhitungan algoritma Pippenger dibagi menjadi dua langkah:
1/ Scalar dibagi menjadi Windows. Jika Scalar adalah 256bits, dan sebuah Window adalah 8bits, maka semua Scalars dibagi menjadi 256/8=32 Windows. Setiap lapisan Window menggunakan "Buckets" untuk menyimpan sementara hasil antara. GW_x adalah titik hasil akumulasi pada satu layer. Menghitung GW_x juga relatif sederhana, yaitu melintasi setiap Skalar dalam satu lapisan secara bergantian, dan menggunakan nilai lapisan Skalar sebagai Indeks, dan menambahkan G_x yang sesuai ke Bucket yang sesuai. Padahal, prinsipnya relatif sederhana, jika koefisien penjumlahan dua titik sama, jumlahkan kedua titik terlebih dahulu, lalu tambahkan Skalar lagi, bukan menjumlahkan dua titik sebelum menambahkan Skalar.
2/ Poin yang dihitung oleh setiap Jendela diakumulasikan dengan penjumlahan ganda untuk mendapatkan hasil akhir.
Algoritma Pippenger juga memiliki banyak algoritma optimasi deformasi. Bagaimanapun, perhitungan yang mendasari algoritma MSM adalah penambahan titik pada kurva eliptik. Algoritme pengoptimalan yang berbeda sesuai dengan jumlah poin yang ditambahkan berbeda.
Penambahan titik kurva eliptik (Penambahan Titik)
Anda dapat melihat berbagai algoritme untuk penambahan titik pada kurva eliptik dengan bentuk "Weierstrass pendek" dari situs ini.
Dengan asumsi bahwa koordinat Proyektif dari dua titik berturut-turut adalah (x1, y1, z1) dan (x2, y2, z2), hasil penjumlahan titik (x3, y3, z3) dapat dihitung dengan rumus perhitungan berikut.
Alasan untuk memberikan proses perhitungan secara rinci adalah untuk menunjukkan bahwa seluruh proses perhitungan sebagian besar merupakan operasi bilangan bulat. Lebar bit integer tergantung pada parameter kurva eliptik. Berikan lebar bit dari beberapa kurva eliptik umum:
BN256 - 256 bit
BLS12_381 - 381 bit
BLS12_377 - 377 bit
Perhatian khusus adalah bahwa operasi bilangan bulat ini adalah operasi pada bidang modulo. Penambahan modul/pengurangan modulus relatif sederhana, fokus pada prinsip dan implementasi perkalian modular.
模乘（Perkalian Modular）
Diberikan dua nilai pada bidang modulo: x dan y. Perhitungan perkalian modular mengacu pada x*y mod p. Perhatikan bahwa lebar bit bilangan bulat ini adalah lebar bit kurva elips. Algoritma klasik perkalian modular adalah perkalian Montgomery (MontgomeryMulplication). Sebelum melakukan perkalian Montgomery, perkalian harus dikonversi ke representasi Montgomery:
Rumus untuk menghitung perkalian Montgomery adalah sebagai berikut:
Ada banyak algoritma implementasi perkalian Montgomery: CIOS (Pemindaian Operan Terintegrasi Kasar), FIOS (Pemindaian Operan Terintegrasi Halus), dan FIPS (Pemindaian Produk Terintegrasi Halus) dan seterusnya. Artikel ini tidak memperkenalkan detail berbagai implementasi algoritma secara mendalam, dan pembaca yang tertarik dapat melakukan riset sendiri.
Untuk membandingkan perbedaan performa antara FPGA dan GPU, pilih metode implementasi algoritme paling dasar:
Sederhananya, algoritma perkalian modular dapat dibagi lagi menjadi dua perhitungan: perkalian bilangan besar dan penjumlahan bilangan besar. Setelah memahami logika perhitungan MSM, Anda dapat memilih performa perkalian modular (Throughput) untuk membandingkan performa FPGA dan GPU.
Amati dan pikirkan
Di bawah desain FPGA seperti itu, dapat diperkirakan bahwa seluruh VU9P dapat menyediakan throughput pada titik kurva eliptik BLS12_381. Penambahan titik (tambahkan_campur cara) membutuhkan sekitar 12 perkalian modular. Jam sistem FPGA adalah 450M.
Di bawah algoritme perkalian/penambahan modulus modular yang sama, menggunakan algoritme penambahan titik yang sama, titik plus Troughput dari Nvidia 3090 (mempertimbangkan faktor transmisi data) melebihi 500M/s. Tentu saja, keseluruhan kalkulasi melibatkan berbagai algoritme, beberapa algoritme mungkin cocok untuk FPGA, dan beberapa algoritme cocok untuk GPU. Alasan menggunakan perbandingan algoritma yang sama adalah untuk membandingkan kemampuan komputasi inti FPGA dan GPU.
Berdasarkan hasil di atas, rangkum perbandingan antara GPU dan FPGA dalam hal kinerja pembuktian ZKP:
Ringkas
Semakin banyak aplikasi yang mengadopsi teknologi bukti tanpa pengetahuan. Namun, ada banyak algoritma ZKP, dan berbagai proyek menggunakan algoritma ZKP yang berbeda. Dari pengalaman teknik langsung kami, FPGA adalah pilihan, tetapi GPU saat ini merupakan pilihan yang hemat biaya. FPGA lebih memilih komputasi deterministik, yang memiliki keunggulan latensi dan konsumsi daya. GPU memiliki programabilitas tinggi, memiliki kerangka kerja komputasi kinerja tinggi yang relatif matang, dan memiliki siklus iterasi pengembangan yang singkat, dan lebih memilih skenario throughput.
Lihat Asli
Konten ini hanya untuk referensi, bukan ajakan atau tawaran. Tidak ada nasihat investasi, pajak, atau hukum yang diberikan. Lihat Penafian untuk pengungkapan risiko lebih lanjut.
Artikel untuk memahami kelebihan dan kekurangan FPGA dan GPU mempercepat komputasi tanpa pengetahuan
Ditulis oleh: Bintang Li
Teknologi bukti tanpa pengetahuan semakin banyak digunakan, seperti bukti privasi, bukti perhitungan, bukti konsensus, dan sebagainya. Sambil mencari skenario aplikasi yang lebih banyak dan lebih baik, banyak orang secara bertahap menemukan bahwa bukti tanpa pengetahuan membuktikan bahwa kinerja adalah hambatan. Tim Trapdoor Tech telah meneliti secara mendalam teknologi bukti tanpa pengetahuan sejak 2019, dan telah mengeksplorasi solusi percepatan bukti tanpa pengetahuan yang efisien. GPU atau FPGA adalah platform akselerasi yang relatif umum saat ini di pasaran. Artikel ini dimulai dengan perhitungan MSM, dan menganalisis kelebihan dan kekurangan FPGA dan GPU yang dipercepat perhitungan bukti tanpa pengetahuan.
##TL;DR
ZKP adalah teknologi dengan prospek masa depan yang luas. Semakin banyak aplikasi yang mengadopsi teknologi bukti tanpa pengetahuan. Namun, ada banyak algoritma ZKP, dan berbagai proyek menggunakan algoritma ZKP yang berbeda. Pada saat yang sama, kinerja komputasi bukti ZKP relatif buruk. Makalah ini menganalisis algoritme MSM, algoritme penambahan titik kurva eliptik, algoritme perkalian Montgomery, dll. Secara detail, dan membandingkan perbedaan kinerja antara GPU dan FPGA dalam penambahan titik kurva BLS12_381. Secara umum, dalam hal komputasi bukti ZKP, GPU jangka pendek memiliki keunggulan yang jelas, throughput tinggi, kinerja biaya tinggi, programabilitas, dan sebagainya. Secara relatif, FPGA memiliki keunggulan tertentu dalam konsumsi daya. Dalam jangka panjang, mungkin ada chip FPGA yang cocok untuk perhitungan ZKP, atau chip ASIC yang disesuaikan untuk ZKP.
Kompleks algoritma ZKP
ZKP adalah istilah umum untuk teknologi Zero Knowledge Proof (Zero Knowledge Proof). Terutama ada dua klasifikasi: zk-SNARK dan zk-STARK. Algoritme umum zk-SNARK saat ini adalah Groth16, PLONK, PLOOKUP, Marlin dan Halo/Halo2. Iterasi algoritme zk-SNARK terutama sepanjang dua arah: 1/apakah diperlukan penyiapan tepercaya 2/kinerja struktur sirkuit. Keuntungan dari algoritme zk-STARK adalah tidak diperlukan pengaturan tepercaya, tetapi jumlah perhitungan verifikasi adalah log-linear.
Sejauh penerapan algoritme zk-SNARK/zk-STARK, algoritme pembuktian tanpa pengetahuan yang digunakan oleh berbagai proyek relatif tersebar. Dalam penerapan algoritme zk-SNARK, karena algoritme PLONK/Halo2 bersifat universal (tidak perlu penyetelan tepercaya), mungkin semakin banyak aplikasi.
PLONK membuktikan jumlah komputasi
Mengambil algoritma PLONK sebagai contoh, menganalisis jumlah perhitungan bukti PLONK.
Besaran perhitungan bagian bukti PLONK terdiri dari empat bagian:
1/ MSM - Perkalian Skalar Berganda. MSM sering digunakan untuk menghitung komitmen polinomial.
2/ Komputasi NTT - Konversi polinomial antara nilai titik dan representasi koefisien.
3/ Perhitungan polinomial - penjumlahan, pengurangan, perkalian, dan pembagian polinomial. Evaluasi polinomial (uasi) dan seterusnya.
4/ Sintesis Sirkuit - sintesis sirkuit. Perhitungan bagian ini terkait dengan skala/kompleksitas rangkaian.
Secara umum, jumlah kalkulasi di bagian Circuit Synthesize lebih bersifat penilaian dan logika loop, dan tingkat paralelismenya relatif rendah, yang lebih cocok untuk kalkulasi CPU. Secara umum, percepatan bukti tanpa pengetahuan umumnya mengacu pada percepatan perhitungan dari tiga bagian pertama. Diantaranya, jumlah perhitungan LSL relatif paling besar, diikuti NTT.
Apa itu MSM
MSM (Perkalian Skalar Berganda) mengacu pada serangkaian titik dan skalar tertentu pada kurva eliptik, dan menghitung titik yang sesuai dengan hasil penjumlahan titik-titik ini.
Misalnya, diberikan serangkaian titik pada kurva eliptik:
Diberikan satu set tetap titik kurva Elliptic dari satu kurva tertentu:
[G_1, G_2, G_3, ..., G_n]
dan koefisien acak:
dan elemen bidang terbatas sampel acak dari bidang skalar tertentu:
[s_1, s_2, s_3, ..., s_n]
MSM adalah perhitungan untuk mendapatkan titik kurva Elliptic Q:
Q = \sum_{i=1}^{n}s_i*G_i
Industri umumnya mengadopsi algoritma Pippenger untuk mengoptimalkan perhitungan MSM. Perhatikan lebih dekat diagram skematik dari proses algoritma Pippenger:
Proses perhitungan algoritma Pippenger dibagi menjadi dua langkah:
1/ Scalar dibagi menjadi Windows. Jika Scalar adalah 256bits, dan sebuah Window adalah 8bits, maka semua Scalars dibagi menjadi 256/8=32 Windows. Setiap lapisan Window menggunakan "Buckets" untuk menyimpan sementara hasil antara. GW_x adalah titik hasil akumulasi pada satu layer. Menghitung GW_x juga relatif sederhana, yaitu melintasi setiap Skalar dalam satu lapisan secara bergantian, dan menggunakan nilai lapisan Skalar sebagai Indeks, dan menambahkan G_x yang sesuai ke Bucket yang sesuai. Padahal, prinsipnya relatif sederhana, jika koefisien penjumlahan dua titik sama, jumlahkan kedua titik terlebih dahulu, lalu tambahkan Skalar lagi, bukan menjumlahkan dua titik sebelum menambahkan Skalar.
2/ Poin yang dihitung oleh setiap Jendela diakumulasikan dengan penjumlahan ganda untuk mendapatkan hasil akhir.
Algoritma Pippenger juga memiliki banyak algoritma optimasi deformasi. Bagaimanapun, perhitungan yang mendasari algoritma MSM adalah penambahan titik pada kurva eliptik. Algoritme pengoptimalan yang berbeda sesuai dengan jumlah poin yang ditambahkan berbeda.
Penambahan titik kurva eliptik (Penambahan Titik)
Anda dapat melihat berbagai algoritme untuk penambahan titik pada kurva eliptik dengan bentuk "Weierstrass pendek" dari situs ini.
Dengan asumsi bahwa koordinat Proyektif dari dua titik berturut-turut adalah (x1, y1, z1) dan (x2, y2, z2), hasil penjumlahan titik (x3, y3, z3) dapat dihitung dengan rumus perhitungan berikut.
Alasan untuk memberikan proses perhitungan secara rinci adalah untuk menunjukkan bahwa seluruh proses perhitungan sebagian besar merupakan operasi bilangan bulat. Lebar bit integer tergantung pada parameter kurva eliptik. Berikan lebar bit dari beberapa kurva eliptik umum:
模乘（Perkalian Modular）
Diberikan dua nilai pada bidang modulo: x dan y. Perhitungan perkalian modular mengacu pada x*y mod p. Perhatikan bahwa lebar bit bilangan bulat ini adalah lebar bit kurva elips. Algoritma klasik perkalian modular adalah perkalian Montgomery (MontgomeryMulplication). Sebelum melakukan perkalian Montgomery, perkalian harus dikonversi ke representasi Montgomery:
Rumus untuk menghitung perkalian Montgomery adalah sebagai berikut:
Ada banyak algoritma implementasi perkalian Montgomery: CIOS (Pemindaian Operan Terintegrasi Kasar), FIOS (Pemindaian Operan Terintegrasi Halus), dan FIPS (Pemindaian Produk Terintegrasi Halus) dan seterusnya. Artikel ini tidak memperkenalkan detail berbagai implementasi algoritma secara mendalam, dan pembaca yang tertarik dapat melakukan riset sendiri.
Untuk membandingkan perbedaan performa antara FPGA dan GPU, pilih metode implementasi algoritme paling dasar:
Sederhananya, algoritma perkalian modular dapat dibagi lagi menjadi dua perhitungan: perkalian bilangan besar dan penjumlahan bilangan besar. Setelah memahami logika perhitungan MSM, Anda dapat memilih performa perkalian modular (Throughput) untuk membandingkan performa FPGA dan GPU.
Amati dan pikirkan
Di bawah desain FPGA seperti itu, dapat diperkirakan bahwa seluruh VU9P dapat menyediakan throughput pada titik kurva eliptik BLS12_381. Penambahan titik (tambahkan_campur cara) membutuhkan sekitar 12 perkalian modular. Jam sistem FPGA adalah 450M.
Di bawah algoritme perkalian/penambahan modulus modular yang sama, menggunakan algoritme penambahan titik yang sama, titik plus Troughput dari Nvidia 3090 (mempertimbangkan faktor transmisi data) melebihi 500M/s. Tentu saja, keseluruhan kalkulasi melibatkan berbagai algoritme, beberapa algoritme mungkin cocok untuk FPGA, dan beberapa algoritme cocok untuk GPU. Alasan menggunakan perbandingan algoritma yang sama adalah untuk membandingkan kemampuan komputasi inti FPGA dan GPU.
Berdasarkan hasil di atas, rangkum perbandingan antara GPU dan FPGA dalam hal kinerja pembuktian ZKP:
Ringkas
Semakin banyak aplikasi yang mengadopsi teknologi bukti tanpa pengetahuan. Namun, ada banyak algoritma ZKP, dan berbagai proyek menggunakan algoritma ZKP yang berbeda. Dari pengalaman teknik langsung kami, FPGA adalah pilihan, tetapi GPU saat ini merupakan pilihan yang hemat biaya. FPGA lebih memilih komputasi deterministik, yang memiliki keunggulan latensi dan konsumsi daya. GPU memiliki programabilitas tinggi, memiliki kerangka kerja komputasi kinerja tinggi yang relatif matang, dan memiliki siklus iterasi pengembangan yang singkat, dan lebih memilih skenario throughput.