Jelaskan secara rinci dua alat SNARK baru yang diluncurkan oleh a16z crypto

Artikel ini berasal dari 16 z, penulis asli: Justin Thaler, disusun oleh penerjemah Odaily Planet Daily, Jessica.

Pada 10 Agustus, 16 z crypto meluncurkan alat baru berbasis SNARK Lasso dan Jolt, yang bersama-sama mewakili pendekatan baru untuk desain SNARK yang dapat meningkatkan kinerja rantai alat yang digunakan secara luas dengan urutan besarnya atau lebih; menyediakan lebih baik, lebih nyaman pengalaman pengembang, dan membuat audit lebih mudah.

SNARK (Argumen Pengetahuan Non-Interaktif Singkat) adalah protokol kriptografi di mana siapa pun dapat membuktikan kepada pemverifikasi yang tidak tepercaya bahwa ia mengetahui "saksi" yang memenuhi properti tertentu.

• Kasus penggunaan yang menonjol di Web 3 adalah agar L2 membuktikan kepada L1 bahwa mereka mengetahui tanda tangan digital yang mengesahkan serangkaian transaksi, sehingga tanda tangan itu sendiri tidak harus disimpan dan diverifikasi oleh jaringan L1, meningkatkan skalabilitas.
• Aplikasi di luar blockchain meliputi: dengan cepat membuktikan validitas semua keluaran yang dihasilkan oleh perangkat keras yang tidak dipercaya, memastikan bahwa pengguna dapat mempercayainya. Individu dapat membuktikan dengan cara tanpa pengetahuan bahwa otoritas tepercaya telah memberikan kredensial kepada mereka yang membuktikan bahwa mereka cukup umur untuk mengakses konten yang dibatasi usia tanpa mengungkapkan tanggal lahir mereka. Siapa pun yang mengirim data terenkripsi melalui jaringan dapat membuktikan kepada administrator bahwa data tersebut mematuhi kebijakan jaringan tanpa mengungkapkan detail lebih lanjut.

Sementara banyak SNARK tetap menjadi biaya yang menarik bagi pemverifikasi, SNARK biasanya masih memperkenalkan sekitar enam kali lipat biaya overhead dalam perhitungan pembukti. Pekerjaan ekstra yang ditanggung oleh pembukti sangat paralel, tetapi overhead jutaan kali sangat membatasi ruang lingkup penerapan SNARK.

**SNARK dengan lebih banyak keunggulan kinerja akan mempercepat L 2 dan juga memungkinkan pembuat membuka kunci aplikasi yang belum terbayangkan. **Inilah mengapa kami memperkenalkan dua teknologi terkait baru: Lasso, parameter pencarian baru yang dapat meningkatkan biaya pembuktian secara signifikan; Jolt, yang menggunakan Lasso untuk menyediakan kerangka kerja baru untuk apa yang disebut zkVM Dan desain front-end yang lebih luas untuk mendesain SNARK. Bersama-sama, mereka meningkatkan kinerja, pengalaman pengembang, dan kemampuan audit desain SNARK, yang pada gilirannya meningkatkan pembangunan di web 3.

Implementasi awal kami dari Lasso telah menunjukkan percepatan lebih dari 10x dibandingkan dengan parameter pencarian di toolchain halo 2 SNARK yang populer. Saat basis kode Lasso dioptimalkan sepenuhnya, kami mengharapkan peningkatan ~40x. Jolt menyertakan inovasi lain di atas Lasso, dan kami berharap ini mencapai kecepatan yang sama atau lebih baik daripada zkVM yang ada.

Temukan parameter, Lasso dan Jolt

Ujung depan SNARK adalah kompiler yang mengubah program komputer menjadi sirkuit yang dapat dicerna oleh ujung belakang SNARK. (Catatan: Sirkuit adalah model komputasi yang sangat terbatas di mana satu-satunya "operasi primitif" yang tersedia adalah penjumlahan dan perkalian.)

