Mengukur kinerja SNARK: Frontend, backend, dan masa depan

SNARK (Succinct Non-interactive Arguments of Knowledge) adalah aplikasi pencarian primitif kriptografi yang penting untuk skalabilitas blockchain (misalnya, rollup L2) dan privasi. SNARK membiarkan seseorang membuktikan kepada pemverifikasi yang tidak percaya V (misalnya, blockchain Ethereum) bahwa mereka mengetahui beberapa data (misalnya, sekumpulan transaksi yang valid). Cara naif untuk membuktikan ini adalah dengan mengirim data ke V, yang kemudian bisa langsung mengecek keabsahannya. SNARK mencapai hal yang sama, tetapi dengan biaya yang lebih baik untuk V. Secara khusus, bukti SNARK harus lebih pendek daripada bukti naif yang terdiri dari data itu sendiri. (Untuk lebih detail, lihat draf buku teks saya, Bukti, Argumen, dan Pengetahuan Nol. Untuk pengenalan SNARK, lihat Sarah Meicklejohn's presentasi di kripto a16z Seri Penelitian Musim Panas.)

Biaya verifikasi untuk SNARK dapat bervariasi, tetapi dipahami dengan baik dan seringkali cukup baik. Sebagai contoh, PlonK bukti biaya sekitar 290,000 bensin untuk memverifikasi di Ethereum, sementara bukti StarkWare menghabiskan sekitar 5 juta gas. SNARK berpotensi berlaku dalam pengaturan yang beragam bahkan di luar blockchain — misalnya memungkinkan penggunaan yang cepat tetapi tidak tepercaya server dan perangkat keras. 

Tetapi karena verifikasi SNARK biasanya murah, penentu utama penerapannya adalah biaya SNARK prover. P. Dalam posting ini, saya menjelaskan cara memperkirakan biaya ini untuk menentukan kapan penggunaan SNARK masuk akal, dan bagaimana SNARK dapat ditingkatkan di masa depan. Perlu dicatat bahwa ini adalah ruang yang bergerak cepat, dan beberapa proyek yang dibahas dalam posting ini secara aktif meningkatkan kinerjanya.

Tapi pertama-tama: Bagaimana SNARK dikerahkan

Dalam penyebaran SNARK, pengembang biasanya menulis program komputer ψ yang mengambil sebagai input data w bahwa si pemikir mengaku tahu (w singkatan menyaksikan), dan periksa bahwa w adalah benar. Misalnya, dalam rollup, program akan memeriksa bahwa semua transaksi di w ditandatangani secara digital, tidak menyebabkan saldo akun turun di bawah nol, dan seterusnya. Program ψ kemudian diumpankan melalui Tampilan depan SNARK yang mengkompilasinya ke dalam format yang lebih sesuai dengan penerapan teknologi SNARK. Format ramah SNARK ini disebut sebagai representasi perantara (IR). 

Biasanya, IR adalah semacam contoh kepuasan sirkuit yang setara dengan ψ. Ini berarti bahwa sirkuit C mengambil sebagai input data w, serta beberapa input tambahan yang biasanya disebut "nasihat non-deterministik", dan berjalan ψ on w. Masukan saran digunakan untuk membantu C menjalankan ψ, sambil menjaga C kecil. Misalnya, setiap kali ψ membagi dua bilangan x dan y, hasil bagi q dan sisa r dapat diberikan sebagai saran untuk C, dan C hanya dapat memeriksa itu x = qy + r. Cek ini lebih murah daripada membuat C jalankan algoritma pembagian untuk menghitung q dan r dari awal.

Akhirnya, SNARK untuk kepuasan sirkuit diterapkan pada C. Ini disebut Bagian belakang SNARK. Untuk beberapa masalah yang sangat terstruktur seperti perkalian matriks, konvolusi, dan beberapa masalah grafik, SNARK yang dikenal ada yang menghindari paradigma frontend/backend ini dan dengan demikian mencapai pembuktian yang jauh lebih cepat. Tetapi fokus dari posting ini adalah pada SNARK tujuan umum.

Seperti yang akan kita lihat, biaya pembuktian dari backend SNARK tumbuh dengan C's ukuran. Penyimpanan C kecil dapat menjadi tantangan, karena sirkuit adalah format yang sangat terbatas untuk mengekspresikan perhitungan. Mereka terdiri dari gerbang, dihubungkan oleh kabel. Setiap gerbang g diberi makan beberapa nilai dan berlaku a sangat fungsi sederhana untuk nilai-nilai tersebut. Hasilnya kemudian dimasukkan ke gerbang "hilir" melalui kabel yang berasal dari g.

Skalabilitas SNARK: Berapa lama waktu yang dibutuhkan?

Pertanyaan kuncinya adalah, Berapa banyak lagi waktu yang dibutuhkan peribahasa SNARK, dibandingkan dengan hanya mengeksekusi ulang ψ pada datanya? Jawabannya adalah biaya overhead dari SNARK, relatif terhadap pemeriksaan saksi langsung. Ungkapan terakhir mengacu pada fakta bahwa, dalam bukti naif di mana P mengirimkan w untuk V, V pemeriksaan w's validitas dengan mengeksekusi ψ di atasnya. 

Akan sangat membantu untuk memecah overhead pembukti menjadi "overhead frontend" dan "overhead backend." Jika mengevaluasi sirkuit C gerbang demi gerbang adalah F kali lebih mahal daripada berlari ψ, maka kita katakan overhead frontend adalah F. Jika menerapkan pembukti backend ke C is B kali lebih mahal daripada mengevaluasi C gerbang demi gerbang, maka kita katakan bahwa overhead backend adalah B. Total overhead pembuktian adalah produk, F·B. Overhead multiplikatif ini bisa menjadi substansial bahkan jika F dan B secara individual sederhana. 

Dalam prakteknya, F dan B keduanya bisa sekitar 1000 atau lebih besar. Ini berarti total biaya pembuktian relatif terhadap pemeriksaan saksi langsung dapat mencapai 1 juta hingga 10 juta atau lebih. Program yang berjalan hanya satu detik di laptop dapat dengan mudah menyebabkan SNARK Prover yang membutuhkan waktu komputasi puluhan atau ratusan hari (single-threaded). Untungnya, pekerjaan ini biasanya dapat diparalelkan ke berbagai tingkat (tergantung pada SNARK). 

Singkatnya, jika Anda ingin menggunakan SNARK dalam aplikasi hari ini, maka salah satu dari tiga hal harus benar:

1. Pemeriksaan saksi langsung membutuhkan waktu kurang dari satu detik di laptop.
2. Pemeriksaan saksi langsung sangat cocok untuk representasi di sirkuit, sehingga overhead frontend kecil.
3. Anda bersedia menunggu berhari-hari hingga SNARK Prover selesai, dan/atau membayar sumber daya komputasi paralel yang sangat besar.

Tsisa posting ini menjelaskan dari mana overhead frontend dan backend berasal, dan bagaimana saya memperkirakannya untuk SNARK yang berbeda. Kami kemudian akan beralih ke prospek untuk perbaikan. 

Memisahkan frontend dan backend

Memisahkan sepenuhnya frontend dari backend dapat menjadi tantangan karena backend yang berbeda mendukung jenis sirkuit yang berbeda. Oleh karena itu, frontend dapat berbeda tergantung pada backend yang mereka harapkan untuk berinteraksi.

Backend SNARK umumnya mendukung apa yang disebut sirkuit aritmatika, yang berarti bahwa input ke sirkuit adalah elemen dari beberapa medan hingga, dan gerbang sirkuit melakukan penambahan dan perkalian dua elemen medan. Sirkuit ini secara kasar sesuai dengan program komputer garis lurus (tidak ada cabang, pernyataan bersyarat, dan sebagainya) yang bersifat aljabar — yaitu, tipe data primitifnya adalah elemen bidang. 

Sebagian besar backend sebenarnya mendukung generalisasi sirkuit aritmatika yang sering disebut instans Kepuasan Kendala Peringkat-1 (R1CS). Dengan pengecualian dari Groth16 dan pendahulunya, SNARK ini dapat dibuat untuk mendukung IR lain juga. Misalnya, StarkWare menggunakan sesuatu yang disebut Algebraic Intermediate Representation (AIR), yang juga mirip dengan gagasan yang disebut aritmetisasi PlonKish yang dapat didukung oleh PlonK dan backend lainnya. Kemampuan beberapa backend untuk mendukung IR yang lebih umum dapat mengurangi overhead frontend yang menghasilkan IR tersebut. 

Backend juga bervariasi dalam hal bidang terbatas yang mereka dukung secara asli. Saya akan membahas ini lebih lanjut di bagian berikutnya.

Berbagai pendekatan untuk frontend

Beberapa program komputer (sangat khusus) secara alami sesuai dengan sirkuit aritmatika. Salah satu contohnya adalah program komputer yang melakukan perkalian matriks secara naif pada beberapa bidang. Tetapi kebanyakan program komputer bukanlah garis lurus atau aljabar. Mereka sering melibatkan pernyataan bersyarat, operasi seperti pembagian bilangan bulat atau aritmatika floating point yang tidak secara alami sesuai dengan aritmatika medan hingga, dan banyak lagi. Dalam kasus ini, overhead frontend akan menjadi substansial. 

Salah satu pendekatan frontend yang populer adalah untuk menghasilkan sirkuit yang pada dasarnya mengeksekusi langkah demi langkah beberapa CPU sederhana, juga disebut mesin virtual (VM). Perancang frontend menentukan satu set "operasi primitif" yang analog dengan instruksi perakitan untuk prosesor komputer nyata. Pengembang yang ingin menggunakan frontend akan menulis "program pemeriksaan saksi" secara langsung dalam bahasa assembly atau dalam beberapa bahasa tingkat tinggi seperti Solidity, dan program mereka secara otomatis dikompilasi ke dalam kode assembly. 

Misalnya, StarkWare's Kairo adalah bahasa rakitan yang sangat terbatas di mana instruksi rakitan secara kasar mengizinkan penambahan dan perkalian pada bidang yang terbatas, pemanggilan fungsi, dan membaca dan menulis ke memori yang tidak dapat diubah (yaitu, tulis-sekali). VM Kairo adalah arsitektur von Neumann, yang berarti bahwa sirkuit yang dihasilkan oleh frontend pada dasarnya mengambil program Kairo sebagai input publik dan "menjalankan" program pada saksi. Bahasa Kairo adalah Turing Complete — meskipun set instruksinya terbatas, ia dapat mensimulasikan lebih banyak arsitektur standar, meskipun melakukannya mungkin mahal. Frontend Kairo mengubah program Kairo mengeksekusi T instruksi primitif ke dalam apa yang disebut "derajat-2 UDARA dengan T baris dan tentang 50 kolom.” Apa persis ini artinya tidak penting untuk pos ini, tetapi sejauh menyangkut SNARK, ini sesuai dengan sirkuit dengan antara 50 dan 100 gerbang untuk masing-masing T langkah-langkah CPU Kairo. 

RISC Nol mengambil pendekatan yang mirip dengan Kairo, tetapi dengan mesin virtual yang disebut Arsitektur RISC-V, arsitektur sumber terbuka dengan ekosistem perangkat lunak kaya yang semakin populer. Sebagai set instruksi yang sangat sederhana, merancang frontend SNARK yang efisien yang mendukungnya mungkin relatif mudah dikendalikan (setidaknya relatif terhadap arsitektur yang rumit seperti x86 atau ARM). Pada Mei, RISC Nol sedang memutar program mengeksekusi T instruksi RISC-V primitif menjadi AIR derajat-5 dengan 3T baris dan 160 kolom. Ini sesuai dengan sirkuit dengan setidaknya 500 gerbang per langkah CPU RISC-V. Perbaikan lebih lanjut diharapkan dalam waktu dekat.

Berbagai proyek zkEVM (misalnya, zkSync 2.0, Scroll, zkEVM Polygon) menjadikan mesin virtual (ya) Mesin Virtual Ethereum. Proses mengubah setiap instruksi EVM menjadi "gadget" yang setara (yaitu, sirkuit yang dioptimalkan yang mengimplementasikan instruksi) secara substansial lebih terlibat daripada arsitektur Kairo dan RISC-V yang lebih sederhana. Untuk ini dan alasan lainnya, beberapa proyek zkEVM tidak secara langsung mengimplementasikan set instruksi EVM melainkan mengkompilasi program Soliditas tingkat tinggi ke dalam bahasa rakitan lain sebelum mengubahnya menjadi sirkuit. Hasil kinerja dari proyek-proyek ini tertunda.

Proyek “CPU emulator” seperti RISC-V dan Cairo menghasilkan sirkuit tunggal yang dapat menangani semua program dalam bahasa rakitan terkait. Pendekatan alternatif adalah "seperti ASIC," menghasilkan sirkuit yang berbeda untuk program yang berbeda. Pendekatan seperti ASIC ini dapat menghasilkan sirkuit yang lebih kecil untuk beberapa program, terutama ketika instruksi perakitan yang dijalankan program pada setiap langkah waktu tidak bergantung pada input program. Misalnya, ini berpotensi menghindari overhead frontend sepenuhnya untuk program garis lurus seperti perkalian matriks naif. Tetapi pendekatan ASIC juga tampaknya sangat terbatas; sejauh yang saya tahu, tidak diketahui bagaimana menggunakannya untuk mendukung loop tanpa batas iterasi yang telah ditentukan. 

Komponen terakhir dari frontend overhead berasal dari fakta bahwa semua SNARK menggunakan sirkuit yang beroperasi pada bidang yang terbatas. CPU pada laptop Anda dapat mengalikan atau menambahkan dua bilangan bulat dengan satu instruksi mesin. Jika frontend mengeluarkan rangkaian di atas bidang karakteristik yang cukup besar, pada dasarnya dapat mensimulasikan perkalian atau penambahan itu melalui operasi bidang yang sesuai. Namun, menerapkan operasi lapangan pada CPU nyata biasanya akan memerlukan banyak instruksi mesin (walaupun beberapa prosesor modern memiliki dukungan asli untuk bidang tertentu). 

Beberapa backend SNARK memungkinkan pilihan bidang yang lebih fleksibel daripada yang lain. Misalnya, jika backend menggunakan grup kriptografi G, medan sirkuit harus sesuai dengan jumlah elemen dalam G, yang dapat membatasi. Selain itu, tidak semua bidang mendukung algoritme FFT praktis. 

Hanya ada satu SNARK yang diimplementasikan, Pengereman, yang secara native mendukung komputasi pada bidang arbitrer (cukup besar). Seiring dengan nya keturunan, ia memiliki kinerja pembukti beton tercepat yang diketahui bahkan di atas bidang yang didukung SNARK lain, tetapi buktinya saat ini terlalu besar untuk banyak aplikasi blockchain. Kerja terbaru berusaha untuk meningkatkan ukuran bukti, tetapi penyelidik secara asimtotik lebih lambat dan di sana kelihatan seperti hambatan untuk kepraktisan.

Beberapa proyek telah memilih untuk mengerjakan bidang dengan aritmatika yang sangat cepat. Sebagai contoh, Plonky2 dan yang lainnya menggunakan bidang karakteristik 2⁶⁴ - 2³² +1 karena aritmatika di bidang ini dapat diimplementasikan beberapa kali lebih cepat daripada di bidang yang kurang terstruktur. Namun, menggunakan karakteristik sekecil itu dapat menimbulkan tantangan dalam merepresentasikan aritmatika bilangan bulat secara efisien melalui operasi lapangan (misalnya, mengalikan dua bilangan bulat 32-bit yang tidak bertanda dapat menghasilkan hasil yang lebih besar daripada karakteristik bidang). 

 Namun tidak peduli apa, untuk semua SNARK populer saat ini untuk mencapai keamanan 128 bit (tanpa peningkatan biaya verifikasi yang signifikan), mereka harus bekerja pada bidang berukuran lebih besar dari 2¹²⁸. Sejauh yang saya tahu, ini berarti bahwa setiap operasi lapangan akan membutuhkan setidaknya sekitar sepuluh perkalian mesin 64-bit, dan lebih banyak penambahan dan operasi bitwise. Oleh karena itu, seseorang harus memperhitungkan setidaknya urutan besarnya overhead frontend karena kebutuhan akan sirkuit yang beroperasi di atas medan yang terbatas. 

Untuk meringkas, frontend yang ada yang menggunakan abstraksi mesin virtual menghasilkan sirkuit dengan gerbang 100x hingga 1000x per langkah mesin virtual, dan mungkin lebih untuk mesin virtual yang lebih rumit. Selain itu, aritmatika bidang hingga setidaknya 10x lebih lambat daripada instruksi analog pada prosesor modern (dengan kemungkinan pengecualian jika prosesor memiliki dukungan bawaan untuk bidang tertentu). “Pendekatan frontend ASIC” mungkin mengurangi beberapa biaya tambahan ini tetapi saat ini terbatas pada jenis program yang dapat didukungnya.

Apa hambatan backend?

SNARK untuk kepuasan sirkuit biasanya dirancang dengan menggabungkan protokol informasi-teoretis yang disebut "TIO polinomial” dengan protokol kriptografi yang disebut “skema komitmen polinomial.” Dalam kebanyakan kasus, hambatan konkret untuk Prover adalah skema komitmen polinomial. Secara khusus, SNARK ini memiliki proof yang secara kriptografis berkomitmen pada satu atau lebih polinomial yang derajatnya (setidaknya) |C|, jumlah gerbang dalam rangkaian C. 

Pada gilirannya, kemacetan beton dalam skema komitmen polinomial akan tergantung pada skema yang digunakan dan ukuran sirkuit. Tapi itu akan selalu menjadi salah satu dari tiga operasi berikut: menghitung FFT, eksponensial dalam grup kriptografi, atau Hash Merkle. Merkle-hashing biasanya merupakan hambatan hanya jika sirkuitnya kecil, jadi kami tidak akan membahasnya lebih lanjut. 

Komitmen polinomial berdasarkan log diskrit

Dalam komitmen polinomial berdasarkan kekerasan masalah logaritma diskrit dalam kelompok kriptografi G (KZG, Anti peluru, Perahu nelayan, dan Hyrax-komit), pembukti harus menghitung a Komitmen vektor Pedersen dengan koefisien polinomial. Ini melibatkan multi-eksponensial, dengan ukuran yang sama dengan derajat polinomial. Di SNARK, gelar ini biasanya ukurannya |C| sirkuit C.

Dilakukan secara naif, ukuran multi-eksponensial |C| membutuhkan sekitar 1.5·|C|·mencatat |G| ≈ 400·|C| operasi kelompok, dimana |G| menunjukkan jumlah elemen dalam grup G. Namun, ada sebuah pendekatan, yang disebut algoritma Pippenger, yang dapat mengurangi ini dengan faktor kira-kira log |C|. Untuk sirkuit besar (katakanlah, |C| 225), log ini |C| faktor secara konkret dapat menjadi 25 atau lebih, yaitu, untuk sirkuit besar, kami berharap bahwa komitmen vektor Pedersen dapat dihitung dengan sedikit di atas 10·|C| operasi kelompok. Setiap operasi kelompok pada gilirannya cenderung (sebagai stadion baseball yang sangat kasar) sekitar 10x lebih lambat dari operasi lapangan yang terbatas. SNARK yang menggunakan komitmen polinomial ini sama mahalnya dengan P sekitar 100·|C| operasi lapangan. 

Sayangnya, SNARK yang ada memiliki overhead tambahan di atas faktor 100x di atas. Sebagai contoh:

• tabah's prover, yang menggunakan komitmen polinomial Hyrax, harus dilakukan |C|^½ banyak multi-eksponensial masing-masing ukuran |C|^½, melemahkan percepatan dari algoritma Pippenger dengan faktor sekitar dua. 
• In Groth16, P harus bekerja pada grup yang cocok untuk berpasangan, yang operasinya biasanya setidaknya 2x lebih lambat daripada grup yang tidak ramah berpasangan. P juga harus melakukan 3 multi-eksponensial daripada 1. Gabungan, ini menghasilkan setidaknya faktor-6 tambahan yang melambat relatif terhadap 100·|C| perkiraan di atas. 
• Marlin dan PlonK juga membutuhkan pasangan, dan penyerbunya harus berkomitmen pada lebih dari 3 polinomial. 
• Untuk setiap SNARK yang menggunakan Anti peluru (misalnya, Halo2, yang kira-kira PlonK tetapi dengan Bulletproofs daripada komitmen polinomial KZG), peribahasa harus menghitung secara logaritmik banyak eksponensial selama fase "pembukaan" skema komitmen, dan ini sebagian besar menghapus kecepatan Pippenger apa pun. 

Singkatnya, SNARK yang diketahui menggunakan komitmen vektor Pedersen tampaknya memiliki overhead backend setidaknya 200x dan hingga 1000x atau lebih. 

Komitmen polinomial lainnya

Untuk SNARK yang menggunakan komitmen polinomial lain (seperti GRATIS dan Ligero-komit), hambatannya adalah bahwa peribahasa perlu melakukan FFT besar. Misalnya, dalam AIR derajat-2 yang diproduksi oleh Kairo (dengan 51 kolom dan T baris, satu per langkah CPU Kairo), Prover yang disebarkan StarkWare melakukan setidaknya 2 FFT per kolom, dengan panjang antara 16 ·T dan 32 ·T. Konstanta 16 dan 32 bergantung pada parameter internal FRI yang ditetapkan oleh StarkWare dan dapat dikurangi — tetapi dengan biaya peningkatan biaya verifikasi. 

Secara optimis, FFT dengan panjang 32·T membutuhkan waktu sekitar 64·T·catatan(32T) perkalian bidang. Ini berarti bahwa bahkan untuk nilai yang relatif kecil T (misalnya, T ≥ 2²⁰), jumlah operasi lapangan per kolom setidaknya 64·25·T= 1600·T. Jadi overhead backend tampaknya setidaknya ribuan. Selain itu, FFT besar mungkin lebih terhambat oleh bandwidth memori daripada operasi lapangan. 

Dalam beberapa konteks, overhead backend SNARK yang melakukan FFT besar dapat dikurangi dengan teknik yang disebut agregasi bukti. Untuk rollup, ini berarti bahwa P (layanan rollup) memecah batch besar transaksi menjadi, katakanlah, 10 batch yang lebih kecil. Untuk setiap batch kecil i, P menghasilkan bukti SNARK πi validitas batch. Tetapi P tidak memposting bukti ini ke Ethereum, karena ini akan menyebabkan peningkatan biaya gas hampir 10 kali lipat. Sebaliknya, SNARK diterapkan lagi, kali ini untuk menghasilkan bukti π menetapkan itu P tahu π₁ ...,π₁₀. Yaitu, saksi bahwa P mengaku tahu adalah sepuluh bukti₁,…,₁₀, dan pemeriksaan saksi langsung menerapkan prosedur verifikasi SNARK pada masing-masing alat bukti. Bukti tunggal ini π diposting ke Ethereum. 

Dalam komitmen polinomial seperti komitmen FRI dan Ligero, ada ketegangan yang kuat antara P waktu dan V biaya, dengan parameter internal bertindak sebagai tombol yang dapat menukar satu sama lain. Sejak π₁ ,…,₁₀ tidak diposting ke Ethereum, kenopnya dapat disetel sehingga bukti ini besar, dan memproduksinya lebih cepat. Hanya dalam aplikasi akhir SNARK, untuk mengagregasi π₁ ,…,₁₀ menjadi satu bukti π, apakah skema komitmen perlu dikonfigurasi untuk memastikan bukti kecil. 

StarkWare berencana untuk menyebarkan agregasi bukti dalam waktu dekat. Ini juga merupakan fokus dari proyek-proyek seperti Plonky2.

Apa hambatan lain untuk skalabilitas SNARK?

Posting ini berfokus pada peribahasa waktu, tetapi biaya pembuktian lainnya juga dapat menjadi hambatan skalabilitas. Sebagai contoh, untuk banyak backend SNARK, penyelidik perlu menyimpan beberapa elemen medan untuk setiap gerbang di C, dan biaya ruang ini bisa sangat besar. Misalnya, program ψ berjalan dalam satu detik pada laptop dapat melakukan mungkin satu miliar operasi primitif pada prosesor modern. Seperti yang telah kita lihat, secara umum orang harus mengharapkan C membutuhkan lebih dari 100 gerbang per operasi tersebut. Ini berarti 100 miliar gerbang, yang, tergantung pada SNARK, dapat berarti puluhan atau ratusan terabyte ruang untuk P. 

Contoh lain: banyak SNARK populer (misalnya, PlonK, Marlin, Groth16) memerlukan "upacara penyiapan tepercaya" yang rumit untuk menghasilkan "kunci pembuktian" yang terstruktur, yang harus disimpan oleh peribahasa. Sejauh yang saya tahu, upacara terbesar seperti itu menghasilkan kunci pembuktian yang mampu mendukung sirkuit dengan sekitar 2²⁸≈250 juta gerbang. Kunci pembuktian berukuran beberapa lusin gigabyte. 

Dalam konteks di mana agregasi bukti dimungkinkan, kemacetan ini dapat dikurangi secara substansial. 

Ke depan: prospek SNARK yang lebih terukur

Overhead frontend dan backend bisa tiga kali lipat atau lebih. Bisakah kita mengharapkan ini turun secara substansial dalam waktu dekat? 

Saya pikir kita akan - sampai titik tertentu. Pertama, backend tercepat saat ini (mis. tabah dan Pengereman, dan SNARK lain yang menggabungkan protokol sum-cek dengan komitmen polinomial) memiliki bukti besar — ​​biasanya akar kuadrat dalam ukuran sirkuit — jadi orang tidak benar-benar menggunakannya. Saya berharap ukuran proof dan waktu verifier akan berkurang secara berarti dalam waktu dekat melalui komposisi depth-one dengan SNARK small-proof. Mirip dengan agregasi bukti, ini berarti seorang ahli pertama-tama akan menghasilkan bukti SNARK π dengan SNARK “fast-prover, large-proof”, tetapi tidak mengirim π untuk V. Agak, P akan menggunakan SNARK kecil-bukti untuk menghasilkan bukti π' itu tahu π, dan kirim π' untuk V. Ini dapat mencukur urutan besarnya dari overhead backend SNARK yang populer saat ini. 

Kedua, akselerasi perangkat keras dapat membantu. Aturan umum yang sangat kasar adalah bahwa GPU dapat membeli 10x speedup lebih dari CPU, dan ASICs 10x speedup lebih dari GPU. Namun, saya memiliki tiga kekhawatiran di depan ini. Pertama, FFT besar mungkin terhambat oleh bandwidth memori daripada operasi lapangan, sehingga SNARK yang melakukan FFT seperti itu mungkin melihat percepatan terbatas dari perangkat keras khusus. Kedua, sementara posting ini berfokus pada bottleneck komitmen polinomial, banyak SNARK yang membutuhkan pembukti untuk melakukan operasi lain yang hanya sedikit lebih murah. Jadi memecahkan hambatan komitmen polinomial (misalnya, mempercepat multi-eksponensial di SNARK berbasis log diskrit) dapat meninggalkan operasi kemacetan baru yang tidak jauh lebih baik daripada yang lama. (Misalnya, SNARK termasuk Groth16, Marlin, dan PlonK juga memiliki FFT, selain multi-eksponensial.) Akhirnya, bidang dan kurva eliptik yang mengarah ke SNARK paling efisien dapat terus berkembang untuk beberapa waktu, dan itu dapat menciptakan tantangan untuk akselerasi Prover berbasis ASIC.

Di sisi frontend, kita mungkin semakin menemukan bahwa pendekatan "emulator CPU" dari proyek-proyek seperti Kairo, RISC Zero, zkEVMs, dan lainnya benar-benar berskala cukup baik (dalam hal kinerja) dengan kompleksitas set instruksi CPU. Memang, inilah harapan dari berbagai proyek zkEVM. Ini mungkin berarti bahwa, sementara overhead frontend tetap tiga kali lipat atau lebih, frontend berhasil mendukung VM yang semakin cocok dengan arsitektur CPU nyata. Kekhawatiran penyeimbang adalah bahwa frontend mungkin menjadi rumit dan sulit untuk diaudit, karena gadget berkode tangan yang menerapkan instruksi yang semakin rumit berkembang biak. Metode verifikasi formal kemungkinan akan memainkan peran penting dalam mengatasi masalah ini. 

Akhirnya, setidaknya dalam aplikasi blockchain, kami mungkin menemukan bahwa sebagian besar kontrak pintar yang muncul di alam liar terutama menggunakan instruksi sederhana yang ramah SNARK. Hal ini dapat memungkinkan overhead frontend yang rendah dalam praktik sambil mempertahankan generalitas dan pengalaman pengembang yang ditingkatkan yang datang dengan mendukung bahasa pemrograman tingkat tinggi seperti Solidity dan set instruksi yang kaya termasuk EVM. 

***

Justin Thaler is seorang Associate Professor di Universitas Georgetown. Sebelum bergabung dengan Georgetown, ia menghabiskan dua tahun sebagai Research Scientist di Yahoo Labs di New York, sebelum itu ia menjadi Research Fellow di Institut Simons untuk Teori Komputasi di UC Berkeley. 

***

Ucapan Terima Kasih: Saya berterima kasih kepada Burger Elena untuk mengusulkan topik posting ini, dan untuk Arasu Arun, Joseph Bonneau, dan Sam Ragsdale untuk komentar yang berwawasan. Terima kasih khusus juga kepada editor saya, Tim Sullivan.

***

Pandangan yang diungkapkan di sini adalah pandangan individu AH Capital Management, LLC (“a16z”) yang dikutip dan bukan pandangan a16z atau afiliasinya. Informasi tertentu yang terkandung di sini telah diperoleh dari sumber pihak ketiga, termasuk dari perusahaan portofolio dana yang dikelola oleh a16z. Meskipun diambil dari sumber yang dipercaya dapat dipercaya, a16z belum memverifikasi informasi tersebut secara independen dan tidak membuat pernyataan tentang keakuratan informasi yang bertahan lama atau kesesuaiannya untuk situasi tertentu. Selain itu, konten ini mungkin termasuk iklan pihak ketiga; a16z belum meninjau iklan tersebut dan tidak mendukung konten iklan apa pun yang terkandung di dalamnya.

Konten ini disediakan untuk tujuan informasi saja, dan tidak boleh diandalkan sebagai nasihat hukum, bisnis, investasi, atau pajak. Anda harus berkonsultasi dengan penasihat Anda sendiri mengenai hal-hal itu. Referensi ke sekuritas atau aset digital apa pun hanya untuk tujuan ilustrasi, dan bukan merupakan rekomendasi investasi atau penawaran untuk menyediakan layanan konsultasi investasi. Selanjutnya, konten ini tidak ditujukan atau dimaksudkan untuk digunakan oleh investor atau calon investor mana pun, dan dalam keadaan apa pun tidak dapat diandalkan saat membuat keputusan untuk berinvestasi dalam dana yang dikelola oleh a16z. (Penawaran untuk berinvestasi dalam dana a16z hanya akan dilakukan dengan memorandum penempatan pribadi, perjanjian berlangganan, dan dokumentasi lain yang relevan dari dana tersebut dan harus dibaca secara keseluruhan.) Setiap investasi atau perusahaan portofolio yang disebutkan, dirujuk, atau dijelaskan tidak mewakili semua investasi dalam kendaraan yang dikelola oleh a16z, dan tidak ada jaminan bahwa investasi tersebut akan menguntungkan atau bahwa investasi lain yang dilakukan di masa depan akan memiliki karakteristik atau hasil yang serupa. Daftar investasi yang dilakukan oleh dana yang dikelola oleh Andreessen Horowitz (tidak termasuk investasi yang penerbitnya tidak memberikan izin kepada a16z untuk mengungkapkan secara publik serta investasi yang tidak diumumkan dalam aset digital yang diperdagangkan secara publik) tersedia di https://a16z.com/investments /.

Bagan dan grafik yang disediakan di dalamnya hanya untuk tujuan informasi dan tidak boleh diandalkan saat membuat keputusan investasi apa pun. Kinerja masa lalu tidak menunjukkan hasil di masa depan. Konten berbicara hanya pada tanggal yang ditunjukkan. Setiap proyeksi, perkiraan, prakiraan, target, prospek, dan/atau pendapat yang diungkapkan dalam materi ini dapat berubah tanpa pemberitahuan dan mungkin berbeda atau bertentangan dengan pendapat yang diungkapkan oleh orang lain. Silakan lihat https://a16z.com/disclosures untuk informasi penting tambahan.