Alat utama dalam desain SNARK modern adalah protokol yang disebut parameter pencarian, yang memungkinkan pembukti yang tidak tepercaya untuk mengirimkan vektor besar secara kriptografis dan kemudian membuktikan bahwa setiap entri vektor tersebut terdapat di tengah tabel yang telah ditentukan sebelumnya. Parameter pencarian dapat membantu menjaga sirkuit tetap kecil dengan memproses operasi secara efisien yang tidak dihitung secara alami dengan penambahan dan perkalian kecil.

Namun, seperti yang dikatakan oleh Barry Whitehat dari Ethereum Foundation tahun lalu, "jika kita dapat secara efisien menentukan sirkuit hanya dengan menggunakan parameter pencarian, ini akan menghasilkan alat dan sirkuit yang lebih sederhana". Sirkuit yang kami rancang hanya melakukan pencarian. Seiring waktu, parameter pencarian "akan menjadi lebih efisien daripada batasan polinomial untuk hampir semua hal".

Visi ini sangat kontras dengan cara kerja saat ini, di mana pengembang menyebarkan SNARK dengan menulis program menggunakan bahasa khusus domain khusus yang mengkompilasi program ke dalam batasan polinomial, atau dengan mengkodekan batasan secara langsung. Toolchain ini banyak pekerjaan dan menyediakan banyak area permukaan untuk bug keselamatan-kritis untuk masuk. Bahkan dengan alat dan sirkuit yang rumit, kinerja SNARK masih lambat, yang membatasi penerapannya.

Lasso dan Jolt membahas ketiga masalah utama: kinerja, pengalaman developer, dan kemampuan audit, dan bersama-sama mewujudkan visi untuk menemukan singularitas. Lasso dan Jolt juga memaksa memikirkan kembali banyak kebijaksanaan yang diterima dalam desain SNARK.

Setelah memberikan latar belakang yang diperlukan, berikut ini meninjau kembali beberapa gagasan umum tentang kinerja SNARK dan menjelaskan bagaimana mereka dapat dioptimalkan dengan mempertimbangkan inovasi seperti Lasso dan Jolt.

Latar belakang desain SNARK: mengapa sangat lambat?

Sebagian besar backend SNARK memiliki pembukti secara kriptografis yang berkomitmen pada nilai setiap gerbang di sirkuit menggunakan skema komitmen polinomial. Prover kemudian membuktikan bahwa nilai yang diajukan memang sesuai dengan pelaksanaan yang benar dari pemeriksa saksi.

Saya mengacu pada karya pembukti dari skema komitmen polinomial sebagai biaya komitmen. **SNARK memiliki biaya bukti tambahan dari skema komitmen polinomial. Tetapi biaya komitmen seringkali menjadi hambatan. ** Lasso dan Jolt juga. Jika SNARK dirancang di mana biaya komitmen bukan biaya pembuktian utama, bukan berarti skema komitmen polinomial itu murah. Sebaliknya, itu berarti bahwa biaya lain lebih tinggi dari yang seharusnya.

Secara intuitif, tujuan komitmen adalah untuk meningkatkan kesederhanaan sistem bukti secara kriptografis dengan aman. Ketika seorang pembukti mengirimkan vektor nilai yang besar, kira-kira seolah-olah pembukti mengirimkan seluruh vektor ke pemverifikasi, sama seperti sistem pembuktian normal mengirimkan seluruh saksi ke pemverifikasi. Skema komitmen dapat mencapai hal ini tanpa memaksa validator untuk benar-benar menerima seluruh saksi—artinya tujuan skema komitmen dalam desain SNARK adalah untuk mengontrol biaya validator.

Tetapi metode kriptografi ini sangat mahal untuk pembukti, terutama dibandingkan dengan metode teori informasi yang digunakan SNARK di luar skema komitmen polinomial. Metode teoretis informasi hanya mengandalkan operasi medan terbatas. Dan operasi lapangan jauh lebih cepat daripada waktu yang dibutuhkan untuk mengirimkan elemen bidang arbitrer.

Komputasi komitmen melibatkan beberapa eksponensial (juga dikenal sebagai perkalian skalar ganda, atau MSM) atau FFT dan hash Merkle, bergantung pada skema komitmen polinomial yang digunakan. Lasso dan Jolt dapat menggunakan skema komitmen polinomial apa pun, tetapi memiliki biaya yang sangat menarik saat dibuat menggunakan skema berbasis MSM, seperti IPA/Bulletproofs, KZG/PST, Hyrax, Dory, atau Zeromorph.

Mengapa Lasso dan Jolt penting

Lasso adalah parameter pencarian baru di mana pembukti menjanjikan nilai yang lebih sedikit dan lebih kecil dari pekerjaan sebelumnya. Ini bisa menjadi percepatan 20x atau lebih, di mana percepatan 2 hingga 4x berasal dari nilai komitmen yang lebih sedikit, dan percepatan 10x lainnya berasal dari fakta bahwa semua nilai komitmen di Lasso kecil. Tidak seperti banyak parameter pencarian sebelumnya, Lasso (dan Jolt) juga menghindari FFT, yang menghabiskan banyak ruang dan dapat menjadi hambatan untuk instans besar.

Selain itu, Lasso bekerja bahkan dengan tabel besar, selama tabel tersebut "terstruktur" (dalam pengertian teknis yang tepat). Tabel ini terlalu besar untuk diimplementasikan secara eksplisit oleh siapa pun, tetapi Lasso hanya membayar untuk elemen tabel yang benar-benar diaksesnya. Secara khusus — dibandingkan dengan parameter pencarian sebelumnya — jika tabel terstruktur, maka tidak ada pihak yang perlu melakukan semua nilai dalam tabel dalam bentuk terenkripsi.

Lasso menggunakan dua konsep struktural yang berbeda: dekomposabilitas dan struktur LDE. (LDE adalah akronim untuk konsep teknis yang disebut Low Degree Extended Polynomial.) Penguraian secara kasar berarti bahwa satu pencarian tabel dapat dijawab dengan melakukan pencarian dalam jumlah yang lebih kecil pada tabel yang lebih kecil. Ini adalah persyaratan yang lebih ketat daripada struktur LDE, tetapi Lasso sangat efektif bila diterapkan pada tabel yang dapat didekomposisi.

Tersentak

Jolt (Just One Lookup Table) adalah frontend baru yang dibuka dengan kemampuan Lasso untuk menggunakan tabel pencarian besar. Jolt menargetkan abstraksi mesin/CPU virtual, juga dikenal sebagai Instruction Set Architecture (ISA). SNARK yang mendukung abstraksi ini disebut zkVM. Misalnya, pertimbangkan set instruksi RISC-V (termasuk ekstensi perkalian) yang juga ditargetkan oleh proyek RISC-Zero. Ini adalah ISA sumber terbuka populer yang dikembangkan oleh komunitas arsitektur komputer tanpa memikirkan SNARK.

Untuk setiap instruksi RISC-V fi, ide utama Jolt adalah membuat tabel pencarian yang berisi seluruh tabel evaluasi fi. Pada dasarnya untuk setiap instruksi RISC-V, tabel pencarian yang dihasilkan dapat didekomposisi dan berlaku laso.

Meninjau kembali kearifan yang diterima dalam desain SNARK

Lasso dan Jolt juga menumbangkan beberapa kebijaksanaan yang diterima dalam desain SNARK.

** # 1. SNARK area besar adalah pemborosan. Setiap orang harus menggunakan FRI, Ligero, Brakedown atau variannya, karena menghindari teknik kurva eliptik yang biasanya berlaku untuk skala besar. **

Ukuran bidang di sini kira-kira sesuai dengan ukuran angka yang muncul di bukti SNARK. Karena penjumlahan dan perkalian bilangan yang sangat besar itu mahal, gagasan bahwa SNARK pada bidang besar itu boros berarti kita harus berusaha merancang protokol yang tidak pernah memiliki bilangan besar. Komitmen berbasis MSM menggunakan kurva eliptik, yang biasanya ditentukan pada bidang besar (ukuran ~2 256), jadi janji ini memiliki reputasi kinerja yang buruk.

Apakah masuk akal untuk menggunakan bidang kecil (bahkan jika itu adalah opsi) sebagian besar bergantung pada aplikasi. Lasso dan Jolt melangkah lebih jauh. Mereka menunjukkan bahwa bahkan dengan skema komitmen berbasis MSM, pekerjaan pembukti hampir tidak bergantung pada ukuran lapangan. Ini karena, untuk komitmen berbasis MSM, ukuran nilai komitmen lebih penting daripada ukuran bidang tempat nilai tersebut berada.

SNARK yang ada membuat pembukti melakukan banyak elemen bidang acak. Misalnya, pembukti di backend SNARK populer yang disebut Plonk melakukan sekitar 7 elemen bidang acak (dan elemen bidang non-acak lainnya) per gerbang sirkuit. Elemen bidang acak ini bisa besar meskipun semua nilai yang muncul dalam perhitungan terbukti kecil.

Sebaliknya, Lasso dan Jolt hanya meminta pembukti untuk mengajukan nilai kecil (pembukti Lasso juga mengajukan nilai lebih sedikit dari parameter pencarian sebelumnya). Hal ini sangat meningkatkan kinerja skema berbasis MSM. Minimal, Lasso dan Jolt harus membongkar anggapan bahwa masyarakat harus meninggalkan komitmen berbasis MSM dalam kasus di mana kinerja pembukti penting.

**#2 Rangkaian instruksi yang lebih sederhana menghasilkan zkVM yang lebih cepat. **

Kompleksitas Jolt (per-instruksi) hanya bergantung pada ukuran input instruksi, selama tabel evaluasi untuk setiap instruksi dapat didekomposisi. Sentakan mendemonstrasikan bahwa instruksi yang sangat rumit dapat diuraikan, khususnya semua RISC-V.

Ini bertentangan dengan kepercayaan umum bahwa mesin virtual yang lebih sederhana (zkVM) harus mengarah ke sirkuit yang lebih kecil dan terkait dengan pembuktian yang lebih cepat (setiap langkah VM). Ini adalah motivasi pemandu di balik zkVM yang sangat sederhana seperti VM Kairo, yang dirancang khusus agar ramah SNARK.

Faktanya, untuk mesin virtual yang lebih sederhana, Jolt mencapai biaya komitmen yang lebih rendah untuk pembuktian daripada SNARK sebelumnya. Misalnya, untuk eksekusi VM Kairo, pembukti SNARK mengirimkan 51 elemen bidang pada setiap langkah VM. SNARK yang digunakan oleh Kairo saat ini bekerja pada bidang 251-bit (63 bit adalah batas bawah yang keras pada ukuran bidang yang dapat digunakan SNARK). Prover Jolt bekerja pada ~60 elemen bidang per langkah (mendefinisikan lebih dari tipe data 64-bit) untuk CPU RISC-V. Setelah memperhitungkan fakta bahwa elemen bidang yang dikirimkan kecil, biaya pembukti Jolt kira-kira setara dengan biaya pengiriman 6 elemen bidang 256-bit acak.

**#3 Tidak ada penalti kinerja untuk memecah perhitungan besar menjadi bagian-bagian kecil. **

Berdasarkan pandangan ini, proyek hari ini menguraikan sirkuit besar apa pun menjadi blok-blok kecil, membuktikan setiap blok secara terpisah, dan menggabungkan hasilnya secara rekursif melalui SNARK. Penyebaran ini menggunakan pendekatan ini untuk mengurangi kemacetan kinerja di SNARK populer. Misalnya, SNARK berbasis FRI membutuhkan ruang bukti hampir 100 GB, bahkan untuk sirkuit kecil. Mereka juga membutuhkan FFT, operasi ultra-linier yang dapat menjadi hambatan jika SNARK diterapkan "secara bersamaan" ke sirkuit besar.

Kenyataannya adalah bahwa beberapa SNARK (seperti Lasso dan Jolt) menunjukkan skala ekonomi (bukan skala disekonomis yang ditemukan di SNARK yang saat ini digunakan). Ini berarti bahwa semakin besar pernyataan yang dibuktikan, semakin kecil overhead pembukti relatif terhadap pemeriksaan saksi langsung (yaitu, pekerjaan yang diperlukan untuk mengevaluasi rangkaian saksi tanpa menjamin kebenaran). Pada tingkat teknis, skala ekonomi berasal dari dua tempat.

Percepatan Pippenger untuk MSM dengan ukuran n: peningkatan faktor log( n ) dibandingkan algoritme naif. Semakin besar n, semakin besar peningkatannya.

Dalam parameter pencarian seperti Lasso, pembukti membayar biaya "satu kali" yang bergantung pada ukuran tabel pencarian tetapi tidak ada hubungannya dengan jumlah nilai yang dicari. Biaya pembuktian satu kali diamortisasi untuk semua pencarian ke tabel. Blok yang lebih besar berarti lebih banyak pencarian, yang berarti amortisasi lebih baik.

Cara populer untuk berurusan dengan sirkuit besar saat ini adalah memecah berbagai hal menjadi bagian terkecil yang mungkin. Kendala utama pada ukuran setiap bagian adalah bahwa mereka tidak boleh terlalu kecil sehingga bukti agregasi rekursif menjadi hambatan bagi pembukti.

Lasso dan Jolt mengusulkan pendekatan yang pada dasarnya berlawanan. Orang harus menggunakan SNARK yang memiliki skala ekonomi. Kemudian hancurkan perhitungan besar menjadi potongan-potongan sebesar mungkin, dan ulangi hasilnya. Batasan utama pada ukuran setiap fragmen adalah ruang pembuktian, yang tumbuh seiring dengan semakin besarnya fragmen.

**#4 Pembatasan ketinggian diperlukan untuk SNARK yang efisien. **

Jolt menggunakan R 1 CS sebagai representasi perantaranya. Tidak ada manfaat menggunakan batasan Tinggi atau Kustom di Jolt. Sebagian besar biaya pembukti di Jolt terletak pada mencari parameter Lasso, daripada membuktikan kepuasan dari sistem kendala yang dihasilkan yang menerima pencarian begitu saja.

Jolt bersifat universal, sehingga tidak kehilangan keserbagunaannya. Dengan demikian, ini melawan fokus intens pengembang pada batasan ketinggian desain (sering kali ditentukan secara manual) dalam upaya untuk memeras peningkatan kinerja dari SNARK populer saat ini.

Tentu saja, beberapa konteks mungkin masih mendapat manfaat dari batasan tinggi atau kustom. Contoh penting adalah Minroot VDF, yang batasan 5 derajatnya dapat mengurangi biaya komitmen dengan faktor sekitar 3.

**#5 Skema komitmen polinomial jarang mahal dan harus dihindari sebisa mungkin. **

Ini adalah kritik utama terhadap sistem pengekangan yang baru diperkenalkan yang disebut CCS dan SNARK yang mendukungnya - Spartan dan Marlin, CCS adalah generalisasi yang jelas dari semua sistem pengekangan yang lazim dalam praktik saat ini.

Kritik ini tidak berdasar. Faktanya, inti teknis dari Lasso dan Jolt adalah skema komitmen polinomial yang jarang di Spartan - Spark. Spark sendiri adalah konversi umum dari skema komitmen polinomial (non-jarang) apa pun ke skema yang mendukung polinomial jarang.

Lasso mengoptimalkan dan memperluas Spark untuk memastikan bahwa pembukti hanya berkomitmen pada nilai "kecil", tetapi bahkan tanpa pengoptimalan ini, kritik tidak dapat dibenarkan. Nyatanya, pembuktian Spartan berkomitmen pada elemen bidang (acak) yang lebih sedikit daripada SNARK (seperti Plonk yang menghindari komitmen polinomial yang jarang).

Pendekatan Spartan memiliki keunggulan kinerja tambahan, terutama untuk sirkuit dengan struktur berulang. Untuk sirkuit ini, gerbang tambahan tidak menambah karya kriptografi dari pepatah Spartan. Pekerjaan ini hanya tumbuh dengan jumlah variabel dalam sistem kendala yang diberikan, bukan dengan jumlah kendala. Tidak seperti Plonk, Prover Spartan tidak perlu mengirimkan beberapa "salinan" yang berbeda dari variabel yang sama.

Kami optimis bahwa Lasso dan Jolt akan secara dramatis mengubah cara SNARK dirancang, meningkatkan kinerja, dan kemampuan audit. Ini adalah alat kunci dengan kemampuan luar biasa untuk meminimalkan biaya komitmen pembukti.